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

и ( 1 I ! о

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

На правах рукописи УДК 681.324

ПОЛЕНОВ Максим Юрьевич

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

Специальности: 05.13.13 - Вычислительные машины, комплексы,

системы и сети 05.13Л6 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

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

Таганрог - 1995

Работа выполнена на кафедре вычислительной техники Таганрогского государственного радиотехнического университета

НАУЧНЫЙ РУКОВОДИТЕЛЬ: доктор технических наук, профессор

ЗОЛОТОВСКИЙ В.Е. ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ: доктор технических наук, профессор

НИКОЛАЕВ И А. " . доктор технических наук

МАРГЕЛОВ А.В. .

ВЕДУЩЕЕ ПРЕДПРИЯТИЕ: Научпо-производственное объединение

"Марс", г.Ульяновск /

Защита' состоится " у? " ( ¿¿¿ГУзЛ 1996г. в 14 часов на заседании диссертационного совета Д 063.13.02* по защите диссертаций при Таганрогском государственном радиотехническом университете по адресу: 347915, г.Таганрог, пер.Некрасовский 44, ауд. Д-406.

С диссертацией можно ознакомиться в библиотеке университета. • Автореферат разослан !J¡&¿¿tx¿¡fц 1995г.

Учёный секретарь диссертщионного совета -канд. техн. наук, доцент

А.Н.Цёлых

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

АКТУАЛЬНОСТЬ ТЕМЫ. В настоящее время интенсивно ведутся работы по исследованию и разработке вычислительных систем (ВС), предназначенных для управления объектами, оборудованием и технологическими процессами. Данные ВС должны функционировать в особых условиях, обладать высокой надежностью, обеспечивать своевременную реакцию- на связанные с управляемым объектом действия и решать заранее определенный набор прикладных задач, что позволяет отнести их к классу проблемно-ориентированных вычислительных систем (ПОВС), работающих в реальном масштабе времени (РМВ). В последнее время наметилась тенденция создания ПОВС в виде многопроцессорных ВС, что позволяет значительно увеличить их производительность путем распараллеливания процесса вычислений, повысить надежность системы, а также обеспечить легкость реконфигурации вычислительных ресурсов и модификациирешаемых задач.

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

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

ЦЕЛЬ И ЗАДАЧИ РАБОТЫ. Целью диссертационной работы является исследование и разработка методов и средств, позволяющих учесть особенности организации и сократить сроки проектирования высокопроизводительных _ПОВС, работающих в РМВ. Для достижения поставленной цели решаются следующие задачи:

- анализ особенностей организации и функционирования многопроцессорных ПОВС, как объекта исследования;

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

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

■ - создание Окомплекса средств описания, моделирования и проектирования, основанного на предложенных методах и подходах к разработке и оптимизации ПОВС.

МЕТОДЫ ИССЛЕДОВАНИЯ. Для решения поставленных задач .используются методы теории вычислительных систем, теории графов, теории множеств, распараллеливания алгоритмов и имитационного моделирования.

ОСНОВНЫЕ ПОЛОЖЕНИЯ ВЫНОСИМЫЕ НА ЗАЩИТУ. На защиту выносятся следующие положения и результаты:

алгоритмо-ориентированный подход к исследованию ПОВС, объединенный с методикой нисходящего проектирования систем;

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

- методы определения оптимального числа параллельных ::ствей и распараллеливания ациклических графов алгоритмов;

способ. иерархического многокомпонентного представления и моделирования ПОВС.

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

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

- определены этапы, алгоритмо-ориентированного подхода и предложен механизм двухуровневой оптимизации при Создании ПОВС;

- разработан способ параметрического представления "алгоритмов прикладных задач в виде графа зависимостей; ■ . ■

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

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

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ РАБОТЫ представляют:

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

высокоуровневый язык описания и моделирования систем, позволяющий произвести. определение как аппаратной, так и программной компонент ПОВС; ■ ,

- программная среда для исследования, моделирования и построения высокопроизводительных ГГОВС.

ИСПОЛЬЗОВАНИЕ РЕЗУЛЬТАТОВ РАБОТЫ. Теоретические и практические результаты диссертационной работы использовалась при выполнении госбюджетных и хоздоговорных работ кафедры "Вычислительной техники" Таганрогского государственного радиотехнического университета: "Исследование и разработка программируемого преобразователя сигналов" ( № ГР 01.90.0007251), "Разработка прохраммного эмулятора аппаратной части МВК 'Траверс", "Разработка эмулятора базового модуля наращивания "супер-ЭВМ " ( N° ГР 01.9 50003771 ), выполненных для НИИ многопроцессорных вычислительных систем; "Разработка _ микро ЭВМ перспективного персонального компьютера", "Разработка МВС на базе микропроцессора ¡386",выполненных для, НПО "Марс" г.Ульяновск; госбюджетной НИР "Разработка, принципов построения и Создание многопроцессорных вычислительных систем с матрично-потоковой архитектурой и системой закрытия данных в каналах связи" (№ ГР 01.9.40002376).

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

. АПРОБАЦИЯ РАБОТЫ. Основ1шё результаты работы Докладывались и обсуждались / на научно-технических конференциях (НТК): межреспубликанской НТК "Актуальные проблемы фундаментальных наук" (г.Москва,1989г.); VIII всесоюзной НТК " Перспективы развития и применения средств вычислительной техники для моделирования и автоматизированного исследования " ( г.Москва,1991г.); областной НТК, посвященной Дню радио (г. Ростов-на-Дону, 1992г); XLVIII научной сессии, посвягценной Дню радио (г.Москва,1993г.); северо-кавказской региональной НТК "Методы и средства ЦОС" (^Таганрог, 1993г.); VI всероссийской НТК "Однородные вычислительные системы,, структуры и среды" (г.Москва, 1993г.); международной НТК "Диагностика, информатика и метрология -94" (г. С. Петербург, i 994г.); НТК профессорско-преподавательского состава, аспирантов и сотрудников ТРТУ (г.Таганрог, 1990 - 1994 г.г.).

ПУБЛИКАЦИИ. По результатам диссертационной рабогы опубликовано 14 печатных работ. Кроме того, значительная часть практических результатов изложена в отчетах о выполнении НИР.

•V 6

СТРУКТУРА И ОБЪЕМ РАБОТЫ. •Диссертационная работа состоит из введения, четырех разделов и заключения, изложенных на .141 странице, содержит 18 рисунков, 115 ьаимекований библиографии и 54 страницы приложения, всего 207 страниц.

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

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

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

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

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

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

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

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

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

Во втором разделе рассматриваются основные Этапы предложенного алгоритмо-ориентированного подхода к разработке и оптимизации ПОВС.

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

Для заданной задачи 2 в общем случае существует множество А алгоритмов ее решения: 2 А = {а,},/ = при этом каждому алгоритму соответствует подмножество архитектур а1 В( = = ТЖи - М,. Тогда

N м1

возможное число архитектур: = £ £ Ьд .

/-1/М

Для сокращения временных затрат на разработку ПОВС и числа исследуемых архитектур предлагается произвести двухуровневую оптимизацию

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

На первом этапе производится описание представляемого алгоритма при помощи средств формализации и переход к графу зависимостей

Ф^.я,--» (?„=< К,/> где V- множество вершин; .Г- множество дуг.

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

Следующим этапом является распараллеливание полученного графа зависимостей и получение набора подграфов параллельной реализации:

Ср = {¿рпЬ" = ¡Л

Поскольку разрабатываемая ПОВС имеет иерархическую организацию, то

■ у-- , ■

выделяются три уровня Параллелизма: крупноблочный; циклических и ациклических участков; крупных операций и выражений. Для перехода с уровня на уровень, и получения субоптимального алгоритма выбирается критерий оценки по двум параметрам: времени вычислений по алгоритму Та и сложности алгоритма .У0. Данные параметры рассматриваются в предположении соответствия архитектуры алгоритму, т.е. вершинам графа из множества V соответствуют определенные типы функциональных узлов или блоков из множества II:

«РЗ-.Г О- = =

ч

где Рц - число типов узлов. Каждый узел иг е ¿/ имеет собственное время лполнения и сложность Тогда для параллельного алгоритма время ;ализаций:

Та* ~

1ВД + ттах(Г,')лг; (=1 у.

где: Г*- время выполнения ¡-го последовательного участка; Л"/ -число рохождений 1-го последовательного участка; ГД- время выполнения к-ой етви j-гo параллельного участка; И? - число прохождений .¡-го параллельного частка; Ь5 и Ьр - число последовательных и параллельных участков. Сложность алгоритма:

Sa=Ylfímзx(dirk)Sr!L^LsVLp г=и-1/б£

где: ЛЬ- число узлов г-го типа для /-го оператора к-й ветви; К - число

араллельных ветвей.

Тахим образом, можно сформулировать задачу построения опгим&чьного

¡араллелыгого алгоритма по критериям быстродействия и сложности, т е.

[¿обходима найти алгоритм с минимальной сложностью при заданных

'граничениях на время выполнения: гшп(50|70 ^ Г™),где: Г™- время решения

веЛ '

адачи, связанное с ограничениями на быстродействие. С учетом осмотренных соотношений:

гпш

о

ЕЕ

1*1

Еад + Е^Гто; /»1 «*=».* ^

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

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

критериями метода являются: время исполнения параллельного участка сложность исполнения. На основе анализа определенных на этапе отображеня зависимостей и непосредственно предшествующих вершин, производите распределение вершин графа алгоритма по ветвям, согласно выбранны критериям. Помимо минимизации времени и сложности исполнения алгоритм данный метод позволяет: получить сбалансированные по длине ветв] заполнить образуюифеся в ветвях участки простоя; определить необходимы набор операций для каждой ветви и распределять вершины не имекищ ограничений на число источников данных. Универсальность метода так* заключается в том, что он может быть использован и на следующем уровне распараллеливании операторов , и выражений, если не удается наЙ1 оптимальное решение на уровне ациклических участков. Тогда, производите разложение каждой вершины графа на ряд вершин второго уровня, каждая 1 которых отображает отдельную операцию и к полученному 1рафу применяет« рассмотренный метод.

При. получении 1рафа Ор осуществляется переход к этапу огображеш алгоритма на архитектуру:

¿Рфб, в = = щ:.

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

Ъ) =< 0,С,1У,Н > .

где О - множество выполняемых операций; С - матрица соединени задающая связность процессоров одного уровня; IV - матрица объем* требуемой памяти; Л - матрица назначений участков параллельного 1рафа 1 исполнительные модули ПОВС.

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

От описания архитектуры осуществляется переход к формированию модели:

где Е - подсистема отображения аппаратных средств; 0 - подсисте! отображения программного обеспечения. Данный этап состоит из следующ основных шагов: формализованное описание архитектуры; профаммирован на языке описания и моделирования систем; моделирование работы ПОВ

и

нализ результатов экспериментов и выбор (ытиматьиой архитектуры. В ачестве критерия также используется критерий быстродействия и сложности: ^о»). но оценивается быстродействие аппаратуры и сложное п

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

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

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

1) уровень системной ¡'рхитектуры, отображающий взаимосвязь базовых локов систем^. взаимодействие узловых процессоров (У 14), блоков памяти и .оммугаторов, и соответствующий уровень крупных программных модулей;

2) уровень архитектуры узлового процессора, определяющий структуру вязей между процессорными элементами (ПЭ), входящими в УП, н и* заимодействие и уровень параллглыю-иоследовательных промпммнь'х юдулей, получаемых на следующем этапе для процессорных элементов;

3) уровень архитектуры ПЭ, фиксирующий набор и взаимосвязь )ункциональных блоков (ФБ) процессорного элемента и уровень программ на шкроаесемблере, получаемых на этапе распараллеливания крупных операторов [ выражений и реализуемых на ФБ:

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

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

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

Формирование.^ программной компоненты п изводится на основ« программных модулей соответствующего уровня представления, полученных ш этапе распараллеливания алгоритмов и назначенных на конкретный блок н< этапе отображения. Реализация программных модулей осуществляется npi помощи, процессов функциональной модели. Таким образом, появляето возможность построения системной модели, позволяющей произвести кш • анализ и выбор архитектуры ПОВС, так и адаптацию, и отладку программной обеспечения.

Поскольку существующие языки моделирования ориентированы нг описание аппаратных средств ВС и конкретную формальную схему, то дщ реализации многоуровневого и многомодельного подхода} характеризующегося четырехкомпонентным определением модели системы, предлагается высокоуровневый язык описания и Моделирования систем (ЯОМС). Ochobhoî единицей описанья для данного языка является модуль, который представляе] собой часть проекта выбранного уровня иерархии. Каждый! модуль может имел в своем составе четыре раздела описания, соответствующие рассмотренньин моделям-компонентам: Interface - определение интерфейса модуля; Connection! -•структурное описание межсоединений в модуле; Descriptions - описание функщюнированкя и взаимодействия блоков. внутри модуля; Program -описание программной компоненты модуля.

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

В состав среды входят подсистема анализа программного обеспечения v подсистема описания и моделирования. Результатом работы первой подсистемк явдяется параметрическое описание архитектуры ПОВС и параллельные графк дnsf рыбращюго уровня представления. В подсистему описания v моделирования входят: компилятор с ЯОМС; блок компоновки и генерации моделе^; блоки моделирования, организации эксперимента и отображение pe^ibT^çï} а также нвбор библиотек удаленных опвсамхй, модулей и тестовые водайствю!. Ядром подсистемы является управляющая программ;

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

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

Произведенный анализ алгоритма решения задачи позволил при едстаплении в виде графя зависимостей, сократить число вершин верхнего осня на 10% и выделить крупные блоки алгоритма, отображенные средством проекции на матрицу узловых процессоров. В результате . п а ралл е л и яа н ия крупных 5 л о ко в был получен набор параллельных- ветвей, >актеризующихся уменьшением на 15%'числа обменных операций между гяями и сокращением времени простоя в ветвях, что позволило сократить на % аппаратные затраты при отображении на архитектуру узлового процессора. >сле этапа моделирования был выбран УП состоящи1 :з трех процессорных гментов, объединенных по полному графу. С учетом возможности спараллелнвачия крупных операторов и выражений, была выбрана структура

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

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

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

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

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

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

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

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

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

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

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

•\5. Для реализации предложенного способа представления моделирования ДОВС создан высокоуровневый язык описания моделирования систем, поддерживающий нисходящее проектирование ■ иерархию уровней описания. Преимуществами языка являются возможное компактного, описания организации и поведения системы как на высок« . уровне абстракции представления архитектуры, так . и и-, уровне логическ элементов, а также описание программной компоненты в виде фрагмент графов, полученных на определеннгм уровне при распараллеливании.

6. Разработана и создана инструментальная программная среда д исследования и проектирования высокопроизводительных ПОВ Особенностью данной среды является предоставляемая разработки возможность анализа и детальной проработки как аппаратной, так программной компонент ПОВС на каждом из уровней иерарх!

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

Использование разработанных средств позволяет уменьшить сроки исследования'и проектирования ПОВС в среднем на 20-30% за счет поиска оптимального алгоритма, приводящего х сокращению числа анализируемых архитектур, использования ЯОМС и уменьшения, времени, затрачиваемого на моделирование аппасап "мх средств и отладку программного обеспечения.

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

1. Золотовский В.Е., Поленов М.Ю. Имитационное моделирование, экспериментальные исследования высокопроизводительных систем // Актуальные проблемы фундаментальных наук : Тез.докл. межреспуб. науч.тех. конф, - М.: Издательство МВТУ, 1989.- С.95-96.

2. Золотовский В.Е., Поленов М.Ю., Павленко В.Г. Система моделирования архитектур проблемно-ориентированных вычислительных систем с целью оптимизации // Перспективы развития и применения средств вычиатпелт.кой техники для моделирования и автоматизированного исследования: Тез.докл. VIII всессюз. науч. тех.конф. - М., 1991. - С.26-27.

3. Поленов М.Ю. Разработка ¡шструментальных средств для исследования высокопроизводительных систем // XXXVIII науч.техн.конф. ТРТИ. Тез.докл. -Таганрог, 1992. - С. 21. ,

4. Поленов М.Ю. Структурное моделирование при комплексном исследовании сложных систем /'/ Областная шуч.техн.конф., посвященняя Дню радио: Тез.докл. - Ростов-на-Дону, 1992. - С.ЗЗ.

5. Павленко В.Г., Середа A.A., Поленов М.Ю. Разработка и оценка высоконадежной матрично-потоковой системы // XLVIII Научная сессия, посвященная Дню радио: Тез.докл.-М., 1993. - С.39-40.

6. Золотовский В.Е., Поленов М.Ю. Средства отображения алгоритмов ЦОС на матричные архитектуры // Методы и средства ЦОС -.Тез.докл. Северо-Каеха:<ской регион, науч.техн.конф.- Таганрог, 1993. - С.46-47.

7. Гузик В.Ф„ Поленов М.Ю. Языковые средства высокоуровневого описания и исследования однородных вычислительных систем //Однородные вычислительное системы, структуры и среды: Тез.докл.У] всеросс. науч.техн. конф. - м., 1953.- С.7.

, 8. Поленов М.Ю. Создание средств описания архитектуры матричных систем// XXXIX науч.техн.конф. ТЕТИ: Тез. докл. - Таганрог, 1993. - С.С5-66.

9. Гузик В.Ф., Середа А.А., Поленов М.Ю., Павленко В.Г. Оценк; производительности отказоустойчивой системы с матрично-потоково! архитектурой // Диагностика, информатика и метрология 94: Тез. докл междунар. науч.техн.конф. - С.Петербург, 1994. - С. 183-184.

10. Поленов М.Ю. Инструментальные средства иерархическогс проектирования систем //Депонир. в ВИНИТИ. № 2291-В94 от 4.10.9* Таганрог, 1994. - 30с

11. Поленов Кг'Ю. Алгоритмо-ориентированный подход при решенш задачи проектирования матричных структур // Известия ТРТУ. № 1. Таганрог, 1995. - С.66.

12. Золотовский В.Е., Поленов М.Ю. Программно-инструментальньп комплекс оценки эффективности параллельных систем при г 1зработке и: архитектуры // Многопроцессорные вычислительные структур^: Сб.науч.тр. Вып. 15 (XXIV). - Таганрог, 1995. - С.4-7.

13. Поленов М.Ю. Многоурозневое моделирование и оптимизации матрично-потоковой вычислительной системы // Сборник научных трудо] ТРТУ. - Таганрог, 1995. - С.99-101.

14. Гузйк В.Ф., Золотовский В.Е., Поленов М.Ю,, Середа А.А Распараллеливание алгоритмов й их отображение на архитектур; многопроцессорных систем // Депонир. в ВИНИТИ. № 2702-В95 от 6.10.95. Таганрог, 1995. - 28с.

В работах, написанных в соавторстве, личный вклад автора состоит ] следующем: в [ 1,2] предложены состав и структура системы моделирования, : [5,9] рассмотрены архитектурные модели, на основе которых производили^ оценки матричной МВС, в [6] предложен способ представления алгоритмов : виде параметрического графа зависимостей, в [7] предложен многоуровневьй многокомпонентный механизм представления ПОВС и язык описания ] моделирования систем,» в [12] рассмотрены состав и организаци инструментальной программной среды для исследования и разработки ПОВС, [14] разработаны алгоритмы распараллеливания и перехода к параметрическо] архитектуре ВС.

оп трту. зак.^72 т"р'