В модели “Общая память” задачи разделяют общее адресное пространство, в котором они производят чтение и запись асинхронно. Для контроля доступа к разделяемой памяти используются различные механизмы, например, блокировки и семафоры. Преимущество этой модели с точки зрения программиста заключается в отсутствии понятия владельца данных, и, кроме того, отсутствии необходимости обменов между задачей-производителем данных и задачей-потребителем.
Другая часто используемая модель, параллелелизм данных, называется так из-за использования параллелелизма, возникающего при выполнении некоторой операции над многими элементами некоторой структуры данных (например, массива). Поскольку каждая операция над каждым элементом данных может быть представлена как независимая задача, грануляция вычислений мала и концепция локальности не возникает. Однако, компиляторы, реализующие эту модель, часто требуют от программиста информацию о распределении данных между процессорами. Такой компилятор может затем транслировать программу в представление SPMD, автоматически создавая код для осуществления необходимых обменов.
Рассмотренные модели параллельного программирования предоставляют программисту возможность разработки ПО, удовлетворяющего требованиям к параллельным программам. Параллельные языки, созданные на базе традиционных (таких как Fortran, C), или являющиеся их расширением, в той или иной степени реализуют эти модели, оставляя, однако, за программистом проблему выбора параллельного алгоритма и решение задач, связанных с оптимизацией распределения данных, минимизацией расходов на коммуникационные обмены и многих других.
История эволюции средств разработки ПО показывает, что в ее процессе решается несколько задач:
реализация новых языков программирования;
переработка алгоритмов анализа исходного текста программы с целью генерации наиболее оптимального исполняемого кода;
максимальное упрощение процесса разработки ПО и др.
В последнее время необходимость в облегчении работы программиста стала, возможно, наиболее актуальной из-за резко возросшего спроса на программные продукты во всех областях деятельности: время, необходимое на создание работоспособной, максимально свободной от ошибок программы, превратилось чуть ли не в самый значительный параметр. Перерождение тройки «редактор-компилятор-компоновщик» в среду разработки, последующая ее визуализация, и дальнейшее превращение в систему «быстрой разработки программ» позволило программисту сосредоточиться на оптимизации алгоритма, избавив от рутинных действий по созданию исполняемого кода из исходного текста и даже от многих этапов собственно программирования - примером может служить занимающая много времени работа по созданию пользовательского интерфейса.
Разработка параллельного ПО - задача на порядок сложнее, поэтому от средств такой разработки требуется вся помощь, которую они могут предоставить. Программист должен работать в тесном сотрудничестве со своей средой, как получая от нее подсказки, так и предоставляя ей необходимую информацию о структуре программы и обрабатываемых данных в случае невозможности автоматического принятия решения. Одним из подходов к такой разработке может быть написание программы на привычном последовательном языке, с дальнейшей ее трансляцией в текст соответствующего расширенного языка - уже параллельного. Такой метод, во-первых, позволяет осуществлять разработку машинно-независимого продукта - генерация исполняемого кода производится компилятором целевой архитектуры, а, во-вторых, предлагает неплохое решение проблемы существования большого количества уже написанных последовательных программ. Подобные средства разработки носят название «исходный код - в исходный код трансляторы».
Алгоритм работы такой системы может быть следующим:
1) анализ исходной программы на последовательном языке с целью выяснения скрытого в ней параллелелизма;
2) один или более пробных запусков программы под средой (или в присутствии блока анализа времени выполнения) для получения более полной информации об ее структуре и оценке времени последовательного выполнения;
3) выбор оптимального с точки зрения системы варианта распараллеливания и оценка времени параллельного выполнения, основанная на параметрах некоторой целевой архитектуры, заданных пользователем;
4) выдача результатов - величина полученного ускорения и причины невозможности распараллеливания некоторых участков с предоставлением пользователю возможности вмешаться в процесс и дать необходимые инструкции; этот этап продолжается, пока не будет достигнут удовлетворяющий пользователя вариант или он не прекратит дальнейший анализ;
5) генерация текста на целевом параллельном языке и выдача подробного отчета о результатах распараллеливания.
Разработка параллельного ПО является очень трудоемкой задачей из-за сложности определения скрытого параллелелизма, возможности внесения некорректного, нарушающего семантику программы, ложного параллелелизма, и из-за необходимости учитывать большое число факторов, влияющих на конечную производительность программы. Автоматические средства разработки параллельных продуктов и распараллеливания готовых последовательных предоставляют возможность существенно облегчить этот процесс.
Одной из первых задач, возлагаемых на автоматический распараллеливатель программ, является анализ исходной последовательной программы с целью сбора максимального количества необходимой для распараллеливания информации об ее структуре. Данные, полученные на этом этапе, в совокупности с результатами работы блока динамического анализа являются основой дальнейшей деятельности системы.
Задача статического анализа исходной программы может быть условно разделена на два этапа:
1) трансляция текста программы в некоторое внутреннее представление и построение структур, отражающих последовательность работы программы и используемые в ней данные;
2) поиск возможных вариантов распараллеливания с выбором оптимального и определение «узких» участков, препятствующих распараллеливанию.
Рассмотрим несколько более подробно 1-й этап, поскольку решение связанных с ним задач является темой данной дипломной работы. Внутреннее представление программы необходимо для возможности ее анализа независимо от исходного последовательного языка, т.е. оно является точным переложением текста программы, записанным в терминах, понятных системе. Кроме того, оно должно быть достаточным для последующей генерации текста параллельной программы на целевом языке. После создания такого представления, необходимо подняться на такой уровень абстракции, который позволит исследовать алгоритм программы с требуемой точки зрения. Иными словами, надо построить структуры данных, содержащих всю программу в приемлемом для последующего анализа виде, расширенные для возможности хранения и обработки результатов работы других блоков распараллеливателя.
Данная дипломная работа является частью проекта разработки системы автоматического распараллеливания программ на языке Fortran77. Система состоит из нескольких функциональных блоков, каждый из которых реализует один или более этапов построения параллельной программы, сохраняющей семантику заданной последовательной программы. Фиксированный интерфейс обмена данными между ними позволяет производить независимую модификацию каждого блока. Таким образом, система может развиваться в сторону дальнейшего увеличения ее интеллектуальности в принятии решений о возможности распараллеливания входной программы и поиска наиболее эффективных вариантов ее преобразования.
Представляемая система предназначена для распараллеливания программ, написанных на языке Fortran77. Использование этого языка как основного при разработке научных и инженерных приложений на протяжении многих лет привело к образованию большого числа программ, необходимость в которых сохраняется и сегодня. Автоматическая трансляция накопившегося последовательного кода в параллельный позволит использовать новые архитектурные возможности при существенно меньших по сравнению с повторной реализацией затратах. Формируемый системой отчет о принятых в процессе распараллеливания решениях может служить основой рекомендаций по модификации исходного кода с целью достичь наиболее эффективного результата.
Второй аспект применения - разработка параллельного ПО на основе Fortran77. Достоинство такого подхода заключается в использовании привычного языка программирования и передаче системе распараллеливания обязанностей по оценке эффективности реализации алгоритмов с точки зрения параллельного выполнения.
На вход системы автоматического распараллеливания (САР) подается текстовый файл с программой на Fortran77. Она должна, во-первых, быть правильной с точки зрения языка, и, во-вторых, удовлетворять накладываемым системой ограничениям.
Первый шаг - разбор текста средствами библиотеки Sage++, в результате которого образуется файл с внутренним представлением исходной программы.
Задача блока INLINE-подстановки процедур САР заключается в модификации структуры исходной программы с целью привести ее к виду, облегчающему дальнейший анализ и повышающему его точность. В результате его работы образуется файл с внутренним представлением программы, состоящей только из главного модуля, в котором все вызовы подпрограмм заменены их телами. Если исходная программа не содержит процедур, пользователь может не использовать этот блок.
Внутреннее представление без вызовов процедур поступает на вход двух блоков. Первый - блок статического анализа. Его задачей является статическое построение расширенного графа потока управления программы и некоторых вспомогательных структур данных.
Блок подготовки программы для динамического анализа также получает внутреннее представление. Его назначение - создание версии программы для последующей обработки блоком динамического анализа.
Задача блока динамического анализа - дополнение графа управления данными, полученными при выполнении программы в его присутствии. Кроме того, на этом шаге некоторые результаты статического анализа могут быть скорректированы.
Следующий этап - поиск оптимального распределения вычислений и данных между узлами вычислительной сети. Анализ производится на основе информации о возможности распараллеливания тех или иных участков программы, полученной на предыдущих шагах.
Страницы: 1, 2, 3, 4, 5, 6, 7
