Диссертация (1149957), страница 14
Текст из файла (страница 14)
Так, для программы,реализующей блочное QR-разложение матрицы, ускорение составляет 1.15 раза, вто время как для программы, реализующей быстрое блочное возведение матрицыв квадрат, ускорение составляет 4.69 раз.104Тест 1. Быстрое двумерное преобразование ФурьеВ данном эксперименте в качестве входной программы подается программа,реализующая быстрое преобразование Фурье. Исходный текст программы,реализующей двумерное быстрое преобразование Фурье взят из [61].
и ручномупереписыванию не подвергался. В текст программы были добавлены директивыблочного размещения данных.На Рисунке 22 представлен график времени работы алгоритма состандартным размещением входной матрицы и график времени работы того жесамого алгоритма с блочным размещением входной матрицы. Переход кблочному размещению был произведен при помощи реализованного авторомпреобразования блочного размещения данных.Рис. 22: График сравнения производительности исходной программы ипреобразованной программы. По вертикальной оси отложено время работыпрограммы, по горизонтальной оси – размер блоков, на которые разбиваетсявходная матрицаПо горизонтальной оси отложен размер блоков, на которые разбиваетсявходная матрица при блочном ее размещении.
Как видно из результатовэксперимента блочное размещение входной матрицы в данном эксперименте105позволило ускорить входную программу. Оптимальный размер блока находится вдиапазоне – 15-20.Тест 2. Блочный алгоритм ФлойдаВ данном эксперименте в качестве входной программы подается программа,реализующая блочный алгоритм Флойда:Листинг 22. Блочный алгоритм Флойда, аннотированный директивами блочногоразмещения массивов.// Цикл по блокам.
Идем по диагоналиfor (int L = 0; L < n; L+= d){int k1 = L;int k2 = MIN(n, L+d);// Фаза 1. Рассчитываем self-depended block (не используя другие блоки)for (int k = k1; k < k2; k++)for (int i = k1; i < k2; i++)for (int j = k1; j < k2; j++){double v = A[f1(i, k, n)] + A[f1(k, j, n)];if (v < A[f1(i, j, n)])A[f1(i, j, n)] = v;}// Фаза 2. Рассчитываем блоки на той же строке и на том же столбце.for (int K = 0; K < n; K+=d){if (K == L)continue;106int j1 = K;int j2 = MIN(n, K+d);int i1 = L;int i2 = MIN(n, L+d);for (int k = k1; k < k2; k++)for (int i = i1; i < i2; i++)for (int j = j1; j < j2; j++){double v = A[f1(i, k, n)] + A[f1(k, j, n)];if (v < A[f1(i, j, n)])A[f1(i, j, n)] = v;}for (int k = k1; k < k2; k++)for (int j = j1; j < j2; j++)for (int i = 0; i < d; i++){double v = A[f1(j, k, n)] +A[f1(k, i, n)];if (v < A[f1(j, i, n)])A[f1(j, i, n)] = v;}}// Фаза 3.
Рассчитываем остальные блокиfor (int K = 0; K < n; K+=d){107int i1 = K;int i2 = MIN(n, K + d);for (int S = 0; S < n; S+=d){if (K == L || S == L)continue;int j1 = S;int j2 = MIN(n, S + d);for (int k = k1; k < k2; k++)for (int i = i1; i < i2; i++)for (int j = j1; j < j2; j++){double v = A[f1(i, k, n)] + A[f1(k, j, n)];if (v < A[f1(i, j, n)])A[f1(i, j, n)] = v;}}}}В Таблице 16 представлено время работы программной реализации данногоалгоритма, использующего стандартное размещение матрицы, а также времяработы программной реализации того же самого алгоритма, использующегоблочное размещение входной матрицы.
Размер блока выступает в качествепараметра. Размер матрицы фиксирован и равен 2048. Переход к блочномуразмещениюбылпроизведенприпомощипреобразования блочного размещения данных.реализованногоавтором108Таблица 16. Время работы алгоритма Флойда до и после применения блочногоразмещения матрицы.РазмерРазмерВремя работыВремя работы программыматрицыблокапрограммы сос блочным размещениемстандартнымматрицы (мсек)размещениемматрицы (мсек)81613210.3912190.31483212137.887495.3820486410860.376071.0420489610614.735304.56204812810249.034939.49204819214885.375339.54204825620949.185418.81На Рисунке 23 представлен график времени работы данного алгоритма состандартным размещением входной матрицы и график времени работы того жесамого алгоритма с блочным размещением входной матрицы.Рис.
23: График сравнения производительности исходной программы ипреобразованной программы. По вертикальной оси отложено время работыпрограммы, по горизонтальной оси – размер блока109По горизонтальной оси отложен размер блоков, на которые разбиваетсявходная матрица при блочном ее размещении. Как видно из результатовэксперимента блочное размещение входной матрицы в данном экспериментепозволило ускорить входную программу. Оптимальный размер блока находится вдиапазоне – 120-130.Результаты численных экспериментов подтверждают, что реализованноеавтором преобразование блочного размещения данных позволяет существенноувеличитьпроизводительностьрезультирующейпрограммы.Ономожетиспользоваться в качестве вспомогательного преобразования для оптимизацииблочных программ.4.8.Реализация парсера языка ФОРТРАН для системы ОРСДля системы ОРС [75] автором был разработан парсер языка ФОРТРАН.Парсер поддерживает стандарт ФОРТРАН 77, а также включает некоторыеконструкции работы с динамической памятью из языка ФОРТРАН 90/95.
Парсерполностью разбирает пакет численных методов ACELAN [1] и POM (PrincetonOcean Model) [103]. Корректность работы парсера проверялась также на тестах изGCC [85], Parawise [37], ParcBench [90]. Разработанный парсер может бытьиспользован в ОС Windows и Linux.При разработке парсера языка ФОРТРАН использовался генератор парсеровANTLR.
В качестве исходной грамматики была взята грамматика языкаФОРТРАН из проекта Open Fortran Parser [91].На реализацию парсера большое влияние оказало внутреннее представлениеОРС. Оно имеет структуру близкую к языку Си, а не ФОРТРАН, и в связи с этимвозникли проблемы, связанные с отображением программ на языке ФОРТРАН вовнутреннее представление. Рассмотрим примеры решения некоторых такихпроблем.110Пример 14. Отображение COMMON-блоков во внутреннее представление.Фрагмент кода.Листинг 23. Объявление common-блока SampleCommonBlock внутри функций A иB.SUBROUTINE ACOMMON / SampleCommonBlock / iVar1_1, iVar1_2END SUBROUTINE ASUBROUTINE BCOMMON / SampleCommonBlock / iVar2_1, iVar2_2END SUBROUTINE Bотображается во внутреннее представление следующим образом:Листинг 24.
Результат преобразования common-блока в язык Сиstruct SampleCommonBlock {union A { int ivar1_1, ivar1_2 }union B { int ivar2_1, ivar2_2 }}SampleCommonBlock block_var;void A(){...}void B(){...}111Пример 15. Проблема отображения срезов массивов. В языке ФОРТРАНесть поддержка обращений к срезам массивов, в то время как в языке Си такойвозможности нет. В парсере реализована ограниченная поддержка такихопераций. Он разбирает операторы присваивания видаЛистинг 25.
Оператор присваивания нескольким элементам массива X некоторогозначенияX[x1:y1:k1,x2..y2] = expr;в гнезда циклов видаЛистинг 26. Результат преобразования в язык Сиfor (i = x1; i<=y1; i+=k1)for (j = x2; j<=y2, j+=1)X[i][j] = expr;4.9.Выводы к четвертой главеВчетвертойглавеприводитсяалгоритмавтоматизацииблочныхразмещений данных, реализованный в системе ОРС. Такая автоматизацияреализована на уровне директив компилятора языка Си. Автором реализовантакже парсер языка ФОРТРАН 77/90, который был протестирован на пакетахACELANиPOM.РеализованныйпарсерязыкаФОРТРАНпозволяетиспользовать систему ОРС для оптимизации программ, написанных на языкеФОРТРАН. Таким образом, в данной главе раскрывается решение задачи 3 изадачи 4.Описание директив блочного размещения данных приведено в параграфе4.2.
Описанные директивы позволяют блочно размещать также массивыпроизвольной размерности. В параграфах 4.3-4.4 приводятся программные112проекты, в которых можно протестировать работу данных директив. Впараграфах 4.5-4.5 строится алгоритм обработки компилятором директивблочного размещения данных. Параграф 4.7 содержит результаты численныхэкспериментов,вкоторыхсравниваетсявремяработыпрограмм,скомпилированных в двух режимах – без директив блочного размещения данныхибезних.реализованнаяРезультатычисленныхавтоматизацияблочныхускорение для некоторых классов задач.экспериментовразмещенийподтверждают,даетчтодополнительное113ЗаключениеВ диссертации проведены исследования, направленные на оптимизациюработы с памятью существующих вычислительных систем.Построенная модель времени выполнения программ позволяет оцениватьвремя работы программ.
В ней учитываются частота процессора, а такжеразличные характеристики иерархии кеш-памяти, такие как латентность,физическийразмер,ассоциативность.Учетэтихпараметровпозволяетпрогнозировать более точно время выполнения программ, что было подтвержденочисленными экспериментами в параграфах 2.1-2.2. Таким образом, описанная вглаве 2 модель времени выполнения программ является решением выносимого назащиту положения 3.В третьей главе описан и реализован высокопроизводительный алгоритмумножения матриц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
