Диссертация (1149957), страница 5
Текст из файла (страница 5)
Тестирование проводилось на квадратных матрицахразмером от 100x100 до 2048x2048. Результаты экспериментов показали, чтоблочно-рекурсивное распределение проигрывает стандартным распределениям наархитектуре x86. В случае процессоров Alpha и Sparc блочно-рекурсивноеразмещение имеет преимущество по сравнению с одним из стандартныхразмещений.В [11] авторы ускорили алгоритм, реализующий преобразование УолшаАдамара. За счет переразмещения данных в оперативной памяти удалосьуменьшить количество возникающих кеш-промахов.В [13] представлена методика разделения массивов (array partitioning), прииспользовании которой кеш-память разделяется на несколько одинаковых поразмеру частей.
Массивы размещаются таким образом, что они попадают вразличные части кеш-памяти.В статье [35] приводятся результаты ускорения программ на GPGPU за счетиспользования нестандартных размещений данных. Тестирование проводилось 15примерах, на которых достигается ускорение в 4.3 раза.1.3.2.Блочное размещение данныхБлочное размещение – это способ хранения массива в памяти, при котороммассив разбивается на блоки одинакового размера.
Блоки матрицы хранятся впамяти последовательно без промежутков (Рисунок 5). Элементы, находящиеся27внутри одного блока, хранятся в памяти стандартным образом, например, построкам:Рис. 5: Блочное размещение элементов матрицы 8x8. На месте элементов матрицырасположен относительный адрес соответствующего элемента.Общая формула вычисления адреса элемента с индексом (i,j) матрицы Xимеет следующий вид:addr( X , i, j) X (i / d1 ) * N 2 / d 2 * d 2 ( j / d 2 ) * d1 * d 2 (i%d1 ) * d 2 j%d 2(1)Где N2 – количество элементов в строке матрицы X d1xd2 – размер блока.В некоторых блочных алгоритмах блочное размещение массивов даетувеличение производительности [15], [16], [18] , [19], [12], [28], [63]. Так в задачеблочного умножения матриц блочное размещение матриц позволяет существенно28сократить количество промахов к кеш-памяти и кеш-памяти TLB.
Подробнее обэтом излагается в Главе 2.В[15]представленыреализацииоптимизированныхалгоритмовтранспонирования матрицы, умножения матриц и генерации полигонов в методеконечных элементов. Данные алгоритмы используют блочные вычисления иблочное размещение данных в совокупности. Тестирование производительностипроводилось на процессорах UltraSPARC II, Alpha 21264 и Pentium III. В задачетранспонированияматрицыавторыдостигли50%увеличенияпроизводительности, 22% ускорения умножения матриц по сравнению салгоритмами CBLAS.
В блочном алгоритме генерации полиэдров в методеконечных элементов блочное размещение дает 1.7 раза по сравнению состандартным размещением.В [16] исследовано влияние нестандартных видов размещения данных,таких как блочное и мортоновское размещения, на эффективность использованиякеш-памяти и кеш-памяти TLB в блочных программах. Представлены методикиопределения оптимального размера блока, используемого при размещении матрицблочным образом. Эффективность данной методики была проверена на задачахLU-разложения матрицы, разложении Холецкого матрицы и умножения матриц.Результаты численных экспериментов показали, что блочное размещение всовокупностисблочнымивычислениямидаетдополнительнуюпроизводительность более чем на 50% по сравнению со стандартнымиразмещениями.В [23] рассматривается вопрос оптимизации алгоритма двумерногобыстрого преобразования Фурье.
Авторы статьи исследовали зависимостьвремени работы алгоритма от метода размещения данных. Результаты численныхэкспериментов показали, что при использовании блочного размещения времяработы алгоритма меньше чем при стандартном размещении. Это связано с тем,что в данной задаче вычисление преобразования Фурье для столбцов матрицы,размещеннойпострокам,ассоциативности кеш-памяти.являетсядорогостоящейоперацией,всилу29В некоторых задачах выбор способа размещения данных сильно влияет наэффективность векторизации.
Так, в алгоритме умножения матриц в библиотекахGotoBLAS [86] и OpenBlas [30] для реализации эффективной векторизации(register blocking) используется блочное размещение матриц. В работе [46], [47],[48]предложеныспецифическиеспособыраспределениямассивовдлятрафаретных программ (stencil codes). Результаты численных экспериментовпоказали, что предложенные способы размещения массивов позволяют увеличитьэффективностьрезультирующейпрограммы(10-200%взависимостиотвычислительной архитектуры и задачи).В[14]представленвысокопроизводительныйблочныйалгоритмпереразмещения матриц из стандартного формата в блочный формат и наоборот.Особенностью данного алгоритма является то, что он не требует большогоколичества дополнительной памяти, и поэтому он может использоваться дляпереразмещения матриц большого размера.Изложенные выше методы оптимизации увеличивают эффективностьиспользования памяти за счет переразмещения элементов в рамках каждого измассивов.
В случае, когда в программе производится обращение к элементамнесколькихмассивов,томожетвозникнутьситуация,прикоторойзапрашиваемые элементы разных массивов будут отображаться в одни и те жебанки памяти, что снизит эффективность работы кеш-памяти. Эта проблемаможет быть решена, если разместить массивы так, чтобы запрашиваемые в одно ито же время элементы разных массивов хранились в памяти близко друготносительно друга.
В [13] приводятся результаты численных экспериментов,которые подтверждают, что подобное размещение массивов может датьдополнительную производительность.1.4.Выравнивание данных в памятиПри разработке программ следует помнить о том, что данные должны бытьвыровнены в памяти. Это требование связано с тем, что процессоры30обрабатывают выровненные данные намного эффективнее, чем невыровненные.Некоторые процессоры [60] при невыровненном доступе к данным аварийнопрекращают выполнение программы.Для того чтобы переменная, занимающая несколько байт памяти, былавыровнена, необходимо, чтобы ее адрес был кратен ее размеру. Так, например,если объявленная в программе переменная имеет тип int32 (4 байта), то для того,чтобы она была выровнена, она должна быть размещена по адресу кратному 4.Если процессор поддерживает невыровненный доступ, то может возникнутьситуация, когда невыровненное данное находится в соседних словах.
В этомслучае процессору придется считывать из памяти соседние слова, в которыхнаходится данное, а также произвести “склейку” этих частей. Таким образом, придоступекневыровненнымданнымпроизводятсядополнительныеарифметические операции чтения данных. Невыровненный доступ порождаетдополнительные кеш-промахи в случае, когда считываемая переменная хранитсяна границе кеш-линеек или на границе виртуальных страниц.Современные компиляторы способны выравнивать данные автоматически.Поэтому программисту в большинстве случаев не приходится думать овыравнивании данных. Рассмотрим примеры того, как происходит выравниваниеданных компиляторами.Пример 1.
Для того, чтобы в структуреЛистинг 3. Объявление структуры, в которой размер первого поля меньшеразмера второго поля.struct Foo1{short a;int64 b;}31поле b было выровнено, компилятор после размещения поля ‘a’ вставляетдополнительные 6 байт. Поэтому размер такой структуры равен 16 байт, а не 10.Пример 2.
Рассмотрим следующую структуру:Листинг 4. Объявление структуры, в которой размер первого поля больше размеравторого поля.struct Foo2{int64 b;short a;}В данной структуре размер поля b больше размера поля a. Поэтому компиляторразмещает поле a сразу после поля b без добавления промежуточных байт. Послебайт, относящихся к полю ‘a’ компилятор вставляет дополнительные 6 байт,чтобы размер структуры был кратен размеру максимального типа, используемогопри объявлении полей этой структуры.
Дополнительные байты вставляются вконец структур для того, чтобы обеспечить автоматическое выравнивание данныхвнутри массивов структур.В некоторых компиляторах реализована возможность ручного контроля надвыравниванием полей структур. Так, например, в компиляторах C/C++ MSVCподдерживаются директивы pragma pack push/pop.1.5.Оптимизация работы с данными программ современнымикомпиляторамиСистема компиляторов ROSE [44], [89], [88] предназначена для построенияsource-to-source трансляторов. В качестве входных языков поддерживаютсяFortran 2003, C, C++.
Система ROSE имеет высокоуровневое внутреннее32представление, а также большой набор высокоуровневых оптимизирующихпреобразований(оптимизациигнездциклов,inlining,PartialRedundancyElimination).В языке Fortran DVM [39] реализована поддержка ручного размещенияданных в распределенной памяти. Для эффективной работы программы,работающей на многопроцессорной системе, программист должен правильноразместить данные в оперативной памяти каждого из узлов системы.Автоматическое выравнивание данных реализовано во всех компиляторах,поддерживающих автоматическую векторизацию (GCC [85], Intel [38], LLVM[83], MSVC [104]). В некоторых компиляторах семейства PGI [45] реализованыоперации копирования массивов (copyin) на графический ускоритель и выгрузкарезультатов с ускорителя в оперативную память (copy).Существуют оптимизаторы кода Polly LLVM [81], [82] и PLUTO [87], [43],которые ускоряют программы за счет автоматического применения методатайлинга и распараллеливания программы для многоядерных процессоров.Массивы данных в современных языках программирования могут бытьопределены как массивы структур, структуры массивов либо как комбинация этихподходов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
