| ВВЕДЕНИЕ 5 | |
| Глава 1 МАТЕМАТИЧЕСКИЙ АППАРАТ И МОДЕЛИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ | 8 |
| 1.1 Основные определения | 8 |
| 1.1.1 Функции, задающие индексы массивовданных | 8 |
| 1.1.2 Зависимости | 9 |
| 1.1.3 Представление зависимостей | 12 |
| 1.2 Типы зависимостей. Устранение антизависимо стей и зависимостей по выходу | 15 |
| 1.2.1 Переобозначение | 16 |
| 1.2.2 Увеличение размерности | 17 |
| 1.2.3 Расщепление операторов | 17 |
| 1.3 Таймирующие функции | 21 |
| 1.4 Аффинные преобразования гнезд вложенных циклов | 25 |
| 1.4.1 Преобразования тесно вложенных циклов | 26 |
| 1.4.2 Применение к не тесно вложенным циклам . | 31 |
| Глава 2 ПОЛУЧЕНИЕ ТАЙМИРУЮЩИХ ФУНКЦИЙ И ПРЕОБРАЗОВАНИЙ ЦИКЛОВ | 33 |
| 2.1 Распараллеливание, использующее уровни зави симостей | 33 |
| 2.2 Получение таймирующих функций для однород ных гнезд циклов | 38 |
| 2.3 Необходимые и достаточные условия для сохра нения зависимостей | 45 |
| 2.4 Получение таймирующих функций для аффин ных гнезд циклов | 49 |
| 2.4.1 Условия и алгоритм получения t -функций | 49 |
| 2.4.2 Получение наибольшего числа независимых тай- мирований | 52 |
| 2.5 Генерация кода | 57 |
| Глава 3 РАСПРЕДЕЛЕНИЕ ОПЕРАЦИЙ И ДАН НЫХ МЕЖДУ ПРОЦЕССОРАМИ. ЛОКАЛИЗАЦИЯ ДАННЫХ | 64 |
| 3.1 Пространственно-временное отображение. Обоб щенный конвейерный параллелизм | 64 |
| 3.2 Функции распределения массивов между процес сорами и итерациями | 67 |
| 3.3 Организация обмена данными | 75 |
| | |
| 3.3.1 Организация бродкаста | 75 |
| 3.3.2 Организация трансляции данных | 77 |
| 3.3.3 Установление схемы обмена данными | 79 |
| | |
| 3.4 Улучшение локальности гнезд циклов | 85 |
| 3.5 Блокинг. Тайлинг | 92 |
| | |
| 3.5.1 Задачи, связанные с разбиением операцийалгоритма на зерна вычислений | 92 |
| 3.5.2 Разбиение пространств итераций на блоки и тайлы | 94 |
| 3.5.3 Выбор параметров таила и локальность данных | 95 |
| 3.5.4 Получение зерна вычислений | 95 |
| 3.5.5 Примеры разбиения циклов | 97 |
| ЛИТЕРАТУРА | 99 |