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



Легко ли достичь пиковой производительности компьютера 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 элементов и время начального разгона конвейера, относятся к накладным расходам на организацию векторных операций на конвейерных функциональных устройствах.


Содержание  Назад  Вперед