Содержание к диссертации
Введение
Глава 1 Исследование современного состояния проблемы разработки параллельных программ для многопроцессорных вычислительных систем 11
1.1 Архитектурные особенности построения многопроцессорных вычислительных систем 12
1.2 Технологические подходы к разработке параллельных программ 19
1.3 Анализ возможностей автоматического распараллеливания 25
1.4 Формирование набора требований к параллельным программам 28
1.5 Выбор стратегии модификации параллельных программ 30
1.6 Выводы по главе 1. Постановка задачи 36
Глава 2 Разработка математического обеспечения распределения данных в проблемно-ориентированных параллельных программах 40
2.1 Формализация задачи 40
2.2 Математическая модель распределения времени выполнения параллельных программ 50
2.3 Использование метаязыковых средств как инструмента модификации исходного кода 63
2.4 Лексико-синтаксический анализ исходного кода 74
2.5 Балансировка времени выполнения между гнёздами циклов 80
2.6 Выводы по главе 2 87
Глава 3 Разработка препроцессора «PyNorma» для модификации исходного кода параллельных программ 91
3.1 Основной управляющий скрипт программы 93
3.2 Библиотека ввода/вывод и хранения конфигурации 96
3.3 Библиотека лексико-синтаксического анализа 98
3.4 Библиотека работы с абстрактным синтаксическим деревом 100
3.5 Библиотека балансировки времени выполнения гнёзд циклов 102
3.6 Библиотека генерации тестов 105
3.7 Выводы по главе 3 105
Глава 4 Тестирование препроцессора «PyNorma» на различных аппаратных платформах 107
4.1 Описание аппаратных платформ, на которых производилось тестирование 107
4.2 Результаты тестирования на вычислительном кластере МГУПИ 109
4.3 Результаты тестирования на суперкомпьютере «Ломоносов» 115
4.4 Выводы по главе 4 120
Заключение 121
Библиографический список 126
Приложения 145
- Технологические подходы к разработке параллельных программ
- Использование метаязыковых средств как инструмента модификации исходного кода
- Библиотека лексико-синтаксического анализа
- Описание аппаратных платформ, на которых производилось тестирование
Введение к работе
Актуальность темы исследований. Актуальность исследований в области разработки эффективных параллельных программ в первую очередь определяется необходимостью решения широкого спектра национально-значимых задач в соответствии с приоритетными направлениями развития науки, технологий и техники в Российской Федерации и перечнем критических технологий РФ, утвержднными указом Президента РФ от 7 июля 2011 г. № 899. Широкий спектр задач моделирования использует алгоритмы, в которых вычисления производятся во вложенных циклах над значениями функции на границах элементов (узлах сетки). Проблемно-ориентированные параллельные программы, реализующие подобные алгоритмы, требуют значительных вычислительных ресурсов, формируя тем самым большую часть нагрузки на суперкомпьютерные системы.
В то же время основным вектором развития таких систем является повышение максимальной производительности, определяющей научный и технический потенциал отрасли на ближайшие годы и зависящей от быстродействия аппаратной базы вычислителя и эффективности программного обеспечения (ПО). Причм потребность в вычислительных ресурсах не успевает решаться только за счт наращивания мощности аппаратной платформы средствами замены элементной базы или масштабирования.
Эффективность программного обеспечения для многопроцессорных
вычислительных систем (МВС) определяется приемлемыми временными
рамками обсчта целевой задачи и объмом потребляемых при этом ресурсов
аппаратной платформы. Ручная модификация существующих, и разработка
новых параллельных программ эффективных по одному из вышеприведнных
критериев является трудомкой и затратной процедурой. Использование
оптимизирующих/распараллеливающих компиляторов/систем не всегда
оправдано с точки зрения проблемы «стена памяти» (memory wall), заключающейся в отставании скорости подготовки данных при их передачи по коммуникационной сети от скорости обсчта на вычислительных узлах (ВУ) и
являющейся одним из основных препятствий при достижении экзафлопсного барьера в суперкомпьютерных вычислениях.
Здесь необходимо отметить, что по данным в последние годы акцент в рейтинге проекта TOP500 сместился в сторону вычислительных кластеров – HPC (High-Performance Computing), реализующих архитектуру MPP (Massive Parallel Processing) и занимающих более 84% от общего числа суперкомпьютеров мира с неизменным наращиванием преимущества. В этом контексте ещ более ужесточаются требования к программному обеспечению в части касающейся временной эффективности и ресурсомкости.
Одним из путей преодоления отмеченных проблемных мест в области разработки эффективных проблемно-ориентированных параллельных программ для вычислителей с архитектурой MPP является выбор рационального распределения обрабатываемых данных в локальной памяти данных на вычислительных узлах и, как следствие, повышения быстродействия целевой аппаратной платформы МВС. В рамках данной работы под термином проблемно-ориентированные параллельные программы понимаются программы научно-технического характера, обрабатывающие массивы большой размерности, основные вычисления которых сосредоточены во вложенных циклах (гнздах циклов).
В разное время вопросами параллельных вычислений занимались такие исследователи как Воеводин В.В., Воеводин Вл.В., Тыртышников Е.Е., Жуматий С.А., Стефанов К.С., Антонов А.С., Гергель В.П., Вальковский В.А., Кутепов В.П., Соколинский Л.Б., Букатов А.А., Дацюк В.Н., Жегуло А.И., Корнеев В.Д., Крюков В.А., Андрианов А.Н., Бугеря А.Б., Ефимкин К.Н.
Наиболее близкими к тематике исследования и посвящнные вопросам размещения данных в памяти вычислителя являются работы Штейнберга Б.Я. и Полуяна С.В. Однако, проблематика распределения данных для проблемно-ориентированных параллельных программ, нацеленных на промышленное использование, со сложной структурой исходного кода, остатся решнной не полностью. Описанные выше причины вынуждают развивать методы
минимизации времени выполнения параллельной программы за счт
модификации распределения данных в рамках блоков исходного кода с набором гнзд циклов (cycle nest).
Объектом исследования являются МВС с распределнной памятью. Под термином МВС с распределнной памятью понимаются такие классы суперкомпьютеров как кластерные HPC и массово-параллельные MPP вычислительные системы.
Предметом исследования определн областью исследования № 3 паспорта специальности 05.13.11 «Модели, методы, алгоритмы и программные инструменты для организации взаимодействия программ и программных систем», а также перечнем задач, решаемых в диссертации.
Целью работы является уменьшение общего времени выполнения проблемно-ориентированных параллельных программ за счт снижения потерь времени на пересылку данных между вычислительными узлами средствами рационального размещение массива исходных данных в распределенной памяти МВС.
Задачи исследования. Достижение поставленной цели предполагает решения следующих основных задач:
-
анализ современного состояния проблемы разработки и специфики построения исходного кода проблемно-ориентированных параллельных программ, систематизация методов минимизации времени выполнения без изменения заложенных алгоритмов и аппаратной конфигурации МВС;
-
разработка математической модели, отражающей распределение времени выполнения проблемно-ориентированных параллельных программ с учтом объединения гнзд циклов, имеющих зависимость по данным, в блоки исходного кода;
-
разработка метода лексико-синтаксического анализа исходного кода проблемно-ориентированных параллельных программ для построения абстрактного синтаксического дерева (АСД) и его декомпозиции, для поиска гнзд циклов со связью по данным и объединения их в блоки;
-
разработка системы эвристических правил, позволяющая производить выбор рационального варианта распределения данных для гнзд циклов в рамках блоков исходного кода;
-
разработка метода перераспределения времени выполнения между гнздами циклов со связью по данным в рамках блоков исходного кода;
-
реализация и тестирование препроцессора для выполнения модификации исходного кода проблемно-ориентированных параллельных программ. Методы исследования включают в себя методы теории компиляции
программ, анализа исходного кода, теории графов, теории алгоритмов,
технологии разработки программного обеспечения. При реализации
программного обеспечения использовались принципы параллельного и функционального программирования.
Научную новизну результатов работы определяют:
-
математическая модель распределения времени выполнения параллельной программы, учитывающая группировку гнзд циклов c зависимостью по данным в блоки исходного кода;
-
метод лексико-синтаксического анализа параллельной программы для построения абстрактного синтаксического дерева и его декомпозиции, позволяющий производить поиск/обработку гнзд циклов в блоке;
-
система эвристических правил, позволяющая произвести выбор рационального варианта распределения данных в рамках блоков исходного кода с набором гнзд циклов;
-
алгоритм и программная реализация балансировки времени выполнения между гнздами циклов, позволяющие производить модификацию исходного кода проблемно-ориентированных параллельных программ. Практическая значимость работы состоит в том, что предложенные
модели и методы доведены до конкретных алгоритмов, на основе которых была
сформирована система эвристических правил и разработано программное
обеспечение, посредством которого возможно производить: лексико-
синтаксический анализ исходного кода проблемно-ориентированных
параллельных программ на метаязыке; разбор функциональных элементов
внутреннего представления препроцессора, сформированного в виде абстрактного синтаксического дерева; модификацию параметра распределения данных в рамках блоков исходного кода.
Практическая значимость работы подтверждается соответствующими актами внедрения.
Достоверность и обоснованность полученных результатов, приведенных в диссертационной работе, обеспечивается:
использованием надежных методов исследования и результатами, полученными в ходе экспериментов по уменьшению времени выполнения параллельных программ на различных аппаратных платформах МВС;
апробацией и обсуждением результатов работы на международных и Всероссийских научных конференциях, научными статьями, опубликованными в ведущих научных журналах из перечня ВАК РФ;
разработкой действующих программных средств, подтвержденных свидетельствами о государственной регистрации.
Внедрение результатов работы. Разработано программное обеспечение «Препроцессор PyNorma», на которое получено свидетельство о государственной регистрации программ для ЭВМ Роспатента №2013612115 от 12.01.2013 г. Данный программный продукт использовался в научно-исследовательских работах в ЗАО «Энергокомплект» (акт о внедрении) и в ОАО «Праймтек» (акт о внедрении). Результаты исследования используются в учебном процессе при подготовке специалистов на кафедре «Персональные компьютеры и сети» МГУПИ в рамках дисциплины «Параллельные вычисления».
Апробация работы. Основные положения и результаты диссертационной работы докладывались на международных и Всероссийских конференциях, и семинарах: международной научно-практической конференции «Современные направления теоретических и прикладных исследований», Одесса, 2008, 2010, 2011, 2012 г.; 2, 3, 4, 5 международной научно-практической интернет-конференции «Актуальные проблемы аппаратно-программного и информационного обеспечения науки, образования, культуры и бизнеса», Москва, 2009, 2010, 2011, 2012 г.; ежегодной Всероссийской научной
конференции «Современные тенденции развития теории и практики управления в
системах специального назначения», Москва, 2011, 2012, 2013 г.; 13
Всероссийской научно-технической конференции «Новые информационные
технологии», Москва, 2010 г.; научном семинаре «Проблемы современных
информационно вычислительных систем» под руководством д.ф.-м.н., проф. В.А.
Васенина, МГУ имени М. В. Ломоносова, Москва, 2012 г.; международной
заочной научно-практической конференции «Современные тенденции
экономики, управления, права, социологии, образования, медицины, физики, математики: Новый взгляд», Санкт-Петербург, 2013 г.;
Публикации. По материалам диссертации опубликованы 21 печатная работа, из них 4 статьи в ведущих научных журналах и изданиях, рекомендованных ВАК РФ, 4 статьи в сборниках научных трудов, зарегистрированных в системе Российского индекса научного цитирования (РИНЦ), 6 публикаций в научных трудах международных и Всероссийских конференций, 7 публикаций в журналах и межвузовских сборниках научных трудов.
Структура и объм работы. Диссертация состоит из введения, 4 глав, заключения, библиографического списка и приложений. В конце работы помещены акты о внедрение результатов работы, и справка о регистрации программ. Общий объем работы – 149 страниц машинописного текста, из них 118 страниц – основное содержание, 19 страниц – библиографический список (168 наименований).
Технологические подходы к разработке параллельных программ
На практике наиболее распространены следующие технологические подходы к программированию для МВС [34,37]. Непосредственное формирование потоков параллельного управления, с учетом особенностей архитектур МВС и ОС [35]. Данный подход представляет собой ручное программирование на стандартных и широко распространённых языках программирования с использованием высокоуровневых коммуникационных библиотек и интерфейсов прикладного программирования API (Application Programming Interface) [140] для организации взаимодействия между ВУ. Для МВС с распределённой памятью и ВК стандартом является интерфейс передачи сообщений MPI (Message Passing Interface) [36], для систем с общей памятью – открытый стандарт OpenMP (Open Multi-Processing) [38].
Программный интерфейс MPI представляет собой стандартизованный интерфейс обмена сообщениями между процессами в рамках одной параллельной программы. Разработаны стандартные расширения для различных языков программирования, в том числе для Си/Си++/Фортран. Существуют бесплатные и коммерческие реализации для многих архитектур МВС, а также для ВУ под управлением различных ОС. Реализации стандарта MPI поддерживают программные механизмы взаимодействия между ВУ по типу отношений один к одному и один ко многим. Передача сообщений между ВУ может быть организована с поддержкой буферизованных, небуферизованных, синхронных, асинхронных или с ожиданием методов доставки данных [41]. Интерфейс MPI позволяет использовать минимально-необходимый набор функциональных возможностей, состоящий из 6 функций передачи/приёма сообщений, одновременно с этим являясь достаточно гибким и мощным инструментом, содержащим более 120 различных функций [42]. Открытый стандарт OpenMP является одним из наиболее популярных средств организации параллельных вычислений для МВС с общей памятью и систем с многоядерными процессорами. Технология OpenMP реализует параллельные вычисления с помощью многопоточности, в которой основной (master) поток создает набор подчиненных (slave) потоков с распределением активных задач между ними [39]. Задачи, выполняемые потоками параллельно, так же, как и данные, требуемые для выполнения этих задач, описываются с помощью специальных комментариев. Технология OpenMP позволяет реализовать подход, при котором алгоритм организации параллельных вычислений добавляется в исходный код при помощи специальных комментариев [40]. Перед компиляцией блоки исходного кода с комментариями обрабатываются специальным препроцессором, при этом оставляя неизменным остальной массив исходного кода программы. В случае отсутствия препроцессора, компилятор сгенерирует последовательную программу.
Таким образом, обе технологии дают возможность программирования на стандартных языках с использованием в качестве конструктивных элементов механизмы передачи сообщений или заранее распараллеленных процедур из набора поставляемых библиотек, подразумевая расширение существующего синтаксиса языков операторами распараллеливания и синхронизации. Примерами реализации такого подхода могут служить ряд таких библиотек как Intel Threading Building Blocks (TDB), Boost C++ Libraries, Pthreads, Qt Threads [22, 24, 25, 26]. Уровень параллелизма при использовании данных решений полностью контролируется разработчиком и формируется исходя из его квалификации на основе понимания архитектурных особенностей целевой МВС [116]. Поэтому качественные характеристики параллельной программы напрямую зависит от компетентности специалиста и его умения работать с конкретными технологиями. Перенос ПО разработанного подобным образом без существенной модификации исходного кода с одной архитектуры МВС на другую практически невозможен [44]. В связи с этим наблюдается тенденция к абстрагированию от работы с низкоуровневыми интерфейсами и переход к использованию специализированных средств, позволяющих сосредоточится на алгоритме решения задачи, а не на её реализации. К таким программным средствам можно отнести функциональные/параллельные языки программирования и средства автоматического распараллеливания. Описание параллелизма без использования явного управления. К данной категории в первую очередь относится концепция функционального подхода в программирование, которая не требует явного указания параллелизма задачи [35]. Достаточно задать информационную взаимосвязь между функциями, осуществляющими обработку исходных данных. В этом случае информационный граф алгоритма решения задачи может быть раскрыт компилятором/транслятором с максимально-возможным уровнем параллелизма [76]. В ходе компиляции/транслирования исходного кода программы, производится его преобразование согласно тем требованиям и ограничениям, которые определяются средой выполнения и целевой архитектурой МВС [50]. Функциональный подход предполагает обходиться вычислением результатов функций от исходных данных и служебных функций обработчиков, и не предполагает явного хранения состояния программы [53]. Чистые функции, рекурсия, лямбда-исчисления и другие синтаксические элементы поддерживаться помимо изначально функциональных языков программирования Haskell [45, 46] и Erlang [47, 48] рядом других языках, в частности Python [152, 153], Java [49] и т.д. Несмотря на то, что рассмотренные функциональные языки ориентированы на решение достаточно узкоспециализированных задач, в них может отсутствовать поддержка побочных эффектов вычислений и фиксация порядка следования операторов. Наличие таких свойств или частичная поддержка функциональной парадигмы программирования не делает вышеперечисленные языки функциональными, но потенциально позволяет программисту использовать больше возможностей при разработке параллельных программ [51].
Одним из ключевых преимуществ функциональных программ является то, что они предоставляют широкие возможности для автоматического распараллеливания вычислений [55]. Отсутствие побочных эффектов вычислений ограничено на уровне программной реализации компилятора/транслятора, что позволяет для каждой функции гарантировать параллельное вычисление двух различных входных параметров, так как порядок вычислений не оказывает влияние на конечный результат [52]. Несмотря на рядом потенциальных преимуществ при разработке параллельных программ, функциональный подход не был востребован по причине отсутствия стабильных компиляторов/трансляторов с приемлемой ресурсоёмкость на этапе подготовки вычислений [54].
Использование метаязыковых средств как инструмента модификации исходного кода
С точки зрения размещение массива исходных данных в распределённой памяти МВС, решение задачи нахождения рационального варианта распределения для каждого блока исходного кода с набором ГЦ, может быть найдено, в том числе, с помощью специализированных языковых средств разработки параллельных программ. Современные системы параллельного программирования в большинстве своём реализуют различные механизмы управления размещением массивов с данными в распределённой памяти МВС. Рассмотрим основные программные реализации для систем DVM, трС, НОРМА.
В системе DVM [62] поддерживается распределение блоками (равными и неравными) и распределение выравниванием через директивы DISTRIBUTE (для статических массивов) и REDISTRIBUTE (для динамических массивов). Для одномерных массивов поддерживается несколько форматов задания распределения:
формат BLOCK, при котором исходные массивы данных распределяются последовательно (равномерно) блоками на линейку ВУ;
формат GEN_BLOCK, при котором распределение блоками разных размеров позволяет балансировать нагрузку на ВУ для алгоритмов, которые выполняют разное количество вычислений на различных участках области данных;
формат WGT_BLOCK, при котором распределение обрабатываемых данных задаётся блоками по их относительным «весам»;
формат MULT_BLOCK, при котором размер блока на каждом ВУ будет кратен определённому числу;
формат , при котором исходные данные не распределяются и присутствуют на каждом ВУ целиком.
Для многомерных массивов формат распределения указывается для каждого измерения (индексного направления). Каждая матрицы может быть разбита (равномерно) на вертикальные/горизонтальные полосы (в случае топологии МВС - линейка) или блоки (в случае топологии МВС - решётка) и распределена на ВУ.
В системе трС [34], которая представляет собой расширение языка Си и разрабатывалась специально для реализации параллельных вычислений в сети неоднородных по производительности и/или архитектуре ВУ, присутствует возможность задания способа распределения на уровне данных и команд для ВУ целевой аппаратной платформы МВС. Соответственно поддерживается функционал для описания виртуальной сети/подсети для фиксации соответствия между виртуальными процессорами и физическими ВУ. Для задания распределения данных используется набор ключевых слов и синтаксических конструкций.
Ключевое слово repl, которое указывается перед объявлением переменной, в результате чего помеченная таким образом целевая переменная копируется на каждый ВУ.
Синтаксическая конструкция [+] для переменной указывает на то, что все копии переменной на каждом ВУ нужно сложить и синхронизировать результат таким образом, чтобы на всех ВУ оказалось одинаковое значение суммы всех копий переменной. Синтаксическая конструкция [ ] служит для управления распределением функций, которые должны быть выполнена всеми доступными ВУ.
Синтаксическая конструкция [/lost] в противовес предыдущему объявлению служит, для того, чтобы функция была выполнена одним ВУ.
В данной диссертационной работе по причине невысокой трудоёмкости лексико-синтаксического анализа в качестве инструментария модификации исходного кода использовался декларативный язык программирования сверхвысокого уровня «НОРМА» [111] (Непроцедурное описание разностных моделей алгоритмов). Данный язык и система параллельного программирования в основном предназначены для автоматизации решения вычислительных сеточных задач на МВС с распределённой памятью. Расчётные формулы записываются в математическом виде, затем генерируется исходный код на языках программирования Си/Фортран с использованием одного из поддерживаемых механизмов передачи сообщений (MPI/GNS/PVM) [116]. Основное предназначение данного языка программирования заключается в кодировании численных методов решения задач математической физики разностными методами.
Исходя из области применения рассматриваемого языкового средства и ориентацию на проблемно-ориентированность для разработчика становится возможным определить в рамках данного исследования системы параллельного программирования НОРМА в рамках терминологии метаязыка [119]. Тогда процесс разработки программ для решения научно-технических задач на метаязыке, состоит из следующих основных этапов:
постановка задачи и составление системы дифференциальных уравнений;
выбор пространственно-временной сетки и дискретизация уравнений с помощью одного из разностных методов; выбор метода решения дискретных уравнений и составление формул для выполнения вычислений в узлах сетки [117];
перекодирование формул в синтаксис метаязыка с последующим выполнением на целевой аппаратной платформе МВС.
Основная идея, положенная в основу метаязыка, заключается в том, что полученное на третьем этапе описание решения задачи, почти непосредственно используется для ввода его в вычислительную систему и выполнения расчётов [86]. Организация процесса вычислений с учетом целевой архитектуры МВС, в частности возможностей параллельной обработки данных, является задачей транслятора [113], в то время как большая часть исходного кода представляет собой строгую запись численных методов решения математической задачи. Такая запись не в полной мере является алгоритмом, а набором расчетных формул и другой необходимой информации, необходимой для разработки параллельных программ для научно-технических расчётов. Порядок следования операторов может быть произвольным, так как информационные взаимосвязи будут выявлены и учтены при организации процесса трансляции исходного кода метаязыка в результирующую параллельную программу на Си/Фортран [115] (рис. 2.3.1).
Библиотека лексико-синтаксического анализа
Библиотека лексико-синтаксического анализа принимает входную последовательность в виде словарей с исходным кодом целевой программы из библиотеки обработки вводы/вывода. Первым этапом каждый словарь модифицируется таким образом, чтобы, в следующую ячейку массива помещался вложенный словарь для хранения блоков данных, где каждый блок представляет собой отдельную функцию/раздел параллельной программы. Таким образом, промежуточная структура данных принимает вид набора пар ключ/значение, где хранится исходный код блока с дополнительной информацией.
На рисунке 3.3.1 с помощью ключа --search-part показан вывод промежуточной информации при разбиении массива исходного кода целевой параллельной программы на отдельные блоки. Рисунок 3.3.1. - Вывод промежуточной информации в процессе разбиения массива исходного кода на блоки
К дополнительной информации относятся такие атрибуты как размер блока и наличие точки входа в программу. Вторым этапом каждый блок анализируется отдельно на предмет активных индексов, которые будут использоваться при работе с АСД [115]. При задействовании ключа --search-part выводимые на консоль информационные сообщения помечаются дополнительными цветными маркерами:
[f ] - маркер, отмечающий обрабатываемый в данный момент файл с исходным кодом целевой параллельной программы;
[%] - маркер, отмечающий статус обработки файла в виде полосы прогресса процесса;
[p] - маркер, отмечающий информацию о разделах параллельной программы.
На рисунке 3.3.2 с помощью ключа -- search - index показан вывод работы препроцессора при поиске индексов в каждом блоке параллельной программы.
При задействовании ключа --search-index выводимые на консоль информационные сообщения помечаются дополнительным цветным маркером [i], который отмечает информацию об активных индексах в разделах параллельной программы.
Библиотека построения/работы с АСД использует в своей работе вызовы методов из библиотеки лексико-синтаксического анализа через общий, для всех библиотек препроцессора, прикладной интерфейс (API). В качестве входной последовательности принимается набор вложенных словарей с обработанным исходным кодом и дополнительными атрибутами. В процессе работы набор вложенных словарей преобразуется к виду АСД. Таким образом, исходный код преобразуется в структуру данных вида АСД, которая отражает синтаксическую структуру входной последовательности и хорошо подходит для дальнейшей обработки [122].
На рисунке 3.4.1 с помощью ключа --search-assume показан вывод работы препроцессора при поиске коллективных операторов для каждого блока параллельной программы в процессе построения АСД.
Вывод информации при поиске коллективных операторов в каждом блоке параллельной программы Информация о найденных коллективных операторах добавляется как новый лист к ветви раздела. Сохранённая в таком виде информация в дальнейшем используется в библиотеки вычисления/балансировки вычислительной трудоёмкости. При задействовании ключа --search-assume выводимые на консоль информационные сообщения помечаются дополнительным цветным маркером [a], который отмечает информацию о значении коллективных операторах в рамках одного блока целевой параллельной программы. На рисунке 3.4.2 с помощью ключа --search-di показан вывод работы препроцессора при поиске операторов распределения данных для каждого блока параллельной программы в процессе построения АСД.
Описание аппаратных платформ, на которых производилось тестирование
Параллельные программы, модифицированные с помощью препроцессора PyNorma [138], тестировались на следующих аппаратных платформах:
вычислительный кластер Московского государственного университета приборостроения и информатики (МГУПИ) для отладки, тестирования параллельных программ [154] и получения предварительных результатов [155];
суперкомпьютер «Ломоносов» Московского государственного университета им. Ломоносова (МГУ) для получения основных практических результатов [157].
Характеристики и архитектурные особенности данных МВС представлены далее по тексту. Основные технические характеристики аппаратной платформы вычислительного кластера МГУПИ и суперкомпьютера «Ломоносов» НИВЦ МГУ им. Ломоносова приведены в таблицах 4.1.1 и 4.1.2 соответственно.
На ВУ установлено следующее прикладное и системное ПО:
передача файлов: RCP, FTP;
среды исполнения: OpenMPI 1.4;
языки программирования: C/C++, Fortran 77/90;
наборы компиляторов: GNU 4.0;
системы контроля версий: SVN;
языки сценариев: Perl, Shell.
На ВУ установлено следующее прикладное и системное ПО:
средства резервного копирования NetBackup (Symantec);
средства архивации данных: Bacula 3 (Т-Платформы);
передача файлов: SCP, SFTP;
управление заданиями и ресурсами: SLURM 2.0;
среды исполнения: OpenMPI 1.4, MVAPICH 1.1, IntelMPI 4;
языки программирования: C/C++, Fortran 77/90/95;
наборы компиляторов: Intel 12, GNU 4.4, Pathscale, PGI;
средства отладки и анализа производительности: Intel ITAC 12, grpof 4, Intel vTune 4, Intel Thread Checker, Acumem ThreadSpotter, IDB, Allinea DDT;
системы контроля версий: SVN, GIT;
языки сценариев: Perl, Python, Shell.
На первом этапе исследования тестирование и отладка проводилось на аппаратной платформе МГУПИ, с организацией топологии сети передачи данных в виде «линейки» (linear array) ВУ, которые пронумерованы по порядку кроме первого управляющего [20]. В качестве тестовых параллельных программ использовались программы, реализующие различные действия над матрицами. Структура получаемого исходного кода и распределение времени выполнения в таких программах полностью соответствовали характеру параллельных программ для решения сеточных задач математической физики/механики, используемых в промышленных целях [97].
Рассмотрим несколько практических экспериментов, для которых зависимость времени выполнения целевой параллельной программы от варианта распределения данных в блоке с набором ГЦ наиболее выражена [110]. Результаты экспериментов для параллельных программ, реализующих основные типовые операции над массивами большой размерности, легли в основу системы эвристических правил для препроцессора «PyNorma».
Первая из рассматриваемых тестовых параллельных программ, реализует типовую операцию умножения матриц размерностью 2 103 элементов (вещественные числа двойной точности в Фортран - ), по ленточному алгоритму [158]. В данном алгоритме исходные матрицы разбиваются на горизонтальные и вертикальные полосы, которые копируются на все ВУ в соответствии с вариантом распределения [104]. На ВУ происходит перемножение полос приводит и получение блоков результирующей матрицы [159]. По причине того, что объём памяти, необходимый для одновременного хранения исходных матриц целиком на каждом ВУ, может превысить доступный объём физической памяти узлов, вычисления организуются таким образом, чтобы в каждый момент времени узел содержали лишь часть элементов исходных матрицы, а доступ к остальной части обеспечивался средствами механизма передачи сообщений.
При получение исполняемого (бинарного) кода тестовых параллельных программ с различными вариантами размещения массивов в распределённой памяти МВС, алгоритм умножения матриц описывался средствами метаязыка. Метаязыковой исходный код обрабатывался препроцессором PyNorma в режиме перебора значений (--generateest). В данном режиме работы препроцессор определяет все возможные варианты распределения и генерирует на каждый вариант отдельную параллельную программу [163]. Затем версии параллельных программ на метаязыке транслировались в исходный код на Фортран с вызовами MPI функций, который компилировался в исполняемый код ELF [133] (Executable and Linkable Format) для выполнения на ОС Slackware Linux [134]. Перед компиляцией в исходный код программ на Фортран внедрялись специальные счётчики, использующие системные вызовы ядра ОС Linux, задачей которых являлось вычисление времени выполнения и запись полученных результатов в отдельный файл. Компиляция осуществлялась командой mpif77 -o BIN_NAME SOURCE_NAME.F , а запуск производился командой mpirun -n PROCESSORS_COUNT+1 BIN_NAME , где BIN_NAME – имя файла скомпилированной программы, SOURCE_NAME.F – имя файла с исходным кодом Фортран, PROCESSORS_COUNT – число ВУ для обсчёта вычислительной задачи без учёта управляющего ВУ.
В случае программной реализации типовой операции умножения матриц на НОРМА существует шесть вариантов распределения данных (вдоль трёх индексных направлений по строкам/столбцам решётки ВУ) в результирующей программе на Фортран [110]. На рисунке 4.2.1 приведён график, отражающий зависимость коэффициента ускорения тестовой параллельной программы от значения параметра распределения на вычислительном кластере МГУПИ с задействованием от 1 до 20 ВУ [15]. 110 На графике для наглядности результаты выполнения тестовой программы с близкими значениями были объединены в три группы (, , ). Каждая программа в группе обозначена в соответствии с индексом распределения для ГЦ (основной и служебный ГЦ с глубиной вложения 3) в блоке исходного кода. Группы и показали схожие результаты, в то время как группа , объединяющая результаты для программ с индексами распределения в блоке / (рациональное размещение данных вдоль индекса по топологии МВС), показала прирост производительности в среднем в 2,5 раза по сравнению с точкой отсчёта – наихудшим результатом без ускорения. Заметно явное уменьшение коэффициента ускорения для тестовых программ из групп и после преодоления порога в 12 ВУ. Такое поведение стало результатом уменьшения размера блока данных пересылаемых между ВУ, вследствие того, что размерность исходной задачи оставалась прежней, а число задействованных узлов увеличивалось. В свою очередь это привело к более частым обменам данными между узлами, что спровоцировало рост времени сетевого взаимодействия, следовательно, и суммарное время выполнение параллельной программы. Очевидно, что в случае конкретной реализации задачи умножения матриц и аппаратной платформы рациональное число ВУ находится в пределах от 8 до 12. Однако это утверждение верно для версий тестовых программ с вариантами распределения данных / и / (размещение данных по топологии МВС вдоль индексов и соответственно), объединённых в группы и . Для группы эффект замедления вычислений не наблюдается вплоть до порога в 20 задействованных ВУ.
В следующем эксперименте тестовая параллельная программа, реализует типовые операции поиска максимального элемента в квадратной матрице размерностью 3 103 элементов и умножение матрицы на вектор длинной 2 103 элементов. Тип данных для элементов матриц и вектора, алгоритм генерация версий программ на Фортран, и процедура вставки датчиков аналогичны первому тесту.
