Автоматическое распараллеливание некоторого класса фортран-программ. Отображение на кластер тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Клинов, Максим Сергеевич

• Клинов, Максим Сергеевич
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Клинов, Максим Сергеевич

Введение.

Актуальность темы.

Цель работы.

Постановка задачи.

Научная новизна работы.

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

Апробация работы и публикации.

Краткое содержание работы.

Глава 1. Обзор систем автоматического и автоматизированного распараллеливания программ на кластер.

1.1 Обзор систем автоматизации анализа и отображения на кластер.

1.2 Подход к автоматическому отображению на кластер.

1.3 Трудности автоматического отображения на кластер.

Глава 2. Схема построения компилятора ПАРФОР.

2.1 Схема работы компилятора ПАРФОР.

2.2 Схема построения ПАРФОР.

2.3 Схема работы эксперта.

2.4 Состав текущей версии ПАРФОР.

2.5 Сценарий использования текущей версии компилятора ПАРФОР.

Глава 3. Алгоритм моделирования параллельного выполнения DVM-программы.

3.1 Описание входных данных.

3.2 Описание выходных данных.

3.3 Алгоритм моделирования вычислений.

3.4 Алгоритм моделирования коммуникаций.

Глава 4. Алгоритм построения схем распараллеливания.

4.1 Алгоритм отбора перспективных вариантов распределения данных .44 4.1.1 Построение графа лтссивов.

4.1.2 Построение вариантов распределения данных.

4.1.3 Построение директив распределения данных.

4.2 Распределение вычислений и организация коммуникаций.

4.2.1 Обобщение использований массивов внутри циклов на внешние циклы.

4.2.2 Построение графа массивов с циклами.

4.2.3 Граф текущего распределения данных.

4.2.4 Определение возможности распараллеливания циклов.

4.2.5 Построение директив распределения вычислений и организации доступа к удаленным данным.

Глава 5. Алгоритм оценки эффективности схем распараллеливания.

5.1 Алгоритм поиска оптимальной решетки.

Глава 6. Исследование алгоритма автоматического распараллеливания

6.1 Результаты автоматического распараллеливания.

6.2 Исследование эвристик отбора распределений данных.

6.3 Исследование организации коммуникаций.

6.4 Исследование алгоритмов моделирования.

6.5 Исследование алгоритма поиска оптимальной конфигурации процессоров.

Введение диссертации (часть автореферата) на тему «Автоматическое распараллеливание некоторого класса фортран-программ. Отображение на кластер»

Актуальность темы

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

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

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

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

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

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

Все больше специалистов предлагают использовать языки с неявным параллелизмом, при программировании на которых не требуется знать архитектуру параллельной ЭВМ. В качестве таких языков особенно привлекательно использовать Фортран и Си/Си++, поскольку их в основном и используют программисты при решении задач, наиболее остро требующих распараллеливания.

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

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

Цель работы

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

Целью данной диссертационной работы являлись:

• разработка алгоритма моделирования параллельного выполнения программ на языке Фортран-DVM [1] и прогнозирования его характеристик;

• разработка алгоритма преобразования последовательной программы на языке Фортран 77 (для класса задач, при решении которых используются разностные методы на статических структурных сетках) в параллельную программу для кластера на языке Фортран-DVM.

Постановка задачи

При автоматическом распараллеливании программ на кластер необходимо использовать в качестве промежуточного языка программирования язык Фортран-DVM. Он имеет ряд преимуществ для решения задачи автоматического распараллеливания.

При автоматическом распараллеливании необходимо оценивать варианты распараллеливания программы, поэтому в качестве первой цели поставлена задача разработки алгоритма моделирования параллельного выполнения Фортран-РУМ-программ.

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

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

• общее время использования процессоров, то есть произведение времени выполнения на число процессоров;

• полезное время - предполагаемое время выполнения на одном процессоре, равное сумме следующих характеристик: полезное процессорное время; полезные системные расходы; время ввода-вывода - сумма времен выполнения операций ввода-вывода, без учета затрат на коммуникации;

• коэффициент эффективности, равный отношению полезного времени к общему времени;

• потерянное время, равное сумме следующих характеристик: время потерь из-за недостаточного параллелизма (дублирования вычислений на нескольких процессорах); время коммуникаций; время простоев процессоров;

• разбалансировка загрузки процессоров при параллельных вычислениях - это потенциальные потери, которые могут быть вызваны неравномерностью загрузки процессоров;

• общее время перекрытия обменов сообщениями и вычислений.

Алгоритм преобразования последовательной программы на языке Фортран 77 в параллельную программу для кластера на языке Фортран-DVM. должен быть ориентирован на распараллеливание программ, удовлетворяющих требованиям:

• Должны быть написаны на языке Фортран 77;

• Не содержать подпрограммы или допускать их инлайн-подстановку;

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

• отсутствие преобразований кода, только вставка директив языка Фортран-DVM (параллельная программа должна минимально отличаться от исходной последовательной);

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

• требования к параллельным циклам, вытекающие из выбора языка Фортран-DVM в качестве языка параллельного программирования они не обязательно должны соблюдаться для всех циклов, для всех массивов и всех их измерений - их нарушение приведет к тому, что соответствующие циклы могут остаться не распараллеленными, а измерения массивов нераспределенными): цикл является тесно-гнездовым циклом с прямоугольным индексным пространством; измерения массивов индексируются только регулярными выражениями типа a*I + b , где I - индекс цикла; между витками цикла могут быть только зависимости (на двух витках цикла идут обращения к одной ячейке памяти, и это мешает выполнять витки параллельно) по редукционным переменным, приватным переменным и регулярные зависимости по массиву; нет операторов ввода-вывода; есть только один вход и один выход из цикла; распределение измерений массивов равными блоками (для распределения неравными блоками требуется информация о зависимости времени выполнения витка цикла от его номера, что трудно получить без профилирования последовательной программы); статическое распределение данных (перераспределения требуются очень редко); отсутствие оптимизации коммуникаций (группировка, асинхронность, удаление ненужных обменов, замена коммуникаций дублирующими вычислениями); сначала выбор вариантов распределения данных (путем грубых оценок их эффективности и применения эвристик), затем выбор вариантов распределения вычислений и организация коммуникаций для них, затем более точная оценка вариантов, построенная на алгоритме моделирования параллельного выполнения Фортран-БУМ-программ.

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

Научная новизна работы

1. Разработан алгоритм моделирования параллельного выполнения DVM-программы (программы на языке Фортран-DVM или Си-DVM), позволяющий прогнозировать время выполнения и другие характеристики эффективности параллельной программы

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

• отбора наиболее перспективных вариантов распределения данных

• распределения вычислений и организации коммуникаций

• выбора наиболее эффективной схемы распараллеливания . программы посредством моделирования ее параллельного выполнения

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

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

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

Алгоритм автоматического отображения последовательной программы на кластер был реализован в экспериментальной версии распараллеливающего компилятора с языка Фортран (компилятора ПАРФОР), созданного в рамках программы Союзного государства "ТРИАДА", и может служить базой для развития алгоритмов отображения последовательных программ на кластер (параллелизм задач, оптимизации коммуникаций, перераспределение данных) и создания алгоритмов отображения на SMP-кластеры.

Апробация работы и публикации

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

1. Всероссийской научной конференции "Научный сервис в сети Интернет: технологии параллельного программирования", сентябрь 2006 г., г. Новороссийск.

2. Всероссийской научной конференции "Научный сервис в сети Интернет: многоядерный компьютерный мир", сентябрь 2007 г., г. Новороссийск.

3. Научной конференции "Тихоновские чтения", октябрь 2008 г., г. Москва.

4. Международной научной конференции "Параллельные вычислительные технологии" (ПаВТ'2009), март 2009 г., г. Нижний Новгород.

5. XIV Байкальской Всероссийской конференции "Информационные и математические технологии в науке и управлении", июль 2009 г., г. Иркутск.

Имеется 5 публикаций [20-24], из которых две [21, 23] - в журналах из списка ВАК.

Краткое содержание работы

В первой главе приводится обзор систем автоматического и автоматизированного распараллеливания программ.

Вторая глава посвящена описанию схемы построения автоматически распараллеливающего компилятора с языка Фортран (ПАРФОР), функций блока преобразования последовательной Фортран-программы в параллельную программу на языке Фортран-DVM, входной и выходной информации этого блока.

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

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

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

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

Автор выражает благодарность коллективу разработчиков системы V-RAY [2] под руководством Воеводина Владимира Валентиновича, в совместной работе с которым были получены первые результаты

12 распараллеливания простейших программ и выявлены основные направления дальнейшего развития.

Автор благодарен Барановой Татьяне Петровне, Вершубскому Валентину Юрьевичу и Ефимкину Кириллу Николаевичу - разработчикам статического анализатора ВерБа, с помощью которого были проверены алгоритмы распараллеливания.

Автор выражает благодарность всем разработчикам компилятора ПАРФОР.

Работа выполнена под руководством доктора физико-математических наук, заведующего отделом Института прикладной математики им. М.В. Келдыша Крюкова Виктора Алексеевича, которому автор выражает искреннюю признательность.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Клинов, Максим Сергеевич

Основные результаты работы

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

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

• отбора наиболее перспективных вариантов распределения данных,

• распределения вычислений и организации коммуникаций,

• выбора наиболее эффективной схемы распараллеливания программы посредством моделирования ее параллельного выполнения.

3. Разработанные алгоритмы программно реализованы в экспериментальной версии распараллеливающего компилятора с языка Фортран.

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

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Клинов, Максим Сергеевич, 2009 год

1. DVM система: сайт.- URL: http://www.keldysh.ru/dvm (дата обращения 26.01.2009).

2. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления, СПб., БХВ-Петербург, 2002, с. 608.

3. Polaris Developer's Document. URL: http://polaris.cs.uiuc.edu/polaris/polarisdeveloper/polarisdeveloper.html (дата обращения 26.01.2009).

4. CAPO (Computer-Aided Parallelizer and Optimizer): сайт.- URL: http://people.nas.nasa.gov/~hjin/CAPO/index.html (дата обращения 26.01.2009).

5. Satoh M., Aoki Y., Wada K., Iitsuka Т., Kikuchi S. Interprocedural parallelizing compiler WPP and analysis information visualization tool Aivi. URL:http://www.compunity.org/events/pastevents/ewomp2000/MakotoPaper.pdf (дата обращения 26.01.2009).

6. The Stanford SUIF Compiler Group: сайт.- URL: http://suif.stanford.edu (дата обращения 26.01.2009).

7. VAST/Parallel. URL: http://www.crescentbaysoftware.com/vastparallel.html (дата обращения 26.01.2009).

8. Kasahara H., Obata M., Ishizaka K. Automatic coarse grain task parallel processing on smp using openmp. // Proc. of 13 th International Workshop on Languages and Compilers for Parallel Computing, Aug. 2000.

9. Intel OpenMP. URL: http://wvAV.intel.com/software/products/compilers/flin/docs/mainfor/merged projects/coptsfor/commonoptions/optionopenmp.htm (дата обращения 26.01.2009).

10. PARADIGM: A Parallelizing Compiler for Distributed Memory Message-Passing Multicomputers: сайт.- URL:http://www.ece.northwestern.edu/cpdc/Paradigm/Paradigm.html. (дата обращения 26.01.2009).

11. Zotov S., Emelianov V., Orlov S., Lifshitz Y., Mnev A. APC: Compiler for Automatic Dynamic Data Partitioning on Multicomputers. // Proc. of 2nd International Conference on Parallel Computing Systems, Ensenada, Mexico, Aug. 1999.

12. Vikram K., Avijit K., Aggarwal S.K. OlyMPIx A Program Parallelization Tool using MPI on Computational Grids. URL: http://www.es.Cornell.eduMcvilaam/papers/pdcn.ps (дата обращения 26.01.2009).

13. Открытая распараллеливающая система: сайт.- URL: http://www.ops.rsu.ru (дата обращения 26.01.2009).

14. Система ParaWise: сайт.- URL: http://www.parallelsp.com (дата обращения 26.01.2009).

15. Applied Parallel Research. FORGE Magic/DM. URL: http://wotug.ukc.ac.uk/parallel/vendors/apr/ProductInfo/dpfdatasheet.txt (дата обращения 26.01.2009).

16. BERT 77: Automatic and Efficient Parallelizer for FORTRAN, сайт.- URL: http://www.basement-supercomputing.com/content/view/24/50/ (дата обращения 26.01.2009).

17. The NAS Parallel Benchmarks: сайт.- URL: http://www.nas.nasa.gov/Resources/Software/npb.html (дата обращения 24.10.2009).

18. Денисов В.Е., Ильяков В.Н., Ковалева Н.В., Крюков В.А. Отладка эффективности DVM-программ. // Препр. ИПМ РАН. 1998. № 74.

19. Клинов М.С. Прогнозирование характеристик эффективности выполнения DVM-программ на кластере. // Вестник Нижегородского университета им. Н.И. Лобачевского, 2009, №. 4, С. 190-197.

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

21. Ustyugov S.D. Three Dimensional Numerical Simulation of MHD Solar Convection on Multiproccesors Supercomputer Systems. // Proc. of the NSO

22. Workshop "Solar MHD: Theory and Observations a High Spatial Resolution Perspective", Sunspot, New Mexico, USA, 18-22 July, 2005.

23. Крюков В.А. Разработка параллельных программ для вычислительных кластеров и сетей. // Информационные технологии и вычислительные системы. 2003. № 1-2. С. 42-61.

24. Учреждение Российской академии наук Межведомственный суперкомпьютерный центр РАН: сайт.- URL: http://www.jscc.ru (дата обращения 17.02.2009).

25. Суперкомпьютер "МВС-ЮОК": сайт.- URL: http://www.jscc.ru/hard/mvsl00k.shtml (дата обращения 26.01.2009).