Параллельные вычисления в ИММ УрО РАН
 
 
Институт автоматики и процессов управления ДВО РАН
СМИРНОВ Сергей Викторович

Инструкция по применению программной имитации векторного вычислителя на процессорном элементе с INTEL860

Вычисления с двойной точностью (длина слова 64-разряда)

ВМЕСТО ВВЕДЕНИЯ

Я призываю внимательнейшим образом изучить штатные средства оптимизации программ, предоставляемые транслятором. Если они Вас не удовлетворяют, обратитесь к программам из известных пакетов производства Kuck & Associates,Inc. Описание их есть в ОСО ИММ, названия библиотек: libksign.a и libkmath.a. Но если и это Вас не устроило, значит Вас хорошенько припекло и Вы подготовлены к освоению векторного вычислителя.

ОБЩАЯ ИДЕЯ ОРГАНИЗАЦИИ ВЕКТОРНЫХ ВЫЧИСЛЕНИЙ

Проще всего взять половину кэш-памяти (4096 байт), нарезать ее на куски, которые можно назвать векторными регистрами (в.регистрами), и выдавать команды: - записать в основную память (ОП) в.регистр, - загрузить из ОП в.регистр, (реализованы с помощью pfld) - выполнить в.операцию, с указанием входных и выходного в.регистров. Чтобы в.регистры не вытеснялись из кэш-памяти, надо запретить обновление этой половины кэш-а.

ПОЧЕМУ ВЕКТОРНЫЕ РЕГИСТРЫ ВЫРАВНИВАЮТСЯ НА ГРАНИЦУ 16-ТИ БАЙТНОГО СЛОВА

Дело в том, что самый быстрый обмен с кэш-памятью производится 16-ти байтными словами. Если обмениваться 8-ми байтными словами, то количество команд обмена увеличивается вдвое, и просто невозможно все это записать в коротком цикле. Поэтому универсализмом жертвуют в погоне за скоростью вычислений. Чтобы пользователь не заметил этого жульничества, всю скучную и кропотливую работу с кэш-памятью, в том числе и выравнивание, создатели транслятора поручают векторизатору. И Вам очень повезло, если транслятор делает то, что Вам надо.

ЧТО ДЕЛАТЬ, ЕСЛИ ВЕКТОРНЫХ РЕГИСТРОВ ОБЩЕЙ ДЛИНОЙ 4096 БАЙТ ВАМ НЕ ХВАТАЕТ

Прежде всего, воспользуйтесь менее прожорливым алгоритмом и оцените, стоит ли еще ускорять вычисления. Учтите, что в CRAY-1 всего восемь векторных регистров длиной 64 с элементами в 64 разряда, и это в сумме составляет ровно 4096 байт!!! Если Вы все-таки решили пойти по этому пути, то в Вашем распоряжении весь кэш для данных. И здесь есть выбор: или захватить весь кэш, что приведет к замедлению при обслуживании внешнего цикла, или все-таки поделиться с транслятором и уступить ему часть кэш-памяти под автоматические переменные. Чтобы воспользоваться второй возможностью, надо определить, где эти переменные размещаются. Для этого вычисляем адрес стека до входа в подпрограмму и после входа, автоматические переменные расположены в этом диапазоне.

РАЗМЕЩЕНИЕ ВЕКТОРНЫХ РЕГИСТРОВ В ПОЛОВИНЕ КЭШ-ПАМЯТИ

Прежде всего, необходимо иметь два участока оперативной памяти размером по 4096 байт и с адресами V_Regs и V_Flush, начало каждого выровнено на границу 32-х байтного слова. Предположим, что Вы хотите отвести под в.регистры половину кэша с номером 0, тогда в половине кэша с номером 1 не должно быть элементов из этото участка. Это будет так, если Вы захватили память и еще не работали с ней, но в общем случае производится предварительная прочистка:
  1. вызывается подпрограмма cache_replacement( 1, V_Flush, 256 ); где V_Flush - адрес участка оперативной памяти, который предназначен только для прочистки.
  2. Вызывается подпрограмма cache_replacement( 0, V_Regs, 256 ); Теперь прежнее содержание половины кэша с номером 0 вытеснено в основную память, а взамен там расположилась копия того, что расположено в основной памяти по адресу V_Regs. Чтобы в.регистры не вытеснялись в основную память, надо запретить обновление той половины кэш-памяти, где они расположены:
  3. Вызывается подпрограмма grab_cache_way( 0 ); Приступаем к раздаче памяти под отдельные в.регистры V_Reg1, V_Reg2, ...:
      V_Reg1 = &(V_Regs[0]);   V_Reg2 = &(V_Regs[64]);  
      V_Reg2 = &(V_Regs[128]); ...
    
    В этом примере вектор содержит 64 элемента. После окончания работы с в.регистрами кэш-память нужно отпереть:
  4. вызывается подпрограмма ungrab_cache;
                       ОПИСАНИЕ ВЫЗОВА ПРОГРАММ /Си

            1. ПРОГРАММЫ ДЛЯ ОРГАНИЗАЦИИ ВЕКТОРНЫХ РЕГИСТРОВ
void *sp_addr();
cache_replacement( long, void *, long );
grab_cache_way( long );
ungrab_cache( );

Программа:          void cache_replacement( long, void *, long )
Назначение:         прописывает половину кэш-памяти для данных
                    заданным кол-вом слов длиной 16 байт из основной памяти,    
                    начиная с указанного адреса
Описание входных параметров: 
 номер описание                       назначение
   1 -     long - указывает какую именно половину половину кэша надо прописать;
                  возможные значения: 0 или 1
   2 - double * - адрес ОП, выровненный на границу 32-байтного слова
   3 -     long - число слов длиной 16 байт, чтобы прописать половину 
                  кэш-памяти надо указать 256.
Замечание:        Если в другой половине кэш-памяти уже находятся данные с
                  адресами из указанного диапазона, то никаких действий 
                  не производится  

Программа:        void grab_cache_way( long )
Назначение:         запрещает обновление указанной половины кэш-памяти
Описание входных параметров: 
 номер описание                       назначение
   1 -     long - указывает какую именно половину половину кэша запрещено
                  обновлять; возможные значения: 0 или 1

Программа:        void ungrab_cache();
Назначение:         отменяет все запреты на обновление кэш-памяти

Программа:        void *sp_addr();
Назначение:         возвращает текущий адрес стека

                2. ПРОГРАММЫ ВЕКТОРНОЙ ОБРАБОТКИ
void abxpy8p( double *, double, double, double *, double *, long, long ); 
void axpb8( double *, double, double *, double, long ); 
void axpb8s( double *, double, double *, double, long ); 
void axpy8( double *, double, double *, double *, long ); 
void axpy8axl( double *, double, double *, double *, double *, long ); 
void axpy8p( double *, double, double *, double *, long ); 
void axpy8pl( double *, double, double *, double *, double *, long ); 
void axpy8ql( double *, double, double *, double *, double *, long ); 
void axpy8s( double *, double, double *, double *, long ); 
double dot8( double *, double *, long ); 
double dot8pl( double *, double *, double *, long ); 
void dot8plr( double *, double *, double *, long ); 
void strin8( double *, double *, long, long );
void strout8( double *, double *, long );
void xmxy8( double *, double *, double *, long ); 
void zxpy8( double *, double *, double *, double *, long ); 
void zxpy8p( double *, double *, double *, double *, long ); 

____________________________________________________________________________
программа              размер   параметр    расположение   выравнивание 
                       кода,    /к чему     данных         на границу 16-байт
                       байт     относится/  (КЭШ или ОП)
____________________________________________________________________________
abxpy8p(V,a,b,X,Y,N,M) 864      1/V/         кэш            да
                                2/a/          -             -
                                3/b/          -             -
V[i]=a*X[i]+Y[i]                4/X/         ОП             нет
0 <= i < N                      5/Y/         кэш            да
N <= i < M                      6/N/          -             -
                                7/M/          -             -
____________________________________________________________________________
axpb8(V,a,X,b,N)       416      1/V/         кэш            да
                                2/a/          -             -
V[i]=a*X[i]+b                   3/X/         кэш            да
0 <= i < N                      4/b/          -             -
                                5/N/          -             -
____________________________________________________________________________
axpb8s(V,a,X,b,N)      320      1/V/         ОП             нет
                                2/a/          -             -
V[i]=a*X[i]+b                   3/X/         кэш            да
0 <= i < N                      4/b/          -             -
                                5/N/          -             -
____________________________________________________________________________
axpy8(V,a,X,Y,N)       480      1/V/         кэш            да
                                2/a/          -             -
V[i]=a*X[i]+Y[i]                3/X/         кэш            да
0 <= i < N                      4/Y/         кэш            да
                                5/N/          -             -
____________________________________________________________________________
axpy8axl(V,a,X,Y,Z,N)  384      1/V/         кэш            да
                                2/a/          -             -
V[i]=a*X[i]+Y[i],               3/X/         ОП             нет
Z[i]=a*X[i],                    4/Y/         кэш            да
0 <= i < N                      5/Z/         кэш            да
                                6/N/          -             -
____________________________________________________________________________
axpy8p(V,a,X,Y,N)      352      1/V/         кэш            да
                                2/a/          -             -
V[i]=a*X[i]+Y[i]                3/X/         ОП             нет
0 <= i < N                      4/Y/         кэш            да
                                5/N/          -             -
____________________________________________________________________________
axpy8pl(V,a,X,Y,Z,N)   384      1/V/         кэш            да
                                2/a/          -             -
V[i]=a*X[i]+Y[i],               3/X/         ОП             нет
Z[i]=X[i],                      4/Y/         кэш            да
0 <= i < N                      5/Z/         кэш            да
                                6/N/          -             -
____________________________________________________________________________
axpy8ql(V,a,X,Y,Z,N)   384      1/V/         кэш            да
                                2/a/          -             -
V[i]=a*X[i]+Y[i],               3/X/         кэш            да
Z[i]=Y[i],                      4/Y/         ОП             нет
0 <= i < N                      5/Z/         кэш            да
                                6/N/          -             -
____________________________________________________________________________
axpy8s(V,a,X,Y,N)      352      1/V/         ОП             нет
                                2/a/          -             -
V[i]=a*X[i]+Y[i]                3/X/         кэш            да
0 <= i < N                      4/Y/         кэш            да
                                5/N/          -             -
____________________________________________________________________________
a=dot8(X,Y,N)         320       1/X/         кэш            да
  i < N                         2/Y/         кэш            да
a=SUM(X[i]*Y[i]),               3/N/          -             -
  i=0
____________________________________________________________________________
a=dot8pl(X,Y,Z,N)     384       1/X/         ОП             нет
  i < N                         2/Y/         кэш            да
a=SUM(X[i]*Y[i]),               3/Z/         кэш            да
  i=0                           4/N/          -             -
Z[i]=Y[i],   0 <= i < N 
____________________________________________________________________________
dot8plr(X,Y,V,N)      320       1/X/         ОП             нет
     j < N                      2/Y/         кэш            да
V[i]=SUM(X[j]*Y[j]),            3/Z/         кэш            да
     j=0                        4/N/          -             -
0 <= i < N 
____________________________________________________________________________
strin8(X,V,N,M)       128       1/X/         ОП             нет
                                2/V/         кэш            нет
V[i]=X[M*i],                    4/N/          -             -
0 <= i < N                      4/M/          -             -
____________________________________________________________________________
strout8(X,V,N)        160       1/X/         кэш            да
V[i]=X[i],                      2/V/         ОП             нет
0 <= i < N                      3/N/          -             -
____________________________________________________________________________
xmxy8(V,X,Y,N)        448       1/V/         кэш            да
                                2/X/         кэш            нет
V[i]=(X[i]-X[i-1])*Y[i]         3/Y/         кэш            нет
0 <= i < N                      4/N/          -             -
____________________________________________________________________________
zxpy8(V,Y,X,Z,N)      288       1/V/         кэш            да
                                2/Y/         кэш            да
V[i]=Z[i]*X[i]+Y[i]             3/X/         кэш            да
0 <= i < N                      4/Z/         кэш            да
                                5/N/          -             -
____________________________________________________________________________
zxpy8p(V,Z,X,Y,N)     448       1/V/         кэш            да
                                2/Z/         ОП             нет
V[i]=Z[i]*X[i]+Y[i],            3/X/         кэш            да
0 <= i < N                      4/Y/         кэш            да
                                5/N/          -             -
____________________________________________________________________________

ВМЕСТО ЗАКЛЮЧЕНИЯ

Теперь, когда есть инструмент для работы с векторными регистрами, можно приступить к существенному пополнению набора программ. Источником является библиотека векторных примитивов PGCLIB. Векторизатор транслятора подставляет вместо определенных циклов вызовы подпрограмм именно из этой библиотеки. Приведенные выше программы векторной обработки, по-существу, являются дополнением к этой библиотеке. Особенно ценными в PGCLIB являются программы вычисления функций сразу для всех элементов вектора аргументов.