Параллельная обработка данных


Легко ли достичь пиковой производительности компьютера CRAY C90? - часть 3


Алгоритм в таком виде не мог быть векторизован, выполнялся в скалярном режиме, а значит не мог в принципе получить никакого выигрыша от параллельной структуры компьютера CRAY Y-MP C90.

Немного подумав, нетрудно понять, каким образом можно модифицировать данный алгоритм и сделать его основную часть векторизуемой. Ясно, что, начиная с некоторого номера i0, смещения пакуемых секций всех элементов массива A в массиве B будут повторяться, причем будут повторяться циклически с периодом не более, чем 63 (число разрядов в слове данного компьютера равно 64, но знаковый разряд в каждом элементе B(j) надо было пропускать). Поэтому битовые секции всех элементов A(ibeg+i*63), i=0... для каждого фиксированного значения ibeg=1...63 будут расположены, начиная с одного и того же смещения в элементах массива B, причем эти элементы массива B будут расположены так же с некоторым фиксированным шагом! Становиться понятной общая схема нового алгоритма: упаковку первых 63 элементов делаем как и прежде в скалярном режиме, запоминая смещения в элементах массива B и определяя шаг по этому массиву, а затем в векторном режиме располагаем секции элементов A(ibeg+i*63), i=1... для каждого значения ibeg отдельно. После реализации второго алгоритма оказалось, что время его работы в 30 раз (!) меньше времени работы первого алгоритма. Основная причина очевидна - значительное увеличение доли операций Г2, выполняемых в векторном режиме.

Примерная схема первого варианта (каждая итерация ждет окончания предыдущей для определения смещения в слове массива B):

  • выделение битовой секции из A(i)

  • запись в B(j) с позиции p

  • если вся секция в B(j) не поместилось, то переносим остаток в B(j+1), j=j+1,

  • модификация p, i=i+1

  • следующий шаг

Примерная схема векторного варианта:

  • определение смещений (p[ibeg]) для первых 63 элементов массива A - для каждого ibeg=1,63:

  • выделение битовой секции из A(i*63+ibeg)

  • запись очередной секции в B(j) с позиции p[ibeg]

  • i=i+1, j=j+bstep

Следующие два фактора, снижающие реальную производительность (они же определяют невозможность достижения пиковой производительности) - секционирование длинных векторных операций на порции по 128 элементов и время начального разгона конвейера, относятся к накладным расходам на организацию векторных операций на конвейерных функциональных устройствах.


Начало  Назад  Вперед



Книжный магазин