Автоматическое распараллеливание программ для распределенных систем. Статическое построение расширенного графа управления

Модель Message Passing, вероятно, является сегодня наиболее распространенной. В этой модели программа также создает набор задач, каждая из которых содержит локальные данные, и идентифицируется уникальным именем. Задачи могут передавать и принимать сообщения для\от именованной задачи. Таким образом, рассматриваемая модель представляет собой лишь сокращенную версию модели задача/канал – отличие т

олько в механизме передачи данных. Однако на практике большинство message-passing систем при старте программы создают фиксированное количество одинаковых задач и не позволяют создавать или уничтожать задачи во время выполнения. Т.е. эти системы фактически реализуют модель SPMD - “одна-программа-много-данных”, в которой все задачи выполняют одну и ту же последовательную программу над разными данными.

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

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

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

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

История эволюции средств разработки ПО показывает, что в ее процессе решается несколько задач:

n реализация новых языков программирования;

n переработка алгоритмов анализа исходного текста программы с целью генерации наиболее оптимального исполняемого кода;

n максимальное упрощение процесса разработки ПО и др.

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

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

Алгоритм работы такой системы может быть следующим:

1) анализ исходной программы на последовательном языке с целью выяснения скрытого в ней параллелелизма;

2) один или более пробных запусков программы под средой (или в присутствии блока анализа времени выполнения) для получения более полной информации об ее структуре и оценке времени последовательного выполнения;

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

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

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

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

Анализ последовательной программы

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

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

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

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

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

 Скачать реферат