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

Размещено на http://www.allbest.ru/

Специальность 05.13.11 -- Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

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

Юрушкин Михаил Викторович

Ростов-на-Дону 2016

Работа выполнена в институте математики механики и компьютерных наук федерального государственного автономного образовательного учреждения высшего профессионального образования "Южный федеральный университет".

Научный руководитель: Штейнберг Борис Яковлевич,

доктор технических наук, профессор, старший научный сотрудник, заведующий кафедрой алгебры и дискретной математики института математики механики и компьютерных наук федерального государственного автономного образовательного учреждения высшего профессионального образования "Южный федеральный университет".

Официальные оппоненты: Болдырев Юрий Яковлевич,

доктор технических наук, профессор, профессор кафедры прикладной информатики федерального государственного автономного образовательного учреждения высшего образования "Санкт-Петербургский политехнический университет Петра Великого"

Булычев Дмитрий Юрьевич,

кандидат физико-математических наук, доцент кафедры системного программирования федерального государственного бюджетного образовательного учреждения высшего образования "Санкт-Петербургский государственный университет".

Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт систем информатики им. А.П. Ершова Сибирского отделения Российской академии наук.

Защита состоится 6 октября 2016 г. в 15:30 на заседании диссертационного совета Д 212.232.51 на базе Санкт-Петербургского государственного университета по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 28, математико-механический факультет, ауд. 405.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу 199034, Санкт-Петербург, Университетская наб., 7/9 и на сайте https://disser.spbu.ru/disser/soiskatelyu-uchjonoj-stepeni/dis-list/details/14/1007.html

Ученый секретарь диссертационного совета Д 212.232.51, д.ф.-м.н., профессор Демьянович Юрий Казимирович

Общая характеристика работы

Актуальность

Высокопроизводительные вычисления используются во многих отраслях экономики. Областями применения высокопроизводительных вычислений являются оборонная промышленность, создание новых лекарств, высокочастотная торговля фьючерсами, моделирование деталей автомобилей, визуализация киноэффектов, прогнозирование изменений климата и т.д.

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

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

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

Степень разработанности темы

Ускорение программ с помощью перехода к блочным вычислениям исследовалось в работах Н.А. Лиходеда, В.Э Малышкина, Ф.Г. Густавсона, Моники Лэм, Майкла Вульфа, Д. Донгарры, Чарльза Ван Лоана. Дополнительное ускорение блочных вычислений за счет нестандартных размещений массивов в памяти рассматривалось в работах Д. Донгарры, В. Прасанна, Л. Карлсона.

Большинство работ, посвященных исследованию блочного размещения данных, связано с написанием вручную высокопроизводительных блочных алгоритмов, использующих блочно размещенные матрицы. Современные компиляторы и библиотеки на данный момент не поддерживают блочные размещения данных, ориентируясь только на стандарт языка программирования, который предписывает хранить матрицы либо по строкам (Си, ПАСКАЛЬ), либо по столбцам (ФОРТРАН). Исключение составляет пакет PLASMA для решения задач линейной алгебры. В нем реализованы алгоритмы некоторых важных задач линейной алгебры (умножение матриц, LU-разложение матрицы, QR-разложение матрицы, разложение Холецкого и т.д.), которые работают с блочно размещенными матрицами. Также в нем реализованы специальные функции, которые производят переразмещения из стандартного вида в блочный вид хранения матриц.

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

Все это подчеркивает актуальность исследований, посвященных оптимизации размещений массивов в общей памяти и, в частности, автоматизации таких размещений.

Объект исследований

Программы, ориентированные на большие объемы вычислений и использующие общую память. программа вычисление алгоритм память

Цель работы

Разработка методов и средств ускорения параллельных программ на основе оптимизации размещения массивов в общей памяти.

Сформулированная цель может быть достигнута путем решения следующих задач:

1. Создание модели времени выполнения программ для систем с общей памятью.

2. Использование нестандартных размещений данных для построения высоко оптимизированного алгоритма умножения матриц.

3. Автоматизация блочного размещения данных.

4. Модификация Оптимизирующей распараллеливающей системы.

Методология

Методология исследования основана на последовательной идентификации и анализе проблемы, а также анализе существующей литературы. При исследовании предлагаемой модели времени выполнения программ использовалась модель процессора, существенно приближенная к существующим процессорам. Для проверки корректности модели времени выполнения программ использовался метод численного эксперимента. При реализации высокопроизводительного алгоритма умножения матриц, а также алгоритма автоматизации блочного размещения матриц в общей памяти использовались методы низкоуровневой оптимизации программ, теории графов, теории распараллеливающих/оптимизирующих преобразований программ, линейной алгебры. Для проверки эффективности предлагаемых алгоритмов также использовался метод численного эксперимента.

Научная новизна

Разработан новый алгоритм умножения матриц, который показывает большую производительность по сравнению с известными пакетами OpenBLAS, Intel MKL и PLASMA.

Разработана модель времени выполнения программ для систем с общей памятью, которая отличается от известных учетом латентности разных уровней иерархии памяти.

Впервые разработана система поддержки автоматизированного блочного размещения многомерных массивов в оперативной памяти компилятором, которая позволяет получать ускорение для широкого класса программ.

Теоретическая значимость

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

Практическая значимость

Разработанные директивы блочного размещения данных позволяют компиляторам генерировать более быстрый код. Реализованный алгоритм умножения матриц может быть использован для ускорения многих задач линейной алгебры. Разработанная модель времени выполнения программ может быть использована для прогнозирования времени работы программ. Реализованный парсер языка ФОРТРАН позволяет использовать систему ОРС (Оптимизирующая распараллеливающая система www.ops.rsu.ru) для оптимизации программ, написанных на языке ФОРТРАН. Полученные результаты могу быть использованы для создания новых инструментов разработки быстрых программ.

Личный вклад

Все результаты, приведенные в диссертации, разработаны автором лично. В исследованиях использовалась система ОРС, которая разработана на мехмате ЮФУ. Автор диссертации является одним из разработчиков ОРС.

Использование результатов работы

Часть результатов диссертации используются в учебном процессе мехмата Южного федерального университета в магистерской программе "Высокопроизводительные вычисления и технологии параллельного программирования". Результаты диссертации могут использоваться предприятиями, разрабатывающими системное и высокопроизводительное программное обеспечение.

Гранты, поддерживавшие исследования диссертации

Стипендия Правительства РФ 2014 г.

ФЦП "Исследования и разработки по приоритетным направлениям научно-технологического комплекса России на 2009-2013 гг" "Распараллеливание программ с одновременной оптимизацией обращений к памяти" по государственному контракту от "10" октября 2013 г. № 14.514.11.4104

Внутренний грант ЮФУ по Программе развития университета на период до 2021 года в целях повышения конкурентоспособности среди ведущих мировых научно-образовательных центров "Разработка библиотеки алгоритмов решения задач с теплицевыми матрицами и анализ их вычислительных характеристик" 01.05.2013 - 15.12.2013

Лаборатория Ангстрем-ЮФУ.

ФЦП "Научные и научно-педагогические кадры инновационной России", по теме "Создание биоинформационной технологии поиска взаимосвязанных сценариев организации в геномах животных и человека некодирующей ДНК и кодирующей белок ДНК" Государственный контракт № 14.740.11.0006 от 1 сентября 2010.

ФЦП "Научные и научно-педагогические кадры инновационной России" на 2009-2013 годы по лоту "Проведение научных исследований коллективами научно-образовательных центров в области информатики" шифр "2009-1.1-113-050" по теме: "Диалоговый высокоуровневый оптимизирующий распараллеливатель программ и его приложения" (шифр заявки "2009-1.1-113-050-043") Государственный контракт № 02.740.11.0208 от 7 июля 2009 г.

Внутренний грант Южного федерального университета "Учебно-научная лаборатория оптимизации и распараллеливания программ", 2007г.

Степень достоверности и апробация результатов работы

Достоверность результатов диссертации подтверждается математической строгостью изложения алгоритмов, многими численными экспериментами.

Результаты, изложенные в диссертации, опубликованы в 13 научных работах, включая 6 из перечня российских рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание учёных степеней доктора и кандидата наук, в том числе 1 в издании, индексируемом в реферативной базе Scopus, 1 монографию и 6 материалов научных конференций. Имеется свидетельство о государственной регистрации программы ЭВМ. Эти результаты также докладывались на семинарах и конференциях:

1. Национальный суперкомпьютерный форум (НСКФ) 2015.

2. Московский суперкомпьютерный форум (МСКФ) 2014.

3. Параллельные вычислительные технологии (ПаВТ) 2014.

4. Московский суперкомпьютерный форум (МСКФ) 2013.

5. YSC-2013 "High Performance Computing and Simulation", Барселона, Испания. 2013.

6. VI сессия научной школы-практикума молодых ученых и специалистов "Технологии высокопроизводительных вычислений и компьютерного моделирования: технологии eScience".НИУ ИТМО. 09.04.13-12.04.13

7. XIV молодежная конференция-школа с международным участием "Современные проблемы математического моделирования", п. Абрау-Дюрсо, 12-17 сентября 2011 года.

8. На научном семинаре ФГУП Квант, весна 2011 г.

9. "Научный сервис в сети Интернет", г. Новороссийск, 20-26 сентября 2010 г.

10. На постоянно действующем научном семинаре мехмата ЮФУ "Автоматическое распараллеливание программ".

Основные положения, выносимые на защиту

1. Модель времени выполнения программ для систем с общей памятью.

2. Высокопроизводительный алгоритм умножения матриц, использующий нестандартное размещение данных.

3. Автоматизация блочного размещения данных в оперативной памяти.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения, списка сокращений и списка литературы. Текст диссертации изложен на 127 страницах и содержит 15 примеров, 23 рисунка и 16 таблиц. Список литературы содержит 104 наименования.

Основное содержание работы

Первая глава носит вспомогательный характер. В ней описываются понятия, необходимые для изложения результатов диссертации. В параграфе 1.1 приведены принципы работы иерархии памяти современных вычислительных систем. В частности, говорится, что уровнями иерархии памяти являются оперативная память, многоуровневая кеш-память и регистры процессора, в которых также можно хранить данные (Рисунок 1).



Рис. 1: Иерархия памяти многих современных процессоров.

Дается определение кеш-памяти, виртуальной памяти, кеш-памяти TLB.

Параграф 1.2 посвящен методу тайлинга, который предназначен для оптимизации временной локальности данных. В параграфе 1.3 приведено определение пространственной локальности данных, а также различных методов размещения данных. В частности, описывается блочное размещение данных, автоматическую поддержку которого реализовал автор диссертации в системе ОРС. Блочное размещение - это способ хранения массива в памяти, при котором массив разбивается на блоки одинакового размера. Блоки матрицы хранятся в памяти последовательно без промежутков (Рисунок 2). Элементы, находящиеся внутри одного блока, хранятся в памяти стандартным образом, например, по строкам:

Рис. 2: Блочное размещение элементов матрицы 8x8. На месте элементов матрицы расположен относительный адрес соответствующего элемента.Общая формула вычисления адреса элемента с индексом (i,j) матрицы X имеет следующий вид:

(1)

где N2 - количество элементов в строке матрицы X, d1xd2 - размер блока.

В параграфе 1.4 приводится понятие выравнивания данных в памяти. На примерах представлено как производится выравнивание данных современными компиляторами. Параграф 1.5 содержит обзор компиляторов, которые содержат в своем составе оптимизации работы с памятью. В частности, приводится описание проекта TALC, который входит в систему компиляторов ROSE и представляет собой расширение языков C/C++. Следует отметить, что блочные размещения массивов не поддерживаются проектом TALC.

Вторая глава посвящена построению модели прогнозирования времени выполнения программ. Данная модель позволяет определять оптимальные параметры для блочных программ. Сначала приводится общая формула времени выполнения программ, которая имеет следующий вид:

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

Таблица 1. Результаты профилировки блочного алгоритма Флойда-Уоршалла

N	d	LL3 cache miss impact	L2 cache miss impact	L1 cache miss impact	Elapsed (sec)	Theoretical time (sec)
2048	64	1.2	6.9	0.22	47.919996	27.39792
2048	96	1.0	5.2	0.44	46.652864	26.6684
2048	128	0.92	4.4	0.7	45.936372	26.30375
2048	160	0.92	3.1	0.95	45.513963	26.08492
2048	176	3.0	2.5	0.79	47.382814	26.00534
2048	192	6.0	1.7	1.0	49.601719	25.93903
2048	256	11.0	0.41	1.2	50.248607	71.89401

Из эксперимента видно, что оптимальный размер блока равен 160. В таблице приведено также теоретическое время работы программы, которое вычисляется с использованием полученной формулы времени выполнения программы. Теоретическое значение размера блока близко к практическому значению и равно 192.

В таблице 2. приведены результаты численного эксперимента, в котором замерялось время работы блочного алгоритма Флойда-Уоршалла с блочным размещением.

Таблица 2. Результаты профилировки блочного алгоритма Флойда-Уоршалла с блочным размещением

N	d	LL3 cache miss impact	L2 cache miss impact	L1 cache miss impact	Elapsed (sec)	Theoretical time (sec)
2048	272	0.26	1.1	0.59	43.762151	25.72449
2048	336	0.28	0.85	0.61	43.48941	25.62641
2048	400	0.31	0.87	0.51	43.375812	25.55972
2048	496	0.44	0.84	0.47	43.320609	25.49195
2048	528	0.53	0.68	0.5	43.144292	25.47484
2048	560	0.88	0.68	0.42	43.352389	25.45968
2048	624	2.7	0.48	0.41	44.037547	25.43403
2048	688	3.9	0.1	0.56	44.883257	71.89401

Из эксперимента видно, что оптимальный размер блока равен 528. Теоретическое оптимальное значение размера блока близко к практическому значению и равно 624.

Параграф 2.3 посвящен анализу масштабируемости параллельного блочного алгоритма Флойда. В конце параграфа приводится оценка оптимального количества ядер процессора, при котором теоретическое время работы алгоритма будет минимальным.

В параграфе 2.4 описывается метод статического определения количества кеш-промахов, возникших во время выполнения алгоритма.

Третья глава посвящена построению высокопроизводительного алгоритма умножения матриц рекордной производительности. В параграфе 3.1 описываются существующие высокопроизводительные алгоритмы умножения матриц (Intel MKL, PLASMA и OpenBLAS). В параграфе 3.2 приводится описание алгоритма умножения матриц рекордной производительности. В основе реализованного автором алгоритма умножения лежит следующий блочный алгоритм умножения матриц, представленный на листинге 1.

Листинг 1. Основа алгоритма умножения матриц рекордной производительности

void MatrixMult(double* A, double* B, double* C) {

for (dk=0; dk<K; dk+=Dk)

for (di=0; di<M; di+=Di)

for (dj=0; dj<N; dj+=Dj)

BlockAAddr = … // вычисление адреса блока матрицы A

BlockBAddr = … // вычисление адреса блока матрицы B

BlockCAddr = … // вычисление адреса блока матрицы C

BlockMult(BlockAAddr, BlockBAddr, BlockCAddr);

}

Внутри функции BlockMult производится умножение блоков матрицы A и матрицы B, результат сохраняется в блок матрицы C. Матрицы при реализации такого алгоритма умножения разбиваются на блоки согласно схеме представленной на Рисунке 3.

Рис. 3. Схема разбиения матриц для высокоуровневой части алгоритма умножения матриц

Особенностью предлагаемого алгоритма является то, что данные хранятся в памяти дважды блочно. Так, матрица A размещается в оперативной памяти прямоугольными блоками размера , которые хранятся по столбцам:

Рис. 4. Размещение блоков матрицы A в оперативной памяти. Стрелки показывают, где блоки матрицы хранятся в оперативной памяти.

Матрица B размещается в оперативной памяти блоками размера , которые хранятся по строкам:

Рис. 5. Размещение блоков матрицы B в оперативной памяти. Стрелки показывают, где блоки матрицы хранятся в оперативной памяти.

Матрица C разбивается на блоки размера , которые хранятся по строкам:

Рис. 6. Размещение блоков матрицы C в оперативной памяти. Стрелки показывают, где блоки матрицы хранятся в оперативной памяти.

Умножаемые блоки при таком размещении разбиваются на блоки меньшего размера согласно схеме, представленной на Рисунке 7.



Рис. 7. Разбиение блока матрицы A, блока матрицы B и блока-результата матрицы С для размещения их в оперативной памяти.

Параметр L выбирается, исходя из размера кеш-памяти L1, а именно - L должно быть таким, чтобы умножаемый блок второго уровня матрицы A, умножаемый блок второго уровня матрицы B, а также блок матрицы С с результатами вычислений помещались в кеш-памяти L1:

В этом случае элементы блока матрицы B не будут вытесняться между итерациями.

В параграфе 3.3 приводятся результаты численных экспериментов, в которых сравнивается производительность программной реализации разработанного алгоритма умножения матриц, а также программных реализаций других алгоритмов (Intel MKL, PLASMA, OpenBLAS). В частности, для случая, когда размер матрицы A равен и размер матрицы B равен графики производительности приведены на Рисунке 8.



Рис. 8. Графики производительности программных реализаций предлагаемого алгоритма, а также алгоритмов пакетов MKL, OpenBLAS и PLASMA. Случай, когда размер матрицы A равен и размер матрицы B равен .

Тестирование проводилось на вычислительной системе с процессором Intel Core i7-3820 с выключенной опцией Turbo Boost. Размер кеш-памяти L1 равен 64 КБ, размер кеш-памяти L2 равен 1 МБ, размер кеш-памяти L3 равен 10 МБ, тактовая частота 3.6 ГГц. В качестве компилятора использовался Intel C++ Composer XE. Пиковая производительность вычислительной системы равна 115,2 ГФЛОПС.

Производительность программной реализации считалась в гигафлопсах по формуле

,

где T - время работы программы в секундах.

Согласно результатам всех проведенных численных экспериментов, для значений N более 2000 программная реализация предлагаемого алгоритма по производительности превосходит программные реализации алгоритмов MKL, PLASMA, OpenBLAS, и его производительность составляет в среднем 98-99% от теоретической производительности процессора.

В четвертой главе приводится алгоритм автоматизации блочных размещений данных в системе ОРС. Такая автоматизация реализована автором на уровне директив компилятора, описание которых приводится в параграфе 4.2. Перед объявлением блочно размещаемого массива указывается директива

#pragma ops array declare(name, array dimension size list, block dimension size list) (1)

где name - имя размещаемого массива, array dimension size list - массив размерностей размещаемого массива по каждому измерению, block dimension size list - массив размерностей блока по каждому измерению.

В данной директиве указывается информация о размере массива, а также размере блоков, на которые указанный массив стоит разбить.

Оператор, в котором производится выделение памяти для массива A, следует пометить директивой

#pragma ops array allocate(name) (2)

Директива (2) заменяет исходный оператор выделения памяти новым оператором освобождения памяти, в котором выделяется память под блочно размещенный массив. Блочно размещенный массив должен иметь размер кратный размеру блока, т.к. выполнение данного условия на практике сильно упрощает генерацию индексных выражений. Аналогично, оператор, в котором производится освобождение памяти массива A, следует пометить директивой

#pragma ops array release (name) (3)

Директива (3) заменяет исходный оператор освобождения памяти на новый оператор освобождения памяти, в котором освобождается память, выделенная под блочно размещенный массив.

В параграфах 4.3-4.4 приводится описание программных проектов (OPS5Demo и Web-распараллеливатель), в которых можно протестировать работу данных директив. В параграфах 4.5-4.5 строится алгоритм обработки компилятором директив блочного размещения данных. Параграф 4.7 содержит результаты численных экспериментов, в которых сравнивается время работы программ, скомпилированных в двух режимах - без директив блочного размещения данных и без них.

Для проверки эффективности и корректности представленных директив написан пакет прикладных блочных программ, аннотированных директивами блочного размещения данных. В таблице 3 приведены результаты сравнения производительности программ, скомпилированных с включенной опцией блочного размещения данных, а также без нее. Тестирование производилось на компьютере с процессором Intel Core i5-2410M Processor (3M Cache, 2.90 GHz). В качестве компилятора использовался Intel C++ Composer XE 2013 SP1 for Linux, Update 3.

Таблица 3. Результаты тестирования директив блочного размещения в памяти компилятором Intel C++ Composer XE 2013 SP1 for Linux, Update 3

Название алгоритма	Размер матриц	Размер блока	Время работы алгоритма без директив (сек)	Время работы алгоритма с дирек- тивами (сек.)	Ускорение
Блочное LU-разложение матрицы	2048x2048	256x256	27.4	14.44	1.9
Быстрое двумерное преобразование Фурье	4096x4096	4x4	5.16	4.54	1.14
Блочный алгоритм Флойда	2048x2048	256x256	47.49	41.17	1.15
Блочное QR-разложение матрицы	2048x1024	256x256	19.6	17.11	1.15
Блочное умножение квадратных матриц	2048x2048	256x256	14.93	11.2	1.33
Блочное возведение матрицы в квадрат	2048x2048	256x256	81.37	17.36	4.69

Как видно из результатов таблицы, ускорение, получаемое за счет использования представленного преобразования блочного размещения данных, сильно зависит от входной программы. Так, для программы, реализующей блочное QR-разложение матрицы, ускорение составляет 1.15 раза, в то время как для программы, реализующей быстрое блочное возведение матрицы в квадрат, ускорение составляет 4.69 раз.

Следует отметить, что автоматизация блочного размещения массивов является дополнением к преобразованию программы к виду с блочными вычислениями и дает дополнительное ускорение. Если автоматизировать переход к блочным вычислениям, то обе автоматизации возможны одновременно, и программист должен будет лишь один раз указывать в прагмах размеры блоков, этим самым, минимизируя интеллектуальные усилия. Автоматизацию преобразования программы к блочным вычислениям выполняют другие разработчики ОРС.

В заключении подводятся итоги исследований, представленных в диссертации. Описываются основные полученные результаты, решенные задачи, обсуждается их новизна и практическая значимость. Обосновывается достижение цели диссертации.

Заключение

В диссертации проведены исследования, направленные на оптимизацию работы с памятью существующих вычислительных систем.

Построенная модель времени выполнения программ позволяет оценивать время работы программ. В ней учитываются частота процессора, а также различные характеристики иерархии кеш-памяти, такие как латентность, физический размер, ассоциативность. Учет этих параметров позволяет прогнозировать более точно время выполнения программ, что было подтверждено численными экспериментами в параграфах 2.1-2.2. Таким образом, описанная в главе 2 модель времени выполнения программ является решением выносимого на защиту положения 3.

В третьей главе описан и реализован высокопроизводительный алгоритм умножения матриц. Этот алгоритм может использоваться для ускорения алгоритмов линейной алгебры, которые сводятся к задаче умножения матриц (например, QR разложение матрицы).

Описанный алгоритм является новым. Его новизна состоит в использовании нестандартного иерархического блочного размещения матриц. Такое размещение матриц позволяет уменьшить количество кеш-промахов и тем самым увеличить общую производительность алгоритма. Таким образом, в данной главе раскрывается решение положения 1, выносимого на защиту.

В четвертой главе приводится алгоритм автоматизации блочных размещений данных, реализованный в системе ОРС. Такая автоматизация реализована на уровне директив компилятора языка Си. Реализована также поддержка блочных размещений для программ, написанных на языке Фортран. С целью внедрения автоматического блочного размещения данных в программах, написанных на языке ФОРТРАН, автором был реализован парсер языка ФОРТРАН 77/90 в системе ОРС, который был апробирован на пакете ACELAN. Этим самым, в данной главе раскрывается решение положения 2, выносимого на защиту.

И так, все поставленные в диссертации задачи решены, и цель диссертации достигнута.

Результаты диссертации внедрены в научных исследованиях (при разработке Оптимизирующей распараллеливающей системы мехмата Южного федерального университета) и в образовании (в магистерской программе "Высокопроизводительные вычисления и технологии параллельного программирования").

Можно выделить следующие рекомендации по применению полученных результатов:

1. Предлагаемый алгоритм умножения матриц может использоваться для ускорения работы существующих пакетов прикладных программ, написанных для процессоров с поддержкой AVX, и использующих умножение матриц в качестве подзадачи. При этом программист должен учитывать, что подаваемые на вход матрицы должны храниться в памяти блочно.

2. Директивы, реализованные в компиляторе языка Си системы ОРС, позволяющие автоматически блочно размещать матрицы, могут использоваться для ускорения программ.

3. Полученная модель времени выполнения может использоваться для прогнозирования времени работы некоторых работающих с матрицами программ и может использоваться для построения подобных моделей для других случаев.

Перспективы дальнейшей работы таковы:

· Адаптация полученных в диссертации методов оптимизации к вычислительным архитектурам близкого будущего и исследование влияния этих методов на производительность оптимизируемых программ.

· Применение изложенных методов оптимизации программ к другим задачам, требующим большого объема вычислений.

Публикации автора по теме диссертации

в журналах из перечня российских рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание учёных степеней доктора и кандидата наук

1. Юрушкин, М.В. Двойное блочное размещение данных в оперативной памяти при решении задачи умножения матриц [Текст] / М.В. Юрушкин // Программная инженерия. - 2016. - C. 132-139.

2. Юрушкин, М.В. Автоматизация блочного размещения данных в памяти компилятором языка Си [Текст] / М.В. Юрушкин // Программная инженерия. - 2013. - C. 355-358. - ISSN 2220-3397.

3. Юрушкин, М.В. Новым процессорам - новые компиляторы [Текст] / М.В. Юрушкин, Б.Я. Штейнберг // Открытые системы. СУБД. - 2013. - Т.1. - С. 55-58. - ISSN 1028-7493.

4. Юрушкин, М.В. Предметно-ориентированные технологии создания виртуальных рабочих пространств в среде облачных вычислений Clavire [Текст] / А.В. Духанов, Е.В. Болгова, Л.Р. Гервич, В.Г. Колпаков, Е.Н. Кравченко, И.И. Курочкин, Е.Д. Масленников, И.В. Офёркин, А.О. Рубцов, С.А. Смирнов, О.Б. Штейнберг, М.В. Юрушкин // Известия ВУЗов. Приборостроение. - Т. 5. - 2013.

5. Юрушкин, М.В. Программирование экзафлопсных систем [Текст] / Л.Р. Гервич, Б.Я. Штейнберг, М.В. Юрушкин // Открытые системы. СУБД. - Т. 8. - 2013. - C. 26-29. - ISSN 1028-7493.

В изданиях, индексируемых в реферативных базах Scopus и Web Of Science

6. Юрушкин, М.В. Автоматизация распараллеливания программ с блочным размещением данных [Текст] / Л.Р. Гервич, Е.Н. Кравченко, Б.Я. Штейнберг, М.В. Юрушкин // Сибирский журнал вычислительной математики. - 2015. - Т. 18, №1. - С. 41-53. - DOI: 10.1134/S1995423915010012.

Прочие публикации

7. монография Юрушкин, М.В. Разработка параллельных программ с оптимизацией использования структуры памяти [Текст] / Л.Р. Гервич, Б.Я. Штейнберг, М.В. Юрушкин // Ростов-на-Дону, изд-во Южного федерального университета. - 2014. - 120 с.

8. Юрушкин, М.В. Диалоговый высокоуровневый автоматический распараллеливатель (ДВОР) [Текст] / Б.Я. Штейнберг, А.А. Абрамов, Е.В. Алымова, А.П. Баглий, С.А. Гуда, Д.В. Дубров, Е.Н. Кравченко, Р.И. Морылев, З.Я. Нис, В.В. Петренко, С.В. Полуян, И.С. Скиба, В.Н. Шаповалов, О.Б. Штейнберг, Р.Б. Штейнберг // Научный сервис в сети Интернет: Труды Всероссийской суперкомпьютерной конференции (20-26 сентября 2010 г., г. Новороссийск) . - М.: Изд-во МГУ. - 2010. - C. 71-75.

9. Юрушкин, М.В. Реализация алгоритма распределения данных под общую и распределенную память в системе ДВОР [Текст] / М.В. Юрушкин // Сборник трудов XIV молодежной конференции-школы с международным участием. Ростов-на-Дону, издательство Южного федерального университета. - 2011. - C. 396-400.

10. Юрушкин, М.В. Распараллеливание и оптимизация программ с помощью Web-ускорителя [Текст] / Е.В. Алымова, Е.Н. Кравченко, Р.И. Морылев, Б.Я. Штейнберг, М.В. Юрушкин // Труды Международной суперкомпьютерной конференции "Научный сервис в сети Интернет": (17-22 сентября 2012 г., г. Новороссийск). - М.: Изд-во МГУ. - 2012. - C. 612-618.

11. Юрушкин, М.В. Модель времени вычислений [Текст] / Б.Я. Штейнберг, М.В. Юрушкин // Тезисы выступлений МСКФ'14. - 2014, http://www.ospcon.ru/node/107941.

12. Юрушкин, М.В. Web-ориентированный автоматический распараллеливатель программ [Текст] / Б.Я. Штейнберг, А.Н. Аллазов, Е.В. Алымова, А.П. Баглий, С.А. Гуда, Д.В. Дубров, Е.Н. Кравченко, Р.И. Морылев, А.С. Рошаль, М.В. Юрушкин, Р.Б. Штейнберг // Труды международной научной конференции ПаВТ'14. - Издательский центр ЮУрГУ. - 2014. - C. 380-380.

13. Юрушкин, М.В. Автоматизация блочного размещения данных в оперативной памяти компилятором языка Си [Текст] / М.В. Юрушкин // Труды международной научной конференции ПаВТ'14. - Издательский центр ЮУрГУ. - 2014. - C. 355-358.

Размещено на Allbest.ru

...