Автореферат (1149956), страница 2
Текст из файла (страница 2)
ФЦП «Исследования и разработки по приоритетным направлениям научнотехнологического комплекса России на 2009-2013 гг» «Распараллеливание программ с одновременной оптимизацией обращений к памяти» по государственному контракту от «10» октября 2013 г. № 14.514.11.4104 Внутренний грант ЮФУ по Программе развития университета на период до 2021 года в целях повышения конкурентоспособности среди ведущих мировых научно-образовательных центров «Разработка библиотеки алгоритмов решения задач с теплицевыми матрицами и анализ их вычислительных характеристик» 01.05.2013 — 15.12.2013 ° Лаборатория Ангстрем-ЮФУ. ° ФЦП «Научные и научно-педагогические кадры инновационной России», по теме «Создание биоинформационной технологии поиска взаимосвязанных сценариев организации в геномах животных и человека некодирующей ДНК и кодируюшей белок ДНК» Государственный контракт № 14.740.11.000б от 1 сентября 201 О.
° ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы по лоту «Проведение научных исследований коллективами научно-образовательных центров в области информатики» шифр «2009-1.1- 113-050» по теме: «Диалоговый высокоуровневый оптимизирующий распараллеливатель программ и его приложения» (шифр заявки «2009-1.1-113- 050-043») Государственный контракт № 02.740.11.0208 от 7 июля 2009 г. ° Внутренний грант Южного федерального университета «Учебно-научная лаборатория оптимизации и распараллеливания программ», 2007г. Степень достоверности и апробации результатов работы Достоверность результатов диссертации подтверждается математической строгостью изложения алгоритмов, многими численными экспериментами. Результаты, изложенные в диссертации.
опубликованы в 13 научных работах, включая б из перечня российских рецензируемых научных журналов, в которых должны быль опубликованы основные научные результаты диссертаций на соискание ученых степеней докгора и кандидата наук. в том числе 1 в издании, индексируемом в реферативной базе ссорив, 1 монографию и б материалов научных конференций. Имеется свидетельство о государственной регистрации программы ЗВМ. Эти результаты также докладывались на семинарах и конференциях: 1. Национальный суперкомпьютерный форум (НСКФ) 2015.
2. Московский суперкомпьютерный форум (МСКФ) 2014. 3. Параллельные вычислительные технологии (ПаВТ) 2014. 4. Московский суперкомпьютерный форум (МСКФ) 2013. 5. т'ЯС-2013 "Н1кЬ Рег(оппапсе Согприппя апд Япш!апоп", Барселона, Испания, 2013. б. У1 сессия научной школы-практикума молодых ученых и специалистов «Технологии высокопроизводительных вычислений и компьютерного моделирования: технологии еЯс1епсе».НИУ ИТМО. 09.04 13-12.04.13 7. Х1Ч молодежная конференция-школа с международным участием "Современные проблемы математического моделирования", п.
Абрау- Дюрсо, 12-17 сентября 2011 года. 8. На научном семинаре ФГУП Квант, весна 2011 г. 9. «Научный сервис в сети Интернет», г. Новороссийск, 20-2б сентября 2010 г. 10. На постоянно действующем научном семинаре мехмата ЮФУ «Автоматическое распараллеливание программ». Основные положении, выносимые на защиту 1. Модель времени выполнения программ для систем с общей памятью. 2. Высокопроизводительный алгоритм умножения матриц, использующий нестандартное размещение данных.
3. Автоматизация блочного размещения данных в оперативной памяти. Структура и объем диссертации Диссертация состоит из введения, четырех глав, заключения, списка сокращений и списка литературы. Текст диссертации изложен на 127 страницах и содержит 15 примеров, 23 рисунка и 1б таблиц. Список литературы содержит 104 наименования. Основное содержание работы Первая глава носит вспомогательный характер. В ней описываются понятия, необходимые для изложения результатов диссертации.
В параграфе 1.1 приведены принципы работы иерархии памяти современных вычислительных систем. В частности, говорится, что уровнями иерархии памяти являются оперативная память, многоуровневая кеш-память и регистры процессора, в которых также можно хранить данные (Рисунок 1). Рис. 1: Иерархия памяти многих современных процессоров. Дается определение кеш-памяти, виртуальной памяти, кеш-памяти П.В. Параграф 12 посвящен методу тайлинга, который предназначен для оптимизации временной локальности данных. В параграфе 1.3 приведено определение пространственной локальности данных, а также различных методов размещения данных. В частности, описывается блочное размещение данных, автоматическую поддержку которого реализовал автор диссертации в системе ОРС.
Блочное размещение — это способ хранения массива в памяти, при котором массив разбивается на блоки одинакового размера. Блоки матрицы хранятся в памяти последовательно без промежутков гРисунок 2). Элементы, находящиеся внутри одного блока, хранятся в памяти стандартным образом, например, по строкам: Рис.
2: Блочное размещение элементов матрицы Ях8. На месте элементов матрицы расположен относительный адрес соответствующего элемента. Общая формула вычисления адреса элемента с индексом (ц) матрицы Х имеет следующий вид: Таблица 1. Результаты профилировки блочного алгоритма Флойда-Уоршалла ТЬеоге11са$ типе (вес) Ь2 сасне 1.1 сас)те ппвв ппи 1птраст пп ас1 Е!аркен (вес) 1Д.З сасне ппвв 1птрас1 27.39792 6.9 0.22 47.919996 46.652864 0.44 1.0 2630375 26.08492 45.936372 45.513963 0.7 2048 128 0.92 0.95 0.92 47.382814 0.79 2048 176 3.0 2.5 49.601719 1.0 6.0 2048 192 71.89401 50.248607 11.0 2048 256 10 асЫг(Ху)= Х+(юг, )ЧН /сЦМ +Г(lй,)ЫМ, +Г!Ч4,)Я~+)%с1, (1) где М2 — количество элементов в строке матрицы Х, д1хс(2 — размер блока. В параграфе 1.4 приводится понятие выравнивания данных в памяти.
На примерах представлено как производится выравнивание данных современными компиляторами. Параграф 1.5 содержит обзор компиляторов, которые содержат в своем составе оптимизации работы с памятью. В частности, приводится описание проекта ТА1С, который входит в систему компиляторов КОКЕ и представляет собой расширение языков С/С++. Следует отметить, что блочные размещения массивов не поддерживаются проектом ТА1 С, Вторая глава посвящена построению модели прогнозирования времени выполнения программ. Данная модель позволяет определять оптимальные параметры для блочных программ. Сначала приводится общая формула времени выполнения программ, которая имеет следующий вид: Т( ) емгор> т Г ) ~иод Г ) где и — размер входных данных, Т(п) — время выполнения программы.
Т,„„,„„,„(п)- общее время выполнения арифметических операций, Т, „Гп) - общее время перекачки данных между оперативной памятью и кеш-памятью. Точная формула времени выполнения зависит от алгоритма. На основе данной формулы в параграфах 2.1-2.2 строятся специализированные формулы времени выполнения программ, реализующих алгоритм блочного умножения матриц, а также блочного алгоритма Флойда-Уоршалла. Точность формул демонстрируется численными экспериментами. В частности, для блочного алгоритма Флойда-Уоршалла результаты численного эксперимента приведены ниже: Из эксперимента видно, что оптимальный размер блока равен 160.
В таблице приведено также теоретическое время работы программы, которое вычисляется с использованием полученной формулы времени выполнения программы. Теоретическое значение размера блока близко к практическому значению и равно 192 В таблице 2. приведены результаты численного эксперимента, в котором замерялось время работы блочного алгоритма Флойда-Уоршалла с блочным размещением. Таблица 2.
Результаты профилировки блочного алгоритма Флойда-Уоршалла с блочным размещением Т)теогепса1 птпе (зес) 1.1.3 сасне ш1як 1ш ас1 Ь2 сасне пэ1зз пп ас1 1.1 сас)те ппзз пп ас~ Е1арзей 1зес) 25,72449 25,62641 2555972 2048 272 2048 336 43.762151 43.48941 43.375812 0.26 0,59 0.28 0.85 0.61 0,51 2048 496 0.44 2048 528 0.53 0.84 43.320609 43.144292 25.49195 25.47484 0.47 0.68 0.5 0.88 0.42 560 0.68 0.41 44.037547 2.7 0.48 25.43403 71.89401 0.56 44.883257 3.9 0.1 11 Из эксперимента видно, что оптимальный размер блока равен 528. Теоретическое оптимальное значение размера блока близко к пракгическому значению и равно 624.
Параграф 2.3 посвящен анализу масштабируемости параллельного блочного алгоритма Флойда. В конце параграфа приводится оценка оптимального количества ядер процессора, при котором теоретическое время работы алгоритма будет минимальным. В параграфе 2.4 описывается метод статического определения количества кеш-промахов, возникших во время выполнения алгоритма. Третья глава посвящена построению высокопроизводительного алгоритма умножения матриц рекордной производительности. В параграфе 3.1 описываются существующие высокопроизводительные алгоритмы умножения матриц (1п1е1 МКЬ, Р1.АЯМА и ОрепВ?.АЯ). В параграфе 3.2 приводится описание алгоритма умножения матриц рекордной производительности.
В основе реализованного автором алгоритма умножения лежит следующий блочный алгоритм умножения матриц. представленный на листинге 1. Листинг 1. Основа алгоритма умножения матриц рекордной производительности Внутри функции 81оскМи1г производится умножение блоков матрицы А и матрицы В, результат сохраняется в блок матрицы С. Матрицы при реализации такого алгоритма умножения разбиваются на блоки согласно схеме представленной на Рисунке 3. 9 С 1Л~ Рис. 3. Схема разбиения матриц для высокоуровневой части алгоритма умножения матриц Особенностью предлагаемого алгоритма является то, что данные хранятся в памяти дважды блочно.
Так, матрица А размещается в оперативной памяти прямоугольными блоками размера Р х 0~, которые хранятся по столбцам: Оперативная память Рис. 4. Размещение блоков матрицы А в оперативной памяти. Стрелки показывают, где блоки матрицы хранятся в оперативной памяти. Матрица В размещается в оперативной памяти блоками размера Р: ~~., которые хранятся по строкам: О! в РМ Оперативная память Рис. 5. Размещение блоков матрицы В в оперативной памяти.
Стрелки показывают, где блоки матрицы хранятся в оперативной памяти. Матрица С разбивается на блоки размера Р "~~, которые хранятся по строкам: Оперативная память Рис. 6. Размещение блоков матрицы С в оперативной памяти. Стрелки показывают, где блоки матрицы хранятся в оперативной памяти. Умножаемые блоки при таком размещении разбиваются на блоки меньшего размера согласно схеме, представленной на Рисунке 7. В!осад ~В!ос~В 8 В1ос1С вЂ” 14 Рис. 7. Разбиение блока В1оН, матрицы А, блока Иос/с„матрицы В и блока- результата ВЬИс матрицы С для размещения их в оперативной памяти. Параметр Е выбирается, исходя из размера кегц-памятн 11, а именно - Е должно быть таким, чтобы умножаемый блок второго уровня матрицы А, умножаемый блок второго уровня матрицы В, а также блок матрицы С с результатами вычислений помещались в кеш-памяти 1.1: (4~8+4" Е+8~1)' вгео1(доиЫе1 < и' еог(1ЛСаиЬе) В этом случае элементы блока матрицы В не будут вытесняться между итерациями.
В параграфе ЗЗ приводятся результаты численных экспериментов, в которых сравнивается производительность программной реализации разработанного алгоритма умножения матриц, а также программных реализаций других алгоритмов 11пге1 МК1., Р1.АБМА, ОрепВ1.АБ), В частности, для случая, когда размер матрицы А равен А ~ 2048 и размер матрицы В равен 2048~ Ю графики производительности приведены на Рисунке 8. 14 с ф~,, ~ ~с ЯиряряФяярйьп) МК1. ~.'рррр.лр марри рийрв рррр) иапо 5СХ Рис. 8. Графики производительности программных реализаций предлагаемого алгоритма„а также алгоритмов пакетов МК1., ОрепВ1.АБ и Р1.АЯМА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
