WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 |   ...   | 2 | 3 ||

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

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

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

В пятой главе описывается алгоритм оценки эффективности разных схем распараллеливания.

В отличие от описанного в третьей главе алгоритма моделирования параллельного выполнения DVM-программы, в DVM-эксперте используется упрощенное моделирование параллельного выполнения программы. Это позволило сократить время оценки схем. К тому же моделирование производится по другой входной информации: не по трассе выполнения программы, а по полученной в результате анализа структуре программы и схеме распараллеливания. Поэтому необходимо знать размеры массивов, параметры циклов (начальное значение, конечное значение, шаг цикла) и свойства условных операторов (вероятность выполнения каждой ветки).

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

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

Решетка задает, на сколько процессоров распределяется каждое измерение данных. Для ускорения моделирования по каждому измерению процессорной решетки берется только по 4 процессора: 3 первых и последний. Загрузка других процессоров будет экстраполирована линейно (по второму и третьему процессору).

Помимо этого для каждого процессора конвейера детально моделируются выполнение только 4-х квантов конвейера (3 первых и последний). По характеристикам второго и третьего кванта экстраполируются характеристики последующих квантов от четвертого до предпоследнего. Характеристики первого и последнего квантов могут отличаться от характеристик средних квантов, и поэтому рассматриваются отдельно.

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

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

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

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

Компилятор ПАРФОР был испытан на ряде простых тестов, проверяющих различные механизмы распараллеливания программ. Также были получены результаты по распараллеливанию реальных приложений. Среди них тесты NAS BT, LU, SP, а также разработанные в ИПМ им.М.В.Келдыша РАН программы MHPDV и ZEBRA. Тексты этих всех программ были получены из их DVM-версий путем удаления всех DVM-директив и инлайн-подстановки процедур в тело головной подпрограммы.

Программа BT (Block Tridiagonal Solver) – нахождение конечноразностного решения 3-х мерной системы уравнений Навье-Стокса для сжимаемой жидкости или газа. Используется трех диагональная схема, метод переменных направлений. При выполнении программы задавался класс С (сетка 162x162x162 и 250 итераций).

Программа LU (Lower-Upper Solver) отличается от BT тем, что применяется метод LU-разложения с использованием алгоритма SSOR (метод верхней релаксации), а программа SP (Scalar Pentadiagonal Solver) – тем, что используется скалярная пяти диагональная схема.

Программа MHPDV – трехмерное моделирование сферического взрыва во внешнем магнитном поле с помощью решения уравнений идеальной магнитной гидродинамики.

Программа ZEBRA – расчет нейтронных полей атомного реактора в диффузионном приближении.

Ниже приводятся времена выполнения исходных вариантов (распараллеленных вручную) программ, а также их вариантов, полученных в результате автоматического распараллеливания.

Таблица 1. Времена выполнения вариантов программ на МВС-100К (сек) (“авт” - автоматическое распараллеливание, “ручн” - ручное) Число Число Число Число Число Варианты процессоров процессоров процессоров процессоров процессоров 1 8 64 256 BT-авт мало памяти 1255.97 182.70 54.64 21.BT-ручн мало памяти 817.88 128.01 30.27 7.LU-авт 3482.40 1009.49 148.78 40.33 25.LU-ручн 2103.14 858.26 122.61 34.99 19.SP-авт 1982.00 - - - - SP-ручн 2601.85 - - - - MHPDV-авт 3703.23 500.78 89.32 34.75 12.MHPDV-ручн 3574.29 486.74 79.63 32.15 10.ZEBRA-авт 75.09 11.13 1.96 - - ZEBRA-ручн 75.62 10.18 1.85 - - Таблица 2. Времена выполнения на Blue Gene/P (ВМК МГУ) Число Число Число Число Число Варианты процессоров процессоров процессоров процессоров процессоров 1 8 64 256 BT-авт мало памяти 2814.59 473.37 166.66 70.BT-ручн мало памяти 1620.97 240.55 72.67 26.LU-авт мало памяти 1897.53 352.28 125.53 61.LU-ручн мало памяти 1670.60 259.09 92.40 47.SP-авт мало памяти - - - - SP-ручн мало памяти - - - - MHPDV-авт 12619.35 1604.29 228.56 59.97 18.MHPDV-ручн 12627.59 1606.61 233.33 61.05 18.ZEBRA-авт 569.73 74.45 10.83 - - ZEBRA-ручн 587.02 76.85 11.06 - - Программу SP распараллелить не удалось (никаких DVM-директив в нее не было вставлено). Для распараллеливания необходима ее серьезная модификация, чтобы избавиться от имеющихся там зависимостей между витками циклов, препятствующих их параллельному выполнению (разные витки одного цикла модифицируют один элемент массива, который не является редукционной или приватной переменной).

Увеличение времени выполнения автоматически распараллеленных вариантов программ BT и LU на малом количестве процессоров объясняется тем, что на этих программах подстановка процедур сильно повлияла на оптимизацию кода компиляторами. Увеличение времени выполнения на большом количестве процессоров происходит из-за того, что DVM-эксперт не сумел организовать доступ к удаленным данным так же эффективно, как это смогли сделать разработчики DVM-системы вручную.

На программах MHPDV и ZEBRA времена выполнения автоматически распараллеленных вариантов близки к временам выполнения вручную распараллеленных вариантов.

Увеличение количества процессоров для программы ZEBRA (свыше 64-х) уже не ускоряет ее выполнение.

Таблица 3. Времена работы DVM-эксперта и характеристики программ BT LU SP MHPDV ZEBRA Время работы DVM1855 96 879 41 эксперта на ПЭВМ (сек) Количество строк 10442 3635 5950 1878 Количество циклов 504 424 499 116 Количество параллелизуемых циклов 481 410 293 115 DVM-экспертом Количество обращений к 30530 6638 11015 4643 массивам Количество массивов 34 30 37 33 Суммарное число 75 64 70 78 измерений 16 22 21 16 Распределение массивов 5 3 3 0 по измерениям 7 0 9 6 (начиная с одномерных 3 5 4 11 массивов) 2 Количество групп 6 5 5 5 измерений Количество построенных 16 16 16 16 схем Среднее время построения 38,56 3,93 2,62 1,43 0,одной схемы (сек) Среднее время оценки эффективности одной 77,39 2,06 52,31 1,13 11,схемы (сек) Общее количество перебранных 127 127 182 144 процессорных решеток В заключении сформулированы основные результаты работы.

Основные результаты работы 1. Разработан алгоритм моделирования параллельного выполнения DVM-программы, позволяющий прогнозировать время выполнения и другие характеристики эффективности параллельной программы 2. Разработан алгоритм автоматического отображения последовательной программы на кластер, состоящий из алгоритмов • отбора наиболее перспективных вариантов распределения данных • распределения вычислений и организации коммуникаций • выбора наиболее эффективной схемы распараллеливания программы посредством моделирования ее параллельного выполнения 3. Разработанные алгоритмы программно реализованы в экспериментальной версии распараллеливающего компилятора с языка Фортран.

На базе разработанного алгоритма моделирования параллельного выполнения DVM-программы был также создан инструмент (DVM-предиктор), позволяющий на инструментальной ЭВМ проводить предварительную отладку эффективности выполнения DVM-программы на кластерах с заданными характеристиками узлов и коммуникационной системы. Этот инструмент используется на факультете ВМК МГУ при проведении практикума по технологиям параллельного программирования.

Публикации по теме диссертации 1. М.С. Клинов, В.А. Крюков. “Прогнозирование характеристик параллельного выполнения DVM-программ”. // Труды Всероссийской научной конференции “Научный сервис в сети Интернет: технологии параллельного программирования”, сентябрь 2006 г., г. Новороссийск. – М.: Изд-во МГУ, 2006, стр. 113-2. М.С. Клинов, В.А. Крюков. Система автоматизированного распараллеливания программ на языке Фортран. DVM-эксперт. // Труды Всероссийской научной конференции “Научный сервис в сети Интернет:

многоядерный компьютерный мир”, сентябрь 2007 г., г. Новороссийск. – М.: Изд-во МГУ, 2007, стр. 95-97.

3. М.С. Клинов, В.А. Крюков. Автоматическое распараллеливание Фортранпрограмм. Отображение на кластер. Вестник Нижегородского университета им. Н.И. Лобачевского, 2009, № 2, с. 128–134.

4. М.С. Клинов. Прогнозирование характеристик эффективности выполнения DVM-программ на кластере. Вестник Нижегородского университета им.

Н.И. Лобачевского, 2009, №. 4, с. 190-197.

5. М.С. Клинов. Алгоритмы автоматического отображения последовательных Фортран-программ на кластер. // Труды Всероссийской научной конференции “Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность”, сентябрь 2009 г., г. Новороссийск. – М.:

Изд-во МГУ, 2009, с. 298-299.

Pages:     | 1 |   ...   | 2 | 3 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»