Содержание
- 2. Теория компиляторов-2. Л.3 Общая схема распараллеливания программы Необходимо преобразовать линейный список инструкций [w1,w2,…,wn] в список широких
- 3. Теория компиляторов-2. Л.3 1. Управляющий граф программы Вершины–источники - 2, 5 и 10. Стоки-вершины 5 и
- 4. Теория компиляторов-2. Л.3 Этапы 1. Формирование модели макроуровня. Объект – исходный поток инструкций. 1.1. Расстановка меток.
- 5. Теория компиляторов-2. Л.3 Структура ПК
- 6. Теория компиляторов-2. Л.3 Расстановка меток Для каждой тетрады определяются ее атрибуты, относящие тетраду к типу «развилка»,
- 7. Теория компиляторов-2. Л.3 Построение управляющего графа УГ содержит описание линейных блоков программы УГ - орграф, вершины
- 8. Теория компиляторов-2. Л.3 Планирование трасс «Хорошие» линейные участки - длинные «Плохие» линейные участки: короткие или содержащие
- 9. Теория компиляторов-2. Л.3 Эвристики Предсказание на основе истории ветвлений. Сбор статистики об исходах операций ветвления и
- 10. Теория компиляторов-2. Л.3 Пример В первую очередь, избегаем плохих инструкций (4). Если бы (4) была хорошей
- 11. Теория компиляторов-2. Л.3 Преобразование трасс Метод дублирования остатка Вход в трассу Выход из трассы Объем инструкций
- 12. Теория компиляторов-2. Л.3 Линейные участки ЛУ - последовательность инструкций, у которой имеется вход и два выхода.
- 13. Теория компиляторов-2. Л.3 Граф зависимости по данным Пусть имеется участок программы – список инструкций A=(a1,a2,…,an) Каждая
- 14. Теория компиляторов-2. Л.3 Пример ГЗД S = p*(p–a)*((p–b)*(p–c)) 1. (-, p, a, T1) 2. (-, p,
- 15. Теория компиляторов-2. Л.3 Ярусно-параллельная форма 1. Построение дерева Для преобразования ГЗД к дереву (лесу бинарных деревьев)
- 16. Теория компиляторов-2. Л.3 Ярусно-параллельная форма Пример. a=(b+c)*(c+d)*(b+d)
- 17. Теория компиляторов-2. Л.3 Построение ЯПФ ЯПФ – эта форма разметки дерева. В ЯПФ каждой вершине графа
- 18. Теория компиляторов-2. Л.3 Алгоритм построения ЯПФ Вход: поток тетрад {T} Выход: граф G в ярусно-параллельной форме
- 19. Теория компиляторов-2. Л.3 Пример (+,a,b,c) -- c:=a+b (+,a,b,c) -- c:=a+b (+,a,b,b) -- b:=a+b (+,d,e,f) -- f:=d+e
- 20. Теория компиляторов-2. Л.3 Распределение регистров 11 регистров Для двухпортового регистрового файла из ЯПФ формируем: Cw1: (load
- 21. Теория компиляторов-2. Л.3 Оптимальная загрузка регистров Регистров обычно не хватает Сведем задачу распределения регистров к задаче
- 22. Теория компиляторов-2. Л.3 Граф конфликтов Граф конфликтов – это неориентированный граф, вершинами которого являются используемые переменные
- 23. Теория компиляторов-2. Л.3 Пример a:=b+c; k:=a*d e:=b+f m:=b*g Без раскраски – 9 регистров R0-R8
- 24. Теория компиляторов-2. Л.3 Построение графа конфликтов Далее - раскраска графа Использованы краски с именами 0-4. Итого
- 25. Теория компиляторов-2. Л.3 Раскраска графа (1) Гипотеза о четырех красках: Хроматическое число любого планарного графа не
- 26. Теория компиляторов-2. Л.3 Раскраска графа (2) Нахождение оптимальной раскраски – это NP–полная задача. Поэтому чаще всего
- 27. Теория компиляторов-2. Л.3 Стратегии последовательных раскрасок 1. НП–стратегия («Наибольшие–Первыми»). Упорядочить вершины v1,…,vn по убыванию их степеней
- 29. Скачать презентацию