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

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

Вот описание одной итерации алгоритма на C. У нас есть два буфера констант с байтами «слева» и «справа» (данные, которые мы сравниваем), и общий изменяемый массив int32, называемый вектором. '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-байтовое слово не влияла на соседние слова). Будет ли такой общий вектор работать хорошо?

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


gpu opencl gpgpu
person fish    schedule 04.06.2011    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вы можете попробовать. У графического процессора будут серьезные проблемы с циклом 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;
       }
   }

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

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

person DarkZeros    schedule 06.06.2011