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

РГ6 од

МИНИСТЕРСТВО НАУКИ И ТЕХНИЧЕСКОЙ ПОЛИТИКИ

1 5 ноя шз российской федерации

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА И ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЯЩИ АВИАЦИОННЫЙ ИНСТИТУТ имени СЕРГО ОРДЖОНИКИДЗЕ

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

ЩЕГЛОВ Михаил Александрович

АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ СТРУКТУР БОРТОВЫХ МНОГОМАШИННЫХ ВЫЧИСЛИТЕЛЬНЫХ КОМПЛЕКСОВ

I- -ц-г.

Специальность 05.13.12 "Системы автоматизации проектирования в радиоэлектронике"

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

Москва Издательство МАИ 1993

Работа выполнена в Московском ордена Ленина и Орден Октябрьской революции авиационном институте имени Серг< Орджоникидзе.

Научный руководитедель доктор-технических наук, профессор Собкин Б. Л.

Официальные оппоненты:

доктор технических наук профессор Ильин В. К.,, кандидат технических наук Бернэр Л. И.

Ведущая организация КИИ Приборостроения, г. Жуковский.

Защита состоится " 7 " 1993 г. .1 ^ дам-ы

специализированного совета Д'053.18;ОТ при Московском авиационном институте.

Адрес института: 12Б871, Москва, Волоколамское шоссе, д. 4. С диссертацией можно ознакомиться в библиотеке МАИ.

о диссертацией можно ознакомиться в библио' Автореферат разослан " 5 " ¡ХоР>Ял993 г

Учйнуй секретарь специализированного Совета Д 053.18.01

кандидат технических наук, доцент ...

с///,

Л.М.Федотов

Общая характеристика работы

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

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

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

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

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

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

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

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

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

- систематизацией видов структур ММВК, классификацией методов их построения и дисциплин обслуживания ими задач,

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

- разработкой математических моделей ММВК и отдельных его компонент, выбором целевого критерия и постановкой задач синтеза и оптимизации ММВК;

- разработкой оптимизационных и эвристических методов решения сформулированных математических задач автоматизированного проектирования ММВК;

- разработкой и апробацией созданных на основе этих методов программных средств;

- разработкой и практическим внедрением в промышленности конкретных средств автоматизации проектирования бортовых ММВК.

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

Научная новизна работы заключается б следующем:

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

- на основании принятых допущений создана и обоснована матоматичоская модель синтезируемого бортового ММВК, определены и формально описаны компоненты и состав характеристик модели, выбран глобальный критерий оптимизации системы, дана математическая постановка задачи её оптимизации;

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

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

универсальность и расширить область применения разработанных математических средств автоматизации проектирования ММВК;

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

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

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

- созданы средства САПР, основанные на разработанном программном обеспечении и получившие практическое использование ;

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

Реализация результатов. Результаты диссертации внедрены на трбх предприятиях в рамках соответствующих договоров на проведение научно-исследовательских работ: НИИ "Системотехники", НПО ЩБ Министерства Связи, АО "АтлантикТрансгаэСис-тема". Общий экономический эффект от внедрения диссертации составил 1770 тыс. рублей.

Материалы диссертации внедрены также в учебном процессе в Московском авиационном институте.

Апробация работы. Основные результаты работы были изложены на конференции "Гибридные экспертные системы в задачах проектирования сложных технических объектов". ( Санкт-Петербург, ДЦНТП, 1992 ) и ряде научно - технических семинаров по автоматизации проектирования ( Москва, МАИ, 1990, 1991, 1992, 1993 г.).

Публикации. По' материалам диссертации опубликовано Б печатных работ. Результаты выполненных исследований отражены также в пяти отчётах по НИР.

ОбъОм и структура работы. Диссертация состоит из вводония, четырёх глав и заключения, списка литературы и приложений. Работа изложона но 148 страницах машинописного текста. Описок литературных источников содержит 92 наименования. В диссертации содержится 7 приложений, 1Б риоутсоп и 3 таблицы.

Содержание работы.

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

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

Классифицированы варианты построения ММВК по характеру взаимодействия между ВУ по шести типам:

- через общее внешнее запоминающее устройство ( ВЗУ );

- через оперативное запоминающее устройство ( ОЗУ );

- через адаптеры "канал - канал";

- через канал прямого управления процессорами;

- через магистральный интерфейс межмашинного обмена;

- сети ЭВМ.

Проведено обобщение способов коммуникации нескольких ММВК в единый комплекс на основе рассмотрения существующих методов объединения для каждого из шести выделенных выше вариантов организации ММВК. На основании проведанного анализа выбрана обобщённая структурная схема ММВК, а также обоснована необходимость рпссмотропия частных 08 вариантов: полноспязного и иерархического.

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

Рассмотрение математических методов синтеза и оптимизации

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

Обзор по оущеотвукхцим работам в выбранной области показал актуальность и необходимость разработки теш диссертации.

Во второй главе проведена математическая формализация задачи автоматизированного синтеза и оптимизации структуры бортового ММВК. Математичеокая постановка задачи представлена как оптимизационная процедура, в качестве целевого критерия которой принята минимизация обобщённой массы ММВК, как наиболее важного параметра для бортовой споцифики:

Здесь А® и М^ - число и масса ВУ типа и в ММВК;

Ам и IIм - число и масса мостов типа п в ММВК;

п п

и - число и масса СПД типа 1 в ММВК;

Акнт1 и Мкнт1- число и масса контроллеров СПД тииа 1 в

ММВК.

Ограничения оптимизационной процедуры задают аналитическую модель ММВК, учитывающую "нагрузочную и пропускную способность СПД и мостов, память и производительность ВУ, функциональные ограничения на размещение задач и соединение компонент ММВК ( ВУ, СПД, мостов ) между собой. Требующие определения переменные модели отражают количество ВУ, СПД и мостов определённого типа в ММВК, их соединение между собой, пространственную и временную диспетчеризацию задач и пути породачи информации между задачами, т.о. полностью определяют структуру ММВК в рамках принятых допущений.

При определении модели ММВК были сделаны следующие допущения:

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

2). Из предыдущего допущения следует, что должен быть

С -

? и".Ам + $ М?-А= + $ И?-А? + $

1=1 " п к 1&1 1 1 1^1

1-1

Мкнт1-Акнт1 - ш1п (I)

заранео известен перечень задач, решаемых ММВК, для каждой из задач должно быть известно время решения на ВУ любого из допустимых к применению в ММВК' типов, интенсивность и очерёдность передачи данных между данной и другими задачами, а также кратность решения задачи на периоде циклограммы.

3). Время передачи данных от задачи - источника к задаче - приёмнику считается составной частью решения задачи -источника.

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

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

6). Система ограничений не учитывает надёжность и стоимость ММВК, что сделано сознательно для сокращения сложности и увеличения наглядности модели и является легко устранимым допущением.

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

l

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

На основе этого были сформулированы постановки задач следующих этапов ( в порядке очерёдности ):

1). Выбор числа ВУ по критерию минимума массы с целевой функцией:

Q - f М®-А® - min (2)

k-1 * к

2). Распределение задач по ВУ по критерию минимума связности между ВУ ( пространственная диспетчеризация ) с целевой функцией:

Q"Z 1 2 1 к±±-,х±ч,х±ч-

min (3)

•i,i' = i----1; d,----j;

где i - общее количество задач, решаемых ММВК; J - общее количество вычислителей в ММВК;

к1±.

О если задачи решаются в одном ВУ;

С в обратном случав где С1±, - количество данных, передаваемое от задачи ± к задаче 1•;

I, если задача i решается на ВУ^

О в обратном случав

3). Временная диспетчеризация задач по критерию минимума времени окончания решения последней задачи в ВУ, последним заканчивающим вычисления, с целевой функцией:

Q » max ( max ( Т + Тз )) - min; (4)

j i 3 3

i - 1 . . .i3$ j = 1...j

где T и Тэ1j - время начала и длительность решения задачи

на выбранном ВУ.

4). Выбор числа СПД по критерию минимума массы с целевой Функцией:

Q - -Мкнт, ) ■ A° t MKiirmin. (.м Апкпт-2А") • min (Г.)

li?1 J 11 i S-i 1

гдо MKHTmin - масса минимального по выборке. Нкнт^, 1.1...1,

контроллера; Апкнт рассчитывается по формуле:

Апкнт = Anmin - 1 +

и

(б)

1 = 1

где Апт1п - оценка минимально необходимого числа мостов п структуре ММВК.

Б). Распределение ВУ по СПД по критерию минимума связности между СПД с целевой функцией:

где в - чило СПД з ШВК;

(О при в = в' С^. при в И

С*

(V)

' J J '

О при i = 3• 7, бели BYj подсоединено к СПЛи

О в обратном случав

6). Выбор числа мостов по критерию минимума массы с целевой функцией:

М •А - min

S)

П=1

7). Синтез окончательной конфигурации ММВК. Этот этяп может различаться для различных выбранных конфигураций ММЬК, в том числе иерархической, полносвязной структуры ММЗК или общего случая структуры.

Выделенные этапы объединяются в представленный на рис.1 общий алгоритм синтеза посредством прямых и обратных связей путвм последовательного • решения зпдпч отдельных эталон о ьо:шрптом ЛрИ необходимости НЯ рМЛНИи ОТПДИИ. Тпкон рИОб'г'.иПИи на отдельные этапы позволило систематизировать, проанализировать И унифицировпть МеТОДН решения поотлнопок различных ;.т.|ЦОи, рпосмотр"'! ь лримышиио гочних, ¡(Ьристическг.-. и

рис. I. Алгоритм поэтапного решения задачи синтеза и оптимизации ММВ1С.

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

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

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

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

Во втором разделе главы рассматривается влгоритм решения квадратичной задачи о назначениях на примере пространственной диспетчеризации задач. Кроме пространстьешгой^диспетчеризации, квадратичная задача о назначениях также используется ещё на нескольких этапах изображённого на рис. I алгоритма, в том числе при распределении ВУ по СПД и на этапе окончательного

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

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

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

В четвёртой главе рассмотрены вопросы практической реализации разработанных средств математического обеспечения САП? ММВК, при этом основное внимание уделяется подпрограммам, реализующим предложенные в диссертации алгоритмы. Программное обеспечение реализовано на алгоритмическом языке Си для персонального компьютера 1ВМ/Р0/АТ.

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

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

В частности, созданное прогриммноо обооночонио иг>шло применение в НИИ "Системотехники" при разработке программных средств синтеза и оптимизации неоднородного магистрально -модульного многомашинного вычислительного .. комплекса, в процессе функционирования выполняющего решение 39 частотных и Б однократно выполняемых задач, запускаемых на рошоние по мере начала и окончания работы прооктируемого бортового ММВК. Наиболее пшашм критерием оф^ктиппооти в донном случае

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

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

Исходя из сказанного, при автоматизированном проектировании данного ММВК использовалось следующее программное обеспечение САПР:

- прбграмма выбора набора ВУ по минимуму массы;

- программа пространственной диспетчеризации задач;

- программа временной диспетчеризации задач.

Все оти программы выполнены в ьиди отдельных модулей,

обмен данными можду которыми осуществляется чороз текстовые

фПЙЛЫ 11(1 ДИСКО.

В результате примонония разработанных программных средств была синтезирована неоднородная магистралыю - модульная бортовая ММВК, состоящая из двух разнотипных вычислителей, соединенных магистралью межмашинного обмена ММИ.

Общий годовой экономический эффект разработки составил 230000 рублей.

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

Методы и алгоритмы, разработанные в диссертации, успешно применены при распределении баз данных и оптимизации интенсивности обменов между узлами регионально - распределённой вычислительной сети автоматизированной системы управления производственно - хозяйственной деятельностью Национальной Газовой Компании "КазахГаэ". Ожидаемый экономический эффект от проведённой работы составит 1БООООО,рублей.

Кроме этого, результаты диссертации внедрены в учебный процесс в Московском Авиационном Институте, в двух курсах лекций по специальности 2205.

Факты -знедрения подтверждаются соответствующими актами.

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

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

Основные результаты, полученные г> работе, заключаются п следующем.

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

ММВК и разработать их методы решения.

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

В' сжатом виде результаты работы можно сформулировать следующим образом:

1). На основе проведённого обзора и анализа выделен объект рассмотрения, в качестве которого выбрана обобщённая архитектура многомашинного вычислительного комплекса и её частные варианты - иерархическая и полносвязная архитектуры. Конкретизированы их основные компоненты - вычислительные устройства, системы передачи данных, мосты, а также дисциплина обслуживания задач в виде статической циклограммы. Доказано актуальность разработки средств автоматизации проектирования выбранного варианта построения бортовых многомашинных вычислительных комплексов.

2). Рассмотрены методы синтеза и оптимизации многомашинных вычислительных оиотим, И роиульччп'и чого оОоспиыжо применение детерминированных аналитических моделей при формализации объекта автоматизированного проектирования, а в качестве его базового математического аппарата - целочисленного программирования.

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

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

б). Обоснована необходимость и произведена декомпозиция общей задачи автоматизированного проектирования многомашинной

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

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

7). Дан анализ частных постановок задач и проведена их классификация в соответствии с требуемыми методами- решения, рассмотрены отличительные особенности и возможности их использования, доказана возможность рошония различных частных постановок одними методами. На основании проведённого анализа обоснована необходимость разработки алгоритмов решения трЗх задач целочисленного математического программирования: задачи выбора, квадратичной задачи о назначениях и задачи теории расписаний.

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

9). На осноно разработанных в диссертации алгоритмов созданы программные средстьм, включающие 11 свой ооотяп подпрограммы рошония задач целочисленного математического нро1праммирования: задачи выбора, квадратичной задачи о назначениях, задач теории расписаний. Рассмотрены особенности организации созданных подпрограмм, обеспечившие их универсальность и эффективное применение тгри решении всех'присутствующих в работе постановок.

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

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

11). Представлены документальные данные о внедрении разработок в промышленности, в том число в НИИ "Системотехники", АО "АтлантикТрансгозСистома", НПО ЦКБ Министерства Связи, о суммарным годовым экономическим эффектом свыше 1770 тыс. рублей.

12). Представлены данные о внедрении результатов диссертации в учебном процессе в Московском Авиационном Кнституто в дпух курсах лекций по специальности 2205.

Ociioninjo положения диссортоцни опубликованы в р&ботах: '

1. Собкин Б.Л., Илюшин С.А., Ковалев A.A., Щеглов М.А. Интеллектуальная система автоматизации проектирования многомашинных управляющих вычислительных систем. /, "Гибридны о экспертные системы в задачах проектирования сложных технических объектов. Санкт-Петербург: ЛДНТП, - 1992.

2. Собкин Б.Л., Щеглов М.А. Алгоритм временной диспетчеризации задач в многомашинных вычислительных системах //Вопросы радиоэлектроники / Сер. ЗВТ. - 1992. - Вып. 4. -0.7Г-79.

3. Со.бкин В.Л., Щеглов М.А. Алгоритм выбора ЗВМ в неоднородны-/ вычислительных системах //Вопросы радиоэлектроники / Сер. ЗВТ. - 1991. - Вып. 4. - С.Б2-Б7.

4. Собкин П.Л., Щеглов М.А., Панфилов П.В. Эвристический алгоритм. временной диспетчеризация задач в многомашинных вычислительных системах //Вопросы радиоэлектроники / Сер. ЭВТ. - 1992. - Вып. 4. - С.80-Я4.

G. Собкин Б.Л., Илюшин O.A., Ковале;, A.A., Панфилов П.В., Попов К.А., Щеглов М.А. Интеллектуальная система автоматизации проектирования многомашинных управлявших вычислительных систем. //Вопроси радиоэлектроники ' Сер. ПИТ. - 1992. - Вып. 4. - С.39-44.