Диссертация (1149957), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Внешний цикл, является потенциальным циклом по блокам k-гоизмерения массива A; внутренний цикл является потенциальным циклом поэлементам блоков k-го измерения массива A.Если некоторое обращение к массиву A имеет вид A[BlockSiz e * f(di) + g(i)] ивыполняются следующие условия:1. di – счетчик внешнего цикла, i – счетчик внутреннего цикла.2. BlockSize - размер блока по k-му измерению;3. 0  f(di)  N/BlockSiz e , 0  g(i)  BlockSize ,то di k  f (di) , wi k  g (i) .Пример 9:Листинг 16. Гнездо циклов, удовлетворяющее условиям варианта 1// локальный индекс блокаfor (di = 0; di <= N/BlockSize; ++di)// локальный счетчик элемента внутри блокаfor (i = 0; i <BlockSize; ++i)A[di*BlockSize+i] (1) = di*BlockSize+i;Для вхождения (1) одномерного блочно размещаемого массива A di1  di ,wi 1  i .Вариант 2.

Внешний цикл, является потенциальным циклом по блокам k-гоизмерения массива A; внутренний цикл является потенциальным циклом поадресам элементов блоков i-го измерения массива A.Если некоторое обращение к массиву A имеет вид A[i  free_coef] ивыполняются следующие условия:1. di – счетчик внешнего цикла, i – счетчик внутреннего цикла.2. BlockSize - размер блока по k-му измерению.933. free_coef  BlockSize - некоторая константа.4.  k: k * BlockSize  i + free_coef < (k + 1) * BlockSize .то di k  k , wi k  i  free _ coef  k * BlockSize .Пример 10:Листинг 17. Гнездо циклов, удовлетворяющее условиям варианта 2// локальный индекс блокаfor (di = 0; di <= N/BlockSize; ++di)// глобальный счетчик элемента внутри блокаfor (i = MAX(0, di*BlockSize); i <MIN(N, (di+1)*BlockSize-2); ++i)A[i+2] (1) = i;Для вхождения (1) одномерного блочно размещаемого массива A верныравенства di1  di и wi 1  i  2  di * BlockSize .Вариант 3.

Внешний цикл, является потенциальным циклом по адресам блоков kго измерения массива A; внутренний цикл является потенциальным циклом поэлементам блоков k-го измерения массива A.Если некоторое обращение к массиву A имеет вид A[di  g(i)] и выполняютсяследующие условия:1. di – счетчик внешнего цикла, i – счетчик внутреннего цикла.2.

BlockSize - размер блока по k-му измерению;3. 0  g(i)  BlockSize ,то di k  di / BlockSize , wi k  g (i) .94Пример 11:Листинг 18. Гнездо циклов, удовлетворяющее условиям варианта 3// глобальный индекс блокаfor (di = 0; di < N; di+=BlockSize)// локальный счетчик элемента внутри блокаfor (i = 0; i < MIN(N-di,BlockSize); ++i)A[di+i] = di+i;Для вхождения (1) одномерного блочно размещаемого массива A верныравенства di1  di / BlockSize и wi 1  i .Вариант 4. Внешний цикл, является потенциальным циклом по адресам блоков kго измерения массива A; внутренний цикл является потенциальным циклом поадресам элементов блоков i-го измерения массива A.Если некоторое обращение к массиву A имеет вид A[i  free_coef] ивыполняются следующие условия:1.

di – счетчик внешнего цикла, i – счетчик внутреннего цикла.2. BlockSize - размер блока по k-му измерению.3. free_coef  BlockSize - некоторая константа.4.  k: di  k * BlockSize  i + free_coef < di  (k + 1) * BlockSize .тоdi k  di / BlockSize  k , wi k  i  free _ coef  dik * BlockSize .Пример 12:Листинг 19. Гнездо циклов, удовлетворяющее условиям варианта 4// глобальный индекс блокаfor (di = 0; di < N; ++di)// глобальный счетчик элемента внутри блокаfor (i = MAX(di,0); i < MIN(di+BlockSize,N); ++i)95A[i] (1) = i;Для вхождения (1) одномерного блочно размещаемого массива Adi1  di / BlockSize , wi 1  i  di1 * BlockSize .Вариант 5 (Общий случай).Если некоторое обращение к массиву A имеет вид A[f(i )] и выполняетсяусловие 0  f(i) < N , то di1  f (i) / BlockSize , wi 1  f (i)% BlockSize .Выше для каждого из вариантов 1-5 записи циклов описан алгоритмполучения wi k и di k . Для варианта 1 генерация индексов является самой быстрой,т.к.

не требует дополнительных вычислений. Для вариантов 2-4 вычисленийпроизводится несколько больше. Вариант 5 является самым медленным, т.к. в немиспользуются операции деления и деления по модулю, которые являютсяресурсоемкими.4.6.Алгоритм блочного размещения данных.Алгоритм блочного размещения данных реализован в ОРС в видеотдельногопреобразования,котороеприменяетсяккаждойфункции,определенной в исходной программе. При анализе конкретной функциипроизводится поиск всех директив блочного размещения данных, которымианнотируются: Объявления блочных массивов.

Перед ними ставится директива #pragmaops block_array_declare. Операторы выделения памяти под блочные массивы. Перед ними ставитсядиректива block_array_allocate. Операторы выделения памяти под блочные массивы. Перед ними ставитсядиректива block_array_release.96Для каждого аннотированного массива производится проверка на то, что егоможно разместить блочно. Единственное требование, которое накладывается наблочно размещаемый массив, заключается в том, чтобы к обращениям массива неприменялись операции адресной арифметики, за исключением быть можетоператоров,аннотированныхдирективамииblock_array_allocateblock_array_release.Далеевыраженийпроизводитсяблочнодвухшаговыйразмещаемыхалгоритммассивов.Нагенерациикаждоминдексныхшагестроитсяспециальная таблица.

С каждой строкой таблицы сопоставлено вхождение pмерного массива Al , а также измерение k ( 0  k  p ). С каждым столбцомсопоставляется цикл, который встречается в тексте программы. Если индекс Al поизмерению k линейно зависит от счетчика i некоторого цикла, то всоответствующей ячейке таблицы находится коэффициент при i. Рассмотримпример построения такой таблицы.Пример 13. Пусть на вход преобразованию подается следующая программа:Листинг 20. Программа, содержащая директивы ops block array declare и ops blockarray allocateint main(){int i,j, i1, j1;int N1, N2;int d1, d2;#pragma ops block_array_declare(A, 2, N1, N2, d1, d2)double* A;d1 = 5; N1 = 7;d2 = 8; N2 = 9;97#pragma ops block_array_allocate(A)A = malloc(N1*N2*sizeof(double));for (i1=0; i1<N1; i++)for (j1=0; j1<N2; j1++)A[i1*N2+j1] (1) = i1+j1;}В данной функции выполняется блочное переразмещение матрицы A.

Впроцессе выполнения преобразования будет построена следующая таблица(Таблица 13):Таблица 13. Таблица с коэффициентами при индексах, линейно зависящих отсчетчиков циклов, получаемая на первом шаге алгоритма.<Вхождение>:<номер измерения>i1j1ijA1: 01000A2: 00010A1: 10100A2 10001В данном примере каждая из строк таблицы попадает под вариант 5 (см.параграф 4.5) обращения к элементам блочно размещаемого массива. Генерацияиндексных выражений для варианта 5 приведет к замедлению результирующейпрограммы.Поэтому на первом шаге производится проверка на то, что каждая строкатаблицы (в данном примере, это A1:0, A1:1, A2:0, A2:1) попадает под варианты 14 обращения к элементам блочно размещаемого массива (см. параграф 4.5).

Если98данное условие выполняется, то дополнительных преобразований программы нетребуется и производится переход на второй шаг алгоритма.В противном случае преобразование пытается преобразовать некоторыециклы входной программы так, чтобы количество строк таблицы, попадающихподварианты1-4,быломаксимально.Вкачествевспомогательногопреобразования используется гнездование циклов.В данном примере к каждому из циклов применяется гнездование ккаждому из циклов программы. Исходная таблица примет следующий вид(Таблица 14):Таблица 14.

После применения гнездования к циклам программПара <Вхождение>:<номеризмерения>di_idj_jdi_2idj_2jA1: 0d11000000A2: 00000d1100A1: 100d210000A2 1000000d21Теперь каждая из строк таблицы попадает под вариант 1 и, следовательно,генерируемые индексные выражения будут содержать минимальное количествоарифметических операций.На втором шаге алгоритма производится генерация индексных выраженийсогласно формуле (3). В качестве дополнительных оптимизаций производятсяпредвычисление констант, а также вынос общих подвыражений. Для нашегопримера результирующая программа будет иметь следующий вид:99Листинг 21.

Результат работы преобразования блочного размещения массивов.int main(){…d1 = 5;N1 = 7;d2 = 8;N2 = 9;__uni9_A_NN_0 = ((N1 + d1) / d1) * d1;__uni10_A_NN_1 = ((N2 + d2) / d2) * d2;__uni32_A_d_coef_0 = d1 * __uni10_A_NN_1;__uni33_A_i_coef_0 = d2;__uni34_A_d_coef_1 = d1 * d2;__uni35_A_i_coef_1 = 1;A = malloc(((__uni9_A_NN_0 * __uni10_A_NN_1) * 8));{int __uni16_di;int __uni17;int __uni18;int __uni19;int __uni20;__uni17 = floor_kernel_func(((0 * 1.) / d1));__uni18 = ceil_kernel_func(((N1 * 1.) / d1));for (__uni16_di = __uni17; __uni16_di < __uni18; __uni16_di = __uni16_di + 1){double *__uni31;__uni31 = A + (1 * __uni32_A_d_coef_0) * __uni16_di;__uni19 = 0 - __uni16_di * d1 > 0 ? 0 - __uni16_di * d1 : 0;__uni20 = N1 - __uni16_di * d1 > d1 ? d1 : N1 - __uni16_di * d1;100for (i = __uni19; i < __uni20; i = i + 1){double *__uni36;__uni36 = __uni31 + (1 * __uni33_A_i_coef_0) * i;{int __uni11_dj;int __uni12;int __uni13;int __uni14;int __uni15;__uni12 = floor_kernel_func(((0 * 1.) / d2));__uni13 = ceil_kernel_func(((N2 * 1.) / d2));for (__uni11_dj = __uni12; __uni11_dj < __uni13; __uni11_dj = __uni11_dj + 1){double *__uni37;__uni37 = __uni36 + (1 * __uni34_A_d_coef_1) * __uni11_dj;__uni14 = 0 - __uni11_dj * d2 > 0 ? 0 - __uni11_dj * d2 : 0;__uni15 = N2 - __uni11_dj * d2 > d2 ? d2 : N2 - __uni11_dj * d2;for (j = __uni14; j < __uni15; j = j + 1){double *__uni38;__uni38 = __uni37 + (1 * __uni35_A_i_coef_1) * j;*__uni38 = (i + __uni16_di * d1) + (j + __uni11_dj * d2);}}}}}}{101int __uni26_di;int __uni27;int __uni28;int __uni29;int __uni30;__uni27 = floor_kernel_func(((0 * 1.) / d1));__uni28 = ceil_kernel_func(((N1 * 1.) / d1));for (__uni26_di = __uni27; __uni26_di < __uni28; __uni26_di = __uni26_di + 1){double *__uni39;__uni39 = A + (1 * __uni32_A_d_coef_0) * __uni26_di;__uni29 = 0 - __uni26_di * d1 > 0 ? 0 - __uni26_di * d1 : 0;__uni30 = N1 - __uni26_di * d1 > d1 ? d1 : N1 - __uni26_di * d1;for (i = __uni29; i < __uni30; i = i + 1){double *__uni40;__uni40 = __uni39 + (1 * __uni33_A_i_coef_0) * i;{int __uni21_dj;int __uni22;int __uni23;int __uni24;int __uni25;__uni22 = floor_kernel_func(((0 * 1.) / d2));__uni23 = ceil_kernel_func(((N2 * 1.) / d2));for (__uni21_dj = __uni22; __uni21_dj < __uni23; __uni21_dj = __uni21_dj + 1){double *__uni41;__uni41 = __uni40 + (1 * __uni34_A_d_coef_1) * __uni21_dj;__uni24 = 0 - __uni21_dj * d2 > 0 ? 0 - __uni21_dj * d2 : 0;102__uni25 = N2 - __uni21_dj * d2 > d2 ? d2 : N2 - __uni21_dj * d2;for (j = __uni24; j < __uni25; j = j + 1){double *__uni42;__uni42 = __uni41 + (1 * __uni35_A_i_coef_1) * j;printf(" %6.2f", (*__uni42));}}}printf("\r\n");}}}free(A);return 0;}4.7.Численные экспериментыДля проверки эффективности и корректности реализованных директивнаписан пакет прикладных блочных программ, аннотированных директивамиблочного размещения данных.

В Таблице 15 приведены результаты сравненияпроизводительностипрограмм,скомпилированныхсвключеннойопциейблочного размещения данных, а также без нее. Тестирование производилось накомпьютере с процессором Intel Core i5-2410M Processor (3M Cache, 2.90 GHz). Вкачестве компилятора использовался Intel C++ Composer XE 2013 SP1 for Linux,Update 3 [38].103Таблица 15. Результаты тестирования директив блочного размещения в памятикомпилятором Intel C++ Composer XE 2013 SP1 for Linux, Update 3Название алгоритмаРазме РазмерВремяВремяУскоррработыработыениематралгориталгоритмаицмаблокабез сдиректив директива(сек.)Двумерное быстрое4096xпреобразование Фурье4096Блочный алгоритм2048xФлойда2048Блочное QR-2048xразложение матрицы1024Блочное LU-2048xразложение матрицы2048Блочное умножение2048xквадратных матриц2048Блочное возведение2048xматрицы в квадрат2048ми (сек.)256x25617.910.5441%256x25647.4941.1713.3%256x25619.617.1112.7%256x25627.414.4447%256x25614.9311.225%256x25681.3717.3678.6%Как видно из результатов, представленных в Таблице 15, ускорение,получаемое за счет использования реализованного преобразования блочногоразмещения данных, сильно зависит от входной программы.

Характеристики

Список файлов диссертации