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

п

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

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА И ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ АВИАЦИОННЫЙ ИНСТИТУТ ИМЕНИ СЕРГО ОРДЖОНИКИДЗЕ

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

МОРАРУ Виктор Андреевич

УДК 681.324

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

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

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

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

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

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

профессор БРЕХОВ О.М.

Официальные оппоненты: доктор технических наук ЛИТВИН В.Г.

кандидат технических наук, с.н.с. ДЕГТЯРЕВ Е. К.

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

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

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

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

Ведущее предприятие: Институт проблем управления,

г. Москва

Защита диссертации состоится

д. 4, МАИ

Автореферат разослан

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

Ю. В. Горбатов

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

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

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

Работы таких авторов как Денис X., Гурд Ж. , Гостелов К., Вин А., Мотоока Т. , Майерс Г. , Артамонов Г. Т. , Барский А. Б., Белецкий В.Н. , Брехов 0.М. , Бурцев B.C. , Евреинов Э.В. , Прангишвили И. В., Игнатущенко В. В. , Торгашев В. А. , Плюснин В. У. показывают, что один из наиболее перспективных методов увеличения производительности вычислительных структур, особенно при решении задач с нерегулярной структурой, является асинхронное управление вычислительным процессом, одна из разновидностей которого - управление от потока данных.

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

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

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

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

В соответствии с поставленной задачей исследования проводились по следующим направлениям:

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

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

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

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

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

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

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

Научные результаты. В результате проведения исследований автором получены следующие результаты:

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

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

3. Разработана модель ЭВМ УПД с общим ресурсом при предельных случаях загрузки процессоров

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

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

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

Практическую ценность представляют:

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

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

Реализация и внедрение результатов исследований. Разработанная на основе аналитических и имитационных моделей методика и комплекс программ оценки производительности потоковых вычислительных структур внедрены в НИИ "Аргон", г. Москва, а также использовались в учебном процессе в двух ВУЗах, что подтверждается

соответствующими актами о внедрении.

Апробация работы. Основные результаты работы докладывались и обсуждались на 8 Всесоюзных и республиканских конференциях и семинарах:

- Всесоюзный симпозиум "Перспективы развития вычислительных систем".- Рига, 1989

- Республиканская научно-техническая конференция, посвященная 25-летию образования КПИ им. С.Лазо. - Кишинев, 1989

- Белорусская зимняя школа-семинар по теории массового обслуживания "Математические методы исследования сетей связи и сетей ЭВМ".- Минск, 1990

- Всесоюзная конференция "Однородные вычислительные среды и систолические структуры". - Львов, 1990

- Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания. - Москва, 1990

- Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания. - Москва, 1991

- Научно-техническая конференция "Автоматизация проектирования РЭА и ЭВА". - Пенза, 1991

- Всесоюзная конференция "Интеллектуальные системы". Туапсе, 1991.

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

Структура диссертационной работы. Диссертация состоит из введения, четырех глав, списка литературы С101 наименование) и приложения. Объем работы - 161 страница, 51 рисунков, 3 таблицы.

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

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

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

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

обзор существующих языков программирования потоковых ЭВМ.

В зависимости от способа передачи данных Снепосредственная или пакетная передача) и от архитектуры ЭВМ Сстатическая или динамическая) приводится классификация потоковых ВС и приведены основные представители того или иного класса ЭВМ УПД.

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

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

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

Целесообразно рассмотреть зависимость производительности потоковой ЭВМ от класса решаемых задач, а также сравнить ее с производительностью ЭВМ_ фон-неймановского типа.

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

с = е , т

1=0

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

Следует ожидать что значение С=1 является критическим при оценке производительности ЭВМ УПД, т.е. при С<1 производительность должна быть сравнительно небольшой, а при С>1 она должна возрасти. Необходимо более точно оценить степень влияния значения С на производительность, в том числе и при С=1.

В силу определения условия

I 4i = 1 С2Э

i=o

для выполнения неравенства С>1 должно выполняться

J (i-l)q, £ qn СЗ)

i—Z

или, обозначая Qj^qvqg, имеем

К = £ Ci-1)Q. £ 1. (4)

i=2

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

С - 1 = q0CK-lD. С5)

Заметим, что при К>1 имеем ЮС, а при К<1 выполняется неравенство К<С.

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

В потоковой ЭВМ с общим ресурсом командный блок С КБ), состоящий из М блоков памяти, посылает образованные токены через селекторную сеть С CCD в процессорный блок СПБ), состоящий из N процессоров. После обработки полученные данные передаются через распределительную сеть С PC) в КБ, либо выводятся из системы

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

Интерфейс "процессоры-блоки памяти" должен быть полнодоступным и в потоковых структурах с ЧДР,и с ЛДР, но в структуре с ЧДР селекторная сеть разделена на несколько сетей и связь блоков памяти с процессорами обеспечивается только в пределах подмножества в котором они состоят . Это дает значительное упрощение структуры селекторной сети, поскольку вместо одной сети, обеспечивающей МхЫ связей при ОР, потребуется п сетей обеспечивающих МхЫ/п2 связей Сп - количество подмножеств состоящих из блоков памяти и процессоров). Всего будут обеспечиваться МхЫ/п связей. Структура этих сетей более простая (при определенных условиях они могут быть полносвязными) и уменьшается время передачи информации через них. При ЛДР селекторная сеть вообще отсутствует и структура ЭВМ УПД может быть представлена в виде микропроцессоров с небольшой памятью (например, транспьютеров), соединенных между собой распределительной сетью.

При построении вероятностных моделей ЭВМ УПД различных структур в дальнейшем принимается ряд допущений:

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

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

- все операции являются одноместными, т.е. для активизации блока памяти из КБ необходим только один операнд.

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

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

ния вероятностных моделей для соответствующих структур связи.

Для случая слабой загрузки процессоров, т.е. когда время

работы процессоров намного меньше времени обработки информации в

блоках памяти Сд>А], модели трех рассмотренных структур ВС УПД Сс

общим ресурсом, с частично доступным ресурсом и с локально

доступным ресурсом) совпадают, и поэтому достаточно рассмотреть

одну модель. Будем считать, что полученный в ПБ результат может

использоваться максимум в трех последующих операциях (Ь=3), з

т.е. £ я = 1 . С учетом этого, определим среднее количество 1=0

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

Модель ЭВМ УПД при слабой загрузке процессоров описывается следующей системой уравнений ССУР]:

С1-д0-д1ЗР1 = 2ЧоР2 ,

¿=2 1=2,М-1

Ч0МРм =ЬЕсм-рр 2 д , с 6]

0 = 1 0 1=.}*1

где Р1 - вероятность нахождения модели с 1 активными БП. В результате решения СУР СБ), получаем:

[М/2] . М-2Л-1 . ,

Мер = Р £ СОд+Су1 С? , С7]

1 о=о 3 1=о 23 10

где [М/2] - целая часть от деления М/2.

г

Для случая, когда £ я = 1 СЬ = 23 выражение (73 принимает 1=0

вид:

О" - 1

Мер = - . С8)

" 1

При сильной загрузке процессоров вероятностная модель ЭВМ УПД с общим ресурсом описьюается следующей СУР:

С1-Я0-Ч1ЗР1 = 2Ч0Р2 ;

С1-я1Э1Р1 = I я ^0С1+1ЭР1М , 1=шШС1,М,

0=2 1=2,Ы ;

ЫС1-Ч1)РМ = | ' СШ

О—л

1=1,11-2; 1 =1, М-Ь+1;

Я0МРМ =ЬЁ1СМ^ЭР 2 Я, , 0=1 0 1=0+1

где Р - вероятность нахождения системы с I работающими процессорами при ¡гИ; при заняты все N процессоров, J

команд находятся в КБ готовые к выполнению.

Решая СУР С9) для И=3 , получаем среднее количество работающих процессоров:

[ (М+Ы-1 )/2] . М+М-2о-1

Ыср = Р. Е От Е СО^&р1 с^, . СЮ)

1 0=0 3 1=0 23 1 0

2

Для случая когда £ я = 1 СЬ = 2) выражение СЮ) принимает 1=0

ВИД:

0?н - 1

Мер = -. СИ)

0,-1

В модели ЭВМ УПД с ЧДР при сильной загрузке процессоров множество блоков памяти и процессоров разделено на два подмножества, в которых КБ выполняют роль буферной памяти с емкостью ш=М/2, в которой хранятся готовые к выполнению команды при отсутствии в соответствующем подмножестве свободных процессоров. Каждое из подмножеств содержит п=Ы/2 процессоров. Для случая когда я0+я1+я2 = 1 система описывается следующим основным уравнением:

[и+12-1/2П1+12)Ч1]Рп>12 = Чо[Ш+1)Рп..,.г + С12+13Р,1.1гм]

♦ чДмХИ+ПР^^ + 1/2С12+ПРи_1>1г+1] + С123

+ Я2[С1/4С 11-13 + 12/23Ри_1>12 + С1/4С12-1Э + П/гЭР^^ +

♦ 1/4П1+пр1тлг_г + ишг+пр^ы] ,

где Рп - вероятность нахождения системы с П и с 12 работающими процессорами в соответствующих подмножествах.

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

ЭВМ УПД с ЛДР при сильной загрузке процессоров описываются следующей системой уравнений СЬ=23:

Ь-ц. ¡1 -+ СЗ-1Э -1 |Р =

I- Ч М-1+1 М-1 «и 10

М-3+1 J-i+l

С1+1Э -Р1М , . + СЗ-1+23 -Р. . . . | +

гг СЗ-1+2ЭСЗ-1+1Э М-3+1 3-1 3-1+1 п

сг_-[ Гс 1-1Э-+ (3-1+13 —с — + --Лр, .

2Ч- СМ-1+2ЭСМ-1+1Э М-1+1 М-1 М-1+1 -1 1-1 •

СМ-3+2ЭСМ-3+1Э СЗ-1+2ЭСЗ-1+1)

+ С1+13 -5- Р + СЗ-1+ЗЭ -Р Н

)2 1 1 СМ-1+2ЭСМ-1+1Э 1 2-«1+1

СМ-1Э'

г . СЗ-1+23^-1+и м^п ^ц-х - ..

Ю-1-1Э - + 1 - С - + - Э Р. . Л ,

I- (М-1+23СМ-1+13 М-1+1 М-1 м-1+1 ■>

1=0,3, 3=0,м, 1+3*0 ,

где Р^ - вероятность нахождения моделируемой системы с 1 готовыми к выполнению командами в КБ и с 3 работающими процессорами.

Для данной модели также приведена цепь Маркова и граф ее переходов.

Как видно из главы 2, модифицированный граф переходов модели

+

+

ЭВМ УПД с ЧДР и граф переходов ЭВМ УПД с ЛДР совпадают , хотя индексы вероятностей имеют различный физический смысл. Для определения стационарных вероятностей этих моделей в работе предлагается рекуррентная процедура.

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

Одним из основных вьводов во второй главе является то, что граничные соотношения позволяют оценить производительность потоковой ЭВМ при К<Кт1п и при К>Кгах Сзначения Кт1п порядка 0,95, К „ - 1,05), а в интервале [К ,К ] их использование приводит

тпах 1 гп1 п ггаж

к большой погрешности. Интервал уменьшается по мере

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

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

структур потоковой ЭВМ при помощи их моделей предельной загрузки процессоров.

Стационарные вероятности модели ЭВМ УПД с ОР при произвольной загрузке процессоров Р^, где 1 - число активных блоков памяти и ] число процессоров, занятых обработкой информации, определяются следующим основным соотношением:

ПЛ+^Р1о = С^д^Р^ ^+и+ШР^ ^ , С14Э

которое соответствующим образом модифицируется на нижней и верхней границах изменения 1 и j с учетом физического функционирования системы. Во-первых, возможна блокировка работы блока памяти, вызванная невозможностью передачи токена на обработку в ПБ из-за отсутствия свободных процессоров; во-вторых, в рамках стационарной теории, рассматривается случай невырожденного протекания вычислительного процесса, когда число активных блоков памяти и работающих процессоров одновременно не равно нулю П+,)*03.

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

Для оценки производительности структур с ЧДР и с ЛДР также предлагаются вероятностные модели, которые ввиду их сложности здесь не приводятся.

Определение стационарных вероятностей модели ЭВМ УПД с ОР представляет определенные трудности. В работе предложена рекуррентная процедура, позволяющая их обойти.

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

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

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

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

увеличении числа процессоров производительность не меняется.

Несомненно, представленные в работе сравнительные данные по э<|фективности применения ЭВМ УПД и ЭВМ фон-неймановской архитектуры при своей конкретности должны рассматриваться только как качественные результаты, давшие право на жизнь ВС различных архитектур при решении соответствующих задач.

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

Модели ЭВМ УПД с ЛДР и с ЧДР при произвольной загрузке процессоров являются довольно сложными и при большом количестве компонент в системе их решение численными методами весьма затруднительно. Для этого случая была разработана универсальная имитационная модель потоковой ЭВМ Сона позволяет моделировать все рассматриваемые структуры) на языке СРЗБ/РС.

Имитационная модель позволяет определить среднее количество работающих процессоров и, таким образом, оценить производительность рассматриваемой системы. Кроме того, при имитационном моделировании появляется возможность рассмотреть и другие Снеэкс-поненциальные) законы распределения времени обработки информации в КБ и в ПБ, а также оценить влияние на производительность ЭВМ УПД временных задержек передачи токенов в коммуникациях. При разработке аналитических вероятностных моделей максимальное количество порожденных одним результатом токенов было ограничено тремя СЬ=3), а в некоторых случаях двумя. Имитационная модель позволяет снять это ограничение. При моделировании ЭВМ УПД с ЧДР количество подмножеств п, на которое разбиваются множества процессоров и командных блоков не ограничено С при аналитическом моделировании разработаны модели только для п=2).

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

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

чества процессоров и блоков памяти в системе, а также от пропускной способности коммуникационных сетей:

1. При определении эффективности структур УПД для реальной задачи необходимо разработать ее блок-диаграмму. Если рассматривается определенный класс задач. необходимо знать его статистические параметры 1=0,Ь.

2. Определить относительный коэффициент распараллеливания решаемой задачи К по методике, описанной в гл. 4. Если К<К или

^шт и ^тах определяются по графику при' заданном количестве процессоров в системе}, то необходимо применить граничныэ модели оценки эффективности структур УПД, а при КС1К ,К ] -модели потоковых структур при произвольной загрузке процессоров.

3. При КССК 4 ,К ] выбрать интересующую структуру УПД: при структуре с ОР использовать рекуррентную процедуру, описанную в гл. 3. При структурах с ЧДР и с ЛДР использовать имитационную модель.

4. При К<Кт1п или КЖ^ определить загрузку процессоров р как отношение быстродействия процессоров и блоков памяти.

5. При р< 1 для всех структур ЭВМ УПД использовать формулы, полученные для модели ЭВМ УПД при слабой загрузке процессоров.

6. При р>1 для структуры с ОР необходимо использовать формулы, полученные для модели ЭВМ УПД с ОР при сильной загрузке процессоров, для структур с ЧДР и с ЛДР используется рекуррентная процедура, описанная в гл. 2.

Необходимые исходные данные для моделирования структур ЭВМ

УПД:

1. Общее количество процессоров в моделируемой системе N.

2. Общее количество блоков памяти в моделируемой системе М.

3. Время выполнения операций в БП и в процессорах С или соответствующие параметры Лид).

4. Количество подмножеств на которые разбиты множества всех процессоров и блоков памяти Столько для структуры с ЧДР).

5. Параметры рабочей нагрузки: для статистического задания класса решаемых задач - вероятности 1=0,И ; для реальных задач - при использовании граничных моделей загрузки процессоров - частоты N , 1=0,Ь , 1*1 использования полученного в процессоре результата в 1 дальнейших операциях; при использовании моделей с произвольной загрузкой процессоров - еще и частоту N и общее количество операций в программе N ^ . .

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

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

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

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

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

- разработаны вероятностные модели структур ЭВМ УГШ при соизмеримых быстродействиях блоков памяти и процессорных элементов

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

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

- разработана универсальная имитационная модель для всех рассматриваемых структур ЭВМ УПД,

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

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

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

1. Г.Т.Артамонов, В. А. Морару, С. Л.Ротарь. Модели вычислений на сетях процессоров // Республиканская научно-техническая конференция, посвященная 25-летию образования КПИ им. С.Лазо. Тезисы докладов. - Кишинев, 1989. - с. 40.

2. О.М. Брехов, Е. Н. Климовец, Р. И. Завалко, В. А. Морару. Ана-литико-имитационное моделирование функционирования потоковых ВС <•/ Перспективы развития вычислительных систем. III Всесоюзный симпозиум. Тезисы докладов. - Рига, 1939. - с. 148.

3. О.М. Брехов, В. А. Морару. Аналитическая оценка функциони-

рования ВС, управляемых потоком данных // Математические методы исследования сетей связи и сетей ЭВМ. VI Белорусская зимняя школа-семинар по теории массового обслуживания. Тезисы докладов. - Минск, 1990. - с. 20-21.

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

1990. - с. 81-83.

5. О.М.Брехов, В.А. Морару. Оценка производительности потоковых структур статической архитектуры // III Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания. Тезисы докладов. - Москва, 1990. - с. 150-151.

В. О.М.Брехов, В.А.Морару. Граничные оценки производительности ЭВМ управляемых потоком данных //IV Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания. Тезисы докладов. - Москва, 1991. - с. 210-212.

7. Брехов О.М., Морару В.А. Влияние структуры и рабочей нагрузки потоковой ЭВМ на ее производительность // Всесоюзная конференция "Интеллектуальные системы". Тезисы докладов. - Туапсе,

1991.

8. Брехов О.М., Морару В.А. Методика задания рабочей нагрузки в моделях ЭВМ, управляемых потоком данных // Всесоюзная конференция по автоматизации проектирования РЭА и ЭВА. Тезисы докладов. - Пенза, 1991. - с. 97-99. 1

9. О.М.Брехов, Е.Н.Климовец, В. А. Морару. Моделирование потокового спецпроцессора для параллельной обработки данных //Однородные вычислительные среды и систолические структуры. I Всесоюзная конференция. Тезисы докладов. - Львов, 1990.- том 3, с.32-39.

10. В.А.Морару. Моделирование различных структур ЭВМ УПД // Деп. в ВИНИТИ 11 февраля 1991 г. , № 701-В91, 9 с.

И. В. А.Морару. Метод определения статических вероятностей модели ЭВМ УПД // Деп. в ВИНИТИ И февраля 1991 г., № 702-В91, 7 с.

12. В. А.Морару. Аналитическое вероятностное моделирование потоковой архитектуры БМПС // Отчет по НИР. Госрегистрация № У29948 - М. ; МАИ, июнь 1990 г. , п. 2.2.4, с. 131-137.

-•13. В. А. Морару.. Структура БМПС управляемых потоком данных // Отчет по НИР. Госрегистрация № У29948 - М.; МАИ, декабрь 1990 г., п. 2.4, с. 61-66.

ВВЕДЕНИЕ

ГЛАВА 1. АРХИТЕКТУРА СОВРЕМЕННЫХ ПОТОКОВЫХ

ВЬНИСЛИТЕЛЬНЫХ СТРУКТУР.

1.1 Место потоковых ЭВМ среди параллельных вычислительных машин.

1.2 Программирование ЭВМ управляемых потоком данных

1.2.1 Потоковые программы.

1.2.2 Языки программирования ЭВМ УПД

1.3 Архитектура ЭВМ УПД

1.3.1 Процессорньй элемент

1.3.2 Коммуникация

1.4 0<5зор существующих ЭВМ УПД.

1.4.1 Машины с непосредственной коммуникацией

1.4.2 Потоковые машины статической архитектуры с пакетной передачей

1.4.3 Машины с копированием кодов

1.4.4 Машины с тегированием токенов

1.4.5 Машины с одновременным использованием тегирования токенов и копирования кодов

1.5 Постановка задачи исследования производительности

ЭВМ УПД статической архитектуры

1.5.1 Основные параметры задач, решаемых на ЭВМ УПД.

1.5.2 Структуры потоковых ЭВМ статической архитектуры.

1.5.3 Постановка задачи

1.6 Выводы.

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

2.1 Исследование производительности потоковых машин при слабой загрузке процессоров

2.2 Исследование производительности потоковых машин при сильной загрузке процессоров

2.2.1 ЭВМ УПД с общим ресурсом СОР)

2.2.2 ЭВМ УПД с частично доступным ресурсом СЧДР)

2.2.3 ЭВМ УПД с локально доступным ресурсом (ЛДР)

2.3 Выводы.

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

3.1 Вероятностная модель ЭВМ УПД с общим ресурсом при произвольной загрузке процессоров

3.1.1 Методика определения стационарных вероятностей в модели потоковой ЭВМс~0Р

3.2 Анализ производительности ЗВМ УПД с ЧДР при произвольной загрузке процессоров

3.3 Анализ производительности ЭВМ УГЩ с ЛДР при произвольной загрузке процессоров.

3.4 Влияние пропускной способности сети на производительность потоковых структур.

3.5 Сравнительный анализ производительности потоковых структур и ЭВМ традиционной архитектуры

3.6 Выводы.

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

4.1 Методика определения параметров распараллеливания решаемой задачи

4.2 Программы аналитического и численного моделирования потоковых структур

4.3 Имитационное моделирование потоковых вычислительных структур

4.4 Методика оценки производительности структур управляемых потоком данных.

4.5 Выводы.

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

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

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

Ограничение, вносимое счетчиком команд, можно преодолеть в некоторых приложениях, в которых структуры данных, такие как массивы, являются естественными единицами, которыми можно оперировать, И тип данных "массив", и команды для манипулирования ими могут поддерживаться аппаратно. Декодирование одной команды обеспечивает выполнение операции над массивами, включая сюда накладные расходы на управление циклом. Производительность машины при выполнении векторных команд часто ограничивается только размером памяти, и компьютеры, основанные на таком подходе, являются достаточно удачными С например, компьютер Cray Х-МР [2Ш. Однако, могут быть векторизованы не все прикладные программы с параллелизмом, даже если они закодированы непосредственно с использованием векторных команд. Часть программного кода, которая может быть векторизована, колеблется от 10 до 90 процентов в зависимости от области приложений. В то время когда эффективность векторных команд увеличивается, невекторизуемый код имеет тенденцию становиться узким местом. Более сложно повысить производительность компьютера с векторными операциями, если исходный код написан на одном из языков высокого уровня и векторизация выполнена компилятором. Автоматическая векторизация требует сложного анализа потока данных, который затруднен в этих язьках из-за побочных эффектов, вызываемых глобальной областью действия и наложением переменных. Уменьшить некоторые из этих трудностей компилятора могут различные векторные расширения языков высокого уровня, но программирование при использовании этих расширений сложное, и результирующие программы являются машинно-зависимыми и негибкими.

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

Параллелизм обработки данных на всех уровнях организации вычислительного процесса Сот логического до системного), являющийся основным структурные резервом повыиения производительности, не « может бьггь реализован в рамках структуры машин фон-Неймана. Увеличение степени параллельности обработки путем модульного расширения системы дополнительным оборудованием Сдобавление новых ЭВМ, процессоров, блоков ввода-вывода), добавление к системе специализированных устройств, очень эффективных для определенного класса применений, максимальное использование параллельности, присутствующей в программах, применение конвейерной, матричной, ассоциативной организации вычислений, оптимизация обмена между - отдельными устройствами приводят к чрезмерному усложнению программирования и управления ЭВМ, что, в свою очередь, снижает их надежность и производительность. Добиться же значительного скачка в повыиении производительности ЭВМ на несколько порядков невозможно в рамках традиционной архитектуры [36]. Это подтверждается опытом разработки универсальных высокопроизводительных ЭВМ всех зарубежных фирм.

Для повыиения производительности современных ЭВМ исследуются и применяются новые архитектурные решения и перспективные методы параллельной обработки. Один из таких методов - управление вычислительным процессом потоком данных.

ЭВМ управляемые потоком данных (УГШ свободны от основных недостатков ВС фон-неймановской архитектуры (глобальная обновляемая память и единственный счетчик команд). Во-первых, потоковая модель имеет дело только со значениями, а не с адресами, содержащими значения. Эта концепция является основной также и для чисто функциональных или аппликативных языков, и, следовательно эти язьки не имеют заложенного в них понятия глобальной обновляемой памяти. Оператор в этих языках порождает значение, которое используется другими операторами. Во-вторых, потоковая модель не имеет ничего похожего на счетчик команд: команда активизируется тогда и только тогда, когда все требуемые входные значения будут вычислены. Активизированные команды потребляют входные значения, выполняют вычисление и порождают наборы выходных значений, которые посылаются другим командам, которым эти значения требуются. В потоке данных команда не имеет побочных эффектов, и язьки, основанные на концепциях потока данных, не вносят других ограничений на порядок выполнения вычислительного процесса, кроме ограничений, накладываемых зависимостями по данным, имеющимися в алгоритме. Таким образом, в принципе возможно выявить весь параллелизм потоковой программы.

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

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

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

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

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

В соответствии с поставленной задачей исследования проводились по следующим направлениям:

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

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

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

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

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

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

Научные результаты. В результате проведения исследований автором получены следующие результаты:

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

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

3. Разработана модель ЭВМ УПД с общим ресурсом при предельных случаях загрузки процессоров;

4. Разработана методика определения стационарных вероятностей для рассматриваемых моделей;

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

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

Практическую ценность представляют:

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

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на 8 Всесоюзных и республиканских конференциях и се-минаpax:

- Всесоюзный симпозиум "Перспективы развития вычислительных систем".- Рига, 1989

- Белорусская зимняя школа-семинар по теории массового обслуживания "Математические методы исследования сетей связи и сетей ЭВМ",- Минск, 1990

- Всесоюзное совещание по распределенные автоматизированным системам массового обслуживания. - Москва, 1990

- Всесоюзное совещание по распределение автоматизированным системам массового обслуживания. - Москва, 1991

- Всесоюзная конференция "Однородные вычислительные среды и систолические структуры".- Львов, 1990

- Республиканская научно-техническая конференция, посвященная 23-летию образования КПИ им. С.Лазо. - Кишинев, 1989

- Научно-техническая конференция "Автоматизация проектирования РЭА и ЭВА". - Пенза, 1991

- Всесоюзная конференция "Интеллектуальные системы". Туапсе, 1991.

Публикации. Основные положения и результаты диссертационной работы опубликованы в 13 печатных работах, г Структура диссертационной работы. Диссертация состоит из введения, четьрех глав, списка литературы С101 наименование) и приложения. Объем работы - 161 страница, 51 рисунков, 3 таблицы.

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

1. Разработана методика оценки параметров распараллеливания задач, решаемых в потоковом режиме.

2. Произведена оценка влияния пропускной способности сети на производительность многопроцессорных потоковых ЭВМ.

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

4. Разработаны вероятностные модели структур ЭВМ УПД при соизмеримых быстродействиях блоков памяти и процессорных элементов.

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

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

7. Разработана универсальная имитационная модель для всех рассматриваемых структур ЭВМ УПД.

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

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

1. Альянах И.Н. Моделирование вычислительных систем. Л.: Машиностроение, 1988. - 223 с.

2. Артамонов Г.Т. Топология регулярных вычислительных сетей и сред. М.: Радио и связь, 1985. - 192 с.

3. Артамонов Г.Т., Брехов 0. М. Аналитические вероятностные модели функционирования ЭВМ. М., Энергия, 1978. - 368 с.

4. Артамонов Г.Т., Морару В.А., Ротарь С.Л. Модели вычислений на сетях процессоров // Республиканская научно-техническая конференция, посвященная 25-летию образования КПИ им. С.Лазо. Тезисы докладов. Кишинев, 1989. - с. 40.

5. Артамонов Г.Т., Тюрин В.Д. Топология сетей ЭВМ и многопроцессорных систем. М.: Радио и связь, 1991. - 248 с.

6. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. М.: Радио и связь, 1990.- 256 с.

7. Барский А.Б.Потоковая обработка информации в ВС наасинхронном решающем поле // Вопросы кибернетики. Проблемы организации высокопроизводительных ЭВМ / НС по комплексной проблеме "Кибернетика" АН СССР. М., 1984. - с. 119-141.

8. Башарин Г. П. , Толмачев А.Л. Теория сетей массового обслуживания и ее приложения к анализу информационно-вычислительных систем // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. М., 1983. - с. 3-119.

9. Байцер Б. Архитектура вычислительных комплексов: В 2-х томах. Пер. с англ. М.: Мир, 1974.

10. Белецкий В.Н. Многопроцессорные и параллельные структуры с организацией асинхронных вычислений. Киев: Наук, думка, 1988.- 240 с.

11. И. Белецкий В.Н. , Ронто В. А. , Крапивка В.Н. Организация и моделирование потоковых ЭВМ // Институт проблем моделирования в энергетике АН УССР: Препринт, 1989. N 1. - с. 1-43.

12. Брехов О.М., Климовец Е. Н., Завалко Р. И. , Морару В. А. Аналитико-имитационное моделирование функционирования потоковых ВС // Перспективы развития вычислительных систем. III Всесоюзный симпозиум. Тезисы докладов. Рига, 1989. - с. 148.

13. Брехов О.М. , Климовец Е.Н. , Морару В.А. Моделирование потокового спецпроцессора для параллельной обработки данных // Однородные вычислительные среды и систолические структуры. I Всесоюзная конференция. Тезисы докладов. Львов, 1990. - том 3, с. 32-39.

14. Брехов 0. М. > Морару В.А. Граничные оценки производительности ЭВМ управляемых потоком данных //IV Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания. Тезисы докладов. Москва, 1991. - с. 210-212.

15. Брехов 0. М. , Морару В.А. Оценка производительности потоковых структур статической архитектуры //III Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания. Тезисы докладов. Москва, 1990. - с. 150-151.

16. Брехов О.М., Морару В.А. Влияние структуры и рабочей нагрузки потоковой ЭВМ на ее производительность // Всесоюзная конференция "Интеллектуальные системы". Тезисы докладов. Туапсе, 1991.

17. Брехов 0. М., Морару В.А. Методика задания рабочей нагрузки в моделях ЭВМ, управляемых потоком данных // Всесоюзная конференция по автоматизации проектирования РЭА и ЭВА. Тезисы докладов. Пенза, 1991. - с. 97-99.

18. Бурцев В.С. Тенденция развития супер-ЭВМ ✓✓ Отдел вычислительной математики АН СССР: Препринт, 1989. N 241. - с. 1-30.

19. Вальковский В. А. Распараллеливание алгоритмов и программ. Структурный подход. М.: Радио и связь, 1989. - 176 с.

20. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы супер-ЭВМ: Пер. с англ./ Под ред. Я.Ковалика. М.: Радио и связь, 1988. - 432 с.

21. Вычислительная техника за рубежом в 1980 году // Под ред. В.С.Бурцева / ИТМ и ВТ АН СССР. Москва, 1981. - 277 с.

22. Головкин Б.А. Параллельные вычислительные системы. М.: Наука, Главная редакция физико-математической литературы, 1980. -519 с.

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

24. ГОСТ 16325-88. Машины вычислительные электронные общего назначения. Общие технические требования.

25. Данильченко А. В. Модели и методы приближенного анализа производительности информационно-вычислительных систем на основе замкнутых сетей массового обслуживания / Автореф. Дис. канд. техн. наук. JI.: ЛИТМО, 1986.

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

27. Евреинов Э.В., Хорошевский В.Г. Однородные вычислительные системы. Новосибирск: Наука, 1978. - 320 с.

28. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь, 1988. - 192 с.

29. Игнатущенко В.В. Организация структур управляющих многопроцессорных вычислительных систем. М.: Энергоатомиздат, 1989. -182 с.

30. Клейнрок Л. Вычислительные системы с очередями. Пер. с англ. М.: Мир, 1979. - 600 с.

31. Клейнрок Л. Коммуникационные сети, стохастические потоки и задержки сообщений. М.: Наука, 1970.

32. Клейнрок Л. Принципы и уроки пакетной связи //ТИИЭР. Пер. с англ., 1978. т. 66. - N 11. - с. 30-42.

33. Крэйн М., Лемуан 0. Введение в регенеративный метод анализа моделей. Пер. с англ. М.: Наука, 1982. - 104 с.

34. Мартин Дж. Вычислительные сети и распределенная обработка данных: программное обеспечение, методы и архитектура. Вып. 1 -М.: Финансы и статистика, 1985. - 256 с.

35. Майерс Г. Архитектура современных ЭВМ: В 2-х кн. Пер. с англ. М.: Мир, 1985.

36. Мищенко В.А., Лазаревич Э.Г., Аксенов А. И. Расчет производительности многопроцессорных вычислительных систем. Мн.: Вып. шк. , 1985. - 208 с.

37. Морару В.А. Аналитическое вероятностное моделирование потоковой архитектуры БМПС // Отчет по НИР. Госрегистрация N У29948 М.; МАИ, июнь 1990 г., п. 2.2.4, с. 131-137.

38. Морару В.А. Вероятностная модель ЭВМ, управляемой потоком данных // Информационное и программное обеспечение автоматизированных систем. Межвузовский сборник научных трудов. Рязань, 1990. - с. 81-85.

39. Морару В. А. Метод определения статических вероятностей модели ЭВМ УПД // Деп. в ВИНИТИ 11 февраля 1991 г., № 702-В91, 7с.

40. Морару В.А. Моделирование различных структур ЭВМ УПД // Деп. в ВИНИТИ 11 февраля 1991 г., № 701-В91, 9с.

41. Морару В.А. Структура БМПС управляемых потоком данных // Отчет по НИР. Госрегистрация N У29948 М.; МАИ, декабрь 1990 г., п. 2.4, с. 61-66.

42. Морисита И. Аппаратные средства микро-ЭВМ. Пер с япон. -М.: Мир, 1988. 280 с.

43. Мотоока Т. , Томита С., Танака X., Сайто Т., Узтхара Т. Компьютеры на СВИС: В 2-х кн. М.: Мир, 1988.

44. Мультипроцессорные системы и параллельные вычисления / Под ред. Ф.Г.Энслоу: Пер. с англ. М.: Мир, 1976. - 383 с.

45. Прангишвили И.В. Микропроцессоры и локальные сети мик-ро-ЭВМ в распределенных системах управления. М.: Знергоатомиз-дат, 1985. - 272 с.

46. Прангишвили И. В. , Стецюра Г. Г. Микропроцессорные системы. М.: Наука, 1980. - 225 с.

47. Саати T.JI. Элементы теории массового обслуживания и ее применение. М.: Советское радио, 1971. - 520 с.

48. Самофалов К. Г. , Луцкий Г.М. Основы теории многоуровневых конвейерных вычислительных систем. М.: Радио и связь, 1989. -272 с.

49. Системы параллельной обработки / Под ред. Д.Ивенса; Пер. с англ. под ред. Ю. Г. Дадаева. М.: Мир, 1985. - 416 с.

50. Тербер К. Л. Архитектура высокопроизводительных вычислительных систем: Пер. с англ. М.: Наука, 1985. - 272 с.

51. Торгашев В. А. Управление вычислительным процессом и машины с динамической архитектурой // Вычислительные системы и методы автоматизации исследований и управления. М., Наука, 1982.с. 172-187.

52. Торгашев В. А. , Плюснин В. У. Процессоры с динамической архитектурой. // Электрониз. нар. х-ва., N 1-2, с. 27-36, М., 1989.

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

54. Фрир Лж. Построение вычислительных систем на базе перспективных микропроцессоров: Пер. с англ. М.: Мир, 1990. -413 с.

55. Хокни Р., Джессхоуп К. Параллельные ЭВМ. Архитектура, программирование и алгоритмы: Пер. с англ. М.: Радио и связь,1986. 392 с.

56. Хорошевский В.Г. Инженерный анализ функционирования вычислительных машин и систем. М.: Радио и связь, 1987. - 256 с.

57. Шеннон Р. Имитационное моделирование систем искусство и наука. - М.: Мир, 1978. - 418 с.

58. Шилов В.В. Имитационная модель потоковой вычислительной системы. // Вопросы кибернетики. Разработка и использование супер-ЭВМ / НС по комплексной программе "Кибернетика" АН СССР.- М.,1987. с. 145-162.

59. Шпаковский Г. И. Архитектура параллельных ЭВМ: Учеб. пособие для вузов. Мн.: Университетское, 1989. - 192 с.

60. Шрайбер Т.Дж. Моделирование на GPSS. М.: Машиностроение, 1980. - 592 с.

61. ЭВМ пятого поколения. Концепции, проблемы, перспективы / Под ред. Т.Мотоока; Пер. с англ. под ред. А.А.Рывкина, В.М.Савинкова. М.: Финансы и статистика, 1984. - 112 с.

62. Amamiya М., Takesue М., Hasegawa R. , Mikami Н. Implementation and evaluation of a list-processing-oriented data flow machine. Proceedings of the 13th Annual Symposium on Computer architecture (Tokyo, June 2-5). ASM, New York, pp. 10-19, 1986.

63. Arvind, Gostelow K. A computer capable of exchanging processors for time. Information Processing 77, Ed. North-Holland, New York, pp. 849-853, 1977.

64. Arvind, Kathali V. A multiple processor dataflow machine that supports generalized procedures. Proceedings of the 8th Annual Symposium on Computer Architecture (Minneapolis, Minn., May 12-14). ACM, New York, pp. 291-302, 1981.

65. Bic L., Gaudiot J-L. Special issue on data-flow computing. Parallel and Distrib. Comput., pp. 277-278, 1990.

66. Burkowski F.J. A multi-user data flow architecture. Proceedings of the 8th Annual Symposium on Computer Architecture (Minneapolis, Minn., May 12-14). ACM, New York, pp. 327-340, 1981.

67. Comte D. , Hifdi N., Syre J.C. The data driven LAUmultiprocessor system: Results and perspectives. Proceedings of the IFIP Congress 80 (Tokyo and Melbourne, Australia, Oct. 6-17), S.Lavington, Ed. North-Hoiiand, Amsterdam, pp. 175-180, 1980.

68. Cornish M., et al. The TI data flow architectures: The power of concurrency for avionics. Proceedings of the 3rd Conference on Digital Avionics Systems (Fort. Worth, Tex., Nov.), IEEE, New York, pp. 19-25, 1979.

69. Chin C.J., Hwang K. Packet Switching Networks for Multiprocessors and Data Flow Computers, IEEE Transactions on computers, vol. С-33, pp. 991-1003, Nov. 1984.

70. Davis A.L. Architecture of DDM1: A recursively structured data driven machine. Tech. Rep., Dept. of Computer Science, Univ. of Utah, Salt Lake City, Utah, 1977.

71. Davis A.L. A data flow evaluation systems based on the concept of recursive locality. Proceedings of the National Computing Conference. AFIPS Press, Reston, Va., pp. 1079-1086, 1979.

72. Dennis J.B. First version of a data flow procedure language. Lecture Notes in Computer Science, vol. 19, G.Goos and J.Hartmanis, Eds. Springer, New York, pp. 362-376, 1974.

73. Dennis J.B., Misunas R.P. A preliminary architecture for a basic data flow processor. Proceedings of the 2nd Annual Symposium on Computer Architecture (Houston, Tex., Jan. 12-14). Comput. Archit. News 3,4, pp. 126-132, 1974.

74. Dennis J.B. , Lim W.Y.P, Ackerman W.B. The MIT data flow engineering. Proceedings of the IFIP 9th World Computer Congress (Paris, Sept. 19-23), R. E. A. Mason, Ed. North-Holland, New York, pp. 553-560, 1983.

75. Dennis J.B. , Gao G.R., Todd K.W. Modeling the weather with a data flow supercomputer. IEEE Trans. Comput., C-21, No 7,pp. 392-603, Sept. 1984.

76. Duncan R. A Survey of Parallel Computer Arcitectures. -Computer, vol. 23, No 2, pp. 3-16, Feb. 1990.

77. Flynn M.J. Some computer organizations and their effectiveness. IEEE Trans. Comput., C-21, No 9, pp. 948-960, Sept. 1972.

78. Ghosal Dipak, Bhuyan Laxmi N. Performance Evaluation of a Dataflow Architecture. IEEE Tranzactions on computers, vol. С-39, No. 5, pp. 615-627, May 1990.

79. Gostelow K.P., Thomas R. E. Performance of simulated dataflow computer. IEEE Tranzactions on computers, C-29, No 10, pp. 905-919, Oct. 1980.

80. Gurd J.R., Watson I. A data driven system for high speed parallel computing. Comput. Design 19, Part I, No 6, pp. 91-100, Jun. 1980, Part II, No 7, pp. 97-106, Jul 1980.

81. Gurd J.R. , Watson I., Kirkham C.C. The Manchester prototype dataflow computer. Commun. ACM. vol. 28, pp. 34-52, Jan. 1985.

82. Hahn W. Perspectives of data-flow Architectures. Ann. Oper. Res., vol. 16, No 1-4, pp. 281-298, 1988.

83. Hudak P. , Goldberg B. Distributed execution of functional programs using serial combinators. IEEE Trans. Coput., C-34, No 10, pp. 881-891, Oct. 1985.

84. Iwashita M., Temma T., Matsumoto K. , Kurokawa H. Modular dataflow image processor. Spring 83 C0MPC0N. IEEE, New York, pp. 464-467, 1983.

85. Jeffery T. The |uPD7281 Processor. Byte, pp. 237-246, Nov. 1985.

86. Johnson D. and al. Automatic partitioning of programs in multiprocessor systems. Proceedings of the Spring 80 C0MPC0N.1.EE, New York, 1980.

87. Marczynski M.P., Milewski J. A data driven system based on a micropropgrammed processor module. Proceedings of the 10th Annual Symposium on Computer Architecture (Stockholm, June 13-173, IEEE, New York, pp. 98-106, 1983.

88. Miranker G.S. Implementation of procedures on a class of a data flow processors. Proceedings of the 1977 International Conference on Parallel Processing (Detroit, Mich., Aug. 23-263, J.L.Baer, Ed. IEEE, New York, pp. 77-86, 1977.

89. Rumbaugh J. A data flow multiprocessor. Proceedings of the 1975 Sagamore Computer Conference on Parallel Processing (Sagamore, N.Y.), pp. 220-223, 1975.

90. Shirazi B., Hurson A.R. A data driven multiprocessor -its architecture and performance evaluation. Multiprocess, and Microprogr., vol. 26, No 2, pp. 97-112, 1989.

91. Smith B.J. A pipelined shared resource MIMD computer.-Proceedings of the 1978 International Conference on Parallel Processing. IEEE, New York, 1978.

92. Srini V.P. An architectural comparison of dataflow systems. Computer 19, No 9, pp. 68-88, Mar. 1986.

93. Swan R.J., Fuller S.N. , Siewiorek D.P. Cm* A modular, multi-microprocessor. - Proceedings of the National Computer Conference (Dallas, Tex., June 13-16) AFIPS Press, Arlington, Va., pp. 637-644, 1977.

94. Takahashi N., Amamiya M. A data flow processor arraysystem; Design and analysis. Proceedings of the 10th Annual Symposium on Computer Architecture (Stockholm, June 13-173, IEEE, New York, pp. 243-250, 1983.

95. Vedder R., Finn D. The Hughes data flow multiprocessor: Architecture for efficient signal and data processing. Proceedings of the 12th Annual Symposium on Computer Architecture (Boston, Mass., June 17-19), IEEE, New York, pp. 324-332, 1985.

96. Veen A.H. Dataflow Machine Architecture. ACM Computing Surveys, Vol. 18, No 4, Dec. 1986, pp. 365-396.