Средства автоматизации распараллеливания программ (курсовая)

Национальный исследовательский университетМосковский энергетический институтКурсовой проектпо дисциплинеПроектирование программного обеспеченияавтоматизированных системСредства автоматизации распараллеливания программвыполнил студентгруппы А-13-08Буренков Сергейнаучный руководительк.т.н., доц. ШамаеваОльга Юрьевнапреподавательк.т.н., доц. МеньшиковаКсения ГеоргиевнаМосква, 2012 годОглавление1. Введение ................................................................................................................................................... 22. Проблемы автоматического распараллеливания ..............................................................

53. Средства автоматического распараллеливания ................................................................. 7BERT–77 .............................................................................................................................................................. 7FORGExplorer .................................................................................................................................................... 9Kuck Accelerator Package............................................................................................................................. 9ДВОР .....................................................................................................................................................................

94. Отладка параллельных программ ........................................................................................... 125. Литература ........................................................................................................................................... 13ВведениеАктуальность автоматизации разработки параллельных программ связана сбурным развитием параллельной вычислительной техники, за которым непоспевают технологии параллельного программирования. Многообразие иусложнение архитектур создает проблемы разработки нового и переносимостистарого параллельного программного обеспечения. Ручное переписывание большихобъемов высокопроизводительного программного обеспечения долго и дорого.Поэтому особенно обостряется потребность в разработке новых инструментовавтоматизации распараллеливания программ для различных суперкомпьютеров,которые могли бы повысить эффективность использования параллельныхкомпьютеров, понизить требования к квалификации программистов, уменьшитьвремя разработки, повысить надежность и удешевить параллельное программноеобеспечение.Мечта о распараллеливающих компиляторах появилась в начале 70-х гг.прошлого века, практически сразу после появления первого параллельногосуперкомпьютера ILLIAK-IV.

Распараллеливающие компиляторы должны былирешить задачу переноса (на уровне исходного кода) накопленных библиотекприкладных программ с последовательных компьютеров на параллельные. Былосовершено множество попыток написания распараллеливающих компиляторов.Профессор Владимир Александрович Вальковский представил обзорразрабатывавшихся в СССР распараллеливающих компиляторов. Обзор охватил 18компиляторов, один из которых имеет объем 10 тыс.

строк, остальные –значительно меньшего объема. Для сравнения, современные распараллеливающиесистемы и компиляторы с функциями автоматического распараллеливания (Intel,2Microsoft, GCC) имеют объем порядка 100 тыс. или даже миллиона строк – и при этомдля эффективного переноса старых последовательных программ на новыепараллельные компьютеры иногда программу приходится переделывать.

[1]Следует отметить, что успешными являются системы автоматическогораспараллеливания для вычислительных машин с общей памятью. Длявычислительных машин с распределенной памятью успешной можно отметитьтолько диалоговую систему Parawise.Разработка последовательно-параллельных программ длявысокопроизводительных кластеров и других параллельных систем продолжаетоставаться исключительно сложным делом, доступным узкому кругу специалистови крайне трудоемким даже для них.

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

Использование гибридноймодели параллельного программирования (MPI + OpenMP) является еще болеесложной задачей. Поэтому вполне естественно, что прикладной программист хотелбы получить либо инструмент, автоматически преобразующий егопоследовательную программу в параллельную, либо высокоуровневый языкпараллельного программирования, обеспечивающий эффективное использованиесовременных параллельных систем.Проведенные в 90-х годах исследования показали, что полностьюавтоматическое распараллеливание для систем с распределенной памятьюреальных производственных программ возможно только в очень редких случаях.Поэтому исследователи сосредоточились на двух направлениях:1)Разработка высокоуровневых языков параллельногопрограммирования (HPF, OpenMP-языки, DVM-языки, CoArray Fortran, UPC, Titanium,Chapel, X10, Fortress);2)Создание систем автоматизированного распараллеливания(CAPTools/Parawise, FORGE Magic/DM, BERT77 и др.), в которых программистактивно вовлечен в процесс распараллеливания. [1]Изначально высокие требования к эффективности выполнения параллельныхпрограмм и последовавшие затем изменения в архитектуре параллельных системЭВМ привели к тому, что в настоящее время нет ни одного параллельногообщепризнанного высокоуровневого языка параллельного программирования длясовременных высокопроизводительных систем.В системах автоматизированного распараллеливания на программиста сталивозлагаться ответственные решения не только по уточнению свойств егопоследовательной программы, но и по ее отображению на параллельную ЭВМ.Кроме того, отсутствие широко распространенного высокоуровневой языка3параллельного программирования вынуждало использовать в качестве выходногоязыка систем автоматизированного распараллеливания низкоуровневые языки.Полученные на них программы сложны для восприятия и внесения в нихмодификаций.

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

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

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

[2]•Проблемы определения информационных зависимостей для линейногокласса программОпределение информационных зависимостей в программе – основараспараллеливающих и оптимизирующих преобразований программ. Известныеметоды не всегда могут точно автоматически установить информационныезависимости в программе. Подавляющее большинство таких методовориентировано на так называемый линейный класс программ. Но даже для этогокласса программ иногда в принципе невозможно автоматически точноустановить зависимость. [3]Более сложные проблемы определения информационных зависимостейвозникают для программ, не принадлежащих линейному классу. Проблемыостаются для тех случаев, в которых:1) на наличие зависимости влияют внешние переменные;2) в случае нелинейной зависимости индексных выражений переменных отсчетчиков циклов;3) при наличии внешних переменных в индексных выражениях массивов;4) наличие псевдонимов.• Проблемы автоматизации распараллеливания на вычислительныесистемы с распределенной памятьюРазмещение массивов в распределенной памяти с оптимизацией затрат намежпроцессорные пересылки.

Минимальные затраты на пересылки реализуютсяпри вычислениях на одном процессоре. Минимизировать следует суммарноевремя пересылок и вычислений. Следует отметить, что время пересылок зависитот коммуникационного устройства и размещения данных в параллельнойпамяти. Здесь же возникает задача оптимальных переразмещений данных приразличных способах организации распределенной памяти. [1]5•Проблема разработки новых эффективно распараллеливаемыхалгоритмовДля решения одной и той же задачи на различных вычислительных архитектурахмогут быть эффективны различные алгоритмы.

Например, при перемноженииматриц небольших размерностей (100-1000 элементов) для процессоров, укоторых время выполнения умножения чисел дольше времени обращения кпамяти (70-ые годы), эффективен алгоритм Штрассена. Для нынешнихпроцессоров стандартный алгоритм перемножения матриц значительноэффективней.

Таким образом, возникает проблема для одних и тех же задачразрабатывать различные алгоритмы для различных вычислительныхархитектур, с различными способами организации памяти, с различнымикоммуникационными системами. [3]•Проблема распознавания алгоритмаПредположим, что следует распараллелить программу перемножения матриц, воснове которой лежит алгоритм Штрассена. Такая программа плохораспараллеливается.