Содержание к диссертации
Введение
1. Обзор методов межпроцедурного анализа и внутренних представлений целевого языка 8
1.1 Анализ совмещений 9
1.2 Анализ значений 15
1.3 Анализ использования переменных 18
1.3.1 Неточные алгоритмы описания областей массивов 20
1.3.1.1 Регулярные секции (Regular Sections) 21
1.3.1.2 Дескрипторы доступа к данным (Data Access Descriptors) 22
1.3.1.3 Регионы (Regions) 23
1.3.2 Точные алгоритмы описания областей массивов 24
1.3.2.1 Образы (Atom Images) 24
1.3.2.2 Линеаризация (Linearization) 25
1.3.2.3 Омега-тест 26
1.3.3 Комбинированные методы . 27
1.4 Анализ контекста использования процедуры 28
1.5 Язык SISAL 30
1.5.1 Система SFP 32
1.5.2 Внутреннее представление IR1 33
1.5.3 Внутреннее представление IR2 34
1.5.4 Внутреннее представление IR3 37
Выводы по первой главе 38
2. Практическая реализация анализа и оптимизаций 39
2.1 Свойства внутренних представлений 40
2.2 Хранение контекстных условий 49
2.3 Алгоритмы анализа 51
2.3.1 Протягивание одиночных значений 52
2.3.2 Протягивание мультизначений 57
2.3.3 Протягивание диапазонов 59
2.3.4 Протягивание мультидиапазонов 61
2.3.5 Протягивание другой информации о значениях 63
2.3.6 Анализ массивов 67
2.3.7 Реализация алгоритмов анализа значений 73
2.4 Алгоритмы оптимизации 74
2.4.1 Удаление избыточного кода 75
2.4.3 Вынос инвариантных вычислений 80
2.4.4 Оптимизация циклических конструкций 82
2.4.5 Оптимизация копирования 84
2.5 Межпроцедурный анализ 86
2.5.1 Граф исполнений вызовов 87
2.5.3 Алгоритмы анализа 89
2.6. Алгоритмы распараллеливания 98
2.6.1 Построение развёртки 100
2.6.2 Влияние оптимизирующих алгоритмов 107
2.6.3 Макропараллелизм циклов SISAL 109
Выводы по второй главе 111
3. Тестирование анализа и оптимизаций 112
3.1 Структура разработанного транслятора 113
3.2 Ввод и вывод данных 116
3.3 Вычислительные задачи 120
Выводы по третьей главе 126
Заключение 127
Список литературы 128
Приложение
- Анализ использования переменных
- Анализ контекста использования процедуры
- Протягивание другой информации о значениях
- Влияние оптимизирующих алгоритмов
Введение к работе
Актуальность проблемы
В данной работе пойдёт речь о статическом анализе программ, а именно о той части, которая отвечает за взаимодействие процедур и функций программы.
Межпроцедурный анализ относится в первую очередь к анализу потока данных, который поступает при вызове в процедуру и из неё. В рамках данной работы под межпроцедурным анализом будем понимать анализ влияния вызова процедуры на контекст вызова и определение влияния контекста вызова на исполнение вызываемой процедуры.
Такой вид анализа приобретает особую ценность в распараллеливающих компиляторах. Если не анализировать код вызываемых процедур, придётся предположить, что все параметры и глобальные переменные могут измениться в результате вызова. Это существенно снизит эффективность результирующего кода, потому что, например, циклы, содержащие вызовы, не будут распараллелены в большинстве случаев. А распараллеливание на сегодняшний день также является неотъемлемой частью оптимизирующего транслятора, поскольку в последнее время увеличение вычислительных мощностей связано уже не с ускорением отдельного, а с добавлением дополнительных вычислителей и созданием различного рода суперкомпьютеров и кластеров.
Оптимизации и работа компилятора вообще заключается в преобразовании внутреннего представления. Внутренние представления варьируются от приближенных к языкам высокого уровня до приближенных к уровню машинного кода. Параллелизм наиболее универсально описывается при помощи представлениях, основанных на потоке данных. В таких представлениях не требуется тратить дополнительные усилия для анализа зависимостей. Примером могут служить многочисленные проекты, развивающие SSA форму. Одним из таких представлений является IR2, рассматриваемое в данной работе. К такому представлению может быть приведён даже императивный язык. Известны проекты, где Fortran транслируется в IF1, представление с аналогичной структурой, но другим набором вершин.
Потоковая структура IR2 является наиболее универсальным описанием параллелизма, что важно для переносимости кода. При решении вычислительных задач, удобнее всего не вдаваться в конкретные детали распараллеливания своей задачи и создавать код, который мог быть исполнен на системах с различной конфигурацией.
Все перечисленные причины делают анализ и оптимизацию потоковых структур актуальными.
Цель работы - адаптация известных оптимизаций и распараллеливания для потоковой модели вычислений. Разработка новых алгоритмов анализа и оптимизации.
Методы исследования. В диссертационной работе использовались понятия и методы теории построения компиляторов, теории смешанных вычислений, теории алгоритмов, теории графов, теории схем программ и элементы теории множеств.
Научная новизна.
Предложен новый метод анализа значений элементов массивов, который позволяет оптимизировать всюду завершаемые частичные вычисления.
Предложен новый подход к межпроцедурному анализу, основанный на графе исполнений вызовов, в рамках которого предложены эффективные алгоритмы осуществления анализа.
Впервые исследованы параллельные свойства и преобразования потоковых программ в рамках иерархического графового представления IR2.
Практическая ценность.
Практическая часть данной работы описывает реализацию межпроцедурного анализа и распараллеливания в рамках системы функционального программирования (SFP), разрабатываемой в Институте Систем Информатики им. А.П. Ершова (ИСИ СО РАН). Основные оптимизирующие преобразования в SFP производятся на уровне внутреннего потоко-
вого представления IR2, в которое может быть транслирован даже императивный язык. Это внутреннее представление может описывать массивы и циклические конструкции, что не является обычным для внутреннего представления функционального языка программирования.
Разработанные методы реализованы в рамках компилятора Sisal 3.2. Компилятор Sisal 3.2 является частью системы SFP, разрабатываемой в рамках проекта ПРОГРЕСС. Компилятор будет использоваться другими разработчиками системы, которая ориентирована на решение математических задач на суперкомпьютерах и обучение функциональному программированию .
Апробация работы. Основные положения диссертации обсуждались на следующих конференциях и семинарах:
1.Семинар «Конструирование и оптимизация программ», Новосибирск, ПСИ СО РАН, 2004-2008 г.;
2.конференция-конкурс «Технологии Microsoft в информатике и программировании», Новосибирск, 2008 год.
3.XLIV Международная научная студенческая конференция «Студент и научно-технический прогресс», Новосибирск, 2006 г.
4.Четвертая азиатская международная школа-семинар «Проблемы оптимизации сложных систем» / ИВМиМГ 2008
5.Решетнёвские чтения / Красноярск 2009
Публикации. Результаты работы опубликованы в 9 печатных работах, из которых 4 полных статьи и 5 тезисов конференций.
Структура и объем работы
Диссертационная работа состоит из введения, трёх глав, заключения, списка литературы и двух приложений. Объем диссертации - 127 стр. Список литературы содержит 80 наименований. Работа включает 26 рисунков и графиков, полученных в результате расчетов на ЭВМ.
Анализ использования переменных
При анализе процедуры можно выделить четыре множества переменных: READ — множество переменных, используемых для чтения в теле подпрограммы, WRITE — множество переменных, используемых для записи в теле подпрограммы, EST —множество используемых для чтения внешних переменных и параметров процедуры, OUT — множество переменных, вычисляемых и записываемых в процедуре, используемых в последующем коде.
Информация об этих множествах востребована оптимизирующими преобразованиями, в частности, на основе этой информации часть внутреннего или внешнего кода процедуры может быть исключена.
Первые три множества могут быть получены при анализе тела подпрограммы и вызываемых ею подпрограмм, а четвёртое множество — только путём анализа всего кода, который исполняется после процедурного вызова. Такой анализ не производится, если не учитывается возможность вызова процедуры из различных контекстов и влияние контекста на тело процедуры вообще. Множество OUT отражает характеристики не самой подпрограммы, а последующего кода, и может быть использовано для межпроцедурных оптимизаций. Например, может оказаться, что некоторые или все внутрипроцедурные вычисления могут быть удалены как мёртвый код.
В случае, когда транслятор различает обязательные и не обязательные результаты и аргументы операций, связанные с ветвлениями кода [60], к этим множествам добавляются соответствующие необязательные варианты. Таким образом, вместо множества записываемых переменных появляется «обязательное» множество записанных переменных и «необязательное» множество записанных переменных, которые не пересекаются. Если переменная находится среди необязательно записываемых — это означает, что она может быть не записанной при каких-то параметрах задачи. Но это не означает, что такой случай обязательно будет иметь место на практике.
Если при анализе переменных рассматривать каждый массив как одно целое (запись в элемент массива считать записью массива, а чтение переменной массива считать чтением массива) — результат получается слишком грубым. Для более точного анализа следует рассматривать компоненты массива отдельно, что и производится при анализе итераций циклов, использующих массивы, но для глобального анализа этот способ имеет большие накладные расходы. Компромиссом является рассмотрение отдельных областей массива в качестве атомарных единиц. Существует множество способов описания областей, они различаются по точности, скорости работы и требуемым объёмам памяти. Рассмотрим основные способы описания областей массивов. Их можно разделить на две группы: точные — дают такой же результат, что и анализ каждой компоненты массива как отдельной переменной; неточные - дают приближённое описание областей массивов, которое требует меньше памяти и вычислительного времени, но даёт огрублённый результат.
В некоторых случаях, на стадии статического анализа нельзя точно ответить на вопрос: будет ли записана переменная X при исполнении программы. В этом случае компилятор должен сделать «пессимистическое» предположение о том, что переменная будет записана. А оптимизирующие преобразования должны быть устроены таким образом, что не должны порождать неэквивалентный код в таких случаях. Для считываемых переменных ситуация полностью аналогична. Таким образом, мы можем пометить даже все переменные как считываемые и записываемые во всех функциях программы, а оптимизирующие преобразования должны породить эквивалентный код. Безусловно, это скажется на характере и эффективности оптимизаций. Неточные алгоритмы описания областей массивов используют эту возможность «пессимистичного» предположения и описывают область, которая включает искомую область. В таком случае говорят о приблизительном описании областей массивов.
Кроме рассмотренных ниже алгоритмов анализа, разработчики Fida [8] включают в состав неточных алгоритмов «Пессимистический (Pessimistic) алгоритм», который заключается в том, что все массивы предполагаются изменяемыми в процессе работы процедуры (межпроцедурный анализ не осуществляется), и «Классический (Classic)» — анализ массивов как скаляров. Это делается для сравнения их на тестах другими алгоритмами.
Этот алгоритм впервые предложили Каллаган и Кеннеди [9] (Callahan, Kennedy). Области массивов задаются через значения индексных переменных размерностей массива. Регулярные секции делятся на два вида: ограниченные регулярные секции (restricted regular sections) и описания с помощью триплетов (bounded regular sections). В методе ограниченных регулярных секций каждой из размерностей массива сопоставляется одно из следующих выражений: 1. - - - если индексная переменная может принимать любое значение. 2. а - если переменная принимает только одно, константное значение. 3. a±jk — если индексная переменная связана с другой индексной переменной этого же массива константным смещением.
Анализ контекста использования процедуры
Анализ контекста использования направлен на уточнение оптимизаций путём анализа различных вариантов использования процедуры. Информация о совмещениях, диапазоны изменения переменных и, как следствие, набор возможных оптимизаций зависят от контекста вызова процедуры. Рассмотрим следующий пример: в этом примере подпрограмма может изменять параметр Ъ или параметр а в зависимости от значения параметра с. Контекст вызова процедуры определяется набором параметров совмещений (alias) и информацией о возможных значениях переменных, которая генерируется в процессе протягивания констант. В данном примере оптимизирующий компилятор может принять решение о замене этой процедуры двумя следующими:
Будет произведена замена вызовов процедуры а на вызовы процедур а_1 и а_2 в зависимости от значения параметра с. Оговоримся, что такое решение принимается только в результате анализа контекста использования процедуры а, потому что возможны такие варианты программы, при которых такая оптимизация не будет возможной. Например: в первом случае явная разделимость процедуры а на две разные процедуры не даёт ничего, а во втором — просто не требуется (при условии, что это все вызовы а в программе), потому что используется только при с=1, что даёт возможность найти и удалить «мёртвый код» ветви с 1. Замена одной процедуры несколькими называется клонированием (procedure cloning). Предельный случай клонирования процедур (когда процедура клонируется столько раз, сколько вызывается) является аналогом прямой подстановки (inlining), которая применялась, например, в трансляторе АЛЬФА [38, 39]. Клонирование процедур уменьшает огрубление информации о поведении процедуры в конкретном контексте. Решение о клонировании принимается на основе анализа контекстов возможного использования и тела процедуры. Разработчики SUIF [61] утверждают, что таким образом они достигают точности прямой подстановки без излишнего увеличения размера анализируемого кода. В случае если выполняется частичная подстановка, решение о подстановке принимается на основе анализа графа вызовов. Подстановка применяется к висячим процедурам.
Аббревиатура SISAL образована от выражения: Streams and Iteration in a Single Assignment Language [19, 20]. Что буквально означает: «Язык однократного присваивания с потоками и итерациями». Sisal является функциональным языком однократного присваивания, отличительной чертой которого является наличие циклов и потоковых типов. Sisal не содержит императивных элементов, как и некоторые другие функциональные языки программирования (Clean [40], Miranda [41], Пифагор [42]). Особенностью таких языков является то, что они оперируют не с ячейками памяти, а со значениями. «Переменные» не могут быть переопределены, как и не могут быть не определены. Например, массив определяется один раз при создании, после чего невозможно добавить или изменить элемент, поменять границы массива. Такие операции осуществляются при помощи создании другого массива, основанного на предыдущем. Эта особенность позволяет не задавать строго порядок выполнения кода, а выполнять вызовы функций по готовности входных значений. Языки такого типа распараллеливаются более естественно. Но есть и минусы, связанные с этой особенностью. Например, иногда в реальных алгоритмах требуется заменить элемент в массиве, в этом случае приходится создавать новый массив с изменённым значением. Такой способ кажется нерациональным, но тесты производительности, проведённые на компиляторе языка Sisal OS С, показали, что за счёт оптимизаций на уровне компилятора производительность Sisal-программ может быть сравнима с производительностью программ, созданных на Fortran [21].
Первый стандарт языка Sisal был разработан в 1983 году [19] совместными усилиями Манчестерского университета, Ливерморской национальной лабораторией имени Лоренца, Колорадского университета и фирмы DEC. Язык разрабатывался как замена Fortran для вычислений на многопроцессорных системах, и был первоначально получен из функционального языка VAL [23] (Value-oriented Algorithmic Language) путём добавления рекурсии и бесконечных потоковых типов.
Можно выделить следующие основные этапы в развитии языка Sisal: Первый компилятор OSC (Optimizing Sisal Compiler) был разработан в 1989 году, он использовал стандарт языка Sisal 1.2 [20]. В 1990 году разработана параллельная версия OSC - POSC (Partitioning and Optimizing Sisal Compiler) [22]. В 1991 году был разработан стандарт языка Sisal 2.0 [24, 25], который так и не был реализован. В 1995 году разработан стандарт языка Sisal 90 [26, 27], который использовал идеи Fortran 90 и базировался на Sisal 1.2, а не на Sisal 2.0. В 2001 году разработкой языка и компилятора занялся Институт Систем Информатики им. А.П. Ершова (ИСИ СО РАН). Был представлен стандарт языка Sisal 3.0 [18]. В 2007 году опубликована новая версия языка Sisal 3.1 [35] В 2007 году разработан sourceo-source транслятор из языка Sisal в язык С#, ориентированный на последовательный код. В 2008 году компилятор получает параллельную реализацию по средствам библиотек System.Threading платформы .NET. [28]
Протягивание другой информации о значениях
Когда одно из значений, составляющих выражение, является неопределённым, рассмотренные алгоритмы не будут срабатывать, но в случае сокращения неизвестного значения, общее выражение может быть вычислено до исполнения программы. Рассмотрим следующий пример:
В этом примере избыточный код можно обнаружить при помощи прямой подстановки (forward substitution). Не сложно придумать пример, где такой способ не сработает:
В данном случае прямая подстановка в чистом виде ничего не даст, если только не будет скомбинирована с дополнительными алгоритмами оптимизации.
Для этого примера можно ограничиться алгоритмом протягивания значений, только в качестве значения использовать тройку связанная переменная, операция связи, константа. Это очень похоже на способ описания областей массивов при помощи триплетов, с той разницей, что здесь в качестве связанных переменных выступают не итераторы циклов, а просто некоторые переменные программы. В этом случае информация распространится следующим образом:
Оценив действие алгоритма не сложно модифицировать пример так, чтобы программа сохранила свой смысл, но алгоритм не срабатывал:
В этом случае уже не получится обойтись этим же алгоритмом с модифицированным представлением данных, потребуется анализ с учётом пути исполнения. Отметим также, что этим примером случаи несрабатывания алгоритма не ограничиваются; значение может зависеть от двух или трёх переменных, и в процессе его вычисления могут встречаться произвольные функции.
Сформулируем общий критерий: подстановку константы можно совершить на стадии компиляции тогда и только тогда, когда может быть однозначно вычислен статический срез по переменной подстановки. Здесь срез — это подмножество операторов и выражений исходной программы, которые прямо или косвенно влияют на значения, вычисляемые в точке критерия среза (в нашем случае это значения, для которых требуется определить возможность их подстановки на стадии компиляции), но не обязательно составляют исполняемую программу [3].
Становится ясно, что для более точного поиска инвариантных значений можно воспользоваться алгоритмами вычисления минимального статического среза.
Для построения однопроцедурных статических срезов программ задача сводится к нахождению всех достижимых вершин из точки критерия среза в графе программных зависимостей, что является верным и для графа IR2, поскольку операторы, вычисляемые в процессе получения значения, соответствуют операторным вершинам, достижимым при прохождении графа IR2 в направлении, обратном выполнению вычислений.
Построение статического среза программы, представленной в виде графа программных зависимостей, является задачей линейной сложности. Срез должен быть вычислен для каждого значения в программе, после чего потребуется дать заключение о возможности его вычисления до исполнения программы. Таким образом, сложность алгоритма 0(V (N+D)), где V количество значений, для которых требуется произвести вычисление среза, а N и D количество вершин и рёбер графа IR2. В случае, когда срез не является однозначно вычислимым, представление возможных значений в виде среза не является удобным для других алгоритмов оптимизации и вряд ли может быть использовано повторно.
Как и в случае протягивания констант, сам алгоритм анализа является внешним по отношению к способу, при помощи которого производится описание областей массивов. В компиляторе Sisal было внедрено новшество, связанное с тем, что описываются не только области значений индексных переменных, но и области возможных принимаемых значений для элементов массива. Таким образом, анализ массивов становится естественным обобщением анализа скалярных величин, рассмотренного в предыдущем разделе.
Как было отмечено в обзорной части данной работы, массив можно представить как скаляр, если не учитывать индексы. К сожалению, такой метод не подходит для исследования значений, которые принимают ячейки массива, поскольку результаты действия простых операций (присваивание, сложение, вычитание) нельзя будет определить аналогичным образом. Например, если изменяется переменная — компилятор помечает её как изменяемую, то же самое можно сделать и с массивом при изменении любого из его элементов, но если к константе прибавили константу — в результате получается опять константа, что нельзя обобщить на произвольный элемент массива. Возможности применения анализа массивов, как и анализа переменных для языков однократного присваивания отличаются от возможностей в императивных языках.
Условно разделим анализ на три части: 1. Анализ областей чтения 2. Анализ областей записи 3. Анализ значений компонент массива Анализ областей чтения может быть направлен на оптимизацию пересылок данных при параллельном вычислении в системах с распределённой памятью. Исследование областей записи массивов вместе с анализом областей чтения для языка однократного присваивания имеет смысл проводить с целью поиска мёртвого кода или ошибок в программе. У анализа значений компонент массива цель схожа с протягиванием констант, это выделение избыточного кода, оптимизация ошибочных значений и получение информации для других алгоритмов анализа. В практической реализации интерфейс класса анализа аналогичен интерфейсу для протягивания констант. Отличия алгоритма анализа заключаются в том, что он рассматривает циклы в целом и вместо добавления литералов, когда возможное принимаемое значение единственное — изменяет структуру циклов либо удаляет их.
Влияние оптимизирующих алгоритмов
Для того, чтобы показать как влияют описанные алгоритмы оптимизации на распараллеливание программы, докажем несколько утверждений.
Теорема 25. Удаление недостижимых вершин не может привести к увеличению времени исполнения программы.
Доказательство. Для последовательного исполнения это очевидно — большее количество операций приводит к большему времени исполнения, но может ли это повлиять на минимальное время исполнения программы в условиях параллельного исполнения. Обратимся к теории временных развёрток программы, которая была использована в предыдущем параграфе. Рассмотрим начальный граф G и граф G без недостижимых из конечных данных вершин. Очевидно, что в графе G максимальное время развёртки rnaxftj), относится к выходным данным, поскольку в противном случае это бы означало, что в графе существует некоторая вершина, время развёртки для которой больше, чем для конечных данных, притом она влияет на их вычисление.
Скопируем значения развёртки из графа G в граф G и покажем, что такая развёртка будет корректной для графа G . На значение t,- в некоторой вершине могут влиять только те вершины, которые связаны с ней. Это значит, что недостижимые вершины не могут влиять на значение развёртки в некоторой вершине. Соответственно, отсутствие этих вершин также не может влиять на значение развёртки. Получаем, что такая развёртка будет удовлетворять правилам и максимальное время maxfti) для графа G будет меньше или равно времени для графа G.
Определение 20. Будем говорить, что граф G потока данных добавлен в граф G и в результате получен граф G", если граф G" содержит все вершины и дуги графов G и G. Для любой дуги из G", не принадлежащей к G или G , её начальная вершина принадлежит G, а конечные принадлежит к вершинам S(G ), отвечающим за начальные данные для графа G\ Лемма 1. После добавления в граф G с минимальной развёрткой tt графа G с развёрткой t) результирующая развёртка графа G" t"i будет удовлетворять следующему условию: max (t"i) maxft +maxft j).
Доказательство. В случае если G" не содержит новых дуг (не принадлежащих G или G ) max (t"j) — min(max(t,), max(t )). Если есть новое ребро из G в S(G ) тогда максимальная развёртка для вершин G в графе G" может увеличиться на t,Si, следовательно, для max(t"i) maxftJ-Si+maxft J, а так как Sj 0 — получаем что утверждение верно. Теорема 26. Вынос инвариантных вычислений за пределы цикла не может привести к увеличению времени исполнения программы в условиях параллельных вычислений, если каждая отдельная итерация цикла исполняется последовательно. Доказательство. В случае последовательного исполнения внутри итерации цикла выполнение некоторых инвариантных вычислений будет занимать время t, которое будет добавляться к общему времени выполнения итерации, а в случае выноса вычислений время в соответствии с леммой 1 не может увеличиться больше, чем на время исполнения этого участка кода в условиях параллелизма. Это время меньше или равно времени исполнения этого кода последовательно. Так как в компиляторе Sisal не производится распараллеливания на уровне команд, а отдельно взятая итерация цикла всегда исполняется последовательно — преобразование может быть использовано без ограничений. Теорема 27. Преобразование слияния циклов не может увеличить время исполнения программы в условиях параллелизма. Доказательство. Слияние циклов соответствует добавлению графа тела одного цикла, к графу тела другого. По лемме 1 такое преобразование не может увеличить время исполнения. Исследования макропараллелелизма программы, представленной в виде графа вычислений, направлены на выделение поверхностей постоянной развёртки. Операции, относящиеся к одному уровню развёртки, могут быть выполнены параллельно. Циклические конструкции языка SISAL отличаются от тех, что мы привыкли иметь в императивных языках программирования наличием механизма свёрток. Это добавляет некоторые дополнительные сложности, но и позволяет выделить параллельные слои внутри одного цикла. На рисунках 2.17 и 2.18 изображены развёрнутые циклы For All (цикл с генератором диапазона) и For Repeat (цикл с постусловием), состоящие из 4-х итераций. Стрелками изображены дуги передачи данных. Видно, что всегда одновременно с вычислением функции редукции можно начинать вычислять функции следующей итерации. Это свойство может быть полезно при распараллеливании на низком уровне для небольшого количества вычислителей. В рамках данной работы распараллеливание было ориентировано на платформу SMP, поэтому возможность конвейерного исполнения циклов на низком уровне была рассмотрена только теоретически. Во второй главе были рассмотрены анализ и преобразования потоковой программы, выраженной в терминах IR2. Для алгоритмов анализа и оптимизации приведены оценки сложности, доказаны свойства. Как было доказано, особенности модели параллельного исполнения, а именно тяжеловесные нити, позволяют производить некоторые преобразования без возможности ухудшить характеристики кода. А такие преобразования как удаление недостижимых вершин и слияние циклов будут всегда не ухудшать временные характеристики программы вне зависимости от модели параллельного исполнения. В этой главе кратко описан компилятор Sisal, в рамках которого были внедрены алгоритмы из прошлой главы. Результаты тестирования оптимизаций представлены в виде графиков и числовых данных. Компилятор Sisal, описанный в этой работе существует в виде Sourceo-Source транслятора из Sisal 3.2 в С#. В дальнейшем планируется трансляция в язык IL внутреннего представления платформы .NET.
