Методы планирования вычислений в САПР систем реального времени
Диссертация
В наиболее общей формулировке задачи составления расписаний состоят в следующем. С помощью допустимого набора ресурсов или обслуживающих устройств должна быть выполнена система заданий. Цель заключается в том, чтобы при известных свойствах заданий и ресурсов и наложенных на них ограничениях найти эффективный алгоритм упорядочения заданий, оптимизирующий желаемую меру эффективности. В качестве… Читать ещё >
Содержание
- ГЛАВА 1. СИСТЕМА АВТОМАТИЗАЦИИ ПРОГРАММИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ. ОБЩАЯ СХЕМА, ПОТОКИ ИНФОРМАЦИИ, СТРУКТУРА СИСТЕМЫ
- 1. 1. Задачи, назначение и общая схема САПР систем реального времени «СРВ-Конструктор»
- 1. 2. Язык реального времени
- 1. 3. Основные блоки транслятора
- 1. 4. Управляющий монитор
- ГЛАВА 2. ВХОДНОЙ ЯЗЫК САПР ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ
- 2. 1. Синтаксис
- 2. 2. Типы данных 31 2.2.1. Целые константы 31 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. 1. Основные функции генератора сетевых моделей и расписаний
- 3. 2. Структурная схема и последовательность выполнения основных блоков 69 3.2.1. Основные определения и обозначения
- 3. 3. Основные алгоритмы
- 3. 3. 1. Построение сети М-модулей
- 3. 3. 2. Вычисление директивных интервалов
- 3. 3. 3. Построение допустимого расписания
- 3. 3. 4. Построение таблицы соответствия Т-, Е- и Л-модулей
- 3. 3. 5. Вычисление размеров буферов для входных параметров
- 3. 3. 6. Назначение стеков Т-модулям
- 4. 1. Выбор операционной среды
- 4. 2. Основные функции управляющей программы
- 4. 3. Структура управляющей программы
- 4. 3. 1. Интерпретатор команд
- 4. 3. 2. Диспетчер
- 4. 3. 3. Монитор данных
- 4. 3. 4. Драйверы внешних устройств
- 5. 1. Сборка и запуск программного комплекса «СРВ-Конструктор»
- 5. 2. Генератор кодов
- 6. 1. Постановка задачи для случая процессоров одинаковой производительности
- 6. 2. Постановка задачи для случая процессоров различной производительности
- 6. 3. Существующие методы решения
- 6. 3. 1. Алгоритмы случайного поиска
- 6. 3. 2. Алгоритмы детерминированной коррекции расписаний
- 6. 3. 3. Алгоритмы имитации отжига
- 6. 3. 4. Генетические и эволюционные алгоритмы
- 6. 3. 5. Алгоритмы агрегирования
- 6. 4. Выводы
- 7. 1. Решение задачи 6.1 (для случая одинаковых процессоров)
- 7. 1. 1. Эври стический алгоритм
- 7. 1. 2. Контрольный алгоритм
- 7. 1. 3. Контрольный алгоритм
- 7. 1. 4. Сравнительные итоги расчётов по алгоритму 1 с разными процентами калибровки
- 7. 2. Решение задачи 6.2 (для случая различных процессоров)
- 7. 2. 1. Описание жадного алгоритма
- 7. 2. 2. Описание эвристического алгоритма
- 7. 2. 3. Вычислительные эксперименты и рекомендации к применению
Список литературы
- Танаев B.C., Гордон B.C., Шафранский Я. М. Теория расписаний. Одностадийные системы. — М.: Наука, 1984.
- Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. М.: Радио и связь, 1990.
- Головкин Б.А. Расчёт характеристик и планирование параллельных вычислительных процессов. М.: Радио и Связь, 1983.
- Логинова И.В., Сушков Б. Г. Динамическое распределение памяти в системах реального времени при имеющемся расписании центрального процессора // В сборнике «Теория и реализация систем реального времени», ВЦ АН СССР, стр. 49−69, 1984.
- Луганский И.Л., Сушков Б. Г. Язык программирования детерминированных систем реального времени. М.: ВЦ АН СССР, 1986.
- Сушков Б. Г ЭВМ управляет экспериментом. (Вычислительные системы реального времени.) // Новое в жизни, науке, технике. Сер. «Математика, кибернетика». -М.: Знание, 1987, N9.
- Шкурба В.В., Селивончик В. М. Расписания, имитационное моделирование и оптимизация. Кибернетика, 1981, № 1, с. 91−96.
- Костенко В.А., Смелянский Р. Л., Третиt А.Г. Синтез структур вычислительных систем реального времени с использованием генетических алгоритмов//Программирование, 2000, № 5.
- Лазарев A.A., Гафаров Е. Р. Теория расписаний. Минимизация суммарного запаздывания для одного прибора. М.:ВЦРАН, 2006
- Сигал И.Х. Задача коммивояжера большой размерности // ВЦ АН СССР, 1986.
- Сигал ИХ. Приближенные методы и алгоритмы в дискретной оптимизации // ВЦ РАН М.: Изд-во ВЦ РАН, 2000.
- Сигал И.Х., Иванова А. П. Введение в прикладное дискретное программирование // ФИЗМАТЛИТ. 2002.
- Federgruen A., Groenevelt H. «Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Technique». Management Science Vol. 32, No. 3, March 1986.
- Гэри M., Джонсон Д. Вычислительные машины и трудно решаемые задачи // М.: Мир, 1982.
- Dertouzos M.L. Control Robotics: The Procedural Control of Physical Processes, Information Processing 74, North-Holland Publishing Company, 1974.21 .Conway R., Maxwell IV., Miller L. Theory of Scheduling. // Addison Wesley Publishing Company, 1967.
- Конвей P.В., Максвелл В. Л., Миллер Л.В."Теория расписаний", М.: Наука, 1975.
- Кормен Т., Лейзерсон Ч., Pueecm Р. «Алгоритмы: построение и анализ» М. МЦНМО, 1999.
- Коффман Е. До/с., Грэхем Р. Л. Теория операционных систем // М.: Наука, 1984.
- Мок A.K. Fundamental Design Problems of Distributed Systems for the Hard Real-Time Environment, Ph. D Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1983.
- Audsley N., Burns A., Richardson M. and Wellings A. Hard Real-Time Scheduling: The Deadline Monotonic Approach, IEEE Workshop on Real-Time Operating Systems, 1992.
- Ramamritham K. and Stankovic J.A., Scheduling Algorithms and Operating Systems Support for Real-Time Systems, Proceedings of the IEEE, 82(1): 55−67, Jan 1994.
- Stankovic J.A., et. al., Implications of Classical Scheduling Results for Real-Time Systems, IEEE Computer Society Press, 1995.
- Ульман Дж. Полиномиально полные задачи составления расписаний // Operating Systems Review, 1973.
- Бездушный А.Н., Лютый В. Г., Серебряков В. А. Разработка компиляторов в системе СУПЕР. М.: ВЦ АН СССР, 1991.
- Ахо А., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии, инструменты. М.: Вильяме, 2001.
- Microsoft С. Advanced programming techniques, 1990.38 .Held М., Karp R. A dynamic programming approach to sequencing problern. // SLAM, 1962.
- Корбут A.A., Финкелъштейн Ю. Ю. Дискретное программирование// М. Наука. Гл. ред. физ.-мат. лит. 1969.
- Растригин JI.A. Статистические методы поиска // М.: Наука, 1968.
- Гончаров E.H., Кочетов Ю. А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискрет, анализ и ис-след. операций Сер. 2, 2002. Т. 9, № 2. С. 13−30.
- А2.Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискрет, анализ и исслед. операций Сер. 2, 2003. Т. 10, № 1, С. 11−44.
- АЪ.Ьапй А. Н., and Doig A.G. An automatic method of solving discrete programming problems. // Econometrica. v. 28 (1960), pp. 497−520.
- AA.Little J.D.C., Murty K.G., Sweeney D.W., and Karel C. An algorithm for the traveling salesman problem. // Operations Research, vll (1963), pp 972−989.45 .Алексеев О. Г. Комплексное применение методов дискретной оптимизации // Наука, 1986.
- АЬ.Киселев В. Д., Карелин Д. В. Метод ветвей и границ для решения задач целочисленного квадратичного программирования с булевыми- переменными // Известия Тульского Государственного Университета, 1995, Том 1, выпуск 3, Информатика.
- AU.Panwalkar S., Iskander W. A survey of scheduling rules. // Operations Research. 25(1):45−61, 1977.
- А9.Гуз Д. С. Разработка точных и приближённых алгоритмов составления расписаний и синтеза систем жёсткого реального времени //
- Диссертация на соискание учёной степени канд. физ.-мат. наук, М., 2005.
- Штовба С. Д. Муравьиные алгоритмы // ExponentaPro. Математика в приложениях, № 4(4), 2003.51 .Laarhoven P., Aarts Е., Lenstra J. Job Shop Scheduling by Simulated Annealing // Operations Research, 40(1): 113−125, 1992.
- Holland J.N. Adaptation in Natural and Artificial Systems // Aim Arbor, Michigan: Univ. of Michigan Press, 1975.
- Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs // Third, Revised and Extended Edition, Springer, 1999.
- Goldberg D.E. Genetic Algorithms in Search Optimization & Machine Learning // Addison Wesley, Reading, 1989.bl.Mataric M., Cliff D. Challenges in Evolving Controllers for Physical’Robots // Robotics and autonomous systems, 19(1), p. 67−83, 1996.
- Periaux J. and Winter G. editors. Genetic Algorithms in Engineering and Computer Science // John Wiley & Sons Ltd., 1995.
- CorneD., FangH.-L., Mellish C. Solving the Modular Exam"Scheduling Problem with Genetic Algorithms // DAI Research Paper № 622.
- Daaldr J., Eklund P. W., Ohtnori K. High-Level Synthesis Optimization with Genetic Algorithms // Proceedings of the 4th Pacific Rim International Conference on Artificial Intelligence, Cairns (Australia), 26−30 August 1996, p.276−287.
- Tsurkov V.I., Large-Scale Optimization Problems and Methods // Dordrecht, Boston, London: istent Kluwer Acad. Publ., 2001.
- Красовский Д.В. алгоритмы решения задачи составления оптимального расписания без прерываний // Диссертация на соискание учёной степени канд. физ.-мат. наук, М., 2007.
- Альберт А. Регрессия, псевдоинверсия и рекуррентное оценивание. М, Наука: 1977.
- Rust В., Burrus W.Q., Schneeborder С. A simple algorithm for computing the generalized inverse of matrix. ACM. 1966, V.9.
- Сушков Б.Г., Фуругян М. Г., Гончар Д. Р., Кондратьев О. Л. Методология и программные средства мониторинга чрезвычайных ситуаций. //Тез. докл. конф. «Проблемы управления в чрезвычайных ситуациях», Москва, ИПУ РАН, 1992, 2 с.
- Сушков Б.Г., Фуругяи М. Г., Гончар Д. Р., и др. САПР вычислительных систем реального времени для IBM PC. // Тез. межд. конф. «Проблемы регионального и муниципального управления». Москва: РГГУ, 1999, 1 с.
- Сушков Б.Г., Фуругян М. Г., Гончар Д. Р., и др. Система автоматизации программирования вычислительных систем реального времени. В сб. «Теория и реализация вычислительных систем реального времени». М.: ВЦ РАН, 1999, 8 с.
- А.Сушков Б. Г., Белый Д. В., Фуругян М. Г., Гончар ДР., Кондратьев О. Л. и др. Автоматизация программирования вычислительных систем реального времени. //В сб.: Моделирование обработки информации и процессов управления. М.: МФТИ, 2000, 10 с.
- Gonchar D., Fourougyan М. The decision of one problem of distribution of resources at presence of uncertain factors. // Proceedings of III Moscow International Conference on Operations Research / ВЦ PAH. M., 2001, 1 c.
- Гончар Д.Р., Фуругян М. Г. Автоматизация проектирования систем реального времени для испытаний и мониторинга сложных технических объектов. Материалы 9-й межд. конф. «Проблемы управления безопасностью сложных систем», М., ИПУ РАН, 2001, 4 с.
- Гончар ДР. Мультиоценочный эвристический алгоритм распределения М заданий на N одинаковых процессорах //В сб. Процессы и методы обработки информации. М.: МФТИ, 2005. 3 с.
- Фуругян М.Г., Гончар Д. Р. Мультиоценочный алгоритм решения минимаксной задачи составления расписания. /Сборник научных трудов Моделирование процессов обработки информации. М.: МФТИ, 2007. С. 202 — 209.