В дипломной работе рассматриваются задачи, связанные с технологией автоматического распараллеливания программ.
В первой ее части обсуждаются этапы развития компьютерной науки в области параллельных вычислений, существующие архитектурные и теоретические решения.
Вторая часть содержит описание проекта разработки системы автоматического распараллеливания программ на языке Fortran77, частью которого является данная дипломная работа.
Третья часть посвящена одному из этапов автоматического распараллеливания – созданию внутреннего представления программы, соответствующего проблематике решаемой задачи. Реализация этого этапа является задачей данной дипломной работы.
В четвертой части приведено описание программного кода дипломной работы, осуществляющего решение поставленной задачи.
В приложении содержится один из примеров, использованных при тестировании программы дипломной работы, и распечатка результатов его обработки.
Введение........................................................................................................... 4
1. Система автоматического распараллеливания........................................ 11
1.1 Назначение системы................................................................................ 11
1.2 Схема работы системы автоматического распараллеливания.............. 12
1.3 Постановка задачи дипломной работы.................................................. 14
2. Создание внутреннего представления программы.................................. 15
2.1 Разбор исходного текста. Система Sage++............................................ 15
2.2 Внутреннее представление программы высокого уровня.................... 19
2.3 Расширенный граф управления. Вспомогательные структуры............ 20
3. Построение расширенного графа управления........................................ 24
3.1 Ограничения на входную программу.................................................... 24
3.2 Описание классов.................................................................................... 24
3.3 Алгоритмы............................................................................................... 30
Заключение.................................................................................................... 35
Библиография................................................................................................ 36
Приложение................................................................................................... 37
Введение
Определим параллельный компьютер как множество процессорных устройств, которые могут согласованно работать над решением вычислительных задач. Это определение является достаточно широким, чтобы в него можно было включить параллельные суперкомпьютеры с сотнями или тысячами процессоров, объединенные в сети рабочие станции, многопроцессорные рабочие станции. Параллельные компьютеры представляют интерес из-за возможности объединения вычислительных ресурсов (процессоров, памяти и др.) для решения важных счетных задач. Если раньше параллелелизм относился к несколько экзотическим областям науки, то дальнейшее изучение направлений развития архитектуры компьютеров, сетевых технологий и конечных приложений коренным образом изменило это представление. Использование параллельных вычислений стало повсеместным, а параллельное программирование – центральным направлением в индустрии программного обеспечения.
Несмотря на постоянно увеличивающееся быстродействие компьютеров, нельзя ожидать, что они станут достаточно быстрыми для удовлетворения всех потребностей всевозможных задач вычислительного характера. Напротив, история компьютерной науки показывает, что как только новейшие архитектурные технологии начинают справляться с требованиями уже существующих приложений, очень скоро появляются новые приложения, вызывающие необходимость дальнейшего их развития. И если раньше основным побуждающим фактором создания передовых вычислительных разработок являлись задачи математического моделирования сложных систем - погодные и климатические явления, электронные цепи, производственные процессы, различные физические и химические процессы, то сейчас не меньшее значение приобрели коммерческие приложения, обрабатывающие большие объемы информации: программное обеспечение для проведения видеоконференций, медицинской диагностики, параллельные СУБД, системы виртуальной реальности.
Производительность компьютера напрямую зависит от времени, необходимого для совершения простейшей операции, и количества таких операций, совершаемых одновременно. Это время, в свою очередь, ограничено тактовой частотой процессора, – для которой существует некоторый предел, обусловленный физическими законами. Таким образом, ускорения процессоров недостаточно для дальнейшего увеличения вычислительной мощности. Хотя рост производительности компьютеров от их создания до наших дней описывается экспоненциальным законом (от нескольких десятков операций с плавающей точкой в секунду для первых ЭВМ в 1940-х до десятков миллиардов в 1990-х), наиболее значительным достижением представляется их эволюция от последовательной архитектуры к параллельной.
Другим важным направлением развития, несомненно, сильно изменившим взгляд на вычислительные процессы, является большое увеличение возможностей сетей, соединяющих компьютеры. Резко возросшая пропускная способность, высокая надежность, защищенность передаваемой информации и другие успехи в этом направлении позволяют разрабатывать приложения, использующие физически распределенные ресурсы как части одной системы. Такие приложения могут, например, использовать процессорное время множества удаленных компьютеров, обращаться к распределенным базам данных, осуществлять рендеринг одновременно на нескольких графических станциях.
Таким образом, можно сделать вывод о бесспорной необходимости использования принципов параллелелизма при решении задач, требующих большого объема вычислений (в том числе в реальном времени), а также о существовании позволяющих использовать такой подход архитектурных и сетевых решений.
Основой модели компьютера фон Неймана является процессор, способный выполнять последовательность инструкций. Кроме различных арифметических операций, эти инструкции могут специфицировать адрес данных в памяти для чтения или записи, адрес следующей инструкции. И хотя вполне возможно создавать программы в рамках этой модели при помощи машинных языков, такой метод слишком сложен для большинства приложений. Поэтому на практике применяется технология модульного проектирования, при которой сложные программы конструируются из более простых компонентов, и в этих компонентах используются такие элементы абстракции высокого уровня, как структуры данных, циклы и процедуры. Несколько более высоким уровнем абстракции является технология объектно-ориентированного программирования. Высокоуровневые языки, такие, как Fortran, Pascal, Ada, C, C++, предоставляют возможность разработки ПО в рамках этих технологий с автоматической компиляцией текста в исполняемый код.
Параллельное программирование привносит дополнительный уровень сложности: если мы станем программировать на низком уровне, не только резко увеличится количество инструкций по сравнению с последовательной программой, но и придется подробно распределять задания между, возможно, тысячами процессоров, и координировать миллионы межпроцессорных обменов. Таким образом, модульность можно назвать одним из основных требований к параллельному ПО. Поскольку большинство существующих алгоритмов ориентировано на однопроцессорные системы, очевидна необходимость при разработке новых алгоритмов учитывать особенности одновременного выполнения многих операций: параллельность – неотъемлемое требование к алгоритмам, реализуемым в параллельном ПО. Постоянное увеличение количества процессоров в параллельных компьютерах приводит нас к выводу, что программы, рассчитанные на фиксированное число CPU, равно как и программы, предназначенные для выполнения на одном компьютере, нельзя считать приемлемыми. Следовательно, мы можем к списку требований добавить расширяемость – “эластичность” к увеличению числа процессоров, на которых выполняется программа. Если все параллельные вычислительные системы классифицировать по способу организации доступа к памяти, то можно выделить две группы: системы с общей памятью – каждый процессор (вычислительный узел) имеет непосредственный доступ к запоминающему устройству, и системы с распределенной памятью – каждый узел имеет отдельное ЗУ. Во 2-м случае обмены данными требуют достаточно высоких накладных расходов, и если для мультипроцессорных компьютеров доступ к данным другого процессора может потребовать в 10 – 1000 раз больше времени, чем к своим, то для сетевых распределенных систем порядок может быть намного выше. В связи с этим, к параллельным алгоритмам и программам предъявляется также требование локальности – оптимальное с точки зрения расходов на межпроцессорные коммуникации распределение данных.
Рассмотрим несколько моделей параллельного программирования. Простейшая модель опирается на два понятия: задача и канал. При этом параллельное вычисление состоит из одной или более задач, выполняющихся одновременно, их количество может меняться в процессе выполнения программы. Каждая задача включает в себя последовательную программу и локальную область памяти, что, фактически, является виртуальной машиной фон Неймана. В дополнение к этому, задача имеет набор входных и выходных портов, определяющих ее интерфейс с окружением. Кроме чтения и записи в локальную память, задача может: посылать сообщения в свои выходные порты, принимать сообщения через свои входные порты, создавать новые задачи (приостанавливаясь до их завершения), прекращать свое выполнение. Операция посылки сообщения асинхронная, т.е. она завершается сразу независимо от реакции принимающей стороны, операция приема – синхронная, т.е. она вызывает приостановку задачи, пока сообщение не станет доступным. Пары входных/выходных портов могут быть соединены очередями сообщений, которые называются каналами. Каналы могут создаваться и удаляться во время выполнения программы, ссылки на каналы (порты) можно включать в сообщения, так что соединения достаточно динамичны. Задачи могут быть отображены на физические процессоры различными способами (в частности, все задачи на одном процессоре) без изменения семантики программы.