Введение
1. Анализ методов, алгоритмов и специализированных устройств планирования размещения подпрограмм в мультипроцессорных системах 18
1.1 Обзор мультипроцессорных систем 18
1.2 Задача размещения программ в мультипроцессорных системах 21
1.3 Классификация методов и алгоритмов размещения 23
1.4 Метаэвристические алгоритмы планирования размещения 1.4.1 Муравьиные алгоритмы 30
1.4.2 Алгоритм роящихся частиц 35
1.4.3 Пчелиный алгоритм поиска варианта размещения 36
1.4.4 Планирование размещения на основе генетических алгоритмов 1.4.5 Планирование размещения методом «гильотинного» разреза 49
1.4.6 Планирование размещения параллельных программ методом свертки 50
1.5 Анализ целесообразности аппаратной реализации задачи размещения 1.6 Выводы 71
2. Модели, методы, алгоритмы разбиения линейных, условных, циклических участках последовательных программ, их размещение в матричных масштабируемых мультипроцессорах 72
2.1 Обобщенная постановка задачи разбиения 72
2.2 Формализованная постановка и математические модели задачи разбиения 75
2.3 Методы разбиения в линейных, условных и циклических участках последовательных программ 89
2.4 Алгоритмы разбиения линейных, условных и циклических участков последовательных программ 92
2.5 Выводы 99
3. Математическая модель, методы и алгоритмы ускоренного планирования
размещения параллельных программ в отказоустойчивых матричных
масштабируемых мультипроцессорах 100
3.1 Обобщенная постановка задачи планирования размещения программ в матричных масштабируемых мультипроцессорах 100
3.2 Формализованная постановка задачи размещения программ в масштабируемых мультипроцессорах 104
3.3 Подход планирования размещения программ в матричных масштабируемых мультипроцессорах 106
3.4 Методика и алгоритмы планирования размещения программ в масштабируемых мультипроцессорах 108
3.5 Выводы 117
4. Математическая модель, методы и алгоритмы оператвного переразмещения параллельных программ в матричных масштабируемых мультипроцессорах с учетом отказов 118
4.1 Анализ средств обеспечения отказоустойчивости мультипроцессорных систем 118
4.2 Метод оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах
4.2.1 Обобщенная постановка задачи переразмещения программ 131
4.2.2 Математическая постановка задачи отказоустойчивого переразмещения 133
4.3 Алгоритмы переразмещения программ при отказах процессоров и
межпроцессорных связей 137
4.3.1 Алгоритм замены отказавшего процессора резервным 137
4.3.2 Алгоритм переразмещения при отказе процессора и межпроцессорной связи 138
4.4 Выводы 143
5. Экспериментальны исследования эффективности методов и алгоритмов разбиения линейных, условных, циклических участков последовательных программ, их размещения в масштабируемых мультипроцессорах системах .
5.1 Методы и методики постановки эксперимента 144
5.2 Оценка эффективности алгоритмов разбиения 146
5.3 Оценка эффективности алгоритмов размещения программ в мультипроцессорных системах 147
5.4 Оценка эффективности алгоритмов отказоустойчивого переразмещения программ в мультипроцессорных системах
5.4.1 Программная модель процедур переразмещения с учётом отказа процессора и/или отказа линка 159
5.4.2 Результаты исследования эффективности алгоритма планирования размещения 161
5.4.3 Результаты исследования эффективности алгоритма переразмещения с учетом отказа процессора и/или отказа линка 166
5.5 Выводы 169
6. Аппаратные средства планирования размещения параллельных программ в отказоустойчивых масштабируемых мультипроцессорных системах 171
6.1 Анализ подходов к аппаратной реализации задачи планирования размещения программ в мультипроцессорных системах 171
6.2 Алгоритмы, структурные и функциональные схемы специализированного устройства разбиения
6.2.1 Функциональная организация устройства формирования матрицы неполного параллелизма 183
6.2.2 Алгоритмы работы устройства разбиения 185
6.2.3 Алгоритмы работы вычислительных модулей 190
6.2.4 Анализ временной и аппаратной сложности устройства разбиения 196
6.3 Структурные и функциональные схемы планирования размещения
программ в мультипроцессорных системах 199 6.3.1 Структурная организация специализированного акселератора
планирования размещения программ 201
6.3.2 Алгоритмы функционирования специализированного устройства 203
6.3.3 Устройство проверки качества размещения задач 207
6.4 Устройство оперативного переразмещения программ в
отказоустойчивых мультипроцессорных системах 217
6.4.1 Принцип аппаратной реализации переразмещения подпрограмм в отказоустойчивых мультикомпьютерах 217
6.4.2 Структурная организация акселератора переразмещения 219
6.4.3 Алгоритмы функционирования акселератора 220
6.4.4 Устройство замены отказавшего модуля резервным 224
6.4.5 Оценка производительности и быстродействия акселератора 230
6.4.6 Устройство поиска кратчайшего пути обхода межпроцессорной связи 234
6.4.7 Оценка аппаратной и временной сложности устройства поиска кратчайшего пути 240
6.5 Выводы 245
Заключение 247
Библиографический список 251
