Методы планирования вычислений в САПР систем реального времени

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

Содержание
ВВЕДЕНИЕ
ГЛАВА X. СИСТЕМА АВТОМАТИЗАЦИИ ПРОГРАММИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ. ОБЩАЯ СХЕМА, ПОТОКИ ИНФОРМАЦИИ, СТРУКТУРА СИСТЕМЫ

1.1. Задачи, назначение и общая схема САШ систем реального времени СРВКонструктор

1.2. Язык реального времени

1.3. Основные блоки транслятора

1.4. Управляющий монитор

ГЛАВА 2. ВХОДНОЙ ЯЗЫК САПР ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ

2.1. Синтаксис

2.2. Типы данных

2.2.1. Целые константы

2.2.3. Длинные целые константы
2.2.3. Константы с плавающей точкой
2.2.4. Константы с плавающей точкой двойной точности
2.2.5. Символьные константы
2.2.6. Строковые константы
2.2.7. Булевские константы
2.3. Описании
2.3.1. Константные величины
2.3.2. Переменные
2.3.3. Источники поступления информации в ВСРВ
2.3.4. Кадр входных данных
2.3.5. Прикладные модули
2.3.6. Таблица переключений
2.4. Исполняемые конетрукцни
2.4.1. РВциклы
2.4.2. Предварительная и заключительная части простых заданий
2.4.3. Фоновые работы
2.4.4. Модуль реакции
2.5. Структура РВпрограммм
2.5.1. Условное задание
2.5.2. Простое задание
ГЛАВА 3. СИСТЕМА АВТОМАТИЗИРОВАННОГО СИНТЕЗА МОДЕЛИ ВСРВ. ГЕНЕРАТОР СЕТЕВОЙ МОДЕЛИ И РАСПИСАНИЙ
ЗЛ. Основные функции генератора сетевых моделей п расписаний
3.2. Структурная схема и последовательность выполнения основных блоков
3.2.1. Основные определения и обозначения
3.3. Основные алгоритмы
3.3.1. Построение сети Ммодулей
3.3.2. Вычисление директивных интервалов
3.3.3. Построение допустимого расписания
3.3.4. Построение таблицы соответствия Г, Е и модулей
3.3.5. Вычисление размеров буферов для входных параметров
3.3.6. Назначение стеков Тмодуля.м
ГЛАВА 4. УПРАВЛЯЮЩАЯ ПРОГРАММА САПР СРВКОНСТРУКТОР
4.1. Выбор операционной среды
4.2. Основные функции управляющей программы
4.3. Структура управляющей программы
4.3.1. Интерпретатор команд
4.3.2. Диспетчер
4.3.3. Монитор данных
4.3.4. Драйверы внешних устройств
ГЛАВА 5. ПРОГРАММНЫЙ КОМПЛЕКС СРВКОНСТРУКТОР
5.1. Сборка и запуск программного комплекса СРВКонструктор
5.2. Г оператор кодов.
ГЛАВА 6. ПЛАНИРОВАНИЕ РАСПИСАНИЙ ДЛЯ МНОГОПРОЦЕССОРНОГО ВАРИАНТА СИСТЕМЫ СРВКОНСТРУКТОР. ЗАДАЧА РАСПРЕДЕЛЕНИЯ М ЗАДАНИЙ НА ПРОЦЕССОРОВ
6.1. Постановка задачи для случая процессоров одинаковой
производительности
6.2. Постановка задачи для случая процессоров различной
производительности
6.3. Существующие .методы решения
6.3.1. Алгоритмы случайного поиска
6.3.2. Алгоритмы детерминированной коррекции расписаний
6.3.3. Алгоритмы имитации отжига
6.3.4. Генетические и эволюционные алгоритмы
6.3.5. Алгоритмы агрегирования
6.4. Выводы
ГЛАВА 7. ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ РАСПРЕДЕЛЕНИЯ ЗАДАНИИ ПО ПРОЦЕССОРАМ В САПР СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ
7.1. Решение задачи 6.1 для случая одинаковых процессоров.
7.1.1. Эвристический алгоритм 1
7.1.2. Контрольный алгоритм 1
7.1.3. Контрольный алгоритм 2
7.1.4. Сравнительные итоги расчбтов по алгоритму 1 с разными процентами калибровки
7.2. Решение задачи 6.2 для случая различных процессоров
7.2.1. Описание жадного алгоритма
7.2.2. Описание эвристического алгоритма 2
7.2.3. Вычислительные эксперименты п рекомендации к применению
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Многие варианты задач составления многопроцессорного расписания являются NP-трудными. Принимая во внимание трудность задачи, любая практическая реализация составления многопроцессорного расписания — это всегда своеобразный компромисс между результатом и вычислительной сложностью. Поэтому вопрос составления более эффективных эвристических алгоритмов, в том числе для конкретных видов задач составления расписаний, является в настоящее время достаточно актуальным для рассматриваемой предметной области. Создание и использование ВСРВ стало актуальной задачей при появлении достаточно надёжной и мощной вычислительной базы, что, как известно, произошло к -х годам XX в. С этого времени изучению математических вопросов теории расписании и её приложений исследователи уделяют повышенное внимание. В России, а до того в СССР, задачей построения расписаний в системах реального времени занимались Танаев В. С.[1], Барский А. Б.[2], Головкин Б. А.[3], Сушков Б. Г.[4, 5, 6 и др. Шкурба В. В.[7], Гордон В. С.[1], Костенко В. А.[8], Лазарев А. А.[9], Мищенко A. B. [], Португал В. М.[], Сигал И. Х.[, ,], Шафранский B. C. [1] и др. Среди зарубежных учёных следует отметить Бернса (Burns)[], Бруксра (Bruker)[], Гонзалеса (Gonzales) [], Греневельта (Groenevelt) [], Гэри М. Garey)[], Дертузоса (Dertouzos)[], Джонсона Д. Jolinson)[], Конвея Р. В. (Conway)[, ], КорменаТ. Коффмана (Koffman)[, ], JIbio(Liu)[], Лейланда (Layland)[], Лей-зерсона 4. Leiserson) [], Максвелла В. Л.(Maxwell) [, ], Мартеля (Martel)[], Миллера Л. В. (Miller) [,], Мока (Mok)[], Одели (Aud-sley) [], Рамамритама (Ramamritham)[], Ривеста T. Rivest) [], Ричардсона (Richardson)[], Сахни (Sahni)[], Станковича (Stankovic)[, ], Ульмана Дж. Считаю своим долгом выразить благодарность Ю. А.Флёрову, М. Г.Фуругяну, О. Л.Кондратьеву, А. В.Сухих, О. С.Н. Мирошнику за помощь в работе и обсуждение полученных результатов. Цели и задачи исследования. Основной целью диссертационной работы является разработка программного комплекса инструментальной САПР «СРВ-Конструктор» для персональных электронно-вычислительных машин, а также новых методов составления расписаний, предназначенных для функционирования на многопроцессорной ВС. Эти методы можно включить в состав программных средств, предназначенных для осуществления планирования вычислений на вычислительных системах, в том числе системах жёсткого реального времени. САПР для многопроцессорных вычислительных комплексов разработаны и реализованы новые эвристические алгоритмы решения задачи построения оптимального по быстродействию расписания без прерываний. Б.Г. Бремени (РВ-программы), описывающей на формальном языке необходимый порядок выполнения прикладных программ пользователя, генерирующего таблицы данных для работы последующих блоков и вычисляющего размеры буферов обмена данными между программными модулями. Блока генерации сетевой модели и расписаний, строящего математическую модель вычислений, выполняемых в реальном времени, в виде графа, в котором вершины соответствуют прикладным модулям пользователя, а дуги определяют частичный порядок их выполнения, определяющего директивные интервалы выполнения прикладных модулей, возможность построения допустимого расписания выполнения прикладных модулей и само расписание, если оно существует, а также выполняющего некоторые другие вспомогательные функции построения инструмен-тапьной САПР ВСРВ. Блока генерации кода, формирующего на языке С и записывающего в текущий каталог исходные тексты получившейся программы, а также создающего ряд вспомогательных файлов для последующих определенных действий пользователя, компиляции и редактирования связей. Управляющего монитора на основе многозадачной оболочки реального времени СТайк-КТ, обеспечивающего работу в реальном времени прикладной программы пользователя, сгенерированной на этапе предварительной обработки посредством САПР ВСРВ. Предмет исследования. В соответствии с поставленной целью предметом исследования является методология построения инструментальной САПР систем реального времени.