WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 | 3 | 4 |

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

Гончар Дмитрий Русланович МЕТОДЫ ПЛАНИРОВАНИЯ ВЫЧИСЛЕНИЙ В САПР СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ Специальность 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

Москва – 2008

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

Научный консультант: кандидат физико-математических наук, доцент Фуругян Меран Габибуллаевич

Официальные оппоненты: доктор физико-математических наук Серебряков Владимир Алексеевич кандидат технических наук Кононов Дмитрий Алексеевич

Ведущая организация: Институт системных исследований РАН

Защита состоится «30» октября 2008 г. в 14 час.

на заседании диссертационного совета Д 002.017.02 в Вычислительном центре им. А.А.Дородницына РАН по адресу: 119333, г. Москва, ул. Вавилова, 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан «29» сентября 2008 г.

Учёный секретарь диссертационного совета доктор физико-математических наук, профессор В.В.Рязанов 2

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы.

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

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

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

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

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

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

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

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

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

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

В математическом плане центральной задачей автоматизированного построения ВСРВ, как правило, является задача составления расписаний.

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

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

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

Среди зарубежных учёных следует отметить Бернса (Burns), Брукера (Bruker), Гонзалеса (Gonzales), Греневельта (Groenevelt), Гэри М. (Garey), Дертузоса (Dertouzos), Джонсона Д.(Johnson), Конвея Р.В. (Conway), Кормена Т. (Cormen), Коффмана (Koffman), Лью(Liu), Лейланда (Layland), Лейзерсона Ч.(Leiserson), Максвелла В.Л.(Maxwell), Мартеля (Martel), Миллера Л.В.(Miller), Мока (Mok), Одсли (Audsley), Рамамритама (Ramamritham), Ривеста Т. (Rivest), Ричардсона (Richardson), Сахни (Sahni), Станковича (Stankovic), Ульмана Дж.(Ullman), Федергрюна (Federgruen) и др.

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

Цели работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты диссертации и материалы исследований докладывались и обсуждались на:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Pages:     || 2 | 3 | 4 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»