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

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

PPS 07)

ТЫНЧЕНКО Сергей Васильевич

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

СИСТЕМАМИ

Специальность 05.13.01 - Управление в технических системах

АВТОРЕФЕРАТ

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

Красноярск 2000

Работа выполнена в НИИ систем управления, волновых процессов и технологий Министерства образования Российской Федерации (г. Красноярск)

Научные руководители:

кандидат технических наук, профессор Лебедев В.А. кандидат технических наук, доцент Терсков В.А.

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

доктор технических наук, профессор Антамошкин А.Н. кандидат физико-математических наук Косарев Н.И.

Ведущая организация:

Государственный НИИ информационных технологий и телекоммуникаций "Информика", г. Москва

Защита состоится "10" июля 2000 года в 11 часов на заседании диссертационно Совета К 064.46.01 в Сибирской аэрокосмической академии по адресу: Краен ярск, проспект имени газеты "Красноярский рабочий", 31.

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

Ваш отзыв, заверенный печатью, просьба высылать по адресу: 660014, Красноярс а/я 486, САА, учёному секретарю диссертационного Совета И.В. Ковалеву

Автореферат разослан 8 июня 2000 г. Учёный секретарь диссертационного Совета д.т.н, профессор

И.В. Ковалев

Н 6.0

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

Актуальность работы. ЭВМ все стремительней внедряются в общественное фоизводство и быт, становятся незаменимым инструментом для автоматизации >азнообразных процессов во всех областях человеческой деятельности. Использо-шние ЭВМ в качестве быстродействующих арифмометров все в большей степени вменяется комплексной автоматизацией процессов сбора и переработки информа-щи, принятия решений и непосредственного управления. Меняются требования к сарактеристикам вычислительных машин, средствам и способам общения с ними. Основной при проектировании современных ЭВМ остается задача повышения их фоизводительности. Однако, разработка перспективных ЭВМ комплексов оперативного управления сложными системами немыслимо без учета и анализа надеж-гости. Недостаточная надежность может привести не только к чрезмерным эксплуатационным издержкам (ремонт и восстановление), но и к более тяжким последствиям (невыполнение задачи, опасные ситуации, аварии). Поэтому модели и методы позволяющие устанавливать количественные показатели надежности, :равнивать различные варианты по этим показателям, упрощать и сокращать прочее выбора лучшего варианта вычислительного комплекса проектируемой системы управления сегодня исключительно важны, а их разработка и применение яв-1яются актуальной исследовательской задачей.

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

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

Эта цель обусловила необходимость решения следующих задач:

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

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

з

3. Разработка имитационной модели функционирования МВС с многоши ной организацией связи произвольного количества разнородных процессоров общей ОГЬдля проверки адекватности математической модели.

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

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

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

Научная новизна результатов, полученных в диссертации, состоит в с. дующем:

1. Построены новые математические модели оценки надежности cпeциaJ зированных МВС с многошинной организацией связи разнородных процессор© общей ОП.

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

3. Предложены новые алгоритмы решения дискретных задач условной оп мизашш с алгоритмически заданными функциями, основанные на сочетании 1 тодов прямого поиска и модификации метода множителей Лагранжа.

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

Практическое значение. Диссертационная работа выполнялась в соотв ствин с заданной Главнокомандующим войсками ПВО НИР "Механика'" и в рам1 госбюджетных и хоздоговорных НИР, проводимых Сибирским отделением Р сийской инженерной академии по заказам промышленных предприятий г. Крас ярска. а также НИИ систем управления, волновых процессов и технологий Ми стерства образования Российской Федерации.

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

'Системный анализ", "Теория оптимизации", а также кафедры информатики, САА ю дисциплине "Устройство и функционирование ЭВМ".

Математические модели, алгоритмы оптимизации и программная система ¡месте с результатами решения практических задач переданы для использования в 1/4 03059 и в отдел автоматизации управления воздушным движением аэропорта 1мельяново.

На защиту выносятся:

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

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

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

Публикации. По теме диссертации опубликовано десять работ, список кото->ых приводится в конце автореферата.

Апробация работы. Основные положения и отдельные результаты диссер-ационной работы докладывались и обсуждались на первой НТК Военной акаде-1ии республики Беларусь (Минск, 1996), пятой НТК КВКУРЭ ПВО (Красноярск, 997), четвертой межвузовской научно-практической конференции (Красноярск, 997), пятой НТК Московского ВУРЭ ПВО (Москва, 1997), четвертой межвузовкой НТК НВЗРКУ ПВО (Нижний Новгород, 1997).

Диссертационная работа в целом обсуждалась на научных семинарах кафедр [нформатики и системного анализа и исследования операций Сибирской аэрокос-шческой академии (1998-2000), кафедры вычислительной техники КВКУРЭ ПВО 1995-1998), научно-техническом совете НИИ СУВПТ (1999-2000).

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

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

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

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

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

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

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

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

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

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

Процесс функционирования МВС представлен замкнутой системой массо вого обслуживания (СМО) с ожиданием и случайным распределением запросо! всех типов по всем шинам без взаимодействия между собой. При этом предполага ется, что суммарный поток запросов от процессоров каждого типа является про стейшим с параметром V, (Ч = , где N - количество типов процессоров), а врем)

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

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

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

к+е /1+е-д

РкЛ = X X X р/,'!/г.....у„_„(*+л-л) •

>1=0 у2-о ;„-1=о А М-к ср ~ X

ы\

е,- = 1 + -

ъ+т,

Тогда относительную производительность МВС можно определить, используя выражение :

" Ш Пер = X*, а > /=.( i

т

где kt = - коэффициент, учитывающий быстродействие процессоров каждого мм

типа, Toi - относительное время выполнения операции процессорами i-ro типа, T0mm - наименьшее значение из Т0;.

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

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

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

Исследуемая МВС состоит из N типов процессоров, содержащих по т/г = 1,А'Л процессоров каждого типа. Процессоры объединяются с ОП посредством п шин, причем, в предельном случае количество шин может быть равно количеству процессоров (полносвязный интерфейс). Количество блоков общей оперативной памяти (ОП) определяется необходимым объемом ОП.

Процесс функционирования МВС представляется замкнутой системой массового обслуживания (СМО) с ожиданием. Каждый элемент вычислительной системы в некоторые случайные моменты времени выходит из строя и нуждается в восстановлении. Поток отказов от процессоров каждого типа и шин интерфейса простейший с параметром где ; = 1,2,..., Л* +1. Интенсивность восстановления каждого вышедшего из рабочего состояния элемента вычислительной системы подчиняется экспоненциальному закону распределения с параметром ¡¿¡. Если вновь поступивший на восстановление запрос застанет обслуживающий прибор свободным, то он принимается на обслуживание. Если же поступивший запрос застанет обслуживающий прибор занятым, он становится в очередь и ждет своего обслуживания. Дисциплина обслуживания - случайный равновероятный выбор из очереди. Рассматриваемая СМО может находиться в следующих состояниях: ао,о.о.. ,о ~ интерфейс и все процессоры неисправны и восстанавливаются. Вычислительный процесс остановлен.

81.0.0,..о -исправна одна шина интерфейса, а (гП|-1) шин неисправны и восстанавливаются. Все процессоры неисправны и восстанавливаются. Вычислительный процесс остановлен.

ао,1.о, .„ ~ все шины интерфейса неисправны и восстанавливаются, все процессоры, за исключением одного процессора первого типа, неисправны и восстанавливаются. Вычислительный процесс остановлен.

а00, 0 - все шины интерфейса неисправны и восстанавливаются, все процессоры, за исключением одного процессора второго типа, неисправны и восстанавливаются. Вычислительный процесс остановлен.

ао.о.о. ,1 ~ все шины интерфейса неисправны и восстанавливаются, все процессоры, за исключением одного процессора М-го типа, неисправны и восстанавливаются. Вычислительный процесс остановлен.

а)1)Ы1 1ы1 -]) шин интерфейса исправны и участвуют в вычислительном процессе, а (тг^) неисправны и восстанавливаются, }2 процессоров первого типа исправны и участвуют в вычислительном процессе, а (шг-Ь) неисправны и восстанавливаются, ]3 процессоров второго типа исправны и участвуют в вычислительном процессе, а (т3^3) неисправны и восстанавливаются,..., процессоров Н-го типа исправны и участвуют в вычислительном процессе, а (тк+г неисправны и восстанавливаются.

аш,.■»,.»„ .т„„ ~ все процессоры и шины, входящие в состав вычислительной системы, исправны и участвуют в вычислительном процессе.

Фрагмент графа состояний рассматриваемой СМО приведен на рис. 1.

Рис. 1.

Число состояний СМО равно А=|^(гя, +1).

1.1

Для стационарного режима получим систему линейных уравнений.

~ £ т.мАл.....О + у Ал.....о + У Ал.....о + - + У^Ал.....1 = О

(.1

N +1

-1 - + V,+ (т, - Л + .....+ (т2 - 32 + 1)

1= I

РгРл.»->.....Js^t + ••• + («*♦! - Л-1 + .....+~ +

+ ..........= о (1)

.....+ .....»,., +/»»Л.,.«,-!„«„., + А,»,......„.,-1 =° •

'-I

Система уравнений (1) с учетом условия нормировки имеет единственное решение

Для решения системы уравнений (1) в общем виде сделаем следующую подстановку

»1

и перепишем систему линейных уравнений (1) в следующем виде:

- £[(«, - Л + V, к К ■ - • К„+ <т> ~ Л + ЪнА-Л ■■■■ ■р+ К - Л +!)

Ы

+ »АЛ..--Л., +... + =

Перегруппируем (3) таким образом, чтобы Р входили в соответствующие выражения, содержащие т.е. произведем разделение переменных по ин-

дексам.

{(»1, - у, +1)^,., - [(и, + АЛ., - л +1)^-. -

-(К +у2]РЛ + +

........................................................................................................ (4)

+ {(«*., -Лч, -[(«»♦. -у'^Кч, Л •..•■?„ =о.

Система линейных уравнений (4) будет иметь решение только в том случае, когда выражения в фигурных скобках равны нулю, т.к. Р] * 0 для всех iJ. Следовательно, можно записать

(m, -у, +1 -[(m, + v,i>„+1 =0;

(m2 — j2 -[(«г — Л+

Каждое уравнение системы (5) представляет собой систему уравнений СМО, гоящей из п^ источников требований одного типа с одним обслуживающим бором. Следовательно, граф состояний исходной СМО будет представлять со-упность из N+1 однолинейных графов. Решаем систему уравнений (5).

Осуществляя обратную подстановку (5) в (2) с учетом биноминальных и по-омиальных коэффициентов получим

т,\

А/+1 _ N*l

. ..р/'^о.о.....о >

(6)

Р0 0 0 - вероятность нахождения СМО в состоянии а0 0 0 ,которая определяется словия нормировки.

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

в этом состоянии равна сумме вероятностей достижения его по каждому пути. :ичество путей X,j достижения состояния в общем случае соответствует поливальному коэффициенту и равно

(7)

Ш,!

/ = од,..£у,. Следовательно

Wf I т.!

-п-

"г ,»!

РГ

(8)

Произведя подстановку (8) в (6), получим решение системы уравнений (1) в 1ем виде.

/I П*\ m I

П,

1*1

v Л W т.\

, у, =l,m,, i = l,JV + l.

(9)

о П-><!' „I

Jл

а

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

нии аМ1 показатели надежности микропроцессорных ЭВМ определяется с; дующим образом:

Ж,......(Ю)

л-4а.

Jг-!¡,m1

Р' Р'

' Р'-{\-Р') 2Р' -1 '

2 X уг+...+ '

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

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

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

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

Метод статических штрафов предполагает формирование для каждого ог-аничения семейства интервалов, которые определяют соответствующие коэффи-иенты штрафов. Метод работает по следующей схеме: для каждого ограничения определяется несколько уровней (/) его нарушения, для каждого уровня нарушений каждого ограничения определяется коэффициент [трафа Д, (/ = 1,2,...,/, у'= 1,2,...,ю); большие значения коэффициентов соответствуют ольшим уровням нарушения ограничений,

в качестве целевой функции используется Р(Х) = /(Л')+ • //(ЛГ), где _ДХ) -

елевая функция, ^(Х) - штраф за нарушение у-го ограничения,/=1,..., т.

Недостатком метода является большое число параметров. Для т ограниче-ий метод требует определения т(2/+1) параметров.

В методе динамических штрафов коэффициент штрафа вычисляется динами-

ески, в зависимости от степени нарушения ограничений (\ffiXj,) и итерации ^

гшения задачи: ^(0 = С-/а. Этот метод требует намного меньше параметров, ем предыдущий (их число не зависит от количества ограничений). Вместо выбора з набора фиксированных уровней нарушения ограничений в данном методе праф рассчитывается динамически. В результате экспериментов установлено, что среднем метод работает эффективно при С = 0.5, а=р=2.

Очевидным недостатком обоих подходов является то, что они не учитывают ачества поисковых точек (какая часть точек на каждом шаге является допустимой, зляется ли допустимой наилучшая точка и т.д.). Поэтому был разработан еще цин метод - метод адаптивных штрафов. В отличие от предыдущих, в данном ме-эде штрафные функции зависят не только от номера итерации, но и от количества опаданий лучшей точки на каждом шаге в допустимую или недопустимую облас-л. Если в течение к итераций наилучшая поисковая точка всегда является допус-шой, то коэффициент штрафа Ц/) уменьшается в Р] раз, если всегда не допусти-а, то увеличивается в (З2 раз, в остальных случаях остается неизменным. Числа к, I и р2 являются дополнительными параметрами алгоритма, обеспечивающими его эльшую гибкость. Выбор коэффициентов должен осуществляться по своему для зждой задачи, при этом Р1 * р2 для избежания зацикливания.

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

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

Одним из наиболее перспективных методов прямого поиска является генет ческий алгоритм (ГА), который представляет собой вариант случайного поиска моделирует процессы естественной эволюции. В генетическом алгоритме испол зуется так называемая популяция, моделирующая вектор неизвестных задачи. Да ная популяция эволюционирует, добиваясь увеличения функции пригодности св их индивидуумов, а заодно и оптимизируя целевую функцию. В случае задачи о тимизации с ограничениями необходимо каким-то образом учитывать эти огран чения при расчете функции пригодности. В теории оптимизации известен мет обобщенного Лагранжиана, в котором условный оптимум ищется как седлов точка функции Лагранжа. При этом в точке, являющейся решением, достигает минимум по переменным задачи и максимум по коэффициентам Лагранжа (для з дачи минимизации). Если бы оптимальные коэффициенты Лагранжа были извес ны заранее, то решение задачи условной оптимизации было бы сведено к одн кратному решению задачи безусловной оптимизации. Однако эти коэффициент неизвестны и процесс решения условной задачи состоит в одновременном реш нии задачи безусловной минимизации по объектным переменным и задачи без> ловной максимизации по коэффициентам Лагранжа. При таком подходе мож быть применен коэволюционный ГА, в котором эволюционируют совместно д популяции, каждая из которых имеет свое представление хромосомы, свои пар метры алгоритма и свою стратегию эволюции. Первая популяция (А) моделиру объектные переменные, а вторая (В) - коэффициенты Лагранжа. Размеры и пре ставление популяций, а также параметры ГА устанавливаются независимо, a con сование процессов эволюции выполняется через оценивание функции пригодн сти. Основой для вычисления функции пригодности служит функция Дх^у), у кот рой х берется из популяции А, а у - из популяции В. Поэтому функция пригодное индивида из популяции А зависит от популяции В и наоборот.

Пригодность индивида х из популяции А определяется выражением /а(*) = т™Ах,У),

уеВ

а пригодность индивида у популяции В - выражением /в(У)= тЬ Л*. У)-

хел

Схема алгоритма приведена на рис. 2.

Procedure co-ev_GA begin

инициализировать популяцию А инициализировать популяцию В for к = 1,2,... cmax do for i = 1,2, . . . а ¡пах do сгенерировать новую популяцию А оценить А

fox j e 1,2,... bm&x

do

сгенерировать новую популяцию В

оценить В

end

Рис. 2. Общая структура коэволюционного ГА

Процесс решения задачи состоит в поочередной работе ГА с обеими популяциями. Сначала ГА работает с популяцией А, давая ей эволюционировать опреде-енное пользователем количество поколений атах. Затем ГА работает с популяцией ! в течение Ьтах поколений. Этот цикл повторяется стах раз. Общее число поколе-:ий вычисляется как nS=cmax'(amm+ bma)- Таким образом, атах и Ътах являются араметрами алгоритма, от которых зависит его эффективность и которые должны ыть настроены в процессе работы. Данный подход был также проверен на тесто-ых задачах и был в последующем, наравне с адаптивными штарфами использован ля решения задач выбора надежных вариантов МВС управления сложными сис-емами.

В четвертой главе описывается практическая реализация предложенных юделей и методов. Для проверки адекватности и проведения численных экспери-[ентов была разработана программная система, реализующая оценку надежности ÍBC с использованием аналитических моделей, предложенных в первой главе, и а базе имитационной модели. С использованием данной системы была проведена роверка адекватности аналитических моделей. Были получены результаты, пока-ывающие совпадение тенденций аналитических и имитационной моделей, при том численное расхождение составляло до 30%, что для данного типа моделей вляется удовлетворительным. Основной причиной расхождения является то, что митационная модель учитывает методы разрешения конфликтов, чего аналитиче-кая не делает.

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

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

Нятош Мпсгррыгы Свойства. V . - ' ,

'(Ж

£ -8*

I-

1 "г. X"»

/

М етоды ----:———-—--

С Мстсд сг«л^(г.кич С Мвпяйх+ямщбсхян штрафов | С Мегоа ааатиеньы и/грвФов '

С МйТ0й''о«рТйЛЫ1еЛ ШТрЛФОЬ" - ■

<5* ¡М^тоа поа^е^аской пайятг|

С" »лол з^еэкие сгеам/ггныу. т-.грп'.

. ; С Мтси •-.ьд'^Т'-мь* тс:-еу.

Дополнительно

Зарыть

Опредчеии» прдиаволитальжцгу» инотЧшрома^

- Номер понояетя •

Г

- Сапвкцмя

И

Вероятность мутачнн [005 Вероятность скрешмванмя

Змст даспредвденмя дяа»

выбора ТОЧКИ СВДМЫЦМММт ' - -•-«••. —-----— - - Калмчасггю ипанвмл

Ш

браня обработки **1Фор«чации (емко). • {0&Б

. Коэффициент связности алгоритма по ммяги }0 25 . ЭремяраЬоты сгммятыо{мкс} [ГУ

г Количества процессоров

—>¡.1 Мкиимально ооэмсмоюе- |У" " т| ■ Максимально в

'Х-'.-".;'!: •.',•'.: ' 'У.'*-' —------

ггКолмчесгао гяжалвн.

Ртах 8 51572 " *■" " • :Г^°яи,,всТва в системе РСЗ] ''•)] Минимально возможное

; КоЯИЧвСГв^ ОПЫТ О»

ш«тг<»««»т >ч>»щуинпт »ш»* иг» п»т>1 «ттт т тш ш »ттшг

1.34.15' (Время загус*« 2ИЗГ23 ]|эремя останов* 2й31;4& • ]Время рвбагьс-

Мака«*1Льно возможное

Модем» —~ •

/» Аниттнческ С Имитационн

!ЗВП»Ск [ \Jptd- Гьичанрс^} Лросоаник-МиЬДрУ • Ц &Рр<шиге

Н 20:34

Рис. 3. Вид рабочих окон оптимизационной программной системы.

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

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

Основные результаты и выводы

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

В работе получены следующие результаты:

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

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

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

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

5. Решены практические задачи выбора надежных вариантов МВС для АСУ ПВО и системы управления воздушным движением гражданского аэропорта.

Работы, опубликованные по теме диссертации

1. Рогов C.B., Терсков В.А., Нечушкин А.П., Тынченко C.B. Проектирование сложных систем с использованием многопроцессорных средств вычислительной техники // Отчёт. НИР "Механика". - Красноярск: КВКУРЭ ПВО, ! 997. 43 с.

2. Терсков В.А.. Нечушкин А.П., Серенков В.И., Тынченко C.B. Исследование проблем совершенствования информационной подготовки курсантов и слушателей// Отчёт. НИР "Информатика-971'.- Красноярск: КВКУРЭ ПВО, 1997. 65 с.

3. Тынченко C.B. Богомолов Н.П. Обработка радиолокационной информации в многопозиционном радиолокационном комплексе // Сб. тез. докладов XVIII военно-научной конференции ВА ПВО Тверь, 1998. Сс. 68-69.

4. Богомолов Н.П., Тынченко C.B. Некоторые алгоритмы применения экстраполированной оценки координат цели в многопозиционном радиолокационном комплексе Сб. тез. докладов XVIII военно-научной конференции ВА ПВО Тверь, 1998. С. 67.

5. Тынченко C.B. О согласовании характеристик специализированных процессоров при параллельных вычислениях // Сборник "Решетневские чтения" Материалы всероссийской научно-практической конференции, 1998. С. 152.

6. Тынченко C.B. Аппаратная реализация операций в информационных системах Четвертая Всероссийская конференция "Проблемы информатизации региона (ПИР-98), 1998. С. 269.

7. Тынченко C.B. Определение вероятностных характеристик вычислительно системы с произвольным числом типов потоков требований при организаци параллельных вычислений // Информатика и системы управления, вып. 3, 199' Сс. 107-112.

8. Тынченко C.B. Метод прямого поиска для условной оптимизации в задачах вь бора надёжных вариантов многопроцессорных вычислительных систем // Вест ник НИИ СУВГТГ, вып. 1, 1999. - Сс. 56-61.

9. Терсков В.А., Тынченко C.B. Аналитическая модель оценки производительнс сти специализированной МВС с разнородными процессорами и многошинны; интерфейсом. - В кн.: Семенкин Е.С., Терсков В.А. Модели и методы оптимизг ции систем управления сложными объектами. - Красноярск: НИИ СУВПТ, 200< Сс. 224-236.

10. Терсков В .А., Тынченко C.B. Аналитическая модель оценки надежности сш циализированной МВС с разнородными процессорами и многошинным инте{ фейсом. - В кн.: Семенкин Е.С., Терсков В,А. Модели и методы оптимизаци систем управления сложными объектами. - Красноярск: НИИ СУВПТ, 2000. Ci 254-268.

ВВЕДЕНИЕ

Глава1. Анализ функционирования и оценка производительности МВК оперативного управления сложными техническими системами

§ 1.1. Работа МВК систем управления в реальном масштабе времени и проблемы оценки производительности

§ 1.2. Надежность МВК оперативного управления сложными техническими системами.

§ 1.3. Метод выбора множества макроопераций для реализации аппаратными средствами.

§ 1.4. Математическая модель функционирования многопроцессорных вычислительных систем с разнородными процессорами и многошинной организацией связи процессоров с ОП.

§ 1.5. Аналитический метод и-алгоритм, расчета производительности МВС, состоящей из. произвольного количества типов процессоров, произвольного количества процессоров каждого типа и произвольного количества шин, объединяющих процессоры с ОП. Выводы

Глава2. Модели оценки надежности МВС

§ 2.1. Общая характеристика избранного подхода моделирования расчета надежности специализированных МВС.

§ 2.2. Аналитическая модель расчета надежности для МВС с произвольным количеством однородных процессоров и блоков общей оперативной памяти.

§ 2.3. Аналитическая модель расчета надежности для МВС с разнородными процессорами и одношинным интерфейсом

§ 2.4. Аналитическая модель расчета надежности для МВС с разнородными процессорами и одношинным интерфейсом

§ 2.5. Аналитическая модель расчета надежности для МВС произвольной конфигурации Выводы

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

§ 3.1. Локальный поиск в задачах дискретной оптимизации

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

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

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

Эта цель обусловила необходимость решения следующих задач:

1. Анализ процессов функционирования МВС управления сложными техническими системами и определение критериев их общей эффективности. 5

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

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

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

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

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

Научная новизна результатов, полученных в диссертации, состоит в следующем:

1. Построены новые математические модели оценки надежности специализированных МВС с многошинной организацией связи разнородных процессоров с общей ОП.

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

3. Предложены новые алгоритмы решения дискретных задач условной оптимизации с алгоритмически заданными функциями, основанные на сочетании методов прямого поиска и модификации метода множителей Лагранжа.

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

Практическое значение. Диссертационная работа выполнялась в соответствии с заданной Главнокомандующим войсками ПВО НИР "Механика" и в рамках госбюджетных и хоздоговорных НИР, проводимых Сибирским отделением Российской инженерной академии по заказам 6 промышленных предприятий г. Красноярска, а также НИИ систем управления, волновых процессов и технологий Министерства образования Российской Федерации.

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

Математические модели, алгоритмы оптимизации и программная система вместе с результатами решения практических задач переданы для использования в в/ч 03059 и в отдел автоматизации управления воздушным движением аэропорта Емельяново.

На защиту выносятся:

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

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

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

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

Апробация работы. Основные положения и отдельные результаты диссертационной работы докладывались и обсуждались на первой НТК Военной академии республики Беларусь (Минск, 1996), пятой НТК КВКУРЭ ПВО (Красноярск, 1997), четвертой межвузовской научно-практической конференции (Красноярск, 1997), пятой НТК Московского ВУРЭ ПВО (Москва, 1997), четвертой межвузовской НТК НВЗРКУ ПВО (Нижний Новгород, 1997).

Диссертационная работа в целом обсуждалась на научных семинарах кафедр информатики и системного анализа и исследования операций Сибирской аэрокосмической академии (1998-2000), кафедры вычислительной техники КВКУРЭ ПВО (1995-1998), научно-техническом совете НИИ СУВПТ (1999-2000). 8

Выводы

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

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

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

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

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

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

129

Заключение

В работе получены следующие результаты:

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

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

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

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

5. Решены практические задачи выбора надежных вариантов МВС для АСУ ПВО и системы управления воздушным движением гражданского аэропорта.

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

130

1. Авен О.И., Коган Я.А. Управление вычислительным процессом в ЭВМ (Алгоритмы и модели).- М.: Энергия, 1978,- 240с.

2. Автоматизированный радиотехнический узел АРТУ-1. / Под ред. A.C. Магдесиева,- М.: Воениздат, 1970.-240с.

3. Антамошкин А.Н. Регулярная оптимизация псевдобулевых функций. Красноярск: Изд-во КГУ, 1989. 160 с.

4. Букатова И.Л., Ю.И.Михасев, А.М.Шаров. Эвоинформатика: Теория и практика эволюционного моделирования. -М.: Мир, 1991. 206 с.

5. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее инженерные приложения. М.: Наука, 1991.

6. Емеличев В.А., Комлик В.М. Метод построения последовательности планов для решения задач дискретной оптимизации. -М.: Наука, 1981. 207 с.

7. Жилинскас А.Г. Методы исследования глобального экстремума. М.: Наука, 1991.

8. Жилинскас А., Шалтянис В. Поиск оптимума. М.: Наука, 1989. 128 с.

9. Иванов М.В., Рубан А.И. Поисковый непараметрический алгоритм спуска в область Парето при многокритериальной оптимизации // Информатика и процессы управления: Сб. науч. работ. Красноярск: КГТУ, 1995. Сс. 118-124.

10. Ильичев A.B. Эффективность проектируемой техники: основы анализа. -М.: Машиностроение, 1991. 336 с.

11. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979. - 432 с.

12. Корбут A.A., Финкелыптейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.

13. Корбут A.A., Финкелыптейн Ю.Ю. Приближенные методы дискретного программирования. Известия АН СССР. Техническая кибернетика, 1983, №1. Сс. 165-176.

14. Коробейников С.П. Методы многокритериальной оптимизации для задач синтеза управления сложными объектами. Дисс. на соиск. уч. степ. канд. техн. наук. - Красноярск: ГХК, 1997. 174 с.

15. Королюк В. С., Турбин А. Ф. Процессы марковского восстановления в задачах надежности систем. Киев: Наукова думка, 1982.131

16. Лапко A.B. Непараметрические методы оптимизации и их применение. Новосибирск: Наука, 1993. 152 с.

17. Ларичев О.И., Мовшевич E.H. Качественные методы принятия решения. М: Наука, 1996. 286 с.

18. Бухараев Р.Г. Вероятностные автоматы,- В кн: Итоги науки и техники. "Теория вероятностей. Математическая статистика. Теоретическая кибернетика". Том 15.-М.: ВИНИТИ, 1978, с. 137-185.

19. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. Новосибирск: ИМ СО АН СССР, 1981. 160 с.

20. Машунин Ю.К. Модели и методы многокритериальной оптимизации. М: Наука, 1982. 128 с.

21. Медведев A.B. Непараметрические системы адаптации. -Новосибирск: Наука, 1983. 174 с.

22. Медведев A.B. Непараметрические методы в кибернетике. -Известия ВУЗов. Физика, 1995, № 9. Сс. 46-54.

23. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. Кибернетика, №12, 1975.

24. Многокритериальные задачи принятия решений. Под ред. Д.М. Гвишиани, C.B. Емельянова. М.: Машиностроение, 1978.

25. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1979.

26. Растригин Л.А. Статистические методы поиска. М.: Наука,1968.

27. Растригин Л.А. Адаптация сложных систем. Рига: Зинатне,1981.

28. Растригин Л.А., Фрейманис Э.Э. Решение задач разношкальной оптимизации методом бинаризации. Вопросы разработки ТАСУ. Кемерово: НТО, 1984. Вып. 3. Сс.39-48.

29. Резников Б. А. Методы и алгоритмы оптимизации на дискретных моделях сложных систем. Л.: ВИКИ им. Можайского, 1983. 250 с.

30. Рубан А.И. Метод непараметрической поисковой оптимизации. -Известия ВУЗов. Физика, №9, 1995. Сс. 65-73.

31. Рубан А.И. Поисковая оптимизация на основе использования инверсных непараметрических характеристик // Информатика и процессы управления: Сб. науч. работ. Красноярск: КГТУ, 1995. Сс. 94-104.

32. Рыбников К. А. Введение в комбинаторный анализ. М.: Изд-во Моск. ун-та, 1985. - 308 с.

33. Саати Т. Целочисленные методы оптимизации и связанные с ними проблемы. М.: Мир, 1973.132

34. Семенкин Е.С. Оптимизация сложных систем и интеллектуальные информационные технологии. Новые информационные технологии и развитие региона. Красноярск: КГТУ, 1996. Pp. 121-132.

35. Семенкин Е.С., Коробейников С.П. Эволюционные алгоритмы многокритериальной оптимизации сложных систем. Межвуз. сб. трудов -Красноярск: КГТУ, 1997. Сс. 65-72.

36. Семенкин Е.С. и др. Оптимизационные программные системы при поддержке принятия решений в проектировании сложных систем. Вестник КГТУ, вып. 5. Красноярск: КГТУ, 1996. Сс. 121-128.

37. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности,- Новосибирск: Наука, Сибирское отделение, 1966,- 308с.

38. Журилов B.C. Тенденция развития вычислительной техники,- В кн.: Научно-методические материалы в/ч 03444, вып 2(31).- Калинин : 1974, с. 198-222.

39. Заболотный A.A., Недзельский Д.А. Анализ алгоритмов связи с главной памятью в мультипроцессорных системах,- Приборы и системы управления, 1976, №4, с. 17-18.

40. Затраты потребителей на электронную вычислительную технику в США,- Радиоэлектроника за рубежом, 1982, №6, с. 20-22.

41. Семенкин Е.С. и др. Методы решения сложных оптимизационных задач и системы искусственного интеллекта. Вестник КГТУ, вып. 5. Красноярск: КГТУ, 1996. Сс. 108-112.

42. Семенкин Е. С., Семенкина О. Э., Коробейников С. П. Поисковые методы синтеза систем управления космическими аппаратами. Красноярск: СИБУП, 1996. - 324 с.

43. Семенкин Е. С., Семенкина О. Э., Коробейников С. П. Оптимизация технических систем. Красноярск: СИБУП, 1996. - 285 с.133

44. Заявка на изобретение №3287718 (СССР). Устройство для умножения. / О.В. Глушко, В.Ф. Зелтинып, JI.M. Осинский, Г.С. Тимофеев,- Положительное решение ВНИИГПЭ 19 февраля 1982 г.

45. Коган Б.М., Крейнтн А.Я. Модели конфликтов в памяти мультипроцессорных систем,- Автоматика и вычислительная техника, 1982, №2, с. 59-65.

46. Каган Б.М., Сташин В.В. Микропроцессоры в цифровых системах,-М.: Энергия, 1989,- 192с.

47. Кнут Д. Искусство программирования. Методы сортировки и поиска. Том 3. Пер. с англ. Н.Ю. Вьюновой, В.А. Галатенко и А.Б. Ходулева. / Под ред. Ю.М. Баяковского и B.C. Штракмана.-М.: Мир, 1978,-843с.

48. Семенкин Е. С., Семенкина О. Э., Коробейников С. П. Адаптивные поисковые методы оптимизации сложных систем. Красноярск: СИБУП, 1996, 275 с.

49. Семенкина О. Э. Поисковые методы синтеза систем управления космическими аппаратами: Дисс. на соиск. уч. степ. канд. техн. наук. Красноярск: CAA, 1995. - 181 с.

50. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наукова думка, 1981.

51. Тихонов В. П., Миронов Н. А. Марковские процессы. М.: Советское радио, 1977. - 488 с.

52. Ушаков И. А. О вычислении среднего стационарного времени пребывания полумарковского процесса в подмножестве состояний // Извещение АН СССР. Техническая кибернетика. 1990. - № 4.

53. Котов В.Е. Алгебра регулярных сетей Петри,- Кибернетика, 1980, №5, с.10-18.

54. Котов В.Е. О параллельных языках,- Кибернетика, 1980, №3, с. 3-12 и №4, с. 1-10.

55. Финкельштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. 264 с.

56. Химмельблау Д. Прикладное нелинейное программирование. -М.: Мир, 1975. 534 с.

57. Шойер Э. Теория надежности. Исследование операций. М.: Мир, 1981. Т. 2. Сс. 314-343.

58. Юдин Д.Б. Задачи и методы стохастического программирования. М.: Сов. радио, 1979. 392 с.

59. Юдин Д.Б., Горяшко А.П., Немировский A.C. Математические методы оптимизации алгоритмов и устройств АСУ. М.: Радио и связь, 1982. 288с.134

60. Antamoshkin A. and Semenkin E. Local Search Under Optimizing Unimodal Pseudoboolean Functions. Informática 4 (1996). 18 pp.

61. Antamoshkin A., Semenkin E., Volovik M. The Models and Methods System for CAD of Spacecrafts Control Systems. Optimization-Based Computer-Aided Modeling and Design. Leidschendam: Lansa, 1992. Pp. 31-42.

62. Ларионов A.M., Литвинов A.B., Полюснин В.У., Цуканов Ю.П. Основные структурные особенности высокопроизводительных моделей ЕС ЭВМ,- Вопросы радиоэлектроники. Серия. Электронная вычислительная техника, вып. 5. 1977. с. 3-11.

63. Лебедев С.А. Электронные вычислительные машины,- В кн.: Сессия АН СССР по научным проблемам автоматизации производства. Пленарные заседания. Том 1,- М.: АН СССР, 1957, с. 162-180.

64. Линдси Ч., Мюйлен С. Неформальное введение в АЛГОЛ- 68: Пер. с англ. Л.Я. Лейфмана. / Под ред. А.П. Ершова.- М.: Мир, 1973,- 401с.

65. Липаев В.В. Проектирование математического обеспечения АСУ (Системотехника, архитектура, технология).- М.: Сов. радио, 1977,- 400с.

66. Baluja and R. Caruana. Removing the genetics from the standard genetic algorithm. In Proc. Of the 12th Intern. Conf. on Machine Learning, Lake Tahoe, 1995.

67. Brucker P., Hurink J., Werner F. Improving Local Search for Some Scheduling Problems. Part I and Part II. Osnabruecker Schriften zur Mathematik, Hefte 161-162, 1994.

68. De Jong K. An analysis of the behavior of a class of genetic Algorithms. Doctoral dissertation. University of Michigan, 1975.

69. Floudas C.A., Pardalos P.M. (Eds.) Recent Advances in Global Optimization New Jersey: Primceton University Press, 1992.

70. Freeman J., Skapura D. Neural Networks: Algorithms, Applications, and Programming Techniques. Houston. University of Houston at Clear Lake. Addison-Wesley, 1991.

71. Glover, F. (1977). Heuristics for Integer Programming Using Surrogate Constraints,Decision Sciences, Vol. 8, No. I, January, 156-166.

72. Glover, F. (1993) Tabu Thresholding: Improved Search by Nonmonotonic Trajectories, to appear in ORSA Journal on Computing.

73. Goldberg D.E. (1989). Genetic Algorithms in search, optimization and machine learning

74. Goldberg, K.Deb, H. Kargupta, and G. Harik. Rapid, accurate optimization of difficult problems using fast messy genetic algorithms. In S.135

75. Forrest, editor, Proc. Of the Fifth Int. Conf. On Genetic Algorithms, pages 56-64, San Mateo, 1993. Morgan-Kaufman.

76. Holland J.H. Adaptation in natural and artifical systems. Ann Arbor: The University of Mithigan Press, 1975.

77. Michalewicz Z. Genetic algorithms, numerical optimization and constraints. // Proc. of the Sixth Int. Conf. on Genetic Algorithms and their Applications, Pittsburgh, PA, 1995.

78. Майоров С.А., Новиков Г.И. Принципы организации цифровых машин,- Л.: Машиностроение. Ленинг. отделение, 1974.- 208с.

79. Майоров С. А., Новиков Г.И. Структура электронных вычислительных машин,- Л.: Машиностроение. Ленинг. отделение, 1979.-384с.

80. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer Verlag, New York, second edition, 1992.

81. Mühlenbein and D. Schlierkamp-Voosen. Predictive models for the breeder genetic algorithm I. Continuous Parameter Optimization. Evolutionary Computation, 1:25-49, 1994.

82. Mühlenbein and D. Schlierkamp-Voosen. The science of breeding and its application to the breeder genetic algorithm. Evolutionary Computation, 1:335-360, 1994.

83. Parmee I. (Ed.) Adaptive Computing in Engineering Design and Control. Proceedings of the 2nd International Conference, Plymouth, 1996. 325 pp.

84. Rechenberg I. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Stuttgart: Frommann-Holzboog (1973).

85. Schlierkamp-Voosen D., Mühlenbein H. Strategy Adaptation by Competing Subpopulations. Parallel Problem Solving from Nature (PPSN III), Jerusalem, Springer, 1994. Pp. 199-208.

86. Schwefel H.-P. Evolution and Optimum Seeking.-N.Y.:Whiley Publ.,1995.612pp.

87. Semenkin E. Search Discrete Optimization for CAD of Spacecrafts, Optimization-Based Computer-Aided Modeling and Design Leidschendam: Lansa, 1992. Pp. 43-50.

88. Semenkin E., Volovik M. Modeling and optimization of spacecrafts' system design. Operations Research. Berlin: Springer, 1995. Pp. 353-358.136

89. Semenkin E. et al. Adaptive search in spacecrafts systems design. Adaptive computing in engineering design and control. Plymouth: Plymouth University, 1994. Pp. 194-200.

90. Semenkin E. et al. Optimization tools for support of decision making in design of spacecrafts' systems. Operations Research.-Berlin: Springer, 1995. Pp. 329-334.

91. Основы теории вычислительных систем. I Под ред. С.А. Майорова,- М.: Высшая школа, 1978,- 408с.

92. Панфилов И.В., Половко A.M. Вычислительные системы. / Под ред. A.M. Половко,- М.: Сов. радио, 1980,- 304с.

93. Поляков Н.К. Основные принципы организации радиолокационного обеспечения боевых действий соединений ПВО, оснащенных АСУ,- В кн.: Материалы учения "Кристал-78",- М.: 1978, с. 20-36.

94. Пономарев В.А. Об одной конструкции конечного автомата асимптотически оптимального в стационарной случайной среде,-Биофизика, вып. 1, 1964, №9, с. 104-110.

95. Поспелов Д.А. Введение в теорию вычислительных систем,- М.: Сов. радио, 1982,- 280с.

96. Поспелов Д. А. Классификация структур алгоритмов, реализуемых на вычислительных системах,- Известия АН СССР. Техническая кибернетика, 1977, №5, с. 128-135.

97. Поспелов Д.А. О некоторых математических проблемах, возникающих при совместной работе нескольких вычислительных машин.-Труды МЭИ, вып.53,164, с. 97-110.

98. Прангишвилли И.В., Стецюра Г.Г. Микропроцессорные системы,- М.: Наука, 1980.-237с.

99. Пржиялковский В.В. Состояние и перспективы дальнейшего развития ЕС ЭВМ,- Вопросы радиоэлектроники. Серия. Электронная вычислительная техника, вып.5,1981, с. 3-9.

100. Frick A. Evolution programs and object-orientation. Evolutionary computation and its applications. Moscow: Presidium of the RAS, 1996. Pp. 5665.

101. Barbosa H.J.C. On genetic algorithms for min-max problems. Evolutionary computation and its applications. Moscow: Presidium of the RAS, 1996. Pp. 99-109.

102. Саати Т.JI. Элементы теории массового обслуживания и ее приложения: Пер. с англ. Е.Г. Коваленко. М.: Сов. радио, 1971.-520с.137

103. Северек Д.П., Кини В., Мэшберн X., Макконел С., Цао М. Исследование систем Ст тр, Ст* и C.Vmp. 1. Опыт обеспечения отказоустойчивости в мультипроцессорных системах. / Пер. с англ. под общей ред. A.C. Манделя. ТИИЭР, 1978, Т.66, №10, с. 89-117.

104. Синюкова Л.Ф., Штрик A.A. Оценка потерь производительности многопроцессорных комплексов при конфликтах в секционированной общей памяти,- Автоматика и телемеханика, 1978, №10, с. 192-199.

105. Слуцкин А.И., Цуканов Ю.П., Шаруненко И.М. Структурные методы уменьшения эффективного цикла двухуровневой оперативной памяти в мультипроцессорных системах.- Управляющие системы и машины, 1982, №2, с. 22-25.

106. Смирнов Ю.А., Лобанов Л.П., Рубцов B.C., Тимофеев Г.С., Коваленко Г.И. Моделирование деятельности сложных объектов радио и радиотехнической разведки автоматами с целесообразным поведением.-Деп. рукопись ЦИВТИ МО, 1982 (в печати).

107. Сокол Ю.М. Анализ эффекта совмещения работы процессора и памяти в мультипроцессорных системах,- Автоматика и вычислительная техника, 1981, №5, с. 8-16.

108. Техническая политика фирмы IBM. Организация НИР, ОКР и производства,- Радиоэлектроника за рубежом. Информационный Бюллетень,- М.: НИИЭИ по радиоэлектронике, вып. 13(881), 1979, с. 35-43.

109. Титов Ю.И., Шаханов В.А., Шмигельский В.Н. Модуль полупроводникового ОЗУ для микро-ЭВМ.- В кн.: Микроэлектроника и полупроводниковые приборы. / Под ред. A.A. Васенкова и Я.А. Федотова,-М.: Сов. радио, вып. 4, 1979, с. 139-148.

110. УК 5Э75: Техническое описание. КН.1. Управляющий комплекс 5Э75. ТО, 1970- 109с.

111. Универсальный язык программирования Ра /1./ Пер. с англ. под ред. В.М. Курочкина,- М.: Мир, 1968,- 352с.138

112. Файзулаев Б.Н. Поблема быстродействия элементной базы ЭВМ,- В кн.: Микроэлектроника и полупроводниковые приборы. / Под ред. A.A. Васенкова, Я.Е. Федотова.- М.: Сов. радио, вып. 6, 1981, с. 3-24.

113. Феллер В. Введение в теорию вероятностей и ее приложения. / Пер. с англ. под ред. Е.Б. Дынкина, с предисловием А.Н. Колмогорова,- М.: Мир, 1964.- 498с.

114. Феррари Д. Оценка производительности вычислительныз систем: Пер. с англ. А.И. Горлина, Ю.Б. Котова, Л.В. Ухова. / Под ред. В.В. Мартынюка.- М.: Мир, 1981,- 576с.

115. Халилов А.И. Алгоритмический язык для описания параллельных процессов (АЛГОПП).- В кн.: Автоматизация программирования, вып.З,- Киев: ИК АН УССР, 1978, с. 78-104.

116. Цетлин M.J1. О поведении конечных автоматов в случайных средах,- Автоматика и телемеханика, 1961, Т. XXII, №10, с. 1345-1354.

117. Цикритзис Д., Бернстайн Ф. Операционные системы: Пер. с англ. В.Л. Ушаковой и Н.Б. Фейгельсона. / Под ред. И.Б. Задыхайло и В.В. Мартынюка.- М.: Мир, 1977,- 366с.

118. Антамошкин А.Н. Оптимизация функционалов с булевыми переменными. Томск: Изд-во ТГУ, 1987. 104 с.

119. Штрик A.A. Оценка производительности многопроцессорных систем с приоритетным и неприоритетным обслуживанием в общей памяти.- Вопросы специальной радиоэлектроники. Серия. Телемеханика и системы управления, вып. 2, 1984, с. 96-105.

120. Штрик A.A. Приближенный расчет потерь производительности и определение загрузки многопроцессорных комплексов при конфликтах в секционированной общей памяти,- Управляющие системы и машины, 1979, №5, с. 29-34.

121. Штрик A.A. Производительность однородных многопроцессорных комплексов с общей памятью,- Управляющие системы и машины, 1978, №3, с. 55-61.

122. Абрамович К.Ю. Методы решения специальных классов задач оптимизации при синтезе управления космическими аппаратами. Дисс. на соиск. уч. степени канд. техн. наук. - Красноярск: CAA, 1997. 156 с.

123. Погребинский С.Б. Проектирование и надёжность многопроцессорных ЭВМ,- М.: Радио и связь, 1988.

124. Панадмитриу X. Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность,- М.: Мир, 1979.

125. Корнеев В.В. Параллельные вычислительные системы,- М.: "Нолидж", 1999. 320 с.

126. Семёнкин Е.С. Оптимизация технических систем,- Красноярск,1996.139

127. Рогов C.B., Терсков В.А., Нечушкин А.П., Тынченко C.B. Проектирование сложных систем с использованием многопроцессорных средств вычислительной техники // Отчёт. НИР "Механика". Красноярск: КВКУРЭ ПВО, 1997. 43 с.

128. Терсков В.А., Нечушкин А.П., Серенков В.И., Тынченко C.B. Исследование проблем совершенствования информационной подготовки курсантов и слушателей// Отчёт. НИР "Информатика-97",- Красноярск: КВКУРЭ ПВО, 1997. 65 с.

129. Тынченко C.B. Богомолов Н.П. Обработка радиолокационной информации в многопозиционном радиолокационном комплексе // Сб. тез. докладов XVIII военно-научной конференции ВА ПВО Тверь, 1998. Сс. 6869.

130. Богомолов Н.П., Тынченко C.B. Некоторые алгоритмы применения экстраполированной оценки координат цели в многопозиционном радиолокационном комплексе // Сб. тез. докладов XVIII военно-научной конференции ВА ПВО Тверь, 1998. С. 67.

131. Тынченко C.B. О согласовании характеристик специализированных процессоров при параллельных вычислениях И Сборник "Решетневские чтения" Материалы всероссийской научно-практической конференции, 1998. С. 152.

132. Тынченко C.B. Аппаратная реализация операций в информационных системах // Четвертая Всероссийская конференция "Проблемы информатизации региона" (ПИР-98), 1998. С. 269.

133. Тынченко C.B. Определение вероятностных характеристик вычислительной системы с произвольным числом типов потоков требований при организации параллельных вычислений // Информатика и системы управления, вып. 3,1999. Сс. 107-112.

134. Тынченко C.B. Метод прямого поиска для условной оптимизации в задачах выбора надёжных вариантов многопроцессорных вычислительных систем // Вестник НИИ СУВПТ, вып. 1, 1999. Сс. 56-61.