Введение
Глава 1. Исследование задачи планирования вычислений в многопроцессорных системах с неполным графом связей 13
1.1. Постановка задачи 13
1.2. Потоковый алгоритм для случая полного графа связей 15
1.3. NP-трудность некоторых задач 16
1.3.1. Задача с издержками на переключения 16
1.3.2. Задача с издержками на прерывания на одном процессоре 17
1.3.3. Случай неидентичных процессоров 17
1.3.4. Случай произвольного графа связей 19
1.3.5. Случай двух отдельных полных компонент 19
1.4. Формулировка основной задачи. Некоторые упрощения 22
1.5. Алгоритм решения основной задачи 27
1.5.1. Задача преобразования расписания 27
1.5.2. Задача преобразования таблицы 28
1.5.3. Полиномиальное сведение 29
1.5.4. Масштабирование 35
1.6. NP-трудность основной задачи в общем случае 40
1.7. Учет издержек на прерывания и переключения 47
1.7.1. NP-трудность 47
1.7.2. Случай полного графа связей 48
1.7.3. Метод последовательных приближений 48
1.7.4.Общий случай 49
1.8. Специальная задача с учетом некоторых переключений 50
1.8.1. Формулировка задачи 50
1.8.2. Эквивалентная задача 52
1.8.3. Сведение к задаче булевого линейного программирования ...58
1.8.4. Сведение к задаче целочисленного линейного программирования 62
Глава 2. Алгоритмы организации рестартов в системах реального времени 64
2.1. Формулировка задачи 64
2.2. Простейший случай 67
2.2.1. Упрощающие предположения 67
2.2.2. Предварительные результаты 68
2.2.3. Одинаковое число модулей-буферов и модулей контроля 73
2.2.4. Один модуль-буфер 75
2.2.5. Два модуля-буфера 77
2.2.6. Произвольное число модулей-буферов 81
2.3. Случай нескольких параллельных цепочек рабочих модулей 87
2.3.1. Постановка задачи 87
2.3.2. Разделение модулей контроля по одинаковым цепочкам 89
2.3.3. Разделение модулей контроля по цепочкам при заданном разделении модулей-буферов 93
2.3.4. Приближенный алгоритм расстановки модулей 95
2.3.5. Точный алгоритм расстановки модулей контроля и модулей-буферов в случае нескольких параллельных цепочек 99
2.4. Расположение модулей контроля для случая ориентированного дерева 102
2.4.1. Постановка задачи 102
2.4.2. Связь расстановок модулей контроля в дереве и в цепочке 105
2.4.3. Алгоритм для построения оптимальной расстановке модулей контроля в дереве 106
2.5. Расположение модулей контроля для случая произвольного графа связей между рабочими модулями 110
2.5.1. Порядок выполнения рабочих модулей при заданном расположении модулей контроля 110
2.5.2. NP-трудность в сильном смысле задачи расстановки модулей контроля для случая произвольного графа 114
2.5.3. Применение метода "ветвей и границ" 117
2.5.4. Альтернативная стратегия при обнаружении ошибки 121
2.6. Расстановка модулей контроля для случая произвольной вероятности ошибки 123
2.6.1. Вычисление математического ожидания 124
2.6.2. Оптимальное расположение модулей контроля для случая цепочки 126
2.6.3. Случай равных паралельных цепочек 130
2.6.4. Случай произвольных паралельных цепочек 134
Заключение 135
Список использованных источников 137
