Алгоритмы планирования вычислений и организации рестартов в системах реального времени

• Автор: Гречук, Богдан Васильевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 140 с.

ф Глава 1. Исследование задачи планирования вычислений в

многопроцессорных системах с неполным графом связей

1.1. Постановка задачи

1.2. Потоковый алгоритм для случая полного графа связей

< 1.3. ИР-трудность некоторых задач

1.3.1. Задача с издержками на переключения

1.3.2. Задача с издержками на прерывания на одном процессоре

1.3.3. Случай не идентичных процессоров

ф 1.3.4. Случай произвольного графа связей

1.3.5. Случай двух отдельных полных компонент

1.4. Формулировка основной задачи. Некоторые упрощения

1.5. Алгоритм решения основной задачи
1.5.1. Задача преобразования расписания
1.5.2. Задача преобразования таблицы
1.5.3. Полиномиальное сведение
1.5.4. Масштабирование
1.6. ЫР-трудностъ основной задачи в общем случае
1.7. Учет издержек на прерывания и переключения
1.7.1.14Р-трудность
1.7.2. Случай полного графа связей
1.7.3. Метод последовательных приближений
1.7.4.0бщий случай
# 1.8. Специальная задача с учетом некоторых переключений
1.8.1. Формулировка задачи

1.8.2. Эквивалентная задача
1.8.3. Сведение к задаче булевого линейного программирования
1.8.4. Сведение к задаче целочисленного линейного программирования
Глава 2. Алгоритмы организации рестартов в системах реального времени
2.1. Формулировка задачи
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.3.4. Приближенный алгоритм расстановки модулей
2.3.5. Точный алгоритм расстановки модулей контроля и модулей-буферов в случае нескольких параллельных цепочек
2.4. Расположение модулей контроля для случая ориентированного дерева
2.4.1. Постановка задачи
2.4.2. Связь расстановок модулей контроля в дереве и в цепочке

2.4.3. Алгоритм для построения оптимальной расстановке модулей
контроля в дереве
2.5. Расположение модулей контроля для случая произвольного графа связей между рабочими модулями
2.5.1. Порядок выполнения рабочих модулей при заданном расположении модулей контроля
2.5.2.1ЧР-трудность в сильном смысле задачи расстановки модулей контроля для случая произвольного графа
2.5.3. Применение метода “ветвей и границ”
2.5.4. Альтернативная стратегия при обнаружении ошибки
2.6. Расстановка модулей контроля для случая произвольной вероятности ошибки
• 2.6.1. Вычисление математического ожидания
2.6.2. Оптимальное расположение модулей контроля для случая цепочки
2.6.3. Случай равных паралельных цепочек
2.6.4. Случай произвольных паралельных цепочек
Заключение
Список использованных источников

прерываний и переключений. При этом длина интервала увеличивается на 4тпг и становится равной Гу;
Сделаем следующие замечания:
1) Как правило, число процессоров - несколько десятков, число работ -несколько сотен, а число тактов - десятки или сотни тысяч. Поэтому замена величины Гу на величину /у - 4тпг является не очень грубой и при
определенном запасе тактов алгоритм найдет допустимое расписание.
2) Алгоритм является полиномиальным (а не псевдополиномиальным), что весьма существенно при большом числе тактов.
3) Если алгоритм не находит допустимого расписания, можно применить метод последовательных приближений (см.п.З).
1.8. Специальная задача с учетом некоторых переключений
1.8.1. Формулировка задачи
В предыдущем разделе построены некоторые эвристические алгоритмы для решения ЫР-трудной задачи построения допустимого расписания с учетом затрат на прерывания и переключения. Конечно, во многих практических случаях эвристических алгоритмов (которые могут решить задачу, а могут и не решить) недостаточно. Распространенным приемом при решении ЫР-трудных задач является их сведение к задаче целочисленного линейного программирования. Эта задача, хоть и является НР-трудной, широко известна, и известно много более-менее эффективных подходов для ее решения.
В работах [13], [14] задача составления допустимого расписания для общего случая (с учетом потерь на прерывания и переключения и для произвольного графа связей) сведена к задаче булевого линейного программирования. Но количество переменных в полученной задаче пропорционально числу тактов. Поэтому при большом числе тактов задача становится трудно разрешимой практически.