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

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

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

Его особенностью является то, что данные хранятся в памятинебольшими блоками нестандартным образом, а не стандартным образом. Впараграфе 3.3 приводятся результаты численных экспериментов, в которыхсравнивается производительность программной реализации разработанногоалгоритма, а также существующих других высокопроизводительных реализаций(IntelMKL,PLASMA,OpenBLAS).Согласнорезультатамчисленныхэкспериментов представленный в диссертации алгоритм по производительностипревосходит остальные алгоритмы, и его производительность составляет всреднем 98-99% от теоретической производительности процессора.81Глава 4Автоматизация блочных размещений данных в системе ОРСВ предыдущих главах показана важность метода размещения данных воперативной памяти и его влияние на время выполнения программы.Современные языки программирования используют разные методы размещенияданных в оперативной памяти.

Язык ФОРТРАН использует размещение постолбцам [10] в то время как языки C/C++/Pascal используют размещение построкам [10]. Поэтому программисту для написания быстрого алгоритманеобходимо учитывать способ размещения данных, используемый в языкепрограммирования. Также, современные компиляторы не имеют встроеннойподдержки нестандартного размещения массивов.Ручное изменение метода размещения данных является затруднительнойоперацией,т.к.предполагаетвысокуюквалификациюпрограммистаидополнительные затраты времени. Непосредственное применение, например,блочногоразмещенияувеличивает объем результирующейпрограммыипорождает сложные индексные выражения во вхождениях блочно размещаемыхмассивов. Поэтому представляется интересной задача автоматизации поддержкиблочного размещения массивов в языках программирования.

Такая автоматизацияреализована в системе ОРС (Оптимизирующая распараллеливающая система) ввиде нескольких директив компилятора. Она может использоваться для получениядополнительного ускорения блочных программ. Детали реализации такойавтоматизации описаны в данной главе. В конце главы приводятся результатыускорения программ за счет данных директив на задачах линейной алгебры (LUразложение матрицы, умножение матриц), преобразования Фурье и т.д.824.1.Оптимизирующая распараллеливающая системаОптимизирующаяраспараллеливающаясистемапредставляетсобойинструмент для построения оптимизирующих компиляторов.

Она состоит изнескольких модулей:1. Парсеры языка ФОРТРАН и Си. Парсер языка ФОРТРАН разработанавтором диссертации. Особенности его реализации приводятся в параграфе4.8.2. Высокоуровневое внутреннее представление (Reprise). В его состав входитнесколькодесятковпреобразованийпрограмм(гнездованиецикла,канонизация циклов, разрезание цикла и т.д.). Также есть поддержкатрансляции данного внутреннего представления в SSA форму.3.

Модули отображения внутреннего представления в языки Си, ФОРТРАН,VHDL.4.2.Директивы блочного размещения данных в компиляторе языка СиАвтором диссертации в системе компиляторов ОРС поддержка блочногоразмещения массивов реализована в виде нескольких директив компиляции.Перед объявлением блочно размещаемого массива указывается директива.#pragma ops array declare(name, array dimension size list, blockdimension size list)(1)Список параметров директивы: name – имя размещаемого массива. array dimension size list – массив размерностей размещаемого массивапо каждому измерению. block dimension size list – массив размерностей блока по каждомуизмерению.83В данной директиве указывается информация о размере массива, а такжеразмере блоков, на которые указанный массив стоит разбить.Оператор, в котором производится выделение памяти для массива A,следует пометить директивой#pragma ops array allocate(name)(2)Директива (2) заменяет исходный оператор выделения памяти новымоператором освобождения памяти, в котором выделяется память под блочноразмещенный массив.

Блочно размещенный массив должен иметь размер кратныйразмеру блока, т.к. выполнение данного условия на практике сильно упрощаетгенерацию индексных выражений. Аналогично, оператор, в котором производитсяосвобождение памяти массива A, следует пометить директивой#pragma ops array release (name)(3)Директива (3) заменяет исходный оператор освобождения памяти на новыйоператор освобождения памяти, в котором освобождается память, выделенная подблочно размещенный массив. Ниже приведен пример использования директивблочного размещения матриц для блочного алгоритма умножения матриц:Листинг 15. Блочный алгоритм умножения матриц с использованиемдиректив блочного размещения матриц.void matrix_mult(int N, int d) { ...#pragma ops array declare(A, N, N, d, d)#pragma ops array declare(B, N, N, d, d)#pragma ops array declare(C, N, N, d, d)84double *A, *B, *C;#pragma ops array allocate(A)A = malloc(sizeof(double)*N*N);#pragma ops array allocate(B)B = malloc(sizeof(double)*N*N);#pragma ops array allocate(C)C = malloc(sizeof(double)*N*N);// инициализация матриц A, B// блочное умножение матрицfor(di = 0; di < N; i+=d)for(dj = 0; dj < N; j+=d)for(dk = 0; dk < N; k+=d)for(i = di; i < MIN(N, di+d); i++)for(k = dk; k < MIN(N, dk+d); k++)for(j = dj; j < MIN(N, dj+d); j++)C[i*N+j] += A[i*N+k]*B[k*N+j];#pragma ops array release(A)free(A);#pragma ops array release(B)free(B);#pragma ops array release(C)free(C);}85Для того, чтобы компилятор переразметил данные, к входной программепредъявляется следующее требование: в программе не должно быть операцийвзятия адреса блочно размещаемого массива, кроме как в операциях выделения иосвобождения памяти массива.

Операции выделения и освобождения памятидолжны быть аннотированы директивами (2) и (3) соответственно.4.3.Работа с блочным размещением в OPS Demo5Блочное размещение данных легче всего применить к программе спомощью специальной программы OPSDemo5 [75], которая предназначена длядемонстрации работы преобразований системы ОРС. При запуске программаOPSDemo5 имеет следующий вид (Рисунок 16):Рис. 16: Программа OPS5DemoДля того чтобы применить к своей программе блочное размещение данных,пользователь должен с помощью кнопки Open загрузить ее исходный код вOPSDemo5 (Рисунок 17).86Рис. 17: Загруженная в OPSDemo5 программа пользователяДалее,вовкладкеTransformsпользовательдолженвыбратьпреобразование “Data Distribution for shared memory” и нажать кнопку Apply(Рисунок 18).Рис.

18: Применение преобразования “Data distribution for shared memory”87После этого будет применено блочное размещение данных. Результатработыпрограммыотобразитсявправойвкладке“Transformation Result” (Рисунок 19).Рис. 19: Результат применения преобразования “Data distribution for sharedmemory”Скачать программу OpsDemo5 можно по адресу [75].4.4.Реализация блочного размещения данных в Web- распараллеливателепрограмм.Описанные в параграфе 4.2 директивы блочного размещения данных вошлив состав Web-распараллеливатель [67], [77].

Web- распараллеливатель – этопрограмма, предназначенная для ускорения блочных алгоритмов за счетэффективногоиспользованиякеш-памятиилираспараллеливаниянасуперкомпьютер с распределенной памятью. Данный проект основан на базеДВОР. На Рисунке 20 представлено главная страница Web- распараллеливателя.Для того чтобы применить блочное размещение данных к программе88необходимо на Шаге 1 выбрать опцию “Автоматическое распределение данныхпод кеш-память”.Рис.

20: Web-распараллеливатель программ. Выбор режима преобразования.На Шаге 2 необходимо указать источник программы, которую необходимопреобразовать (Рисунок 21). На вход Web-распараллеливателю подаютсяпрограммы на языке Си, соответствующие стандарту C99. Входная программадолжна состоять из одного *.c файла. Если программа включает нестандартныезаголовочные файлы, то перед загрузкой необходимо включить их исходный кодв текст программы с помощью препроцессора.89Рис. 21: Web-распараллеливатель программ. Выбор источника программы.Результатом работы Web-распараллеливателя является преобразованнаяпрограмма.4.5.Проблема вычисления адреса элемента при блочном размещениимассива и анализ вариантов ее решения.Пусть дан многомерный массивA[ N 1 , N 2 ,..N p ] .Будем считать, чтоизначально данные в массиве хранятся по строкам. Т.е. элемент A[i1 , i2 ,..i p ]относительноначаламассивахранитсяадресу AddrA, i1 , i2 ,..i p  i1 * N 2 * ... * N p  i2 * N 3 * ...

* N p  i p . Выражениепоikбудемназывать индексом по k-му измерению при вхождении массива A.Предположим, что массив A нужно разместить блочным образом сразмером блока равным( BlockSize1 , BlockSize2 ,..., BlockSize p ) .В этом случаесоответствующий ему блочный массив имеет размер A block [ N 1block , N 2 block ,.. N p block ] , где90Nkblock N k / BlockSizek  . При этом элемент A[i1 , i2 ,..i p ] относительно начала массивауже будет храниться по адресуAddr( A block , i1 , i 2 ,..i p ] di1 * BlockSize1 * N 2 * ...

* N p di2 * BlockSize1 * BlockSize2 * N 3 * ..N p  ... di p * BlockSize1 * BlockSize2 * ... * BlockSize p wi1 * BlockSize2 * BlockSize3 * .. * BlockSize p wi2 * BlockSize3 * BlockSize4 * .. * BlockSize p  ....  wi p  di1di2... di pwi1wi2BlockSize1 * N 2 * ... * N p BlockSize1 * BlockSize2 * N 3 * ..N p (3)... BlockSize1 * BlockSize2 * ...

* BlockSize p ... wi p  *  BlockSize2 * BlockSize3 * .. * BlockSize p BlockSize3 * .. * BlockSize p...1Где dik  ik / BlockSizek  - номер блока по измерению k, а wik  (ik %BlockSizek ) номер элемента относительно начала блока по измерению k.В формуле (3) второй умножаемый вектор можно вычислить заранее. Темне менее, вычисление адреса элемента блочно размещенного массива являетсязатратной операцией, т.к. для получения переменных di k и wi kтребуютсядополнительные операции целочисленного деления и взятия остатка.На практике в большинстве случаев дополнительные вычисления можноизбежать.

Эффективноевычислениеиндексныхвыраженийблочноразмещенных массивов зависит от формы записи циклов, счетчики которых в нихиспользуются.Введем несколько определений.Определение 3. Цикл с заголовком “for (di=LBound; di<RBound;di+=step)”называется потенциальным циклом по блокам i-го измерения массива A, еслиLBound  0 и RBound  N / BlockSizek91Определение 4. Цикл с заголовком “for (di=LBound; di<RBound;di+=step)”называется потенциальным циклом по адресам блоков k-го измерения массива A,если1) LBound  02) LBound%BlockSizek равно 03) RBound  N4) step%BlockSizek равно 0Определение 5. Цикл с заголовком “for (wi=LBound; wi<RBound; wi+=step)”называется потенциальным циклом по элементам блока по k-го измерениямассива A, если1) LBound  02) RBound  BlockSizekОпределение 6.

Цикл с заголовком “for (i=LBound; i<RBound;i+=step)” называетсяпотенциальным циклом по адресам элементов блока по k-му измерению массиваA, если1) LBound  02) RBound  N3)  s  0 , при котором i  BlockSizek * s и i  BlockSizek * (s  1)Рассмотрим варианты записи циклов, счетчики которых входят в индексныевыражения блочно размещаемых массивов: для каждого случая выпишемусловия, накладываемые на индексные выражения блочно размещаемыхмассивов, а также формулы быстрого вычисления di k и wi k .92Вариант 1.

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

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