Методы приближенного анализа производительности и повышения эффективности функционирования вычислительных систем с параллельной обработкой данных: Стохастические и детерминированные модели тема диссертации и автореферата по ВАК РФ 05.13.13, кандидат технических наук Труб, Илья Иосифович

• Труб, Илья Иосифович
• кандидат технических наук
• 1994

Оглавление диссертации кандидат технических наук Труб, Илья Иосифович

Введение.

ГЛАВА 1. Методы оценки быстродействия диалоговых вычислительных систем с циклической дисциплиной обслуживание.

1.1 Распределение времени ожидания в открытой вычислительной системе.

1.1.1. Аналитические результаты.

1.1.2. Результаты численных экспериментов.

1.2. Анализ неоднородной вычислительной системы коллективного пользования.

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

2.1. Обзор основных методов исследования.-2.2. Модель функционирования модульной с равновероятными обращениями к каждому модулю.

2.2.1. Постановка задачи.—

2.2.2. Определение множеств состояния и событий.

2.2.3. Построение системы уравнений.

2.2.4. Сведение к системе линейных уравнений

2.2.5. Анализ основных характеристик системы.

2.3. Исследование функционирования модульной памяти с неравновероятными обращениями.

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

2.3.2. Анализ особенностей системы. Определение множества состояний.

2.3.3. Построение системы уравнений для. вероятностей состояний

2.3.4. Вывод уравнения для ъ.

2.3.5. Критерий эффективности.

ГЛАВА 3. Анализ производительности ЭВМ,. управляемой потоком операндов

3.1. Введение и обзор литературы.—

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

3.2.1. Постановка задачи.—

3.2.2. Математическая модель для случая А,<р,.

3.2.3. Случай различного быстродействия. процессоров

3.2.4. Учет быстродействия блоков памяти

3.2.5. Анализ средних.

3.2.6. Численные эксперименты.

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

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

3.3.2. Математическая модель.

3.3.3. Численные эксперименты.

ГЛАВА 4. Вычислительная система, управляемая потоком запросов: редукция к задаче на графе, алгоритмы анализа и оптимизации

4.1. Введение и обзор литературы.~

4.2. Математическая модель. Основные определения.

4.3. Режимы обслуживания запросов.

4.4. Расчет времени работы для режима 1.

Дисциплина FCFS

4.5. Расписания на графах потоков данных.

4.6. Стратегия оптимизации.

4.7. Моделирование обслуживания запросов в режиме

4.8. Дальнейшие направления изучения графов. потоков данных

Введение диссертации (часть автореферата) на тему «Методы приближенного анализа производительности и повышения эффективности функционирования вычислительных систем с параллельной обработкой данных: Стохастические и детерминированные модели»

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

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

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

Основными задачами исследования являются:

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

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

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

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

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

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

Защищаемые научные положения и результаты, их новизна:

Положения:

1. Необходимым и достаточным условием существования стационарного режима в вычислительной системе, управляемой потоком операндов, является выполнение соотношения Р/ц < 1, где Б - средняя местность команд программы (число входных операндов), q - средняя ширина параллелизма алгоритма.

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

Результаты:

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

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

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

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

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

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

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

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

Апробация. Основные результаты работы докладывались и обсуждались на научно-исследовательском семинаре по дискретной математике (Южный центр АН Украина, Одесса, 1993), I Международной конференции "Компьютерные программы учебного назначения" (Мариуполь, 1993), научных семинарах в ИПММ АН Украины (Донецк, 1993), кафедры алгебры и теории вероятностей Донецкого государственного университета (1992-1993 гг.), кафедры прикладной математики и информатики Донецкого технического университета (1992-1993 гг.).

Публикации. Содержание диссертации отражено в 8 опубликованных работах.

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

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

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

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

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

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

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

Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Труб, Илья Иосифович

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Труб, Илья Иосифович, 1994 год

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

2. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычис-тельных сетях. М.: Наука, 1989.

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

4. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979

5. Клейнрок Л. Теория массового обслуживания. Л.: Машиностроение, 979.6. "Компьютер-пресс", Л 5, 1993.

6. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М.: аука, 1975.

7. Сигнаевский В.А., Коган Я.А. Методы оценки быстродействия вычис-ательных систем. М.: Наука, 1991.

8. Фельдман Л.П., Дедшцев В.А. Математическое обеспечение САПР: мо-злирование вычислительных и управляющих систем. Киев, УЖ ВО, 1992

9. Шерр А. Анализ вычислительных систем с разделением времени.- М.: яр, 1970.

10. Яшков С.Ф. Анализ очередей в ЭВМ. М.: "Радио и связь", 1989.

11. Bhat U.N. "Elements of Applied Stochastic Processes". Wiley, 2W York, 1972.

12. Ochi M.K. "Applied Probability and Stochastic Processes in Engl-serlng and Physical Sciences". Wiley, New York, 1990.

13. Taylor H.M., Karlin S. "An Introduction to Stochastic Modeling" Academic Press, New York, 1984.

14. Tipper D., Smdareshan M.K. "Numerical Methods for Modeling Com-iter Networks Under Nonstationary Conditions". IEEE Journal on Seated Areas in Communication, J 9, 1990.1. К главе 2

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

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

17. Барлоу Р.Х. Оценка производительности параллельных алгоритмов. В кн. Системы параллельной обработки (Под ред. Д.Ивенса). М.: Мир, 1985.

18. Гилмор П. Высокопараллельный процессор МРР.- В кн. СуперЭВМ: аппаратная и программная организация (Под ред. С. Фернбаха). М.: Радио и связь, 1991.

19. Дегтярев Е.К. Оценка средней скорости многосекционной памяти ЦВМ. Известия АН СССР. Техническая кибернетика, 1970, N 2.

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

21. Кемени Д.Д., Снелл Д. Конечные цепи Маркова. М.: Наука, 1970

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

23. Миура К. СуперЭВМ фирмы Fujitsu: векторная система РАСОМ (Там же где и 4.).

24. Миура К., Учида К. Векторный процессор РАСОМ. В кн. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы суперЭВМ (Под ред. Я.Ковалика).- М.: Мир, 1988.

25. Остланд Н.С., Хиббэрд П.Г., Вайтсайд P.A. О применении сильносвязанных многопроцессорных систем для научных вычислений. В кн. Параллельные вычисления (Под ред. Г.Родрига) - М.: Наука, 1986.

26. Пом А., Агравал 0. Быстродействующие системы памяти. М.: Мир, 1987.

27. Фельдман Л.П. Методические указания по курсу "Структуры вычислительных систем и организация вычислительных процессов". Донецк, ДНИ, 1987.

28. Фельдман Л.П., Дедищев В.А. Математическое обеспечение САПР: моделирование вычислительных и управляющих систем. Киев, ШК ВО, 1992

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

30. Bhandarkar D.P. "Analysis of Memory Interference in Multiprocessors". IEEE Transactions on Computers, N9, 1975.

31. Budnik P., Kuck D.J. "The Organization and Use of Parallel Memories". IEEE Transactions on Computers, N12, 1971.

32. Burnett G.J., Goffman E.J. "Analysis of Interleaved Memory Systems Using Blockage Buffers". Commun. Ass. Gomput.Mach., N2, 1975.

33. Censier L., Feautier P. "A New Solution to the Coherence Problem in Multicache Systems"-IEEE Transactions on Computers, N12, 1978

34. Chang D.Y., Kuck J., Lawrie D.H. "On the Effective Bandwidth of Parallel Memories". IEEE Transactions on Computers, N5, 1977.

35. Coffman E.G., Burnett G.J., Snowdon R.A. "On the Performance of Interleaved Memories with Multiple Word Bandwidths". IEEE Transactions on Computers, N12, 1971.

36. Coffman E.G., Denning P.J. "Operating System Theory". Engle-wood Cliffs NJ Prentice-Hall, 1973.

37. De-Lei Lee "Architecture of an Array Processor Using a Nonlinear Skewing Scheme" . IEEE Transactions on Computers, N 4, 1992.

38. Dubois M., Briggs P.A. "Effects of CacheCoherency In Multiprocessors". IEEE Transactions on Computers, N11, 1982.

39. Flynn M.J. "Some Computer Organizations and Their Effectiveness" IEEE Transactions on Computers, N9, 1972.

40. Gottlieb A., Grishman R., Kruskal C.P., McAuliffe K.P., Rudolph L., Snir M. "The NYU Ultracomputer Designing an MIMD Shared Memory Parallel Machine".- IEEE Transactions on Computers, N2, 1983

41. Harper D.T. "Increased Memory Performance During Vector Accesses Through the Use of Linear Address Transformations" IEEE TransactIcms on Computers, N2, 1992.

42. Harper D.T., Jump J.R. "Vector Access Performance In Parallel Memories Using a Skewed Storage Scheme".- IEEE Transactions on Computers, N 12, 1987.

43. Hoogendorn O.H. "A General Model for Memory Interference in Multiprocessors". IEEE Transactions on Computers, N10, 1977.

44. Hwang K., Brlggs I*.A. "Oomputer Architecture and Parallel Processing". Mc Graw Hill, 1984.

45. Kaplan K.R., Winder R.O. "Cache-based computer systems", Computer, N 3, 1973.

46. Khuth D.E., Rao G.S. "Activity in an Interleaved Memory" IEEE Transactions on Computers, N9, 1975.

47. Kurtsberg M. "On the Memory Conflict Problem in Multiprocessor Systems". IEEE Transactions on Computers, N3, 1974.

48. Lawrie D.H. "Access and Alignment of Data in Array Processor" IEEE Transactions on Computers, N12, 1975.

49. LiuY.-C., Jou C.-J. "Effective Memory Bandwidth and Processor Blocking Probability In Multiple-Bus System". IEEE Transactions on Gomputers, N6, 1987.

50. OedW., Lange 0. "On the Effective Bandwidth of Interleaved Memories in Vector Processor Systems" IEEE Transactions on Computers, N 10, 1985.

51. Patel J.M. "Analysis of Multiprocessors with Private Cache Memories". IEEE Transactions on Gomputers, N3, 1982.

52. Rau B.R. "Interleaved Memory Bandwidth in a Model of Multiprocessor Computer System". IEEE Transactions on Computers, N7, 1979.

53. Rau B.R. "Program Behavior and the Performance of Interleaved Memories".- IEEE Transactions on Gomputers, N3, 1979.

54. Ravi C.V. "On the Bandwidth and Interference in Interleaved Memory Systems". IEEE Transactions on Computers, N8, 1972.

55. Sethi A.S., Deo N. "Interference in a Multiprocessor System with Localized Memory Access Probabilities". IEEE Transactions on Computers, N2, 1979.

56. Shapiro H.D. "Theoretical Limitation on the Efficient Use of Parallel Memories".- IEEE Transactions on Computers, N5, 1978.

57. Smilauer B. "General Model for Memory Interference In Multiprocessors and Mean Value Analysis". IEEE Transactions on Computers, N8, 1985.

58. Smith A. "Cache Memories". Computing surveys, N 9, 1982.

59. Spirn J.R. "Program Behavior Models and Measurements" -New-York, Elsevier-North Holland, 1977.

60. Herman F.W. "A Study of Interleaved Memory Systems by Trace Driven Simulation". Fourth Symp. on Simulation of Computer Systems, August, 1976.

61. Watson W.J. "The TIASG A Highly Modular and Flexible Super Computer Architecture". - AFIPS, Proceeding FJCC, 1972.

62. Wijshoff H.A.G., Leeuwen van J. "The Structure of Periodic Storage Schemes for Parallel Memories". IEEE Transactions on Computers, N6, 1985.1. К главам 3 и 4

63. Брехов 0., Морару В. Определение граничной производительности ЭВМ управляемой потоком данных. Автоматика и телемеханика ,N6,1992.

64. Брехов 0., Морару В. Оценка структурных различий ЭВМ, управляемых потоком данных. Автоматика и телемеханика, N 7, 1992.

65. Бэбб Р. Параллельная обработка крупноструктурированных потоков данных на CRAY Х-МР. В кн. СуперЭВМ: аппаратная и программная реализация (Под ред. С.Фернбаха), М.: Радио и связь, 1991.

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

67. Воеводин В.В. Математические модели и методы в параллельных процвссах. М.: Наука, 1Э86.

68. Диниччи Дэвид Loral Dataflo LDP 100.- В кн. Программирование на параллельных вычислительных системах (Под ред.Р.Бэбба) М. : Мир, 1991

69. Дэннис Дж., Шнабель Р. Численные метода безусловной оптимизации и решение нелинейных уравнений. М.: Мир, 1988.

70. Зыков A.A. Основы теории графов. М.: Наука, 1987.

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

72. Клейнрок Л. Теория массового обслуживания. Л.: Машиностроение, 1979.

73. Конвей Р.В., Максвелл Л.А., Миллер Л.В. Теория расписаний. М.: Наука, 1975.

74. Левин В.И. К планированию работы вычислительных систем. Ч. 1, 2, 3. Автоматика и вычислительная техника, 1982- N5; 1983 - N 2, 3.

75. Левин В.М. Структурно-логические методы исследования сложных систем с применением ЭВМ. М.: Наука, 1987.

76. Лекции по теории графов (Емеличев В.А., Мельников О.И. и др. ) -- М.: Наука, 1990.

77. Майерс Г. Архитектура современных ЭВМ. Т.2. М.: Мир, 1982.

78. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.: Мир, 1991.

79. Саати Т.Л. Элементы теории массового обслуживания и ее приложения М.: Советское радио, 1971.

80. Сир Ж.- К. Метод потока операндов в многопроцессорных системах типа MIMD. В кн. Системы параллельной обработки (Под ред. Д. Ивенса), М.: Мир, 1985.

81. Триливен Филип К. Модели параллельных вычислений ( Там же, где и 17.).

82. Ху T.G. Параллельное упорядочивание и проблемы линии сборки. -Кибернетический сборник, вып.4. М.: Мир, 1967.-АЪ^

83. Amamiya M., Hasegawa R. "Dataflow Computing and Eager and Lazy Evaluations" New Generation Computers, 1984.

84. Arvlnd, Nlkhil R.S. "Executing a Program on the MIT Tagged Token Dataflow Architecture" IEEE Transactions on Computers, N 3, 1990.

85. Baba T., Bing Yao S., Hevner A.R. "Design of a Functionally Distributed, Multiprocessor Database Machine Using Data Flow Analysis" -- IEEE Transactions on Computers, N 6, 1987.

86. Bhuyan L., Ghosal D. "Approximate Analysis of Single and Multiple Ring Networks" IEEE Transactions on Computers, N 7, 1989.

87. Bohm A.P.W., Sargeant J. "Code Optimization for Tagged Token Dataflow Machines" IEEE Transactions on Computers, N 1, 1989.

88. Brock J.D.,Montz L.B. "Translation and Optimization of Data Flow Programs" in Proc. 1979 Int. Conf. Parallel Processing, 1979.

89. Buehrer R., Ekanadham K. "Incorporating Data Flow Ideas Into yon Neumann Processors for Parallel Execution" IEEE Transactions on Computers, N 12, 1987.

90. Campbell M.L. "Static Allocation for a Data-Flow Multiprocessor" in Proc. 1985 Int. Conf. Parallel Processing, August, 1985.

91. Chang P.R., Lee C.S.G. "A Decomposition Approach for Balancing Large Scale Acyclic Data Flow Graphs" IEEE Transactions on Computers, N 1, 1990.

92. Coffman E.G. "Computer and Job-Shop Scheduling Theory" New York Wiley, 1976.

93. Comte D., Hlfdi N., Syre J.C. "The Data Driven LAU Multiprocessor System: Results and Perspectives" Proc. IFIP, 1980.

94. Cornish M. "The TI Dataflow Architectures: the Power of Concurrency for Avionics" Proc. 3rd Conf. on Digital Avionics Systems, IEEE, New York, 1979.

95. Dennis J.B. "Data Plow Supercomputer" IEEE Computer, N 11, 1980.

96. Dennis J.B. "First Version of a Data Plow Procedure Language" Lecture Notes in Computer Science, vol.19, Sprlnger-Verlag, 1974.

97. Dennis J.B., Gao C.-R., Todd K.W. "Modeling the Weather with a Data Plow Supercomputer" IEEE Transactions on Computers, N 7, 1984

98. Dennis J.B., Lim W.Y.P., Ackerman W.B. "The MIT Data Plow Engineering Model" IF IP Proc., 1983.

99. Ercegovac M.D., Patel D.R., Lang T. "Functional Language and Data Flow Architectures" Proc 1983 Summer Computer Simulation Conference, vol.2, 1983.

100. Friedman D.P.,Wise D.S. "Cons Should Not Evaluate Its Arguments" Automata Languages Programming, 1976.

101. Gaudiot J.-L. "Data-Driven Multicomputers in Digital Signal Processing" Proc. IEEE, N 9, 1987.

102. Gaudiot J.-L. "Structure Handling in Data-Flow System" IEEE Transactions on Computers, N 6, 1986.

103. Gaudiot J.-L., Ercegovac M.D. "Performance Analysis of a Data Flow Computer with Variable Reduction Actors" Proc. 4th Intl. Conf. Distributed Computing Systems, 1984.

104. Gaudiot J.-L., Vedder R.W., Tucker G.K., Finn D., Campbell M.L., "A Distributed VLSI Architecture for Efficient Signal and Data Processing" IEEE Transactions on Computers, N 12, 1985.

105. Gaudiot J.-L., Wei Y.-H. "Token Relabeling In Tagged Token Data-Flow Architecture" IEEE Transactions on Computers, N 9, 1989.

106. Ghosal D.,Bhuyan L.N. "Performance Evaluation of Dataflow Architecture". IEEE Transactions in Computers, N 5, 1990.

107. Gonzalez M.J. "Review on Deterministic Scheduling Theory" ACM- i 8S

108. Computer Surreys, N 3, 1977.

109. Gostelow К.P., Thomas R.E. "Performance of a Simulated Dataflow Computer" IEEE Transactions on Computers, N 10, 1980.

110. Granski M., Koren I., Silberman G.M. "The Effect of Operation Scheduling on the Performance of a Data Flow Computer" IEEE Transactions on Computers, N 9, 1987.

111. Gurd J.R., Kirkham C.C., Watson I. "The Manchester Prototype Dataflow Computer" Comm. ACM, N 1, 1985.

112. Ha S., Lee E.A. "Compile-Time Scheduling and Assignment of Dataflow Program Graphs with Data-Dependent Iteration" IEEE Transactions on Computers, N 11, 1991.

113. Hartimo I., Kronlof K., Simula 0., Skutta J. "DESP: A Data Flow Signal Processor" IEEE Transactions on Computers, N 1, 1986.

114. Hudak P. »Goldberg B. "Distributed Execution of Functional Programs Using Serial Comblnators" Transactions on Computers, N10, 1985.

115. IEEE Computer. Special Issue on Dataflow Computers.- N 2, 1982.

116. Jen C.W., Kwai D.M. "Data Flow Representation of Iterative Algorithms for Systolic Arrays" IEEE Transactions on Computers, N 3, 1992

117. Jess A.G., Keesh G.M. "A Data Structure for Parallel L/U decomposition" IEEE Transactions on Computers, N 3, 1982.

118. Johnsson T. "Efficient Computation of Lazy Evaluation" ACM SIG-PLAN Notices, N 6, 1984.

119. KanR. "Machine Scheduling Problems" Nethelands: Nijhoff, 1976.

120. Kavi K.M., Buckles B.P., Bhat U.N. "A Formal Definition of Dataflow Graph Model" IEEE Transactions on Computers, N 11, 1986.

121. King P.J.В., Mitrani I. "Modeling a Slotted Ring Local Area Network" IEEE Transactions on Computers, N 5, 1987.

122. Kohler W.H. "A Preliminary Evaluation of the CP Method for Scheduling Tasks on Multiprocessor Systems",' IEEE Transactions on Computers, N 12, 1975.

123. Lee E.A., Messerscbmitt D.G. "Static Scheduling of Synchronous Data Plow Programs for Digital Signal Processing" IEEE Transactions on Computers, N 1, 198T.

124. Loucks W.M., Hamacher V.G., Prelss В., Wang L. "Short-packet Transfer Performance in Local Area Ring Networks". IEEE Transactions on Computers, N 11, 1985.

125. Mago G.A. "A Network of Microprocessors to Execute Reduction Languages". Int. Journ. of Computer and Information Sciences, 8.5 and 8.6 (1979)

126. O'Leary D., Stewart G. "Data-Plow Algorithms for Parallel Matrix Computations" Commun ACM, N 6, 1985.

127. Parhl K.K.,Messerschmitt D.G. "Static Rate-Optimal Scheduling of Iterative Data-Plow Programs via Optimum Unfolding". -IEEE Transactions on Computers, N 2, 1991.

128. Patnaik L.M., Govindarajan R., Ramadoss N.S. "Design and Performance Evaluation of EXMAN: An Extended Manchester Data Plow Computer" IEEE Transactions on Computers, N 3, 1986.

129. Pingali K., Arvlnd "Efficient Demand-Driven Evaluation" Part 1, ACM Trans. Programming Language Systems, N 4, 1985; part 2, N 1,1986.

130. Ramamdarthy C.V., С handy K.M., Gonzalez M.J. "Optimal Scheduling Strategies In a Multiprocessor Systems" IEEE Transactions on Computers, N 2, 1972.

131. Rambaugh J.E. "Data Flow Multiprocessor". IEEE Transactions on Computers, N 2, 1977.

132. Reed D., Patrick M. "Iterative Solution of Large Sparse Linear Systems on a Static Data Flow Architectures:Performance Studies" IEEE Transactions on Computers, N 10, 1985.

133. Requa J.E., McGraw J.R. "The Piecewise Data Flow Architecture: Architectural Concepts" IEEE Transactions on Computers, N 5, 1983.

134. Sarkar V., Hennessy J. "Partitioning Parallel Programs for Macro&ataflow" in Proc. 1986 AGI Conf. Lisp Functional Programming, Cambridge, MA, Aug. 4-6, 1986.

135. Srinlvas M.A. "Optimal Parallel Scheduling of Gaussian Elimination DAG's" IEEE Transactions on Computers, N 12, 1983.

136. Takesue M. "Cache Memories for Data Plow Machines" IEEE Transactions on Computers, N 6, 1992.

137. Treleaven P.C., David B.R., Hopkins B.R. "Data driven and Demand-driven Computer Architecture" ACM Gomput. Surveys, N 3, 1982.

138. Turner D.A. "A Hew Implementation Technique for Applicative Languages" Software: Practice and Experience, N 9, 1979.

139. Ullman J.D. "MP-complete Scheduling Problems" Journal on Computer Systems Sciences, N 6, 1975.

140. Veen A.H. "Dataflow Machine Architecture" AGM Computer Survey, N 12, 1986.

141. Vegdahl S.R. "A Survey of Proposed Architectures for the Execution of Functional Languages" Transactions on Computers, N 12, 1984.

142. Wadge W.-W., Ashcroft E.A. "Lucid. The Dataflow Programming Language" London, England: Academic, 1985.

143. Wei Y.-H.,Gaudlot J.-L. "Demand-Driven Interpretation of PP Programs of a Data Plow Microprocessors" IEEE Transactions on Computers, N 8, 1988.

144. Wing 0., Huang J.W. "A Computation Model of Parallel Solution of Linear Equations" IEEE Transactions on Computers, N 7, 1980.1. S it