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

РЯЗАНСКАЯ ГОСУДАРСТВЕННАЯ РАДИОТЕХНИЧЕСКАЯ АКАДЕМИЯ

МЕТОДЫ И АЛГОРИТМЫ АВТОМАТИЗИРОВАННОГО СИНТЕЗА АРХИТЕКТУР МНОГОФУНКЦИОНАЛЬНЫХ КОНВЕЙЕРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

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

систем и соти

Автореферат диссертации но соискание ученой степени

РГ6 од 3

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

кандидата технических наук

Рязань 1994

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

Научный руководитель - доктор тоишчоских наук, профессор, чл.-кор . АТН РФ, академик МАИ -В ЛЬ Корячко s-

Официальные оппонента: зав. каф. САПР Московского государственного технического университета им. Н.Э.. Баумана, проф., д.т.н. Норенков Игорь Петрович; Доцент РГРТА, к.т.и. Пржегорлинский Виктор Николаевич.

Ведущая организация -НПО "Персей" НИИ "Аргон", г.Москва.

Защита диссертации состоится ¿¿J&JUsi 1994г. в "Ю" часов на заседании специализированного совета К.063.92.01 в Рязанской государственной радиотехнической академии по адресу: г. Рязань, ул. Гагарина, 59/1. «

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

Автореферат разослан "ft* 1994р.

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

доцент A.M. Столяров

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

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

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

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

и системах реального времени привела к созданию клт<пй»ров с перекрытием или параллельно конвейерных ВС, в которых исиомь зуется как принцип конвейеризации, так и нршииш параллелизма. Такие системы являются сугубо специализированными и ориентира ванн на реализацию одного, редко двух, относительно нростох алгоритмов. Со многих хо системах реального времени т[юбуотся обрабатывать но один, а несколько различных алгоритмов или в зависимости от внешних условий перестраиваться с одного алгоритма на другой. Такие конвейерные ВС называются многофункциональными (1ЖВС).

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

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

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

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

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

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

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

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

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

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

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

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

1. Метод синтеза параллельно-конвейерных форм алгоритмов

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

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

3.' Методика расчета параметров КВС, ориентированная на получение приемлемого проектного решения при минимуме аппаратных ресурсов.

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

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

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

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

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

_и_&не_дрени_еРезультата, полученные автором при _ждодцмши_д<сео1т1Щ1о_Н11оЯ работы, были использован» » ряде на-

учно-иследоаательских работ - хоздоговорной, выполненной по заказу НПО "Персей" (г.р.й 01060119417), и двух госбюджетных (г.р.й 0Т910ОЗвОГ>5, г.р. й 01880063171) и внедрены на двух предприятиях и В учебном процессе РГГТА.

Ада^адая^аботи^ Основные пождания диссертации обсувдены на Российской научно-практической конференции "Исследование, проектирование и реализации пользовательского интерфейса в САПР" (г.Орел, 1992 г.), на 2-й научно практической конференции стран СНГ "Распознавание образов и анализ изображений: новые информационные технологии" (г.Ташкент, 1992 г.), на 19 й молодежной научно-тохиичиской кстфиреццци "Гагаринские чтения" (г.Москва, . 1993 г.), на 2-й Международной конференции "Информационные сети и системы <КШ.:-93)" (г.Санкт-Петербург, 1993 г.).

Публикации. Основные результаты диссертационной роботы опубликованы в 9 пнчатных работах и двух научно-технических отчетах.

Структура и »/*>7.ем работы. Лиссертзция состоит из введения, четырех глаь, заключения, библиографического списка, занимающих 226 стр, и прилчкнния на 29 стр. Библиографический список содержит 136 наименований.

2.ОСНОВНОЕ СОДЕПШШЕ РАБОТЫ

Во_ьюд>)1Ши обоснована актуальность темы, сформулирована цель диссертационной работы и приводе™ основные научные положения, которые выносятся на защиту.

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

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

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

Причины этих недостатков кроются в следующем:

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

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

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

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

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

Для графовых моделей алгоритмов и архитектур сформулирована задача структурного проектировать КВС по заданным алгоритмам функционирования- найти некоторый метод ъ отображения мно-даства Функциональных графов алгоритмов {0А>)в граф МКВС Сп: 7л с а ■* '■'■>, I -Г.ч. При атом могут накладываться некоторые ограничения, м-и]1иччр, на время решения алгоритма т , число МО, йро-# изводлтельнгють КЬС и т.д.

При [.'роккти^шянии МКВС приходится сталкиваться со следующими пр^б.п-мчми:

Г. Граф коньс'йг'ряпго здгаислитоля весьмп снеци'Ьичнн и должен иметь структуру, ияоморфну» графу исходного алгоритма, в слупи». МКВС гр'!'! конвейерного и/ч1'.слвт»ля изомор^н нескольким, п оляуга

случае различным графам исходим алгоритмов.

?,. Управлении в МКВС должно быть организовано таким обра- , зом, чтобы обрабатываемые одновременно на конвейере задачи не

ресурсами МКВС.

Для решения атих проблем, создания методов «""алгоритмов--

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

Произведен анализ существующих методов отображения графов исходных алгоритмов функционирования в граф конвейерной вычислительной системы. Установлено, что наиболее широко пр^зняеше методологии канонического и обобщенного отображения применима• только для сильно регулярных (решетчатых) графов, узлы которых чаще всего представляют элементарные операции, такие как "умно-иение-и-сложение". Попытки применить эти методологии к графам произвольной формы не дали положительных результатов, а разра- , ботанныо алгоритмы и программы имеют большую вычислительную сложность. Данные методологии не применимы для проектирования многофункциональных КВС. Более универсальным является метод синтеза архитектур ВС (но только КВС) путем штьективного отобракения узлов графа частного алгоритма в узлы пространственно-временной решетки ь* (или ит-укладки): 1с:У—»ьа с последующим проецированием ее на гиперплоскость устройств. Этот метод может бить легко представлен в виде задачи математического программирования. Однако трудоемкость задачи двумерной укладки орграфа весьма высока, особенно для КВС, где число модулей обработки очень велико. Данную модель построения архитектуры МКВС, путем построения ит-ук-ладки,целесообразно принять за базовую и разработать для не& прикладные методы снижения трудоемкости. А в качестве базовой архитектуры МКВС целесообразно принять структуру, состоящую из нес-' кольких параллельно работающих нелинейных конвейеров, соединенных

мэжду собой и с устройствами памяти и управления модулями коммута-

•ЦИЯ.

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

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

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

Был произведен анализ совместимости таблиц занятости исходных алгоритмов. Установлено, что две смонные задачи А и В всегда совместимы, если одноименные строки 1 их таблиц занятости подчиняются неравенству:х"(;П + «"(;5)>Ьо* (хь(1

для У^ттт,. х"=--571ГгТ,хь=0,Ьь-1, где Р число МО;

Ьа и Ьь- лвтентности обработки таблицы А и В (соответственно) на однсфуикциональном конвейере; колаекая латеитмость обработ«-ки таблицы в после а.

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

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

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

~ций заранёТ1кшзвостныТ^йн а лизтгоко зол ,ч то -в —том случае Со с-_

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

1) не требуют дополнительных программных и аппаратных затрат на управление;

2) позволяют получить максимальную производительность в загруженность ступеней конвейера;

3) возможно проектирование всех ч последовательностей независимо друг от друга.

Для получения таких последовательностей предлагается разбить все множество операций V алгоритма на Н зависимых упорядоченных подмножеств У^ отвечающих условиям: ' У(п V =о, 0 для V М«^.));

ук<у1 для V V (к*1), если 3 в„"<Л

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

С помощью аппарата теория расписаний был произведен анализ вариантов запуска ветвей операций на конвейере. Установлено, что время выполнения задачи шнпдаально, если самая длинная (трудоемкая) ветвь операций запускается первой (т(У1)=тах т (V ^)), а длины остальных ветвей подчиняются выражению: )=га(У1)-где 3 при последовательном запуске- номер такта запуска ветви, а при параллельном запуске -уменыиашшй на единицу номер модуля обработки, с которого осуществлен запуск V . Для данной стратегии обработки ветвей операций V (1=ГГВ) получены выракения, позволяющие определить минимально необходимое число модулей обработки Р в конвейере, необходимое число разбиений исходного алгорисма задачи на N ветвей. Данные выражения позволяют предложить простую методику расчета пара>двтров КВС, ориентированную на получ. ние приемлемого проектного решения при минимуме аппаратных ресурсов.

Как указывалось ранее, для разбиеш1я исходного алгоритма на ветви операций наиболее перспективным и легко формализуемым явля -ется метод отображения в узлы пространственно-временной решетки Ъ* (ит-укладка графа): ах-» Ь* и нахождение миокества П(0)*{я (0), яи(0)) укладок графов всех частных алгоритеов 0*0А.

Учитывая большую вычислительную сложность (КР полная) задача и особенности конвейерной обработки, предлагается несколько упростить исходную задачу, производя отображение не в двухмерную Ьа решетку, а на N прямых ь", т.е. ПИ)): V-» (Ь ), 1=1",Н,или П(0)«{* ), где Ь* • Каждой целочислонной точке Г (1Ми,

1,2,,..)) прямой I/ соответствуют проекции * и * , т.е. сущи ствуют отображения Т-1/ и 1м" . Проекции каждой точки 11 прямых однозначно могут быть оггрмдилены по смещению относительно на чальной точки I =о соответствующий примой I,'.

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

Разработан алгоритм на основе метода ветвей и границ, и кото ром на каждом шаге выделяется подмножество распределяемых вершин V и подмножество точек (1И Л) >( в которые производится рас-

пределение. Для выделенных вершин находятся возможные варианты

размещоиий к(1) с последующим отбором вариантов, для которых критерий оптимальности rain. Для снижения трудоемкости применены следующие метода отсечения неперспективных ветвей: отсечение ветрей соответствующих дублированию в листьях одного и того ад яруса дерева поиска, но~сгхудаой41ц0вкой-74^):-ввтввй,--соот=— ветствущих укладкам, которые не могут быть реализованы за заданное время н тактов конвейера; и укладки с худшей оценкой /(Е) для ярусов k>N, т.к. в дерево поиска начиная с яруса N оценка ? возрастает ш> всех ветвях дерева поиска пропорционально не менее чем на величину Вычислительная сложность точного алгоритма для случая абсолютно равномерных ярусно-параллолышх форм (ЯПФ) графов исходных алгоритмов не превышает 0((nl)N"), а эвристического о(н(п!)). Для абсолютно равномерных ЯЛФ более про- -изводительными являются алгоритмы на основе метода групповых перестановок, вычислительная сложность таких алгоритмов^ не превышает 0(п").

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

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

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

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

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

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

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

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

лено , что метод групповых перестановок- не прЕзмоиим для этого случая. Разработан алгоритм на основа метода ветвей и грашщ, который за время,пропорциональное 0<Н'й-г"»производит построе-1ше-нпраллелык>-пос,лвдог1атодышх-4£рм^|н5|ш^к1х№ В отличие от алгоритма и главе 2 на кавдом ярусе определяется кэ множество I1 точек с равновромешшми проекциями, о множество активных модулей обработки и. Трудоемкость перебора при построения частичных укладок снижается за счет сопоставления времени работа модулей обработки и трудоемкости распределяемых операций, в также отсечения ветвей, которые но могут Сыть реализованы на заданном множество модулой обработки. Преимущество данного алгоритма в том, что он позволяет строить последовательности с заранее заданными таблицами занятости. В этом случае множество активных модулей обработки определяется не из ь' прямых, а непосредственно из таблицы занятости. Этот ко алгоритм применим для построения вычислителышх последовательностей в неоднородных ШФС, когда типы модулей обработки заранее известны.

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

Разработан алгоритм определения последовательности задач в цикла с минимальным применен выполнения по критерию минимума простоев в системе. Трудоемкость алгоритма не превышает о(ч°), где ч-число задач в цикле.

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

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

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

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

Программные модули пакета написаны на языки pascal и функционируют под управлением операционной системы mí: !ю« на пор-зоналыгых ЭВМ типа IBM PC/AT/XT, но могут быть перо но се ни и на ЭВМ других типов, где имеется язык программирования pascal. Минимальный объем оперативной памяти, необходимый для работы па-сета, составляет 28 Кслов. Все входные и промежуточные данные гакето хранятся в файлах прямого доступа, что обеспечивает удоб-зтно их контроля и коррекции.

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

Пакет бил использован при проектировании преобразователя 1ходной информации в бортовой системе контроля и управления ле-■ателышм аппаратом. Пересчет входных данных производится в за-1Исимости от .угла крена летательного аппарата по трем различным встиым алгоритмам. Полученная в результате расчета структура встоит из пяти однотипных модулей обработки, среднее значение лгрузки МО такой структуры близко к 100%. Реализация донного иожостиз алгоритмов на параллельной ВС показывает, что парал-едып;о свойства исходных частных алгоритмов будут исчерпаны уже ри четырех МО при средней загрузке МО 60 - Дальнейшее

наращиваше вычислительной мощности параллельной ВС нецелесообразно, при этом производительность такой ВС почти вдвое меньш

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

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

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

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

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

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

3. Предложены методы и алгоритмы определения параметров проектируемых МКВС: число модулей обработки, количество и мощности ветвей вычислений.

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

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

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

пей системы при реализации иа ней заданного класса алгоритмов в режиме реального времени.

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

Результаты диссертации использованы в трех научно-исследовательских работах Рязанской государственной радиотехнической академии, выполненных в 1986-1994 годах, 'внедрены на двух пред-триятиях и в учебном процессе РГРТА.

Основные положения диссертации опубликованы в следующих работах.

1. Гусев П-В., Копейкин Ю.А. Алгоритм минимизации числа дакмодульных пересылок в параллельной многопроцессорной вычислительной системе //Автоматизация проектирования ЭВМ: Меквуз.сб. яаучшх трудов.-Рязань:РРТИ, 1993. С.48-53.

2. Копейкин Ю.А. Выбо_р оптимального числа процессоров в конвейерной вычислительной системе //Проектирование ЭВМ: Мех-вуз. сб. научных трудов.-Рязань :РРТИ," 1992. С.12-17.

3. Копейкин'Ю.А. Критерии оценки качества вычислительных зистем //Автоматизация проектирования и микроминиатюризация ЭВМ. :Межву'з. сб. научных трудов. -Рязань: РРТй, 1988. С.47-52.

4. Копейкин С.А. Выбор алгоритмов для конвейерной организации вычислегай // Автоматизация проектирования микроэлектрокных вычислительных средств: Межвуз. сб. научных трудов. -Рязань: РРТИ. 1990. С. 102-105.

5. Копейкин Ю.А. Конвейерные преобразователи информации в пользовательских интерфейсах интеллектуальных САПР // Исследование, проектирование и реализация пользовательского интерфейса в СаПР: Материалы Российской научно-практической конференции. -Орел: Администрация Орловской обл., Общество "Знание" России, Ин-т автоматизированного проектирования РАН, А/0."Техником", Московский полиграфический ин-т, МП "Гамма", 1992. С.36-37.

6. Копейгаш Ю.А. Алгоритм минимизации числа межмодульных пересылок в бортовых специализированных вычислительных системах // Тезисы докладов и сообщений XIX Молодешой научно-практичес-

кой конференции "Гагаринскиэ чтения".-м.: МНВШ и ТП РФ. Ассоциация инженерных вузов РФ, Академия космонавтики, МГАТУ им. К.Э.

-ЦиолковскоГОт-19ЯЗ.^-С^ЭЗ=аа.______

7. Копейкин Ю.А. Конвейерныо преобразователи информации в системах распознавания образов //Распознавание образов и анализ • изображений: новые информационные технолог™: Тозиси докладов 2 научно-практической конференции 2-8 сентября 1992 г. -Ташкент: Институт кибернетики и ВЦ АН Узбекистана, 1992. С.105-107.

8. Копейкин Ю.А. Алгоритм минимизации числа нелинейных связей в последовательной многофункциональной конвейерной вычислительной системе реального времени //Автоматизация проектирования ЭВМ: Можвуз. сб. научных трудов.-Рязань:РРГИ, 1993. 0.24-29.

9. Корячко В.П., Копейкин Ю.А. Распределение связных подзадач по вычислительным ресурсам информационно-вычислительной сети //Информационные сети и системы (КИСС-93): Тезисы 'докладов 2-Й Международной конференции КИСС-93. -С.-Петербург: ГУТ им. проф. М.А. Бонч-Бруевича, Международная Академия информатизации, 1993. С.104-106.

КОПЕЙКИН Юрий Алексеевич

НЕТОДЫ И АЛГОРИТМЫ АВТОМАТИЗИРОВАННОГО СИНТЕЗА АРХИТЕКТУР Ш0Г0ФУ1ИЦШ1АЛЫПЯ КОНВЕИКГШХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ Автореферат диссертации на соискание учоной степени кандидата технических наук Подписано в почать OG.05.94. Формат бумаги 60*84 1/16. Бумага газетная . Печать ротапринтная. Усл. печ. л. 1,0. Уч.-изд.л. 1,0. Тирах ьо экз. Зака. Бесплатно. Рязанская государстпоштя радиотехническая академия. 390005, Рязань, уд. Гагарина, 59/1. Участок оперативной полиграфии облетатущ'»шюния. 390013, Рязань, ул. Типанова, 4.