Читать фрагмент

книга

Оптимизирующие преобразования программ

В учебном пособии рассматриваются ускоряющие (оптимизирующие и распараллеливающие) преобразования программ. Представленные преобразования иллюстрируются многочисленными примерами преобразований программ языка С. Тематика предлагаемого материала актуальна, поскольку популярные промышленные оптимизирующие компиляторы плохо оптимизируют код. Разрабатываемые программы зачастую используют около 1 % пиковой производительности процессора – это притом, что быстродействие во многих приложениях имеет существенное значение. По этой тематике издано много книг и обзорных статей, часть из которых представлена в списке литературы. Данное учебное пособие отличается строгостью формулировок и обоснований представленных преобразований, основное внимание уделяется преобразованиям циклов.Предназначено для студентов направлений подготовки «Прикладная математика и информатика» и «Фундаментальная информатика и информационные технологии».

Форматы: PDF

Издательство: Южный федеральный университет

Год: 2025

Место издания: Ростов-на-Дону, Таганрог

ISBN: 978-5-9275-4947-4

Страниц: 124

Артикул: 115950

Возрастная маркировка: 16+

Электронная книга

183 ₽

Купить и скачать

Содержание

Содержание книги "Оптимизирующие преобразования программ "

ВВЕДЕНИЕ

1. СВЕДЕНИЯ ИЗ ТЕОРИИ ГРАФОВ

2. ПРЕОБРАЗОВАНИЯ ПРОГРАММ

2.1. Программные зависимости и базовые преобразования

2.1.1. Модель рассматриваемых программ

2.1.2. Управляющий граф программы

2.1.3. Информационная зависимость и граф информационных связей

2.1.4. Граф зависимостей по данным

2.1.5. Решётчатый граф программы

2.2. Базовые преобразования программ

2.2.1. Базовые понятия о преобразованиях программ

2.2.2. Пустой оператор. Удаление и вставка операторов

2.2.3. Удаление мёртвого кода. Поиск и удаление недостижимых и неиспользуемых по управлению операторов

2.2.4. Удаление оператора (заголовка) цикла

2.2.5. Удаление условных операторов

2.2.6. Приведение выражения к стандартному виду («приведение подобных»)

2.3. Преобразования линейных участков программы

2.3.1. Перестановка фрагментов (блоков) программы

2.3.2. Подстановка вперёд

2.3.3. Вынос вычисления выражений и замена общих подвыражений

2.4. Преобразования циклов

2.4.1. Раскрутка цикла

2.4.2. Канонизация циклов

2.4.3. Перестановка блоков в цикле

2.4.4. Расщепление цикла

2.4.5. Разрыв итераций, гнездование цикла и подобные им преобразования

2.4.6. Развёртка цикла

2.4.7. Расщепление вершин (Введение временных массивов)

2.4.8. Растягивание скаляров и расширение массива

2.4.9. Разбиение цикла

2.4.10. Приведение цикла к разбиваемому виду

2.4.11. Использование перестановки операторов для разбиения цикла

2.4.12. Использование расщепления вершин для разбиения цикла

2.4.13. Повышение размерности массивов для разбиения циклов

2.4.14. Слияние циклов

2.4.15. Инверсия цикла

2.4.16. Вынос оператора из цикла

2.4.17. Индуктивные и охватывающие переменные в цикле

2.5. Преобразования неканонических циклов

2.5.1. Сдвиги границ циклов

2.5.2. Расщепление с перестановкой

2.6. Преобразования функций

2.6.1. Инлайнинг

2.6.2. Уменьшение количества параметров функции

3. РАСПАРАЛЛЕЛИВАНИЕ

3.1. Параллельные процессы

3.2. Параллельные вычислительные архитектуры

3.3. Виды распараллеливания программ

3.4. Распараллеливание циклов на архитектуру SIMD

3.5. Распараллеливание конкатенации блоков на архитектуру MIMD

3.6. Распараллеливание циклов на архитектуру MIMD

3.7. Асинхронное распараллеливание циклов с зависимыми итерациями

3.8. Ошибочные представления о распараллеливании

4. ПРИМЕРЫ КОНТРОЛЬНЫХ ЗАДАНИЙ

4.1. Пример контрольного задания на построение графа информационных связей

4.2. Пример тестовых вопросов по преобразованиям программ

ЛИТЕРАТУРА

Отрывок из книги

132.1. Программные зависимости и базовые преобразованияками, которые перехватывают передачи управления, входящие в рассматриваемый цикл и выходящие из него. Пример 4. В этом примере все операторы информационно незави-симы. Управление передаётся от каждого предыдущего оператора к последующему. Но операторы 3 и 4 можно менять местами, а опе-раторы 1 и 2 – нельзя. Заметим, что перестановка операторов 1 и 2 приводит к программе синтаксически и семантически коррект-ной, но не эквивалентной исходной. По этой причине иногда при-ходится оговаривать, какие именно операторы входят в рассма-триваемый фрагмент. 1 GOTO 2;2 X = 1; 3 Y = 2 ;4 Z = 3 ;Конец примера. Строгое определение корректности преобразования про-грамм обсуждается в [6]. В данной работе исследуются эквива-лентность и эффективность преобразований программ. Синтак-сическая корректность преобразований если не оговаривается, то подразумевается. При автоматических преобразованиях программы в опти-мизирующих компиляторах программы, как правило, находятся в древовидных внутренних (промежуточных) представлениях. И преобразования проводятся во внутреннем представлении и представляют собой преобразования деревьев. Этим самым устра-няются некоторые некорректности, которые возможны при пре-образованиях текста. Например, невозможно переставить местами тело цикла и заголовок цикла, поскольку заголовок цикла – это корень куста, на котором тело цикла находится, а переставлять можно только целые кусты. В Оптимизирующей распараллелива-ющей системе (ОРС) строится визуализация управляющего графа программы (рис. 1).

Внимание!
При обнаружении неточностей или ошибок в описании книги "Оптимизирующие преобразования программ (автор Борис Штейнберг)", просим Вас отправить сообщение на почту help@directmedia.ru. Благодарим!