Введение к работе
Актуальность темы. Потребности в высоком быстродействии и большом объече оперативной памяти при проектировании локальных сетей ЭВМ обычно вступают в противоречие с ограниченными техническими и финансовыми возможностями. В связи с этим проблемы эффективного использования ресурсов локальных сетей не теряют своей актуальности.
Особенно важное значение эти проблемы имеют для управления технологическими процессами в режиме реального времени. К таким системам предъявляется требования высокой надежности при жестких ограничениях на продолжительность обработки данных. Большинство программ обработки данных должны выполняться в заданные директивные сроки, а информационный обмен между ЭВМ сети сводиться к минимуму, с тем чтобы обеспечить гарантированное время ответа системы. Кроме того, характерной чертой подобных систем является строгая периодичность обработки данных.
Поэтому, при проектировании таких локальных сетей ЭВМ возникают специфические проблемы расчета и оптимизации временных характеристик, а также выбора и конфигурации основных ресурсов сети - процессоров, оперативной памяти, каналов связи.
Такого рода проблемы приводят обычно к задачам построения допустимых или оптимальных расписаний, задачам упаковки в контейнеры и к некоторым комбинаторным задачам на графах. Большинство этих задач MP-полны и точное переборное решение их бывает затруднительно даже для относительно небольших сетей.
Объект исследования. В настоящей работе исследуются математические модели различных ресурсных составлявших локальных сетей ЭВМ, которые приводят к задачам построения допустимых расписаний, упаковки в контейнеры и поиска максимальной клики в графе.
Целью работы является
/. Разработка эффективных полиномиальных алгоритмов построения допустимых расписаний обслуживания требований, алгоритмов упаковки в контейнеры и поиска максимальной клики в графе.
-
Минимизация и получение оценок сверху числа прерываний в оптимальных расписаниях многопроцессорных одностадийных и многостадийных детерминированных систем обслуживания.
-
Получение оценок эффективности полиномиальных алгоритмов
-V-
упаковки и исследование асимптотического поведения этих оценок, выявление условий асимптотической оптимальности таких алгоритмов.
4. Формулирование условий при которых максимальнаяя клика в большом графе может быть найдена за полиномиальное время.
Научная новизна результатов заключается в том, что
/. Получен быстрый полиномиальный алгоритм построения допустимого расписания в многопроцессорной системе обслуживания для требований порождаемых периодическими задачами. Число прерываний в расписании на порядок меньше оценки известной для общего случая ("теоремы 1.1-І.2).
Обобщена теорема о числе прерываний в оптимальном расписании на случай многостадийных систем обслуживания и произвольных двусторонних функций штрафа (теорема 1.3).
Предложен полиномиальный алгоритм уменьшения числа прерываний в оптимальном расписании для одностадийной многопроцессорной системы обслуживания в общем случае, соответствующая оценка числа прерываний в ОСтР ) раз лучше известной оценки (теорема 1.4).
2. Получена оценка эффективности семейства приближенных
полиномиальных алгоритмов упаковки в контейнеры, показывающая их
высокую асимптотическую эффективность при некоторых естественных
ограничениях (теоремы 2.1-2.2).
Доказана асимптотическая оптимальность двух полиномиальных алгоритмов упаковки для некоторых классов функций распределения вероятностей, включающих в себя, в частности, все выпуклые функции распределения (теоремы 2.3-2.5}.
3. Показано, что максимальная клика в большом графе может быть
"почти всегда" найдена за полиномиальное время, если эта клика
имеет "не случайно" большой размер. Приведены формулы необходимые
для построения алгоритмов поиска и оценки быстродействия этих
алгоритмов С теоремы 3.1-3. 2).
Нетодика исследования комбинаторно-логические методы дискретной математики, элементы теории расписаний, теории вероятностей и математической статистики, эксперименты на ЭВМ.
Практическая ценность. Предложенные в работе алгоритмы и оценки могут быть использованы при проектировании локальных сетей ЭВМ и многопроцессорных комплексов для управления АСУТП.
Публикации и апробация работы. По теме диссертации
опубликовано б печатных работ. Основные результаты докладывались на семинаре "Программирование" МГУ им. М. В. Ломоносова и на
семинарах сектора "Проектирование вычислительных систем реального времени" Вычислительного центра АН СССР.
Структура и объем работы. Диссертация состоит из введения, трех глав и списка литературы С25 наименований). Объем работы страниц машинописного текста.