Содержание к диссертации
Введение
1. Анализ проблемы организации мобильных параллельных вычислений
1.1. Анализ существующих языков и систем параллельного программирования
1.2. Анализ существующих систем автоматического и полуавтоматического распараллеливания последовательных программ
1.3. Анализ формальных моделей данных, алгоритмов и программ
1.3.1. Модель алгоритма 22
1.3.2. Модель программы 25
1.4. Анализ существующих алгоритмов и методов распараллеливания последовательных программ
1.4.1. Методы и алгоритмы, используемые на стадии анализа последовательной программы
1.4.2. Методы и алгоритмы, используемые на стадии синтеза параллельной версии программы
1.5. Анализ существующих способов организации мобильных вычислений 43
1.5.1. Достижение переносимости на уровне ЯВУ 44
1.5.2. Переносимость в пределах заданной ОС 46
1.5.3. Архитектура ВС и обеспечение переносимости ПО 48
1.5.4. Использование промежуточного представления и абстрактной вычислительной машины
2. Модель параллельного промежуточного кода и алгоритмы преобразования исходных текстов последовательных программ в промежуточный код
2.1. Модель типов данных 56
2.1.1. Элементарный тип данных 58
2.1.2. Составной тип данных 65
2.2. Модель операций 72
2.2.1. Семантика операций над данными 73
2.2.2. Семантика управляющих операций 74
2.3. Модель параллельного промежуточного представления 87
2.3.1. Разработка алгоритма исключения оператора break из программы 91
2.3.2. Разработка алгоритма исключения оператора continue из программы
2.3.3. Разработка алгоритма выделения регионов на основе управляющей структуры программы
2.4. Модель параллельного промежуточного кода 98
2.4.1. Выявление параллелизма между регионами параллельного промежуточного кода
3. Синтез параллельных программ на основепараллельного промежуточного кода
3.1. Модель операционной системы как среды функционирования парал- 108
дельных процессов
3.1.1. Алгебраическая модель подсистемы управления процессами ОС
3.1.2. Автоматная сеть как модель параллельного вычислительного процесса
3.2. Статический синтез параллельной реализации последовательной программы для мультипроцессорной вычислительной системы с общей памя
тью
3.2.1. Разработка алгоритма статического синтеза параллельной программы
3.2.2. Разработка алгоритма отображения параллельной программы на модель операционной среды
3.2.3. Уточнение длительности исполнения параллельных регионов программы в условиях неопределенности
3.2.4. Расчет величины уточняющей задержки на основе предварительных статистических испытаний
3.3. Динамический синтез параллельной реализации последовательной программы для мультипроцессорной вычислительной системы с общей памя тью
3.3.1. Использование метода спекулятивной многопоточиости для динамического распараллеливания последовательных программ
3.3.2. Расчет характеристик использования метода спекулятивной мно-гопоточности для динамического распараллеливания циклов
3.3.3. Выделение спекулятивных регионов и эпох на основе параллельного промежуточного кода
4. Экспериментальное исследование разработанных алгоритмов
4.1. Экспериментальное исследование характеристик разработанных алгоритмов
4.1.1. Экспериментальное исследование алгоритма исключения оператора break
4.1.2. Исследование алгоритма исключения оператора continue 156
4.1.3. Экспериментальное исследование алгоритма выделения регионов 158
4.1.4. Экспериментальное исследование алгоритма статического синтеза параллельной программы
4.2. Области практического применения полученных результатов 162
4.2.1. Программные средства поддержки этапа преобразования последовательных программ в мобильный параллельный промежуточный код
4.2.2. Программные средства поддержки этапа исполнения параллельного промежуточного кода
4.3. Результаты внедрения 167
Заключение 169
Список литературы
- Анализ формальных моделей данных, алгоритмов и программ
- Составной тип данных
- Алгебраическая модель подсистемы управления процессами ОС
- Экспериментальное исследование алгоритма статического синтеза параллельной программы
Введение к работе
Актуальность темы. Развитие технологий программирования для персональных компьютеров с точки зрения повышения производительности программ традиционно происходило в основном экстенсивными методами. По большей части разработчики универсального программного обеспечения (ПО) уповали на постоянное совершенствование аппаратных ресурсов компьютера, в частности технологического процесса производства микропроцессоров. Таким образом, очередная установка процессора с увеличенной тактовой частотой позволяла получить ускорение работы прикладных программ без малейшего их изменения.
В настоящее время достигнут фактический предел роста тактовой частоты процессоров и дальнейшее увеличение их производительности становится возможным только за счет перехода к многоядерной архитектуре, по существу к параллельной архитектуре. Так на сегодняшний день для персональных компьютеров уже широко распространены процессоры с 6 и даже 12 ядрами, а в ближайшей перспективе количество ядер может измеряться сотнями. Подобная технологическая революция в архитектуре персонального компьютера предоставляет существенный потенциал для роста производительности ПО, доступный ранее только в мире суперкомпьютеров. Однако для реализации этого потенциала необходимы столь же серьезные революционные изменения современных технологий программирования, а также решение задачи адаптации огромного объема существующего последовательного ПО для эффективного высокопроизводительного выполнения в параллельной вычислительной среде. Термин последовательное ПО подразумевает программы, написанные в расчете на их исполнение на однопроцессорной ВС и не предусматривающие явно организацию параллельных вычислений. В этом смысле без перевода последовательного ПО в параллельную форму выигрыш от использования многоядерных микропроцессоров будет незначительным.
Большое разнообразие существующих сегодня архитектурных платформ, операционных систем (ОС), использующих многоядерные процессоры, а также технологий и языков программирования, положенных в основу последовательного ПО, заставляет искать решение указанной задачи для каждой из них в отдельности. Это создает вторую проблему — проблему переносимости параллельных программ, то есть ставит задачу приведения ПО в соответствие с требованием мобильности. Термин мобильное ПО (portable software) подразумевает программы, которые могут быть откомпилированы и корректно выполнены на вычислительных системах (ВС) с различной архитектурой, без каких-либо изменений.
Сложившаяся ситуация делает важным решение задачи построения и исследования формальных моделей и алгоритмов переноса и распараллеливания универсального последовательного ПО с позиции обеспечения мобильности и эффективности организации его последующего исполнения в среде многоядерных процессоров. Таким образом, тема диссертационной работы является актуальной.
Степень разработанности темы. Научно-методической основой исследований представленных в диссертационной работе являются труды отечественных и зарубежных учёных и специалистов: ГлушковаВ.М, Воеводина В.В., Воеводина Вл.В., ПрангишвилиИ.В., Виленкина С.Я., Поспелова Д.А., Касьянова В.Н., Корячко В.П., ТелковаИ.А., Скворцова СВ., КаширинаИ.Ю., Цейтлина Г.Е., Ющенко Е.Л., БутомоИ.Д., Дейкстры Э., ПраттаТ., ТаненбаумаЭ., Дала Э., Хоара Ч.Э., Brandis М.М., Kazi I.H., Steffan J.G., Mowry Т.С, Gupta R и других.
В работах Телкова И.А. предложена модель вычислительных алгоритмов и вычислительных систем в рамках единой тензорной методологии, определены подходы к обеспечению мобильности параллельных вычислений, обосновано использование виртуальной параллельной машины, предназначенной для выполнения мобильного ПО на любых типах многопроцессорных ВС. Так как практическая реализация тензорных моделей в силу их большой размерности сопряжена с вычислительными трудностями, в диссертационной работе для формализации концепции параллельной виртуальной машины предложено использовать алгебраический и теоретико-графовый подход.
В работах Глушкова В.М., Цейтлина Г.Е., Ющенко Е.Л. предложен аппарат систем алгоритмических алгебр, предназначенный для исследования свойств алгоритмов и программ. В работах Каширина И.Ю. исследованы свойства алгоритмических языков на базе алгебраических моделей, предложен подход к представлению данных и управляющих конструкций программ на основе формального описания программной машины. Во второй главе диссертации предложено развитие данных подходов с позиции обеспечения мобильности данных, разработано семейство алгебраических систем типов данных.
В работах Корячко В.П. исследованы вопросы построения оптимальных укладок функциональных графов программ применительно к задачам оптимизации числа обращений к оперативной памяти, определены основные понятия и характеристики укладок, предложены методы и алгоритмы укладки графов. В третьей главе диссертационной работы предложено распространить использование методов укладки графов программ на решение задачи синтеза параллельной программы.
В работах Скворцова СВ. предложены модели и методы организации параллельных процессов на мелкозернистом уровне параллелизма на основе теоретико-графового подхода. В диссертационной работе предлагается использовать графовые модели на крупноблочном уровне параллелизма.
В работах Steffan J.G. и Mowry Т.С представлено описание метода спекулятивной многопоточности и проведён анализ возможных способов повышения его эффективности на этапе исполнения, в частности за счет использования аппаратной реализации контроля нарушения зависимостей по данным. В работах Kazi I.H. предложен способ организации спекулятивного многопоточного кон-веера для параллельной обработки смежных итераций цикла. В третьей главе диссертационной работы предложены формальная модель метода спекулятивной многопоточности и алгоритмы повышения эффективности его применения на этапе выделения спекулятивных циклических регионов.
Цель диссертационной работы состоит в обеспечении мобильности программ для последующего их высокопроизводительного исполнения в среде многоядерных процессоров путём разработки моделей и алгоритмов организации мобильных параллельных вычислений.
Разработка таких моделей и алгоритмов позволит сократить сроки и дополнительные затраты по переносу последовательных программ в параллельную форму, повысить производительность их исполнения на многоядерных процессорах.
В соответствии с поставленной целью необходимо решить следующие основные задачи:
произвести анализ и оценку существующих методов и систем распараллеливания последовательных программ, а также способов организации мобильных вычислений;
разработать формальные модели мобильного представления последовательных программ;
разработать алгоритмы перевода исходных текстов последовательных программ на языках высокого уровня в переносимую параллельную форму;
разработать алгоритмы планирования и оптимизации вычислительного процесса исполнения программ, представленных в переносимой параллельной форме, в среде ВС с многоядерными процессорами;
спроектировать программные средства, реализующие разработанные модели и алгоритмы, с целью их экспериментальной проверки, апробации и внедрения.
Методы исследования. Для решения поставленных задач в диссертационной работе были использованы следующие методы исследования: теория алгебраических систем, теория графов и математическое программирование, теория расписаний, теория формальных языков.
Научная новизна работы состоит в следующем.
Предложена формальная модель мобильного параллельного промежуточного кода (МППК), основанная на алгебраических моделях типов данных и операций языков программирования, обеспечивающая мобильность параллельного представления последовательных программ, заданных на различных языках высокого уровня, отличающаяся использованием нового базиса управляющих операций.
Разработаны алгоритмы исключения операций выхода за пределы ветви управляющей конструкции, основанные на предложенной модели МППК, обеспечивающие корректность представления исходных текстов программ. Разработан алгоритм выделения программных регионов, основанный на предложенной модели МППК, обеспечивающий предварительное крупноблочное распараллеливания программы, отличающийся меньшей трудоёмкостью в сравнении с аналогами.
Предложена формальная модель подсистемы управления процессами ОС, основанная на предложенной модели МППК и модели автоматной сети, обеспечивающая представление вычислительного процесса на уровне ОС среды многоядерных процессоров.
Разработан эвристический алгоритм статического синтеза параллельной программы для мультипроцессорной вычислительной системы с общей памятью, основанный на методе укладки графов, обеспечивающий синтез параллельной программы для ВС с заданным числом процессорных ядер, отличающийся меньшей трудоёмкостью по сравнению с аналогами.
Предложена формализация метода спекулятивной многопоточности, используемого для динамического планирования параллельных вычислений, основанная на предложенной модели МППК, обеспечивающая оценку перспективности применения этого метода для распараллеливания циклических участков программы.
Разработан алгоритм выделения спекулятивных регионов, основанный на предложенной модели МППК и предложенной формализации метода спекулятивной многопоточности, обеспечивающий повышение эффективности использования данного метода.
Практическая значимость работы состоит в следующем:
разработаны модели и алгоритмы, позволяющие сократить сроки и дополнительные затраты по переносу последовательных программ в параллельную форму, и повысить производительность их исполнения на многоядерных процессорах;
спроектированы программы-конверторы исходных текстов последовательных программ с языков высокого уровня Паскаль и Си в мобильный параллельный промежуточный код;
разработаны программные средства поддержки этапа исполнения мобильного параллельного промежуточного кода, позволяющие ускорить его выполнение на вычислительной системе с многоядерными процессорами.
Апробация результатов диссертации. Результаты, полученные в рамках работы над диссертацией, докладывались на 5 международных и 8 всероссийских научно-технических конференциях: международных конференциях «Управление и информационные технологии на транспорте» (Санкт-Петербург, 1999), «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (Рязань, 1997, 1999, 2000, 2001), всероссийских конференциях «Новые информационные технологии в научных исследованиях и образовании» (Рязань, 1997, 1998, 1999, 2000, 2006, 2008 — 2 доклада, 2009 — 2 доклада, 2010 — 2 доклада).
Публикации. По теме диссертации опубликовано 30 работ: 13 статей (в том числе 3 статьи в журналах из перечня ВАК), 16 тезисов докладов на международных и всероссийских конференциях, одно свидетельство об официальной регистрации программы.
Внедрение результатов работы. Результаты, полученные в диссертационной работе, внедрены в разработки научно-технической продукции филиала ФГУП «ГНПРКЦ «ЦСКБ-Прогресс» - «ОКБ «Спектр» и научно-производственного предприятия ООО «ЭЛЬФ 4М», а также представляют часть НИР № 7-98, № 42/10-01, выполненных в Рязанском государственном радиотехническом университете.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, библиографического списка (157 источников). Основной текст работы содержит 177 страниц, 20 таблиц, 22 рисунка. В приложении на 3 страницах приведены акты внедрения результатов и свидетельство о регистрации программы для ЭВМ.
Анализ формальных моделей данных, алгоритмов и программ
Решение проблемы организации параллельного программирования лежит в области создания новых параллельных языков высокого уровня (ЯВУ), либо в модификации наиболее популярных последовательных ЯВУ путём добавления параллельной парадигмы. Наибольшее распространение получил второй подход, что обусловлено: а) широким распространением наиболее популярных ЯВУ (Фортран, Си, Паскаль); б) наличием строгих спецификаций на уровне международных стандартов для этих языков; в) большим объемом созданного на этих языках ПО; г) широкой практикой программирования на этих языках. Создание принципиально новых ЯВУ обычно оправдано лишь при невозможности использования модификаций ни одного из распространенных ЯВУ, например, для нетрадиционных архитектур ВС — машина потока данных или при разработке проблемно ориентированных ЯВУ.
Модификация последовательных ЯВУ производится на основе следующих подходов.
1) Использование макрорасширений или специальных директив компилятору [83]. Директивы макрорасширения позволяют специфицировать некоторые виды параллельности. Макрорасширения обычно оформляются в тексте программы в виде специальных комментариев и транслируются препро цессором в операторы языка с вызовами специальных подпрограмм, реализую щих параллельную обработку. Пример подобного пакета макрорасширений — пакет Argonne/GMD, разработанный в Аргоннской национальной лаборатории для языков Си и Фортран [121], а также DVM-система, созданная в Институте прикладной математики им. М.В.Келдыша РАН, с расширениями для языков Си и Фортран [63].
Однако подобный подход не очень удобен при программировании на языке высокого уровня, так как исключает возможность своевременного контроля со стороны компилятора [93], а неявное добавление промежуточного кода осложняет отладку программ.
2) Более удобным и естественным является подход, основанный на введении расширений непосредственно в язык. Одновременно это позволяет компилятору производить некоторые дополнительные виды оптимизации. По этому пути пошли разработчики языка и системы программирования трС, соз данных в Институте системного программирования РАН [2] и ориентированных на параллельные вычисления в неоднородных сетях. Создатели языка программирования Cilk из Массачусетского технологического института, также предложили своё параллельное расширение для языка Си, но уже ориентированное на организацию многопоточных вычислений [109].
Однако в процессе разработки расширений возникают дополнительные проблемы, связанные: а) с необходимостью выбора новых средств для представления парал лельности; б) с проблемой отображения выбранных средств в конкретную языковую среду, что требует учёта всего многообразия уже существующих языко вых средств, тонкости использования конструкций языка. 3) Наиболее радикальным представляется подход к созданию новых диалектов традиционных языков, с изменением исходной парадигмы программирования. Примером является отечественная разработка Т-Системы (OpenTS) [1] средства автоматического динамического распараллеливания программ, разработанного в Институте программных систем РАН, основанного на параллельном диалекте языка Си и парадигме функционального программирования.
В отсутствие унифицированных языковых средств ведущие производители параллельных ВС зачастую разрабатывают собственные средства, включая их в состав специализированных компиляторов. Эти средства в основном ориентированы на конкретную архитектуру. Совершенно очевидно, что многообразие подходов делает программы немобильными, затрудняет перенос программ с одной ЭВМ на другую и существенно осложняет перенос ПО.
Проблему обеспечения мобильности помогает частично разрешить стандартизация в языках средств спецификации распараллеливания. Примером может служить создание международного стандарта языка Фортран 90, в который введены новые средства работы с массивами, а так же спецификация стандартов макрорасширений языков Фортран и Си для модели передачи сообщений на базе интерфейса MPI [143, 104, 83, 65, 64] и для модели разделяемой памяти ОрепМР [146, 104, ИЗ].
Таким образом, можно сделать вывод, что решение задачи разработки новых параллельных языков программирования поможет лишь частично снять проблему повышения эффективности многоядерных вычислений. Подобный подход применим только для вновь разрабатываемого ПО, но никак не решает проблему адаптации существующих последовательных программ, а также не снимает проблемы обеспечения мобильных параллельных вычислений.
Составной тип данных
Средства описания данных в ЯВУ определяются исходя из двух противоположных предпосылок: с точки зрения машинной (реализационной) составляющей и с общематематической (теоретико-множественной) позиции. Первая составляющая исторически преобладала в ЯВУ первого и второго поколения, роль второй составляющей усиливалась в последующих поколениях языков.
С машинной точки зрения тип объекта есть форма представления его значения в памяти и определяемый этой формой способ доступа к объекту и его частям. В этом случае тип может быть определён как множество значений, которые могут принимать объекты данных этого типа.
С математической позиции тип данных есть множество с операциями (алгебра). При этом помимо ограничения на область значений накладывается ограничение и на набор операций, выполняемых над этими значениями [38, 55].
При выборе набора базовых операций требуется, чтобы он содержал все операции необходимые для эффективной реализации любой производной операции.
В минимальный, с точки зрения идентификации нового типа данных, набор входят следующие операции [89]: описания и инициализации переменных типа; при этом описание типа дает некоторую интерпретацию определяемым синтаксисом языка символам, которые вводятся для обозначения констант; присваивания; определение и изменение текущего значения для любой переменной типа. Предполагает пересылку полной копии значения данного типа в памяти по месту расположения переменной;отношений равенства (неравенства); сравнение любых двух значений типа, по крайней мере, на равенство или неравенство; эти операции должны входить в набор операций при определении любого типа (операция сравнения должна удовлетворять общепринятым свойствам, например, транзитивности, инвариантности относительно функциональных преобразований и т.д.).
В структуре типов данных большинства современных ЯВУ выделяется три основные категории [38, 89]: элементарный тип определяет простейшие скалярные данные с вещественной или дискретной областью определений и задаёт простейшие арифметические и логические операции; составной тип представляет набор (комбинацию) данных нескольких простых или ранее определенных составных типов данных, объединенных определенным образом; абстрактный тип, в отличие от составного типа, определяет помимо набора данных ещё и дополнительно базовые операции на множестве элементов собственного типа. Преимущества использования абстракции с точки зрения мобильности типов [4,89]: 1) машинная независимость; информация о типе, содержащаяся в промежуточном коде, позволяет определить механизмы реализации ПВМ на целевой ВС форму представления значений переменных и объём требуемой машинной памяти наиболее эффективные с точки зрения особенностей архитектуры этой ВС, в частности произвести необходимое распараллеливание потоков данных; 2) защита (безопасность); контроль типов данных на уровне исполнительной системы целевой ВС программно или аппаратно, для этого требуется информация о типах. Семантика ЯВУ задаётся и интерпретируется через семантику программ и данных, составленных на данном языке. Семантика же программ определяется конечной реализацией машинными средствами целевой ВС. Следовательно, для того, чтобы обеспечить эквивалентную интерпретацию исходной программы для различных ВС, с точки зрения данных программы, необходимо явно указать особенности машинной реализации размещения и обеспечения доступа к данным.
Это можно сделать, дополнив модель данных спецификацией атрибутов данных. Посредством спецификации представления можно уточнить требования к реализации определенных типов на целевой машине. Например, можно указать размерность представления объектов определенного типа (количеством требуемых битов памяти для хранения), что поля структуры составного типа должны располагаться с такого-то адреса. С каждым базовым типом данных сопоставляется свой набор атрибутов спецификации.
Представим всё множество элементарных типов данных ЯВУ семейством частично универсальных алгебраических систем 3E={TEk\k=l,...,NE}. Элементом семейства является алгебраическая система элементарного типа данных вида ТЕ = E,FE,RE,AtrE , состоящая из основного множества Е значений объектов элементарного типа, определенной на нем совокупности частичных операций FE (конечной сигнатуры), а также системы отношений RE на элементах алгебры и множества атрибутов типа AtrE алгебраической системы. Множество частично определенных функций сигнатуры FE составляют в общем случае n-арные функции вида F"(xl)...,x„ ). Для большинства элементарных типов в это множество входят унарные и бинарные арифметические операции. С помощью атрибутов из множества AtrE будем явно задавать некоторые свойства типа данных, имеющие определяющее значение для повышения мобильности программ. Множество Е определяет диапазон и характер области определений (дискретная или непрерывная) объектов типа и области значений применяемого к ним набора операций. Диапазон характеризуется мощностью типа, т.е. количеством различных значений типа и граничными значениями. Средством указания диапазона значений объектов типа, может явиться введение во множество х:еЕ ХієЕ AtrE элементов amin,amax є AtrE \ атіп = min{ ,.};crmax = тах{дг;}. Необходимость і і введения подобных атрибутов явного задания диапазона объясняется конечной природой последующего машинного представления данных элементарных типов средствами ВС. При этом предполагается, что на множестве Е определены отношения линейного порядка R = { , }.
Далее ограничим базовый набор из NE - алгебраических систем элементарных типов данных, так чтобы представить всё многообразие элементарных типов данных современных ЯВУ. Рассмотрим алгебраические системы следующих типов данных: 1) целые числа; 2) действительные числа; 3) перечислимый тип. Тип целых чисел Тип целых чисел относится к классу числовых типов ЯВУ и является машинным представлением бесконечного множества дискретных значений математических целых чисел с определенными на нем арифметическими операциями. Зададим формально тип целых чисел с помощью алгебраической системы целого типа данных Т1Е є Зя следующим образом: где Е = {xt є ZI x0 X; xn}, причем Z является множеством целых чисел, а Е1 подмножеством, ограниченным диапазоном [хо, х„]. Сигнатура алгебры представлена множеством операций: F/ = {:= (2), + (2), - (2), x (2), /(2), mod(2), + (1), - (1), abs(l)}.
Размерность (арность) операции указана в скобках, после соответствующего знака операции. Множество отношений алгебраической системы составляют следующие отношения R e = {-, , , , , Ф} над элементами алгебры. Множество атрибутов типа включает элементы: ат]п, атт,аЪу1е є Atr E.
Семантика большинства операций является интуитивно понятной и совпадает с общепринятыми арифметическими операциями, значения результатов вычисляются точно, без ошибок округления. Семантика операции х/ mod х2 выражается следующей формулой: ху mod х2 = х1—(х1/х2)хх2. Операции являются частично определенными с точки зрения попадания области значения операции в диапазон [х0, х„].
Алгебраическая модель подсистемы управления процессами ОС
Вместе с тем существуют и отрицательные стороны высокоуровневого представления структуры управления. Во-первых, отсутствие явного представления ветвлений (они интегрированы в структуру управляющей конструкции) препятствует проведению анализа условий, минуя границы управляющих конструкций, а это необходимо, например, в случае поиска и устранения повторяющихся вычислений, обусловленных избыточностью условных выражений в управляющей структуре программы. Во-вторых, напротив, наличие в высокоуровневой структуре управления ЯВУ инструкций выхода за пределы управляющих конструкций в произвольном месте — прерывание потока управления, разрушает иерархию вложенности структур запутанными зависимостями между ними, ограничивает возможности оптимизации. К таковым инструкциям относятся, например, операторы безусловного перехода goto, операторы выхода за границы управляющей конструкции exit (Паскль), break, continue (Си).
Приведенный анализ показывает необходимость соблюдения некоторого компромисса при выборе базиса алгебры управляющих операций между явным представлением высокоуровневых структур управления ЯВУ, классифицированных в аксиоматике Хоара, и требованием устранения недостатков непосредственного высокоуровневого представления. Ключом к реализации подобного компромисса является использование предложенной Дейкстрой концепции «охраняемых операторов» [51], что отражается введением в состав базиса управляющих операций 0 так называемых «стражей» (guards), и дальнейшим развитием этой идеи в работе [111], чему соответствует введение в 0с двух типов «объединителей» (merges). Подобное представление позволяет устранить первую из двух вышеперечисленных проблем — совместить явное представление ветвлений и высокоуровневое представление условных структур.
Что касается решения второй проблемы, проблемы представления неструктурированного потока управления, то вполне допустимым представляется ввести запрет на использование оператора безусловного перехода goto, тем более что дисциплина современного программирования в рамках структурного проектирования рекомендует совсем отказаться от его применения и придерживаться строгих ограничений на переход извне через границы управляющих структур [49]: не входить внутрь блока извне; не входить внутрь условного оператора, т.е. не передавать управление операторам, размещенным внутри альтернативных ветвей; не входить извне внутрь структуры «переключатель»; не передавать управление внутрь цикла. Проблему исключения операторов выхода за пределы ветви управляющей конструкции в произвольной точке exit, break, continue можно разрешить с помощью добавления дополнительных условных конструкций таким образом, чтобы сделать выход обусловленным. Алгоритмы подобных преобразований рассматриваются ниже (п.2.3.1, п.2.3.2).
С учётом вышеназванных замечаний, состав базиса управляющих операций О" выберем следующим: 0 = {csq,Csd,cm8,Cmc} (2.1) Семантика элементов множества 0 определяется следующим образом. I. Csq(p/ , Oi+i ,..., Oi+n ) — выполнить (и+і)-операцию над данными of, oi+/,..., оі+/ є If, непосредственно следующую друг за другом. Соответствует структуре «последовательность» в аксиоматике Хоара.
П. cs (р(о/), с,) — если предикат, описывающий некоторое отношение, выполняется (истинен) для выражения of Є If, следует выполнить операцию сj є Ос, в противном случае необходимо запретить выполнение с,. Эта конструкция называется стражем, а операция с} вместе со стражем — охраняемым оператором и обладает свойствами, определёнными в работе [51]. Операция с. может являться производной конструкцией, выраженной с помощью композиции элементов основного множества управляющих операций Ос. III. c" 8(cfd, cf+l,..., cf+n) — задать точку слияния (и+У -стража для объединения всех альтернативных ветвей. Эта операция называется объединителем, позволяющим описывать в общем случае мультиветвление, а при п = 1, задавать точку слияния двух ветвей условной конструкции аксиоматики Хоара «альтернатива». IV. cmc (cj ,cs.,cf) — задать точку слияния потока управления, ведущего извне внутрь цикла, обратного пути после выполнения очередной итерации тела цикла в начало цикла и точку выхода из цикла после его окончания. Эта конструкция является объединителем для структуры типа «цикл». Выделение отдельного объединителя для циклов необходимо для явного представления циклических конструкций. Аргумент ct є Ос является конструкцией, выполнение которой непосредственно предшествует началу цикла. Аргумент cg, — есть страж условной конструкции, описывающейся предусловием или постусловием выполнения тела цикла. Аргумент с\ — есть страж условной конструкции, задающий точку выхода их цикла.
Нижние индексы в обозначении аргументов элементов множества базовых управляющих конструкций представляют собой порядковые номера (адреса) аргументов в записи последовательной композиции промежуточного представления программы. При определении производных от базовых управляющих конструкций необходимо придерживаться следующих правил, вытекающих из семантики базовых управляющих операций.
Экспериментальное исследование алгоритма статического синтеза параллельной программы
Методы статического распараллеливания последовательных программ существенно ограничены в возможностях выявления параллелизма между программными регионами, поскольку основаны на анализе структуры программы до начала её исполнения. На этом этапе ещё не известны значения переменных, используемых в программе, состав её входных данных. В случае если такие переменные используются в индексных выражениях при обращениях к массивам или в граничных значениях циклов, статические методы анализа не смогут сделать какие-либо выводы. Кроме того, в процессе статического анализа не удаётся выявлять информационные зависимости, связанные с использованием динамических структур данных: указателей, динамических массивов, объектов, вызовов функций в индексных выражениях. То есть поток данных между программными регионами (2.2) не должен связывать операторы, состоящие в отношениях о иЫп, О_ош, о"и1_оы1 (2.16 - 2.18), имеющих неопределенный характер. Если это требование не выполняется, требуется заменить данные отношения более строгими: дош_іп, 6іп_оМ, 5ош_оШ (2.13 - 2.15), что существенно ограничивает возможности распараллеливания.
Снять большинство ограничений на структуру управляющих и информационных связей последовательной программы можно, используя методы динамического распараллеливания [53, 37, 62, ПО, 119]. При этом под динамическим распараллеливанием понимается способ выявления параллельных регионов и планирование их выполнения непосредственно во время исполнения (runtime) параллельного промежуточного кода последовательной программы.
Поскольку анализ происходит во время выполнения программы, становятся доступны значения всех переменных, присутствующих в программе. Поэтому появляется возможность проанализировать любые ссылки на элементы массивов: через индексные выражения любой сложности, включая вызовы функций, через указатели. Динамический анализатор всегда может однозначно установить ячейку памяти, которая используется в любом операторе программы.
Однако недостатки динамических методов также следуют из того, что анализ информационных зависимостей производится во время выполнения программы. Во-первых, динамический анализ показывает только те зависимости, которые возникают при данном конкретном запуске программы, т.е. часть информационных зависимостей так и остается неопределенными. Во-вторых, большинство существующих методов динамического распараллеливания пред-. назначены для выявления параллелизма на мелкозернистом уровне и плохо приспособлены для крупнозернистого распараллеливания. В-третьих, сам про-,-цесс планирования отвлекает вычислительные ресурсы, которые могли бы быть использованы для непосредственного исполнения программных инструкций, особенно если требуется анализировать протяженные участки кода при крупноблочном подходе. Поэтому, актуальной является задача разработки подхода к динамическому исполнению параллельного промежуточного кода, который мог бы устранить отмеченные недостатки.
Наиболее подходящим методом динамического распараллеливания последовательных программ для мультипроцессорных (многоядерных) вычислительных систем с общей памятью, с учётом обозначенных выше недостатков, является метод спекулятивной многопоточности [154, 134, 156, 145].
Суть метода состоит в следующем. Среди множества всех регионов G последовательной программы выявляются регионы, имеющие зависимости ти 136 па Зош- п Z-out ЇЇм-т (2Л6 - 2Л8) характер которых не может быть установлен на этапе трансляции программы из-за неоднозначности. Статические методы при планировании параллельного исполнения подобных регионов, чтобы исключить нарушение информационных зависимостей в случае их возникновения, вынуждены использовать более сильные виды отношений, прибегая к позиции крайнего пессимизма. Такой подход негативно отражается на результатах распараллеливания. Метод спекулятивной многопоточности предписывает параллельное многопоточное выполнение подобных регионов, в расчёте на то, что информационные зависимости на стадии исполнения не проявятся, прибегая к позиции крайнего оптимизма (спекулируя на удаче). В случае если подобные надежды оправдают себя, будет получен выигрыш в производительности, в противном случае, результаты вычислений региона должны быть аннулированы, и он будет выполнен повторно, что приведет к накладным расходам. Регионы программы, к которым применяется подобный метод, будем называть спекулятивными регионами [154]
Для того, чтобы организовать многопоточное выполнение спекулятивных регионов, формируется динамическая последовательность стадий их исполнения, называемых эпохами [154] Ve; є ЕР \i — \,N,N = ЕР . Например, для циклического региона эпохами являются отдельные итерации цикла. Каждая эпоха снабжается локальным буфером памяти для сохранения критических к возможным нарушениям зависимости данных. Результаты выполнения эпохи приводятся в соответствие со следующими правилами.
Похожие диссертации на Модели и алгоритмы организации мобильных параллельных вычислений в среде многоядерных процессоров
