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

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

ПАНФИЛОВ ИЛЬЯ АЛЕКСАНДРОВИЧ

МОДЕЛИ И АЛГОРИТМЫ ВЫБОРА ЭФФЕКТИВНОЙ КОНФИГУРАЦИИ МНОГОПРОЦЕССОРНЫХ СИСТЕМ ОБРАБОТКИ ИНФОРМАЦИИ И УПРАВЛЕНИЯ

05.13.01 — Системный анализ, управление и обработка информации

АВТОРЕФЕРАТ

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

Красноярск - 2006

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнёва», г. Красноярск

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

Семенкин Евгений Станиславович

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

Петров Михаил Николаевич доктор технических наук, профессор Усаков Владимир Иосифович

Ведущая организация: Научно исследовательский институт автоматики и

электромеханики (НИИ АЭМ), г. Томск

Защита состоится 15 июня 2006 года в 14 часов на заседании диссертационного совета Д 212.249.02 при Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнёва» по адресу: 660014, г. Красноярск, просп. им. газ. Красноярский рабочий, 31.

С диссертацией можно ознакомиться в библиотеке Сибирского государственного аэрокосмического университета им. ак. Решетнева М.Ф.

Автореферат разослан 12 мая 2006 г.

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

И.В. Ковалев

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

Актуальность темы.

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

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

Целью работы является повышение обоснованности принятия решений при формировании эффективной конфигурации многопроцессорных систем обработки информации и управления.

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

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

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

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

4. Разработать и программно реализовать алгоритм, позволяющий осуществлять поиск решения в большом поисковом пространстве.

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

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

7. Разработать и апробировать систему поддержки принятия решений при формировании конфигурации многопроцессорных систем.

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

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

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

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

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

Практическая значимость. На основе предложенных моделей и алгоритмов разработаны современные программные системы, которые позволяют широкому кругу специалистов проектировать эффективную многопроцессорную вычислительную систему произвольной конфигурации для решения задач управления и обработки информации в режиме реального времени, а так же других сложных задач, к которым предъявляются соответствующие требования по надежности и производительности. Система поддержки принятия решений для выбора эффективной конфигурации многопроцессорных вычислительных систем зарегистрирована в отраслевом фонде алгоритмов и программ (№ ЕСПД .03524577.01437-01 99 01). Материалы исследования и разработанные программные системы были использованы при оценке существующих и разработке перспективных средств вычислительной техники в ФГУП ЦКБ «Геофизика» (г. Красноярск). Результаты проведенного анализа были включены в комплекс предложений по совершенствованию средств вычислительной техники для обработки геофизической информации с измерительных устройств в режиме реального времени.

Основные защищаемые положения:

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

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

3. Модифицированный генетический алгоритм многокритериальной оптимизации позволяет генерировать эффективные конфигурации МСОИУ по критерию производительность/стоимость.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях: X юбилейная Международная научно-практическая конференция «Современные техника и технологии», Томск, 2004; Международная научно-практическая конференция «Актуальные проблемы информатики и информационных технологий», Тамбов, 2004; VIII Всероссийская научная конференция с международным участием «Решетневские чтения», Красноярск 2004; 1-й Международный форум (6-я Международная конференция) «Актуальные проблемы современной науки», Самара, 2005; У1П Всероссийская конференция с участием иностранных ученых "Современные методы математического моделирования природных и антропогенных катастроф", Кемерово, 2005; IX Международная научная конференция посвященная 45-летию Сибирского государственного аэрокосми-чсского университета имени академикам. Ф. Решетнева, Красноярск, 2005; VI Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых), Кемерово, 2005; Международная школа-конференция по приоритетным направлениям развития науки и техники, Москва, 2006.

Публикации. По результатам диссертационной работы опубликовано 13 печатных научных работ, среди которых 5 статей. Список публикаций приведен в конце автореферата.

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

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

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

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

с параметром ц, а время обслуживания подчиняется экспоненциальному закону распределения с параметром щ. Параметры потоков зависят от величин Ты - относительных времен выполнения операций процессорами ¡-то типа, являющихся характеристиками аппаратной реализации спецпроцессоров, и от величины д - коэффициента связанности по памяти алгоритма обработки информации, реализуемого в МСОИУ, определяемого спецификой решаемой задачи обработки информации. Эти зависимости носят довольно сложный характер. Например, для задачи управления воздушным движением в системе с процессорами трех типов с быстродействием 0.66 мке, 8 мке и 57 мке, двумя шинами, с быстродействием 1.2 мке и коэффициентом связанности по памяти 0.35 параметры потоков запросов от процессоров будут соответственно 0.389, 0.225 и 0.003.

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

Алгоритм прямого вычисления производительности МСОИУ предложен В.А. Терсковым. Данный алгоритм при вычислениях основных показателей качества работы МСОИУ (производительности и надежности) использует характеристики самой МСОИУ: М— количество типов процессоров, т, — количество процессоров каждого типа ((= \,Ы ), п — количество шин связывающих процессоры с оперативной памятью. .

Оценки эффективности вычисляются через вероятности состояний системы

• тлк X

по формуле (1). Здесь .....- вероятность того, что в системе находится j¡ запросов от процессоров /-го типа, где /=1,2,..Л', к шин занято обслуживанием, I запросов находятся в очередях па обслуживание, М - суммарное число процессоров, А -—.

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

Р

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

~ X 2 .....

Л=0 л=0 ^лг -1=0 А М-к

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

П

¿-¡а 1-1

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

надежности МСОИУ являются: Ръ - вероятность безотказной работы с заданной производительностью - коэффициент готовности к работе с заданным уровнем производительности.

I

1\*1г...../*+[ »

Л =о^=о

Ке

РЕ-(1-РЕ) 2Р — 1

Эти показатели можно найти, зная вероятности Р^ ^.....^ , т.е. вероятности

пребывания системы в состоянии, когда]\ шин интерфейса исправны и участвуют в вычислительном процессе, а (/игу'О - неисправны и восстанавливаются, 72 процессоров первого типа исправны и участвуют в вычислительном процессе, а (гп2-Ц) - неисправны и восстанавливаются, процессоров второго типа исправны и участвуют в вычислительном процессе, а (»23-73) - неисправны и восстанавливаются,... ,уЛ+1 процессоров уУ-го типа исправны и участвуют в вычислительном процессе, а («л'+г/лч-О - неисправны и восстанавливаются.

ЛЛИ

/! |—г тЛ

АЧ-1

Пл

-Пк^

Л-

1=1

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

Чтобы выяснить способен ли алгоритм прямого вычисления производительности МСОИУ на основе модифицированных моделей находить упомянутые вероятности с необходимой точностью и быстрее классических методов решения СЛАУ, алгоритм сравнивался с методом Гаусса, методом Ш-разложений, методом релаксации, методом вращения, методом Жордана — Гаусса, а также итерационными методами решения СЛАУ.

В результате проведенного сравнительного анализа было показано, что ошибка алгоритма прямого вычисления производительности на основе модифицированных моделей при размерности СЛАУ 60 и более неизвестных, составляла порядка 10"2-10'3, тогда как ошибка классических точных методов решения СЛАУ оставалась на уровне не выше 10"6. Однако такая ошибка вычисления вероятностей состояния системы не является принципиальной - на этапе проектирования достаточно знать значение производительности в шкале отношений. Точность вычисления показателей производительности прямым методом и классическими отличается только в третьем знаке, что не может повлиять на упорядочивание альтернатив. Поэтому точность решения СЛАУ перестает играть первостепенную роль. В этой связи работа методов сравнивалась по трудоемкости. На рисунке 1 показана зависимость роста количества вычислений для сравниваемых методов от размерности СЛАУ при моделировании работы МСОИУ с процессорами 3х типов и одной шиной. Уже при размерности СЛАУ, равной 80, алгоритм прямого вычисления производительности МСОИУ требовал в десятки раз меньше вычислений, чем классические методы.

Применение для решения задачи итерационных методов решения СЛЛУ затруднено тем, что для получающихся СЛАУ не выполняются достаточные условия сходимости данных методов. 800000 700000 -

| 600000 -■

5

| 500000 -■

| 400000 -■

г

ь 300000 -■

I 200000 -■

£ 100000 -■ о -о

Рисунок 1 — Зависимость количества вычислений от размерности СЛАУ

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

Вторая глава диссертации посвящена решению задачи выбора эффективного варианта МСОИУ. В первом параграфе дается постановка задачи. Формальная запись построенной оптимизационной модели выглядит так: П„(и, тх, ..., mh ..., /яы, Гоъ - ,Тт, — , 2ом) тах, НЕ(и, тпи ..., mh ..., mN, Гоь ... ,Toi,..., r0N) -> шах,

С„(и, .......mu mN, Г01,... ,Toi,..., r0N) -> min

В данной модели приняты следующие обозначения: П„ - критерий оценки производительности, Н„ - критерий оценки надежности, Св - критерий оценки стоимости. п — количество шин, 1 < п < 1 б,

TTti — количество Гфоцессоров 1-го типа, 1 S от, <16, г = 1, iV, Tot — среднее время выполнения одной команды в процессоре г-ro типа, T0i>O,i = ÏN.

Разрабатываемые ранее методы построения оптимальной МСОИУ предполагали лишь выбор оптимальной структуры МСОИУ, т.е. оптимизацию по параметрам п, тп\, ..., /я,-, ..., тяц, при фиксированных Tôi.....Toi» ■•• > ^on- В данной работе производится также настройка параметров быстродействия спецпроцессоров Tot■ Выбор эффективного быстродействия спецпроцессоров необходим по той причине, что при фиксированном количестве шин, объединяющих процессоры с оперативной памятью, производительность МСОИУ в целом при простом увеличении быстродействия спецпроцессоров может уменьшаться за счет увеличения числа конфликтов, возникающих при одновременном обращении процессоров к оперативной памяти. Поэтому спецпроцессоры должны проектироваться именно с эффективным, а не максимальным, как до сих пор, быстродействием.

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

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

можно включение в систему до 20 спецпроцессоров каждого типа. Тогда при использовании аналитической модели имеется около 2010 возможных комбинаций. Если осуществлять поиск оптимальной конфигурации не только по структуре МСОИУ, но и по быстродействию спецпроцессоров, то общее число вариантов системы возрастет примерно до 1028. Кроме того, при выборе метода решения, данной задачи необходимо учитывать следующие факторы: переменные задачи выражены в различных шкалах измерения (целочисленные и вещественные переменные), оптимизация производится по нескольким экстремальным критериям одновременно, априорные сведения о свойствах целевых функционалов отсутствуют (оптимизация производится только по измерениям функционалов в фиксированных точках). Метод оптимизации должен учитывать условия накладываемые на критерии. Таким образом при выборе эффективной конфигурации МСОИУ возникает необходимость решения задачи многокритериальной условной оптимизации с алгоритмически заданными функциями разношкальных переменных высокой размерности.

Всеми необходимыми качествами для решения такой задачи обладает метод стохастической оптимизации, имитирующий естественный отбор в природе - генетический алгоритм. Для работы генетического алгоритма необходимо закодировать каждое решение в бинарную строку конечной длины — хромосому. Однако при решении рассматриваемой задачи алгоритм должен работать с вариантами МСОИУ произвольной конфигурации. То есть, заранее не известно не только значение параметров МСОИУ, но и их количество. Действительно, в качестве вариантов МСОИУ, которые рассматривает алгоритм, могут оказаться такие, которые отличаются количеством типов процессоров, а значит и количеством наборов данных. Поэтому для решения задачи выбора эффективной конфигурации МСОИУ генетический алгоритм должен быть существенно модифицирован, для работы с хромосомами разной длины не могут быть использованы традиционные операторы генетического алгоритма. Для решения этой проблемы был предложен и реализован оригинальный оператор процентного скрещивания, позволяющий скрещивать хромосомы разной длины. Схема одноточечного процентного скрещивания для случая, когда в качестве точки скрещивания выбирается точка — 25%, представлена на рисунке 2. Схема двухточечного процентного скрещивания представлена на рисунке 3, где в качестве точек скрещивания выбраны точки 25% и 70%.

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

ooooo Cooooooooooi ^ГосГаТ

(длина 12) хромосома-потомок 1

25% —(длина 20)

ш СиптТГ> SSSST

25%

111 000000000000000 (длина 18)

..... ......„ , . хромосома-потомок 2

00000 111111111 (длина 14)

Рисунок 2 — Схема одноточечного процентного скрещивания

----. ---—v. родительская

0000^0000000р[00000^ хромосома!

25% // 30% (длина20)

родительская 111)1111111 11) хромосома 2

<т _

25% 30% (длина 12)_

хромосома-потомок 1

111000000001111 (длина 15)

хромосома-потомок 2 00000111110000000 (длина 17)

Рисунок 3 — Схема двухточечного процентного скрещивания.

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

N

С = 1000-и + ^[1е(Г0,)-230-/и,] + 100-ТУ ¡=1

Здесь С — стоимость МСОИУ, 1000*» - стоимость всех шин, lg(Toi)*230 — стоимость одного процессора, эквивалентная быстродействию процессора, mi-количество процессоров г-го типа, 100+7V— затраты по обслуживанию, пропорциональные сложности системы.

В качестве инструментов многокритериального выбора эффективной конфигурации сначала были использованы наиболее известные эволюционные алгоритмы многокритериальной оптимизации FFGA (Fonseca, Fleming, 1995) и

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

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

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

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

Таблица 1 - Оценка качества работы методов FFGA, VEGA и гибридной схемы

Среднее значение производительности Среднее значение стоимости Интервал значений производительности Интервала значений стоимости

FFGA 16,71504 10,76092 19,52571 10,22850

VEGA 25,29618 24,54222 44,36946 23,53174

Гибридная схема 23,54195 16,47265 36,53255 17,49435

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

В ходе проведенных исследований было показано, что генетический алгоритм работает не хуже алгоритма локального поиска с разнесенным стартом, а при оптимальной настройке параметров генетический алгоритм с большей вероятностью получает результаты лучшие, чем мультистарт локального поиска. Кроме того, для своей работы ГА требует в несколько раз меньшего количества вычислений целевой функции, В таблице 2 представлены решения, нсулучшае-мые в смысле Парето, полученные мультистартом локального поиска более, чем за 2000 вычислений целевой функции, и генетическим алгоритмом за 400 вычислений целевой функции. Среди решений, полученных генетическим алгоритмом с размером популяции 40, в финальной популяции оказалось 10 решений, неулучшаемых в смысле Парето, тогда как мультистарт локального поиска получил только 3, причем все они доминируются решениями генет!гческо-го алгоритма.

Таблица 2 - Результаты работы модификации генетического алгоритма и мультистарта ло-

кального поиска

Решения полученные генетическим алгоритмом (400 вычислений целевой функции)

Стоимость 17.4 22.1 21.7 5.7 16.5 11.8 21.3 13.8 19.4 5.3

Производительность 30.6 40.5 39.5 15.3 28.6 18.2 34.4 22.1 30.6 8.1

Решения полученные мультистартом локального поиска (2000 вычислений целевой функции)

Стоимость 18.9 12.9 5.91 1

Производительность 25.3 16.2 14.9 1

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

В первом параграфе дается описание программной системы, созданной на основе предложенных алгоритмов. Программный продукт под названием «Система поддержки принятия решения выбора эффективной конфигурации многопроцессорных вычислительных систем» зарегистрирована в отраслевом фонде алгоритмов и программ (№ ЕСПД .03524577.01437-01 99 01). СППР позволяет генерировать многопроцессорные системы оптимальной структуры и с эффективным быстродействием специализированных процессоров. В качестве ре-

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

а

Настроят запуска} Своя МВС' Результаты |.

Парего оптимальные решения

Прсювщительность, Стоимость .

33.5225 21.7

15.3132 • 5.73

28.655? 1а54

18.2773 11.61

34.4348 21.3381

22136 13.835

306343 19.4«

8.19534 5385

• Среднее значение

ориэеедительнеети

Дисперсия сризеедигельноети •

Среснее значение стоимости

. Дисперсия стоимости ..

¡20.5317

(16775

Рисунок 4 — Вид рабочей области «Результаты»

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

Настройки залужё]] Слоя МВС ] Результаты |

Запуск ГА.

г-Н »стройки МВС-

4 Максимум типов ■ процессоров

Г

Быстроаейсгвие шин р ^

Коэффициент связанности рХ35"~

Выход

-Настройки ГА—

Количество поколений

рг

Вероятность мугаиии |0^01 Рвамер популод« рсГ*"

Многокритериальный [ррЗА механизм

Тип

скрещивания • .. ^.точечно* «г|

Рисунок 5 — Вид рабочей области программы «Настройки запуска»

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

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

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

'. Мультипроцессор ПС-2000 Г

УО УО VO • УО

8ГТЭ 8ИЭ 8ПЭ 8ПЭ

1

СВП

Е

СВП

Рисунок б — Структура ПС-2000

Мультипроцессор ПС-2000 состоит из структурированной совокупности однотипных ПЭ и общего устройства управления. Конструктивно восемь ПЭ объединяются в УО. Каждый ПЭ содержит арифметико-логическое устройство с набором регистров общего назначения, каждое устройство за 0,32 мке выполняет операции с фиксированной запятой над 24-разрядными регистровыми операндами. При этом, каждая операция считывания или записи выполняется за 0,96 мкс.

Таким образом, ПС-2000 можно представить как МСОИУ со следующими характеристиками: количеством шин п от 1 до 4, количество однотипных процессоров — 8, 16, 32 или 64, их быстродействие Тт =0,32 мкс, скорость обработки запроса в памяти т,=0,96 мкс. Подбирая быстродействие сразу для всех процессоров входящих в состав одного УО, мы имеем до 8 типов процессоров отличающихся быстродействием.

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

структуры МСОИУ. Решая данную задачу, достаточно определить оптимальное быстродействие для всех типов процессоров. Это позволяет значительно сократить поисковое пространство. Даже при небольшом количестве циклов работы генетического алгоритма удалось получить такой вариант набора параметров для МСОИУ, который превосходил изначальный, предложенный разработчиками ПС-2000, по относительной производительности более чем в 2 раза, и не уступал при этом по показателю стоимости. В таблице 3 приведены данные по трем МСОИУ. В первой строке находятся данные по модели МСОИУ ПС-2000, в таблице представлены быстродействия процессоров всех типов, а так же рассчитанная стоимость и производительность. Во второй и третьей строке представлены данные по двум моделям МСОИУ, предложенных СППР в качестве наиболее предпочтительных решений.

Таблица 3 - Данные по ПС-2000 и решениям полученным С1111Р

Стоимость Производительность То, То.? Тоз То4 Т05 Тоб То7 Тоз

1 12.2358 1.64394 0.32 0.32 0.32 0.32 0.32 0.32 0.32 0.32

2 15.045 4.69568 5.86 2.91 9.33 1.63 0.64 0.45 9.33 5.21

3 11.1412 3.65461 1.15 0.51 8.309 2.31 1.29 0.72 2.31 1.15

В третьем параграфе с помощью разработанных программных средств было подобрано оптимальное быстродействие спецпроцессоров для МВК «Эльбрус-2».

Вычислительные комплексы "Эльбрус-2" разрабатывались для систем ПРО, ЗРК С-300. МВК «Эльбрус-2» и сейчас используются в качестве управляющей машины в ПРО Москвы.

Система «Эльбрус-2» имеет производительность до 125 млн. оп./с над полноразрядными операндами при 10 процессорах, оперативная память с глубоким расслоением для увеличения быстродействия является общей. Блоки оперативной памяти соединяются с любым центральным процессором (их может быть до 10) через быстродействующий коммутатор. К этому же коммутатору подсоединяются периферийные процессоры, обслуживающие внешнюю память, периферию и линии связи.

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

В таблице 4 приведены результаты расчетов оптимального быстродействия для МВК «Эльбрус-2», различных конфигураций. Для всех вариантов МВК быстродействие шин 1.2 мкс, три типа процессоров. Для реальной МВК «Эльбрус-2» быстродействие процессоров различных типов равно соответственно О.бб мкс, 8 мкс и 57 мкс.

Таким образом, использование СППР для выбора эффективного быстродействия процессоров многопроцессорной системы обработки информации и управления позволяет не только значительно облегчить и ускорить процесс разработки МСОИУ, а значит сократить затраты на него, но и получать такие

варианты МСОИУ, которые по некоторым параметрам превосходят системы, разрабатываемые экспертами обычным образом.

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

Таблица 4 - Данные по МВК «Эльбруе-2» и решениям, полученным СШ1Р

Кол-во Кол-во процсссо- Стоимость реаль- Стоимость получе- Быстродействия

. шин ров . ной ной ;.■'. процессоров, мке

1-го 2-го 3-го Производи- Производи-

типа типа типа тельность реальной тельность полученой

1 1 1 3.70017 3.47593 2.8537; 8; 62.375

0.693788 1.15317

1. 5 5 5 3.70017 3.53116 2.9268; 8; 73.125

1.48895 4.81033

10 5 5 3.70017 3.50974 2.926; 9.12; 59.68

1.54061 5.62712

1 1 1 4.70017 . . 4.47698 2.9269; 8; 61,03

0.70855 1.17629

2 5 5 5 4.70017 4.47031 2.9268; 8; 59.687

2.61329 5.69036

10 5 5 4.70017 4.50362 2.92; 8.37; 63.718

2.74942 9.01551

1 1 1 7.70017 ■ 7.47698 2.9268; 8; 61.03

0.711456 1.17813

5 5 5 5 7.70017 - - ■ ' - : 7.47698 2.9268; 8; 61.03

3.43083 5.86831

10 5 5 7.70017 7.48336 2.9268; 8.75; 57

5.99941 9.69333

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

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

2. Показана эффективность применения на этапе проектирования алгоритма прямого вычисления производительности многопроцессорных систем.

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

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

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

6. Разработана система поддержки принятия решения для выбора эффективной конфигурации МСОИУ.

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

Публикации по теме диссертации

1 Ефимов С.Н. Формализация задач выбора эффективного варианта МВК распределенных систем управления / С.Н. Ефимов, И.А. Панфилов, Е.С. Семенкин, В.А. Терехов // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. — Вып. 4. 2003. - С. 2431.

2 Ефимов С.Н. Разработка методов автоматического проектирования МВС / С.Н. Ефимов, И.А. Панфилов // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. — Вып. 1 (8). 2006. - С. 22-36.

3 Панфилов И.А. Формализация задач выбора эффективного варианта МВК распределенных систем управления / И.А. Панфилов, В.А. Терсков // Вестник Красноярского государственного технического университета, вып. 14. - Красноярск: КГТУ, 2004. - С. 37-44.

4 Ефимов С.Н. Формализация задачи выбора эффективной производительности специализированных процессоров МВК управления в реальном времени / С.Н. Ефимов, И.А. Панфилов, В.А. Терсков // Транспортные средства Сибири. Вып. 10. - Красноярск: ИПЦ КГТУ, 2004. - С. 170-179.

5 Ефимов С.Н. Выбор оптимального состава специализированных процессоров для МВК распределенных систем обработки информации / С.Н. Ефимов, И.А. Панфилов, Е.С. Семенкин, В.А. Терсков // VIII Всероссийская конференция "Современные методы математического моделирования природных и антропогенных катастроф". — Кемерово, 2005 г. — http://www.ict.nsc.ru/ws/show abstract.dhtml?ru+126+9119.

6 Панфилов И.А. Система выбора оптимальной конфигурации многопроцессорного вычислительного комплекса с разнородными процессорами / И.А. Панфилов, Е.С. Семенкин, В.А. Терсков, С.Н. Ефимов // - М.: ВНТИЦ, 2006. - № ЕСПД .03524577.01437-01 99 01. - 9 с.

7 Панфилов И.А. Выбор метода решения системы линейных алгебраических уравнений для задачи оценки производительности многопроцессорных вычислительных комплексов / И.А. Панфилов // Современные техника и технологии. - Т.2. Томск: ТПУ, 2004. - С. 184-186.

8 Panfilov I.A. On investigation of direct performance evaluation algorithm for Multiprosseror computational system / I.A. Panfilov // Actual problems of informatics and intelligent techniques. - Tambov, 2004. - P. 76-77.

9 Панфилов И.А. Об исследовании алгоритма прямого вычисления производительности многопроцессорных вычислительных систем / И.А. Панфилов //«Решетневские чтения» —Красноярск: СибГАУ, 2004. - С. 158-159.

10 Панфилов H.A. О задаче выбора эффективного варианта МВС распределенных систем управления / И.А. Панфилов // Актуальные проблемы современной науки Труды 1-го Международного форума (б-й Международной конференции). Дополнительный сборник, Естественные науки. Ч. 45: Самара: СГТУ 2005.-С. 13-15.

11 Панфилов И.А. О генетическом алгоритме с переменной длиной хромосомы / И.А. Панфилов // «Решетневские чтения». — Красноярск: СибГЛУ 2005. - С. 223.

12 Панфилов И.А. Применение алгоритма мультистарт локального поиска при проектировании многопроцессорных вычислительных систем / И.А. Панфилов // VI Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых). - Кемерово: КемГУ, ИБС СО РАН 2005. - С. 24.

13 Егоров A.C. Разработка методов автоматического проектирования МВС / A.C. Егоров, И.А. Панфилов // Международная школа-конференция по приоритетным направлениям развития науки и техники., М.: РГУИТП 2006. -С. 27-29.

Панфилов Илья Александрович

МОДЕЛИ И АЛГОРИТМЫ ВЫБОРА ЭФФЕКТИВНОЙ КОНФИГУРАЦИИ МНОГОПРОЦЕССОРНЫХ СИСТЕМ ОБРАБОТКИ ИНФОРМАЦИИ И УПРАВЛЕНИЯ

Автореферат

Подписано к печати 11.05.2006 Формат 60x84/16. Бумага писчая. Печ. л. 1.0 Тираж 100 экз. Заказ № ¿В/ Отпечатано в отделе копировальной и множительной техники СибГАУ 660014 г. Красноярск, просп. им. газеты "Красноярский рабочий", 31

Введение

ГЛАВА 1 Модели оценки эффективности многопроцессорных систем обработки информации и управления

§ 1.1 Модель оценки производительности МСОИУ

§ 1.2 Модель расчета оценки надежности МСОИУ

§ 1.3 Методы решения СЛАУ

§ 1.4 Сравнительный анализ методов решения СЛАУ 38 Выводы

ГЛАВА 2 Постановка задачи и алгоритмы выбора эффективной конфигурации МСОИУ

§ 2.1 Постановка задачи выбора эффективной конфигурации МСОИУ

§ 2.2 Стандартный генетический алгоритм

§ 2.3 Алгоритмы многокритериальной оптимизации

§ 2.4 Разработка модифицированного генетического алгоритма для решения задачи выбора эффективной конфигурации МСОИУ

§ 2.5 Настройка параметров генетического алгоритма

§ 2.6 Метод случайного поиска для решения задачи глобальной оптимизации 86 Выводы

ГЛАВА 3 Практическая реализация моделей и алгоритмов

§ 3.1 Система поддержки принятия решений для выбора эффективной конфигурации МСОИУ

§ 3.2 Проверка работоспособности СППР на задаче выбора эффективного быстродействия процессоров

МСОИУ ПС-

§ 3.3 Проверка работоспособности СППР на задаче выбора эффективного быстродействия процессоров

МВК «Эльбрус-2»

Выводы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Разработать и программно реализовать алгоритм, позволяющий осуществлять поиск решения в большом поисковом пространстве.

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

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

7. Разработать и апробировать систему поддержки принятия решений при формировании конфигурации многопроцессорных систем.

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

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

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

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

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

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

Практическая значимость.

На основе предложенных моделей и алгоритмов разработаны современные программные системы, которые позволяют широкому кругу специалистов проектировать эффективную многопроцессорную вычислительную систему произвольной конфигурации для решения задач управления и обработки информации в режиме реального времени, а так же других сложных задач, к которым предъявляются соответствующие требования по надежности и производительности. Система поддержки принятия решения для выбора эффективной конфигурации многопроцессорных вычислительных систем зарегистрирована в отраслевом фонде алгоритмов и программ (№ ЕСПД .03524577.01437-01 99 01). Материалы исследования и разработанные программные системы были использованы при оценке существующих и разработке перспективных средств вычислительной техники в ФГУП ЦКБ «Геофизика» (г. Красноярск). Результаты проведенного анализа были включены в комплекс предложений по совершенствованию средств вычислительной техники для обработки геофизической информации с измерительных устройств в режиме реального времени.

Основные положения, выносимые на защиту:

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

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

3. Модифицированный генетический алгоритм многокритериальной оптимизации позволяет генерировать эффективные конфигурации МСОИУ по критерию производительность/стоимость.

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

Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях: X юбилейная Международная научно-практическая конференция «Современные техника и технологии», Томск, 2004; Международная научно-практическая конференция «Актуальные проблемы информатики и информационных технологий», Тамбов, 2004; VIII Всероссийская научная конференция с международным участием «Решетневские чтения», Красноярск 2004; 1-й Международный форум (6-я Международная конференция) «Актуальные проблемы современной науки», Самара, 2005; VIII Всероссийская конференция с участием иностранных ученых "Современные методы математического моделирования природных и антропогенных катастроф", Кемерово, 2005; IX Международная научная конференция посвященная 45-летию Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева, Красноярск,

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

Публикации

По результатам диссертационной работы опубликовано 13 печатных научных работ, среди которых 5 статей, список приведен в конце диссертации [16,18 - 21, 41 - 47, 89].

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

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

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

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

2. Показана эффективность применения на этапе проектирования алгоритма прямого вычисления производительности многопроцессорных систем.

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

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

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

6. Разработана система поддержки принятия решения для выбора эффективной конфигурации МСОИУ.

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

Заключение

1. Амелина Е. Т., Затуливетер Ю. С., Лазебник Е. Р., Медведев И. Л., Нейман А. В., Фищенко Е. А. Миграция временного разреза земли на параллельной ЭВМ ПС-2000 (Быстрое сейсмоголографическое преобразование Кирхгофа). Препринт М., ИПУ, 1992. 36 с.

2. Арлазаров В.Л., Волков А.Ф. Многопроцессорные вычислительные системы. — Москва: Наука, 1975.

3. Бабэ Б. Просто и ясно о Borland С++. М.: БИНОМ, 1994. - 400 с.

4. Бахвалов Н.С. Численные методы. М.: Наука, 1975 г.

5. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. — М.: Наука, 1987 г.

6. Бирюков А. Я., Голован Н. И., Медведев И. Л., Набатов А. С., Фищенко Е. А. Решающие поля многопроцессорных вычислительных систем. В кн.: Многопроцессорные вычислительные системы с общим потоком команд. М., ИПУ, 1978, вып. 19, с. 22-32.

7. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов Москва: Наука, 1981 г.

8. Виленкин И.Я. Комбинаторика. М.: Наука. Главная редакция физико-математической литературы, 1969. — 328 с.

9. Волков Е.А. Численные методы. М.: Наука, 1987 г.

10. Ю.Вороновский Г.К., и др. Генетические алгоритмы, искусственныенейронные сети и проблемы виртуальной реальности. X.: ОСНОВА, 1997.

11. Вычислительные комплексы ПС-2000. Проспект. Ротапринт, г. Се-веродонецк, НПО "Импульс", 1981. 30 с.

12. Гилл Ф., Мюррей У. Численные методы условной оптимизации. -Москва: Мир, 1977 г.

13. Головкин Б.А. Многопроцессорные вычислительные комплексы «Эльбрус». Обзор // Программирование, 1986, №4, с. 76-87.113

14. Гудас О.А., Елынин Е.Ю., Терсков В.А., Чичев С.В. Изобретение на специальную тему // АС №325229 1991 г.

15. Дубов Ю.А., Травкин С.И., Якимец В.Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука. Гл. ред. физ.-мат. лит., 1986. — 296 с. (Теория и методы системного анализа.)

16. Егоров А.С. Разработка методов автоматического проектирования МВС / Егоров А.С., Панфилов И.А. // Международная школа-конференция по приоритетным направлениям развития науки и техники. Тезисы докладов, М., 2006., с. 27-29/

17. Емельянов С.В., Ларичев О.И. Многокритериальные методы принятия решений. М.: Знание, 1985. — 32 с. - (Новое в жизни, науке, технике. Сер. «Математика, кибернетика»; № 10).

18. Ефимов С.Н. Разработка методов автоматического проектирования МВС / С.Н. Ефимов, И.А. Панфилов // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. Вып. 1 (8). 2006. - Сс. 22-36.

19. Канатников А.Н., Крищенко А.П. Аналитическая геометрия: Учеб. для вузов. 2-е изд. / Под ред. B.C. Зарубина, А.П. Крищенко. — М.: Изд-во МГТУ им. Н.Э.Баумана, 2000. 388 с.

20. Кини Р.Л., Райфа X. Принятие решений при многих критериях: предпочтения и замещения: Пер. с англ./Под ред. И.Ф. Шахнова. — М.: Радио и связь, 1981. 560 с. ил

21. Кударенко А.А., Лобанов Л.П., Пивоваров И.В. Терсков В.А., Тимофеев Г.С. Метод анализа одного класса систем массового обслуживания и его использование для оценки производительности вычислительных систем // Программирование, №5, 1988, С. 6-12.

22. Лебедев В.А., Терсков В.А. Моделирование и оптимизация многопроцессорных систем оперативного управления. — М.: МАКС Пресс, 2002.-330 с.

23. Липаев В.В. Распределение ресурсов в вычислительных системах. -М.: Статистика, 1979.-247 с.

24. Липаев В.В., Штрик А.А. Эффективность однородных вычислительных систем, работающих в реальном масштабе времени // Управляющие системы и машины, 1978, №1, С. 58-64.

25. MBK «Эльбрус» // Виртуальный компьютерный музей -http://www.computer-museum.ru/histussr/elbrus12.htm

26. Медведев И. Л. Принципы построения многопроцессорных вычислительных систем с общим потоком команд. В кн.: Многопроцессорные вычислительные системы с общим потоком команд. М., ИПУ, 1978, вып. 19, с. 5-21.

27. Медведев И. Л. Проектирование ядра структуры параллельных процессоров. М., Институт проблем управления, 1992 (препринт). 60 с.

28. Медведев И. Л., Фищенко Е. А. Об одном способе описания программно-доступных средств параллельного процессора. В кн.: Вопросы кибернетики. Вып. 92. М., НС по комплексной проблеме "Кибернетика" АН СССР, 1982, с. 43-67.

29. Микрокод ПС-2000. Руководство программиста. 3.400.027-013301. Ротапринт. Северодонецк, НПО "Импульс", 1983.

30. Мультипроцессорные системы и параллельные вычисления // Под ред. Ф.Г. Энслоу; Пер. с англ. Ю.С. Голубева-Новошилова и А.А. Щерса. -М.: Мир, 1976. -374 с.

31. Новохатный А.А. Экспедиционные геофизические комплексы на базе многопроцессорной ЭВМ ПС-2000. / В. А. Трапезников, И. В.

32. Прангишвили, , В. В. Резанов. Приборы и системы управления, 1981, №2, с. 29-31.

33. Овчаров J1.A. Прикладные задачи теории массового обслуживания -М.: Машиностроение, 1969, 324 с.40.0хорзин В.А. Численные методы в системе MATHCAD — Красноярск, 2003 г.

34. Панфилов И.А. О генетическом алгоритме с переменной длиной хромосомы // Решетневские чтения. Красноярск: СибГАУ 2005., с. 223.

35. Панфилов И.А. Об исследовании алгоритма прямого вычисления производительности многопроцессорных вычислительных систем. / Решетневские чтения. — Красноярск: СибГАУ, 2004.- Красноярск 2004., с. 158-159.

36. Панфилов И.А. Система выбора оптимальной конфигурации многопроцессорного вычислительного комплекса с разнородными процессорами / И.А. Панфилов, Е.С. Семенкин, В.А. Терсков, С.Н. Ефимов // М.: ВНТИЦ, 2006. - № ЕСПД .03524577.01437-01 99 01.-9 с.

37. Панфилов И.А. Формализация задач выбора эффективного варианта МВК распределенных систем управления / Панфилов И.А., Терсков В.А. // Вестник Красноярского государственного технического университета, вып. 14. Красноярск: КГТУ, 2004, с. 37-44.

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

39. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. М., «Сов. радио», 1975, 192 с.

40. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука. Главная редакция физико-математической литературы, 1982. — 256 с.

41. Прангишвили И. В., Виленкин С. Я., Медведев И. Л. Многопроцессорные вычислительные системы с общим управлением. М., Энергоатомиздат, 1983. 312 с.

42. Растригин Л.А. Случайный поиск. М.: Знание, 1979.

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

44. Рубан А.И. Методы анализа данных. Учеб. пособие: В 2 ч. Ч. 2; КГТУ. Красноярск, 1994, 125 с.

45. Рубан А.И. Методы оптимизации: Учебное пособие. Изд. 2-ое. Красноярск НИИ ИПУ, 2001.528 с.

46. Саати Т.Л. Элементы теории массового обслуживания и ее приложения // Пер. с англ. Е.Г. Коваленко. / Под ред. И.Н. Коваленко с предисловием Б.В. Гнеденко. М.: С.в. радио, 1971.- 520 с.

47. Самарский А.А., Гулин А.В. Численные методы: Учеб. пособие для вузов.—М.: Наука, 1989 г.

48. Саульев В.К. Математические теории массового обслуживания — М.: Статистика, 1979. 96 с.

49. Семенкин Е.С., Семенкина О.Э., Коробейников С.П. Оптимизация технических систем. Учебное пособие. — Красноярск: СИБУП, 1996.284 с.

50. Семенкин Е.С., Терсков В.А. Модели и методы оптимизации сложных систем. — Красноярск: СибЮИ MB РФ, 2000. —211 с.

51. Терсков В.А. Модели функционирования и методы оптимизации структуры многопроцессорных вычислительных систем. — Красноярск: СибЮИ МВД РФ, 2001. 215 с.

52. Турчак Л.И. Основы численных методов. / Под редакцией Щенни-кова В.В. М.: Наука, 1987 г.

53. Фищенко Е. А. Выбор системы команд для многопроцессорной вычислительной системы с общим потоком команд. В кн.: Многопроцессорные вычислительные системы с общим потоком команд. М., ИПУ, 1978, вып. 19, с. 33-39.

54. Фищенко Е. А. Принципы построения мнемокода многопроцессорных вычислительных систем с общим управлением. В сб.: Всесоюзное научно-техническое совещание "Проблемы создания и использования высокопроизводительных машин". М., ИПУ, 1979, с.108-110.

55. Хаймен М. Borland С++ для «чайников». К.: «Диалектика», 1995. -416с.

56. Харт-Дэвис Г. Microsoft Windows ХР Professional. Полное руководство. СП ЭКОМ, 2003. - 816 с.

57. Черноруцкий, И.Г. Методы оптимизации и принятия решений: Учебное пособие / И.Г. Черноруцкий СПб: Лань, 2001 - 384 с.

58. Шамис В.А. С++ Builder 3 Техника визуального программирования М.: Нолидж, 1998 г.

59. Back, Hoffmeister, Schwefel. A Survey of Evolution Strategies. / Proc. 4th International Conf. on Genetic Algorithms, 1991.

60. Baker, J. (1985) Adaptive selection methods for genetic algorithms. Proc. International Conf. on Genetic Algorithms and Their Applications. J. Grefenstette, ed. Lawrence Erlbaum.

61. Baker, J. (1987) Reducing Bias and Inefficieny in the Selection Algorithm. Genetic Algorithms and Their Applications: Proc. Second International Conf. J. Grefenstette, ed. Lawrence Erlbaum.

62. Baluja S. The Equilibrium Genetic Algorithm and the Role of Crossover. 1993.

63. Beasley, Bull, Martin. An Overview of Genetic Algorithms: Part2, Research topics. / University Computing, 15(4), 1993. p. 170-181

64. Caruana R., Schaffer J., Representation and Hidden Bias: Gray vs. Binary Coding for Genetic Algorithms. — Proc. 5th International Conference of Machine Learning, 1988.

65. Cieniawski S. E. An investigation of the ability of genetic algorithms to generate the tradeoff curse of a multi-objective groundwater monitoring problem. Master's thesis. University of Illinois at Urbana-Champaign. 1993.

66. Coello Coello C. A. A comprehensive survey of evolutionary-based multiobjective optimization techniques.

67. Cohon, J.: Multiobjective Programming and Planing, John Wiley, New York (1978).

68. De Jong K.A., Spears W.M. An Analysis of the Interacting Role of Population Size and Crossover in Genetic Algorithms.

69. Fonseca C.M., Fleming P.J. Multiobjective optimization and multiple constraint handling with evolutionary algorithms Part I: A unifiedformulation. Technical report 564, University of Sheffield, Sheffield, UK, January 1995.

70. Fonseca C.M., Fleming P.J. Multiobjective optimization and multiple constraint handling with evolutionary algorithms Part II: Application example. Technical report 565, University of Sheffield, Sheffield, UK, January 1995.

71. Goldberg, D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesly, 1989.

72. Horn, J., Nafpliotis N., Goldberg D. E. A niched Pareto genetic algorithm for multiobjective optimization. In Proceedings of the First IEEE Conference on Evolutionary Computation, Vol. 1, Piscataway, 1994. -P. 82-87.

73. Kauffinan S.A. (1989). Adaptation on rugged fitness landscapes. In lectures Notes on Complexity, D. Stein (Ed.), Addition Wesley, 527-618.

74. Koski J., Oscyczka A. Multi-criteria Desighn Optimization. Springer-Verlag, 1990.

75. Kursawe F. Breeding ES first results // Seminar "Evolutionary algorithms and their applications", 1996.

76. Muhlenbein H., Voigt H.-M. Gene Pool Recombination in Genetic Algorithms. In Proc. Of the Metaheuristics Inter. Conf., 1995.

77. Panfilov I.A. On investigation of direct performance evaluation algorithm for Multiprosseror computational system. I I Actual problems of informatics and intelligent techniques. Tambov, 2004., P. 76-77

78. Reeves C.R. Using Genetic Algorithms with Small Populations. / Proc. of the 5th International Conference on Genetic Algorithms, 1993.

79. Schaffer, J. D. Multiple objective optimization with vector evaluated genetic algorithms. In J. J. Grefenstette (Ed.), Proceedings of an International Conference on Genetic Algorithms and Their Applications, Pittsburgh, PA, 1985. P. 93-100.

80. Srinivas, Deb. Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms. / Evolutionary Computation, vol. 2 (3), 1995.

81. Steuer, R.E.: Multiple Criteria Optimization. John Wiley, New York, (1986).

82. Whitley D. Modeling Hybrid Genetic Algorithms.

83. Wolcott P., Goodman S. E. Computing under the stress of economic reform: the case of high perfomance computing in the former Soviet Union. Communications of the ACM, October, 1993, p. 25-29.

84. Wolcott P., Goodman S. E. High-Speed computers of the Soviet Union. Computer, September, 1988.

85. Zitzler E., Thiele L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach // IEEE Transactions on Evolutionary Computation, 1999.