автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы планирования вычислений в САПР систем реального времени

На правах рукописи

00317058Э

Гончар Дмитрий Русланович

МЕТОДЫ ПЛАНИРОВАНИЯ ВЫЧИСЛЕНИЙ В САПР СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ

Специальность 05 13 11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

2 S [JAfi 2003

Москва - 2008

003170589

Работа выполнена в отделе Математического моделирования систем проектирования Вычислительного центра им А А Дородницына Российской академии наук

Научный руководитель: кандидат физико-математических

наук, доцент

Фуругян Меран Габибуллаевич

Официальные оппоненты: доктор физико-математических наук

Серебряков Владимир Алексеевич

кандидат технических наук Кононов Дмитрий Алексеевич

Ведущая организация: Институт системных

исследований РАН

Защита состоится «26 » ¿¿¿о£6г%, 2008 г в час на заседании диссертационного совета Д 002.017.02 в Вычислительном центре им А А Дородницына Российской академии наук по адресу 119333, г Москва, ул Вавилова, 40, конференц-зал

С диссертацией можно ознакомиться в библиотеке ВЦ РАН Автореферат разослан « 2¿» 2008 г

Ученый секретарь диссертационного совета

доктор физико-математических наук, /П. /

профессор В В Рязанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность работы.

Предметом исследования данной работы являются вычислительные системы жесткого реального времени (ВСРВ) и вопросы автоматизации их проектирования В таких системах части заданий назначаются директивные сроки (начала и окончания обработки заданий), не подлежащие нарушению

ВСРВ предназначены для контроля и управления при жестких временных ограничениях процессами в автоматизированных производствах, в производстве энергии (особенно ядерной энергетике), химической промышленности, газо- и нефтедобыче, авиационном, железнодорожном и морском транспорте, в системах управления летными испытаниями, при управлении в чрезвычайных ситуациях Сегодня ВСРВ всё шире применяются в управлении дорожным движением автотранспорта, экологическом и медицинском мониторинге, разнообразных системах безопасности Таким образом, рассматриваемый класс задач имеет, помимо чисто научной, большую практическую важность

Одновременно с увеличением масштабов и разнообразия применений ВСРВ становятся более высокими требования к их эффективности, надежности и скорости разработки Удовлетворить этим отчасти противоречивым требованиям представляется возможным, прежде всего, путём выхода на более высокий уровень автоматизации построения систем реального времени, созданием соответствующих эффективных, надежных и удобных инструментов их программирования

Одним из практически важных и весьма распространенных типов ВСРВ является ВСРВ с периодически поступающей на обработку входной информацией Если при этом возможна приемлемая точность оценки времени на обработку входной информации, возникает возможность разбиения процесса работы ВСРВ на две стадии - предварительную и основную

На предварительной стадии и не в режиме реального времени первоначально описывается (например, средствами специально построенного для этих целей формального языка) состав и периодичность поступающей информации, соответствующие модули-обработчики, последовательность обработки данных, директивные сроки обработки тех или иных данных и допустимость прерывания этой обработки и т д Затем (с учетом необходимой синхронизации процессов обработки, предотвращения программных тупиков и учета иных особенностей программируемых ВСРВ) автоматически рассчитывается допустимое расписание работы ВСРВ (либо делается вывод о невозможности существования такого расписания), составляется с использованием средств автоматизации программирования программа выполнения режима реального времени, обеспечивается создание нужного количества копий программных модулей обработчиков входных и промежуточных данных ВСРВ (с учетом возможности одновременной обработки нескольких поколений входных данных), средств связи между этими модулями и ОС реального

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

Именно такой подход, позволяющий не только качественно повысить эффективность, скорость и надежность разработки (настройки, усовершенствования) ВСРВ, но и существенно расширить возможный диапазон и сложность решаемых задач (особенно при управлении быстропротекающими процессами) был предложен в ВЦ АН СССР лауреатом Премии СМ СССР, к ф -м н Борисом Григорьевичем Сушковым (1941-1997) и во многом осуществлён под его руководством для ЕС ЭВМ

Уже в 90-е годы была понята актуальность и важность разработки подобной системы и для однопроцессорных персональных ЭВМ Такая система САПР «СРВ-Конструктор» была создана с непосредственным существенным участием автора диссертации и подробно представляется в данной работе

В настоящее время автором продолжаются дальнейшие разработки, направленные на развитие системы для многопроцессорных вычислительных комплексов, в частности, на разработку более эффективных алгоритмов задачи построения расписания для ряда важных частных случаев, часто встречающихся в работе подобных систем

Отметим, что совершенствование технологии и конструкции вычислительных средств (на основе кластеров, многоядерных процессоров и т п ) в последние годы сделали многопроцессорные вычислительные комплексы качественно доступнее и поэтому обоснованность их применения в упомянутых областях еще более возрастает

Вышеперечисленные обстоятельства обусловливают актуальность исследований в указанной области

В математическом плане центральной задачей автоматизированного построения ВСРВ, как правило, является задача составления расписаний Многие варианты задач составления многопроцессорного расписания являются NP-трудными Причем любая практическая реализация составления многопроцессорного расписания - это всегда своеобразный компромисс между результатом и вычислительной сложностью Поэтому вопрос составления более эффективных эвристических алгоритмов, в том числе для конкретных видов задач составления расписаний, является в настоящее время достаточно актуальным для рассматриваемой предметной области

Создание и использование ВСРВ стало актуальной задачей при появлении достаточно надежной и мощной вычислительной базы, что, как известно, произошло к 70-х годам XX в С этого времени изучению математических вопросов теории расписаний и ее приложений исследователи уделяют повышенное внимание

В России, а до того в СССР, задачей построения расписаний в системах реального времени занимались Танаев В С, Барский А.Б , Головкин Б А , Сушков Б.Г , Шкурба В В , Гордон В С , Костенко В А , Лазарев А А , Мищенко А В., Португал В.М, Сигал И X, Шафранский ВС и др.

Среди зарубежных ученых следует отметить Бернса (Bums), Брукера (Braker), Гонзалеса (Gonzales), Греневельта (Groenevelt), Гэри М (Garey),

Дертузоса (Dertouzos), Джонсона Д (Johnson), Конвея Р В (Conway), Корме-на Т (Cormen), Коффмана (Koffman), Лью(Ьш), Лейланда (Layland), Лейзер-сона Ч (Leiserson), Максвелла В Л (Maxwell), Мартеля (Martel), Миллера Л В (Miller), Мока(Мок), Одели (Audsley), Рамамртама (Ramamntham), Ривеста Т (Rivest), Ричардсона (Richardson), Сахни (Sahni), Станковича (Stankovic), Ульмана Дж (Ullman), Федергрюна (Federgraen) и др

Считаю своим долгом выразить благодарность Б Г Сушкову Ю А Флерову, М Г Фуругяну, В А Серебрякову, Д А Кононову, и О Федько и С Н Мирошнику за помощь в работе и обсуждение полученных результатов

Цели работы.

Основной целью диссертационной работы является разработка программного комплекса инструментальной САПР «СРВ-Конструктор» для персональных электронно-вычислительных машин, а также новых методов составления расписаний, предназначенных для функционирования на многопроцессорной ВС Эти методы можно включить в состав программных средств, предназначенных для осуществления планирования вычислений на вычислительных системах, в том числе системах жесткого реального времени

Для достижения поставленной цели

- создан программный комплекс, реализующий инструментальную САПР «СРВ-Конструктор»;

- с целью дальнейшего совершенствования указанной САПР для многопроцессорных вычислительных комплексов разработаны и реализованы новые эвристические алгоритмы решения задачи построения оптимального по быстродействию расписания без прерываний

СРВ-Конструктор состоит из

Блока синтаксического и семантического анализа, осуществляющего синтаксический и семантический анализ конструкций программы реального времени (РВ-программы), описывающей на формальном языке необходимый порядок выполнения прикладных программ пользователя, генерирующего таблицы данных для работы последующих блоков и вычисляющего размеры буферов обмена данными между программными модулями

Блока генерации сетевой модели и расписаний, строящего математическую модель вычислений, выполняемых в реальном времени, определяющего возможность построения допустимого расписания выполнения прикладных модулей и само расписание, если оно существует, и выполняющего некоторые другие вспомогательные функции построения инструментальной САПР ВСРВ.

Блока генерации кода, формирующего на языке Си и записывающего в текущий каталог исходные тексты получившейся программы, а также создающего ряд вспомогательных файлов для последующих определенных действий пользователя, компиляции и редактирования связей

Управляющего монитора на основе многозадачной оболочки реального времени СТазк-ЯТ, обеспечивающего работу в реальном времени прикладной программы пользователя, сгенерированной на этапе предварительной обработки посредством САПР ВСРВ

Научная новизна работы.

Научная новизна диссертационной работы заключается в построении инструментального программного комплекса, дающего новые качественные возможности при автоматизации построения систем реального времени с периодическим поступлением входной информации, а также разработке алгоритмов построения расписаний работ для многопроцессорной вычислительной системы

В процессе исследования автором было выполнено следующее

- разработана и программно реализована инструментальная система САПР «СРВ-Конструктор», включающая язык реального времени, блоки синтаксического и семантического анализа, блок генерации сетевой модели и расписаний, блок генерации кода и управляющий монитор,

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

- на основе многочисленных вычислительных экспериментов получены апостериорные оценки точности разработанных алгоритмов

Методы исследований.

Методологическую и теоретическую основу исследования составили методы разработки систем реального времени, теории расписаний, комбинаторной оптимизации и теории графов

Практическая ценность работы.

Основные результаты исследования относятся к созданию нового инструментального программного комплекса САПР «СРВ-Конструктор» для однопроцессорных ПЭВМ и разработке ряда перспективных эвристических алгоритмов оптимизации планирования вычислений в системах реального времени для многопроцессорных вычислительных комплексов для дальнейшего развития системы САПР «СРВ-Конструктор»

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

А то, что в последние годы начато подлинно массовое производство и применение многопроцессорных технических средств (от вычислительных

кластеров до многоядерных процессоров для ПЭВМ), делает применение таких САПР как «СРВ-Конструктор» все более доступным и целесообразным

Апробация работы.

Результаты диссертации и материалы исследований докладывались и обсуждались на- III научной школе "Автоматизация создания математического обеспечения и архитектуры систем реального времени" (Саратовский ф-л Института машиноведения РАН, Саратов, 1992),

- межд конф "Проблемы управления в чрезвычайных ситуациях" (М , ИЛУ РАН, 1992);

- межд конф "Проблемы регионального и муниципального управления" (М Р1ТУ, 1999),

- IX и X межд конф "Проблемы управления безопасностью сложных систем" (М, ИПУ РАН, 2001 и 2002),

-III межд конф по исследованию операций (М , ВЦ РАН, 2001),

- науч конф "Математические модели сложных систем и междисциплинарные исследования" (М, ВЦ РАН, 2002),

- ХЬУ и ХЫХ науч конф Московского физико-технического института (ГУ), (М -Долгопрудный, 2002, 2006);

- II Всеросс науч конф «Методы и средства обработки информации» (М МГУ, 2005),

- научных семинарах сектора проектирования систем реального времени Вычислительного центра им А А Дородницына РАН,

- научных семинарах кафедры математических основ управления Московского физико-технического института (ГУ)

Публикации. По материалам диссертации опубликовано 20 печатных работ, в том числе одна в журнале, входящем в список изданий, рекомендованных ВАК Список работ приведен в конце автореферата

Структура и объём работы.

Диссертация состоит из введения, семи глав, заключения, приложений и списка литературы Общий объем работы составляет 139 страниц

СОДЕРЖАНИЕ РАБОТЫ

Во введении говориться о важности и актуальности построения вычислительных систем реального времени в целом и рассмотрена общая схема включения ЭВМ в контур контроля процессов, происходящих в некотором реальном физическом объекте, основные потоки информации и состав аппаратных средств типичной многоканальной системы сбора данных и управления процессами (см рис 1).

Рис 1 Схема использования ЭВМ для управления физическими процессами Потоки информации и аппаратные средства типичной многоканальной системы сбора данных и управления представляются на различных устройствах отображения (дисплеях итп) и, кроме того, если необходимо, вырабатываются управляющие воздействия, которые после соответствующих преобразований поступают к объекту, управляя его функционированием АЦП - аналогово-цифровой преобразователь ЦАП -цифро-аналоговый преобразователь УВХ~устройства выборки-хранения аналогового сигнала

Первая глава диссертации посвящается общему описанию САПР систем реального времени «СРВ-Конструктор», как основного проектируемого инструментального средства Описывается состав и структура САПР ВСРВ в целом

Существует два основных подхода к созданию САПР ВСРВ Первый связан с расширением существующих языков новыми операторами, позволяющими пользователю описывать параллельные вычисления и их синхронизацию. При этом вся работа по разделению времени для однопроцессорных систем ложится на пользователя

При создании ВСРВ «СРВ-Конструктор» был выбран другой, ботее перспективный подход, при котором вся работа по разделению времени и оптимизации вычислений выполняется транслятором Для осуществления такого подхода необходимо предварительно построить математическую модель ВСРВ, с помощью которой могут быть решены такие задачи, как разбиение программ на параллельные процессы, составление допустимого расписания выполнения процессов, синхронизация вычислений, динамическое распределение памяти

Для генерации прикладной ВСРВ пользователю необходимо иметь прикладные модели, написанные на языках программирования, например Си, Фортран, Паскаль или Ассемблер, и написать на специальном языке реального времени задание на обработку информации в реальном времени - РВ-программу, где задается порядок обработки прикладными модулями входных данных и отображения результатов счета по отношению к периоду поступления кадров данных в систему Если данный порядок обработки может быть соблюден, система обеспечит реализацию заказанной обработки В противном случае выдается сообщение о невозможности вести указанную обработку

В отличие от систем потоковой обработки данных предусмотрена возможность работы прикладных модулей с несколькими поколениями данных Система автоматически обеспечивает хранение этих данных в специальных буферах нужное время При возникновении внештатной ситуации с управляемым объектом, либо для изменения порядка работы программы реального времени, оператором может быть использована предусмотренная возможность быстрой реакции на поступление апериодической информации Также предусмотрено выполнение прикладных модулей в фоновом режиме

Вся остальная работа по генерации прикладной ВСРВ будет выполнена автоматически с помощью разработанной САПР ВСРВ При этом будут решены следующие проблемы

1) проблема синхронизации параллельных процессов в ВСРВ,

2) проблема тупиков при распределении ресурсов вычислительной системы (процессоров, каналов, памяти, периферийных устройств, а также информационных ресурсов),

3) проблема завершения тех или иных вычислений к определенным моментам времени или к моментам определенных событий в системе, указанных пользователем в РВ-программе (соблюдение директивных сроков),

4) проблема сохранения и обновления необходимых наборов поколений данных, как поступающих в ВСРВ извне, так и являющихся результатами вычислений с помощью РВ-программы,

5) проблема обнаружения в режиме реального времени ошибок и сбоев и организация соответствующих реакций ка них

Решение этих задач обеспечивает надежность программного обеспечения ВСРВ

' Разработанная система наиболее эффективна при составлении программ для детерминированных ВСРВ с циклическим поступлением инфор-

I

мации от контролируемого объекта Детерминированность означает здесь следующее

1) входная информация поступает на входные регистры системы с известным периодом Т, т е в моменты времени О ,Т, 2 Т, .,

2) входная информация может быть объединена в кадры, имеющие постоянную часть (т е поступающую в каждый дискретный момент О, Т,2Т, ) и несколько переменных частей, каждая из которых поступает в систему реже, с большим периодом, кратным Т Количество переменных частей кадра произвольно,

3) контролируемый процесс состоит из конечного числа детерминированных участков Для каждого такого участка заранее известно, какие данные необходимо получать от объекта и передавать к нему, определены форматы входных кадров, а также известно, какую обработку необходимо производить, т е задан список программных модулей, осуществляющих нужные вычисления Иными словами, для каждого участка контролируемого процесса известен режим обработки,

4) для каждого программного модуля известна оценка времени его исполнения, а также потребности в других ресурсах системы,

5) в процессе выполнения каждого режима обработки может быть вычислен момент смены текущего режима и однозначно определен следующий режим обработки,

6) задан начальный (стартовый) режим обработки (например, режим ожидания первого кадра информации от контролируемого объекта).

При разработке САПР ВСРВ для №М РС были реализованы

1) язык реального времени,

2) транслятор с этого языка, включающий блоки синтаксического и семантического анализа, построения сетевой модели вычислений и нахождения допустимого расписания выполнения вычислений, автоматической генерации объектного кода программы реального времени,

3) управляющий монитор, контролирующий вычисления в режиме реального времени

Во второй главе приводится подробное описание входного языка реального времени для ВСРВ «СРВ-Конструктор»

Основным простейшим объектом языка является модуль - обычный для многих языков программирования оператор процедуры Все процедуры, участвующие в образовании модулей, составляются заранее и помещаются в системную библиотеку процедур вместе с необходимыми спецификациями формальных параметров Имеется один специальный тип модуля, введённый для облегчения составления РВ программ - это РВ модуль Он по описанию и смыслу ничем не отличается от обычного модуля Но кроме описания он еще имеет тело, внутри которого указаны вызовы других, в том числе и РВ модулей Для РВ модулей имеется ограничение - они не должны содержать рекурсивных вызовов Фактические параметры любого модуля могут быть РВ-параметрами, константами, простыми переменными, идентификаторами с индексами и т д РВ-параметры имеют следующий вид

<РВ-парамстр> => (<имя РВ-иараметра>, <поставщик>, <поколение>)

Компонента <поставщик> однозначно указывает программный модуль, в котором вычисляется запрашиваемое модулем-потребителем значение параметра с данным именем Из дальнейшего описания языка будет видно, что вызовы модулей могут повторяться в программе, а сами модули могут входить в более сложные объекты языка Поэтому эта компонента, в свою очередь, состоит из нескольких полей При отсутствии имени поставщика считается, что этот РВ-параметр присутствует во входных данных

Компонента <поколение> определяет момент времени, в коюрый необходимо взять требуемое значение параметра В этом разделе может быть указано время, кратное периодичности поступления информации от указанного поставщика данных Системой будет передано потребителю последнее имеющееся на заданный момент времени значение этого параметра

Другие виды фактических параметров аналогичны параметрам процедур известных языков программирования

Из модулей может быть составлен следующий по иерархии сложности объект языка - цикл реального времени

<цикл РВ> => <имя цикла РВ>, <период>, <фаза>, <тело цикла РВ>

Компонента <период> задает интервал времени, через который будет повторяться выполнение модулей, указанных в теле цикла РВ Задание периода аналогично заданию времени для РВ-параметра Если в программе реального времени указано несколько источников данных или в качестве базового периода берется период другого цикла РВ, то требуется явное указание его имени перед значением периода Кроме этого период может быть задан в абсолютных величинах времени секундах, миллисекундах Параметр <фаза> указывает сдвиг начала работы РВ-цикла относительно начала работы программы Правила задания параметра <фаза> такие же, как и для <периода> Фаза не может быть задана больше периода, указанного для данного РВ-цикла Если фаза явно не указана, то она равна нулю <Тело цикла РВ> - это список модулей, РВ-параметры которых могут поставляться из блоков входной информации, из модулей других циклов РВ и из модулей данного цикла Поименованная совокупность РВ циклов образует безусловное задание (простое задание)

безусловное задание> => smplpgm <имя задания>, head <список модулей> end, tail <список модулей> end, inherit <список безусловных заданий>, <список циклов РВ> end Безусловное задание может быть снабжено конструкциями предварительной и заключительной части Они служат для проведения набора специ-

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

Для облегчения программирования на языке реального времени, в новое простое задание допускается вставить несколько других простых заданий (конструкция inherit) В этом случае не придется дублировать исходный текст ранее определенного простого задания.

Основную часть простого задания составляют РВ-циклы Все циклы реального времени, входящие в одно простое задание, должны рассматриваться как выполняющиеся параллельно во времени Если модули некоторого цикла требуют на свой вход данные, поставляемые другим циклом, то необходимая задержка организуется системой

В ходе обработки эксперимента может потребоваться изменить режим обработки Такая возможность предусматривается в языке реального времени введением условного задания

<условное задание> condpgm <имя задания>, cvector <вектор условий>, switchtablc <таблица переключений> end,

<флаги и очереди> <список простых заданий>, end

В разделе <вектор условий> определяется список булевых переменных, от значения которых будет зависеть порядок исполнения программы реального времени. Здесь же указываются начальные значения компонент вектора Компоненты вектора условий мо1ут быть использованы в качестве входных и выходных параметров РВ-модулей В разделе <таблица переключений> задаются правила переключения между простыми и условными заданиями, в зависимости от конкретных значений вектора условий Таблица переключений представляется в виде списка значений вектора условий и имени простого или условного задания, на которое требуется переключиться Для таблицы переключений имеется два ограничения

1) В таблице переключений обязана присутствовать строка, соответствующая начальному значению вектора условий

2) Таблица переключений должна однозначно определять на какое задание должно происходить переключение

Наконец, РВ-программа представляет собой совокупность условных заданий, все таблицы условий которой не содержат ссылок на неописанные задания

<программа РВ> => rtpgm <имя программы>,

<описание констант, модулей, переменных, входных данных>,

<условные задания> end,

В третьей главе приводится описание системы автоматизированного синтеза модели выполнения программ в реальном времени и генератора сетевой модели и расписаний

Реализация алгоритмов композиции подмоделей в комплексную модель оформлена в виде системы автоматизированного синтеза модели выполнения программ в реальном времени, которая состоит из следующих блоков генератор рабочих таблиц (ГРТ), генератор сетевых моделей и расписаний (ГСМР) и генератор кодов (ГК)

На вход блока Генератор рабочих таблиц подается исходный 1екст РВ-программы, которая написана на языке сборки композиции моделей и в которой пользователь описывает, как следует объединить имеющиеся подмодели в комплексную модель Каждая подмодель должна быть оформлена в виде прикладного модуля

Генератор рабочих таблиц выполняет следующие функции

1 Осуществляет синтаксический анализ конструкций РВ-программы

2 Выдает сообщения о наличии ошибок в РВ-программе

3 Генерирует таблицы данных для работы последующих блоков

4 Вычисляет размеры буферов обмена данными программных модулей Генератор сетевых моделей и расписаний (ГСМР) выполняет следующие функции

1 Строит математическую модель вычислений в виде графа, в котором вершины соответствуют прикладным модулям, а дуги определяют частичный порядок их активизации

2. Определяет директивные интервалы выполнения прикладных модулей

3. Определяет, существует ли допустимое расписание выполнения прикладных модулей, и строит его, если оно существует

4 Определяет необходимое количество копий для каждого прикладного модуля

5 Вычисляет размеры буферов для входных параметров прикладных модулей

6 Назначает стеки прикладным модулям для работы с данными

В главе подробно описываются математические алгоритмы, лежащие в его основе ГСМР, а именно.

• алгоритм построения сети модулей,

• алгоритмы вычисления и коррекции директивных интервалов,

• алгоритмы проверки существования допустимого расписания выполнения модулей и его построения (при положительном ответе на первый вопрос),

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

на многочисленных примерах, в частности, на примере решения задачи регрессионного анализа

В главе 4 описывается управляющая программа САПР «СРВ-Конструктор»

Работу в реальном времени прикладной программы пользователя, сгенерированной на этапе предварительной обработки, должна обеспечить управляющая программа (УП) Основные функции УП описаны ниже

Хотя операционная система MS-DOS в чистом виде не позволяет организовать многозадачность, но, в отличие от известных систем, предназначенных для этих целей (Unix, OS/2 и т п), она обладает такими несомненными достоинствами, как надёжная файловая система и простота использования Существует множество компиляторов для языков высокого уровня, рассчитанных на работу в среде MS-DOS В силу этих соображений, выбор был остановлен на MS-DOS и сосредоточены усилия на создании приемлемой многозадачной оболочки реального времени

Управляющую программу удалось реализовать в виде многозадачной надстройки над операционной системой MS-DOS версии 3 30 и выше на основе многозадачной оболочки реального времени CTask-RT, прототипом которой послужил распространяемый бесплатно пакет Т Вагнера CTask-RT позволяет создать программную среду, использующую многозадачные элементы BIOS IBM PC/AT, обойти барьеры нереентерабельности MS-DOS и дает возможность работать совместно с резидентными (TSR) программами и под управлением оболочки MS-Windows

Следует заметить, что написанная Управляющая программа достаточно мобильна, т е может быть перенесена на другие операционные системы и машины, поскольку почти 90% кода программы написано на языке Си

Управляющая программа является составной частью исполняемого ЕХЕ-модуля РВ-программы и выполняет следующие функции

• прием, хранение и обработка поступающей извне информации (кадров данных),

• реакция на внешние апериодические сигналы,

• исполнение команд, вводимых с клавиатуры консоли;

• переключение между условными и простыми заданиями в соответствии со значениями системного вектора условий,

• запуск процессора согласно директивным срокам и приоритетам,

• обмен данными между процессами,

• действия по завершению работы процесса

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

• интерпретатор команд,

• диспетчер (ядро),

• монитор данных,

• драйверы внешних устройств

Интерпретатор команд обеспечивает интерфейс между оператором и системой РВ Он представляет собой систему меню, работа с которой возможна как с помощью клавиатуры, так и посредством «мыши»

Примерная схема сеанса работы интерпретатора управляющей программы может быть следующей После запуска ЕХЕ-модуля РВ-программы начинает работать интерпретатор команд На экране появляется главное меню Выбор из меню осуществляется либо нажатием «горячей» клавиши подсвеченной буквы, либо мышью Сначала доступны для выбора поля StartUp и Quit, что соответствует запуску и выходу из системы После выбора StartUp появляется подменю с полями Overview, Help, Info, Install & Run, посредством которых можно получить дополнительную информацию по системе или начать работу.

Функция диспетчера - активизация и запуск на счет процессов в соответствии с приоритетами, которые определяются блоком ГСМР при составлении расписания

Множество процессов PB-программы состоит из процессов реакции на внешнее апериодическое сообщение (по одному на каждое УЗ), основных процессов ПЗ и фоновых процессов УЗ

Каждый процесс состоит из блока управления процесса (шапки) и тела процесса (Е-модуля) Е-модули создаются блоком генератора кодов согласно математической модели В блоке управления содержится вся информация о параметрах процесса типы параметров вызова, их имена и, возможно, параметры глубины по времени выборки данных

При запуске процесса блок управления получает управление, генерирует запрос монитору данных, получает требуемые параметры, после чего запускает процесс После окончания выполнения процесса управление передается в блок управления, который вновь генерирует запрос монитору данных на передачу данных от процесса к потребителю. После передачи данных процесс завершает работу

Монитор данных обеспечивает прием и хранение кадров данных, поступающих в систему извне с помощью драйверов внешних устройств, поставку этих параметров процессам, обмен данными между процессами, изменение системного вектора условий и флагов готовности/ ожидания фоновых процессов

Драйверы внешних устройств позволяют принимать по прерываниям или/ и посредством последовательного опроса приходящие извне кадры данных и поставляют их монитору В настоящее время реализован следующий стандартный набор драйверов внешних устройств драйверы клавиатуры, принтера и последовательного порта (через который по умолчанию поступают внешние данные) Могут обслуживаться несколько печатающих устройств и коммуникационных портов Для подключения нестандартного оборудования нужно лишь добавить соответствующий драйвер, что обеспечивает достаточную гибкость системы

В главе 5 описывается генерация кода, сборка и запуск программного комплекса «СРВ-Конструктор»

Ранее уже упоминалось, что различают подготовительный этап использования «СРВ-Конструктора», по окончании которого генерируется готовая к

выполнению прикладная PB-программы, и этап работы в самом режиме реального времени полученной программы

Для запуска подготовительного этапа от пользователя требуются

- прикладные модули, написанные на языках программирования С, FORTRAN, PASCAL, ASSEMBLER (в формате компиляторов фирмы Microsoft V 6 0,

- задание на обработку информации в реальном времени, написанное на входном языке СРВ-Конструктора

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

Общая схема предварительного этапа показана на рис 2

Предварительный этап работы системы «СРВ-Конструктор» включает последовательный вызов следующих обрабатывающих программных комплексов

- компилятора для трансляции исходного текста PB-программы, формат обращения lang <имя_РВ-программы rts>,

Рис 2 Последовательность проектирования ВСРВ с помощью СРВ-Конструктора

- программы вывода диагностики и сообщений об ошибках при компиляции, помещаемых компилятором в файл <имя_РВ-программы Ы> (предусмотрен анализ более 70 типов ошибок), формат обращения- spl,

- программы генерации сетевых моделей и расписаний, формат обращения _gsm_gr,

- программы генерации кодов, формат обращения _cd_gnr

Далее осуществляется трансляция полученных модулей с помощью компилятора фирмы Microsoft С (6 0) и сборка готового модуля прикладной программы реального времени с помощью стандартного компоновщика связей фирмы Microsoft link Файл с расширением <имя_РВ-программы 1гГ>, ис-почьзуемый при работе данного компоновщика (включает перечень предназначенных для сборки файлов), создается автоматически

Для выполнения расписания может понадобиться создание копий некоторых прикладных модулей пользователя Список пар имен таких модулей (имеющееся имя и то, которое необходимо создать) выдается в файл «_cg_user 1st». Для успешной работы компилятора необходим также ряд вспомогательных файлов

Блок генерации кода выполняет следующие функции

1 Формирует на языке Си и записывает в текущии каталог исходные тексты получившейся программы

2 Создает ряд вспомогательных файлов для последующих определенных действий пользователя, компиляции и редактирования связей

В шестой главе дается формальная постановка задачи построения оптимального по быстродействию расписания выполнения М независимых заданий на N процессорах в системе реального времени Рассматривается случай выполнения заданий без прерываний Производительность каждого процессора считается в одном случае одинаковой, затем рассматривается более общий случай с различной производительностью процессоров

Постановка задачи для случая процессоров одинаковой производительности. Имеется М независимых заданий и N идентичных процессоров, на каждом из которых может выполняться одновременно не более одного задания В фиксированный момент времени каждое задание выполняется не более чем одним процессором Задания выполняются без прерываний и переключений с одного процессора на другой Для каждою задания г известна длительность t¡ его выполнения Необходимо определить такое распределение заданий по процессорам, чтобы время выполнения всей совокупности заданий (от начала первого до завершения последнего) было минимальным

Эту задачу можно описать следующим образом Т -» шш,

м _

Еч" VI

N

1 = 1,м,

*„ = {0,1},

где Г - время выполнения всей совокупности заданий, х, = 1, если г-е задание распределено нау-й процессор, - 0 в противном случае

Постановка задачи для случая процессоров различной производительности. Имеется М независимых заданий и N процессоров, которые могут отличаться производительностью На каждом процессоре одновременно может выполняться не более одного задания В фиксированный момент времени каждое задание выполняется не более чем одним процессором Задания выполняются без прерываний и переключений с одного процессора на другой Объем работы по выполнению задания г равен (2, Производительность процессора у равна 5, Таким образом, если г-е задание выполняется процессором ] в течение интервала /у, то (?, = •

Будем считать, что задания упорядочены по не возрастанию объемов их работ йх>йг> > 0,м, а процессоры упорядочены по не возрастанию их производительностей: > 52 > >

Требуется определить такое распределение заданий по процессорам, чтобы время выполнения всей совокупности заданий (от начала первого до завершения последнего) было минимальным

Эту задачу можно записать следующим образом: Т—> пнп, \

ху<Т, 7=Щ

м

X

в,

Л

1>у=1, 1 = 1, К (2),

= {0Д>, г = Ц*, у = Щ

где т- время выполнения всей совокупности заданий, ху = 1, если г-е задание распределено на/-Й процессор, ху=0 в противном случае

Обе сформулированные выше задачи, как показано в литературе, являются ИР-труднымя в сильном смысле

Приводится обзор существующих методов решения поставленных задачи Основное внимание уделено следующим известным методам

• алгоритмы случайного поиска (ненаправленного, направленного, с самообучением),

• алгоритмы детерминированной коррекции расписаний,

• алгоритмы имитации отжига,

• генетические алгоритмы,

• алгоритмы агрегирования

На основе обзора сделан вывод, что с учетом особенностей задач целесообразно совершенствовать методики построения расписаний по всем указанным направлениям В силу научных интересов автор сосредоточил внимание на новых эвристических алгоритмах

В седьмой главе подробно изложены предлагаемые эвристические алгоритмы

Решение задачи 1 (для случая одинаковых процессоров)

При работе эвристического алгоритма вычисляется идеальная оценка

м

I* = времени завершения всей совокупности заданий, а также ее ка-

г=1

либрованное значение I Под калибровкой понимается увеличение величины /* на некоторое число процентов, причем алгоритм запускается с разными значениями калибровки и выбирается лучшее достигнутое для рассматриваемого набора входных данных решение.

Эвристический алгоритм 1.

а) Отсортировать задания по не возрастанию длительностей, т е будет выполняться соотношение /г > г = 1, ,М-1

б) Вычислить величины * * и 1.

в) Распределять на каждый процессор у, начиная с первого, нераспределенные ранее задания до тех пор, пока суммарная длительность заданий на каждом процессоре не будет превышать величины I. При этом сначала максимально нагружается текущий выбранный процессор, а лишь затем происходит переход к загрузке заданий следующего. Если в какой-то момент при попытке распределить очередное задание на процессор происходит превышение величины I, то сначала производится попытка распределения на тот же процессор оставшихся нераспределённых заданий вплоть до наименее трудоёмкого (также с не превышением величины Г) и только потом - переход на загрузку следующего процессора (для каждого у = 1,..., N определять

м

Ху = 1 до тех пор, пока <1 для Данного у).

1=1

г) Определить номер к* процессора, для которого суммарная длительность заданий, назначенных на него, минимальна, т.е.

м

к* = а^(тт ) (2)

д) Распределить на этот процессор самое длинное из ранее не распределённых заданий.

е) Повторять выполнение пунктов (г) и (д) до тех пор, пока не все задания распределены.

Результаты ряда экспериментов с эвристическим алгоритмом 1 приведены на рис. 3.

М/М (от 5,15 до 7,68)

□ Ряд1 || | В Ряд2'

Рис. 3. Результаты ряда экспериментов с эвристическим алгоритмом 1 Ряд 1 (я) — эвристический алгоритм 1 лучше, чем «жадный». Ряд 2 (■) - результаты совпадают.

Контрольные алгоритмы. Для сравнительного контроля качества получаемых предложенными алгоритмами решений использован известный «жадный» алгоритм распределения заданий. Как уже упоминалось, он состо-

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

Для оценки качества получаемых решений при малых размерностях задачи использовался и метод полного перебора вариантов распределения заданий по процессорам Этот алгоритм хорошо известен и не требуется его описание в подробностях Оценка его трудоемкости составляет величину порядка 0(lf)

Таким образом, оценки трудоемкостей обсуждаемых эвристических алгоритмов определяются трудоемкостью предварительной сортировки и, в зависимости от выбранного метода, составляют либо 0(М2), либо 0(М log М), соответственно Оба вида сортировки используются в связи с тем, что при малых М (М < 14), трудоемкость сортировки методом пузырька оказывается ниже, чем сортировки разделением-слиянием.

Решение задачи 2 (для случая различных процессоров)

Описание жадного алгоритма.

1 Пусть Lj - длина временного интервала загруженностиу-го процессора

2 Положить Lj-О Vj = l^V.

3 Назначить первое задание на первый процессор и lj ~QiIS1

4 Для каждого г = 2,М выполнять шаги 5-7

5 Положить Rj = max(Ц,L2, ,Lj_x,{Lj +Q,ISj), LJ+\, ,Ьы)дш

6 Вычислить R, = mm R,

Jo ПГ7 J

7 Назначить задание i на процессор j0. LJo - LJo + Qt /SjQ

Описание эвристического алгоритма 2.

При работе эвристического алгоритма вычисляется нижняя оценка

'* = (ХбЛ/ времени завершения всей совокупности заданий, а также

,=1 J=l

ее калиброванное значение Г. Под калибровкой понимается увеличение величины (* на некоторое значение, причем алгоритм запускается с разными значениями калибровки и выбирается лучшее достигнутое для данного набора входных данных решение В качестве значения верхней оценки Тс длины расписания используется время выполнения всей совокупности заданий, полученное «жадным» алгоритмом для соответствующих данных

Алгоритм распределения заданий.

1) Вычислить величины Тс Пусть К - заданное число (значение параметра) Алгоритм запускается для следующих значений I

N

2) Распределять на каждый процессор /, начиная с первого, нераспределённые ранее задания до тех пор, пока суммарная длительность заданий на каждом процессоре не будет превышать величины I. При этом сначала максимально загружается текущий выбранный процессор, а лишь затем происходит переход к загрузке заданий следующего. Если в какой-то момент при попытке распределить очередное задание на процессор происходит превышение величины I, то сначала производится попытка распределения на тот же процессор оставшихся нераспределённых заданий вплоть до наименее трудоёмкого (также с не превышением величины г) и только потом - переход на загрузку следующего процессора (для каждого у = 1,..., N определять м о

Хц = 1 до тех пор, пока < ( Для данного /). Для каждого у" вычислить

¡=1 5 у

величину X,.

3) Назначить оставшиеся ранее нераспределённые задания согласно пп. 3-5 «жадного» алгоритма.

Для предложенных алгоритмов даётся оценка точности их вычислений. Приводятся результаты серии расчётов по данным алгоритмам и сравнительный анализ последних.

Результаты ряда экспериментов с эвристическим алгоритмом 2 приведены на рис. 4.

120,00% 100,00%

I

80,00%

I

60,00% 40,00% 20,00% 0,00%

Рис. 4. Результаты ряда экспериментов с эвристическим алгоритмом 2

тах"~ = 2 V .Л,Л

1г

Проведенные эксперименты показали, что с используемыми механизмами калибровки (а) мультиоценочный алюритм целесообразно применять при соотношении числа заданий к числу процессоров, не превосходящем 7 (б) в дополнение к мультиоценочному алгоритму следует использовать также и «жадный» алгоритм, поскольку оба алгоритма работают достаточно быстро и при разных данных могут давать различные по точности результаты

В Приложении 1 приведен пример применения САПР ВСРВ для решения в реальном времени задачи многомерной линейной регрессии

В Приложении 2 - тексты программной реализации предлагаемых эвристических алгоритмов для многопроцессорного варианта САПР «СРВ-Конструктор»

В заключении сформулированы основные теоретические и практические результаты диссертационного исследования

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

Основные результаты диссертационной работы заключаются в следующем

] Для однопроцессорных персональных ЭВМ типа IBM PC создан инструментальный программный комплекс автоматизации проектирования систем реального времени «СРВ-Конструктор», позволяющий в автоматизированном режиме проектировать вычислительные системы реального времени В рамках создания данной САПР решены следующие задачи

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

• трансляции этой программы (используется разработанная в ВЦ РАН система построения компиляторов «Супер»),

• автоматического определения наличия допустимого расписания выполнения поставленной задачи,

• генерации кодов и сборки исполнимых модулей готовой к выполнению ВСРВ

2 С целью дальнейшего совершенствования указанной САПР для многопроцессорных вычислительных комплексов разработаны и реализованы новые эвристические алгоритмы решения задачи построения оптимального по быстродействию расписания без прерываний Данные алгоритмы основаны на мультиоценке и калибровке получаемых результатов и выборе наилучшего среди сгенерированных результатов

Основные результаты диссертации опубликованы в работах:

1 Сушков Б Г, Фуругян МГ, Гончар ДР, Кондратьев О Л Методология и программные средства мониторинга чрезвычайных ситуаций //Тез докл конф "Проблемы управления в чрезвычайных ситуациях", Москва, ИПУ РАН, 1992,2 с

2 Сушков Б Г, Фуругян МГ, Гончар ДР, и др САПР систем реального времени на базе IBM PC "СРВ-конструктор" //Тез докл III научной школы "Авто-

матизация создания мат обеспечения и архитектуры систем реального времени" Саратовский филиал Института машиноведения РАН, Саратов, 1992,2 с

3 Гончар Д Р, САПР систем реального времени для IBM PC (сборник трудов) М, ВЦ РАН, 1993,5 с

4 СушковБГ, Фуругян МГ, Гончар ДР, и dp САПР вычислительных систем реального времени для IBM PC // Тез межд конф "Проблемы регионального и муниципального управления" Москва РГГУ, 1999, 1 с

5 Сушков Б Г, Фуругян МГ, Гончар ДР, и dp Система автоматизации программирования вычислительных систем реального времени - В сб "Теория и реализация вычислительных систем реального времени" М ВЦ РАН, 1999, 8 с

6 Сушков БГ, Белый Д В , Фуругян МГ, Гончар ДР, Кондратьев О Л и dp Автоматизация программирования вычислительных систем реального времени //В сб Моделирование обработки информации и процессов управления М МФТИ, 2000, 10 с

7 Gonchar D, Fourougyan М The decision of one problem of distribution of resources at presence of uncertain factors Тез 3-й Моек межд конф по исследованию операций Москва. ВЦ РАН, 2001 г, 1 с

8 Гончар ДР, Фуругян МГ Автоматизация проектирования систем реального времени для испытаний и мониторинга сложных технических объектов - Материалы 9-й межд конф "Проблемы управления безопасностью сложных систем", М, ИПУ РАН, 2001,4 с

9 Гончар Д Р, Фуругян МГ Алгоритмы анализа и синтеза многопроцессорных систем реального времени Тез конф "Математические модели сложных систем и междисциплинарные исследования" М ВЦ РАН, 2002 1 с

10 Гончар Д Р, Эвристические алгоритмы распределения заданий в многопроцессорной системе реального времени Труды XLV науч конф МФТИ (ГУ), 2002 г, часть VII, М -Дол1 опрудный МФТИ, 2002 1 с

11 Гончар ДР, ГузДС, Красовский ДВ, Фуругян МГ Эффективные алгоритмы планирования вычислений в многопроцессорных системах // Проблемы управления безопасностью сложных систем Труды 10-й международной конференции Книга2 /ИПУ РАН -М, 2002-С 207-211

12 Дадашев ТМ, Рубаев В Ю, Белоусов О Л, Гончар ДР Введение в реляционные базы данных и язык SQL Долгопрудный Вестком, 2002, 287 с

13 Серебряков В А, Галочкин МП, Гончар ДР, Фуругян МГ Теория и реализация языков программирования М МЗ-Пресс, 2003 286 с

14 Гончар ДР Мультиоценочный эвристический алгоритм распределения М заданий на N процессоров// Моделирование процессов управления М МФТИ, 2004-С 170-173

15 Гончар ДР Мультиоценочный эвристический алгоритм распределения М заданий на N одинаковых процессорах // В сб Процессы и методы обработки информации М МФТИ, 2005 3 с

16 Гончар ДР Мультиоценочный эвристический алгоритм распределения М заданий на N процессоров // II Всероссийская научная конференция «Методы и средства обработки информации» М МГУ, 2005 С 537-539

17 Гончар ДР Мультиоценочный эвристический алгоритм распределения М заданий на N процессоров // Сообщения по прикладной математике М ВЦ РАН, 2005,16 с

18 Серебряков В А , Галочкин МП, Гончар ДР, Фуругян МГ Теория и реализация языков программирования Изд2-е, испр идоп М МЗ Пресс, 2006, 350 с

19 Гончар ДР Мультиоценочный алгоритм решения минимаксной задачи составления расписания // Системы управления и информационные технологии № 1 3 (27), 2007 Москва-Воронеж Научная книга, 2007. С 324-328

20 Фуругян МГ, Гончар ДР Мультиоценочный алгоритм решения минимаксной задачи составления расписания // Проблемы управления безопасностью сложных систем Труды ХУ-й международной конференции Часть 2 /ИГ1У РАН -М, 2007-С 149-153

При построении инструментальной системы «СРВ-Конструктор» были приняты за основу и использованы после соответствующей переработки ряд разработок по предыдущей версии данной системы для ЕС ЭВМ, а именно формальный язык описания пользовательской СРВ для системы «СРВ-КОНСТРУКТОР», система автоматизированного построения компиляторов «Супер», ряд конкретных, специфичных для СРВ технических решений (при организации монитора реального времени, генерации кода итп)

Сама идея создания САПР «СРВ-Конструктор» (и реализация для ЕС ЭВМ) принадлежит основателю сектора проектирования ВСРВ Сушкову Б Г Идеи некоторых эвристических алгоритмов выдвинуты совместно с М Г Фу-ругяном В совместных работах автору принадлежит теоретическая часть, постановки задач, разработка, испытания и исследования предложенных в диссертации подходов и алгоритмов В А Серебряков и М П Галочкин принимали участие в разработке вышеупомянутой системы «Супер» О Л Кондратьеву, Д В Белому, Д С Гузу и Д В Красовскому принадлежит рассмотрение ряда других алгоритмов управления и анализа систем реального времени, не вошедших в данную диссертацию

МЕТОДЫ ПЛАНИРОВАНИЯ ВЫЧИСЛЕНИЙ В САПР СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ

Подписано в печать Формат 60x84 1/16 Бумага офсетная Уел печ л 1,0 Тираж 100 экз Заказ №

ЛИЧНЫИ ВКЛАД

Гончар Дмитрий Русланович

ВВЕДЕНИЕ

ГЛАВА 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. СИСТЕМА АВТОМАТИЗИРОВАННОГО СИНТЕЗА МОДЕЛИ

ВСРВ. ГЕНЕРАТОР СЕТЕВОЙ МОДЕЛИ И РАСПИСАНИЙ

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. УПРАВЛЯЮЩАЯ ПРОГРАММА САПР «СРВ-КОНСТРУКТОР»

4.1. Выбор операционной среды

4.2. Основные функции управляющей программы

4.3. Структура управляющей программы

4.3.1. Интерпретатор команд

4.3.2. Диспетчер

4.3.3. Монитор данных

4.3.4. Драйверы внешних устройств

ГЛАВА 5. ПРОГРАММНЫЙ КОМПЛЕКС «СРВ-КОНСТРУКТОР»

5.1. Сборка и запуск программного комплекса «СРВ-Конструктор»

5.2. Генератор кодов.

ГЛАВА 6. ПЛАНИРОВАНИЕ РАСПИСАНИЙ ДЛЯ МНОГОПРОЦЕССОРНОГО ВАРИАНТА СИСТЕМЫ «СРВ-КОНСТРУКТОР». ЗАДАЧА РАСПРЕДЕЛЕНИЯ М ЗАДАНИЙ НА N ПРОЦЕССОРОВ

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. Эври стический алгоритм

7.1.2. Контрольный алгоритм

7.1.3. Контрольный алгоритм

7.1.4. Сравнительные итоги расчётов по алгоритму 1 с разными процентами калибровки

7.2. Решение задачи 6.2 (для случая различных процессоров)

7.2.1. Описание жадного алгоритма

7.2.2. Описание эвристического алгоритма

7.2.3. Вычислительные эксперименты и рекомендации к применению

Вычислительные системы реального времени (ВСРВ) предназначены для контроля и управления при жёстких временных ограничениях процессами в автоматизированных производствах, в энергетике (особенно ядерной), химической промышленности, газо- и нефтедобыче, авиационном, железнодорожном и морском транспорте, в системах управления лётными испытаниями, при управлении в чрезвычайных ситуациях. Сегодня ВСРВ всё шире применяются в управлении дорожным движением автотранспорта, экологическом и медицинском мониторинге, разнообразных системах безопасности.

Изменился и диапазон масштабов разрабатываемых ВСРВ, с одной стороны (с учётом новых возможностей и большей доступности сетевых технологий) расширившись с масштаба цеха или предприятия до масштабов отрасли, государства и международных систем (например, спасания на море), с другой - став доступными на уровне бортового компьютера для серийного современного автомобиля.

Одновременно с увеличением масштабов и разнообразия применений ВСРВ становятся более высокими требования к их эффективности, надёжности и скорости разработки. Удовлетворить этим отчасти противоречивым требованиям представляется возможным, прежде всего, путём выхода на более высокий уровень автоматизации построения систем реального времени, созданием соответствующих эффективных, надёжных и удобных инструментов их программирования.

Одним из практически важных и весьма распространённых случаев ВСРВ является ВСРВ с периодически поступающей на обработку входной информацией (см. рис. 1.1). Если при этом возможна приемлемая для данного приложения точность оценки времени на обработку входной инфор

Рис. 1.1. Схема использования ЭВМ для управления физическими процессами. Потоки информации и аппаратные средства типичной многоканальной системы сбора данных и управления представляются на различных устройствах отображения (дисплеях и т.п.) и, кроме того, если необходимо, вырабатываются управляющие воздействия, которые после соответствующих преобразований поступают к объекту, управляя его функционированием. АЦП — аналогово-цифровой преобразователь. ЦАП — цифро-аналоговый преобразователь. УВХ -устройства выборки-хранения аналогового сигнала. мации, возникает возможность разбиения процесса работы ВСРВ на две стадии - предварительную и основную.

При этом на предварительной стадии и не в режиме реального времени первоначально описывается (например, средствами специально построенного для этих целей формального языка) состав и периодичность поступающей информации, соответствующие модули-обработчики, последовательность обработки данных, директивные сроки обработки тех или иных данных и допустимость прерывания этой обработки и т.д. Затем (с учётом необходимой синхронизации процессов обработки, предотвращения программных тупиков и учёта иных особенностей программируемых ВСРВ) автоматически рассчитывается допустимое расписание работы ВСРВ (либо делается вывод о невозможности существования такого расписания), составляется с использованием средств автоматизации программирования программа выполнения режима реального времени, обеспечивается создание нужного количества копий программных модулей обработчиков входных и промежуточных данных ВСРВ (с учётом возможности одновременной обработки нескольких поколений входных данных), создание средств связи между этими модулями и операционной системой (ОС) реального времени и т.п., а на основном этапе производится собственно выполнение полученной ВСРВ в режиме реального времени.

Именно такой подход, позволяющий не только качественно повысить эффективность, скорость и надёжность разработки (настройки, усовершенствования) ВСРВ, но и существенно расширить возможный диапазон и сложность решаемых задач (особенно при управлении быстропроте-кающими процессами) был предложен в ВЦ АН СССР лауреатом Премии СМ СССР, к.ф.-м.н. Борисом Григорьевичем Сушковым (1941-1997) для ЕС ЭВМ.

Уже в 90-е годы была понята актуальность и важность разработки подобной системы для персональных ЭВМ. Такая инструментальная система автоматизации программирования (САПР) «СРВ-Конструктор» была создана при непосредственном существенном участии автора диссертации и подробно представлена в данной работе.

Важной составляющей инструментальной САПР «СРВ-Конструктор» является блок, определяющий существование допустимого расписания и (если оно существует) выполняющий его построение. Понятно, что для многопроцессорных вычислительных комплексов важность и, в то же время, сложность этого блока только возрастает. Поэтому большое внимание в диссертации уделено разработке алгоритмов построения расписания для ряда важных частных случаев, часто встречающихся в работе подобных многопроцессорных систем.

В наиболее общей формулировке задачи составления расписаний состоят в следующем. С помощью допустимого набора ресурсов или обслуживающих устройств должна быть выполнена система заданий. Цель заключается в том, чтобы при известных свойствах заданий и ресурсов и наложенных на них ограничениях найти эффективный алгоритм упорядочения заданий, оптимизирующий желаемую меру эффективности. В качестве меры эффективности обычно рассматривается длина расписания или среднее время пребывания заданий в системе. Модели этих задач являются детерминированными в том смысле, что вся информация, на основе которой принимаются решения об упорядочении, известна заранее. В частности, задания и все данные о них предполагаются известными в начальный момент времени.

Системы жёсткого реального времени - это такие системы, в которых некоторым заданиям сопоставляются директивные сроки (наиболее ранний момент начала выполнения задания и наиболее поздний момент окончания выполнения), не подлежащие нарушению. Для обеспечения работоспособности и надёжности таких систем необходимо иметь заранее рассчитанное расписание работы всей системы. В данной работе рассматриваются, в частности, эффективные алгоритмы составления расписаний для многопроцессорных систем жёсткого реального времени.

Применение таких систем позволяет уменьшить число отказов сложных технических систем. Во многих случаях управления производством или сложными техническими системами целесообразно применение различного рода систем мониторинга в реальном масштабе времени.

В качестве иллюстрации важности временных ограничений на работы в системах жёсткого реального времени можно привести следующие примеры:

1. Системы управления ядерными энергетическими (АЭС) или силовыми установками.

2. Системы управления технологическими цепочками в целом ряде производств химической промышленности.

3. Системы раннего обнаружения и отслеживания (мониторинга) опасных природных явлений (землетрясений, цунами, наводнений и т.п.)

4. Системы мониторинга существенных параметров экологической и экономической обстановки.

5. Разнообразные бортовые системы управления и испытаний транспортных систем, особенно в авиации и космонавтике.

6. Весьма распространённой ныне является задача рационального подбора конфигурации самих ЭВМ и локальных вычислительных сетей (ЛВС) на их основе, в том числе в реальном времени (без остановки вычислительного процесса), которая в свою очередь распадается на целый ряд ещё более частных задач, например, таких, как определение оптимальной/ рациональной последовательности запуска вычислительных заданий на данной конфигурации вычислительных средств.

7. При составлении учебного расписания ВУЗа необходимо учесть разнообразие специальностей учебных групп, разнообразные ограничения с точки зрения служебных обязанностей, человеческих возможностей и интересов студентов, преподавателей, иного обслуживающего персонала, наличных помещений и оборудования. При этом должны учитываться директивные сроки проведения занятий и завершения освоения запланированных курсов. Вышеперечисленные обстоятельства обусловливают актуальность исследований в области дальнейшего совершенствования методов оперативного планирования, в том числе расчёта и составления рациональных или (если возможно и оправданно) оптимальных расписаний в указанных областях. В том числе с использованием таких инструментальных средств как ВСРВ «СРВ-Конструктор».

Многие варианты задач составления многопроцессорного расписания являются NP-трудными. Принимая во внимание трудность задачи, любая практическая реализация составления многопроцессорного расписания - это всегда своеобразный компромисс между результатом и вычислительной сложностью. Поэтому вопрос составления более эффективных эвристических алгоритмов, в том числе для конкретных видов задач составления расписаний, является в настоящее время достаточно актуальным для рассматриваемой предметной области.

Создание и использование ВСРВ стало актуальной задачей при появлении достаточно надёжной и мощной вычислительной базы, что, как известно, произошло к 70-х годам XX в. С этого времени изучению математических вопросов теории расписаний и её приложений исследователи уделяют повышенное внимание.

В России, а до того в СССР, задачей построения расписаний в системах реального времени занимались Танаев В.С.[1], Барский А.Б.[2], Головкин Б.А.[3], Сушков Б.Г.[4, 5, 6 и др.], Шкурба В.В.[7], Гордон В.С.[1], Костенко В.А.[8], Лазарев А.А.[9], Мищенко A.B. [10], Португал В.М.[11], Сигал И.Х.[12, 13,14], Шафранский B.C. [1] и др.

Среди зарубежных учёных следует отметить Бернса (Burns)[15], Брукера (Bruker)[16], Гонзалеса (Gonzales) [17], Греневельта (Groenevelt) [18], Гэри М. (Garey)[19], Дертузоса (Dertouzos)[20], Джонсона Д. (Johnson)[19], КонвеяР.В. (Conway)[21, 22], КорменаТ. (Cormen) [23],

Коффмана (Koffman)[24, 25], Лью(Ьш)[26], Лейланда (Layland)[26], Лей-зерсона 4.(Leiserson) [23], Максвелла В.Л.(Maxwell) [21, 22], Мартеля (Martel)[27], Миллера Л.В. (Miller) [21,22], Мока (Mok)[28], Одели (Aud-sley) [29], Рамамритама (Ramamritham)[30], Ривеста T. (Rivest) [23], Ричардсона (Richardson)[29], Сахни (Sahni)[17], Станковича (Stankovic)[30, 31 ], Ульмана Дж.(иНшап) [32], Федергрюна (Federgruen) [ 18]

Считаю своим долгом выразить благодарность Ю.А.Флёрову, М.Г.Фуругяну, О.Л.Кондратьеву, A.B.Сухих, О.С.Федько и С.Н.Мирошнику за помощь в работе и обсуждение полученных результатов.

Цели и задачи исследования.

Основной целью диссертационной работы является разработка программного комплекса инструментальной САПР «СРВ-Конструктор» для персональных электронно-вычислительных машин, а также новых методов составления расписаний, предназначенных для функционирования на многопроцессорной ВС. Эти методы можно включить в состав программных средств, предназначенных для осуществления планирования вычислений на вычислительных системах, в том числе системах жёсткого реального времени.

Для достижения поставленной цели:

- создан программный комплекс, реализующий инструментальную САПР «СРВ-Конструктор»;

- с целью дальнейшего совершенствования указанной САПР для многопроцессорных вычислительных комплексов разработаны и реализованы новые эвристические алгоритмы решения задачи построения оптимального по быстродействию расписания без прерываний.

СРВ-Конструктор состоит из:

Блока синтаксического и семантического анализа, осуществляющего синтаксический и семантический анализ конструкций программы и др.

Б.Г.Сушкову, реального времени (РВ-программы), описывающей на формальном языке необходимый порядок выполнения прикладных программ пользователя, генерирующего таблицы данных для работы последующих блоков и вычисляющего размеры буферов обмена данными между программными модулями.

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

Блока генерации кода, формирующего на языке С и записывающего в текущий каталог исходные тексты получившейся программы, а также создающего ряд вспомогательных файлов для последующих определённых действий пользователя, компиляции и редактирования связей.

Управляющего монитора на основе многозадачной оболочки реального времени СТазк-ЯТ, обеспечивающего работу в реальном времени прикладной программы пользователя, сгенерированной на этапе предварительной обработки посредством САПР ВСРВ.

Предмет исследования.

В соответствии с поставленной целью предметом исследования является методология построения инструментальной САПР систем реального времени. Это включает в себя разработку формального языка для описания системы реального времени, построение алгоритмов нахождения допустимого расписания выполнения прикладных модулей для однопроцессорных и многопроцессорных вычислительных комплексов, генерацию кода соответствующей инструментальной САПР системы реального времени и управления в реальном времени.

Методологическую и теоретическую основу исследования составили методы разработки систем реального времени, теории расписаний, комбинаторной оптимизации и теории графов.

Научная новизна.

Научная новизна диссертационной работы заключается в построении инструментального программного комплекса, дающего новые качественные возможности при автоматизации построения систем реального времени с периодическим поступлением входной информации, в том числе разработку алгоритмов построения расписаний работ для многопроцессорной вычислительной системы.

В процессе исследования автором было выполнено следующее:

- разработана и программно реализована инструментальная система САПР «СРВ-Конструктор», включающая язык реального времени, блоки синтаксического и семантического анализа, блок генерации сетевой модели и расписаний, блок генерации кода и управляющий монитор;

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

- на основе многочисленных вычислительных экспериментов получены апостериорные оценки точности разработанных алгоритмов;

Практическая значимость, апробация и внедрение результатов работы.

Основные результаты исследования относятся к созданию нового инструментального программного комплекса САПР «СРВ-Конструктор» для однопроцессорных ПЭВМ и разработке ряда эффективных эвристических алгоритмов оптимизации планирования вычислений в системах реального времени для многопроцессорных вычислительных комплексов для дальнейшего развития системы САПР «СРВ-Конструктор».

Результаты данного исследования обсуждались и докладывались на:

- III научной школе "Автоматизация создания математического обеспечения и архитектуры систем реального времени" (Саратовский ф-л Института машиноведения РАН, Саратов, 1992);

- межд. конф. "Проблемы управления в чрезвычайных ситуациях" (М., ИПУ РАН, 1992);

- межд. конф. "Проблемы регионального и муниципального управления" (М.: РГГУ, 1999);

- IX и X межд. конф. "Проблемы управления безопасностью сложных систем" (М., ИПУ РАН, 2001 и 2002);

- III межд. конф. по исследованию операций (М., ВЦ РАН, 2001);

- науч. конф. "Математические модели сложных систем и междисциплинарные исследования" (М., ВЦ РАН, 2002);

- XLV и XLIX науч. конф. Московского физико-технического института (ГУ), (М.-Долгопрудный, 2002, 2006);

- II Всеросс. науч. конф. «Методы и средства обработки информации» (М.: МГУ, 2005);

- научных семинарах сектора проектирования систем реального времени Вычислительного центра им. A.A. Дородницына Российской Академии Наук;

- научных семинарах кафедры математических основ управления Московского физико-технического института (ГУ).

По итогам исследования опубликовано 20 работ, в том числе одна в издании, входящем в список ВАК. Список работ приведён в конце диссертации [69-88].

Данная работа может быть применена для повышения качества и эффективности проектирования и работы широкого класса систем, работающих в жёстком реальном времени и использующих периодически поступающую входную информацию.

Состав и структура работы.

Диссертация состоит из введения, семи глав, заключения, списка использованной литературы и двух приложений.

Основные результаты диссертации заключаются в следующем: 1. Для однопроцессорных персональных ЭВМ типа IBM PC создан инструментальный программный комплекс автоматизации проектирования систем реального времени «СРВ-Конструктор» для обработки периодически поступающей информации.

Для реализации этого комплекса разработаны:

• Язык реального времени, служащий для описания идущих в реальном времени процессов и предоставляющий возможность синхронизировать производимые вычисления с моментами поступления информации извне - приходами кадров данных.

• Блок синтаксического и семантического анализа, осуществляющий синтаксический и семантический анализ конструкций программы реального времени, описывающей на формальном языке необходимый порядок выполнения прикладных программ пользователя, генерирующего таблицы данных для работы последующих блоков и вычисляющего размеры буферов обмена данными между программными модулями.

• Блок генерации сетевой модели и расписаний, строящий математическую модель вычислений, выполняемых в реальном времени, в виде графа, в котором вершины соответствуют прикладным модулям пользователя, а дуги определяют частичный порядок их выполнения, определяющего директивные интервалы выполнения прикладных модулей, возможность построения допустимого расписания выполнения прикладных модулей и само расписание, если оно существует, а также выполняющего некоторые другие вспомогательные функции построения инструментальной САПР ВСРВ.

• Блок генерации кода, формирующий на языке С и записывающий в текущий каталог исходные тексты получившейся программы, а также создающий ряд вспомогательных файлов для последующих определённых действий пользователя, компиляции и редактирования связей.

• Управляющий монитор на основе многозадачной оболочки реального времени СТавк-ЮГ, обеспечивающего работу в реальном времени прикладной программы пользователя, сгенерированной на этапе предварительной обработки посредством САПР ВСРВ.

2. Для многопроцессорного варианта САПР «СРВ-Конструктор» разработаны два новых эвристических алгоритма распределения М заданий на N процессоров, основанных на мультиоценке результата. Первый алгоритм предназначен для процессоров с одинаковой производительностью. Второй - для случая, когда производительность процессоров может различаться. Проведены многочисленные машинные эксперименты, показавшие, что предложенные алгоритмы лучше известного жадного алгоритма в определённой области входных данных по точности получаемого решения. Даны рекомендации к эффективному применению данных алгоритмов.

Заключение

1. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы. - М.: Наука, 1984.

2. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. М.: Радио и связь, 1990.

3. Головкин Б.А. Расчёт характеристик и планирование параллельных вычислительных процессов. М.: Радио и Связь, 1983.

4. Логинова И.В., Сушков Б.Г. Динамическое распределение памяти в системах реального времени при имеющемся расписании центрального процессора // В сборнике «Теория и реализация систем реального времени», ВЦ АН СССР, стр. 49-69, 1984.

5. Луганский И.Л., Сушков Б.Г. Язык программирования детерминированных систем реального времени. М.: ВЦ АН СССР, 1986.

6. Сушков Б.Г ЭВМ управляет экспериментом. (Вычислительные системы реального времени.) // Новое в жизни, науке, технике. Сер. «Математика, кибернетика». -М.: Знание, 1987, N9.

7. Шкурба В.В., Селивончик В.М. Расписания, имитационное моделирование и оптимизация. Кибернетика, 1981, № 1, с. 91-96.

8. Костенко В.А., Смелянский Р.Л., Третиt А.Г. Синтез структур вычислительных систем реального времени с использованием генетических алгоритмов//Программирование, 2000, №5.

9. Лазарев A.A., Гафаров Е.Р. Теория расписаний. Минимизация суммарного запаздывания для одного прибора. М.:ВЦРАН, 2006

10. Сигал И.Х. Задача коммивояжера большой размерности // ВЦ АН СССР, 1986.

11. Сигал ИХ. Приближенные методы и алгоритмы в дискретной оптимизации // ВЦ РАН М.: Изд-во ВЦ РАН, 2000.

12. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование // ФИЗМАТЛИТ. 2002.

13. Federgruen A., Groenevelt H. "Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Technique". Management Science Vol. 32, No. 3, March 1986.

14. Гэри M., Джонсон Д. Вычислительные машины и трудно решаемые задачи // М.: Мир, 1982.

15. 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.

16. Конвей P.В., Максвелл В.Л., Миллер Л.В.«Теория расписаний», М.: Наука, 1975.

17. Кормен Т., Лейзерсон Ч., Pueecm Р. «Алгоритмы: построение и анализ» М. МЦНМО, 1999.

18. Коффман Е. До/с., Грэхем Р.Л. Теория операционных систем // М.: Наука, 1984.

19. Мок 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.

20. 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.

21. 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.

22. Stankovic J.A., et. al., Implications of Classical Scheduling Results for Real-Time Systems, IEEE Computer Society Press, 1995.

23. Ульман Дж. Полиномиально полные задачи составления расписаний // Operating Systems Review, 1973.

24. Бездушный А.Н., Лютый В.Г., Серебряков В.А. Разработка компиляторов в системе СУПЕР. М.: ВЦ АН СССР, 1991.

25. Ахо А., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии, инструменты. М.: Вильяме, 2001.

26. Microsoft С. Advanced programming techniques, 1990.38 .Held М., Karp R. A dynamic programming approach to sequencing problern. // SLAM, 1962.

27. Корбут A.A., Финкелъштейн Ю.Ю. Дискретное программирование// М. Наука. Гл. ред. физ.-мат. лит. 1969.

28. Растригин JI.A. Статистические методы поиска // М.: Наука, 1968.

29. Гончаров E.H., Кочетов Ю.А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискрет, анализ и ис-след. операций Сер. 2, 2002. Т. 9, №2. С. 13-30.

30. А2.Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискрет, анализ и исслед. операций Сер. 2, 2003. Т. 10, № 1, С. 11-44.

31. АЪ.Ьапй А.Н., and Doig A.G. An automatic method of solving discrete programming problems. // Econometrica. v. 28 (1960), pp. 497-520.

32. 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.

33. АЬ.Киселев В.Д., Карелин Д.В. Метод ветвей и границ для решения задач целочисленного квадратичного программирования с булевыми- переменными // Известия Тульского Государственного Университета, 1995, Том 1, выпуск 3, Информатика.

34. AÜ.Panwalkar S., Iskander W. A survey of scheduling rules. // Operations Research. 25(1):45-61, 1977.

35. А9.Гуз Д. С. Разработка точных и приближённых алгоритмов составления расписаний и синтеза систем жёсткого реального времени //

36. Диссертация на соискание учёной степени канд. физ.-мат. наук, М., 2005.

37. Штовба С. Д. Муравьиные алгоритмы // ExponentaPro. Математика в приложениях, № 4(4), 2003.51 .Laarhoven P., Aarts Е., Lenstra J. Job Shop Scheduling by Simulated Annealing // Operations Research, 40(1): 113-125, 1992.

38. Holland J.N. Adaptation in Natural and Artificial Systems // Aim Arbor, Michigan: Univ. of Michigan Press, 1975.

39. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs // Third, Revised and Extended Edition, Springer, 1999.

40. 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.

41. Periaux J. and Winter G. editors. Genetic Algorithms in Engineering and Computer Science // John Wiley & Sons Ltd., 1995.

42. CorneD., FangH.-L., Mellish C. Solving the Modular Exam»Scheduling Problem with Genetic Algorithms // DAI Research Paper №622.

43. 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.

44. Tsurkov V.I., Large-Scale Optimization Problems and Methods // Dordrecht, Boston, London: istent Kluwer Acad. Publ., 2001.

45. Красовский Д.В. алгоритмы решения задачи составления оптимального расписания без прерываний // Диссертация на соискание учёной степени канд. физ.-мат. наук, М., 2007.

46. Альберт А. Регрессия, псевдоинверсия и рекуррентное оценивание. М, Наука: 1977.

47. Rust В., Burrus W.Q., Schneeborder С. A simple algorithm for computing the generalized inverse of matrix. ACM. 1966, V.9.

48. Сушков Б.Г., Фуругян М.Г., Гончар Д.Р., Кондратьев О.Л. Методология и программные средства мониторинга чрезвычайных ситуаций. //Тез. докл. конф. "Проблемы управления в чрезвычайных ситуациях", Москва, ИПУ РАН, 1992, 2 с.

49. Сушков Б.Г., Фуругяи М.Г., Гончар Д.Р., и др. САПР вычислительных систем реального времени для IBM PC. // Тез. межд. конф. "Проблемы регионального и муниципального управления". Москва: РГГУ, 1999, 1 с.

50. Сушков Б.Г., Фуругян М.Г., Гончар Д.Р., и др. Система автоматизации программирования вычислительных систем реального времени. В сб. "Теория и реализация вычислительных систем реального времени". М.: ВЦ РАН, 1999, 8 с.

51. А.Сушков Б.Г., Белый Д.В., Фуругян М.Г., Гончар ДР., Кондратьев О.Л. и др. Автоматизация программирования вычислительных систем реального времени. //В сб.: Моделирование обработки информации и процессов управления. М.: МФТИ, 2000, 10 с.

52. 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.

53. Гончар Д.Р., Фуругян М.Г. Автоматизация проектирования систем реального времени для испытаний и мониторинга сложных технических объектов. Материалы 9-й межд. конф. "Проблемы управления безопасностью сложных систем", М., ИПУ РАН, 2001, 4 с.

54. Гончар ДР. Мультиоценочный эвристический алгоритм распределения М заданий на N одинаковых процессорах //В сб. Процессы и методы обработки информации. М.: МФТИ, 2005. 3 с.

55. Гончар Д.Р. Мультиоценочный эвристический алгоритм распределения М заданий на N процессоров. // II Всероссийская научная конференция «Методы и средства обработки информации». М.: МГУ, 2005. С. 537-539.

56. Фуругян М.Г., Гончар Д.Р. Мультиоценочный алгоритм решения минимаксной задачи составления расписания. /Сборник научных трудов Моделирование процессов обработки информации. М.: МФТИ, 2007. С. 202 - 209.