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

ЛгШ[ГРАДСХ|Ш иРДЛ1А ДШЩ 11 ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЩИИ Э^ЖРОМаМаСШ ИНСТИТУТ ШИШ В.И.УЛЬЯНОВА (ЛЫША)

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

ИВАНОВ СЕРГЕИ ВИКТОРОВИЧ

УДК 681.325.023:681.3.019

ОРГАНИЗАЦИЯ И ПРОЕКТИРОВАНИЕ ИСПОЛНИТЕЛЬНЫХ ПРОЦЕССОРОВ ШСОКОПРОИЗВОДИТ^ЯЬНЫХ ВЕКТОРНОтЛОТОКОВЫХ систш ОБРАБОТКИ ДАННЫХ

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

системы и сети

Автореферат

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

1990

/' /

Работа выполнена в Ленинградском ордена Ленина и ордена Октябрьасой Революции электротехническом институте имени В.И.Ульянова (Ленина).

Научшй руководитель -

кандидат технических наук доиент Водяхо А.И.

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

доктор технических наук Торгашев В.А.

кандидат технических наук Кизуб В.А.

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

на заседании спешалиэ.,

градского ордена Ленина и ордена Октябрьской Революгии злок-. тротехшческого института имени В.И.Ульянова (Ленина) ни адресу: 197022, Ленинград, ул.Проф.Попова, ¡3.

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

Защита состоится

Учешй секретарь специализированного совета

Анис.п.юв АЛ.'

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

/у—1-" ^'Актуальность проблемы. Сегодня вычислительная техника cтOi:т па пороге создания ЭК.1 пятого Локолешя, которые по сравнению о ЭШ четвертого поколения должны обладать принципиально hobui.hi функиюгальшьи возможностями, основными из которых являются наличие интеллектуального интерфейса с пользователей, способность поддерживать больииэ базы знаний, а также зозшлсность обеспечить достаточно широкому кругу пользователей доступ к высокопроизводительным и сверхвысокопроиз-водлтелышм ресурсам для решения задач как вычислительного, так и логического характера. Необходимость такого сочетания встает лз потребностей практических задач, например, дая решения прщшадных задач бортового авиационного и космического оборудования требуются высокие возможности символьной обработки з сочетании с высокими скоростями числовых вычислений. В задачах реального времени, когда в быстроменяющейся обстановке требуется оперативный анализ исходных данных и принятие управляющих решений, сверхбыстродействующая машина логического, вывода до.тапа обладать быстродействующими средствами числовых вычислений. Одним из возможных подходов к построению подобных систем обработки данных (СОД) является построение модульных слстем с сетевой архитектурой, в основу' функционирования которых положены динамические сетевые модели вычислений, что позволяет обеспечивать возможные наращивания вычислительной мощности за счет увеличения числа модулей и введения специализированных модулей. .

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

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

высокой скорости вычислений рассматривается векторная обработка.

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

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

- разработка базовых вариантов структурной организации СОД с сетевой архитектурой;

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

- исследование вопросов проектирования и технической реализации высокопроизводительных ВШШ.

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

Научная новизна проведенных исследований состоит в том, что:

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

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

Практическая ценность работы' заключается в слоящем:

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

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

- разработаны элементы систешого этапа проектирбвания ВПВС; разработан до уровня принципиальных схем макетный вариант ВПШ с использованием реальных МаШС и конструктивов и выполнена его верификация на программной модели.

Внедрение результатов работы. Полученные в диссертационной работе теоретические и практические результаты внедрены в Институте проблем вычислительной техники АН СССР (г.Ярославль). •

Апробация работы. Основные.положения и результаты диссертационной работы докладывались на 43-й областной научно-технической конференции по узловом проблемам радиотехники, электроники и связи, посвященной Дню радио, г.Ленинград, 1988 г., на Всесоюзной научно-технической конференции "Теория и практика модального проектирования радиоэлектронных систем (РЭС)", г.Ленинград, 1988 г., на Краевой научно-технической конференции "Молодце ученые и студенты - ускорению научно-технического прогресса в области радиоэлектроники и вычислительной техники", г.Красноярск, 1989 г., на 3-м региональном семинаре "Распределенная обработка информации", г.Улан-Уде, 1989 г., на Международной научно-технической конференции "У.Уе</есКо Ксп(егепсиз е&с(го-Ш^Ь-Щ ", г.Кошице (ЧССР), 1989 г., на 7-й Все-

союзной школе-семинаре "Распараллеливание обработки информации", г.Львов, 1989, на 40 и 41 научно-технических конференциях профессорско-преподавательского состава ЛЭТИ имени В.И.Ульянова (Ленина), г.Ленинград, 1987-1988 гг.

Дубликат-ии. По теме диссертации опубликовано 15 печатшх работ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 152 наименований и приломенпя. Работа содержит 149 страниц текста, 81 рисунка и 12 таблиц.

(ЮДВДАШШ РАБОТЫ

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

В первом разделе дается классификация высокопроизводп- ' тельных мультипроцессорных СОД и приводится сравнительный анализ их принципов построения. Описываются принципы организации и основные аспекты использования векторно-потокових СОД (ВП СОД)..

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

Высокопроизводительные мультипроцессорные СОД предлагается классифицировать по следующим 4 основным признакам: проблемная ориентация, принципы построения модулей, организация системы коммутации, стратегия управления. Предлагаемая классификация не противоречит известным классификациям, а в некоторой степени, дополняет их, учитывая специфику современных нетрадиционных архитектур. Из приведенного в работо анализа можно сделать вывод, что фактическая производительность СОД отличается от пиковой в результате наличия потерь производительности в мультипроцессорных СиД за счет различных факторов: а) невозможность загрузить'операционное устройство (07) в случае, когда ширина параллелизма задачи меньше ширины параллелизма 0/; й) невозможность загрузки ОУ за счет несовершенства системы коммутации; в) невозможность загрузить ОУ при достаточном параллелизме и совпадения типов, параллелизма, но механизмы управления этот тип параллелизма не подцерашаыт, т.е. узким мостом является системы управления; г) потери производительности, связанные с несовершенством компилятора.; д) потери, связанные с несовершенством алгоритма решешш за-Лдчи. Очевидно, что потери производительности вследствии •каждого из фикторов будут, определять фактическую .производительность системы, как бы ни уменьшались поторл вносимые остальными факторами.

Все высокопроизводительные мультипроцессорные СОД класса супер-ЭВМ можно разделить на 5 'основных групп: суиор-ЭЬ;.! высшего класса, к которым мино' отнестл •традигиетше супср-ЭИМ,

обладающие рекордной производительностью и включающие ограниченное число процессоров; супер-ЭВМ среднего класса (мини-супер ЭВМ), такие включающие в себя рграниченноо число пропесс.о-ров, но имокщпо существенно меньшую производительность при существенно унылей стоимости; мощные параллельные компьютеры,обладающие производительностью супер-ЭВМ высшего или среднего класса, которая дбстигается за счет объединения большого числа модулой; супер-ЭВМ на базе .ЦВМ общего назначения, достигающие высокой производительности за счет встроенных средств векторных вычислз1ШЙ; проблемно-ориентированные вычислительные системы, обладающие высоким быстродействием при решении определенных классов задач. Сравнительный анализ эффективности архитектурно-структурных решений супер-ЭВМ на эталонной задаче показывает, что практически все супер-ЭВМ высшего класса дают катастрофический провал производительности. Высокой эффективностью отличаются нетрадиционные архитектур! (Tro.ce, Сцс(г<к 5). Таким образом, появляется достаточно большая "экологическая ниша" - класс систем с производительностью порядка сотен «яш'5, обеспечивающих высокую эффективность при рошешш слабовектори-зуог.ых задач, - на которую претендуют ВДВС. •.

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

- совместное использование принципов векторной, потоковой и логической обработки; .

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

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

- взктерная обработка рассматривается как универсальное средстзо дост;ион>1я высокой производительности при логической.

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

Реализация заданной концепции требует решения ряда задач:

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

2. Разработка архитектурно-структурных решений и принципов реализации векторно-потоковых СОД, ориентированных на релешш вычислительных задач.

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

4. Разработка методов и средств интеллектуального сервиса высокопроизводительных СОД с нетрадиционной архитектурой.

Во втором разделе определяется единство чисто потоковых, функциональных и логических моделей вычислений, в основе которых лежит И41ЛИ граф. Анализируются три формы представления И-ИЛИ графа: строковая, графическая и машинная (пакетная).

Графическая форма представления И4Ш1 графа является формальной моделью потоковых вычислений. Обобщенная модель представляет, собой иерархию моделей: I» -модель, f -модель, Ъ -модель.

I,-модель является моделью самого высокого уровня, описывающая процесс логического вывода, управление вычислительным процессом, процесс сервисного обслуживания. L -модель представляет собой ориентированный И-JШ граф G- = (V, Е) с множеством вершин V трех типов: "И"-вершин - А, "ИЖ"-вершин - 0 и терминальных вершин - Т (АD OUT =V, АО ОП Т = 0) ц множеством дуг B^(VxV), который удовлетворяет условиям.:

Имеется начальная вершина графа v0 , такая что ¡л£ (AU 0) и In.( V») v), где ueV ; термшальные веришны tjteT,

Qui (i ) * 0» где i/) - множество дуг, входящих в зернину и , Out (и) - мнояество дуг, выходящих из вершишь.

2. Каждая вершина «/е(А^О) пршидле^т хотя бы одному пути, начинающемуся из вершины Ли заканчивающемуся в одной лз вердин t .

3. A-BopmiHU - это зорипны функционального т^па, когорте осуществляют преобразование информации.

•1. О-верлпт: - это верпишг, 'ойразувде очоред.: o:jctо;; на вадашке запросы. . :

Ь. Т-ворииш - это вершины, которые видают данные по полученному запросу на входную дугу.

Г. По граф/ С- распространяются фиша; двух типов: я-фишки-ззпросно-ресу^егпз и с/-фишш - данных.

7. Все фишки перемещаются по лугам Е, причем ¿-фишки двигаются от вершины ьг, к вершинам I, а с/-фишки двигаются в обратном ¡вправлении.

В. I- и «/-фишки, принадлежащие к одному и тому же набору (запросу), имеют один и тот же индекс (дает).

9. На одной и той же дуга е. е Е не могут одновременно находиться и «/-фишки, раскрашенные одним цветом.

2-фишки продвигаются по И-ЙШ графу согласно правилу активации вершины. При активации вершины происходит поглощение г-фишки, выделение требуемого вершине ресурса, превращение ее в автомат и распространение X-фишек на все выходные дуги. В работе приводятся правила определения готовности вершины, правила смены маркировок.

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

Б-модель является частным случаем ¿-модели, содержит только А-вершины и описывает' детерминированные вычисления. Т> -модель является частным случаем Е-модели, когда по графу движутся только «/-фишки по направлению от терминальных вершин.

В работе рассмотрены 4 основных варианта организации вычислительного процесса в ВП СОД:

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

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

3. Работа с подпрограммами по типу оператора АРВ6У. В сис~

теме команд элементарного уровня имеется команда обращения к подпрограмме по типу оператора АРН.У. Глубина вложения в 8том случае произвольная и определяется объемом имеющихся ресурсов. Оператор АРРАУ представляет собой укрупненный потоко- . вый оператор.

4. Динамические сети предполагают использование операторов порождающего тала, которые порождают операторы-наследники. Каждый оператор может породить произвольное число операторов-наследников. Каждый наследник снабжается данными или ссылками на данные.

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

Рассмотрен переход от модели вычислений к виртуальным потоковым машинам. Анализируются пакетные формы представления И-ИЛИ графа. Вершину И-ШШ графа в форме пакета можно представить следующим образом:

<Вершина> ::= <4ункция><Тело><Связи) <Тело> ::={"<Аргумент>} ■

<Связи> ::*><Имя приемника^<Адрес приемника)

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

Рассмотрена принципы упаковки команд информационного графа БП СОД, что по существу определяет Выбор соответствующей архитектуры. С точки арония упаковки команд, потоковые системы можно разделить на три группы: традиционные потоковые архитектуры (ТЬР), горизонтальные потоковые архитектуры (НТ>Г) и' распределенные потоковые архитектуры (ЬЬБ), каждая из которых в свою очередь имеет скалярную 13) и векторную (V) версию, что приводит, к .6 основный типам потоковых.архитектур. Приведенный анализ возможных способов упаковки команд позволяет ут- ' верждать, что за счет наличия информационной избыточности, присущей сетевым моделям вычислений, создаются услоб;:я ачя создания системы команд более компактной, чем системы команд традиционный ЭШ.

Третий раздел диссегчтацпл поедявдн. вопросам организации В1Ы11 с иерархической распределенной памятью.

В основе ВПВО ле::шт векторное расширение схем потока данных (ОВД), названное схемой'потока векторов (СТО). В отличив от СЦД схемы потока векторов содержат кратные дуги, по которым передвигаются элементы векторов, и, кроме того, добавлено ряд специфических вершин работы с векторами. Рассмот- . репы правила определения готовности команда по первое и по последнему элементу вектора. В приложение приведено форг/алъ-ное определение и анализ С1Б.

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

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

Необходимое условие безопасности вычислений достигается, если прп .ш^бой досгпхзлой маркировке М схемы СПВ & =№,1",лг) выполняется следук^эо условие: .

Го , если И ЧесОиЩ

■^"[Е М(ё) , есл.1

-

/V- множество вершин, Е - множество дуг, Jk- функи;ш входа, Cut -, функхт.ш выхода,/«? - кратность дуги е . При маркировке Ы считается, что дуга £ содержит М^е) фццтг.. Лрч адресном покрытии А считается, что результат срабатывания операторной вершины тг помещается по адресам Aie) , £ -Счб(^) .

Определяем, с точки зрения реализации 131ЬШ, является способ распределения ячеек локальной памяти да хранения дан ных. Можно выделить три основных механизма распределензш ресурсов: статические, динамические к сметанные. Механизмы управления и распределения зависят от организации локальной па мяти (ЛП).

• Еабота не только со скалярами, но и с векторами почти скидает временные затраты на проверку готовности команд, но в то же время ставит две основные проблемы: распределение и перераспределение скалярных и векторных ячеек ЛП и проблему ■коммутатора, вследствиы слишком плотного трафика. Для решети этих проблем рассмотрены три типа структур кошдутакы: система с перекрестным коммутатором; система с распределенной коммутирующей памятью; система с коммутирующей очередью. В работе приводятся алгоритмы управления ЛП в этих олстеыах. Использование функционально-распределенной ЛП позволяет организовать процесс бесконфликтной коммутации, что очень важно в условиях высокого процента загрузки ОУ. Для сокращения времени обработки команда используется механизм расслоения ЛП на банки правых и левых операндов.

Приводятся структура организации ЛП, использующие как статическое, так и динамическое распределение ресурсов. Статическое распределение приводит к наиболее простым механизмам управления ЛП. Однако, здесь встает проблема выбора количества скалярных и векторных ячеек памяти, которые будут сильно завпсить от специфики решаемой задачи. Динамическое распределение ячеек ЛП позволяет эффективно разделять регистровые ресурсы между векторами и скалярами. Однако, динамическое распределение ресурсов приводит к большим аппаратным затратен. Для каждого из 2 а банков ЛП необходимо поддерживать даа независимых стека, два счэтч:и<а и схему прозерки на перехлест. Ери реализации ЗГП1П на СЕ 1С это привод;:!' к увеличении числа типов CEIC, Кроме того, в данном случае неизбежны «линчевав ситуации.

3 работе рассмотрены принципа организации и функцпснпро-

ватт памяти команд и готоэмостой В1Ш. Организация памяти котанд а готовностей суцествотю зависит от способов передачи лрограмг/лого модуля из оперативной памяти (ОП) в ЛП, способов инициализации программного модуля, способов буферизации команд и готовностей. Исио.чьзозашю КЖ-иамяти но только решает проблемы, свлзашме со способам:! перодачи и инлцпализа-иш программных модулей, но и проблем сегментации потоковой программы. ¡tamo выделить следу^щно варианты использования KüU-памяти в ВШШ: отдельная КЭШ-память команд; отдельная КЖ-память донных; совмещенная КЭШ-память команд и данных.

При проектировании КЭШ-памяти команд объем памяти готов-ностей будет зависить от метода распределения: при статнчес-ком распределении память готовностей должна содержать I бит на команду, при динамическом распределении на каждую когданду необходимо {.Cog¿V •+ I) бит. Очистка памяти готовностей может происходить либо в-процессе загрузки КЭЫ-<5уфера, либо в процессе функционирования 11Э в холостые никлы.

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

Приводится обобщенная структура КЭШ-памяти ПЭ и алгоритм свопинга. Время приведенного алгоритма будет определяться соотношением:

Т*эш= (I ОТчк +Á- СТпс + Toon+ Те» + Tj* ■+• Татг + Ток),

где Тч< - время цикла чтения из КЭШ-буфёра; Тпс - время поиска в справочнике; 'Iben - время обращения к ОП при чтошс: дзн~ шх; Т/7> - время пересаль: данных ::э ОП в КЭ^-буфер; Tjk -иро:.и ц/лсл за ¡lio;: в K3L.-6y<jiep; "ícnr - время очистки памяти готовностей; ?<?* - время ожидания ззаерзек;!я предадут?й оле-раг.:л в di: ^ - вероятность неудачного обращения к KäL-бу.^ру. Сравнительной анализ г.р!,о:<т;1аност.: Ю'^-паУлти в BÍLÍÍI по:сазал

ограниченность ее применения»

В четвертом разделе определяется специфика задачи про-ектцроаания высокопроизводительных СОД, приводятся основные задачи системного этапа проектирования ВПВС. Проведенной сравнительный анализ эффективности ВПВС и векторно-конвей-ерных ВС позволил сформулировать обобщенные условия эффективности использования ВПВС. Векторно-потоковые ВС целесообразно применять для обработки слабовекторизуемых задач с ограниченная параллелизмом, т.о. 'задач, у которых векторизуемая доля программного кода: v\< 0,3. 3 свою очередь, параллелизм скалярных участков для задач в ВПВС очень высок :

М ^ аналаза следует, что применение векторно-пото-кового принципа управления целесообразно: в случае плохо векторизуемых задач при их количестве больше 4; в случав хорошо векторизуемых задач (tf^ 0,6) при их количестве больше 8.

Разработан макетный вариант ВЛИП на основе использования реальной КЭБ (HaBiC серии 11-300 и стандартных конструктивов ЕС ЭВМ), доведенный до уровня принципиальных схем. В ■ качестве ОУ используется 16 разрядное арифметико-логическое 'устройство с производительностью до 10 fi^LOfs.

Процессор реализован на 4 платах, на каждой из которых расположены со 4 ЫаЕИС а 6-8 QIC. Данный процессор предполагается использовать в качестве ОУ ВПВС. Практическая сторона разработки сводится к разработке процессора команд, представляющего собой схеьу управления ЛП ПЭ).

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

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

• Вся программа разбивается на программные модули фиксированной длины, которые затем загрукаытса в накопитель 11Э. Уп-

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

При реализации на MaHIC серш 11-300 схема процессора команд занимает 2 БИС, схема упраления оперативной памятью -I НЮ, микропрограммный автомат - I ШС. •

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

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

По процентное соотношении команд видно, что управляющие команды являются самыми многочисленны}®! (от 27$ до 64$ общего количества команд). В 12 из 14 циклов ощ.составляют от 42/0 до 64>* команд (циклы № I - G, 8, 10 - 14). Соотношение арифметико-логических кошнд (от 13 до 31 %) и команд обращений к памяти (от 8/2 до 30^) в этих цшслах прпморно 1:1. Команд умножения-деления в -циклах "-3 I - 6, 8, 14 от 2,'ь до &%. В циклах .'L'fc 10 - 13 их. совсем нот.

Моделирование выполнения пшиюв (донашка) позволяет выявить 3 характер mix вида циклов. Первый вид это циклы Ш I, 7,. 9, гдо наблюдается малое использование ПЭ команд управле-гсм при относительно раннем использовашш остальных ПЭ. Второй в:1Д - г.пелп !№ Ь, о, 8, II. Здесь имеется больной перекос в сторону использования ГГЗ команд упрашюшш и прллорио разном использовании ПЭ сло.'хсн/л-логшси и ПЭ памяти и хороаем использовании ПЭ уг2!о:;:сн-:я-деле<с:я. Третий вид это viuva. № 3, 10, 12, 13. 0:u хара::то:.!И больйьйд коэффициентом аспользова-II.in ПЭ памя?.. при сбалансированной :1сяользо!??:п:1 »12 слох«Ь1Я-легнк:: .'i:0u ПЭ -jizk-:.:„гся-д. ленде с ¿1Э упразлишат.

■ основные вшад И РКЛЧШШы рашш

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

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

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

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

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

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

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

4. Разработаны элементы системного этапа проектирования ВПВС, в частности, сформулированы обобщенные условия целесообразности использования ВПВС. Разработан до уровня пр;шцили-альных схем макетный вариант ВШП с использованием реальных ЫаБ<С н конструктивов, что позволяет сделать вывод о возможности эффективной реализации ЫШ даже при использовании не

самой современной КЭБ. Проработка принципиальных схем показала, что реальное время цикла определяется временем быстрой статической памяти, которое сегодня составляет 15-20 не.

ПУБЛИКАЦИИ ПО Tiä<L2 ¿JICGÛPTAiÛHÎ

1. Алгоритм и структура спецпроцессора быстрого преобразовали Уолыа-Адамара конвейерного типа/Иванов C.B., Колесников ¿.А., Парунов A.B., Свиньин С.Ф.; Ленингр. электро-техл. лн-т. - Л., I98S. - 6 с. - Лол. в ВИНИТИ 06.06.89,

& 3683 - В89.

2. Баталов Д.И., Баталова Л.Ю., Иванов C.B. Управляющие вычислительные системы с ьекторно-потоковой архитектурой// Метода и сродства управления технологическими процессами: тоз. докл., Саранск, 15-17 мая, 1989. - С. 55.

3. Баталов Д.И., Иванов C.B., Шарков А.Ю. Метода и средства иерархической организации системы памяти вокторно-пото-ковой вычислительной олстеш//Распараллоллвание обработки информации: тоз. докл., Львов, 9-14 октября, I989-. - C.I66-IÇ7.

4. Вокторно-потоковые системы и их реализашя/Водяхо А.И., йлоллн B.II., ¡'панов C.B. и др.//Изв. ВУЗов., Приборостроение, 1989. - lb 9. - С. 27-33. .

5. Векторно-потоковые Н1$С процессоры/Власов В.В., Во-дяхо А.И., Иванов C.B. и др. //!>1е;кдународная конференция электротехнического'факультета Высшей технической школы: тез. докл., Коапце (ЧССГ), 29-30 августа, 1989. - С. 124-129.

6. Векторно-потоковые RISC-архитектуры исполнительных процоссоров/Еоддхо А.И., Иванов C.B., Пузанков Д.В., х^ло— лип В.П. - Ярославль. - 1989. - 53 с. - (Препринт ШШТ АН 0001', Ге 5).

7. Водяхо А.П., Иванов C.B., Пузанков Д.В. Вокторно-потоковые вычислительные слстемы//Гаспараллсливаш:е обработки информации: тез. докл., Львов, 9-14 октября, 1989. - С. 147-148..

8. Водяхо А.П., Иванов С.Б., Пузанков' Д.В. Использование зекторно-потоковых архитектур для дости;ло!пи сверхзысокой скалярной нропзво,г<.'Телыюстл//Распределе:шая обработка информа-

: тез. докл., Улан-Уде, 2-G подя, 1989. - С. 5.

9. Иванов C.B. Срггап:?:1"'Л! локальней памяти векторио-по-icKOJcro ученые л студенты - ускоренно научно-'.::;ог1.с-сса в сбластл рз;^:соло::трон-:кл л в::-

числительной техники: тез. докл., Красноярск, 2Ь мая, 1989. -С. 33-34.

10. Иванов C.B., Урдзик П. Особенности и предслышо возможности конвейерных структур супер-ЭШ/Леникгр. электротохн. ин-Т. - Л., 1987. - 24 с. - Дел. в 1Ш1ТИ 22.12.87, Ji В992-Б87.

11. Метода и средства интеллектуальной диагностики сперх-высокопроизводательных вычислительных систем/Баталова-Л.L,, Водяхо А.И., Иванов C.B., Липецкая Н.Д.; Лонингр. электротохн. ин-Т. - Л., 1989. - 27 с. - Де.п. в ВИНИТИ 1-1.02.89, & 937-BU1.).

12. Модульные вокторно-потокоапе вычислительные системы// Пузанков Д.В., Водяхо А.И., Иванов C.B., Начерскпй C.B.// Теория и практика модульного проектирования радиоэлектронных систем: тез. докл., Л., 1988. - С. 77-78.

13. Построение формальной модели-потоковой машины логического вывода/Баталов Д.-И., Водяхо А.И., Иванов C.B., Ьар-ков А.Ь.//Молодце ученее и студента -ускорению научно-технического прогресса в ¿бласти радиоэлектроники к вычислительной техники: твз. докл., Красноярск, 25 мая, 1989. - С. 37.

14. Принципы организации и проектирована локамло-од-нородннх матричных умножителей на основе СБПС/Водяхо А.И., Григорькин А.Я., Грушш В.В., Иванов С.В.//Структура и математическое обебпечешге.специализированных вычислительных комплексов. г-Л,, 1968. - С. 7-12. -'(Изв. ЛЭТЛ; В,in. 394).

15. Система команд векторно-потокозсй вычислительной систеш/Водахо А.И., Иванов C.B., Липецкач Н.Д. :i др.; Лешнгр. •электротехн.,ин-т. - Л., 1988. - 17 с. - Дел. з ВИНИТИ 12.01.89, № 296-В89.

. М-15503. Подписано к печати 8.01.00. Заказ 150. .. Формат 60x64/16. Объём 1 п.л. Тираж 100. Бесплатно.

Лзмрносовсхая типография Ленуприэдата. , 189510, г. Ломоносов, пр. Юного леиинка, 9,