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

На правак рукописи Юрушкин Михаил Викторович Оптимизация размещения массивов в общей памяти Специальность 05.13.11— Математическое н программное обеспечение вычислительных машин, комплексов и компьютерных сетей лвЮРЕфИ ЛХ диссертации на соискание ученой степени кандидата физико-математических наук Ростов-на-Дону 2016 Работа выполнена в институте математики механики и компьютерных наук федерального государственного автономного образовательного учреждения высщего профессионального образования «Южный федеральный университет».

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

Болдырев Юрий Яковлевич, доктор технических наук. профессор, профессор кафедры прикладной информатики федерального госуларствеппога автономного образовательного учреждения высшего образования «Санкт- Петербургский политехнический университет Петра Великого» Булычев Дмитрий Юрьевич, кандидат физико-математических паук„доцент кафелры системного программирования федерального государственного бюдгкетного образовательного учреждения высшего образования «Саикт- Петербургский государственный университет». Федеральное государственное бюлжетиое учреждение науки Институт систем информатики им.

А.П. Ершова Сибирского отделения Российской академии наук. Научный руководитель: Официальные оппоненты: Ведущая организация: Университетская наб„7/9 и на сайте йц ч://г11зьег.ь Ьп.гп/г11ззег/зо1зйа!е! и-цсп'опо'-з1е п1/г11з- Ььдега!!з/14ПОО".!ящ! Автореферат разослан " 20 г. Ученый секретарь диссертационного совета Д 212.232.51, д.ф.-м.н., профессор Демьянович Юрий Казимирович Защита состоится 6 октября 2016 г.

в 15:30 на заседании диссертационного совета Д 2! 2.232.51 иа базе Санкт-Петербургского государственного университета по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 28,математико-механический факультет. ауд, 405. С диссертацией можно ознакомиться в Научной библиотеке им.М. Горького СанктПетербургского государственного университета по адресу 199034, Санкт-Петербург, ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность Высокопроизводительные вычисления используются во многих отраслях экономики.

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

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

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

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

Исключение составляет пакет Р1 АЯМА для решения задач линейной алгебры. В нем реализованы алгоритмы некоторых важных задач линейной алгебры 1умножение матриц, Ш-разложение матрицы, ЯК-разложение матрицы, разложение Хол ецкого и тд.), которые работают с бл очно размещенными матрицами. Также в нем реализованы специальные функции, которые производят переразмещения из стандартного вида в блочный вид хранения матриц. Описанные выше исследования показали высокую эффективность блочных вычислений и блочных размещений матриц. Но не рассмотрены возможности двойного блочного размещения матриц и не рассмотрены возможности использования блочных размещений матрицы компилятором.

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

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

При реализации высокопроизводительного алгоритма умножения матриц, а также алгоритма автоматизации блочного размещения матриц в общей памяти использовались методы низкоуровневой графов, оптимизации теории программ, теории распараллеливающих/оптимизирующих преобразований программ, линейной алгебры. Для проверки эффективности предлагаемых алгоритмов также использовался метод численного эксперимента. Научная новизна ° Разработан новый алгоритм умножения матриц, который показывает 60лыпую производительность по сравнению с известными пакетами ОрепВ1.АЯ, 1пге1 МИ и Р1.АЯМА. Разработана модель времени выполнения программ для систем с обшей памятью, которая отличается от известных учетом латентности разных уровней иерархии памяти.

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

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

В исследованиях использовалась система ОРС, которая разработана на мехмате ЮФУ. Автор диссертации является одним из разработчиков ОРС. Использование результатов работы Часть результатов диссертации используются в учебном процессе мехмата Южного федерального университета в магистерской программе "Высокопроизводительные вычисления и технологии параллельного программирования". Результаты диссертации могут использоваться предприятиями, разрабатывающими системное и высокопроизводительное программное обеспечение. Гранты, поддерживавшие исследования диссертации Стипендия Правительства РФ 2014 г.