Докладчик: Шаповалов Василий Николаевич




Скачать 52.03 Kb.
НазваниеДокладчик: Шаповалов Василий Николаевич
Дата22.01.2013
Размер52.03 Kb.
ТипДоклад

РАСПАРАЛЛЕЛИВАНИЕ С ПОМОЩЬЮ SSA-ФОРМЫ ДЛЯ МАССИВОВ.



В.Н. Шаповалов.

Докладчик: Шаповалов Василий Николаевич

Южный Федеральный Университет, г. Ростов-на-Дону.

тел. +79045045045 e-mail Vasiliy.Shapovalov@gmail.com

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

Форма доклада: стендовый доклад


Abstract: В данной работе предпринято исследование возможности расширения области действия формы со статически однократным присваиванием (static single assignment form [1,2]), или SSA-форма) со скалярных переменных на массивы. Показано, что преобразование программы в SSA-форму способствует оптимизации. Разработано преобразование «удаление полумёртвого кода». Показано, что удаление полумёртвого кода способствует распараллеливанию некоторых циклов.

SSA-форма для массивов.


Можно расширить область действия SSA-формы на вхождения массивов с константными индексами. Действительно, если участок кода содержит вхождения массивов только с константными индексами, то пара <массив, константный индекс> семантически не отличается от переменной.


Пусть L – цикл с фиксированными границами, шагом 1 и единственной точкой входа. Например, цикл for в языке Pascal. Если индексные выражения переменных в теле этого цикла зависят только от констант и счётчика цикла, то можно построить SSA-форму раскрутки этого цикла. В некоторых случаях можно узнать, какой будет SSA-форма раскрутки цикла, не строя самой раскрутки.


Дадим определение пси-функции. I – подмножество Z. ΨI(x,y) возвращает x на тех итерациях, на которых счётчик цикла i∈I, и возвращает y на всех остальных. При раскрутке пси-функции заменяются на один из своих аргументов.


Пусть есть цикл L, содержащий вхождения массивов. Можно доказать, что при некоторых ограничениях существует цикл L1, содержащий пси-функции, раскрутка которого является SSA-формой раскрутки цикла L. Будем называть цикл L1 SSA-формой цикла L.

SSA-форма тесного гнезда циклов.



Есть тесное гнездо из n канонических циклов. Назовём его гнездом циклов с регулярными индексными выражениями, если оно обладает следующим свойством:

Для каждого массива A, имеющего в теле цикла вхождения вида A[ind1][ ind2]…[indn] выполняется:

indj не содержит переменных кроме, может быть, счётчика цикла ij

счётчики циклов ij попарно различны

indj линейно относительно ij и indj =Cj*ij+dj

Есть алгоритм построения SSA-формы гнезда циклов с регулярными индексными выражениями, базирующийся на алгоритме из [1].


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

SSA-граф в качестве вершин имеет вхождения, а дуги идут от генератора к использованиям. Длина дуги SSA-графа есть число итераций, проходящих от исполнения генератора до использования.

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

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

Есть набор преобразований, которые часто реализуют с помощью SSA-формы – протягивание констант, удаление мёртвого кода, подстановка вперёд, переименование переменных [2]. Все они обычно не работают с выражениями, содержащими массивы. С помощью вышеописанной SSA-формы область применимости этих преобразований расширяется. С помощью таблицы финальных значений легче выполняются преобразования, меняющие структуру цикла. Одно из них – предлагаемое в данной работе «удаление полумёртвого кода».

Удаление полумёртвого кода.


Для определения понятия полумёртвого кода вернёмся к раскрутке цикла. Оператор в теле цикла при раскрутке порождает несколько своих копий. Если в теле цикла оператор не является мёртвым кодом, но при раскрутке часть его копий становится мёртвым кодом, то назовём этот оператор полумёртвым кодом.

Приведём алгоритм нахождения полумёртвого кода для случая единственного цикла.

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

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

Алгоритм нахождения полумёртвого кода:


0. Длинна дуги SSA-графа – вектор от генератора до использования. Vol(gi) – число ячеек, записываемых генератором gi. Дуги и вершины SSA-графа будем помечать натуральными числами. F(gi) – пометка вершины. MaxF(gi) – максимальная пометка дуги, исходящей из gi.

Все дуги SSA-графа непомеченные. Все вершины непомеченные. G – множество генераторов gi, у которых Vol(gi) не больше 10.

1. M={ gi | gi - финальный генератор из G, из которого в SSA-графе не выходит ни одной непомеченной дуги }. Это генераторы, которые записывают значения массива, которые в самом цикле не используются. Если таких нет, остановка алгоритма.

2. По таблице финальных значений каждый генератор из M пометить числом Vol(gi). Пометить все дуги, ведущие в правую часть генератора gi, числом F(gi) + длинна дуги. Если это число больше 10, убрать пометку.

3. M’={ g’i | g’i - финальный генератор из G, из которого в SSA-графе не выходит ни одной непомеченной дуги }\M. Если таких нет, остановка алгоритма.

4. Каждый генератор из M’ пометить числом max(Vol(g’i), MaxF(g’i)). Пометить все дуги, ведущие в правую часть генератора g’i, числом F(g’i) + длинна дуги. Если это число больше 10, убрать пометку.

5. M=M объединить с M’. Перейти к шагу 3.


Этот алгоритм можно обобщить на случай гнезда циклов.


На выходе алгоритма имеем множество M. Для удаления мёртвого кода ищем kmax - максимальную пометку генераторов из M. Отщепляем последние kmax итераций и удаляем генераторы из M.


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


Пример. Оптимизация непараллельного цикла.


for(int i=0; i
{

A[i+4]=expr1(B,C,D,…);

A[i]=expr2(B,C,D,…);

}


В этом цикле генератор A[i+4] – полумёртвый код. На каждой итерации, кроме последних четырёх, значение, записанное им, перезаписывается генератором A[i].

Более того, этот цикл непараллельный из-за выходной зависимости между генераторами A[i] и A[i+4]. Обычное решение в таких случаях заключается в разделении цикла на два параллельных:


for(int i=0; i
{

A[i+4]=expr1(B,C,D,…);

}

for(int i=0; i
{

A[i]=expr2(B,C,D,…);

}


Но это не лучшая оптимизация. Удаление полумёртвого кода сгенерирует код почти в два раза более быстрый.

Фрагмент программы после удаления полумёртвого кода:


for(int i=0; i
{

A[i]=expr2(B,C,D,…);

}

for(int i=N-4; i
{

A[i+4]=expr1(B,C,D,…);

A[i]=expr2(B,C,D,…);

}


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


Конец примера.

Список литературы


  1. “Practical Improvements to the Construction and Destruction of Static Single Assignment Form”, Preston Briggs, Keith D. Cooper, Timothy J. Harvey, L. Taylor Simpson, 1998

  2. “Engineering a Compiler.” Cooper, Keith D.; & Torczon, Linda. (2003). Morgan Kaufmann

Похожие:

Докладчик: Шаповалов Василий Николаевич iconСоздание детектора на основе сцинтилляционных монокристаллов СаМоО
Его e-mail и телефон. Корноухов Василий Николаевич,, тел. 129-94-04, 54-04 (м)
Докладчик: Шаповалов Василий Николаевич icon"актуальные проблемы гуманитарных и социальных наук" Владивосток, 27 апреля 2012 г. Оргкомитет
Докладчик – Крадин Николай Николаевич, д и н., профессор, зав каф всеобщей истории, археологии и антропологии двфу, член-корреспондент...
Докладчик: Шаповалов Василий Николаевич iconСписок новых поступлений плоскопечатной литературы, поступившей в фонд крбс IV квартал 2008 г. 2 Естественные науки 26. 89
П28 Песков, Василий Михайлович. Все это было / Василий Песков; рис. С. Любаева. – Москва : терра : Книжный клуб, 2007. – 398, [2]...
Докладчик: Шаповалов Василий Николаевич iconВасилий Александрович Токарев П. Михайлов Игорь Львович Андреев Вячеслав Николаевич Козляков День народного единства: биография праздника
Книга посвящена драматичным событиям российской истории XVII в. – Смутному времени. На основе широкого круга источников и литературы...
Докладчик: Шаповалов Василий Николаевич iconОсновной докладчик семинара д э. н., проф. Ргтэу, чл корр. Раен владимир Николаевич Крючков представил тему «Стратегическая Флатландия», в рамках которой
Крючков описал китайскую систему стратагем, предложил переработанный для России калькулятор стратагем и сформулировал основные задачи...
Докладчик: Шаповалов Василий Николаевич iconЛ. Ф. Кабо в книге «Жил на свете учитель» (М., Знание, 1970 г.)
Пахомов Василий Николаевич, Лукина Анна Иосифовна, Яковлев Еремей Тимофеевич, Никифорова Зинаида Ивановна, Соколов Дмитрий Дмитриевич,...
Докладчик: Шаповалов Василий Николаевич iconГубернатор Василий Голубев встретился с членами Совета Федерации Федерального Собрания РФ и депутатами Государственной Думы пятого созыва от Ростовской области
Открывая встречу, Василий Голубев отметил большой потенциал депутатского корпуса
Докладчик: Шаповалов Василий Николаевич iconВасилий Васильевич Антипов, д-р техн наук, профессор; Владимир Юрьевич Бобрович, д-р техн наук, профессор; Герман Николаевич Сус; Наталья Петровна Ушакова
Целью создания иус является внедрение единой системы внутренних информационных коммуникаций платформы, а также обеспечение автоматизированного...
Докладчик: Шаповалов Василий Николаевич iconУважаемый Василий Юрьевич!
Василий Юрьевич Голубев по обеспечению устойчивого социально-экономического развития области, активизации инвестиционной деятельности,...
Докладчик: Шаповалов Василий Николаевич iconВасилий Аксенов Звездный билет ocr dmitry A. Zakheim
«Василий Аксенов. Звездный билет: Авторский сборник»: Изографус, эксмо пресс; М.; 2002
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница