Может ли Myers Diff работать на графических процессорах? - PullRequest
Новая
       82

Может ли Myers Diff работать на графических процессорах?

1 голос
/ 04 июня 2011

Я заинтересован в том, чтобы ускорить реализацию Myers diff, запустив ее на GPU, то есть с OpenCL. У меня хорошее понимание алгоритма, но я новичок в программировании на GPU. Я догадываюсь, что GPU не будет работать хорошо, но я хотел бы услышать мысли и идеи.

Вот описание одной итерации алгоритма на языке C. У нас есть два постоянных буфера байтов 'left' и 'right' (данные, которые мы сравниваем) и общий изменяемый массив int32, называемый vector. 'idx' - это индекс итерации. Тогда алгоритм по сути такой: 

   void myers_diff_iteration(const uint8 *left, const uint8 *right, int32 *vector, int32 idx) {
       int32 x = MAX(vector[idx-1], vector[idx+1]);
       int32 y = idx - x;
       while (left[x] == right[y]) {
           x++;
           y++;
       }
       vector[x] = x;
   }

Я предполагаю, что цикл while (который имеет очень непредсказуемое количество итераций, в диапазоне от нуля до миллиона), вероятно, будет очень плохим для графического процессора и устранит любой выигрыш в производительности. Это правда? Любые советы, как это улучшить?

Кроме того, вектор является общим для всех итераций цикла. Каждая итерация выполняет запись в другое место, поэтому синхронизация не требуется (кроме того, что запись в выровненное 4-байтовое слово не влияет на соседние слова). Будет ли такой общий вектор работать хорошо?

Спасибо за любую помощь!

1 Ответ

2 голосов
/ 06 июня 2011

Вы можете попробовать. У графического процессора будут серьезные проблемы с циклом while, но пока выполняется достаточно «итераций» (потоков), скорость не должна уменьшаться.

Вы можете переписать это так: 

   void myers_diff_iteration(const uint8 *left, const uint8 *right, int32 *vector, int32 idx) {
       int id = get_global_id(0);
       int32 x = MAX(vector[idx-1], vector[idx+1]) + id;
       int32 y = idx - x + id;
       if (left[x] != right[y]) {
           vector[x] = x;
       }
   }

Только тогда вам нужно запустить максимальное число потоков. Но он будет выдавать только 1 результат вектора при каждом запуске OpenCL.

Лучше всего попробовать, а потом сделать несколько вариантов.

...