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

Создание модели времени выполнения программ для систем с общейпамятью.2. Использованиенестандартныхразмещенийданныхдляпостроениявысокооптимизированного алгоритма умножения матриц.3. Автоматизация блочного размещения данных.4. Модификация Оптимизирующей распараллеливающей системы.МетодологияМетодология исследования основана на последовательной идентификации ианализепроблемы,исследованииатакжепредлагаемойанализемоделисуществующейвременилитературы.выполненияПрипрограммиспользовалась модель процессора, существенно приближенная к существующимпроцессорам.

Для проверки корректности модели времени выполнения программиспользовалсяметодчисленногоэксперимента.Приреализациивысокопроизводительного алгоритма умножения матриц, а также алгоритмаавтоматизации блочного размещения матриц в обшей памяти использовалисьметоды низкоуровневой оптимизации программ [50], [56], [80], теории графов[97], теории распараллеливающих/оптимизирующих преобразований программ[31],[32]линейнойалгебры[92],[93].Дляпроверкиэффективностипредлагаемых алгоритмов также использовался метод численного эксперимента.7Научная новизна Разработан новый алгоритм умножения матриц, который показываетбОльшую производительность по сравнению с известными пакетамиOpenBLAS, Intel MKL и PLASMA. Разработана модель времени выполнения программ для систем с общейпамятью, которая отличается от известных учетом латентности разныхуровней иерархии памяти. Впервые разработана система поддержки автоматизированного блочногоразмещения многомерных массивов в оперативной памяти компилятором,которая позволяет получать ускорение для широкого класса программ.Теоретическая значимостьПолученные в диссертации результаты могут стать основой для созданияновых методов для эффективного отображения высокоуровневых программ навычислительные архитектуры будущего.Практическая значимостьРазработанные директивыблочногоразмещенияданныхпозволяюткомпиляторам генерировать более быстрый код.

Реализованный алгоритмумножения матриц может быть использован для ускорения многих задачлинейной алгебры. Разработанная модель времени выполнения программ можетбытьиспользованадляпрогнозированиявремениработыпрограмм.Реализованный парсер языка ФОРТРАН позволяет использовать систему ОРС дляоптимизациипрограмм,написанныхнаязыкеФОРТРАН.Полученныерезультаты могу быть использованы для создания новых инструментовразработки быстрых программ.8Личный вкладВсе результаты, приведенные в диссертации, разработаны автором лично. Висследованиях использовалась система ОРС, которая разработана на мехматеЮФУ. Автор диссертации является одним из разработчиков ОРС.Использование результатов работыЧасть результатов диссертации используются в учебном процессе мехматаЮжногофедерального“Высокопроизводительныепрограммирования”.предприятиями,университетавычисленияРезультатыразрабатывающимивимагистерскойтехнологиидиссертациисистемноемогутипрограммепараллельногоиспользоватьсявысокопроизводительноепрограммное обеспечение.Гранты, поддерживавшие исследования диссертацииСтипендия Правительства РФ 2014 г.ФЦП «Исследования и разработки по приоритетным направлениям научнотехнологического комплекса России на 2009-2013 гг» «Распараллеливаниепрограмм с одновременной оптимизацией обращений к памяти» погосударственному контракту от «10» октября 2013 г.

№ 14.514.11.4104Внутренний грант ЮФУ по Программе развития университета на период до2021 года в целях повышения конкурентоспособности среди ведущихмировыхнаучно-образовательныхцентров«Разработкабиблиотекиалгоритмов решения задач с теплицевыми матрицами и анализ ихвычислительных характеристик» 01.05.2013 – 15.12.2013Лаборатория Ангстрем-ЮФУ.ФЦП «Научные и научно-педагогические кадры инновационной России», потеме «Создание биоинформационной технологии поиска взаимосвязанныхсценариев организации в геномах животных и человека некодирующей ДНКи кодирующей белок ДНК» Государственный контракт № 14.740.11.0006 от 1сентября 2010.9ФЦП «Научные и научно-педагогические кадры инновационной России» на2009-2013 годы по лоту «Проведение научных исследований коллективаминаучно-образовательных центров в области информатики» шифр «2009-1.1113-050»потеме:«Диалоговыйвысокоуровневыйоптимизирующийраспараллеливатель программ и его приложения» (шифр заявки «2009-1.1113-050-043») Государственный контракт № 02.740.11.0208 от 7 июля 2009 г.Внутренний грант Южного федерального университета «Учебно-научнаялаборатория оптимизации и распараллеливания программ», 2007г.Степень достоверности и апробация результатов работыДостоверность результатов диссертации подтверждается математическойстрогостью изложения алгоритмов, многими численными экспериментами.Результаты, изложенные в диссертации, опубликованы в 13 научныхработах [62], [63], [64], [65], [66], [67], [68], [69], [70], [71], [72], [73], [74] включая6 в журналах перечня ВАК, один из которых индексируется в БД «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.137. XIVмолодежнаяконференция-школасмеждународнымучастием"Современные проблемы математического моделирования", п. АбрауДюрсо, 12-17 сентября 2011 года.108.

На научном семинаре ФГУП Квант, весна 2011 г.9. «Научный сервис в сети Интернет», г. Новороссийск, 20-26 сентября 2010 г.10.НапостояннодействующемнаучномсеминаремехматаЮФУ«Автоматическое распараллеливание программ».Основные положения, выносимые на защиту1. Высокопроизводительный алгоритм умножения матриц, использующийнестандартное размещение данных.2. Автоматизация блочного размещения данных в оперативной памяти.3.

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

В ней описываютсяпонятия необходимые для изложения результатов диссертации. В параграфе 1.1приведены принципы работы иерархии памяти современных вычислительныхсистем. Дается определение кеш-памяти, виртуальной памяти, кеш-памяти TLB.Параграф1.2посвященметодутайлинга,которыйпредназначендляоптимизации временной локальности данных. В параграфе 1.3 приведеноопределение пространственной локальности данных, а также различным методаразмещения данных. В частности, описывается блочное размещение данных,автоматическую поддержку которого реализовал автор диссертации в системеОРС. В параграфе 1.4 приводится понятие выравнивания данных в памяти.

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

Приводится абстрактная формула времени выполненияпрограмм. На основе данной формулы в параграфах 2.1-2.2 строятсяспециализированные формулы времени выполнения программ, реализующихалгоритм блочного умножения матриц, а также алгоритма Флойда-Уоршалла. Впараграфе 2.3 описывается метод статического определения количества кешпромахов, возникших во время выполнения алгоритма.Третья глава посвящена построению высокопроизводительного алгоритмаумноженияматриц.Ввысокопроизводительныепараграфеалгоритмы3.1описываютсяумноженияматриц.существующиеВчастности,упоминаются пакеты Atlas, Intel MKL, PLASMA и OpenBLAS.

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

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

Результаты численныхэкспериментов подтверждают, что реализованная автоматизация блочныхразмещений дает дополнительное ускорение для некоторых классов задач.Взаключенииподводятсяитогиисследований,представленныхвдиссертации. Описываются основные полученные результаты, решенные задачи,обсуждается их новизна и практическая значимость. Обосновывается достижениецели диссертации.13Глава 1Используемые методы оптимизации работы с данными программы1.1.Дисбаланс производительности процессора и памяти.Вычислительные системы развиваются на протяжении последних десятилетий сбольшой скоростью.

Согласно постоянно обновляющимся спискам Top500производительность компьютеров увеличивается каждый год на 30 процентов.Такой рост до 2005 года был обусловлен наращиванием частоты процессоров. С2005 года по наши дни наблюдается больший уклон в сторону увеличенияколичества ядер внутри одного процессора. Это связано с тем, что увеличиватьчастоту еще больше уже невозможно на практике [57]. Разрыв между временемобработки данных процессором и временем считывания данных из памяти впроцессор увеличивается с каждым годом. Поэтому оптимизация работы спамятью является важной задаче. Память современных процессоров по степениудаленности от процессора имеет иерархическую структуру и включает в себятакие уровни как оперативная память, многоуровневая кеш-память и регистроваяпамять (Рисунок 1).14Рис. 1: Иерархия памяти многих современных процессоров.Чем ближе уровень памяти к процессору, тем больше скорость считыванияданных из этой памяти, но, в то же время, меньше ее размер.