Система автоматизации распараллеливания отображения на мультипроцессор

Аннотация

Цель данной работы — разработка и реализация алгоритмов блока «Эксперт для мультипроцессора» в проекте «Экспериментальная система автоматизации распараллеливания». На основании результатов анализа последовательной программы и характеристик конкретного мультипроцессора «Эксперт» генерирует и оценивает различные варианты распределения вычислений и локализаций данных. После выбора наилучшего варианта он вставляет в последовательную программу директивы OpenMP, посредством которых она превращается в параллельную программу для мультипроцессора. Кроме того, эксперт выдает информацию о прогнозируемой эффективности распараллеливания.

1. Введение

• 1.1 Распараллеливание программ
• 1.2 Стандарт OpenMP
• 1.3 Распараллеливание для OpenMP
• 1.4 Cуть и актуальность проблемы
• 2. Цели дипломной работы
• 2.1 Цели проекта «Система автоматизации распараллеливания»
• 2.2 Цели «Эксперта для мультипроцессора»
• 2.3 Входные данные
• 2.4 Выходные и сохраняемые данные
• 3. Предыдущие решения «систем автоматизации распараллеливания»
• 4. Построение решения задачи
• 4.1 Формат входных данных
• 4.2 Основные аспекты работы эксперта
• 4.3 Оценочные функции
• 5. Пошаговая реализация «Эксперта»
• 5.1 Шаг 1. Предварительный анализ
• 5.2 Шаг 2. Выбор варианта распараллеливания
• 5.3 Шаг 3. Выбор варианта локализации
• 5.4 Шаг 4. Внесение конечных комментариев в Базу Данных и подсчет ускорения
• 5.5 Примеры работы алгоритма
• 5.5.1 Программа «Якоби»
• 5.5.2 Программа «Sor»
• 5.5.3 Программа «Модифицированный SOR»
• 5.5.4 Программа «Модифицированный Якоби»
• 6. Заключение
• Перечень принятых терминов
• Литература

1. Введение

1.1 Распараллеливание программ

Последние годы во всем мире происходит бурное внедрение вычислительных кластеров. Это вызвано тем, что кластеры стали общедоступными и дешевыми аппаратными платформами для высокопроизводительных вычислений. Одновременно резко возрос интерес к проблематике вычислительных сетей (GRID) и широко распространяется понимание того, что внедрение таких сетей будет иметь громадное влияние на развитие человеческого общества, сравнимое с влиянием на него появления в начале века единых электрических сетей. Поэтому, рассматривая проблемы освоения кластеров необходимо принимать во внимание и то, что они являются первой ступенькой в создании таких вычислительных сетей.

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

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

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

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

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

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

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

С 1992 года, когда мультикомпьютеры стали самыми производительными вычислительными системами, резко возрос интерес к проблеме разработки для них параллельных прикладных программ. К этому моменту уже было ясно, что трудоемкость разработки прикладных программ для многопроцессорных систем с распределенной памятью является главным препятствием для их широкого внедрения. За прошедший с тех пор период предложено много различных подходов к разработке параллельных программ, созданы десятки различных языков параллельного программирования и множество различных инструментальных средств.

На Рис. 1 описаны основные особенности симметричных мультипроцессорных систем (SMP). Для данных систем, как модель программирования для мультипроцессоров, возникла модель параллелизма по управлению (в западной литературе используется и другое название — модель разделения работы, work-sharing model). На мультипроцессорах в качестве модели выполнения используется модель общей памяти. В этой модели параллельная программа представляет собой систему нитей, взаимодействующих посредством общих переменных и примитивов синхронизации. Нить (по-английски «thread») — это легковесный процесс, имеющий с другими нитями общие ресурсы, включая общую оперативную память.

Рис. 1. Симметричные мультипроцессорные системы.

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

Первая попытка стандартизовать такую модель привела к появлению в 1990 году проекта языка PCF Fortran (проект стандарта X3H5). Однако, этот проект тогда не привлек широкого внимания и, фактически, остался только на бумаге. Возможно, что причиной этого было снижение интереса к мультипроцессорам и всеобщее увлечение мультикомпьютерами и HPF.

Однако, спустя несколько лет ситуация сильно изменилась. Во-первых, успехи в развитии элементной базы сделали очень перспективным и экономически выгодным создавать мультипроцессоры. Во-вторых, широкое развитие получили мультикомпьютеры с DSM (distributed shared memory — распределенная общая память), позволяющие программам на разных узлах взаимодействовать через общие переменные также, как и на мультипроцессорах (Convex Exemplar, HP 9000 V-class, SGI Origin 2000). В-третьих, не оправдались надежды на то, что HPF станет фактическим стандартом для разработки вычислительных программ.

Крупнейшие производители компьютеров и программного обеспечения объединили свои усилия и в октябре 1997 года выпустили описание языка OpenMP Fortran — расширение языка Фортран 77. Позже вышли аналогичные расширения языков Си и Фортран 90/95.

Параллельно развивалась модель передачи сообщений. Обобщение и стандартизация различных библиотек передачи сообщений привели в 1993 году к разработке стандарта MPI (Message Passing Interface). В модели передачи сообщений параллельная программа представляет собой множество процессов, каждый из которых имеет собственное локальное адресное пространство. Взаимодействие процессов — обмен данными и синхронизация — осуществляется посредством передачи сообщений. Однако разработчики MPI подвергаются и суровой критике за то, что интерфейс получился слишком громоздким и сложным для прикладного программиста.

Успешное внедрение OpenMP на мультипроцессорах и DSM-мультикомпьютерах резко активизировало исследования, направленные на поиски путей распространения OpenMP на мультикомпьютеры, кластеры и сети ЭВМ. Эти исследования сосредоточились, в основном, на двух направлениях:

· расширение языка средствами описания распределения данных;

· программная реализация системы DSM, использующей дополнительные указания компилятора, вставляемые им в выполняемую программу.

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

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

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

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

1.2 Стандарт OpenMP

Интерфейс OpenMP задуман как стандарт для программирования на масштабируемых SMP-системах в модели общей памяти (shared memory model). В стандарт OpenMP входят спецификации набора директив компилятора, процедур и переменных среды. Разработкой стандарта занимается организация OpenMP ARB (ARchitecture Board), в которую вошли представители крупнейших компаний — разработчиков SMP-архитектур и программного обеспечения. Спецификации для языков Fortran и C/C++ появились соответственно в октябре 1997 года и октябре 1998 года.

В OpenMP реализована «золотая середина» между двумя крайностями — полностью автоматическим распараллеливанием и кодированием с явным вызовом нитей; это подход, который основывается на распараллеливании обычных последовательных программ компилятором, но «с подсказками» пользователя, помещающего в исходный текст программы директивы в виде комментариев. Эти директивы указывают компилятору на параллелизм на уровне циклов и отдельных фрагментов программы. За счет этого OpenMP идеально подходит для разработчиков, желающих быстро распараллелить свои вычислительные программы с большими параллельными циклами.

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

Автоматическое распараллеливание весьма затруднено тем обстоятельством, что компилятору трудно (если вообще возможно) распознать взаимозависимости по данным, возможности возникновения тупиков, ситуаций типа «гонки» (race condition) и другие подобные ситуации, которые зачастую определяются поведением программы уже на этапе выполнения. Поэтому возможность получить «подсказку» от пользователя может быть очень ценна.

Однако стандарт OpenMP не ограничивается только набором директив, а специфицирует API [10], который, кроме директив компилятору, включает набор функций системы поддержки выполнения OpenMP-программ, а также переменные окружения. Далее мы рассмотрим основные особенности OpenMP применительно к языку Fortran. Существуют аналогичные средства для языков Си/C++. В рамках OpenMP стандартная последовательная модель языка Fortran расширяется параллельными конструкциями SPMD (Single Program, Multiple Data), которые наиболее близки к традиционной «последовательной» идеологии.

В OpenMP используется модель параллельного выполнения fork/join. Программа начинает выполняться как один процесс, который в ОpenMP называется главной нитью (master thread). Этот процесс выполняется последовательно до тех пор, пока он не дойдет до первой параллельной конструкции (в простейшем случае — области, заключенной между директивами PARALLEL и END PARALLEL). В этот момент создается «бригада» (team) нитей, а «бригадиром» для нее является главная нить. Внутри бригады главная нить имеет номер 0, а число нитей в бригаде задается переменной окружения или может изменяться динамически перед началом выполнения параллельной области путем вызова соответствующей функции системы поддержки выполнения OpenMP-программ. Однако внутри параллельной области число нитей фиксировано.

Кусок программы, заключенный между директивами PARALLEL и END PARALLEL, выполняется параллельно всеми нитями бригады (см. Рис. 3). Операторы программы, логически заключенные между этой парой директив, образуют, в терминологии OpenMP, лексическую (статическую) область действия соответствующей параллельной конструкции. Поскольку указанный блок программы может содержать вызовы подпрограмм, которые тоже могут выполняться параллельно, вводится понятие динамической области действия, который включает и подпрограммы, вызываемые из данного блока.

После завершения выполнения параллельной конструкции нити бригады синхронизируются, а выполнение продолжает только главная нить. Естественно, в программе может быть много параллельных конструкций; соответственно бригады нитей могут образовываться не один раз. OpenMP предусматривает возможность вложения параллельных конструкций (пар PARALLEL/END PARALLEL). Многие «ключи» (clauses) в директивах OpenMP позволяют указать атрибуты данных, действующие в период выполнения соответствующей параллельной конструкции.

По умолчанию, в параллельном регионе частными (приватными) являются индексы параллельных циклов DO, все остальные переменные, по умолчанию, общие. Однако это правило умолчания можно изменить, указав ключ DEFAULT (PRIVATE) или вовсе отменить, если задать DEFAULT (NONE). Счетчики фортрановских DO-циклов следует делать приватными (PRIVATE) для каждой нити бригады. Такие приватные объекты (простые переменные, массивы и т. д.) с точки зрения их обработки эквивалентны тому, как если бы для каждой нити имелась бы декларация нового объекта того же типа. Все ссылки на исходный объект в лексической области действия параллельной конструкции заменяются на ссылки на этот новый приватный объект.

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

Директива THREADPRIVATE (список переменных) объявляет приватными в нитях параллельного региона переменные, описанные в программе. Директива указывается сразу после описания соответствующих переменных и не влияет на работу с ними вне параллельного региона. С ней связана директива COPYIN (список переменных) — для каждой нити параллельного региона создаются копии переменных, описанных в директиве threadprivate, копиям присваиваются текущие значения оригиналов. Имена, указанные в списках директивы threadprivate и параметра copyin, должны совпадать. COPING применяется с директивой parallel.

Существует возможность использования условного оператора: IF (cкалярное_логическое_выражение).

Если этот ключ указан, то соответствующая параллельная область кодов будет выполняться несколькими нитями только при условии, что «скалярное_логическое_выражение» истинно. Например, указав IF (N.GT.1000), можно заставить компилятор породить такую программу, что во время выполнения проверяется размерность (N) и программа выполнялась бы параллельно, только если эта размерность достаточно велика — больше 1000. Это позволяет избегать распараллеливания при маленьких размерностях, когда оно может оказаться невыгодным из-за большой доли накладных расходов.

Важным компонентом стандарта OpenMP является набор подпрограмм времени выполнения и переменных окружения, задающих среду OpenMP:

· subroutine OMP_SET_NUM_THREADS (N) — устанавливает число нитей, равное N.

· integer function OMP_GET_NUM_THREADS () — возвращает число нитей в бригаде.

· integer function OMP_GET_THREAD_NUM () -возвращает номер «текущей» нити (из которой произошел вызов функции) в бригаде.

Кроме указаний на распределение работ между нитями, OpenMP имеет директиву SINGLE/END SINGLE, которая разрешает выполнять заключенный в нее блок Fortran-программы только одной нити.

Для распараллеливания циклов существует директива DO (см. Рис. 4). В качестве «ключей» можно указать описатели PRIVATE (список), FIRSTPRIVATE (список), SHARED (список), ключ REDUCTION, а также ключи ORDERED и SCHEDULE.

Ключ SCHEDULE используется для указания дисциплины планирования выполнения цикла нитями и имеет вид: SCHEDULE (тип[, M])

Он указывает, каким образом итерации цикла будут распределены для выполнения между нитями бригады. В качестве параметра «тип» можно указать следующие:

· STATIC [, m] - блочно-циклическое распределение итераций: первый блок из m итераций выполняет первая нить, второй блок — вторая и т. д. до последней нити, затем распределение снова начинается с первой нити; по умолчанию значение m равно 1;

· DYNAMIC [, m] - динамическое распределение итераций с фиксированным размером блока: сначала все нити получают порции из m итераций, а затем каждая нить, заканчивающая свою работу, получает следующую порцию опять-таки из m итераций;

· GUIDED [, m] - динамическое распределение итераций блоками уменьшающегося размера; аналогично распределению DYNAMIC, но размер выделяемых блоков все время уменьшается, что в ряде случаев позволяет аккуратнее сбалансировать загрузку нитей;

· RUNTIME — способ распределения итераций цикла выбирается во время работы программы в зависимости от значения переменной OMP_SCHEDULE.

·

Если в OpenMP-директиве END DO задано NOWAIT, в конце цикла нити не синхронизируются. Ключ REDUCTION директивы !$OMP PARALLEL DO обозначает редукционную переменную (см. Рис. 5).

В OpenMP имеется также возможность использовать сокращения, позволяющие объединять инструкции PARALLEL/END PARALLEL и DO/ENDDO в пару PARALLEL DO/END PARALLEL DO.

Директива SECTIONS (см. Рис. 6) используется для распределения работы между нитями в «неитерационном» случае. Ключи, как и ранее, могут указывать на тип переменных (PRIVATE, FIRSTPRIVATE и т. д.), а также содержать ключ REDUCTION. OpenMP-конструкция SECTIONS позволяет нескольким нитям выполнять параллельно обычный линейный участок программы на Фортране, разбитый на «секции» — блоки операторов языка. Эти секции могут содержать в себе, в частности, вызовы фортрановских подпрограмм.

Богатые возможности предоставляют средства OpenMP и для синхронизации. Соответствующие директивы позволяют, в частности, установить барьер (!$OMP BARRIER) или обеспечить синхронизацию (!$OMP ATOMIC), предохраняющую от одновременной записи несколькими нитями в одно и то же поле оперативной памяти. Это позволяет предотвратить ситуацию гонки. Другая полезная директива, о которой стоит упомянуть — это !$OMP FLUSH. Она заставляет в соответствующей точке программы получить «согласованное» между нитями состояние оперативной памяти (при этом переменные из регистров будут записаны в память, сбросятся буферы записи и т. д.). Пара директив MASTER: END MASTER выделяет участок кода, который будет выполнен только нитью-мастером. Остальные нити пропускают данный участок и продолжают работу с выполнения оператора, расположенного следом за директивой END MASTER. С помощью директивы CRITICAL оформляется критическая секция программы. В каждый момент времени в критической секции может находиться не более одной нити (см. Рис. 7). Если критическая секция уже выполняется какой-либо нитью P0, то все другие нити, выполнившие директиву для секции с данным именем, будут заблокированы, пока нить P0 не закончит выполнение данной критической секции. Как только P0 выполнит директиву END CRITICAL, одна из заблокированных на входе нитей войдет в секцию. Если на входе в критическую секцию стояло несколько нитей, то случайным образом выбирается одна из них, а остальные заблокированные нити продолжают ожидание. Все неименованные критические секции условно ассоциируются с одним и тем же именем.

Директива ORDERED заставляет коды Fortran, заключенные внутри пары ORDERED/END ORDERED, выполняться в «естественном» порядке (в той, в которой итерации цикла выполняются при нормальном последовательном выполнении). Эта пара директив может присутствовать только в динамической области действия директивы DO (или PARALLEL DO), в которой указан ключ ORDERED. Такие директивы могут использоваться для организации печати в нормальной — скажем, по возрастанию счетчика циклапоследовательности.

1.3 Распараллеливание для OpenMP

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

Из этого следует, что:

· трудно рассчитывать на создание системы полностью автоматизирующей это преобразование, т. е. распараллеливание представляется как итерационный процесс взаимодействия пользователя с системой;

· система не должна ограничивать выбор, а по возможности, должна и подсказывать варианты распараллеливания;

· система должна допускать вмешательство пользователя, т. е. принятие решений самим пользователем;

1.4 Cуть и актуальность проблемы

Преимущества OpenMP:

1) Разработчик не создает новую параллельную программу, а просто последовательно добавляет в текст последовательной программы OpenMP-директивы.

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

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

4) Одним из достоинств OpenMP его разработчики считают поддержку так называемых «orphan» (оторванных) директив, то есть директивы синхронизации и распределения работы могут не входить непосредственно в лексический контекст параллельной области.

5) OpenMP — стандарт, который разработан представительным форумом (HP, IBM, Intel, SGI, Sun, Fujitsu, NEC) для программирования мультипроцессоров и DSM-систем

6) Поддерживается в компиляторах языков Fotran, C, C++ для всех основных типов процессоров.

Однако, «легкость» программирования на OpenMP возможно еще упростить, за счет «системы автоматизации распараллеливания». Если «последовательный» программист будет видеть анализ своей программы и рекомендации по распараллеливанию, «умственные затраты» на вставку распараллеливающих директив сведутся к минимуму или пропадут вообще. Другой вариант использования системы — анализ эффективности уже распараллеленной программы или сравнение ее с другими вариантами распараллеливания. В этом случае заметно облегчается поиск оптимального распараллеливания. Таким образом, при существовании такой системы любой последовательный программист сможет без дополнительной подготовки преобразовывать свой код к «параллельному» варианту. Это особенно актуально для программистов, производящих сложные вычисления, занимающие огромное количество времени. Использование мультипроцессорных систем должно дать заметное ускорение таких вычислений.

2. Цели дипломной работы

2.1 Цели проекта «Система автоматизации распараллеливания»

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

Рис. 8. Проект: Система автоматизации распараллеливания.

На Рис. 8 схематически показаны составляющие проекта: «Анализ программы», «Эксперт для мультипроцессора» (OpenMP) и «Эксперт для кластера» (DVM).

Пользователь создает последовательную программу на языке Fortran. В итоге работы системы, пользователь получает информацию для анализа:

· дерево циклов; для каждого цикла — его параметры и атрибуты (результаты анализа);

· описания данных;

· описание использования массивов в циклах и найденные зависимости;

· список предложенных (в том числе рассмотренных, но отвергнутых) вариантов распределения (задача «Эксперта»);

· созданные и модифицируемые пользователем наборы конфигураций целевой машины и размеров задач;

· для каждого предложенного варианта распараллеливания (всех конфигураций и размеров) и каждого цикла и всей программы, как корня дерева циклов, — оценки времени выполнения и качества распараллеливания для данного варианта (задача «Эксперта»);

Программа, поступая в систему автоматизации распараллеливания, проходит анализ, на основании которого формируется База Данных, в которую входят: дерево циклов; описания массивов, описание использования массивов в циклах; дополнительные комментарии.

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

2.2 Цели «Эксперта для мультипроцессора»

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

2.3 Входные данные

Описание цикла содержит:

· указание на переменную цикла;

· первое, последнее значение;

· наличие в цикле операторов ввода-вывода, побочных выходов и т. п.

· оценка трудоемкости одного витка цикла;

· признак тесной вложенности;

· список обращений к массивам и переменным.

Дерево циклов — множество циклов с отношением «непосредственно вложен в». Корень «дерева циклов», уровень программы, сам циклом не является, но формально может считаться «циклом» без переменной цикла с однократным выполнением.

Список массивов (и простых переменных).

Для каждого массива:

· идентификатор;

· размер по каждому измерению;

· список обращений к массиву.

Вариант задачи:

· размерности массивов по каждому измерению (уже как константы);

· число итераций;

· или значения внешних переменных, от которых зависят эти величины.

Вариант массива процессоров:

· число измерений и размер по каждому измерению (решетка процессоров).

Обращения к массивам (и переменным) в цикле — отношение «к <массиву> обращаются в <цикле>». Для каждой пары <�массив, цикл>:

· нет (не создает) зависимости ни между итерациями, ни внутри;

· зависимость внутри одной итерации;

· REDUCTION (зависимость между итерациями создают операторы специального вида, типа a=a+x_i);

· Private, Lastprivate, Firstprivate — приватные переменные

· возникающая из-за него зависимость между итерациями общего вида.

Список всех обращений, т. е. наборов индексных выражений, желательно без повторений. Про каждое надо указать:

· чтение или/и присваивание;

· индексные выражения;

2.4 Выходные и сохраняемые данные

Выходные данные представляют собой:

· Вариант распараллеливания программы. Вариант представляет собой набор правил получения OpenMP-программы. Оценка эффективности выполняется для данного варианта распараллеливания и данного варианта запуска.

· Оценка данного варианта распараллеливания и данного варианта запуска: параметры производительности цикла, программы в целом и эффективности распараллеливания.

· Информация, объясняющая, почему выбрано данное распределение. Для каждой вставленной директивы производится вычисление ускорения, полученного за счет этой директивы.

3. Предыдущие решения «систем автоматизации распараллеливания»

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

1) Interactive Parallelizing Assistance Tool for OpenMP [7]

Aachen University, Германия. 2003 г.

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

2) Interprocedural Parallelizing Compiler WPP and Analysis Information Visualization tool Aivi [8]

Hitachi, Ltd. Япония. 2000 г.

Система производит межпроцедурный анализ: анализ скаляров и массивов, клонирование процедур, анализ вызовов функций. Система работает только с циклами. Генерация OpenMP директив происходит автоматически. В систему входит мощный инструмент визуализации, показывающий пользователю результаты анализа.

3) The ParaWise Expert Assistant [6]

University of Greenwich, Великобритания. Август 2004.

Представляет собой один из инструментов системы ParaWise/CAPO. На основании инструментов системы, проводящих анализ программы, «Экспертассистент» подсказывает: возможно ли распараллеливание, и представляет некоторые варианты распараллеливания (вставки OpenMP директив).

Новыми свойствами, отличающими нашу систему от перечисленных здесь, являются ориентация на кластер и мультипроцессор и возможность пропустить взаимодействие с пользователем, лишь только запросив «добро» на вставку директив. Первое свойство особо важно, так как распараллеливание программ для будущих высокопроизводительных систем с многоуровневым параллелизмом связано с использованием обеих моделей OpenMP и DVM.

4. Построение решения задачи

Так как решение задачи вставки OpenMP директив напрямую зависит от данных, предоставляемых анализатором, то построение решения задач «Эксперта» мы можем рассматривать только в тесной привязке к данным анализа.

4.1 Формат входных данных

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

· Процедура. В данной версии «Системы автоматического распараллеливания» процедурой считается только тело программы.

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

· Линейный фрагмент.

· Условный оператор.

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

4.2 Основные аспекты работы эксперта

При составлении алгоритмов эксперта были учтены следующие возможности OpenMP:

1) возможность работы с циклами (директива DO).

2) возможность обработки редукционных переменных (директива REDUCTION).

3) возможность исполнять часть кода внутри цикла в «естественном» порядке (директива ORDERED).

4) возможность приватизировать переменные (директива PRIVATE).

5) возможность образовывать конвейер посредством OpenMP директив (эта возможность будет рассмотрена ниже).

6) возможность отмены синхронизаций между параллельными циклами (директива NOWAIT).

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

1) содержащие ввод/вывод.

2) содержащие выход из цикла.

Основная цель «Эксперта» — нахождение для последовательной программы набора директив OpenMP такого, что ускорение параллельной программы при заданном варианте работы программы будет максимально. Назовем такой набор директив наилучшими комментариями к программе. Все комментарии разобьем на два вида: комментарии по локализации переменных (PRIVATE, REDUCTION и т. д.) и все другие комментарии. Назовем Вариантом параллелизма программы (далее Вариант параллелизма) - вариант директив OpenMP, описывающих параллельные области и параллельные циклы (без директив локализации переменных). Тогда Вариант локализации переменных (Вариант локализации) - вариант директив локализации переменных. Для каждого варианта параллелизма может существовать несколько вариантов локализации. Проверкой Альтернативной Локализации назовем нахождение минимума оценочной функции для набора локализаций для данного варианта параллелизма с фиксированием комментариев, соответствующих минимальной оценочной функцией. Схема распараллеливания — фиксация одного варианта параллелизма и одного варианта локализации.

Работа Эксперта для мультипроцессора разделена на 4 стадии:

1) Разделение всех циклов программы на ППЦ и ЦНР, обозначение видов ППЦ и предварительное фиксирование набора вариантов локализации переменных.

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

3) Перебор вариантов локализаций программы, фиксирование наилучшей схемы распараллеливания, подсчет ускорения.

4) Расстановка директив OpenMP, соответствующих наилучшей схеме распараллеливания, в программу.

В процессе работы «Эксперта» создаются внутренние представления данных, обеспечивающие решение задачи, представленные в Таблице 1

Таблица 1. Внутренние представления «Эксперта» .

Первое внутреннее представление содержит информацию о локализации переменных.

Эта информация представляет собой 2 пары значений, по которым однозначно можно определить директиву OpenMP, с помощью которой переменная будет локализована в программе нужным способом.

Пометки проставляются для всех переменных, используемых внутри данного оператора. Все возможные пометки представлены в Таблице 2.

Таблица 2. Пометки по локализации переменных.

Как пометки соответствуют директивам OpenMP:

Если 2-е значение 1-й пары = Set, переменную необходимо объявить PRIVATE.

Если 2-е значение 2-й пары = Set, переменную необходимо объявить SHARED.

Если 1-е значение 1-й пары = reduction, необходима директива REDUCTION (2-е значение 1-й пары: имя переменной).

Если 1-е значение 1-й пары = lastprivate, необходима директива LASTPRIVATE (имя переменной).

Если 1-е значение 1-й пары = firstprivate, необходима директива FIRSTPRIVATE (имя переменной).

4.3 Оценочные функции

1) Оценочная функция стоимости параллельного региона вычисляется по следующей формуле:

Стоимость параллельного исполнения = (стоимость последовательного исполнения / число нитей + стоимость ordered) * число итераций + стоимость создания и удаления параллельной области стоимость последовательного исполнения

Это стоимость одной итерации цикла (предоставлена анализатором) без учета стоимости выражений, окруженных директивами Ordered/End Ordered число нитей — количество «полезных» процессоров. Для цикла это значение равно минимуму из общего количества процессоров и количества итераций цикла.

стоимость ordered = стоимость последовательного исполнения выражений, окруженных директивами Ordered/End Ordered.

стоимость создания и удаления параллельной области = const + стоимость создания m приватных переменных + стоимость синхронизации. Константа зависит от архитектуры системы и берется из базы данных или определяется пользователем. Это время, необходимое для создания (инициализации) и удаления параллельного региона.

стоимость создания m приватных переменных = m, где m это количество приватных переменных в данном параллельном регионе. Так как известно, что единица стоимости последовательного исполнения программы эквивалентна единичной записи в память, то для создания m локальных переменных возьмем время равное m «условных единиц». Это связано с тем, что для каждой нити необходимо инициализировать m переменных.

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

2) Оценочная функция стоимости вычисляется по следующей формуле:

Стоимость конвейера = стоимость действий внутри конвейера * количество действий конвейера + инициализация конвейера + синхронизация конвейера.

стоимость действий внутри конвейера = стоимость последовательного исполнения внутреннего цикла (конвейер возможен лишь для тесно вложенных циклов).

количество действий конвейера, количество действий, когда в работу задействована хотя бы 1 нить.

инициализация конвейера = const, зависит от архитектуры системы и берется из базы данных или определяется пользователем.

синхронизация конвейера = количество директив FLUSH, BARRIER и ENDDO * количество локальных переменных * количество действий конвейера.

3) Оценочная функция региона равна сумме всех оценочных функций членов региона.

5. Пошаговая реализация «Эксперта»

5.1 Шаг 1. Предварительный анализ

Данные на входе: База Данных с результатами статического анализа.

Данные на выходе: 1-е внутреннее представление.

Как проходит преобразование входных данных в выходные:

Циклы разделяем на ППЦ и ЦНР, параллельно рассчитывая локализацию по умолчанию. Линейные фрагменты и условные операторы просто переносим. Проход по дереву осуществляется «сверху-вниз» .

Алгоритм преобразования входных данных в выходные:

Проходим по дереву циклов из Базы Данных, в зависимости от вершины делаем соответствующие действия.

Если вершина — цикл, неподдающийся распараллеливанию переносим его в первое внутреннее представление с пометкой ЦНР.

Если вершина — ППЦ, проводим следующую последовательность действий:

1) В текущую версию комментариев к вершине в первом внутреннем представлении записать ППЦ.

2) Пометить уровень вложенности (исходя из того, что «тело» программы имеет уровень 0).

3) Для всех переменных, используемых в данном цикле во временном представлении сделать пометки:

· Для индекса: private, ind, shared, no

· Для остальных: private, pos, shared, def

4) Если есть редукция в цикле: для всех редукционных переменных сделать пометки: reduction, " операция редукции" , shared, no

5) Если в цикле присутствует скалярная зависимость по данным: для всех переменных со скалярной зависимостью сделать пометки: private (lastprivate), set, shared, no

6) Если цикл содержит зависимость по данным в массиве: проставить для данного цикла пометку ordered и для оператора, соответствующего первому использованию массива, имеющего зависимость, в теле цикла пометку «первое использование ordered», для оператора, соответствующего последнему использованию массива, имеющему зависимость, в теле цикла поставить пометку «последнее использование ordered». Массивы, вызвавшие зависимость занести в список «массивов с зависимостями» .

Если вершина — линейный фрагмент или ветвление - просто переносим вершину из Базы Данных в 1-е внутреннее представление.

5.2 Шаг 2. Выбор варианта распараллеливания

Данные на входе: База Данных с результатами статического анализа, 1-е внутреннее представление.

Данные на выходе: незаконченное 2-е внутреннее представление.

Как проходит преобразование входных данных в выходные:

Для ППЦ выбираем наилучший вариант комментариев. Одновременно создается 2-е внутреннее представление, отражающее наилучшую схему распараллеливания: перебором всех возможных вариантов распараллеливания и альтернативных локализаций. Поиск наилучшего распараллеливания происходит «снизу-вверх»: сначала спускаемся на самый нижний уровень, находим распараллеливание для него, затем поднимаемся на 1 уровень выше и находим наилучшее представление для данного уровня и т. д. При нахождении наилучшего варианта распараллеливания на уровне пытаемся объединить подряд стоящие эффективные для распараллеливания циклы в параллельный регион. Если возникает конфликт локализации в регионе, он делится на регионы, в которых не будет конфликта.

На этом шаге обходим дерево из 1-ого внутреннего представления и выбираем наилучшую схему распараллеливания для вложенных ППЦ и объединяем в параллельные регионы «соседние» ППЦ. Для параллельных регионов перебираем все возможные варианты комментариев с фиксированием наилучшего из них во 2-м внутреннем представлении.

Алгоритм преобразования входных данных в выходные:

Проходим вершины дерева из 1-го внутреннего представления. Изначально все ППЦ помечаются как не пройденные. Продолжаем действия, пока не останется не пройденных ППЦ.

Основные действия шага 2:

1) Находим ППЦ наибольшего уровня (т.е. самый «низший» по вложенности) и делаем уровень найденного цикла текущим.

2) Для всех циклов текущего уровня сравниваем 3 оценочных функции:

a) оценочная функция для последовательного варианта,

b) оценочная функция при распараллеливании данного цикла,

c) оценочная функция при распараллеливании вложенных циклов, при том, что данный цикл остается последовательным (этот вариант оценивается только, если существуют вложенные ППЦ).

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

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

5) Далее, цикл помечается, как пройденный. Если на уровне не осталось не пройденных циклов, текущий уровень становится на единицу меньше, и продолжаются действия 2). Если же текущий уровень принял значение 0, то после того, как не останется не пройденных ППЦ формируется второе внутреннее представление, отражающее все циклы, эффективные для распараллеливания.

Как происходит установка NOWAIT для подряд стоящих параллельных циклов:

Условие проверяется для подряд идущих циклов при добавлении нового цикла в параллельный регион.

· Если у последнего цикла в параллельном регионе есть пометка NowaitIn (означает, что перед предыдущим циклом уже установлена директива NOWAIT), то проверить условие Nowait для пар (новый цикл, последний цикл в параллельном регионе). Если условие истинно проверять условие для пар всех (новый цикл, цикл с пометкой NowaitOut), причем начиная с предпоследнего и в обратном порядке, до первой неудачной проверки или до первого цикла без пометки NowaitOut. Если не было неудачных проверок, поставить у нового цикла пометку NowaitIn, а у последнего в параллельном регионе NowaitOut (означает, что после цикла установлена директива NOWAIT).

· Если же у последнего цикла в параллельном регионе нет пометки пометка NowaitIn, то проверить условие Nowait для пар (новый цикл, последний цикл в параллельном регионе). Если условие истинно, поставить у нового цикла пометку NowaitIn, а у последнего в параллельном регионе NowaitOut.

Проверка условия Nowait между двумя циклами:

· Если множество переменных/массивов для 2 подряд идущих циклов не пересекается (за исключением индексов — они могут быть одинаковыми), то проверка удачна.