Презентация Теория компиляторов. Часть II. Лекция 3. Общие методы распараллеливания кода онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Теория компиляторов. Часть II. Лекция 3. Общие методы распараллеливания кода абсолютно бесплатно. Урок-презентация на эту тему содержит всего 28 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Теория компиляторов. Часть II. Лекция 3. Общие методы распараллеливания кода
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:28 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:673.50 kB
- Просмотров:66
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№4 слайд
![Этапы . Формирование модели](/documents_6/42cf02fedf98339c03d619464a03ed6f/img3.jpg)
Содержание слайда: Этапы
1. Формирование модели макроуровня. Объект – исходный поток инструкций.
1.1. Расстановка меток.
1.2. Построение управляющего графа.
1.3. Планирование трасс.
1.4. Преобразование трасс.
1.5. Формирование линейных участков.
2. Формирование модели микроуровня. Объект – линейные участки.
2.1. Построение графа зависимости по данным (ГЗД).
2.2. Преобразование ГЗД к ярусно-параллельной форме.
2.3. Построение графа конфликтов
2.3. Распределение регистров.
№6 слайд
![Расстановка меток Для каждой](/documents_6/42cf02fedf98339c03d619464a03ed6f/img5.jpg)
Содержание слайда: Расстановка меток
Для каждой тетрады определяются ее атрибуты, относящие тетраду к типу «развилка», «сток», «плохая инструкция».
«Плохая инструкция» (операции ввода-вывода, вызовы подпрограмм, операции синхронизации и т.п.)
Если тетрада - операция условного перехода, то это – «развилка».
Если адрес (номер) тетрады используется где-либо в качестве адреса перехода, то это – «сток».
Тетрада может иметь несколько подобных атрибутов (быть и «развилкой», и «стоком»).
№7 слайд
![Построение управляющего графа](/documents_6/42cf02fedf98339c03d619464a03ed6f/img6.jpg)
Содержание слайда: Построение управляющего графа
УГ содержит описание линейных блоков программы
УГ - орграф, вершины которого - линейные участки программы, а дуги указывают пути передачи управления.
УГ имеет единственную входную и единственную выходную вершину. Каждая вершина имеет не более двух потомков.
№8 слайд
![Планирование трасс Хорошие](/documents_6/42cf02fedf98339c03d619464a03ed6f/img7.jpg)
Содержание слайда: Планирование трасс
«Хорошие» линейные участки - длинные
«Плохие» линейные участки: короткие или содержащие «плохие» операции.
"Плохие" инструкции:
вызовы внешних подпрограмм;
возвраты из подпрограмм;
операции ввода-вывода;
операции синхронизации по времени;
переходы по вычисляемым адресам (т.к. адрес перехода неизвестен заранее, то оптимизировать нельзя);
операции с данными, находящимися по вычисляемым адресам (невозможно проследить зависимости по данным на этапе трансляции).
№9 слайд
![Эвристики Предсказание на](/documents_6/42cf02fedf98339c03d619464a03ed6f/img8.jpg)
Содержание слайда: Эвристики
Предсказание на основе истории ветвлений. Сбор статистики об исходах операций ветвления и построение на ее основе строится предположение о результате выполнения текущей операции.
Предсказание на основе пробных прогонов программы. Для этого производится имитация выполнения программы на одном или нескольких наборах данных. Собирается статистика. Недостаток очевиден: метод работает лишь при определенных обстоятельствах и исходных данных.
Использование эвристик выбора доминирующей ветви.
Избегание «плохих» инструкций.
Условия с указателями. Обычно справедливы условия
PtrNULL
Ptr1Ptr2
if((ptr=malloc(…))!=NULL) …
for(p=p0;p!=NULL;p=p–>next) …
Эвристика исполнения циклов. Если при ветвлении одна из ветвей содержит цикл, то обычно именно она и будет доминировать. По статистике исполнение циклов занимает до 90% времени выполнения программы в целом.
Эвристика направления ветвления. Возврат назад более вероятен (высока вероятность неявного цикла с постусловием).
Предсказание по коду операции:
при сравнении чисел с плавающей точкой более вероятно неравенство;
отрицательные числа менее вероятны.
№12 слайд
![Линейные участки ЛУ -](/documents_6/42cf02fedf98339c03d619464a03ed6f/img11.jpg)
Содержание слайда: Линейные участки
ЛУ - последовательность инструкций, у которой имеется вход и два выхода.
ЛУ заканчивается тогда, когда осуществляется переход или ставится метка.
ЛУ – это основной объект оптимизации.
Чем длиннее ЛУ, тем больше возможностей для параллельных вычислений.
ЛУ ГЗД ЯПФ распределение регистров {VLIW}.
№13 слайд
![Граф зависимости по данным](/documents_6/42cf02fedf98339c03d619464a03ed6f/img12.jpg)
Содержание слайда: Граф зависимости по данным
Пусть имеется участок программы – список инструкций A=(a1,a2,…,an)
Каждая инструкция ai представлена в тетрадной форме ai=(OPi, Ii(1), Ii(2), Ri)
ГЗД участка A - граф (A,V) с вершинами aiA и дугами (ai, aj) V
V={(ai, aj): i<j, (Ri=Ij)(Rj=Ii)(Ri=Rj)=true}
№15 слайд
![Ярусно-параллельная форма .](/documents_6/42cf02fedf98339c03d619464a03ed6f/img14.jpg)
Содержание слайда: Ярусно-параллельная форма
1. Построение дерева
Для преобразования ГЗД к дереву (лесу бинарных деревьев) используется дублирование переменных. Дублирование производится для вершин
deg–(aiA)>1
В результате вершина дублируется deg–(ai)–1 раз
Пример. S = p*(p–a)*((p–b)*(p–c))
№17 слайд
![Построение ЯПФ ЯПФ эта форма](/documents_6/42cf02fedf98339c03d619464a03ed6f/img16.jpg)
Содержание слайда: Построение ЯПФ
ЯПФ – эта форма разметки дерева. В ЯПФ каждой вершине графа приписывается некое число – ранг (номер яруса). Вершины, имеющие один ранг (находящиеся на одном ярусе) могут исполняться одновременно.
Пусть ГЗД оперирует двумя видами тетрад (вершин) – полными тетрадами вида
T4=(OP, A1, A2, R)
и неполными (вырожденными) тетрадами вида
T3=(OP, A, ,R)
(+,A,B,C) -- C:=A+B
(*,A,B,C) -- C:=A*B
(:=,A, , C) -- C:=A
Представление графа ЯПФ
Граф ЯПФ – множество вершин-структур
№18 слайд
![Алгоритм построения ЯПФ Вход](/documents_6/42cf02fedf98339c03d619464a03ed6f/img17.jpg)
Содержание слайда: Алгоритм построения ЯПФ
Вход: поток тетрад {T}
Выход: граф G в ярусно-параллельной форме
Очистить список вершин графа G
Цикл по всем тетрадам T
Выбрать очередную тетраду T.
Если тип тетрады T соответствует T4 (T=(OP, A1, A2, R)), то
-- Анализируем аргумент A1.
Если ГЗД нет элемента с именем A1, то -- добавляем новый элемент g1 в G
g1.name := A1;
g1.rank:= 0;
g1.left := NULL;
g1.right := NULL.
добавить элемент g1 в G
иначе запомнить элемент g1 (g1.name=A1)
-- Анализируем аргумент A2.
Если ГЗД нет элемента с именем A2, то -- добавляем новый элемент g2 в G
g2.name := A2;
g2.rank:= 0;
g2.left := NULL;
g2.right := NULL.
добавить элемент g2 в G
иначе запомнить элемент g2 (g2.name=A2)
-- Анализируем аргумент R.
Найти элемент g3 с максимальным рангом, использующий R в качестве аргумента A1 или A2.
Найти элемент g4 максимального ранга с именем R.
Выбираем максимальный из рангов среди найденных элементов gi: rmax = max(g1.rank, g2.rank, g3.rank, g4.rank)
(при этом если какой-либо из элементов gi не был найден в G, то считаем его ранг равным нулю)
Помещаем элемент R на ярус со значением rmax+1.
КонецЕсли
Если тип тетрады T соответствует T3=(OP, A,, R), то
-- Далее все аналогично, только вместо двух анализируется один аргумент – операнд A.
КонецЕсли
КонецЦикла
№21 слайд
![Оптимальная загрузка](/documents_6/42cf02fedf98339c03d619464a03ed6f/img20.jpg)
Содержание слайда: Оптимальная загрузка регистров
Регистров обычно не хватает
Сведем задачу распределения регистров к задаче раскраски графа:
Создать граф, вершинами которого являются данные, а дуги определяют пересечение времен жизни (одновременность использования данных).
Раскрасить граф – приписать каждой вершине графа свой цвет – используемый регистр.
Количество цветов (красок) – это и есть количество регистров.
Прежде следует определиться с тем, какие команды (вершины) вообще могут конфликтовать друг с другом из-за регистров.
№22 слайд
![Граф конфликтов Граф](/documents_6/42cf02fedf98339c03d619464a03ed6f/img21.jpg)
Содержание слайда: Граф конфликтов
Граф конфликтов – это неориентированный граф, вершинами которого являются используемые переменные (данные), а ребра соединяют вершины с пересекающимися временами жизни. Строить граф конфликтов мы будем, опираясь на ЯПФ.
Одновременно "живут" (сосуществуют) те вершины, которые находятся на одном ярусе. Кроме того:
сохраняются связи, полученные в ЯПФ
учитываются связи с вершинами предыдущего ярусами.
Определяется связь со всеми вершинами, которые находятся выше и имеют потомков ниже или на том же уровне, что и текущая:
Для вершины ak строится связь (ak, ai) с вершиной ai такой, что:
L(ai)<L(ak) и aj: L(aj)L(ak)}
№26 слайд
![Раскраска графа Нахождение](/documents_6/42cf02fedf98339c03d619464a03ed6f/img25.jpg)
Содержание слайда: Раскраска графа (2)
Нахождение оптимальной раскраски – это NP–полная задача. Поэтому чаще всего реализуют алгоритмы поиска субоптимального решения.
Последовательная раскраска
Пусть дано упорядоченное множество вершин графа v1,…,vn.
вершине v1 приписываем цвет c1;
если подграф H(v1,…,vi–1), порожденный вершинами v1,…,vi–1 k'–раскрашен, ki–1, то вершина vi получает цвет cm, где mk+1, т.е. цвет с наименьшим номером, не встречающимся на смежных с vi вершинах.
Число цветов k при этом заранее не фиксируется. Этот алгоритм дает точную k–раскраску только для полных k–дольных графов.
k–дольным называется граф, множество вершин которого можно разбить на k непересекающихся подмножеств X1,…,Xk так, что никакие 2 вершины из подмножества Xi, i=1,..,n, не смежны.
k–дольный граф называется полным k–дольным, если каждая вершина из множества Xi смежна с каждой вершиной из Xj, ij.
№27 слайд
![Стратегии последовательных](/documents_6/42cf02fedf98339c03d619464a03ed6f/img26.jpg)
Содержание слайда: Стратегии последовательных раскрасок
1. НП–стратегия («Наибольшие–Первыми»). Упорядочить вершины v1,…,vn по убыванию их степеней связности, т.е. сначала раскрашиваются вершины с максимальными степенями.
В данном случае упорядочивание может выглядеть так: {2,1,3,4,5,6}. Поэтому раскраску начнем с вершины V1=2.
2. ПН–стратегия («Последними–Наименьшие»)
для n=|V| в качестве vn выбирается вершина минимальной степени в G;
для i=n–1,n–2,…,2,1 в качестве vi выбирается вершина минимальной степени в подграфе H(V\{vn,…,vi+1}).
Выберем вершину минимальной связности: V6=6. Далее рассматриваем граф, где нет 6-й вершины. В этом графе V5=5. Далее в оставшемся графе определим V4=4, затем V3=1, V2=2 и V1=3. Итого: {3,2,1,4,5,6}
№28 слайд
![Итоговая последовательность .](/documents_6/42cf02fedf98339c03d619464a03ed6f/img27.jpg)
Содержание слайда: Итоговая последовательность
1. Формирование модели макроуровня. Объект – исходный поток инструкций.
1.1. Расстановка меток.
1.2. Построение управляющего графа.
1.3. Планирование трасс. Эвристики.
1.4. Преобразование трасс.
1.5. Формирование линейных участков.
2. Формирование модели микроуровня. Объект – линейные участки.
2.1. Построение графа зависимости по данным (ГЗД).
2.2. Преобразование ГЗД к ярусно-параллельной форме.
2.3. Построение графа конфликтов
2.3. Распределение регистров.
Скачать все slide презентации Теория компиляторов. Часть II. Лекция 3. Общие методы распараллеливания кода одним архивом:
Похожие презентации
-
Методы улучшения алгоритмов сортировок. Лекция 7
-
Словарные методы сжатия. Лекция 3
-
Статистические методы сжатия. Лекция 2
-
Общие сведения о языке С. Лекция 2. 1
-
Элементы теории языков. Лекция 24
-
Основные элементы класса: поля, методы, конструкторы, декструкторы, свойства. Лекция 3
-
Организация пользовательских подпрограмм, методов класса. Лекция 21
-
Методы и системы программирования. Основные принципы объектно-ориентированного программирования. Лекция 5
-
Теория алгоритмов. Сортировка массива. (Лекция 17)
-
Оптимизации генерации кода в JIT-компиляторе виртуальной машины Java