Диссертация (Оптимизация размещения массивов в общей памяти)

Южный федеральный университетНа правах рукописиЮрушкин Михаил ВикторовичОптимизация размещения массивов в общей памятиСпециальность 05.13.11 —Математическое и программное обеспечениевычислительных машин, комплексов и компьютерных сетейДИССЕРТАЦИЯна соискание ученой степеникандидата физико-математических наукНаучный руководительд. т. н., с.н.с.Б.Я. ШтейнбергРостов-на-Дону — 20162ОглавлениеВведение .................................................................................................................................................

4Глава 11.1.Используемые методы оптимизации работы с данными программы................. 13Дисбаланс производительности процессора и памяти. .................................................... 131.1.1.Кеш-память процессора ............................................................................................... 141.1.2.Аппаратная поддержка виртуальной памяти. Кеш-память TLB. ............................

201.2.Увеличение временной локальности данных. Метод тайлинга. ..................................... 211.3.Увеличение пространственной локальности данных. Переразмещение данных .......... 241.3.1.Нестандартные размещения данных .......................................................................... 241.3.2.Блочное размещение данных ...................................................................................... 261.4.Выравнивание данных в памяти .........................................................................................

291.5.Оптимизация работы с данными программ современными компиляторами ................. 311.6.Выводы к первой главе ........................................................................................................ 33Глава 22.1.Модель времени выполнения программ для иерархической памяти ................. 34Анализ блочного алгоритма умножения матриц ..............................................................

402.1.1.Определение уровня кеш-памяти, для которого оптимально производить тайлинг ......................................................................................................................................... 402.1.2.матрицОпределение оптимального размера блока для блочного алгоритма умножения........................................................................................................................................ 422.2.Определение оптимального размера блока для блочного алгоритма Флойда-Уоршалла................................................................................................................................................ 452.3.Анализ масштабируемости параллельного блочного алгоритма Флойда ...................... 492.4.Статическое определение количества кеш-промахов ......................................................

512.5.Выводы ко второй главе ...................................................................................................... 57Глава 33.1.Умножение матриц рекордной производительности .............................................. 58Высокопроизводительные пакеты программ линейной алгебры .................................... 593.2.Высокопроизводительный алгорит умножения матриц, использующий двойноеблочное размещение данных ........................................................................................................... 603.3.Результаты численных экспериментов ..............................................................................

673.4.Выводы к третьей главе ....................................................................................................... 79Глава 4Автоматизация блочных размещений данных в системе ОРС ............................. 814.1.Оптимизирующая распараллеливающая система ............................................................. 824.2.Директивы блочного размещения данных в компиляторе языка Си ..............................

824.3.Работа с блочным размещением в OPS Demo5 ................................................................. 854.4.Реализация блочного размещения данных в Web- распараллеливателе программ. ...... 874.5.Проблема вычисления адреса элемента при блочном размещении массива и анализвариантов ее решения.......................................................................................................................

894.6.Алгоритм блочного размещения данных. .......................................................................... 954.7.Численные эксперименты ................................................................................................. 10234.8.Реализация парсера языка ФОРТРАН для системы ОРС ............................................... 1094.9.Выводы к четвертой главе .................................................................................................

111Заключение ........................................................................................................................................ 113Список сокращений и условных обозначений ........................................................................... 116Литература ........................................................................................................................................ 1174ВведениеАктуальностьВысокопроизводительные вычисления используются во многих отрасляхэкономики.Областямиприменениявысокопроизводительныхвычисленийявляются оборонная промышленность, создание новых лекарств, высокочастотнаяторговля фьючерсами, моделирование деталей автомобилей, визуализациякиноэффектов, прогнозирование изменений климата и т.д.Для того чтобы удовлетворить увеличивающийся спрос на высокуюпроизводительность современные компьютеры развиваются со стремительнойскоростью.

В 2005 году был выпущен первый двуядерный процессор. Теперь жеколичество ядер в современных процессорах достигает 16 и более. Появилисьновые виды вычислительных систем – видеокарты, количество вычислительныхэлементов которых измеряется в тысячах, а пиковая производительностьизмеряется в терафлопсах.На фоне уменьшения времени выполнения арифметических операций засчет увеличения количества ядер, доступ к памяти становится все более узкимместом в производительности вычислительных систем.

С целью увеличенияэффективности кеш-памяти давно используются блочные вычисления (тайлинг),которые позволяют подстроить алгоритм под иерархию памяти и, тем самым,уменьшить количество кеш-промахов. Также используются выравнивание данныхи нестандартные размещения данных в памяти.В некоторых случаях вместе с тайлингом используется блочное размещениемассивов, позволяющее получить еще большее ускорение. Непосредственноеиспользование блочного размещения массивов затруднительно, т.к. требуетвысокой квалификации программиста и много времени на разработку.5Степень разработанности темыУскорение программ с помощью перехода к блочным вычислениямисследовалось в работах Н.А.

Лиходеда, В.Э Малышкина, Ф.Г. Густавсона,Моники Лэм, Майкла Вульфа, Д. Донгарры, Чарльза Ван Лоана. Дополнительноеускорение блочных вычислений за счет нестандартных размещений массивов впамяти рассматривалось в работах Д. Донгарры, В. Прасанна, Л. Карлсона.Большинство работ, посвященных исследованию блочного размещенияданных, связано с написанием вручную высокопроизводительных блочныхалгоритмов,использующихблочноразмещенныематрицы.Современныекомпиляторы и библиотеки на данный момент не поддерживают блочныеразмещения данных, ориентируясь только на стандарт языка программирования,который предписывает хранить матрицы либо по строкам (Си, ПАСКАЛЬ), либопо столбцам (ФОРТРАН).

Исключение составляет пакет PLASMA для решениязадач линейной алгебры. В нем реализованы алгоритмы некоторых важных задачлинейной алгебры (умножение матриц, LU-разложение матрицы, QR-разложениематрицы,разложениеХолецкогоит.д.),которыеработаютсблочноразмещенными матрицами. Также в нем реализованы специальные функции,которые производят переразмещения из стандартного вида в блочный видхранения матриц.Описанные выше исследования показали высокую эффективность блочныхвычислений и блочных размещений матриц. Но не рассмотрены возможностидвойного блочного размещения матриц и не рассмотрены возможностииспользования блочных размещений матрицы компилятором. Не рассматриваласьдо сих пор основанная на модели задача прогноза времени выполнения программ,использующих блочное размещение матриц, на будущих процессорах.Всеэтооптимизацииподчеркиваетразмещенийактуальностьмассивовавтоматизации таких размещений.висследований,общейпамятии,посвященныхвчастности,6Объект исследованийПрограммы,ориентированныенабольшиеобъемывычисленийииспользующие общую память.Цель работыРазработка методов и средств ускорения параллельных программ на основеоптимизации размещения массивов в общей памяти.Сформулированная цель может быть достигнута путем решения следующихзадач:1.