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

Г0СУДДРСТЕЕ1ШШ"! КОМИТЕТ СССР ПО НАРОДНСШ" ОБРАЗОВАНИЮ

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

На праЕах рукописи ЭДК 681.322-181.5

МУСШШЦ Михаил Томасович

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

Специальность 05.13.05 ~ "Элементы и устройства вычислительной техники и систем управления"

АВТ0РЕ32РАТ диссертации на соискание ученой степени кандидата технических наук

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

1990

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

Научный руководитель: доктор технических наук, профессор ЛЗШОВ Ю.В.

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

МУСАТОВ В.В.

кандидат технических наук, старший научный сотрудник ВЕСЕЛОВСЮЙ Г. Г.

Ведущее предприятие: ШО Точных Приборов, г.Москва

Защита диссертации состоится "_"_1990 г. на

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

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

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

Адрес института: I2587I, г.Ыосква, ГСП, Волоколамское шоссе д.4, МАИ.

Автореферат разослан "_"_1990 г.

Ученый секретарь специализированного Совета к.т.н., доцент

А.К.Шашурин

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

Актуальность пообдемн. К специализированным вячислзтельным системам (ВС), устанавливаемым яа борту некоторых летательных аппаратов (ЛА), в настоящее время предъявляются требования по быстродействию порядка 10 млн я более операций в секунду. Таким требованиям удовлетворяют ВС, относящиеся к классу параллельных векторных вычислительных систем с общш управлением и разделенной память®, отличительной чертой которых является большое отяо-иенда производительности к аппаратурным затратам. Алгоритмы задач, решаемых на ВС данного класса, разбиваются на ряд ветвей, каждая из которых обрабатывается на отдельном процессорном элементе (ПЭ), входящем в решающее поле (ГО). Во всех ПЭ вычисления производятся по одной программе. В процессе вычислений осуществляется информационный (межпроцессорный) обман между ветвями алгоритма, реализуемый структурой внутрисистемных связей, являющейся частью решающего поля БС. Скорость межпроцессорного обмена существенно влияет на быстродействие БС. Критерием, определяющим скорость обдана, является "близость" графа, описывающего структуру внутрисистемных связей, к графу, описывающему алгоритм решаемой задача. При несовпадении указанных графов в ВС могут быть большие потеря производительности, сводящие к нули преимущества от распараллеливания вычислений. Для проектирования структуры связей можно воспользоваться известным методами определения графа структуры по информационному графу алгоритм. Известно, что решение последней задачи неоднозначно как с точки зрения вида графа структуры, так з по способу организации обмена. При создании вычислительной системы, ориентированной на выполнение множества задач с заранее известными информационными графами алгоритмов, для определения универсальной структуры внутрисистемных связей удобно воспользоваться указанной неоднозначностью. Тогда проектирование структуры внутрисистемных связей,решающего поля ВС сводится к выбору лучшего варианта структуры из множества конкурирующих вариантов, холученных при исследовании алгоритмов задач, для решения которых предназначена проектируемая ВС.

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

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

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

1) - формализовать понятие "лучшая для .данной ВС структура связей";

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

Дедь диссертационной работы.

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

- Составление набора существенных характеристик для оценки

и сравнения вариантов структуры внутрисистемных связей дая данного класса ВС.

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

- Сравнительный анализ разработанных вариантов структуры и

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

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

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

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

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

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

1. Обобщены характеристики оценки структуры- многопроцессорных ВС. Для класса параллельных векторных систем с общим управлением преодолен набор из 24 характеристик оценки структуры внутрисистемных связей. Проведен сравнительный анализ распространенных на практике вариантов структуры связей для данного класса ВС.

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

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

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

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

Аптсбэшм работы. Основные положения диссертационной работы докладывались и обсуждались на:

- XI Всесоюзной научно-технической конференции молодых ученых и специалистов (Москва, 1985 г.);

- П Всесоюзном совещании-семинаре "Метода синтеза и планирования развития структур крупномасштабных систем" (Саратов,1986г);

- Научно-техническом совещании Секции управляющих вычислительных комплексов Научного Совета АН СССР, посвященном проблеме "Повышение надежности и эффективности управляющих вычислительных комплексов" (Кишинев, 1986г.);

- Научно-техническом совещании, проводимом Секцией управляющих вычислительных комплексов (УЖ) Научного Совета АН СССР и посвященном проблеме "Автоматизация проектирования УВК" • (Москва-Ярополец, 1987г.);

- Межреспубликанской школе-семинаре "Анализ и синтез распределенных информационно-управляющих систем" (Батуми, 1987г.);

- И-ей Всесоюзной конференции "Проблемы и методы принятия решений в организационных системах управления" (Москва-Звенигород, 1988г.);

- Межотраслевом научно-техническом совещании "Проблемы повышения технического уровня я качества средств вычислительно® техники" (Москва, 1989г.).

Публикации: по материалам диссертационной работы опубликовано 10 печатных работ.

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

Общий объем работы 168 страниц, включая 21 рисунок, 4 таблицы. Библиография - 91 наименование.

СОДЕКШМЕ РАБОТЫ

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

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

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

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

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

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

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

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

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

1. Используемый в структуре принцип разделения каналов связи.

2. Вид графа, описывающего структуру.

3. Количество каналов в структуре связей.

4. Регулярность структуры связей.

5. Еазделенность портов входа-выхода.

6. Число портов входа-внхода.

7. Симметричность портов входа-выхода.

8. Способность к перестроению структуры.

; 9. Способ прокладки путей соединения в структуре.

-10. Длина соединительного пути в структуре.

11. Доступность элементов структуры.

12. Едокируемосгь каналов связи в структуре.

13. Избыточность структуры связей.

14. Способ получения настроечной информации.

15. Язык управления структуры.

16. Число элементов коммутации.

17. Сложность элементов коммутации

а

18. Наращиваемость структуры.

19. Величина временных потерь от простоев.

20. Надежность структуры связей.

21. Контролируемость структуры.

22. Возмсошосгь частичной деградации при отказах.

23. Живучесть структуры.

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

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

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

В данной задаче известны множество альтернатив-вариантов структуры, множество характеристик, по которое можно оценить каждую альтернативу. Неизвестен принцип оптимальности, формализующий понятие "лучшая структура связей". В такой постановке задачи решаются методом теория принятия решений и многокритериального выбора. Согласно данной теории альтернативы X(¿=1, 2.....Н- ) рассматриваются как векторы их оценок

Х4, « ( Х4,Х/уу )■ Задача выбора записывается парой <Х , 0П>, где X - множество альтернатив, ОП - принцип оптимальности, в качестве которого в работе предлагается использовать бинарное отношение предпочтения

А .

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

При анализе наиболее существенных трудностей, возникающих

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

- многоаспектный характер оценок качества альтернатив, требующий осуществления сравнений альтернатив по совокупности всех характеристик и выбора в условиях компромисса;

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

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

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

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

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

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

В работе отмечается, что перечисленные метода не могут быть

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

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

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

- представление экспертных,оценок с использованием аппарата теории полезности, то есть посредством функций полезности;

- применение парных сравнений альтернатив, облегчающее согласование характеристик;

- процесс шкалирования доджей позвшить использовать харак-

теристики с любыми шкалами измерения;

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

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

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

Рассмотрим простейший случай: сравнение двух альтернатив. Пусть X - множество сравниваемых альтернатив, , I =1,

; й - множество характеристик а-(хЙ = 1,2,..,, Уп. . Условие задачи выбора представляется набором векторов оцеНОК ^

X — ( Х-1} Хг,..., ••• ^ )}

где Х^ - оценка альтернатива х'^по характеристике .

Цусть оценкам любой характеристики- может бнть поставлена

в соответствие функция полезности О)^(х) , ^ = 1,2,...,по. . Полезность каждой альтернативы может быть представлена в виде

(I)

Будем считать, что альтернатива X предпочтительнее альтернативы X* ( X' Xя ), если

Ы(Х') ^ ЬПХ") (2)

м т

2б);(Х») (3)

¿«1 У ' « '

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

тогда (4) можно переписать в следующем виде

21 (с*х (х') - о>:(х")) > 2 ( (хп) - оЗ{(х*)) (б) ¡&Е * 4 ' 4 л '

Будем говорить, что по характеристикам'из множества Е имеет место положительный прирост полезности, по характеристикам из множества & - отрицательный прирост полезности. Тогда решение о предпочтении одной из двух сравниваемых альтернатив можно принять, если сравнить по величине суммарный положительный и отрицательный прирост полезности. Для формализации сравнений введем в рассмотрение вектор парных сравнений -

где

Л-1

' + I, если х') ¿¿¿С*')

О, если ¿¿¿(х') - (X*) (8)

I- I. есл

Каждая компонента р^ вектора парных сравненийр ' , отличная от нуля, соответствует некоторому приросту полезности, который при существовании функций ^Сх) имеет определенную величину. Предложим эксперту расставить компоненты р^ в векторе р>(*> * * в порядке убывания соответствующей величины прироста полезности. Тогда решение о предпочтении между сравниваемыми альтернативами можно принять формальным путем, если в векторе р(Я,!< > множества компонент " +1" (Е) и компонент "-Г(<г ) находятся в сюръектив-ном функциональном соответствии Р (& -Р(д) ; ее. £ £ ), то есть выполняется условие (5).

При сравнении нескольких альтернатив на шкалах ^¿(х) тлеется не пара, а большее число значений. Для формализации сравнений можно ввести порядковую (ранговую) функцию полезности ^¿(х). £ =1,2,... ,т- . Оценку альтернативы, имеющую ранг полезности К но характеристике ^(х) будем обозначать Х^ . Рассмотрим две альтернативы х' и Xй , имеющие ранги полезности соответственно К1 и к" . Тогда разницу в полезности между этими альтернативами по ] -ой характеристике можно выразить суммой разниц промежуточное рангов полезности

- Ч-(*Г) - +

(**;-<) - (9)

Условие предпочтения выражается по аналогии с (4)

(ю)

Лножества с и & образуются по аналогии с (5)

к' > к", Ui(xf) > C0j (xf) =i»je E

К* -с K", £0j (xf) < (xf) => j <=• d-

тогда условие (6) можно зависать так:

Для сравнения по величине положительного и отрицательного прироста полезности в векторе (7) необходимо поставить в соответствие каждой компоненте не характеристику, а разницу полезностей между соседними рангами полезности [¿*Jj ( Xj ) - CJ^(Xj~') ] Дня формализации сравнений в этом случае, удобно заменить исход- . вые векторы оценок Х^ на векторы c/J^ оценок альтернатив в шкалах (*j) : •

об'Ч» (ci1}eCn...fc6'r.r..J (12)

где Л/ - J1-00™ ui(*j) Щ*!)»

Г если Ы{( Xj)< ¿¿¡(х/)4& odj(Xj) < ¿¿/xp);

(xj) - полезность оценки XjK , имеющей ранг К (фиксированная дая г -ой компоненты) полезность рассматриваемой оценки альтернативы t as иг X KU.

Таким образом, веютор оценок об "кодирует"'полезность альтернативы x.ft' относительно фиксированных кахсдой компонентой вектора оС'*"' значений (рангов) полезности функций "tfjfXj) , j =1,

Векторы парных сравнений^» ' относительно (7) и (8) примут следующий вид

Р«>\ (Р^Ргу.^РгТ^Ре), ™

где Г + I, если <¿0. >■</.£

J2y = < 0, если «(.*'=

1-1, если <с об-*" Компоненты вектора парных сравненийJb' '* 'характеризуют сравнительную величину полезности оценок Wjfxj)» относительно.ранга К полезности пкаяьг Vj(Xj) . (

Произведя расстановку компонент jb?, в векторе^*'* ' в соответствии с убыванием величины соответствующих разниц [ ^ (Xj )-— WjixT ^l полезности и воспользовавшись соответствием Р , можно проверить условие предпочтения (II) и выделить лучший объект из каждой пары. Если в некоторых векторах pixi*) соответствие не выполняется, то путем проведения дополнительной экспертизы, 14

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

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

Проведенный сравнительный анализ предлагаемого метода выбора с методами, рассмотренными в предыдущей главе, позволяет отметить ряд его достоинств:

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

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

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

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

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

Первым этапом решения задачи выбора структуры ГО является определение назначения СЩЗ и анализа алгоритмов решанмых задач. Б результате проведенного анализа бшга выявлена задача управления .движением ЛА, требующая от СЦП наибольшей вычислительной мощности и заметно превосходящая все остальные задачи по объему обрабатываемых даЕКых. Задача управления движением ЛА заключается в коррекции направления движения ЛА в процессе полета. Коррекция осуществляется путем нолучеюя гояоградшческого изображения мест-

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

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

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

На следующем этапе выбора структуры была произведена оценка 'рассматриваемых альтернативных вариантов. Для всех характеристик, описанных в первом главе работы, проводилась проверка взаимной независимости по предпочтению в условиях данной задачи. Для оценки рассматриваемых вариантов структуры из 24 характеристик было отобрано двенадцать. (Остальные характеристики или не описывают тлеющиеся варианты структуры, или не удовлетворяют условию независимости по предпочтению, или не различают рассматриваемые варианты структуры (последние имеют равные оценки по данным характеристикам) ).

Далее производится сравнительная оценка вариантов структуры (альтернатив) по кандой характеристике в отдельности, результатом которой является получение ранговых функций полезности ,

^ =1,2,...,12.

На следующем этапе выбора структуры формируются векторы оценок в.ранговых шкалах , \ = 1,2,...,12 и векторов парных

сравнений. Количество компонент в векторах оценок и парных сравнений определяется суммарным количеством рангов (21(функций I = 1,2,...,12. Для определения порядна компонент в векторах необходима экспертиза. Эксперту необходимо упорядочить по величине разницы в полезности ( измеряемые в шкалах (¿¿(х) ) между всеми соседними рангами полезности функций (*) . Для этого эксперту предъявляются попарно участки шкал , заключенных между соседними рангами соответствующих • Например, эксперт долкен ответить на вопрос типа: "Что для Зас является более предпочтительным: сокращение валентности ПЭ ог трех айн входа-выхода до двух ззн входа-выхода, или уменьшение количества коммутирующих элементов в структуре от в до б , при прочих равных условиях?". Эксперт долкен дать лишь качественный ответ, например: "Более предпочтительным является указанное сокращение валентности". Другие варианты ответов: "Более предпочтительным является данное уменьшение числа коммутирующих элементов", зли "Данные величины приблизительно равноценна". Таким образом, эксперт должен разделить свои предпочтения на три качественных уровня. Опыт применения данного метода выбора на практике показывает, что для эксперта, являющегося разрабочиком вычислительной системы, дать достоверный качественный ответ на подобные вопросы нэ является трудоемкой задачей.

В рассматриваемой.задаче выбора структуры векторы оценок сС и парных сравненийсодержат 19 компонент (разрядов). Путем применения известного алгоритма выбора из дерева (описанного Д.Кнутом), число вопросов, задаваемых эксперту для получения полного упорядочения компонент в векторах, уменьшено до 87. Если проводить экспертизу по методу Р.Л.Кинп и Х.Райфа, в данной задаче потребовалось бы минимум 255 вопросов, требующих от эксперта ответов в числовом виде, что более трудоемко и вследствпп большей сложности вопросов может- привести к ошибочным выводам.

После получения порядка компонент в векторах, дальнейшее действие по выбору структуры носит чисто формальный характер и не требует участия эксперта. Формирование векторов оценок производится согласно (12), векторов парных сравнений - согласно (13). Определение предпочтения в каждой сравниваемой паре альтернатив производится по взаимному расположению компонент "I" и "~Г" в векторах р(*'>*') . Если в векторе парных сравнений компоненты мшиэствз Е С+1") расположены согласно соответствию Р левее

компонент множества (г ("-1"), го фиксируется предпочтение первой из двух сравниваемые альтернатив. (Предпочтение второй альтернативы ысано определить, поменяв порядок сравнения на обрат-ннй и заменив знаки у- единичных: компонент вектора).

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

4. С практической точки зрения разработанный метод отличается тем, что:

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

- существенно снижена трудоемкость экспертизы при малом числе сравниваемых альтернатив и большом числе характеристик;

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

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

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

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

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

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

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

ПУШИКАШИ СОИСКАТЕЛЯ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

I. Любатов Ю.В., ЭДусинянц М.Т. Сужение области выбора при оптимизации структур сложных систем// Тезисы докладов П Всесоюзного совещания-семинара "Методы синтеза и планирования развития

структур крупномасштабных систем". - Саратов: С1У им.Н.Г.Чернышевского, 1986. - С.72-73.

2. Любатов Ю.В., Мусинянц M.Т. Решение многокритериальных задач выбора при проектировании вычислительных систем// Тезисы докладов и сообщений Межреспубликанской школы-семинара "Анализ и синтез распределенных информационных управляемых систем". Батуми. Октябрь 1987. - Тбилиси: Мецниереба, 1987. - С.61-62.

3. Любатов Ю.В., 1Дусинянц М.Т. Многокритериальный выбор: шкалирование по приросту полезности// Тезисы докладов III Всесоюзной конференции "Проблемы и методы принятия решений в организационных системах управления". Звенигород. Дек. 1988. - М. : ВШИТИ, 1988.-С.126-127.

4. Любатов Ю.В., Цусинянц М.Т. Метод парных сравнений в задаче выбора архитектуры вычислительной системы// Проблемы управления движением и навигации. - М.: АН СССР, 1987, № 18 , - С.Г5.

5. Любатов Ю.В., ВДусинянц М.Т. Сравнительная оценка вычислительных средств по полезности альтернатив// Проблемы управления движением и навигации. - М. : АН СССР, 1988, 19, - С.23,

6. Любатов Ю.В., Мусинянц М.Т. Метод сравнительной оценки качества средств вычислительной техники (СБГ)// Тезисы докладов Межотраслевого научно-технического совещания "Проблемы повышения технического уровня и качества средств вычислительной техники".-М.: ВНИИПВТИ, 1989. - С.20-2Г.

7. Мусинянц М.Т. Сравнение и выбор альтернатив при решении технических задач// Рук. цеп. в ВИНИТИ. Деп. № 6912-389 от £5.11.89. - 15 с.

8. [Дусинянц Ы.Т. Сравнительный анализ структур вычислительных систем .для ШФ// Рук. деп. в ЖНИТИ. Деп. В 7389-В89 от 13.12.89. - 27 с.

9. Любатов Ю.В., Цусинянц М.Т. Проблема транзитивности в задачах выбора вычислительных средств// ^ук. деп. в ВИНИТИ. Деп. № 69I0-B89 от 15.11.89. - С.9.

10. Любатов Ю.В., ;<1усинянц М.Т. Анализ применения теории полезности при выборе альтернатив в технике// Рук. деп. в ВШИТИ. Деп. & 69II-B89 от 15. П. 89. - С. 16.

Техн.редактор Е.А.Смирнова Подписано к печати ОБ.ЮЛО

Бум. офсетная. Формат 60x84 I/I6 Печать офсетная Усл. печ.л. ,1,16. Уч.-изд.л. Г,¿п. Тираж 100 Зак. ¿518 / 5914 . Бесплатно

Типография издательства 'Ш I2587Ï, Москва, Волоколамское шоссе, 4