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

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

РГб им

• .1 . >

Алиева Юлия Владнмнровиа

Разработка методов и инструментальных средств прогнозирования качественных характеристик мультикомпыотерных систем

Специальность 05.13.13

Вычислительные машины, комплексы, системы и сети

АВТОРЕФЕРАТ

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

Москва - 2000

Работа выполнена в Московском энергетическом институте (Техническом университете), на кафедре Вычислительные машины, системы и сети

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

д.т.н., проф. Дзегеленок И.И.

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

д.т.н., проф. Саксонов Е.А. к.т.н., доц. Рудаков И.В.

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

Федеральное государственное

унитарное предприятие "НИИ "Квант""

Защита состоится "22_" июня 2000г. в 16.00 часов, в аудитории Г-306 на заседании диссертационного Совета К-053.16.09 в Московском энергетическом институте (Техническом Университете) по адресу: г.Москва, Красноказарменная ул., д.13.

С диссертацией можно ознакомиться в библиотеке МЭИ (ТУ)

Отзывы в двух экземплярах, заверенные печатью, просьба направлять по адресу: 111250, г.Москва. Красноказарменная ул., д.14, Ученый Совет МЭИ (ТУ).

Автореферат разослан " 43 " хюл 2000г.

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

к.т.н., доц. Дорошенко А.Н.

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

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

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

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

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

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

Цель и задачи диссертации

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

Для достижения этой цели в диссертационной работе решаются следующие задачи:

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

2. Исследование свойства инвариантности архитектуры МКС по отношению к типу задач с конвейерно-параллельной организацией вычислений.

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

4. Создание средств визуализации искомых знаний о правилах эффективной организации мультикомпыотерных систем и поддержки формирования экспертной оценки качества новых моделей МКС.

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

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

Научная новизна работы

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

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

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

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

Степень обоснованности научных положений

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

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

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

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

Реализация и внедрение

Разработанные методы реализованы в виде инструментального комплекса программных средств, работающего в среде \Утскт5'95/98/МТ.

С использованием разработанного комплекса выполнены поисковые исследования по организации проблемно-ориентированных МКС, предназначенных для отработки новых принципов управления электроэнергетическими системами (ГНЦ ВЭИ).

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

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

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

Публикации

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

Альтернативный подход - архитектура МРР (Mass Parallel Processing), проигрывая SMP в скорости, тем не менее является экономически более выгодной, т.к. привлекает минимум дополнительного оборудования и формируется в виде сети, состоящей из стандартных вычислительных средств.

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

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

Мультикомпьютерная система - это организация вида

МКС = {^з}, Ршм„ь, К.С1ГТЬ, И.„„„,,„,, РОС;, ( 1 )

где - набор вычислителей - рабочих станций или специализированных

ЭВМ;

Р-память - распределенная память (оперативная и внешняя память ХУз);

К-сеть_ коммутационная сеть для взаимодействия '\Уз, состоящая из каналов связи (КСв) и интерфейсных портов для подключения \У5 к КСв;

И.маШина - инструментальная машина, необходимая для подготовки прикладных программ и проблемной ориентации МКС в целом;

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

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

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

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

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

Начальными этапами при формировании модели получения и анализа знаний являются выделение и представление знаний о данной предметной области. Предметную область (поисковое пространство), далее обозначаемую D",

будем описывать набором параметров х/.....хп, где п - общее число параметров,

каждый из которых принимает несколько именных значений:

х,={а, 1,а,2.....а„...,а,к1}, где / - индекс параметра, / = I,«, j - порядковый номер

значения /-го параметра, к, - число значений i-го параметра. Объекты исследуемого поискового пространства представляются перечислением значений описывающих ее параметров в виде вектора x=(xi,x2,...,xn). Общее число

л

альтернатив, которые могут существовать в пространстве D", составляет N = kt .

Г-1

В соответствии с заданными Экспертом правилом качественной оценки МКС в виде многоместного от Х|,Х2,...ДП предиката Г1 тогда х е Т; [О, тогда х s F

множество объектов х пространства D" разделяется на подмножества удачных (Т) и неудачных (F) решений. Необходимо добавить, что один из наиболее распространенных способов задания предиката Р(х) состоит в определении условий перехода через известные барьеры или граничные значения по

каждому из внешних показателей качества /(x),...,/v.(x):

</Дх)-> шах, либо //''>/Дх)->. min, г = 1,5. (3)

Для получения искомого эмпирического знания, позволяющего "видеть" степень влияния каждого параметра х, с точностью до его конкретных значений на обобщенный показатель качества функционирования МКС в смысле Р(х)=1, производится обобщение данных об известных объектах хеТ, xeF с использованием методов индуктивного обобщения фактов. Искомое знание представляется как обобщенная скалярная функция выбора (ФВ), имеющая вид:

g (x)=s£v*,+ii>v-\-C„, (4)

где С0 - пороговое значение для функции выбора; хч - вспомогательная булевая переменная соответствующая аи - j-му именному значению параметра х„ такая,

А, _

что = 1 для / = In ; сI! - весовой коэффициент при соответствующем х,у, V -

количество нелинейных компонент (НК) данной ФВ; hv - весовой коэффициент при v-й НК, v = 1,1'; zr - v-я нелинейная компонента, представляет собой логическое произведение переменных хи. Введение нелинейных компонент позволяет частично или полностью исключить ошибки при определении принадлежности объекта х к одному из множеств Т или F в соответствии с условием:

#(х)> 0. если х е Т, Р(х)= 1. g(x)< 0, если х е F, Р(х) = 0. (5)

Рассматриваемый подход опирается на практически подтвержденное допущение о том, что большим значениям g(x) соответствуют лучшие решения х с точки зрения выполнения условия (3). Постановка и решение плохоформализуемых задач формирования эмпирических знаний в соответствии с (2),(4),(5) осуществляется на основе использования понятия Открытой задачи, которая определяется как конструкция вида

D",T[u}F[u]),P(x),g(x),R-»{x0};;, (6)

и направлена на восстановление эмпирического знания в виде зависимости g(x) вида (3), на основе индуктивного обобщения примеров: Т[и] - "удачных решений", F[u] - "неудачных решений", определяющих текущее знание, и применения правила Р(х) к результатам работы механизма R—>{х0} выдвижения гипотез х0, где и - порядковый номер сеанса приобретения эмпирических знаний.

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

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

Уточним последний тезис. Через ха обозначим упорядоченный набор параметров, определяющих тип решаемых задач, а через хь - организацию анализируемой МКС. В целом исследуемый объект х представляет собой композицию х=(ха,хь). Тогда сформированное эмпирическое знание g(x) вида (4) позволяет сделать, по меньшей мере, два основных типа заключений: I. Каким должно быть решение х* для известных значений х„ = const ? II. Каким будет решение х*, если известно хА = const ? Формально, вынесение заключений 1-го и 11-го типа сводится к нахождению условных экстремумов

к; = Arg max g(x)K , x] = Argmaxg(x) , ( 7 )

чеТ " NeT *

соответственно. Наиболее интересен с практической точки зрения случай, когда x=(xa,xb)gT[u] - для первоначально известного подмножества удачных решений при и=1, как для х", так и для xj. В этом случае можно говорить об ' экстраполяционном прогнозировании или "открытии": I. Не рассматриваемого изначально варианта организации МКС; II. Возможно не запланированного, но наиболее подходящего для заданной конфигурации МКС потока задач.

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

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

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

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

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

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

1. Параллельной мультикомпьютерной сети (ПС);

2. Конвейерно-параллельной мультикомпьютерной сети (КПС);

3. Конвейерной мультикомпьютерной сети (КС).

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

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

тактирование параллельных программ; 4) децентрализованное управление доступом к каналу передачи данных.

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

где P*sist - граничные значения соответствующих характеристик.

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

Для определения степени инвариантности МКС потоку решаемых задач (ц) используется геометрический подход, предложенный С. Ченом для оценки архитектур MIMD и MISD. В данной работе получены более общие аналитические выражения для конвейерно-параллельной организации МКС. Идея метода заключается в выделении частей последовательной и параллельной обработки при решении набора задач входного потока. Показатель ц определяется через соотношение площадей Snool и Snap, характеризующих части последовательной и параллельной обработки на соответствующих интервалах времени решения и

5 +5

площади "охвата" обоих частей (SOXB): // = --1—, 0<ц<1. Показатель р -степень параллельности задачи, определяется как отношение Srap к сумме

5

площадей SnoM и Snap: р = „ , 0<р<1.

"поел + пар

На рис. 1а) показана диаграмма процесса обработки заданий входного потока, где через обозначено число параллельно работающих вычислителей на j ярусе конвейерно-параллельной обработки за интервал времени Tj, где j = 1,М , М -номер яруса обработки. Для наглядности рис.1 построен для случая T,=const, М=4, L=6, где L - кратность выполнения задания.

а)

6)

©

(M»L-I)

О

гч\

п:\ t П4

П» Лд ' (I4 П4

У"

It,

(I

'I Tt ' I; 1 Т, ' Т, '

Я

Л п.

JF

П<

HotneftiMTclt.HaSHatTi. оор.ич1Гкн Uj|i,i i IU часть оГ-ра идлжй UNO.iiiom |ИГн.рв и.ииий *\оджт> набор»

Рис. 1 а,б Диаграмма процесса обработки заданий входного потока (а) и ее

преобразование (б).

В результате конкретизации выражений для Snool, Snap и SOXB обобщенного случая, получены следующие аналитические выражения:

М-г, п,

. ______________л. _ Т _

( \

для

1 +

р=1-

(8)

М-г,

• (n —)

м

¿"Iv,

L-I^-n,

а также определены условия применимости выражения (8) для М1МО, М15Б и конвейерно-параллельных структур. Исследования ц показали, что данный показатель чувствителен к изменению характеристик оборудования МКС и параметров решаемых задач, что позволяет использовать его как один из показателей качества мультикомпьютерных систем. При анализе ц было выявлено, что по мере увеличения кратности решения задачи (при прочих равных условиях) степень инвариантности МКС возрастает, а при увеличении числа параллельных ветвей задачи - уменьшается. Чем больше кратность решения задачи по отношению к числу ее ярусов, тем выше значение показателя ц.

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

/«1

j

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

Утверждение. Если для искомой функции выбора g(x), параметр х, принимает к; именных значений, / = 1, п, и каждому j-му именному значению щ ставится в соответствие вспомогательная переменная {0,1}, j=\,k,, то для существования локальных экстремумов х* необходимо и достаточно выполнения следующих условий:

а) с'-,тах/*(х> , б) с = min'SgM , (9)

• / а, ■ / ах„ ^

где / = 1,л, с*,у - вес при вспомогательной переменной х'ц вектора х*, для локальных а) максимумов, б) минимумов соответственно.

Идея разработанного алгоритма заключается в следующем. Для заданной функции выбора формируется, в общем случае, набор векторов нижней оценки / = 1,Р, где Р - число векторов нижней оценки, для

значений x'tl которого выполняются условия = maxfc^), = , i = \уп,

j = \,k, ■ Для каждого i-го параметра существует хотя бы по одному значению Jy=const. Далее, проводится последовательный анализ всех составляющих х'/: можно ли для данного i изменить j-e значение на j -е, так чтобы имело место с; < с .. Если такое возможно, то х/*=^[й,дг2; ) - локальный максимум,

иначе X/' - локальный максимум. В заключении необходимо провести проверку найденных локальных максимумов: Wk > max(ff,), Wk - вес к-то локального

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

Разработанный алгоритм прежде всего составляет основу формирования нелинейного эмпирического знания g(x) и служит для нахождения условных экстремумов при вынесении экспертных заключений I и II типа в смысле (7). Применительно к исследуемым в работе МКС, локальные максимумы можно толковать как наиболее устойчивые структуры, с точки зрения обеспечения необходимого качества, как по отношению к изменениям значений параметров оборудования, так и относительно возможных изменений значений характеристик решаемых задач.

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

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

(дг, принимает значе( (д:2 принимает знача

(Х| не принимает значение ац) или (хг не принимает значение ац)?

Рис. 2 Пример дерева экспертных оценок.

Корневому узлу дерева - приписывается исходный набор объектов. Узел дерева считается листом, если у него нет исходящих ребер и приписанные ему объекты принадлежат только одному из множеств - либо Т, либо Р. Знаком "+" на рис.2 обозначены листья, при сопоставлении с которыми объект оценивается положительно (для такого объекта §(х)>0), знаком "-" - листья, где объект оценивается отрицательно (§(х)<0), в соответствии с (5). Узел дерева является внутренним, он связан с тестовым вопросом. Левому ребру, выходящему из внутреннего узла соответствует положительный, правому ребру - отрицательный ответ на соответствующий тестовый вопрос.

Существуют разные виды тестовых вопросов. Наиболее распространенные -это однозначные и многозначные вопросы.

Тестовые вопросы первого вида предлагается образовывать путем выбора каждого /-го параметра и последовательного перебора всех его у'-х именных значений а,, в соответствии с их важностью по значению с,г При конструировании многозначных тестовых вопросов для каждого внутреннего узла предлагается анализировать набор приписанных ему фактов. Цель - определить значения параметров, встречающиеся у фактов только одного множества - или Т или Б. Из всех найденных значений формируется многозначный тестовый вопрос.

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

Размеры дерева экспертных оценок с многозначными тестовыми вопросами зависят от размерности используемого пространства параметров О". Общее число

узлов бинарного дерева = - п +1, а число его ярусов: Ыу<п. Максимальное

число узлов дерева, содержащих вопросы второго вида, которые необходимо задать для определения качества исследуемого объекта - ы™ч = Ы,-1, минимальное - N""=1. Для небольшой размерности (п=2+4) поискового пространства вид тестовых вопросов может быть любым.

Надо заметить, что чем выше достоверность ФВ §(х) поискового пространства О", тем меньшее количество элементарных вопросов входит в

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

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

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

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

Экспертная система "Решатель открытых задач" позволяет: - проводить настройку на различные наборы параметров МКС (определенные Экспертом для решения поставленной задачи); - формировать эмпирические знания в виде скалярной функции выбора; - определять лучшие решения (варианты построения МКС) и производить оценку новых конфигураций.

Функционирование РОЗ, объединенного в единый комплекс с РИМ обеспечивает усиление экспертных возможностей в части пополнения и анализа знаний. На рис.3 представлена блок-схема организации их взаимодействия. Пунктирными линиями выделены блоки, в которых выполняются: настройка РИМ и РОЗ (блок I), собственно имитационное моделирование (блок II), обучение РОЗ (блок III), анализ и экспертная оценка объектов - различных конфигураций МКС, ориентированных на выполнение заданного класса задач (блок IV).

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

- передача настроечных параметров; -» - направление действия логических связей по управлению; х - описание объекта (конкретной структуры ПМК-сети и решаемых задач); R(x) - значения ВПК, полученные при имитационном моделировании х; g(x) - искомое эмпирическое знание в виде функции выбора (ФВ); Г, F - множества удачных (Т) и неудачных фактов (F) - структур ПМК-сети;

Dn - пространство внутренних параметров РОЗ для описания объектов; Р(х) - правило качественной оценки вариантов х;

х0 - эмпирическая гипотеза, требующая проверки с помощью правила Р(х0); S=(xa,xb) - описание конфигурации (структуры) ПМК-сети и набора решаемых

задач в соответствии с (7); х - найденное удачное сочетание значений параметров среди известных описаний объекта.

Рис. 3 Блок-схема взаимодействия РИМ и Решателя Открытых задач

В блоке I с участием Эксперта происходит начальная настройка РОЗ через задание пространства внутренних параметров D" и определение состава внешних показателей качества посредством блока целеполагания. В блоке III происходит формирование искомого знания в виде функции выбора g(x). В процессе формирования g(x) происходит взаимодействие с РИМ для получения значений показателей качества полученных эмпирических гипотез {хо}. По значениям параметров гипотез Хо в блоке I происходит задание параметров ПМК-сети и решаемых задач. Сформированное описание конфигурации ПМК-сети и решаемых задач (S) передается в блок II. В этом блоке описание S преобразуется во внутреннее представление моделей задачи и структуры ПМК-сети для выполнения имитационного моделирования. В процессе имитационного моделирования из базы алгоритмов функционирования ПМК-сети выбираются заданные в описании гипотез. По окончании процесса моделирования результаты в виде набора ВПК передаются в блоки I и IV для дальнейшей работы. Далее, в блоке III происходит анализ полученных результатов моделирования ПМК-сети, описываемых гипотезами х0 и пополнение базы фактов. Исходными данными для блока IV

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

Графическое представление результатов моделирования позволяет увидеть и оценить динамику изменения поведения исследуемых МКС при изменении внешних воздействий и/или элементов оборудования.

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

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

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

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

Второй пример применения разработанных инструментальных средств -определение диапазона допустимых значений характеристик оборудования специализированной МКС для управления летательными аппаратами (ЛА).

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

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

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

Установлено, что конвейерно-параллельная организация ПМК-сети управления рулем высоты ЛА наиболее эффективна с точки зрения минимизации времени расчета задачи. По сравнению с чисто параллельной организацией вычислений в ПМК-сети выигрыш во времени при использовании КПС при прочих равных условиях составляет от 30% в зависимости от используемой структуры алгоритма решения задачи.

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

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

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

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

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

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

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

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

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

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

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

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

1. Дзегеленок И.И., Барабанова Ю.В. Анализ "пластичности" мультиконвейерных вычислений // Межд. форум по информатизации МФИ-97. Информационные средства и технологии в науке, технике, обучении: Тез.докл.

- Моск.энерг.ин-т. - 1997- С.98-103.

2. Лабораторные работы по курсу "Поисковое проектирование вычислительных систем". И.И. Дзегеленок, Ю.В. Барабанова. - М.: Изд-во МЭИ, 1997. - 37с.

3. Барабанова Ю.В. Способ формирования деревьев экспертных заключений // Межд. форум по информатизации МФИ-99. Информационные средства и технологии в науке, технике, обучении: Тез.докл. - Моск.энерг.ин-т. - 1999 -С.89-92.

4. Барабанова Ю.В. Формирование деревьев экспертных заключений // II Международная научно-практическая конференция - "Сочи-99". Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права: Тез.докл. - МГАПИ. - 1999 - С.42 - 45.

5. Барабанова Ю.В., Дзегеленок И.И., Корлякова М.О. Определение параметров параллельной мультикомпьютерной сети //Вопросы радиоэлектроники. - 1999

- Сер. ЭВТ,- Вып. 1. - С.29-34.

Печ. л. _Тираж ¡00 Зака

Типография МЭИ, Красноказарменная, 13.

ВВЕДЕНИЕ.

1. Проблема прогнозирования качественных характеристик мультикомпьютерных систем (МКС).

1.1 Выделение новых тенденций развития мультикомпьютерных систем

1.2 Описание средств решения проблемы дефицита знаний.

1.3 Анализ открытых задач формирования эмпирического знания с использованием Решателя открытых задач.

1.4 Исследование нерешенных задач качественного прогнозирования МКС

1.5 Выводы по главе

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

2.1 Уточнение условий моделирования МКС в классе ПМК-сетей.

2.1.1 Представление класса решаемых задач.

2.1.2 Определение исходных характеристик ПМК-сети.

2.1.3 Основные особенности ^ётроеййя:.имитационной модели функционирования ПМК-е^ти,.,.!'

2.1.4 Выбор показателей качества функционирования ПМК-сети.

2.2 Разработка теоретической модели оценки инвариантности МКС потоку решаемых задач.

2.3 Разработка алгоритма поиска локальных экстремумов.

2.4 Представление эмпирических знаний в виде дерева экспертных оценок

2.5 Выводы по главе 2.

3. Инструментальная система прогнозирования качественных характеристик мультикомпьютерных систем.

3.1 Разработка расширенной имитационной модели (РИМ) работы ПМК

3.1.1. Общие принципы работы РИМ.

3.1.2. Представление типов решаемых задач.

3.1.3. Отображение структурных особенностей ПМК-сети.

3.1.4. Моделирование работы ПМК-сети.

3.2 Обработка и отображение результатов имитационного моделирования

3.3 Автоматизация взаимодействия РИМ с Решателем Открытых задач.

3.3.1 Настройка Решателя открытых задач.

3.3.2 Обучение Решателя открытых задач.

-33.3.3 Экспертная оценка и прогнозирование.

3.4 Выводы по главе 3.

4. Применение разработанных методов и инструментальных средств.

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

4.2 Определение конфигурации проблемно-ориентированной МКС для управления летательными аппаратами.

4.3 Выводы по главе 4.

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

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

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

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

Цели и задачи работы

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

Для достижения этой цели в диссертационной работе решаются следующие задачи:

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

2. Исследование свойства инвариантности архитектуры МКС по отношению к типу задач с конвейерно-параллельной организацией вычислений.

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

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

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

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

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

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

Научная новизна

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

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

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

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

Результаты исследований, составляющих содержание работы, были доложены и обсуждены на международных конференциях "Информационные средства и технологии", проводившихся Международной академией информатизации в 1996 и 1999г.г., и на ученом совете Республиканского исследовательского научно-консультационного центра экспертизы (РИНКЦЭ), а также отражены в отчетах кафедры о НИР кафедры ВМСС МЭИ за 1994-1998 г.

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

Поставлены и в течение 3-х лет проводятся у студентов 5-го курса специальности 22.01 лабораторные работы по курсу "Поисковое проектирование вычислительных систем": "Поисковое проектирование рабочей станции" и "Моделирование работы параллельной мультикомпьютерной сети".

Публикации

По теме диссертации опубликовано 5 работ. Результаты работы докладывались на конференциях МФИ-97, МФИ-99, "Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права"-"Сочи-99", доклады опубликованы в [5,68,69].

Основные результаты и положения работы отражены в 3-х отчетах по НИР [1,2,3,4].

Состав работы

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

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

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

Выделяются нерешенные задачи качественного прогнозирования МКС и определяется подход к их решению.

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

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

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

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

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

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

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

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

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

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

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

5. Разработана и программно реализована имитационная модель функционирования МКС на примере ПМК-сети, обеспечивающая моделирование

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

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

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

ЗАКЛЮЧЕНИЕ

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

1. Ю.В. Барабанова Подход к построению расширенной имитационной модели ПМК-сети. // Интеграция средств параллельных распределенных вычислений и сетевых технологий. Отчет о НИР. № гос. per. 01960011005. 1997, 60с.

2. Представление качественных оценок эффективности ПМК-сети в виде дерева экспертных оценок. //Отчет/МЭИ; Руководитель работы И.И. Ладыгин. № гос. per. 01910011005, М.: 1998, - 97с.

3. Дзегеленок И.И., Барабанова Ю.В. Анализ "пластичности" мультиконвейерных вычислений // Информационные средства и технологии в науке, технике, обучении: Тез.докл. Межд.форума по информатизации МФИ-97 // Моск.энерг.ин-т.-1997. С.98-103.

4. Лабораторные работы по курсу "Поисковое проектирование вычислительных систем". И.И. Дзегеленок, Ю.В. Барабанова. М.: Изд-во МЭИ, 1997. - 37с.

5. Д. Арапов Можно ли превратить сеть в суперкомпьютер? //Открытые системы №4 1997г.

6. Параллельная обработка информации, т.З A.B. Бабичев, В.А. Вальковский. /Под ред. Свенсена А.И., М.: 1988г. - с

7. Э.В. Евреинов "Коллектив вычислителей"

8. Дзегеленок И.И. Поисковое проектирование мультикомпьютерных систем с использованием индуктивных обобщений. Автореферат дис. На соискание уч. ст. д.т.н. М.; МЭИ, 1996г. - 40с.

9. Дзегеленок И.И. Подход к созданию параллельных компьютерных сетей // Высокопроизводительные вычислительные системы в управлении и научных исследованиях: Тез. докл. Межд. конф., Алма-Ата, 1991. С. 25.

10. Разработка параллельной программы. Методические указания к расчетному заданию по курсу "Основы теории вычислительных систем". М.: Изд-во МЭИ, 1994.-23с.

11. Tanenbaum A.S. etal AMOEBA high performance distributed Computing. Amsterdam. 1989

12. Родина H.B. Организация параллельных вычислений в распределенных управляющих системах. Автореферат дис. на соискание уч. ст. к.т.н. М.; МЭИ, 1991г.-20с.

13. Климов Ю.Н.Кондрат А.В. Архитектура параллельной сети "КУРС-90" 15 Всесоюзная школа-семинар по вычислительным сетям: Тезисы докладов, Ленинград, -1990, ч.1, с. 19-2416. http://parallel.srcc.msu.su/inrussia/organizations.html

14. Башлыков А.А., Еремеев А.П. Экспертные системы поддержки принятия решений в энергетике /Под ред. А.Ф. Дьякова. Изд-во МЭИ, 1994. - 216с., ил.

15. Simon H.A. The new science of management décision. Englewood Cliffs, N.J., Prentice Hall Inc., 1975.

16. Э.А.Трахтенгерц Компьютерная поддержка принятия решений в САПР. //Автоматизация проектирования №5 1997г.

17. Ларичев О.И. Объективные модели и субъективные решения. М., Наука. 1987

18. Построение экспертных систем. -М.: Мир, 1987. 441с.

19. Системы управления базами данных и знаний: Справ, изд. / А.Н. Наумов, А.М. Вендеров, В.К. Иванов и др.; Под ред. А.Н. Наумова. -М.: Финансы и статистика, 1991г.-352с. :ил.

20. Дзегеленок И.И. Логика поиска проектных решений // Учебное пособие по курсу "Теоретические основы машинного проектирования." М.: Моск. энерг. ин-т, 1984, 64 с.

21. Хьюит К. Открытые системы. Реальности и прогнозы искусственного интеллекта / Под ред. В.Л. Стефанюка М.: Мир, 1987

22. Дзегеленок И.И. Открытые задачи поискового проектирования // Учебное пособие по курсу "Основы инженерного творчества." М.: Моск. энерг. ин-т, 1991,66 с.

23. Головкин Б.А. Параллельные вычислительные системы М.: Наука,. 1980. -512с.

24. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов -М.: Радио и Связь, 1983

25. Евреинов Э.В. Однородные вычислительные системы, структуры и среды М.: Радио и связь. - 1981

26. Дзегеленок И.И. Мультиконвейерные вычислительные системы на базе микроЭВМ. // Учебное пособие по курсу "Микропроцессоры в системах управления"М.: Моск. энерг. ин-т, 1985. 60 с.

27. Разработка математических моделей и анализ эффективности вычислительных систем. В.П. Климанов/Под ред. Ю.П. Кораблина. М.: Изд-во МЭИ, 1992. -130с.

28. Том Стерне Учимся моделировать //Открытые системы №5 1998г., с.130-135.

29. Мирослав Макстеник Сравнение сетевых архитектур //Сети №2 1997, с. 14-28

30. Бершадский A.M., Кревский И.Г., Курилов JI.C., "Объектно-ориентированная распределенная вычислительная среда функционирования параллельного алгоритма решения задач автоматизации проектирования"

31. Феррари Д. Оценка производительности вычислительных систем. Пер. с англ. Под ред. В.В. Мартынюка. М.: Мир, - 1981

32. Юдин A.A. Юдин Д.В. Пополнение и синтез знаний в задачах теории принятия решений. //Техническая кибернетика №5 1992г.

33. Дзегеленок И.И., Мильман М.О. Экспертная поддержка "усилителей интеллекта": Тез.докл. XI конф. "Информационные средства и технологии". Моск.энерг.ин-т.-1994. С.34-35.

34. Корлякова М.О. Разработка методов и средств приобретения эмпирических знаний в поисковом проектировании вычислительных систем. Автореферат на соискание уч. ст. к.т.н. М.:МЭИ, 1998г. - 20с.

35. Сессия конференций РаСТ http://www.ssd.sscc.ru/pscts

36. Фундаментальные и прикладные аспекты разработки больших распределенных программных комплексов. Всероссийская научная конференция. http://www.parallel.srcc.msu.su

37. Основы построения вычислительных систем. И.И.Ладыгин, Н.Н.Белоцицкий/Под ред. А.А.Дерюгина.- М.: Изд-во МЭИ, 1992,- 52 с.

38. Карцев М.А., Брик В.А. Вычислительные системы и синхронная арифметика.-М.: Радио и связь, 1981.- 60 с.

39. Валях Е. Последовательно-параллельные вычисления. Пер.с англ.- М.: Мир, 1985.-456 с, ил.

40. Миренков H.H. Параллельное программирование для многомодульных вычислительных систем,- М.: Радио и связь, 1989.- 320 е.,ил.

41. Каган Б.Н. Электронные вычислительные машины и системы. Учебное пособие для вузов.- 3-е изд., перераб. и доп.- М.: Энергоатомиздат, 1991.- 92 е.: ил.

42. Вейцман Кэй Распределенные системы мини- и микро-ЭВМ / Пер. с англ. В.И. Шяудкулиса и В.А. Шапошникова; Под ред. Г.П. Васильева. М.: Финансы и статистика. 1983. 382с.; ил.

43. Д. Французов Оценка производительности вычислительных систем //Открытые системы № 2 1996 с. 58-66

44. Д. Волков Как оценить рабочую станцию //Открытые системы №2 199451. http://www/citforum.ru/hardware/appkis/glava42.shtml

45. Б. Нанс Компьютерные сети. Пер. с англ. М.: Бином, 1996. - 400с.:ил.

46. Блэк. Ю. Протоколы, стандарты, интерфейсы: Пер. с англ. -М.:Мир, 1990. -506с., ил.

47. Макроум Б. Макетирование моделированием. PC Magazine. Russian edition. # 9, 1996, с. 120.

48. Оценка качества информационных систем и процессов. Сб. статей 1981

49. Структуры и организация функционирования ЭВМ и систем. Самофалов К.Г., Луцкий Г.М. Киев, "Вища школа", 1978, 392с.

50. Прангишвили И.В., Подлазов B.C., Стецюра Г.Г. Локальные микропроцессорные вычислительные сети. -М.: Наука, 1994. -176с.

51. Chen Т.С. Parallelism, pipelining and computer efficiency. "Computer design", vol. 10, N1, 1971

52. Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1, 81-106.

53. ALLAN P. WHITE, LIU, WEI ZHONG, Quinlan, J. R. Bias in Information-Based Measures in Decision Tree Induction Machine Learning, 15/ 3, 321-329 (1994)

54. Цветков A.M. Разработка алгоритмов индуктивного вывода с использованием деревьев решений //Кибернетика и системный анализ 1993, №1, с. 174-178

55. Дзегеленок И.И. Решатель открытых задач как инструмент инженерного проектирования // Процедуры и методы инженерного проектирования: Сб. трудов / Моск. энерг. ин-т: АСТЕРРА. М., 1992. - С. 71-80.63. http:// www.spec.org64. http:// www.lva.ru/ LAN

56. М. Киселев, Е. Соломатин Средства добычи знаний в бизнесе и финансах //Открытые системы №4 1997

57. Барабанова Ю.В. Способ формирования деревьев экспертных заключений //Информационные средства и технологии в науке, технике, обучении: Тез.докл. Межд.форума по информатизации МФИ-99.

58. Барабанова Ю.В. Способ формирования деревьев экспертных заключений //Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права: Тез.докл. II Международной научно-практической конференции "Сочи-99".

59. Барабанова Ю.В., Дзегеленок И.И., Корлякова М.О. Определение параметров параллельной мультикомпьютерной сети //Вопросы радиоэлектроники. Сер. ЭВТ. ОАО НИИ ВК им. М.А. Карцева, вып. 1, 1999.

60. На вход ПМК-сети поступают задачи разных типов. Число вычислителей, тазначенных на обработку сегментов вычислений каждого из ярусов решения задач не юегда совпадает с числом сегментов у задач входного потока.

61. Пусть задача представлена следующим графом рис. 1