Синтез архитектур вычислительных систем реального времени с учетом ограничений на время выполнения и требований к надежности

• Автор: Зорин, Даниил Александрович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 133 с. : ил.

Оглавление
Введение
1 Постановка задачи
1.1 Содержательное описание задачи
1.2 Модель входных данных
1.3 Механизмы обеспечения надежности
1.4 Модель расписания
1.5 Вычисление времени выполнения расписания
1.6 Вычисление надежности
1.7 Математическая постановка задачи
1.8 Выводы
2 Обзор возможных подходов к построению алгоритмов решения
задачи и алгоритмов решения близких задач
2.1 Цель обзора
2.2 Полный перебор
2.3 Метод ветвей и границ
2.4 Жадные алгоритмы
2.5 Алгоритм имитации отжига
2.6 Генетические алгоритмы
2.7 Выводы
3 Алгоритм построения расписания
3.1 Общая схема алгоритма
3.2 Операции преобразования расписания
3.3 Стратегии применения операций
3.4 Условие перехода к новому расписанию и критерий останова.

3.5 Вычислительная сложность одной итерации алгоритма
3.6 Выводы
4 Исследование свойств алгоритма
4.1 Асимптотическая сходимость алгоритма
4.2 Метрика в пространстве расписаний
4.2.1 Метрика ЦА, В)
4.2.2 Метрика Н(А, В)
4.2.3 Связь между метриками ЦА, В) и Н(А, В)
4.2.4 Оценка для ЦА, В)
4.3 Экспериментальное исследование алгоритма
4.3.1 Оценка точности на модельных данных
4.3.2 Оценка точности на совместимых исходных данных
4.3.3 Сравнение законов понижения температуры
4.4 Выводы
5 Инструментальная система
5.1 Требования к системе
5.2 Описание системы
5.2.1 Описание архитектуры системы
5.2.2 Графический пользовательский интерфейс
5.2.3 Подсистема для построения вычислительных систем для
обработки данных от фазированных антенных решеток
5.3 Выводы
Заключение
Литература

Приложение А. Способы оценки надежности
А.1 Надежность процессоров. Резервирование
А.2 Надежность программ. 14-версионное программирование
Приложение Б. Модели среды передачи данных
Б.1 Вычисление времени для системы без конфликтов на портах
Б.2 Вычисление времени для системы с общей шиной или коммутатором
Приложение В. Вычисление времени выполнения с помощью имитационного моделирования
Приложение Г. Описание задачи обработки данных от фазированных антенных решеток

щ <щ. Тогда Nj — Ni+1 U Trans(sn+1) U Trans(sn+2) U ... UTrans(sn+fc). Если Ni_1 = Nt, то Ni = Succ(s).
Для преобразования расписаний введены следующие операции.
Операция добавления резервного процессора. В исходном расписании (S, О) к мультимножеству D добавляется новый элемент.
Операция удаления резервного процессора. В исходном расписании (S, В) из мультимножества D удаляется элемент т , для которого Dup(in) > 1.
Операция переноса задания. В исходном расписании (S,D) выбираются элемент sx = (уг, klt т1} щ) процессор тг и номер и2, такой что
Vs£: m£ = ?n2: (п; < n2 => s, £ Succ^sj) A (n; > n2 => sx ? Succ(si)),
и происходит следующая замена:
si = si'mi = m2'.ni>n2 => s- = (vt, к^т^щ + 1).
Эта операция позволяет или изменить порядковый номер выполнения задания на процессоре, или перенести задание на другой процессор.
Операция добавления версий. Версии можно добавлять только парами в силу принципа работы NVP. Добавление одной версии [у, к) эквивалентно последовательности операций: 1) добавить новый процессор т0; 2) назначить версию первым заданием на этот процессор s = (v, к, тп0,1); 3) перенести s на другой процессор в соответствии с определением операции переноса задания; 4)удалить ?п0.
Операция удаления версий. Версии удаляются также парами. Из расписания удаляются два элемента, соответствующие удаляемым версиям.
Утверждение 3.1. Замкнутость системы операций. Если (5, D) - корректное расписание, то после применения любой из операций также получается корректное расписание.