Аннотация
В дипломной работе рассматриваютсязадачи, связанные с технологией автоматического распараллеливания программ.
В первой ее части обсуждаются этапыразвития компьютерной науки в области параллельных вычислений, существующиеархитектурные и теоретические решения.
Вторая часть содержит описаниепроекта разработки системы автоматического распараллеливания программ на языке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 раз больше времени, чем к своим, то для сетевыхраспределенных систем порядок может быть намного выше. В связи с этим, кпараллельным алгоритмам и программам предъявляется также требование локальности– оптимальное с точки зрения расходов на межпроцессорные коммуникациираспределение данных.
Рассмотрим несколько моделейпараллельного программирования. Простейшая модель опирается на два понятия:задача и канал. При этом параллельное вычисление состоит из одной или болеезадач, выполняющихся одновременно, их количество может меняться в процессевыполнения программы. Каждая задача включает в себя последовательную программуи локальную область памяти, что, фактически, является виртуальной машиной фонНеймана. В дополнение к этому, задача имеет набор входных и выходных портов,определяющих ее интерфейс с окружением. Кроме чтения и записи в локальнуюпамять, задача может: посылать сообщения в свои выходные порты, приниматьсообщения через свои входные порты, создавать новые задачи (приостанавливаясьдо их завершения), прекращать свое выполнение. Операция посылки сообщения асинхронная,т.е. она завершается сразу независимо от реакции принимающей стороны, операцияприема – синхронная, т.е. она вызывает приостановку задачи, пока сообщение нестанет доступным. Пары входных/выходных портов могут быть соединены очередямисообщений, которые называются каналами. Каналы могут создаваться и удаляться вовремя выполнения программы, ссылки на каналы (порты) можно включать всообщения, так что соединения достаточно динамичны. Задачи могут бытьотображены на физические процессоры различными способами (в частности, всезадачи на одном процессоре) без изменения семантики программы.
Модель Message Passing,вероятно, является сегодня наиболее распространенной. В этой модели программатакже создает набор задач, каждая из которых содержит локальные данные, иидентифицируется уникальным именем. Задачи могут передавать и приниматьсообщения для\от именованной задачи. Таким образом, рассматриваемая модельпредставляет собой лишь сокращенную версию модели задача/канал – отличие тольков механизме передачи данных. Однако на практике большинство message-passingсистем при старте программы создают фиксированное количество одинаковых задач ине позволяют создавать или уничтожать задачи во время выполнения. Т.е. этисистемы фактически реализуют модель SPMD — “одна-программа-много-данных”, вкоторой все задачи выполняют одну и ту же последовательную программу надразными данными.
В модели “Общая память” задачиразделяют общее адресное пространство, в котором они производят чтение и записьасинхронно. Для контроля доступа к разделяемой памяти используются различныемеханизмы, например, блокировки и семафоры. Преимущество этой модели с точкизрения программиста заключается в отсутствии понятия владельца данных, и, крометого, отсутствии необходимости обменов между задачей-производителем данных изадачей-потребителем.
Другая часто используемая модель, параллелелизмданных, называется так из-за использования параллелелизма, возникающего привыполнении некоторой операции над многими элементами некоторой структуры данных(например, массива). Поскольку каждая операция над каждым элементом данныхможет быть представлена как независимая задача, грануляция вычислений мала иконцепция локальности не возникает. Однако, компиляторы, реализующие этумодель, часто требуют от программиста информацию о распределении данных междупроцессорами. Такой компилятор может затем транслировать программу впредставление SPMD, автоматически создавая код для осуществления необходимыхобменов.
Рассмотренные модели параллельногопрограммирования предоставляют программисту возможность разработки ПО,удовлетворяющего требованиям к параллельным программам. Параллельные языки,созданные на базе традиционных (таких как Fortran, C), или являющиеся ихрасширением, в той или иной степени реализуют эти модели, оставляя, однако, запрограммистом проблему выбора параллельного алгоритма и решение задач,связанных с оптимизацией распределения данных, минимизацией расходов накоммуникационные обмены и многих других.Автоматическиесредства разработки параллельного ПО.
История эволюции средств разработкиПО показывает, что в ее процессе решается несколько задач:
n реализация новых языков программирования;
n переработка алгоритмов анализа исходного текстапрограммы с целью генерации наиболее оптимального исполняемого кода;
n максимальное упрощение процесса разработки ПО и др.
В последнее время необходимость воблегчении работы программиста стала, возможно, наиболее актуальной из-за резковозросшего спроса на программные продукты во всех областях деятельности: время,необходимое на создание работоспособной, максимально свободной от ошибокпрограммы, превратилось чуть ли не в самый значительный параметр. Перерождениетройки «редактор-компилятор-компоновщик» в среду разработки, последующая ее визуализация,и дальнейшее превращение в систему «быстрой разработки программ» позволилопрограммисту сосредоточиться на оптимизации алгоритма, избавив от рутинныхдействий по созданию исполняемого кода из исходного текста и даже от многихэтапов собственно программирования — примером может служить занимающая многовремени работа по созданию пользовательского интерфейса.
Разработка параллельного ПО — задачана порядок сложнее, поэтому от средств такой разработки требуется вся помощь,которую они могут предоставить. Программист должен работать в тесномсотрудничестве со своей средой, как получая от нее подсказки, так ипредоставляя ей необходимую информацию о структуре программы и обрабатываемыхданных в случае невозможности автоматического принятия решения. Одним изподходов к такой разработке может быть написание программы на привычномпоследовательном языке, с дальнейшей ее трансляцией в текст соответствующегорасширенного языка — уже параллельного. Такой метод, во-первых, позволяетосуществлять разработку машинно-независимого продукта — генерация исполняемогокода производится компилятором целевой архитектуры, а, во-вторых, предлагаетнеплохое решение проблемы существования большого количества уже написанныхпоследовательных программ. Подобные средства разработки носят название«исходный код — в исходный код трансляторы».
Алгоритм работы такой системы можетбыть следующим:
1) анализ исходнойпрограммы на последовательном языке с целью выяснения скрытого в нейпараллелелизма;
2) один или болеепробных запусков программы под средой (или в присутствии блока анализа временивыполнения) для получения более полной информации об ее структуре и оценкевремени последовательного выполнения;
3) выбороптимального с точки зрения системы варианта распараллеливания и оценка временипараллельного выполнения, основанная на параметрах некоторой целевойархитектуры, заданных пользователем;
4) выдачарезультатов – величина полученного ускорения и причины невозможностираспараллеливания некоторых участков с предоставлением пользователю возможностивмешаться в процесс и дать необходимые инструкции; этот этап продолжается, покане будет достигнут удовлетворяющий пользователя вариант или он не прекратитдальнейший анализ;
5) генерация текстана целевом параллельном языке и выдача подробного отчета о результатахраспараллеливания.
Разработка параллельного ПО являетсяочень трудоемкой задачей из-за сложности определения скрытого параллелелизма,возможности внесения некорректного, нарушающего семантику программы, ложногопараллелелизма, и из-за необходимости учитывать большое число факторов,влияющих на конечную производительность программы. Автоматические средстваразработки параллельных продуктов и распараллеливания готовых последовательныхпредоставляют возможность существенно облегчить этот процесс.Анализпоследовательной программы
Одной из первых задач, возлагаемых наавтоматический распараллеливатель программ, является анализ исходнойпоследовательной программы с целью сбора максимального количества необходимойдля распараллеливания информации об ее структуре. Данные, полученные на этомэтапе, в совокупности с результатами работы блока динамического анализаявляются основой дальнейшей деятельности системы.
Задача статического анализа исходнойпрограммы может быть условно разделена на два этапа:
1) трансляция текстапрограммы в некоторое внутреннее представление и построение структур,отражающих последовательность работы программы и используемые в ней данные;
2) поиск возможныхвариантов распараллеливания с выбором оптимального и определение «узких»участков, препятствующих распараллеливанию.
Рассмотрим несколько более подробно1-й этап, поскольку решение связанных с ним задач является темой даннойдипломной работы. Внутреннее представление программы необходимо для возможностиее анализа независимо от исходного последовательного языка, т.е. оно являетсяточным переложением текста программы, записанным в терминах, понятных системе.Кроме того, оно должно быть достаточным для последующей генерации текста параллельнойпрограммы на целевом языке. После создания такого представления, необходимоподняться на такой уровень абстракции, который позволит исследовать алгоритмпрограммы с требуемой точки зрения. Иными словами, надо построить структурыданных, содержащих всю программу в приемлемом для последующего анализа виде,расширенные для возможности хранения и обработки результатов работы другихблоков распараллеливателя.
1.Система автоматического распараллеливания
Данная дипломная работа являетсячастью проекта разработки системы автоматического распараллеливания программ наязыке Fortran77. Система состоит из нескольких функциональных блоков, каждый изкоторых реализует один или более этапов построения параллельной программы,сохраняющей семантику заданной последовательной программы. Фиксированныйинтерфейс обмена данными между ними позволяет производить независимуюмодификацию каждого блока. Таким образом, система может развиваться в сторонудальнейшего увеличения ее интеллектуальности в принятии решений о возможностираспараллеливания входной программы и поиска наиболее эффективных вариантов еепреобразования.1.1 Назначение системы
Представляемая система предназначенадля распараллеливания программ, написанных на языке Fortran77. Использованиеэтого языка как основного при разработке научных и инженерных приложений напротяжении многих лет привело к образованию большого числа программ,необходимость в которых сохраняется и сегодня. Автоматическая трансляциянакопившегося последовательного кода в параллельный позволит использовать новыеархитектурные возможности при существенно меньших по сравнению с повторнойреализацией затратах. Формируемый системой отчет о принятых в процессераспараллеливания решениях может служить основой рекомендаций по модификацииисходного кода с целью достичь наиболее эффективного результата.
Второй аспект применения – разработкапараллельного ПО на основе Fortran77. Достоинство такого подхода заключается виспользовании привычного языка программирования и передаче системераспараллеливания обязанностей по оценке эффективности реализации алгоритмов сточки зрения параллельного выполнения.1.2 Схема работысистемы автоматического распараллеливания
/>
На вход системы автоматическогораспараллеливания (САР) подается текстовый файл с программой на Fortran77. Онадолжна, во-первых, быть правильной с точки зрения языка, и, во-вторых,удовлетворять накладываемым системой ограничениям.
Первый шаг – разбор текста средствамибиблиотеки Sage++, в результате которого образуется файл с внутреннимпредставлением исходной программы.
Задача блока INLINE-подстановкипроцедур САР заключается в модификации структуры исходной программы с цельюпривести ее к виду, облегчающему дальнейший анализ и повышающему его точность.В результате его работы образуется файл с внутренним представлением программы,состоящей только из главного модуля, в котором все вызовы подпрограмм замененыих телами. Если исходная программа не содержит процедур, пользователь может неиспользовать этот блок.
Внутреннее представление без вызововпроцедур поступает на вход двух блоков. Первый – блок статического анализа. Егозадачей является статическое построение расширенного графа потока управленияпрограммы и некоторых вспомогательных структур данных.
Блок подготовки программы длядинамического анализа также получает внутреннее представление. Его назначение –создание версии программы для последующей обработки блоком динамическогоанализа.
Задача блока динамического анализа –дополнение графа управления данными, полученными при выполнении программы в егоприсутствии. Кроме того, на этом шаге некоторые результаты статического анализамогут быть скорректированы.
Следующий этап – поиск оптимальногораспределения вычислений и данных между узлами вычислительной сети. Анализпроизводится на основе информации о возможности распараллеливания тех или иныхучастков программы, полученной на предыдущих шагах.
Задача учета затрат на доступ кудаленным данным, на перераспределение данных в процессе выполнения программы ит.п. решается осуществлением запросов к блоку оценки времен коммуникаций.
Следующий блок производит модификациювнутреннего представления с целью реализовать выбранный вариантраспараллеливания.
Задача блока клонирования процедурзаключается в выделении во внутреннем представлении переработанной программыпроцедур, их оформлении и вставки соответствующих операторов вызова.Пользователь может не использовать функции этого блока, если считает этоцелесообразным.
Далее на основе результирующеговнутреннего представления происходит генерация текста программы на FortranDVM.1.3 Постановка задачидипломной работы
Задачей дипломной работы являетсяреализация следующих функций блоков САР:
— Статическое построение расширенногографа потока управления программы и сопровождающих его структур (блок №2);
— Экспорт данных в файлы для блокараспределения вычислений и данных (блок №2);
— Чтение из файлов директив FortranDVM,сформированных блоком распределения, и соответствующая им модификациявнутреннего представления программы (блок №7).
2.Создание внутреннего представления программы
Для программ, назначение которыхзаключается в анализе и обработке других программ, основным параметром являетсятекст исходной программы. В отличие от параметров простых типов, такой сложноорганизованный параметр требует предварительного анализа с целью обеспечитьвозможность получения из него необходимой для решаемой задачи информации. Ипоскольку для большинства приложений такого рода доступа к входной программе науровне символов в текстовом файле недостаточно, возникает задача переводатекста программы в некоторую структуру, отражающую его в виде законченныхязыковых конструкций – идентификаторов, типов, структур данных, операторов,управляющих конструкций и др. Иными словами, необходимо произвести разборисходного текста – parsing. Однако в некоторых случаях этого недостаточнои для решения поставленных задач требуется подняться на более высокий уровеньабстракции. Следовательно, встает вопрос о создании некоего высокоуровнегопредставления программы, отражающего специфику конкретной задачи.2.1 Разбор исходноготекста. Система Sage++
Первоочередной задачей на этапесоздания внутреннего представления программы, написанной на некотором языке,является разбор исходного текста. В результате такого анализа должна бытьдоступна информация о порядке выполнения операторов программы с учетомиспользованных в ней языковых конструкций, нарушающих последовательный характерих выполнения – ветвления, безусловные переходы, циклы, обращения кподпрограммам, операторы прекращения выполнения программы и т.п. Несмотря нато, что для строго типизированных языков программирования анализ операторовобъявления может дать полную информацию о константах, переменных и их типах,представляется существенным дополнением наличие таблиц типов и имен. Всеперечисленные возможности предоставляет свободно распространяемая библиотекаSage++, разработанная в Иллинойском университете..
“Sage++ является попыткой предложитьобъектно-ориентированный инструментарий для построения систем обработкипрограмм на языках Fortran77, Fortran90, C и C++. Sage++ предназначен дляразработчиков, проводящих исследования в следующих областях: построениераспараллеливающих компиляторов, средств анализа производительности иоптимизаторов исходного кода” [2].
Библиотека Sage++ реализована в видеиерархии классов C++, которые позволяют получить доступ к дереву разбора,таблице имен и таблице символов для каждого файла, входящего в исходноеприложение. Классы объединены в пять семейств: “Проекты и файлы” – хранятинформацию обо всех файлах приложения, “Операторы” – ссылаются на базовыеоператоры языков, “Выражения” – указывают на выражения, содержащиеся внутриоператоров, “Символы” – определенные в программе идентификаторы, “Типы” –сопоставленные с каждым идентификатором и выражением типы. Библиотека обеспечиваетсредства как всестороннего изучения исходной программы, так и различной еемодификации – добавление к ней новых файлов, создание и изменение операторов,входящих в файлы, вставка и модификация содержащихся в операторах выражений идр. Рассмотрим основные возможности Sage++, представляющие для нас интерес врамках первого аспекта.
Перед началом анализа программынеобходимо создать и сохранить на диске Sage++-представления каждого входящегов ее состав файла специальной утилитой из пакета Sage++. После этого надосоздать текстовый файл проекта со списком имен полученных файлов.
Для получения доступа к даннымпроекта существует класс SgProject:
SgProject(char*proj_file_name) — конструктор, proj_file_name — имя файла проекта;
int numberOfFiles() –количество файлов в проекте;
SgFile &file(int i) –i-й файл проекта.
Класс SgFile представляетфайл, входящий в исходное приложение:
SgStatement *firstStatement() –указатель на первый оператор файла;
SgSymbol *firstSymbol() –указатель на первый элемент таблицы имен файла;
SgType *firstType() — указатель на первый элемент таблицы типов файла.
Каждый определенный в файлеидентификатор содержится в таблице имен и представляется объектом одного изнаследников класса SgSymbol:
int variant() –тэг, определяющий класс символа;
int id() — уникальный номер символа в таблице ;
char *identifier() — текстовое представление символа
SgType *type() — тип символа;
SgStatement *declaredInStmt() - оператор объявления;
SgSymbol *next() — указатель на следующий элемент таблицы.
После выяснения тэга подлежащегоанализу идентификатора можно при помощи соответствующей ему глобальной функцииполучить указатель на объект класса-наследника SgSymbol, содержащегоспецифические для этого идентификатора данные. Примерами таких производныхклассов могут служить:
SgVariableSymb – переменнаяпрограммы;
SgConstantSymb — константа;
SgFunctionSymb — процедура, функцияили главная программа.
С каждым идентификатором и выражениемсоотнесен его тип – скалярный или сложный, представленный объектом класса SgTypeили одного из его наследников:
int variant() — тэг типа,соответствующий либо скалярному типу, либо классу-наследнику;
int id() — уникальный номер типа в таблице типов;
SgType *baseType() — указательна базовый тип для сложных типов;
SgType *next() – указатель наследующий элемент таблицы типов.
Пример производного от SgType класса– SgArrayType, объект которого создается для каждого определенного в программемассива. Основные члены этого класса:
int dimension() — размерность массива;
SgExpression *sizeInDim(int i) — выражение, характеризующее длину по i-му измерению.
Каждый файл программы разбит наоператоры, для представления которых используется класс SgStatement иего производные:
int variant() — тэг оператора;
int id() — уникальный номер оператора;
int lineNumber() — номерстроки в исходном тексте;
SgExpression *expr(int i) — i-е выражение, входящее в оператор (i = 0,1,2);
SgStatement *lexNext() — следующий влексическом порядке оператор;
SgStatement *lexPrev() — предыдущийв лексическом порядке оператор;
SgStatement *controlParent() — охватывающий управляющий оператор;
SgStatement *lastNodeOfStmt() – дляоператоров, не являющихся листом дерева разбора, возвращает указатель напоследний оператор поддерева.
Аналогично другим классам Sage++ тэгобъекта SgStatement позволяет определить класс-потомок SgStatement,соответствующий рассматриваемому оператору. В каждом из них существуют данные иметоды, специфические для представляемого этим классом оператора. Эти классы объединеныв несколько семейств:
· заголовочныеоператоры;
· операторыобъявления;
· управляющиеоператоры;
· исполняемые идругие операторы.
Примеры классов, относящихся к этимсемействам.
Заголовочные:
— SgProgHedrStmt – заголовок программы(Fortran);
— SgProcHedrStmt – заголовокподпрограммы (Fortran);
— SgBlockDataStmt – оператор блокаданных (Fortran).
Операторы объявления:
— SgVarDeclStmt – оператор объявленияпеременной;
— SgParameterStmt – оператор объявленияконстант (Fortran);
— SgImplicitStmt – оператор Implicit(Fortran).
Управляющие:
— SgForStmt – цикл FOR;
— SgIfStmt — оператор ветвления If-Then-Else (Fortran), if (C);
— SgLogIfStmt — операторлогического If (Fortran);
— SgArithIfStmt — операторарифметического If (Fortran).
Исполняемые и другие:
— SgAssignStmt — оператор присваивания (Fortran);
— SgCallStmt — оператор Call(Fortran);
— SgContinueStmt — операторContinue;
— SgControlEndStmt — обозначаетконец одного из основных блоков (напр. ENDIF);
— SgReturnStmt — операторReturn;
— SgGotoStmt — оператор Goto.
Большинство операторов программысодержат некоторые выражения. Класс SgExpression является базовым длявыражений всех видов:
int variant() — тэг вида выражения;
SgExpression *lhs() — левое поддерево выражения;
SgExpression *rhs() — правое поддерево выражения;
В отличие от иерархии классов,порождаемой SgStatement, не вводится подкласс для каждой операции, находящейсяв корне дерева разбора выражения. Основные бинарные операции, такие, какстандартные арифметические, идентифицируются только тэгом. Листья дерева могутиметь собственные классы, например:
— SgValueExp — представляет значение одного из базовых типов;
— SgVarRefExp — ссылкана переменную или на массив;
— SgArrayRefExp — ссылка наэлемент массива;
— SgFunctionCallExp — вызовфункции.
Разработчиками Sage++ предлагаетсяследующий алгоритм разбора исходной программы. Производится последовательныйперебор файлов, входящих в проект. Начиная с указателя SgStatement* SgFile::firstStatement() осуществляется обход операторов текущего файла. При этоманализируется оператор, входящие в него выражения, тело(а) – для операторов,содержащих таковое (например, управляющей группы). Переход на следующийоператор реализуется кодом cur_stmt=cur_stmt->lastNodeOfStmt()->lexNext()для операторов, не являющихся листом дерева разбора, иcur_stmt=cur_stmt->lexNext() для остальных (где cur_stmt – указатель натекущий оператор). Использование рекурсивного подхода к просмотру деревапредставляется достаточно естественным.2.2 Внутреннеепредставление программы высокого уровня
Представление подлежащей обработкепрограммы в виде, предлагаемом Sage++, или подобном ему дает разработчикуширочайшие возможности для извлечения всей необходимой ему информации опрограмме. Следующим этапом проектирования системы обработки программ являетсяопределение набора знаний об исходной программе, специфического для решаемойзадачи. При этом возникают две стороны переработки внутреннего представленияпрограммы: получение на его основе новых данных, и объединение излишнеподробной информации в более крупные блоки. Иными словами, нужно подняться наболее высокий уровень абстракции и разработать соответствующее емупредставление программы. Рассмотрим интересующую нас предметную область –автоматическое распараллеливание программ и определим требования кпредставлению программы, продиктованные особенностями этой области.
Распределение вычислений и данныхявляется одним из основных шагов в процессе создания параллельного приложения.Существует два подхода к решению этой проблемы: доменная декомпозиция, прикоторой основное внимание уделяется распределению относящихся к задаче данных,и функциональная декомпозиция – сначала распределяются вычисления, а затемотносящиеся к ним данные. Поскольку в нашем проекте системы автоматическогораспараллеливания выбрана вторая методика, вид внутреннего представленияопределяется, в первую очередь, удобным для анализа способом хранениявычислений.
Носителями вычислений программыявляются входящие в ее состав операторы. Однако, с точки зренияраспараллеливания интересны не столько конкретные операторы, сколько участкипрограммы, состоящие из последовательно выполняющихся операторов, целикомподлежащие какому-то из видов исполнения — параллельному или последовательному,а также порядок следования этих участков. Объединяя группу операторов в одинэлемент высокоуровнего представления программы, следует агрегировать в немнекоторую информацию, относящуюся к этим операторам. В нашем случае такой информациейявляется:
— Количество вычислительных операций вблоке – арифметические операции и стандартные функции. Эти данные требуются дляоценки времени выполнения блока.
— Наличие операторов некоторых типов.Например, присутствие в блоке операторов ввода\вывода препятствует егопараллельному выполнению.
— Список обращений к переменным имассивам с разделением по типу обращения – чтение или модификация. Этот списокнужен при поиске в блоке зависимостей по данным, а также для корректногораспределения данных между элементами вычислительной сети.
— Список переменных специального вида иих характеристики. Примером могут служить редукционные переменные.
Линейная последовательностьвыполнения описанных блоков операторов может быть нарушена одной из следующихконструкций: цикл, ветвление, безусловный переход. Для них должны существоватьэлементы специальных типов, отражающих их особенности. В этих элементахнеобходимо предусмотреть возможность хранения относящихся к ним данным. Дляцикла это может быть, в частности, количество итераций, для ветвления –вероятность перехода по каждой из веток и др. 2.3 Расширенный граф управления. Вспомогательные структуры
Классической структурой для описанияпоследовательности выполнения операторов программы является граф потокауправления. Разработанное в данной дипломной работе представление программывыполняет те же функции, только в качестве его элементов используются блокиболее высокого уровня. Такое представление – назовем его расширенным графомпотока управления программы — в совокупности с некоторыми вспомогательнымиструктурами содержит в себе всю информацию, необходимую для следующих в циклеработы блоков системы распараллеливания.
В процессе обработки исходнойпрограммы реализованным в дипломной работе блоком автоматическогораспараллеливателя производится построение следующих структур, образующихвместе высокоуровневое представление программы:
— расширенный граф управления;
— список циклов программы;
— таблица символов программы.
Рассмотрим устройство основнойструктуры – графа управления. Граф состоит из блоков, соответствующихлогическим элементам представления, и дуг, отражающих отношение между ними.
Типы блоков:
— Линейный участок. Объединяет в себенепрерывную группу операторов, выполняющихся последовательно один за другим.
— Цикл. Представляет циклы программы.
— Ветвление. Соответствует условнымоператорам программы.
— Слияние. Это блок, в котором сходятсяветви развилки. Строгое соответствие блоков ветвления и слияния обеспечиваетвозможность изучения находящихся между ними элементов как единого целого.
Отношение между двумя блоками можетдвух типов:
1) второй блоквыполняется сразу после первого;
2) второй блоксодержится внутри первого — такой тип отношения может быть только междублоком-циклом и первым блоком из его тела.
Для облегчения дальнейшего описанияструктуры графа и его визуального представления, введем следующие названия длятипов отношений между блоками:
- если второй блокследует за первым, будем говорить, что он “находится справа” от первого,соответственно первый блок “находится слева” от второго;
- если второй блоксодержится внутри первого, будем говорить, что он “находится снизу” от первого,при этом первый “находится сверху” от второго.
Дуги, представляющие описанныеотношения, будем называть ссылками вправо, влево, вниз, вверх.
Блок ветвления требует наличие двухвправо – по числу возможных ветвей. Соответственно, блок слияния всегда имеетдве входящие слева ссылки. Для осуществления всевозможных вариантов обходаграфа требуются также использования обратных дуг – вверх и\или влево.
Таким образом, у каждого блока можетбыть до шести исходящих из него дуг, имеющих номер, классифицирующийпредставляемое ею отношение:
1) – 1-я ссылкавправо
2) – 2-я ссылка вправо
3) – ссылка вниз
4) – ссылка вверх
5) – 1-я ссылкавлево
6) – 2-я ссылкавлево
Каждый элемент графа помимо ссылок насоседей содержит общую для всех типов информацию:
— уникальный номер;
— тип блока;
— уровень, характеризующий глубинувложенности;
— флаг возможности параллельногоисполнения;
— количество каждой из возможныхвычислительных операций;
— ссылки на 1-й и последний операторыблока.
Специфические данные:
для циклов — уникальный номер цикла;
для ветвлений – вероятность переходапо каждой из ветвей.
Количество операций определяетсяследующим образом:
1) линейный блок — общее их количество во всех входящих в него операторов;
2) блок цикла — сумма операций во всех входящих в его тело блоков;
3) блок ветвления –сумма слагаемых вида: число операций в i-й ветви * вероятность перехода по ней;
4) блок слияния неимеет операций;
5) если блок циклавходит в состав некоторого вышестоящего, то его слагаемое образуется какпроизведение числа операций в нем и количества итераций.
Приведем схему фрагмента некоторойпрограммы и соответствующий ей граф.
ЛИН1
DO 1 … (1)
ЛИН2
DO 1 … (2)
IF … THEN
ЛИН3
ELSE
ЛИН4
ENDIF
1 CONTINUE
DO 2 … (3)
ЛИН5
2 CONTINUE
/>
Основными элементами программы,подлежащими изучению на предмет возможности распараллеливания, являются циклы.Такой подход представляется достаточно естественным, поскольку во многихприложениях основная вычислительная нагрузка находится именно в циклах.Примерами могут служить реализации всевозможных численных методов. Очевиднаянецелесообразность размещения всей специфической для циклов информации в узлахграфа, а также существование этапов изучения циклов программы без учета ихрасположения в графе повлекли за собой разработку дополнительной структурыданных – списка циклов. Он представляет собой двунаправленный линейный список,в котором каждому циклу соответствует уникальный элемент, содержащий следующиеданные:
— Уникальный номер цикла. Служит для связис расширенным графом.
— Уровень вложенности – соответствуетаналогичному полю из графа.
— Ссылка на идентификатор счетчикацикла.
— Начальное, конечное выражениясчетчика, шаг цикла.
— Количество итераций (витков) цикла.
— Списки переменных и элементовмассивов, используемых на чтение и на модификацию.
— Список редукционных переменных.
— Ссылки на оператор заголовка цикла ина оператор его завершения.
Все используемые в графе и спискециклов идентификаторы переменных и массивов объединяются в таблицу имен –третью составляющую нашего представления программы. Для каждого идентификаторахранится следующая информация:
— Тэг вида идентификатора – переменнаяили массив.
— Тип идентификатора.
— Строка имени.
— Размерность и длина по каждомуизмерению – для массива.
— Ссылка на соответствующий элементтаблицы имен низкоуровнего представления.
Описанные структуры образуютпредставление исходной последовательной программы достаточно высокого уровняабстракции, соответствующего проблематике рассматриваемой нами предметнойобласти. Оно позволяет хранить всю необходимую для распределения вычислений иданных информацию о программе, сокращая при этом количество функциональныхблоков до минимума.
3.Построение расширенного графа управления
Выполнение задач дипломной работыосуществлялось на языке C++ с использованием библиотеки Sage++ 2.0. В данномпункте приведены описания классов, составляющих программный код дипломнойработы, использованные в их наиболее существенных методах алгоритмы, а такжеусловия, которым должна удовлетворять входная программа для успешной ееобработки системой в целом, и реализованным в дипломной работе блоком вчастности. 3.1 Ограничения на входную программу
Первое требование к входной программезаключается в ее корректности с точки зрения синтаксиса и семантики Fortran77.Заключенные в ней ошибки, не определенные на этапе разбора текста средствамиSage++, могут привести к непредсказуемым результатам.
Общим для всей системы ограничениемявляется также ее достаточно высокая чувствительность к плохойструктурированности программы, а именно:
— в программе не должны присутствоватьоператоры прекращения выполнения;
— запрещены операторы перехода, заисключением выхода из тела цикла на первый за концом цикла оператор по условию.
Другим существенным требованиемявляется запрет на использование COMMON-областей.
Ограничения, накладываемые в даннойдипломной работе:
— выражения в заголовках циклов(начальное, конечное, шаг) могут быть только линейными относительно некоторойпеременной, т.е. иметь вид C1*V+C0, где C1 и C0 – константы, V — переменная;
— индексные выражения в обращениях кмассивам должны удовлетворять тому же условию;
— отсутствие аппарата поисказависимостей по данным влечет необходимость вставки пользователем комментария“DEPENDENCE” в теле цикла, содержащего зависимость.3.2 Описание классов
В рамках дипломной работы реализованодва набора классов:
1. Классы,выполняющие построение внутреннего представления, экспорт данных для блокараспределения вычислений и данных, последующий импорт результатов работы этогоблока и генерацию текста на FortranDVM.
2. Классы,используемые в блоке распределения вычислений и данных. Выполняют импортвнутреннего представления и воссоздают его структуру, а также производятэкспорт результатов работы этого блока.
Рассмотрим назначение классов 1-гонабора и их наиболее важные члены.
1) Класс cSourceProgramSg –представляет исходную последовательную программу. Обработка входной программыдолжна начинаться с создания объекта этого класса.
cSourceProgramSg (char *projfile) – конструкторкласса, projfile – имя файла проекта Sage++; в этом конструкторе происходитоткрытие проекта, разбор входящего в него файла исходной программы, созданиенезаполненных графа, списка циклов и таблицы символов.
SgStatement *FirstSt() – 1-й оператор программы.
SgStatement *LastSt() — последний оператор программы.
cProgramGraphSg *PrgGraph() – граф программы.
cLoopListSg *LpList() – список циклов.
cSymbolTabSg *SymTab() – таблица символов.
void PrepareConsts ()– замена в теле программы обращений к константам на их значения.
void PrepareLoops ()– конвертация циклов программы к виду DO-ENDDO.
void BuildLoopList() – построение списка циклов.
void BuildProgGraph() – построение графа программы.
void PrintLoopList(ostream&) – вывод в поток списка циклов для просмотра.
void PrintProgGraph(ostream&) – вывод графа.
void PrintSymbolTab(ostream&) – вывод таблицыимен.
void ExportData(char*) – экспорт данных в файлы.
void ImportData(char*) – импорт данных из файлов;
void Unparse (char*)– генерация результирующего текста в файле, имя которого определяетсяпараметром метода.
При экспорте данных в файлыобразуются следующие файлы:
filename.gr – узлы графа;
filename.gri – индексный файл;
filename.lp – список циклов;
filename.st – таблица символов, гдеfilename – параметр метода ExportData(char*).
2) Класс cProgramGraphSg –представляет расширенный граф программы.
cProgramGraphSg (cSymbolTabSg*, cLoopListSg*) –конструктор класса, создает пустой граф управления. Параметры – таблицасимволов и список циклов, на которые будет ссылаться граф.
cLoopListSg *LpList() – список циклов, используемый графом.
cSymbolTabSg *SymTab() – таблица имен, используемая графом.
cProgramGraphNodeSg *CurNode() – текущий узел.
int IsStart() – является ли текущий узел начальным.
int GoStart(), GoDown (), GoUp (), GoLeft1 (), GoLeft2(),
GoRight1 (), GoRight2 (), GoId(long int) – переместить указатель на текущий узел соответственно на 1-й узел,вниз, вверх, влево по 1-й ссылке, влево по 2-й ссылке, вправо по 1-й ссылке,вправо по 2-й ссылке, на узел с заданным номером. Возвращает 1 при удачномпереходе, 0 в противном случае..
void CountOpers () –подсчет числа операций для каждого узла графа.
void ExportData(ofstream&, ofstream&) – экспорт графа и индексной информации в потоки.
void ImportData(ifstream&) – импорт данных от блока распределения вычислений, подлежащихвставке в граф;
void Build(SgStatement*, SgStatement*, int, int) – построение графа.
void Unparse () –произвести вставку добавленных в граф данных во внутреннее представлениеSage++;
3) Класс cProgramGraphNodeSg –представляет узел графа управления.
cProgramGraphNodeSg () – конструктор класса, создаетновый узел.
SgStatement *poSt1,*poSt2, *poSt3 – принимают значения послепостроения графа.
Для линейного участка: poSt1 – 1-йоператор блока, poSt2 – последний оператор.
Для цикла: poSt1 – оператор заголовкацикла, poSt2 – оператор, завершающий цикл (ENDDO)
Для ветвления: poSt1 – IF, poSt2 – ELSE, poSt3 – ENDIF.
int Level– уровень вложенности, внешнему уровню соответствует 0.
int IsParal– признак возможности распараллеливания.
long int LoopId –для элементов типа “цикл” содержит номер соответствующего цикла из списка.
float Ver1, Ver2– для элементов типа “ветвление” вероятность перехода соответственно по 1-й и2-й ветви.
float Opers[df_OPERS_COUNT]– массив, в каждом элементе которого содержится количество соответствующих индексуэлемента операций в блоке. Например, Opers[0] — число сложений, Opers[1] –вычитаний.
long int Id() – уникальный номер узла.
int NodeType() – тэг типа узла.
long int ExportData(ofstream&) – экспорт узла в файловый поток, возвращает количество записанныхбайт.
void ImportData(ifstream&) – импорт данных из файлового потока.
void Unparse () –произвести вставку добавленных в узел данных во внутреннее представлениеSage++.
4) Класс cLoopListSg –представляет список циклов программы.
cLoopListSg (cSymbolTabSg*) – конструкторкласса, создает пустой список циклов, параметр – таблица символов, на которуюбудет ссылаться список.
cSymbolTabSg *SymTab() – таблица символов, используемая списком.
cLoopListNodeSg *CurNode() – указатель на текущий элемент списка.
int GoStart (), GoEnd(), GoRight (), GoLeft (), GoId (longint) – переместить указатель на текущий узел соответственно на 1-й узел,последний узел, влево, вправо, на узел с заданным номером. Возвращает 1 приудачном переходе, 0 в противном случае.
void Analyse () –произвести необходимый анализ элементов списка.
void Build(SgStatement*, SgStatement*, int) – построить список.
void ExportData(ofstream&) – экспорт списка в файловый поток.
5) Класс cLoopListNodeSg –представляет элемент списка циклов.
cLoopListNodeSg () – конструктор класса, создаетновый элемент.
long int Id() – номер элемента.
SgStatement *poSt1,*poSt2 – ссылки соответственно на оператор заголовка цикла и наоператор завершения цикла.
cSymbolSg *poCounterSym– ссылка на переменную-счетчик цикла.
cExpressionSg *poStartExpr,*poEndExpr, *poStepExpr – начальное, конечноевыражения счетчика и выражение шага цикла.
long int IterNum– количество итераций цикла.
int Level –уровень вложенности.
int IoOp, GotoOp– флаги наличия в теле цикла операторов ввода\вывода и операторов перехода затело цикла.
cVarListElemSg *LVar[df_MAX_LRVAR_COUNT],*RVar[df_MAX_LRVAR_COUNT] – списки обращений к переменным иэлементам массивов на модификацию и на чтение соответственно.
sReduct RedVar[df_MAX_REDVAR_COUNT]– список редукционных переменных, содержащихся в теле цикла.
void AnalyseHead(cSymbolTabSg *) – произвести анализ заголовка цикла.
void AnalyseBodyVars(cSymbolTabSg*) – произвести анализ обращений к переменным и элементам массивовв теле цикла.
void AnalyseRedVars(cSymbolTabSg*) – произвести поиск редукционных переменных в теле цикла.
void AnalyseIoOp () –определить присутствие в теле цикла операций ввода\вывода.
void AnalyseGotoOp ()– определить присутствие в теле цикла операторов перехода за тело цикла.
long int ExportData(ofstream&) – экспорт элемента в файловый поток, возвращает количествозаписанных байт.
6) Класс cSymbolTabSg –представляет таблицу символов. Реализована в виде двунаправленного спискаэлементов класса cSymbolSg.
cSymbolTabSg () – конструктор класса, создаетпустую таблицу.
cSymbolSg *FirstSym ()– указатель на 1-й элемент списка.
void ExportData(ofstream&) – экспорт таблицы в файловый поток.
7 ) Класс cSymbolSg –представляет элемент таблицы символов.
cSymbolSg () – конструктор класса, создаетновый элемент.
long int Id () –уникальный номер элемента.
SgSymbol *poSgSym –ссылка на соответствующий элемент таблицы символов Sage++.
int Variant () –тэг вида элемента: переменная или массив.
int Type – кодтипа.
char *Name – строкаимени.
int Dim () –размерность (для массива).
int DimLen (int i)– длина по i-му измерению (для массива).
cSymbolSg *LinkRight() – следующий в списке элемент.
cSymbolSg *LinkLeft ()– предыдущий в списке элемент.
long int ExportData(ofstream&) – экспорт элемента в файловый поток.
int operator ==(cSymbolSg&), operator != (cSymbolSg&)
8) Класс cExpressionSg –представляет выражение. Текущая реализация класса позволяет хранить тольковыражения вида c1*V+c0, где c1,c0 – константы, V – переменная.
cExpressionSg (SgExpression*, cSymbolTabSg*) –конструктор класса, параметрами являются подлежащее разбору выражение,представленное объектом Sage++, и таблица символов, которая будет дополненавходящим в состав выражения идентификатором.
int Variant () –тэг вида выражения.
cSymbolSg *poVariable– ссылка на переменную выражения.
int IntC0 (), IntC1() – значения констант, приведенные к типу int.
float RealC0(), RealC1 () – аналогично, float.
double DoubleC0(), DoubleC1 () – аналогично, double.
long int ExportData(ofstream&) – экспорт выражения в файловый поток.
int operator ==(cExpressionSg&), operator != (cExpressionSg&)
9) Класс cArrayRefSg –представляет ссылку на элемент массива.
cArrayRefSg (SgArrayRefExp*, cSymbolTabSg*) –конструктор класса, параметрами являются подлежащая разбору ссылка на элементмассива, представленная объектом Sage++, и таблица символов, в которую будутдобавлены входящие в ссылку переменные и имя массива.
SgArrayRefExp *poSgArrRef– исходный объект Sage++.
cSymbolSg *poSym –идентификатор массива.
int SubscrNum –количество индексных выражений в ссылке.
cExpressionSg* SubscrList[df_MAX_DIM] – массив индексных выражений.
long int ExportData(ofstream&) – экспорт в файловый поток.
int operator ==(cArrayRefSg&)
int operator !=(cArrayRefSg&)
10) Класс cVarListElemSg –представляет элемент списка обращений к переменным и массивам.
cVarListElemSg (SgVarRefExp*, cSymbolTabSg*), cVarListElemSg(SgArrayRefExp*, cSymbolTabSg*) – конструкторы класса, 1-й для разбораобращения к переменной, параметрами являются ссылка на переменную,представленная объектом Sage++, и таблица символов, в которую будут добавленыидентификаторы; 2-й для разбора ссылки на массив, параметры имеют тот же смысл.
int Variant () –тэг вида элемента (ссылка на переменную или на массив).
cSymbolSg *poSym –идентификатор переменной для ссылки 1-го вида.
cArrayRefSg *poArr– ссылка на массив для 2-го вида.
long int ExportData(ofstream&) – экспорт в файловый поток.
int operator ==(cVarListElemSg&)
int operator !=(cVarListElemSg&).
Для каждого из описанных классовсуществует его аналог во втором наборе, имеющий такое же имя за исключениемпостфикса “Sg”. В классах-аналогах отсутствуют методы для построения структур иконструкторы разбора. Корректная инициализация объектов этих классовпроизводится только за счет введенных методов импорта из файлового потока. Вклассе cProgramGraphNode добавлены члены-данные для хранения директивFortranDVM, формирование которых осуществляет блок распределения вычислений иданных, и методы для их вставки, а также реализован экспорт этих комментариев вфайл.3.3 Алгоритмы
Реализованные в дипломной работеклассы блока статического построения расширенного графа управления программы ивспомогательных структур данных содержат большое число членов-методов, решающихзадачи разной сложности. Остановимся на деталях реализации некоторых из них.
На самом внешнем уровне программыпостроения и экспорта всех структур находится функция main(). Ееосновное содержание заключается в следующих строках:
cSourceProgramSgTestProg(projfile);
TestProg.PrepareAll();
TestProg.BuildAll();
TestProg.PrintAll(cout);
TestProg.ExportData(trgfile);
В первую очередь создается объекткласса cSourceProgramSg, параметром конструктора которого является имяфайла-проекта Sage++. Далее вызываются методы этого класса:
PrepareAll() – предварительнаяобработка Sage++ представления исходного приложения;
BuildAll() – построение всехструктур;
PrintAll(cout) – вывод в поток coutпостроенных структур для просмотра;
ExportData(trgfile) – экспорт данныхв файлы.
void cSourceProgramSg::PrepareAll()
Вызывает методы того же класса:
PrepareConsts(); — подготовкаконстант.
PrepareLoops(); — подготовка циклов.
voidcSourceProgramSg::PrepareConsts()
Осуществляет замену обращений кконстантам их значениями. Алгоритм:
- Просмотр таблицыимен Sage++ и составление списка объявленных констант и их значений.
- Обход всехоператоров программы и поиск во входящих в них выражениях использования каждойиз констант.
- При положительномрезультате поиска, производится рекурсивный обход дерева разбора выражения сзаходом только в те ветки, в которых используются константы. Вместо листа,соответствующего константе, строится новое выражение – значение константы, ионо возвращается на предыдущий уровень рекурсии, для остальных листьеввозвращается исходное выражение. Вернувшись из рекурсивного вызова, заменяемвсю ветку возвращенной. После этого текущее поддерево анализируется навозможность его вычисления. Если удается – вместо этого поддерева возвращаетсявычисленное значение.
При таком алгоритме, например,выражение 2*N+M+t, где N=100, M=5, будет заменено выражением 205+t.
void cSourceProgramSg::PrepareLoops().
Приводит все циклы программы к видуDO-ENDDO. Просматривает операторы программы. Для найденных циклов применяетметод Sage++, выполняющий такое преобразование.
voidcSourceProgram::BuildAll().
BuildLoopList(); — построение спискациклов.
BuildProgGraph(); — построение графа.
voidcSourceProgram::BuildLoopList().
LpList()->Build(FirstSt(),LastSt(), 0); — построение спискациклов.
LpList()->Analyse(); — анализпостроенного списка.
voidcLoopListSg::Build(SgStatement *first_line, SgStatement *last_line, intcur_lev).
Этот метод производитпоследовательный просмотр операторов в промежутке от first_line до last_lineвключительно с обеих сторон. При обнаружении оператора-заголовка цикла,осуществляется добавление к списку циклов нового элемента, в качестве егоуровня вложенности принимается значение cur_lev. Затем метод вызывает себя соследующими параметрами: следующий оператор после обнаруженного заголовка цикла– first_line, оператор завершения найденного цикла – last_line, cur_lev+1 – дляcur_lev в новом вызове. После возвращения из рекурсивного вызова просмотр продолжаетсяс оператора завершения найденного цикла. Метод добавления нового элемента ксписку цикла устроен так, что текущий указатель списка перемещается на вновьдобавленный.
void cLoopListSg::Analyse().
Для каждого элемента списка:
AnalyseHead(SymTab()); — анализзаголовка.
AnalyseBodyVars(SymTab()); — анализобращений к переменным и массивам в теле.
AnalyseRedVars(SymTab()); — поискредукционных переменных.
AnalyseIoOp(); — поиск операторовввода\вывода.
AnalyseGotoOp(); — анализ операторовперехода.
void cLoopListSg::AnalyseRedVars(cSymbolTabSg*).
В нашей задаче переменная считаетсяредукционной, если выполнены следующие условия:
перем = {перем} {операция}{выражение}, или (1)
перем =min/max({выражение}{перем}), или (2)
IF ({перем}{.GT.|.LT.}{выражение})
{перем}={выражение} (3)
{операция}="+"|"*" (4)
где {выражение} не содержит {перем},а также {перем} нигде больше не используется в данном цикле. Условие (3) естьдругая реализация условия (2). Также необходимо обнаруживать редукционныепеременные в выражениях вида:
{перем}={выражение}{операция}{перем}{операция}{выражение}(5), где выполняются те же условия, что и в (1)-(4), но при этом {операция}стоящая по обе стороны {перем} одинакова и если {операция} ="+", то{выражения} не содержат операций умножения и деления.
voidcSourceProgramSg::BuildProgGraph().
PrgGraph()->Build(FirstSt(),LastSt(), 0, sy_DIR_RIGHT1); — построение графа.
PrgGraph()->Analyse(); — анализпостроенного графа.
voidcProgramGraphSg::Analyse().
CountOpers();
void cProgramGraphSg::Build(SgStatement *first_line, SgStatement *last_line, int cur_lev, int cur_dir).
Для идентификации каждого извозможных направлений добавления новых элементов определены константы:
sy_DIR_RIGHT1,sy_DIR_RIGHT2, sy_DIR_DOWN
Добавление нового звена в некоторомнаправлении осуществляется при помощи методов cProgramGraphSg::AddNewRight1 ();
cProgramGraphSg::AddNewRight2 ();
cProgramGraphSg::AddNewRightFull ();- специальное добавление для блока слияния;
cProgramGraphSg::AddNewDown ();
При этом текущий указатель графаперемещается на новый блок.
Поскольку в графе отсутствуетзаглавное звено, первый узел графа строится особым образом независимо отуказанного направления.
Алгоритм работы метода (рекурсивный):
Перемещение текущего указателя спискациклов на первый элемент.
Запомнить номер текущего элементаграфа в переменной node1.
Начать цикл прохода с first_line.
switch
Если текущий оператор – заголовокцикла
Если перед этим прошли какое-токоличество операторов, т.е. надо добавить линейный блок, определяем направлениедобавления следующим образом:
Если еще ничего недобавляли и cur_dir == sy_DIR_DOWN
Добавить вниз.
Иначе
Если ничего недобавляли и cur_dir == sy_DIR_RIGHT2
Добавитьвправо2.
Иначе
Добавитьвправо1.
{такой анализ связан с тем, что когдамы добавляем 1-е звено в данном вызове метода, мы должны учитывать переданноенаправление; в остальных случаях добавление блоков на одном уровне происходитвправо1}
Запомнить номер текущего (только чтодобавленного) элемента в node1.
Заполнитьблок информацией.
{теперь надо добавить блокдля найденного цикла}
Определить направлениеаналогично и добавить.
Заполнить блок информацией.
Добавить в него информацию изтекущего элемента списка циклов и сдвинуться в списке вправо.
Вызвать рекурсивно Build стелом найденного цикла, cur_lev+1, sy_DIR_DOWN.
Установить указатель текущегооператора на конец цикла (ENDDO).
Если текущий оператор – заголовокветвления
Проверка на необходимостьдобавления линейного блока – аналогично.
Добавить блок развилки внужном направлении – аналогично.
Запомнить номер текущегоблока (развилка) в переменной node2.
Заполнить блок информацией.
Добавить слияние.
Запомнить номер текущегоблока (слияние) в переменной node3.
Вернуться влево (наразвилку).
Вызвать Build с телом 1-йветви, cur_lev, sy_DIR_RIGHT1.
Перейти на блок node2.
Вызвать Build с телом 2-йветви, cur_lev, sy_DIR_RIGHT2.
Перейти на блок node3(далее надо добавлять после слияния).
Установить указатель текущегооператора на конец ветвления (ENDIF).
Если текущий оператор – логический IF
Аналогично, только второйветви нет.
Если текущий оператор – IF-ELSEIF
Аналогично, только ELSEIFобрабатывается как новый IF-THEN.
Конец switch
Если текущий оператор == last_line
Закончить цикл просмотра
Проверка на наличие линейного участка– аналогично.
Перейти на блок node1 (тот, накотором были перед вызовом).
Заключение
Реализованные в дипломной работеклассы C++ выполняют следующие функции, соответствующие ее задачам:
— построение расширенного графа потокауправления программы, списка циклов и таблицы используемых идентификаторов;
— экспорт этих структур в файлы;
— предоставление блоку распределениявычислений и данных методов доступа к сохраненным структурам;
— дополнение внутреннего представленияпрограммы директивами FortranDVM, сформированными блоком распределениявычислений и данных.
Общий объем разработанногопрограммного кода – около 4500 строк на языке C++.
Возможные варианты использованияразработанных классов не ограничиваются системой автоматическогораспараллеливания. Они могут быть полезны также для решения задач, связанных соптимизацией программ, поиска логических ошибок в их структуре, профилированиеми др.
Направления развития блока, связаны,в первую очередь, со снятием ограничений на входную программу и реализацией невошедших в дипломную работу видов анализа.
Библиография
1. “Sage++ user’s guide (online)”, May 1995, Version 1.9
2. “Designingand Building Parallel Programs (Online) v1.3”, © Copyright 1995 by Ian Foster
3. “The Polaris InternalRepresentation.” Keith A. Faigin, Jay P. Hoeflinger, David A. Padua, Paul M.Petersen, and Stephen A. Weatherford. International Journal of Parallel Programming, October 1994.
4. “The Structure ofParafrase-2: An Advanced Parallelizing Compiler for C and Fortran” ConstantinePolychronopoulos, Milind B. Girkar, Mohammad R. Haghighat, Chia L. Lee, BruceP.Leung, Dale A. Schouten. Languages and Compilers for Parallel Computing, MIT Press, 1990
Приложение
В качестве одной из тестовых программиспользовалась реализация на языке Fortran77 алгоритма Якоби поиска решениясистемы линейных уравнений A x = b.
PROGRAM JACOB
PARAMETER (L=8, ITMAX=20)
REAL A(L,L), EPS, MAXEPS, B(L,L)
W = 0.5
MAXEPS = 0.5E — 7
DO 1 I = 1, L
DO 1 J = 1, L
A(I,J) = 0.
B(I,J) = (1. +I+J)*2.3
1 CONTINUE
DO 2 IT = 1, ITMAX
EPS = 0.
DO 21 I = 2, L-1
DO 21 J = 2, L-1
EPS = MAX (EPS, ABS(B(I,J)-A(I,J)))
A(I,J) = B(I,J)
21 CONTINUE
DO 22 I = 2, L-1
DO 22 J = 2, L-1
B(I,J) =(W/4)*(A(I-1,J)+A(I,J-1)+A(I+1,J)+A(I,J+1))+(1-W)*A(I,J)
22 CONTINUE
PRINT *, 'IT = ', IT, ' EPS = ', EPS
IF (EPS .LT. MAXEPS) THEN
GO TO 3
ENDIF
2 CONTINUE
3 OPEN (3, FILE='JACOBI.DAT', FORM='FORMATTED')
WRITE(3,*) B
END
Результат вывода в поток coutструктур данных, построенных тестирующей программой.
BuildingLoop List
Building Loop List — ok
Building Prog Graph
Building Prog Graph — ok
Printing Loop List
Count= 7
Id= 1 Lev= 0 Counter: Id= 1 Name= i Start: 1 End: 8Step: 1 IterNum: 8
Left vars: Array name= a Subscr0: 1*i+0 Subscr1:1*j+0 Array name= b Subscr0: 1*i+0 Subscr1: 1*j+0
Right vars: i j
Id= 2 Lev= 1 Counter: Id= 3 Name= j Start: 1 End: 8Step: 1 IterNum: 8
Left vars: Array name= a Subscr0: 1*i+0 Subscr1:1*j+0 Array name= b Subscr0: 1*i+0 Subscr1: 1*j+0
Right vars: i j
Id= 3 Lev= 0 Counter: Id= 5 Name= it Start: 1 End:20 Step: 1 IterNum: 20 Left vars: eps Array name= a Subscr0: 1*i+0 Subscr1:1*j+0 Array name= b Subscr0: 1*i+0 Subscr1: 1*j+0
Right vars: eps Array name= b Subscr0: 1*i+0Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+0 w Array name= aSubscr0: 1*i+-1 Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+-1Array name= a Subscr0: 1*i+1 Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0Subscr1: 1*j+1
Id= 4 Lev= 1 Counter: Id= 1 Name= i Start: 2 End: 7Step: 1 IterNum: 6
Left vars: eps Array name= a Subscr0: 1*i+0 Subscr1:1*j+0
Right vars: eps Array name= b Subscr0: 1*i+0Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+0
Id= 5 Lev= 2 Counter: Id= 3 Name= j Start: 2 End: 7Step: 1 IterNum: 6
Left vars: eps Array name= a Subscr0: 1*i+0 Subscr1:1*j+0
Right vars: eps Array name= b Subscr0: 1*i+0Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+0
Id= 6 Lev= 1 Counter: Id= 1 Name= i Start: 2 End: 7Step: 1 IterNum: 6
Left vars: Array name= b Subscr0: 1*i+0 Subscr1:1*j+0
Right vars: w Array name= a Subscr0: 1*i+-1 Subscr1:1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+-1 Array name= a Subscr0: 1*i+1Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+1 Array name= aSubscr0: 1*i+0 Subscr1: 1*j+0
Id= 7 Lev= 2 Counter: Id= 3 Name= j Start: 2 End: 7Step: 1 IterNum: 6
Left vars: Array name= b Subscr0: 1*i+0 Subscr1:1*j+0
Right vars: w Array name= a Subscr0: 1*i+-1 Subscr1:1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+-1 Array name= a Subscr0: 1*i+1Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+1 Array name= aSubscr0: 1*i+0 Subscr1: 1*j+0
Printing Loop List — ok
Printing Prog Graph
Count= 17
Id= 1 Lev= 0 Type= 1 Opers[4]=2 IsParal=0
Moving right1
Id= 2 Lev= 0 Type= 2 Loopid= 1 Opers[0]=16Opers[2]=8 Opers[4]=16 IsParal=1
Moving down
Id= 3 Lev= 1 Type= 2 Loopid= 2 Opers[0]=2 Opers[2]=1Opers[4]=2 IsParal=1
Moving down
Id= 4 Lev= 2 Type= 1 Opers[0]=2 Opers[2]=1Opers[4]=2 IsParal=0
Moving up
Repeat Id= 3
Moving up
Repeat Id= 2
Moving right1
Id= 5 Lev= 0 Type= 2 Loopid= 3 Opers[0]=36Opers[1]=24 Opers[2]=12 Opers[3]=6 Opers[4]=13 Opers[5]=1 Opers[6]=6 Opers[7]=6IsParal=0
Moving down
Id= 6 Lev= 1 Type= 1 Opers[4]=1 IsParal=0
Moving right1
Id= 7 Lev= 1 Type= 2 Loopid= 4 Opers[1]=6Opers[4]=12 Opers[6]=6 Opers[7]=6 RedVar[0]: var= eps op= 5 IsParal=1
Moving down
Id= 8 Lev= 2 Type= 2 Loopid= 5 Opers[1]=1 Opers[4]=2Opers[6]=1 Opers[7]=1 RedVar[0]: var= eps op= 5 IsParal=1
Moving down
Id= 9 Lev= 3 Type= 1 Opers[1]=1 Opers[4]=2Opers[6]=1 Opers[7]=1 IsParal=0
Moving up
Repeat Id= 8
Moving up
Repeat Id= 7
Moving right1
Id= 10 Lev= 1 Type= 2 Loopid= 6 Opers[0]=36 Opers[1]=18Opers[2]=12 Opers[3]=6 IsParal=1
Moving down
Id= 11 Lev= 2 Type= 2 Loopid= 7 Opers[0]=6Opers[1]=3 Opers[2]=2 Opers[3]=1 IsParal=1
Moving down
Id= 12 Lev= 3 Type= 1 Opers[0]=6 Opers[1]=3Opers[2]=2 Opers[3]=1 IsParal=0
Moving up
Repeat Id= 11
Moving up
Repeat Id= 10
Moving right1
Id= 13 Lev= 1 Type= 1 IsParal=0
Moving right1
Id= 14 Lev= 1 Type= 3 Opers[5]=1 IsParal=0
Moving right1
Id= 16 Lev= 1 Type= 1 IsParal=0
Moving right1
Id= 15 Lev= 1 Type= 4 IsParal=0
Moving left1
Repeat Id= 16
Moving left1
Repeat Id= 14
Moving right2
Repeat Id= 15
Moving left2
Repeat Id= 14
Moving left1
Repeat Id= 13
Moving left1
Repeat Id= 10
Moving left1
Repeat Id= 7
Moving left1
Repeat Id= 6
Moving up
Repeat Id= 5
Moving right1
Id= 17 Lev= 0 Type= 1 IsParal=0
Moving left1
Repeat Id= 5
Moving left1
Repeat Id= 2
Moving left1
Repeat Id= 1
Printing Prog Graph — ok
Printing Symbol Table
Id= 1 Name= i
Id= 2 Name= a Dim= 2 DimLen0= 8 DimLen1= 8
Id= 3 Name= j
Id= 4 Name= b Dim= 2 DimLen0= 8 DimLen1= 8
Id= 5 Name= it
Id= 6 Name= eps
Id= 7 Name= w
Printing Symbol Table — ok
Export Data
Export Data — ok
Opers[0] – ‘+’
Opers[1] – ‘-’
Opers[2] – ‘*’
Opers[3] – ‘/’
Opers[4] – ‘:=’
Opers[5] – ‘’,…
Opers[6] – ABS()
Opers[7] – MAX()
Redop=5 — MIN
Соответствующий распечатке граф.
/>