Далее приведем конкретные примеры управляемых пакетов оптимизаций, реализованных в компиляторе.

Пакет низкоуровневых оптимизаций на потоке данных.

Объектом применения оптимизаций пакета является операция. Дадим краткое описание оптимизаций, входящих в пакет.

· удаление мертвого кода. Удаляются операции, результаты которых далее нигде не используются, а потому их присутствие не влияет на поведение программы при исполнении.

· подстановка констант. Если удалось определить, что результатом операции является константа, то операция удаляется, а константа подставляется в места использования результата операции.

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

· эквивалентные преобразования выражений, состоящих из операций представления. Например, х+0=х, х*1=х

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

· удаление избыточных операций чтения из памяти. Если операции чтения можно поставить в соответствие предшествующую запись в память по тому же адресу (с форматом, не меньшим, чем у этой операции чтения) и между этими операциями нет других, записывающих по тому же адресу, то операция чтения удаляется, а в местах ее использования подставляется записанное ранее значение.

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

Оптимизации пакета не выполняют преобразования промежуточного представления, а заказывают набор преобразований у менеджера пакета. Менеджер пакета предоставляет следующие типы преобразования промежуточного представления:

· Подстановка вместо результата операции константы;

· Удаление операции по одному из правил;

· Замена результата операции на результат уже существующей операции;

· Замена результата операции на результат дерева новых операций, когда новые операции создаются по некоторому их формальному описанию.

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

Управляемый пакет оптимизаций имеет высокую эффективность при сравнительно небольших затратах по времени. Большинство оптимизаций использует одинаковые структуры данных, требующие инициализации. При объединении оптимизаций в пакет инициализация дополнительных структур делается один раз. Известно, что применение одних оптимизаций дает возможность применять другие. Добиться эффективности, соизмеримой с эффективностью управляемого пакета, можно многократными вызовами отдельных оптимизаций, но этот способ требует больших временных ресурсов. В управляемом пакете управляемые вызовы осуществляются только для тех операций, которые этого требуют. Для большинства операций делается всего один проход по всем оптимизациям.

Пакет цикловых макрооптимизаций.

Объектом применения оптимизаций пакета является цикл. Перечислим оптимизации, входящие в пакет.

· слияние внутреннего цикла с охватывающим циклом.

· перестановка циклов.

· полная раскрутка цикла.

· частичное повторение тела цикла (открутка).

· расщепление цикла по инвариантному условию. Для цикла создается точная копия. Управление передается на цикл или его копию в зависимости от предиката инвариантного условия. В цикле инвариантное условие считается тождественной истиной, в копии - тождественной ложью.

· расщепление цикла по индексу. Если в цикле имеется условие, ограничивающее изменение его индуктивной переменной, то он разбивается на два цикла. В первом ограничение, заданное условием, берется в качестве верхней границы, во втором - в качестве нижней. В обоих циклах убираются вычисления, соответствующие условию выхода значения индуктивной переменной за ее границы.

· расщепление цикла по произвольному условию. В случае более общего условия для некоторого условия класса циклов возможно расщепление одного класса на три. Первый цикл не содержит альтернатив условия. Второй цикл содержит первую альтернативу условия. Третий цикл вторую альтернативу условия. Число итераций первого цикла равно числу итераций исходного цикла. Среднее число итераций второго цикла равно среднему числу повторений первой альтернативы. Среднее число итераций третьего цикла равно среднему числу повторений второй альтернативы. Значения переменных исходного цикла, используемых в альтернативах, запоминаются в массивы в первом цикле и считываются во втором и третьем циклах.

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

Объектом применимости управляемого пакета является дерево циклов.

· Основные задачи:

· минимизировать время оптимизации цикловых участков.

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

· разрешение конфликтов между оптимизациями.

Обработка дерева циклов происходит от листьев к корню.

В работе [10] рассматривается компилятор Intel:

Компилятор языка Си использует runtime-библиотеку, разработанную в рамках проекта GNU (libc.a).

Вместе с компилятором Intel C++ поставляются следующие библиотеки:

· libcprts.a - runtime-библиотека языка С++ разработки Dinkumware.

· libcxa.a - дополнительная runtime-библиотека для С++ разработки Intel.

· libimf.a - библиотека математических функций разработки Intel, в которую входят оптимизированные и высокоточные реализации тригонометрических, гиперболических, экспоненциальных, специальных, комплексных и других функций.

· libirc.a - runtime-поддержка профилировки (PGO) и "диспетчеризации" кода в зависимости от процессора (см. выше).

· libguide.a - реализация OpenMP.

Уровни оптимизации
Опция	Описание
-O0	Отключает оптимизацию
-O1 или -O2	Базовая оптимизация на скорость работы. Отключается инлайн-вставка библиотечных функций. Для компилятора С++ эти опции дают одинаковую оптимизацию, для компилятора Фортрана опция -O2 предпочтительнее, т.к. включает еще раскрутку циклов.
-O3	Более мощная оптимизация, включая преобразования циклов, предвыборку данных, использование OpenMP. На некоторых программах может не гарантироваться повышенная производительность по сравнению с -O2. Имеет смысл использовать вместе с опциями векторизации -xK и -xW.
-unroll[n]	Включает раскрутку циклов до n раз.
Оптимизации под конкретный процессор
Опция	Описание
-tpp6	Оптимизация для процессоров Penitum Pro, Pentium II и Pentium III
-tpp7	Оптимизация для процессоров Penitum 4 (эта опция включена по умолчанию для компилятора на IA-32)
-xM	Генерация кода с использованием расширений MMX, специфических для процессоров Pentium MMX, Pentium II и более поздних
-xK	Генерация кода с использованием расширений SSE, специфических для процессоров Pentium III
-xW	Генерация кода с использованием расширений SSE2, специфических для процессоров Pentium 4
Межпроцедурная оптимизация
-ip	Включается межпроцедурная оптимизация внутри одного файла. Если при этом указать опцию -ip_no_inlining, то отключаются инлайн-вставки функций.
-ipo	Включается межпроцедурная оптимизация между различными файлами
Оптимизации с использованием профилей
-prof_gen	Генерируется "профилировочный" код, который будет использован для профилировки, т.е. сбора данных о частоте прохождения тех или иных мест в программе
-prof_use	Производится оптимизация на основе данных, полученных на этапе профилировки. Имеет смысл использовать вместе с опцией межпроцедурной оптимизации -ipo.
Распараллеливание для SMP-систем
-openmp	Включается поддержка стандарта OpenMP 2.0
-parallel	Включается автоматическое распараллеливание циклов

В этом списке перечислены статических библиотек, но для большинства из них существуют также динамические, т.е. подключаемые во время запуска, варианты (.so).

Вместе с компилятором Фортрана поставляются следующие библиотеки: libCEPCF90.a, libIEPCF90.a, libintrins.a, libF90.a, также используется библиотека математических функций libimf.a.

В ОРС [17] библиотека преобразований выделяется в отдельную самостоятельную часть. Такая самостоятельность позволяет библиотеке уделять больше внимания, преобразования классифицировать и группировать, сформировать специальную архитектуру библиотеки, систему тестов для преобразований.

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

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

Всякое преобразование должно сохранять синтаксическую и семантическую корректность. Это означает, например, что нельзя менять местами в тексте программы тело цикла и заголовок. Приведем пример и менее очевидной ошибки. Если при развертке цикла копируется тело цикла, в котором есть операторы с метками, то могут получиться два оператора с одной и той же меткой (чего не допускает синтаксис ФОРТРАНа).

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

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

Библиотека преобразований программ состоит из нескольких уровней.

Верхний уровень -- оптимизирующие (распараллеливающие) преобразования. Эти преобразования могут представлять собой композицию вспомогательных преобразований. Например, вынос инварианта из цикла может быть получен в два приема. Сначала выполняется разрезание цикла на два, в теле первого из полученных циклов должен быть инвариантный оператор, а в теле другого -- остальные. Теперь у первого цикла следует удалить заголовок -- и получится искомое преобразование.

Нижний уровень -- упомянутые выше редакторские преобразования.

Есть еще вспомогательные преобразования, вроде перестановки операторов присваивания (такая перестановка сама по себе ценности не представляет, но может быть полезна, например, при векторизации или при разрезании цикла). Иногда одно оптимизирующее преобразование может играть роль вспомогательного преобразования для другого.

Проверка эквивалентности обратного преобразования может сводиться к проверке эквивалентности прямого (исходного). Например, для проверки эквивалентности слияния циклов достаточно выполнить это слияние и проверить, можно ли к нему применить разбиение цикла.

Самыми первыми должны выполняться канонизирующие преобразования, приводящие элементы программы к стандартному виду.

Оптимизирующие (распараллеливающие) преобразования бывают локальными и глобальными. В многочисленных публикациях описаны десятки таких преобразований.

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

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

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

Выводы из обзора

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

Основной задачей распараллеливающего компилятора является выявление скрытого (как правило) или явного (что редко) параллелизма. Такой анализ проводится не по самому тексту программы, по ее модели.

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

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

Результаты потокового анализа по выявлению параллелизма используются для применения оптимизирующих преобразований из класса реструктурирующих. В общем случае этот класс направлен на эквивалентное преобразование программы, позволяющее впоследствии ее распараллелить. Наиболее часто в трансляторах используются следующие преобразования: перестановка циклов, слияние циклов, разбиение цикла, распределение циклов. Множество используемых на практике преобразований постоянно расширяется. Этому процессу в немалой степени способствует появление компьютеров новой архитектуры.

Несмотря на то, что проблема оптимизации программ для компьютеров с параллельной архитектурой существует уже более 20 лет, ее решение до сих пор нельзя считать удовлетворительным. Было предложено много различных подходов к оптимизации, но ни один из них не предполагает комплексного решения всего множества возникающих проблем. Более того, как показали недавние исследования Иллинойского университета, большинство методов потокового анализа распознают лишь 15% из всех пар зависимостей. На этом фоне успешной выглядит система V-Ray, практическое экспериментальное исследование которой показало превосходство (порой весьма значительное) над другими системами оптимизации. Однако V-Ray является лишь инструментом для выявления параллелизма, а анализ результатов, выбор и применение ОП и производятся вручную и неинтерактивно, как и постановка экспериментов.

2. Описание предметной области, решаемых задач и методов их решения

2.1 Описание предметной области

В данном параграфе описываются знания о преобразованиях и методах потокового анализа распараллеливаемых программ.

2.1.1 Граф алгоритма

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

При некоторых фиксированных входных данных программа описывает некоторый алгоритм. Строится ориентированный граф. В качестве вершин берётся любое множество, например, множество точек арифметического пространства, на которое взаимнооднозначно отображается множество всех операций алгоритма. Берётся любая пара вершин и, v. Допускают, что согласно частичному порядку операция, соответствующая вершине u, должна поставлять аргумент операции, соответствующей вершине v. Тогда проводится дуга из вершины и в вершину v. Если соответствующие операции могут выполняться независимо друг от друга, дуга не проводится. В случае, когда аргументом операции является начальное данное или результат операции нигде не используется, возможны различные договоренности. Например, можно считать, что соответствующие дуги отсутствуют. Построенный таким образом граф можно было бы назвать графом информационной зависимости реализации алгоритма при фиксированных входных данных. Однако такое название слишком громоздко. Поэтому его называют просто графом алгоритма [4]. Независимо от способа построения ориентированного графа, те его вершины, которые не имеют ни одной входящей или выходящей дуги, называют соответственно входными или выходными вершинами графа.

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

В дальнейшем, если не сделаны дополнительные оговорки, рассматриваются детерминированные алгоритмы и программы. Причины введения этого ограничения следующие:

· детерминированные алгоритмы и программы устроены проще и исследования начинают именно с них;

· класс детерминированных алгоритмов и программ весьма широк сам по себе;

· многие формально недетерминированные алгоритмы в действительности являются почти детерминированными. Например, в том случае, когда ветвления охватывают конечное число операций, не зависящее от значений входных данных. Такие ветвления можно погрузить в более крупные операции, имеющие, тем не менее, конечное число аргументов.

Если ветвления охватывают большие детерминированные фрагменты, то все равно исследование графа алгоритма сводится к исследованию этих фрагментов.

Введенный в рассмотрение граф алгоритма есть ориентированный ациклический мультиграф, Его ацикличность следует из того, что в любых программах реализуются только явные вычисления и никакая величина не может определяться через саму себя. Даже если в программе имеются рекурсивные выражения, то это всего лишь удобная форма описания однотипных вычислений. При каждом обращении к рекурсии на самом деле реализуются разные операции. В общем случае граф алгоритма есть мультиграф, т. е. две вершины могут быть связаны несколькими дугами. Это будет тогда, когда в качестве разных аргументов одной и той же операции используется одна и та же величина. Для обозначения графа применяется стандартная символика G = (V, Е), где V- множество вершин, Е- множество дуг графа G.

Истории реализаций программ называют графами алгоритмов. Формально между понятиями истории реализации программы и графа алгоритма, описанного той же программой, нет различий. Но название "граф алгоритма" лучше отражает суть дела. Например, один и тот же алгоритм может быть описан на одном и том же языке разными программами. Соответствующие истории формально также будут разными, если для расположения вершин использовать один и тот же принцип. Однако как графы все истории изоморфны между собой. Следовательно, они скорее отражают не программы, а описываемый ими алгоритм. История реализации есть графовая модель программы. Слово "граф" в названии "граф алгоритма" подчеркивает это обстоятельство. Можно привести и другие аргументы в пользу использования названия "граф алгоритма". По определению, граф алгоритма существует для любой программы.

2.1.2 Графы зависимостей и минимальные графы

Прежде всего, необходимо точно описать множество вершин. Пусть задана произвольная линейная программа. Перенумеруем подряд сверху вниз все операторы циклов do, точнее, все параметры циклов. Обозначаются параметры через I₁, ..., I_n . Считают, что из двух параметров младшим (старшим) является тот, у которого номер меньше (больше). Перенумеруем также сверху вниз все операторы присваивания и обозначим их через F₁, ..., F_m.

С каждым оператором присваивания свяжем тесно вложенное гнездо циклов. Его можно получить, оставляя в программе только те циклы do, в тела которых входит рассматриваемый оператор. Такое гнездо циклов называется опорным для данного оператора. Пусть опорное гнездо оператора F_i описывается параметрами . Рассмотрим арифметическое пространство, координаты точек которого совпадают со значениями этих параметров. Его размерность равна s_i. Такое пространство называется опорным. Если оператор не входит ни в какое гнездо, то размерность опорного пространства будем считать равной 0. Не ограничивая существенно общности, можно предполагать, что отдельный оператор описывается гнездом циклов, у которых нижние и верхние границы изменения каждого из параметров совпадают. Такое предположение позволяет приписать какие-то параметры даже отдельным операторам.

Границы изменения параметров циклов опорного гнезда определяют в опорном пространстве линейный многогранник. Его называют опорным для оператора F_i и обозначают V_i . Ветвления, определяющие условия срабатывания оператора F_i, вырезают из опорного многогранника некоторую область. Принимая во внимание целочисленность параметров циклов, эту область можно описать конечным числом замкнутых линейных многогранников. Ее также называют опорной и обозначают V_i. По определению V_i V_i. Совокупность опорных областей V_i для i = 1, 2, ..., т называется линейным пространством итераций. Это есть многосвязная область, состоящая из линейных многогранников, принадлежащих разным арифметическим пространствам. Факт, что некоторые или даже все многогранники могут порождаться одними и теми же параметрами циклов, не имеет сейчас никакого значения. Это будет отражаться лишь в том, что такие многогранники будут в чем-то похожи по расположению в своих пространствах и иметь какие-то размеры одинаковыми. По определению линейной программы каждый из параметров пробегает некоторое множество целочисленных значений с шагом +1. Точку линейного пространства итераций называют целочисленной, если все ее координаты являются целыми числами. Совокупность всех целочисленных точек линейного пространства итераций называется просто пространством итераций.

Границы изменения параметров циклов и условия ветвления могут зависеть от внешних переменных. Поэтому размеры всех многогранников и их конфигурации могут зависеть от значений этих переменных. Как правило, с ростом значений переменных размеры многогранников неограниченно увеличиваются. Это является характерной чертой пространства итераций.

Каждому срабатыванию оператора F_i при конкретных значениях параметров циклов ставится в соответствие точка пространства итераций из области V_i с теми же значениями координат . Тем самым устанавливается взаимно однозначное соответствие между пространством итераций и множеством всех срабатываний всех операторов программы. Принимая во внимание структуру отдельных срабатываний, получается отображение на пространство итераций множества всех исполняемых операций. Все точки одной области V_i и только они соответствуют срабатываниям одного оператора F_i.

Строя в дальнейшем какие-то графы на множестве операций программы всегда в качестве множества вершин следует брать пространство итераций. Вершины называют точками или векторами.

Каждая линейная программа задает множество исполняемых операций. При реализации программы операции выполняются в строго определенном порядке, который диктуется самой программой. Этот порядок называется лексикографическим. Его обозначают символом . Нестрогий лексикографический порядок будем обозначать символом .

Утверждение 1

Пусть точка J пространства итераций относится j-ому оператору программы и описывается параметрами Ij1,..., Ij1j , точка I относится к i-ому оператору и описывается параметрами Ii1,..., Ii1i. Пусть, например, j < i. Тогда:

* если пересечение совокупностей номеров j1,…,jsj и i1,…,isi, пусто, то любой параметр Ij1 младше любого параметра Iik;

* если пересечение совокупностей номеров j1,…,jsj и i1,…,isi не пусто, то любой параметр, номер которого входит в пересечение, младше любого параметра, номер которого не входит в пересечение; любой параметр Ij1, номер которого не входит в пересечение, младше любого параметра Iik номер которого также не входит в пересечение [4].

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

Это утверждение позволяет ввести отношение порядка в линейном пространстве итераций. Будем также называть его лексикографическим и обозначать тем же символом . Рассмотрим любую пару различных точек I и J. Пусть точка I описывается параметрами I_i1,..., I_i1i, точка J описывается параметрами I_j1,..., I_j1j.

Будем считать, что J I , если:

· либо пересечение совокупностей номеров пусто и j < i;

· либо пересечение совокупностей номеров не пусто, значения всех одинаковых параметров попарно совпадают и j < i;

· либо пересечение совокупностей номеров не пусто, значения каких-то младших одинаковых параметров могут попарно совпадать, но среди одинаковых параметров, значения которых попарно не совпадают, самый младший параметр точки j имеет меньшее значение, чем тот же параметр точки i.

Если рассматривать точки пространства итераций как точки линейного пространства итераций, то лексикографический порядок в линейном пространстве итераций автоматически порождает лексикографический порядок в пространстве итераций. По построению он таков, что J I тогда и только тогда, когда при последовательной реализации программы срабатывание оператора, соответствующее точке J, будет осуществляться раньше срабатывания оператора, соответствующего точке I.

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

Различают четыре типа зависимостей. Для всех начальных (конечных) точек дуг одного типа имеет место один и тот же тип обращения к переменной, определяющей зависимость. Именно, либо всюду значение переменной используется в качестве аргумента при срабатывании оператора, либо всюду результат срабатывания оператора используется для замены значения переменной. Использование значения переменной в качестве аргумента обозначают символом "in", использование результата для замены значения символом "out". Парой in-out (in-in, out-out, out-in) обозначают тип зависимости. Левый (правый) символ в паре относится к начальной (конечной) точке дуги зависимости. Традиционно для типов зависимости используются следующие названия:

out-in - истинная или dataflow-зависимость;

in-out - антизависимость;

out-out - зависимость по выходу;

in-in - зависимость по входу.

Соответственно этому различают четыре типа графов зависимостей. Все дуги любого графа имеют один и тот же тип зависимости.

2.1.3 Циклы ParDo и избыточные вычисления

Все графы зависимостей обладают общим свойством. Именно, для каждой дуги конечная вершина лексикографически старше начальной. Такие графы называются лексикографически правильными. Любой лексикографически правильный граф является ациклическим.

Изучение параллельной структуры программ связано с изучением множеств операций, которые можно выполнять независимо друг от друга. Дадим определения соответствующих понятий. Пусть в пространстве итераций задан ориентированный лексикографически правильный граф G. Это может быть какой-нибудь из минимальных графов зависимостей или некоторый подграф любого из объединений минимальных графов или какой-либо другой граф. Если программа зависит от внешних переменных, то от них будет зависеть и граф G. Рассмотрим непересекающиеся множества М₁, ..., M_p вершин пространства итераций. Назовем эти множества параллельными по графу G или просто параллельными, если при любых фиксированных значениях внешних переменных:

· любой путь графа G, связывающий две вершины одного множества, целиком лежит в этом множестве;

· никакие две вершины из разных множеств не связаны путем графа G.

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

Под параллельной структурой программы понимают совокупность сведений о параллельных множествах в пространстве итераций. Сюда же будем относить и сведения о тех преобразованиях, целью которых является либо выявление, либо изменение параллельных множеств. Говоря о параллелизме в программах, обычно обсуждают два его вида: макропараллелизм и микропараллелизм. Макропараллелизм связан с ситуацией, когда все или хотя бы часть из параллельных множеств содержат много точек. Микропараллелизм имеет дело с теми случаями, при которых в каждом из параллельных множеств находится всего лишь несколько точек. Типичным для микропараллелизма является ситуация, когда множества содержат только по одной точке. В частности, параллельными будут те множества-точки пространства итераций, которые не связаны дугой графа G.

Рассмотрим какой-нибудь цикл do произвольной программы из линейного класса. Его также можно считать программой из линейного класса. Параметры циклов, внешних по отношению к данному циклу do, играют в нем такую же роль, как и внешние переменные программы. Их значения хотя и фиксированы к началу выполнения цикла, но на момент исследования неизвестны. Можно лишь утверждать, что вектор параметров внешних циклов является целочисленным и принадлежит совокупности линейных многогранников. Рассмотрим далее пространство итераций цикла do. Все его точки можно разбить на непересекающиеся множества, если отнести к каждому множеству те из них, которые соответствуют одной и той же итерации цикла. Обозначают эти множества через М₁, ..., М_p . Пусть в пространстве итераций цикла введен ориентированный лексикографически правильный граф G. Будем говорить, что цикл имеет тип ParDo no графу G, если множества М₁, ..., М_р параллельны по этому графу при любых допустимых, но фиксированных значениях внешних переменных.

Заметим, что при любых значениях внешних переменных группы операций, соответствующие множествам М₁, ..., М_р , могут выполняться последовательно друг за другом без выполнения каких-либо других операций. Это означает, что если множества М₁, ..., М_р параллельны по графу G, то несвязанность путем любой пары точек, принадлежащих различным множествам M_i, эквивалентна их несвязанности дугами. Поэтому имеет место

Утверждение 4

Пусть в пространстве итераций цикла DO задан ориентированный лексикографически правильный граф G. Для того чтобы цикл DO был циклом ParDo по графу G, необходимо и достаточно, чтобы никакая пара точек пространства итераций, соответствующих одним и тем же значениям параметров внешних циклов, но различным значениям параметра рассматриваемого цикла, не была бы связана дугой графа G.[4]

Теперь рассмотрим для цикла do его минимальные графы зависимостей или какие-нибудь объединения этих графов.

Если цикл do имеет тип ParDo по графу алгоритма, то никакие пары точек пространства итераций, соответствующие разным итерациям цикла, не могут быть связаны дугами графа алгоритма. Это означает, что при последовательном исполнении цикла результаты реализации операций, относящихся к разным итерациям цикла, не влияют друг на друга. Потенциально итерации цикла ParDo по графу алгоритма можно выполнять независимо друг от друга. Однако для осуществления такой возможности нужно быть уверенным в правильности порядка пересчета значений одних и тех же переменных на разных итерациях цикла.

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

Предположим, что цикл do имеет тип ParDo по объединению всех четырех минимальных графов зависимостей. Теперь любые пары операций из разных итераций циклов всегда имеют дело с разными переменными. Поэтому такие циклы эффективно реализуются на любых вычислительных системах, в том числе и на многопроцессорных системах с распределенной памятью.

Таким образом, графы зависимостей цикла do играют исключительно важную роль в распознавании параллельных свойств цикла. В силу этого необходимо иметь эффективные критерии установления свойства ParDo по таким графам. Пусть граф G представлен покрывающими функциями вида х = Jy + . Здесь J числовая матрица, вектор линейно зависит от внешних переменных цикла, векторы х и у задают точки пространства итераций цикла. Заметим, что параметру цикла соответствуют первые координаты векторов х, у. Один из критериев таков.

Утверждение 5

Пусть граф G задан покрывающими функциями вида х = Jy + . Для того чтобы цикл имел тип ParDo по графу G, достаточно, чтобы граф G был пустым или для всех покрывающих функций первое равенство в выражениях х = Jy + имело вид x₁ = у₁. [4]

Почти всегда это условие на практике оказывается и необходимым. Например, оно заведомо будет таким, если граф описывается покрывающими функциями точно и покрывающие функции являются целочисленными.

2.1.4 Эквивалентные по вычислениям преобразования программ

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

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

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

Сохранение результатов вычислений имеет безусловный приоритет при преобразовании программ. Поэтому очень важно иметь критерий такого сохранения. Уже отмечалась особая роль графа алгоритма среди минимальных графов. Посмотрим, что объединяет программы, эквивалентные по этим графам.

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

При любом порядке перебора вершин результаты выполнения операций, соответствующих первым ярусам, зависят только от входных данных программ. Поэтому для обеих программ они будут одинаковыми при одних и тех же входных данных в операциях, соответствующих одинаково расположенным вершинам. Предположим, что для обеих программ одинаковыми будут результаты выполнения всех соответствующих операций из всех ярусов от 1-го до k-го, k 1. Рассмотрим любую вершину J из (k + 1)-го яруса. Если в вершину J входит дуга из вершины I, то для каждой из программ I J по определению графа алгоритма. Вершина обязательно находится в ярусе, номер которого не превосходит k. Следовательно, при любом допустимом переборе вершин наборы значений аргументов для операции, соответствующей вершине J, будут одними и теми же. Это означает, что и для (k + 1)-го яруса результаты выполнения соответствующих операций будут для обеих программ одинаковыми. Заканчивая перебор всех ярусов, заключаем, что справедливо

Утверждение 6

Пусть программы эквивалентны по графам алгоритма. Тогда при последовательной реализации на одном и том же компьютере при одних и тех же входных данных они будут давать одни и те же результаты, включая всю совокупность ошибок округления.[4]

По существу программы, эквивалентные по графам алгоритма, представляют различные записи одного и того же алгоритма. Единственное, чем они могут принципиально отличаться друг от друга, - это объемом памяти, необходимым для хранения результатов промежуточных вычислений, а также формой организации переменных в массивы. Кроме этого, входные и выходные данные таких программ могут отличаться друг от друга какой-либо их пересортировкой. Мы будем предполагать, что при реализации эквивалентных программ необходимая пересортировка делается. Эквивалентные программы обладают одним и тем же параллелизмом. Однако записан он может быть по-разному. Например, в одной программе какой-то параллелизм может быть описан явно в форме циклов ParDo. В другой программе этот же параллелизм может оказаться неявно описанным в форме скошенного.

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

Пусть выполняется преобразование программы. Чтобы показать, что исходная и преобразованная программы дают одни и те же результаты, вроде бы нужно построить для них графы алгоритмов и сравнить эти графы на изоморфизм. Однако этот способ проверки эквивалентности программ не всегда возможно осуществить на практике. Сравнение графов на изоморфизм является довольно трудоемкой задачей. Кроме этого, очень часто принимать решение о том, какое преобразование нужно делать, приходится по ходу построения самого преобразования. В этом случае мы просто не можем получить граф алгоритма преобразованной программы. Поэтому необходимо поступить иначе. Будем выполнять специальное преобразование. Оно гарантирует в ряде случаев эквивалентность по графам алгоритма и позволяет осуществлять промежуточный контроль. Это преобразование охватывает большую группу конкретных преобразований, объединенных общим названием переупорядочивание пространства итераций. Пусть для исходной программы построен граф зависимостей. Специальное преобразование таково:

· выполняется эквивалентное преобразование пространства итераций;

· для новой программы выбираются такие переменные, чтобы при преобразовании пространства итераций разные переменные переходили в разные, одинаковые - в одинаковые;

· в новом пространстве итераций устанавливается лексикографический порядок, при котором образ графа зависимостей будет лексикографически правильным.

2.2 Модель структурных программ

В данной части описывается представление программы в СБкЗ_ПП - модель структурных программ (МСП). Формальное описание онтологии предметной области «Классические оптимизирующие преобразования» представлено в работах [2, 3]. Первая часть содержит определение терминов для описания объекта оптимизации преобразований. Вторая часть содержит термины для описания процесса оптимизации.

2.2.1 Термины объекта оптимизации

В работах [2] и [3] описана модель структурных программ (МСП).

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

В работе [3] описана модель онтологии объекта оптимизации программ. Сначала неформально описываются основные термины в данной предметной области, а затем даётся их формальное определение. Кроме этого, приводится определение языка описания МСП как примера обогащения модели онтологии. Описанная модель онтологии оптимизации программ позволяет изменять модель языка, на котором описываются оптимизируемые программы, что является важным при изучении свойств ОП для различных языков программирования.