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

ВВЕДЕНИЕ.

ГЛАВА 1. Анализ высокопроизводительных архитектур.

1.1 Конвейерные и векторные ВС.

1.2 Матричные и ассоциативные ВС.

1.3 Принцип макроконвейера.

1.3.1 Макроконвейерные сети.

1.3.2 Проектирование распределенных программ.

1.4 Языки параллельного программирования.

1.5 Специализированные геометрические структуры.

1.6 Структура параллельного коммуникационного контроллера.

Выводы по 1 -ой главе.

ГЛАВА 2. Методы и модели распараллеливания вычислительного процесса.

2.1 Модели параллельных вычислений.

2.2 Сети Петри и их свойства.

2.3 Языки сетей Петри.

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

2.3.2 Свойства классов языков сетей Петри.

2.4 Ординарные сети Петри.

2.5 Счетчиковые автоматы.

2.6 Ингибиторные сети и сети с приоритетами.

2.7 Раскрашенные, синхронные и самомодифицируемые сети.

2.8 Алгебра регулярных сетей.

2.9 Модифицированная параметрическая СП.

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

ГЛАВА 3 Конвейеризация и параллельные подстановки - как методы распараллеливания микропрограмм.

3.1 Метод параллельных подстановок.

3.2 Анализ функционирования конвейера.

3.2.1 Анализ функционирования статического конвейера.

3.2.1.1 Определение таблицы занятости по циклу.

3.2.1.2 Задержка - как способ повышения производительности.

3.2.2 Конвейеры с динамической конфигурацией.

3.2.2.1 Анализ динамического конвейера.

3.2.3 Управление инициациями.

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

ГЛАВА 4 Практическая реализация.

4.1 Назначение ПТД.

4.2 Принципы работы и структура ПТД.

4.3 Применение конвейерной и параллельной обработки в связных контроллерах.

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

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

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

Сейчас можно выделить ряд основных тенденций в области создания высокопроизводительных систем, в частности: 1) разработка программного обеспечения, имеющего значительную степень параллелизма; 2) разработка специализированных систем, ориентированных на эффективное применение в той или иной области, на базе МП или МаБИС; 3) программное обеспечение все теснее увязывается с аппаратурой, например, с перепрограммируемыми постоянными запоминающими устройствами (ПЗУ), чем обеспечивается быстрый переход от одной системы команд к другой. 5

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

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

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

С точки зрения внутренней структуры многопроцессорные вычислители делятся на однородные и неоднородные [3]. Однородные вычислители состоят из 6 идентичных процессоров, каждый из которых может выполнять независимо от других определенное множество комацд. Неоднородный вычислитель состоит из различных процессоров, часто специализированных для решения отдельных типов задач (например, процессор для реализации операционной системы, для распознавания образов, арифметических расчетов, быстрого преобразования Фурье, сортировки и т.д.).

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

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

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

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

Проблемы М1МТ)-машин, существенно отличаются от проблем машин с параллельными процессорами (81МТ)- и М18Б-машин), и они ориентированы на решение более широкого круга задач. Алгоритм, разработанный для 81МО-машин не обязательно эффективен при его использовании на МИУГО-машине, и наоборот. Важной проблемой для достижения высокой эффективности многопроцессорных ВС является решение проблемы синхронизации независимо работающих процессоров и проблемы распределения фрагментов задач между ними. Для некоторых типов многопроцессорных ВС основная проблема состоит в структурной организации коммутации процессоров, модулей памяти и каналов ввода-вывода.

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

Исследование и разработка алгоритмов для многопроцессорных машин на сегодняшний день отстают от разработки алгоритмов для машин типа 81МТ).

Параллельные алгоритмы для МИУГО-машин представляют собой совокупность параллельных процессов, которые при решении данной задачи могут протекать одновременно. Процесс может быть выполнен любым процессором, который был выделен для него операционной системой. Каждый процесс имеет 8 точки, в которых он может быть связан с другими процессами. Точки делят процесс на такты. Продолжительность такта, а, следовательно, и всего процесса, как правило, случайна и зависит от ряда причин.

Отметим главные проблемы параллельных вычислительных машин и перспективы их развития.

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

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

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

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

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

Программы с итеративной структурой в большей степени пригодны для БИУЮ-машин, чем для машин типа МШГО, в которых они реализуются с недостаточной эффективностью из-за наличия синхронизации и диспетчирования. Классические численные алгоритмы более пригодны для машин БШХ). Было показано [25], что некоторые вычисления могут быть выполнены без синхронизации, и их можно эффективно выполнять на многопроцессорных ВС асинхронным способом. "Ручное" распараллеливание алгоритмов и программ для ВС с небольшим числом процессоров не представляет сложности. Однако равномерная загрузка (в рамках одной задачи) машины типа М1МБ с 16-32 процессорами является уже достаточно трудной задачей. Практические методы разработки параллельных программ для многопроцессорных машин типа М1МБ в настоящее время еще не развиты.

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

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

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

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

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

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

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

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

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

Выводы по 4-ой главе:

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

124 югофункциональный конвейер с динамической конфигурацией с возможностью 1раллельной обработки.

Рис.4.3

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

В случае отсутствия ограничений на объём оборудования для достижения лсокой производительности при приемлемой стоимости можно использовать □биение вычислительного процесса (задачи) на подпроцессы и параллельное их »шолнение, конвейеризацию и распараллеливание, как на макро- так и на икроуровнях с различной степенью глубины. Таким образом, приходится идти на

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

Целью экспериментальной части работы была разработка опытного образца ЦУ с использованием параллельной обработки и его отладка, что дало возможность эедиться в работоспособности заложенных в него идей. Выполнена аппаратная зализация БЦУ ПТД на базе разработанных методов, позволившая повысить роизводительность в 3.5-4 раза. Ряд технических решений защищены авторскими зидетельствами. Результаты проведенных исследований использованы в азработанном и доведенном до уровня опытного образца устройстве, прошедшем олную программу тестирования и испытаний (приложение 1).

Разработаны и отлажены программы на IBM PC, выполняющие редварительный анализ степени параллельности программ и конвейеризации команд пи микрокоманд, которые позволяют инженеру быстро оценить структуру тгоритма обработки информации (приложение 2). Данные программы могут быть ключены в состав пакета САПР, реализующего всю цепь разработки спецпроцессора 1нализ алгоритма, оценка производительности, коррекция алгоритма и т.д.), вплоть э выпуска СБИС или вычислительной системы.

Разработанный опытный образец выполнен с использованием многослойных и вухслойных плат, внешний вид которого приводится на фотографии (рис.4.3). 'тладка макета производилась с использованием в качестве инструментального эедства отладки ПЭВМ IBM PC.

126

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

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

ЗАКЛЮЧЕНИЕ

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

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

Развиты теоретические основы метода параллельных подстановок с целью ^ределения множества непересекающихся подстановок. Даны определения ножества непересекающихся подстановок и качества подстановки - как критерия

127

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

На базе разработанного алгоритма анализа вычислительного процесса на степень фаллелизма (с учетом момента вхождения в вычислительный процесс) написаны юграммы анализа граф-схемы алгоритма на степень параллелизма и глубину швейеризации, которые могут быть использованы как на макро- , так и на якроуровне. Данные программы могут быть включены в состав пакета САПР, ¡ализующего всю цепь разработки спецпроцессора (анализ алгоритма, оценка юизводительности, коррекция алгоритма и т.д.), вплоть до выпуска СБИС или ,1Числительной системы.

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

Выполнена аппаратная реализация БЦУ ПТД на базе разработанных методов, «водившая повысить производительность в 3.5-4 раза. Ряд технических решений щищены авторскими свидетельствами. Результаты проведенных исследований :пользованы в разработанном и доведенном до уровня опытного образца устройстве, юшедшем полную программу тестирования и испытаний.

128

1. Авен О.И., Турин H.H., Коган Я.А. Оценка качества и оптимизация вычислительных систем.- М.:Наука, 1982,- 464 с.

2. Алексеев Г.И., Мыльников С.П. Программная реализация Петри-машины. В кн.; Многопроцессорные вычислительные системы и их математическое обеспечение. Новосибирск: Изд. ВЦ СО АН СССР, 1982, с. 94 103с.

3. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем/Под. ред. А.П.Ершова.- М., Наука, 1982-ЗЗбс.

4. Анишев O.A., Ачасова С.М., Бандман О.Л, и др. Методы параллельного микропрограммирования. Новосибирск: Наука, 1981.

5. Астаповский А.Г., Варшавский В.И., Мараховский В.Б. и др, Апериодические автоматы. М.: Наука, 1976.

6. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

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

8. Барский А.Б. Планирование параллельных вычислительных процессов.-М.: Машиностроение, 1980. 192с.

9. Басакер Р., Саати Т. Конечные графы и сети: Пер. с англ.-М.:Наука, 1974.- 366 с.

10. Берне, Браун, Като, Кук, Слотник, Стоке. Многопроцессорная вычислительная система ИЛЛИАК-4: Пер. с англ. Зарубежная радиоэлектроника, 1972, N 5, с. 53 -67.

11. П.Быстров A.B., Дудоров H.H., Котов В.Е. 0 базовом языке. В кн.: Языки и системы программирования. Новосибирск: Изд-во ВЦ СО АН СССР, 1979,с. 85-106.

12. Вальковский В. А. Параллельное выполнение циклов. Метод параллелепипедов//Кибернетика,- 1982.- №2.-с.51-62.

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

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

15. Вентцель Е.С. Исследование операций. .- М.: Сов. радио, 1972. 551с.

16. Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1970.

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

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

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

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

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

22. Каляев A.B. Организация многопроцессорных систем на принципах потока данных и программирования архитектуры//Высокопроизводительные вычислительные системы: Тез. докл. 2-го Всесоюз. совещания.-Батуми, 1984.-е. 1920.

23. Каляев A.B. Многопроцессорные вычислительные системы с программируемой архитектурой.- М.: Радио и связь, 1984,- 240 с.

24. Капитонова Ю.В., Летичевский A.A. Математическая теория проектирования вычислительных систем. М.: Наука, 1988,- 296с.

25. Карп P.M., Миллер P.E. Параллельные схемы программ. В кн.; Кибернетический сборник. Вып. 13 (новая серия), М.: Мир, 1976, с. 5 - 61.

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

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

28. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы: Пер. с англ. М.: Мир, 1976. - 736 с.130

29. Кнут Д . Искусство программирования для ЭВМ. Т.З. Сортировка и поиск: Пер. с англ. М.: Мир, 1978. - 846 с.

30. Котов В.Е. Параллельное программирование с типами управления. Кибернетика, 1979, N3, с. 1-13.

31. Котов В.Е. Алгебра регулярных сетей. Кибернетика, 1980, N 5, с. 10-18.

32. Котов В.Е., Черкасова JI.A. Структурированные сети. Кибернетика, 1981, N 4, с. 33-41.

33. Котов В.Е., Черкасова JI.A. Некоторые критерии структурированности в классе ациклических сетей. В кн.: Многопроцессорные вычислительные системы и их математическое обеспечение. Новосибирск: Изд. ВЦ СО АН СССР, 1982, с.71-83.

34. Котов В.Е. Сети Петри,- М.: Наука, 1984,- 160 с.

35. Коуги П. Архитектура конвейерных ЭВМ: Пер. с англ.- М.: Радио и связь, 1985. 360с.

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

37. Минский М. Вычисления и автоматы. М.: Мир, 1971.

38. ЗБ.Михалевич B.C., Капитонова Ю.В., Летичевский A.A., Молчанов И.Н., Погребинский С.Б. Организация вычислений в многопроцессорных вычислительных системах//Кибернетика, 1984.-№3 с. 1-10.

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

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

41. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Микропроцессорные вычислительные системы с единым потоком команд. М.: Энергоатомиздат, 1983. -311с.

42. Проектирование сверхбыстродействующих систем. Комплекс СТРЕТЧ/Под ред. В. Бухгольца: Сокращ. Пер. с англ. М.: Мир, 1965. - 348 с.131

43. Роджерс С. Теория рекурсивных функций и эффективная вычислимость. М,-Мир, 1972, 624 с.

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

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

46. Таль A.A., Юдицкий С.А. Иерархия и параллелизм в сетях Петри. Сложные автоматные сети Петри с параллелизмом.-Автоматика и телемеханика, 1982, N9,с.83.

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

48. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции,- М.: Наука, 1981.- 254с.

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

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

51. Флинн М. Сверхбыстродействующие вычислительные системы. ТИИЭР, 1966,. 54, N12, с. 311 - 320.

52. Флинн М., Амдал Г. Технические аспекты разработки большой сверхбыстродействующей вычислительной машины. В кн.: Микроэлектроника и большие системы: Пер. с англ. - М.: Мир, 1967, с.58-78.

53. Хассон С. Микропрограммное управление: Пер. с англ. М.: Мир, 1973. - Т.1. -224 е., Т.2. - 477 с.

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

55. Черкасова Л.А. Об отношении параллельности и КА-плотности в ациклических сетях. В кн. - Параллельные вычислительные и программные системы. Новосибирск: Изд-во ВЦ СО АН СССР, 1981, с. 13 - 28.

56. Элементы параллельного программирования/ Вальковский В.А., Котов В.Е., Марчук А.Г., Миренков H.H.; Под ред. В.Е. Котова.- М.: Радио и связь, 1983. 240с.132

57. Яненко Н.Н. Эффективность алгоритмов и принципы их декомпозиции для современных ЭВМ//Комплексы программ математической физики,- Новосибирск, 1984,- с.3-17.

58. Kotov V.E. An algebra for parallelism based on Petri nets. In: Lecture Notes in Computer Science. Berlin: Springer-Verlag, 1978, 64, p. 39-55.

59. Cray Research Inc. 1976. CRA Y -1 Computer System, No. 2240004, Cray Research1.c., Bloomington, Minn.

60. Control Data Corp. 1975. Control Data STAR-100 Computer Hardware Reference Manual, Publication No. 60256000, Control Data Corp., Minneapolis.

61. Tony Brewer and Greg Astfalk. The evolution of the HP/Con-vex Exemplar. In Proceedings of COMPCON Spring '97: Forty-Second IEEE Computer Society International Confer-ence, pages 81-86, February 1997.

62. Asgeir Th. Eiriksson and Ken L. McMillan, Using formal ver-ification/analysis methods on the critical path in system de-sign: A case study. In Proceedings of Computer Aided Verification Conference, Liege Belgium, LNCS 939, Springer Verlag, 1995.

63. Mike Galles. Scalable Pipelined Interconnect for Distributed Endpoint Routing: The SGI SPIDER chip. In Hot Intercon-nects '96.

64. Daniel Lenoski, James Laudon, Kourosh Gharachorloo, Anoop Gupta, and John Hennessy. The directory-based cache coherence protocol for the DASH multiprocessor. In133

65. Proceed-ings of the 17th Annual International Symposium on Comput-er Architecture, pages 148-159, May 1990.

66. Тахаутдинов B.C., Осипов C.H. Метод параллельного микропрограммирования. Тезисы докладов Юбилейной научно-технической конференцииКГТУ.Казань, 1994.

67. Tom Lovett and Russell Clapp, STiNG: A CC-NUMA computer system for the commercial marketplace. In Proceedings of the 23rd Annual International Symposium on Computer Architecture, pages 308-317, May 1996.

68. Steven K. Reinhardt, James R. Larus, and David A. Wood. Tempest and Typhoon: User-level shared memory. In Pro-ceedings of the 21st Annual International Symposium on Computer Architecture, pages 325-336, .April 1994.

69. Mendel Rosenblum, John Chapin, Dan Teodosiu, Scott De-vine, Tirthankar Lahiri, and Anoop Gupta. Implementing effi-cient fault containment for multiprocessors. Communications of the ACM, 39(3):52-61, September, 1996.

70. Wolf-Dietrich Weber, Scalable Directories for Cache-Coherent Shared-Memory Multiprocessors. Ph.D.thesis, Stanford University, Stanford, California, January 1993.

71. Kenneth Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, 16(2):28-40, April, 1996.

72. Dijkstra E.W Cooperating sequential processes. In: Programming Languages. New York: Academic Press, 1968, p. 43 - 112.

73. Petri C.A. Kommunikstion mit Automaten.- Technische Hochschule Darmstadt, 1962.

74. Hack M. Decision problems for Petri nets and vector addition systems. Project MAC Memo 59. Cambridge, 1975.134

75. Hack M. Petri net languages. Project MAC Memo 127. Cambridge, 1975.

76. Keller R.M. Vector replacement systems: a formalism for modelling asynchronous systems. Tech. Report, Princeton University, 117, 1972.

77. Keller R.M. Generalized Petri nets as models for system verification. Tech. Report, Princeton University, 1975,202.

78. Kosaraju S.R. Limitations of Dijkstra's semaphore, primitives and Petri nets. -Operating Systems Review, 1973, 7, №4, p. 122 136.

79. Agerwala T. A complete model for representing the coordination of asynchronous processes. In: Hopkins Computer Research. Report 32. Baltimore, 1974.

80. Agerwala Т., Flynn M. Comments on capabilities, limitations and "correctness" of Petri nets In: Proc. of First Annual Symposium on Computer Architecture. New York, 1973, p. 81- 86.

81. Valk R. On the computational power of extended Petri nets. In: Lecture Notes in Computer Science. Berlin: Springer-Verlag, 1978, 64. p.526 - 535.

82. Valk R. Self-modifying nets, a natural extension of Petri nets. In: Lecture Notes in Computer Science. Berlin: Springer-Verlag, 1978, 62, p.464-476.

83. Осипов C.H., Тахаутдинов B.C. Метод распараллеливания команд // Тезисы докладов Н-й международной научно-технической конференции «Новые информационные технологии и системы». Пенза, 1996. С.35.

84. Осипов С.Н., Тахаутдинов B.C. Распараллеливание команд методом подстановок // Тезисы докладов юбилейной научной и научно-методической конференции, посвященной 65-летию КГТУ им. А.Н.Туполева.- Казань, 1997. С. 164.

85. Сетевая телеобработка данных // Отчет о НИР. № госрегистрации 01860056143, КАИ, Казань, 1986.

86. Davidson, Е. S. 1971. "The Design and Control of Pipelined Function Generators," Proc. 1971 Int. IEEE Conf. on Systems, Networks, and Computers, Oaxtepec, Mexico, January, pp. 19-21.

87. Shar L.E. and E. S. Davidson. 1974. "A MultiminiProcessor System Implemented Through Pipelining," Computer, February, pp. 42-51.135

88. Patel, J. H., and E. S. Davidson. 1976. "Improving the Throuehput of a Pipeline by Insertion of Delays," IEEE/ACM 3rd Ann. Sytmp. Computer Arch., IEEE No.76CH 0143-5C, pp. 159-163.

89. Осипов C.H., Тахаутдинов B.C., Тукмеев P.P. Параллельный процессор телеобработки данных // Тезисы докладов республиканского научно-технического семинара. Казань, 1989. С.13-14.

90. Thomas А.Т., and Е. S. Davidson. 1974. Scheduling of Multiconfigurable Pipelines. Proc.l2th Ann. Allerton Conf. Circuits and System Theory, University of Illinois, Champaign-Urbana, pp. 658-669.

91. Davidson E.S., A.T. Thomas, L. E. Shor, and J. H. Patel. 1975. Effective Control for Pipelined Computers, Proc. Spring COMPCON, IEEE no. 75CH 0920-9C, pp-181-184.

92. Kogge P.M. 1977a. "The Microprogramming of Pipelined Processors," Proc. 4th Ann. Conf. Computer Arch., IEEE No. 77CH 1182-5C, March, pp. 63-69.

93. Kaminsky W.J., and E.S.Davidson. 1977. "Organization of Multiple Stream Pipelined LSI Processors," Coordinated Sciences Laboratory, Univ. of Illinois, Champaign-Urbana.

94. Emer J.S., and E.S. Davidson. 1978. Control Store Organization for Multiple Stream Pipelined Processors, Coordinated Science Laboratory, University of Illinois. Champaign-Urbana.

95. Осипов C.H., Тахаутдинов B.C. Вопросы построения процессора телеобработки данных на МП комплектах БИС // Тезисы докладов 9-й отраслевой научно-технической конференции молодых ученых и специалистов. Казань, 1985. С.43.

96. Ильин А.В., Осипов С.Н., Тахаутдинов B.C. Микропрограммный процессор удаленной телеобработки данных // Тезисы докладов 2-й межреспубликанской студенческой научной конференции. Казань, 1987. С.35.

97. Осипов С.Н., Тахаутдинов B.C. Микропроцессорный связный контроллер с параллельной обработкой микрокоманд // Межвузовский сборник «Проблемно-ориентированные средства повышения эффективности вычислительных систем». -Казань, 1988.С.36-40.