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

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

Окунев Анатолий Семенович

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

Специальность: 05.13.15 - " Вычислительные машины и системы "

АВТОРЕФЕРАТ

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

Москва-2005

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

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

академик РАН |Всеволод Сергеевич Бурцев!

Официальные оппоненты: доктор технических наук, профессор

Московского инженерно-физического института (государственного университета) Ярослав Афанасьевич Хетагуров

кандидат технических наук, старший научный сотрудник Вычислительного центра им. A.A. Дородницына РАН Сергей Алексеевич Щербаков

Ведущая организация: ОАО Институт электронных управляющих

машин (ИНЭУМ)

Защита диссертации состоится ноября 2005 года в' часов на заседании диссертационного совета Д 002.073.01 при Институте проблем информатики РАН по адресу: 119333, Москва, ул. Вавилова, д. 44, корп. 2.

С диссертацией можно ознакомиться в библиотеке Института проблем информатики РАН.

Автореферат разослан " октября 2005 г.

Отзыв, заверенный печатью, просим отправлять в одном экземпляре по адресу: 119333, Москва, ул. Вавилова, д. 44, корп. 2.

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

С.Н. Гринченко

Общая характеристика работы

Актуальность темы диссертации

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

Для решения этих задач требуются суперкомпьютеры с реальной производительностью 1012-1016 операций в секунду. Причем с каждым годом требования, предъявляемые к вычислительной технике, на которой решаются подобные задачи, возрастают.

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

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

- временные потери, возникающие при обмене данными между процессорами.

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

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

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

наук под руководством академика [В.С. Бурцева! разработаны новые принципы

организации вычислительного процесса и на их основе спроектирована

вычислительная система с автом^тад^эдиц, и ФМИШВД Тием ресурсов,

БИБЛИОТЕКА. .

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

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

Цель и задачи работы

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

Для достижения поставленной цели в работе решаются следующие основные задачи:

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

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

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

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

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

Объект и предмет исследования

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

? «•'

Методы исследования

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

Научная новизна

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

Основные научные результаты работы состоят в следующем:

1. На основе проведенного анализа архитектуры ВСАРР разработаны методы работы системы в многозадачном режиме.

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

3. Впервые разработаны подходы к созданию ВСАРР, работающей в реальном масштабе времени, обеспечивающие восстановление работоспособности системы с контрольных точек и обработку прерываний, возникающих при сбоях и отказах отдельных устройств.

4. Впервые разработана структура и принципы функционирования центрального устройства управления памятью (ЦУУТГ), обеспечивающего выполнение специальных команд управления задачами, организацию виртуальной памяти и взаимодействие ВСАРР с операционной системой.

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

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

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

Практическая значимость

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

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

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

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

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

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

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

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

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

Положения, выносимые на защиту

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

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

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

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

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

Реализация результатов работы

Новые теоретические положения и технические решения апробированы на инструментальном испытательном комплексе ВСАРР. Результаты работы реализованы в Институте проблем информатики РАН (ИЛИ РАН) в отделе «Проблем построения информационно-вычислительных систем высокого параллелизма» при исследовании и разработке вычислительной системы с

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

Апробадия работы

Основные положения и результаты работы докладывались и обсуждались на научных семинарах в ИЛИ РАН в 1999-2005 гг., а также на конференциях и научных форумах: на международной конференции «Информационные технологии в науке, образовании, телекоммуникации, бизнесе» (г. Гурзуф, 2001), на международной научно-технической конференции «Интеллектуальные и многопроцессорные системы ИМС'2003» (пос. Дивноморское, 2003), на международной научно-практической конференции «Искусственный интеллект 2004. Интеллектуальные и многопроцессорные системы - 2004» (пос. Кацивели, Крым, 2004), на «П Научной сессии Института проблем информатики Российской академии наук: Проблемы и методы информатики» (Москва, 2005), на международной научно-технической конференции «Интеллектуальные и многопроцессорные системы ИМС'2005» (пос. Дивноморское, 2005), на второй Всероссийской научно-технической конференции «Методы и средства обработки информации МСО-2005» (Москва, 2005).

Некоторые решения, созданные в рамках диссертации в виде имитационной модели, демонстрировались на Всемирной выставке по информационным технологиям СеВ1Т-2003, Ганновер, Германия.

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

Публикации

По материалам диссертационной работы опубликовано 12 печатных работ, список которых приводится в конце автореферата. Кроме того по теме диссертации опубликованы материалы в научно-технических отчетах ИЛИ РАН за 2000-2005 гг.

Структура и объем диссертации

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

Содержание работы

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

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

В разделе 1.1 описываются проблемы повышения производительности в

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

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

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

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

Архитектура потока данных коренным образом отличается от традиционной фон-неймановской архитектуры. Приводится анализ уже существующих архитектур потока данных, выявляются их преимущества и недостатки. Рассматриваются проекты: МТТ Static Dataflow Architecture, реализующий статическую модель вычислений потока данных; MDFM и MIT TTDA. реализующие динамическую модель вычислений потока данных и StarT, реализующий гибридную модель вычислений потока данных. Гибридная модель организации вычислительного процесса с управлением потоком данных явилась попыткой объединить в себе лучшие стороны двух разных по принципам организации вычислительного процесса моделей - фон-неймановской модели и модели с управлением потоком данных. Делается вывод, что на данный момент гибридная модель потока данных является наиболее перспективной в области создания многопроцессорных вычислительных систем.

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

Рассматриваются подходы к управлению ресурсом памяти, примененные в проектах вычислительных систем - MIT TTDA и MDFM.

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

- «взрывной» параллелизм задач;

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

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

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

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

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

В разделе 2.1 дано краткое описание работы ВСАРР. Архитектура ВСАРР построена на основе модели вычислений, управляемых потоком данных. Использование ассоциативной памяти в качестве памяти совпадений и введение комплексной системы управления вычислениями дает возможность использовать все преимущества и устранить недостатки классических потоковых вычислительных систем, снижая при этом требования к объему памяти, сложности отдельных компонентов и стоимости системы.

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

Токен

Маска Признаки Вид операции ^ад. N под зад. Асл. Контекст Данное

Пара Ключ

Маска Признаки Вид операции Ключ Данное 1 Данное 2

Рис 1. Структура токена и пары

Под взаимодействием токенов понимается факт совпадения в ассоциативном запоминающем устройстве (АЗУ) ключей токенов при проведении поиска. Результатом взаимодействия токенов в АП является пара.

Расширенный контекст (РК)

л

рез № задачи № подзадачи Контекст К,

71 О

Рис. 2. Структура ключа токена

Программу, выполняемую на ВСАРР, можно представить в виде виртуального графа вычислений. Граф состоит из узлов (каждый узел имеет не более двух входов и «неограниченное» количество выходов) и указателей, по которым перемещаются данные к следующему узлу. Таким образом, фактически определяется последовательность обработки данных. В узле графа выполняется программа обработки поступивших на него операндов. Результат работы программы узла в виде токенов направляется по ветвям графа в соответствии с указателями к следующим узлам.

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

одной команды. Сами же программы узлов могут выполняться параллельно. Структурно, ВСАРР представляет из себя набор компонентов (рис. 3):

- вычислительные узлы (ВУ) или кольца (ИУ-КМтокенов-МАП-КМпар);

- исполнительные устройства (ИУ);

- модули ассоциативной памяти (МАП);

- коммутационная среда (КМ токенов, КМ пар, КМ вычислительного узла);

- общее оперативное запоминающее устройство (ООЗУ), состоящее из модулей (МООЗУ) и его адаптер;

- центральное устройство управления памятью (ЦУУП);

- накопители на магнитных дисках (НМД);

- хост-машина.

ИУ 1

гл

РХА^] "I

МАП 1

их«* Л

ПИ

МАП п

Рис. 3. Структурная схема ВСАРР

В разделе 2.2 исследуется проблема переполнения ассоциативной памяти ВСАРР и методы ее решения.

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

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

Для любых вычислительных систем всегда может быть написана такая

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

о модульность АП;

о несовершенная хэш-функция, которая адресует модули АП;

о наличие проблемы «взрывного» параллелизма задач;

о использование принципа маскирования ключа токена и бесконечной кратности [2];

о использование глобальных токенов [5];

о возможность генерации программой узла «неограниченного» количества токенов;

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

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

К основным методам решения проблемы переполнения АП можно отнести следующие:

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

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

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

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

Основными причинами неравномерности прохождения токенов и пар по кольцу, и, как следствие, необходимости использования буферов (КМ токенов и КМ пар) являются следующие факторы:

а) изменение параллелизма решаемой задачи;

б) изменение пропускной способности АП из-за неравномерного распределения токенов по модулям;

в) неравномерность режимов работы модулей АП при обработке множественных откликов [4] (что связано с использованием маски ключа и кратности токенов);

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

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

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

- МАП принимает новые токены на вход, даже если он занят операцией поиска или обработкой результатов поиска по ранее пришедшим токенам;

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

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

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

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

Иерархия памяти ВСАРР состоит из пяти уровней. На первом уровне иерархии располагаются быстрые регистры ИУ, которые используются для хранения промежуточных локальных данных, необходимых для выполнения программы узла. Буфер готовых пар (БГП) является вторым уровнем иерархии.

Пары, которые хранятся в БГП, формируются на третьем уровне иерархии -в ассоциативной памяти. Помимо технологии отложенных токенов существует возможность откачки формируемых модулем АП пар непосредственно на четвертый уровень иерархии памяти - в общее ОЗУ (ООЗУ).

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

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

Виртуальное адресное пространство - множество виртуальных адресов, используемых в программах.

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

В отличие от традиционных систем в ВСАРР виртуальный адрес указывает на виртуальный узел - экземпляр одного из типовых узлов, описанных в программе, то есть виртуальный адрес содержит информацию о том, какой именно типовой узел (адрес программы этого узла определяется полем «Асл.» в ключе токена) и какой именно его экземпляр (поле «контекст» в ключе токена) имеется в виду. А физический адрес в АЛ ВСАРР указывает на одну из ячеек ассоциативной памяти предназначенной для хранения токенов. То есть виртуальный адрес и физический адрес указывают на разные виды информации.

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

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

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

Одновременно с откачкой этих токенов работа вычислительной системы с

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

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

В разделе 2.5 описываются аппаратно-программные методы регулирования параллелизма в ВСАРР.

При решении на ВСАРР задач различного класса пришлось столкнуться с проблемой, так называемого, «взрывного» параллелизма.

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

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

К аппаратным методам относятся:

- средства останова, откачки и подкачки токенов;

- управление работой буферов токенов;

- откачка пар из БГП и возвращение их в работу;

- аппаратная поддержка реализации многовходовых узлов.

К программным относятся следующие методы:

- различные варианты генерации токенов из программы узла;

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

- распространение вычислительного процесса по виртуальному графу задачи

последовательно, а не параллельно;

- последовательная подкачка токенов по запросу из программы (интенсивная подкачка).

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

В разделе 3.1 приводится общая классификация команд управления (рис. 4) задачами ВСАРР и краткое описание работы некоторых из них.

Описываются алгоритмы выполнения команд управления.

Возможны следующие режимы работы ВСАРР:

- многозадачный режим работы без подзадач;

- многозадачный режим работы с включением номера подзадачи в ключ;

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

Кроме того, существуют три уровня управления задачами (подзадачами):

- выполнение команды в ЦУУП инициируется операционной системой;

- пользовательская программа инициирует выполнение некоторых команд (только для управления подзадачами) путем осуществления системных запросов к ОС;

- автономная работа ЦУУП для преодоления переполнения отдельных модулей АП.

Рис. 4. Команды управления задачами ВСАРР

Основные типы команд управления задачами:

- «Зарегистрировать задачу»;

- «Удалить зарегистрированную задачу»;

- «Приостановить задачу»;

- «Откачать задачу»;

- «Запустить задачу»;

- «Ввести новые данные задачи»;

- «Проверить активность задачи»;

- «Загрузка памяти ИУ»;

- «Контроль содержимого памяти ИУ»;

- «Загрузка таблицы страниц ИУ»;

- «Контроль содержимого таблицы страниц ИУ»;

- «Подсчитать глобальную кратность»;

- «Снять DUMP для задачи».

Описываются форматы токена-команды, токена-сообщения, токена-фшпки, токена-фиксатора и токена-подтверждения.

В разделе 3.2 описывается аппаратная реализация ЦУУП, основными функциями которого являются:

- установка начальных физических адресов областей в адаптере ООЗУ (для каждого вида откачиваемых токенов имеется своя область в ООЗУ);

- распределение свободных страниц ООЗУ;

- сбор статистики по задачам;

- выполнение ротации задач или подзадач между АП и ООЗУ;

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

- определение окончания выполнения вычислений и останова задач. ЦУУП состоит из следующих основных семи блоков (рис. 5):

1. буферов для временного хранения передаваемых данных;

2. блока распределения токенов по группам;

3. дешифратора команд операционной системы;

4. блока обработки команд ОС;

5. дешифратора запросов из программы;

6. блока управления откачкой и подкачкой задач;

7. блока сбора статистики по задачам и подзадачам.

Рис. 5. Структурная схема ЦУУП

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

К специальным режимам работы относятся:

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

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

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

Четвертая глава посвящена исследованию функционирования вычислительной системы на инструментальном испытательном комплексе ВСАРР.

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

В состав инструментального испытательного комплекса (ИИК) входят:

- имитационная модель ВСАРР (поведенческого уровня);

- программная блочно-регистровая модель - ПБРМ;

- макет ВСАРР, выполненный на ПЛИС фирмы ALTERA.

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

Имитационная модель обеспечивает:

- корректное исполнение программ, диагностику ошибок;

- возможность изменения конфигурации системы;

- демонстрацию загрузки устройств системы.

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

В разделе 4.2 приводится описание программной блочно-регастровой модели ВСАРР.

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

На ПБРМ ВСАРР:

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

б) впервые осуществлялись эксперименты по преодолению переполнения модулей АП;

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

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

В процессе решения задач на ПБРМ пользователю предоставлена возможность отслеживать состояние объектов.

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

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

Таблица 1.

\ исследуемые \ режимы задачи, \ на которыхЧ проводились\ исследования \ алгоритмическое ограничение параллелизма изменение режима работы буферов (FILO, FIFO) подкачка/откачка по номеру задачи/подзадачи подкачка/откачка токенов по областям подкачка во время работы аппаратный многовходовой узел | многозадачный | режим работы без [ подкачки/откачки

«Ферзи» X

«Лабиринт» X

Синтез сетевой топологии X X X

«Эрозия» X X X X

Пузырьковая сортировка X X

«Скелетизация» X

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

Анализ прохождения задач в многозадачном режиме с ограниченным объемом АП (с откачкой/подкачкой токенов)

На ПБРМ было проведено исследование одновременного прохождения трех

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

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

Анализ возможности реализации режима работы с откачкой/подкачкой по областям

На ПБРМ было проведено исследование, целью которого являлся анализ выполнения задач с использованием откачки/подкачки не по номеру подзадачи, а по некоторой области ключа, которая блокирует выполнение части виртуального графа программы. Исследовался как автоматический механизм выделения устройством управления памятью соответствующих областей для откачки, так и задание этих областей программистом на стадии написания программы. В результате выполнения программы «Синтез сетевой топологии» на ограниченном объеме АП без использования механизма откачки/подкачки токенов по областям была зафиксирована блокировка выполнения программы по переполнению памяти на 480 такте (рис. 6а). Выполнение той же программы на той же конфигурации, но с использованием механизма откачки/подкачки токенов по областям было успешно завершено на 4400 такте (рис. 66).

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

а) б)

Рис. 6 Загруженность АП при прохождении задачи «Синтез сетевой топологии» в обычном режиме (а) и с использованием откачки/подкачки по областям (б)

Анализ прохождения задачи с минимальным использованием ресурса АП

Были проведены исследования, направленные на решение задачи минимизации ресурса АП. На ПБРМ была пропущена задача «Эрозия», относящаяся к классу задач математической морфологии. При ее решении были использованы команды подкачки «стартовых» токенов, инициируемые токенами,

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

Анализ прохождения задачи с поддержкой многовходовыхузлов

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

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

Сначала был осуществлен прогон задачи с многовходовыми узлами в режиме разбиения на 2-х входовые узлы (то есть без аппаратной поддержки многовходовых узлов), результаты можно увидеть на рис. 7а. Затем эксперимент был повторен с аппаратной поддержкой многовходовых узлов (рис. 76).

Рис 7 Статистика занятости АЛ при прохождении задачи «Эрозия» в стандартном режиме (а) и с использованием многовходовых узлов (б)

Характер прохождения задачи изменился, в частности, сократилось время выполнения (на 48.3% - с 219111 тактов до 147766), пиковая загрузка АП (11800 токенов) осталась на прежнем уровне, а также снизилась нагрузка на коммутационную сеть.

Анализ возможности управления параллелизмом задачи с помощью изменения алгоритма работы входных буферов МАП

На имитационной модели было проведено исследование влияния на прохождение задачи изменения режима работы буфера токенов (алгоритм работы буфера изменялся с FIFO на FILO). Выполнялась задача «Лабиринт». Эксперимент подтвердил, что переключая режим работы буфера, можно изменять параллелизм задачи, а следовательно, и характер ее прохождения. На рис. 8а видно, что задача при работе буфера в режиме FILO, имеет умеренный параллелизм (около 350

готовых пар) и выполняется за 12317 тактов. При переключении режима работы буфера на FIFO (рис. 86), та же задача (программа не видоизменялась) имеет параллелизм порядка 2200 пар и выполняется за 9622 такта на той же конфигурации системы. Загрузка ИУ увеличилась с 86% в первом случае до 90% -во втором.

3957« 1364 1930 2495 3060 3S25 «91 47SS 5321 5887 6452 7017 7583 81« 8713 K7t 9044 10530 "217 11903 Томл» 3et

1 407 922 1404 19« 25« 3150 3731 4313 4995 5477 8059 6040 7222 78C4 83» 89« 9550 10256 10963 11889 »etteUBui'w PectteM/atp

1 397803 1371 1938 2507 3075 3643 4211 4779 5347 5915 6483 7051 7819 9187 8755 9323 9891 105801127011980

I 366 79Й 1384 1930 2*95 Э060 3625 4191 47S& 53?. 5387 €452 7017 Г Tolwns/Step

£ly8«cfc

Algoc-hn

M««Sm IWxlUO

1 4078» 1404 1996 2566 3150 3731 4313 4695 5477 8059 6640 7222 7804 6366 8966 9550 Р«к«$Suiter Pec*e»»/Stw

6)

-Пары

Рис 8 Прохождение задачи «Лабиринт» с изменением ачгоритлшработы буфера токепов

с F1LO (а) на FIFO (б)

Также в разделе приводится расчет коэффициента эффективности механизма откачки/подкачки токенов:

м„.

ТУШП уиб,,

"отi лп Л р

, где

М0Тк - коэффициент эффективности работы механизма откачки/подкачки токенов; V™'" - полный объем АП [токен];

р - коэффициент порога, при котором начинается откачка; Я/"" - пропускная способность МАП-ООЗУ [бит/сек]; Я™ - пропускная способность МАП-КМ [бит/сек];

Лср - средняя заполненность области (количество токенов в откачиваемой области) [токен];

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

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

В качестве элементной базы для реализации макета ВСАРР были выбраны микросхемы программируемой логики - ПЛИС фирмы ALTERA. Логическое проектирование устройств, входящих в состав АП ВСАРР, проводилось в САПР фирмы ALTERA - Quartus. Данная система позволяет провести полный цикл проектирования и моделирования разрабатываемого устройства, от описания задания до программирования микросхем.

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

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

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

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

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

Основные результаты диссертационной работы

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

2. На основе проведенных исследований ВСАРР предложены методы решения проблемы переполнения ассоциативной памяти.

3. Проведены исследования, связанные с построением иерархии памяти ВСАРР.

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

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

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

7. Исследовано прохождение ряда программ на инструментальном испытательном комплексе, которое подтвердило правильность разработанных методов управления задачами и построения виртуальной памяти ВСАРР.

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

Список работ, опубликованных по теме диссертации

1. A.C. Окунев. Проблемы применения серийно выпускаемых микросхем при макетировании вычислительной системы с автоматическим распределением ресурсов. Международная научно-практическая конференция «Искусственный интеллект - 2004. Интеллектуальные и многопроцессорные системы - 2004. пос. Кацивели, Крым, 2004» // Материалы Международной научно-технической конференции, т.1, Таганрог - Донецк, 2004, стр. 66-69.

2. A.C. Окунев, H.H. Левченко. Методы аппаратной реализации многовходовых узлов вычислительной системы с автоматическим распределением ресурсов // Научно-теоретический журнал «Искусственный интеллект» 3, 2004 1ППП «Наука i освгга», 2004, стр. 149-156 (автору диссертации принадлежит описание аппаратной реализации многовходовых узлов в вычислительной системе и разработка формата «М-токена»).

3. H.H. Левченко, A.C. Окунев. Аппаратно-программная реализация условных конструкций в вычислительной системе с автоматическим распределением ресурсов // Международная научно-практическая конференция «Искусственный интеллект - 2004. Интеллектуальные и многопроцессорные системы - 2004. пос. Кацивели, Крым, 2004» // Материалы Международной научно-технической конференции, т.1, Таганрог - Донецк, 2004, стр. 153-156 (автором диссертации дано описание аппаратной реализации условных конструкций в вычислительной системе).

4. A.C. Окунев. Возможности использования IP-сопроцессора фирмы ЮТ в качестве памяти совпадений при макетировании вычислительной системы, управляемой потоком данных. Проблемы и методы информатики. П научная сессия Института проблем информатики Российской академии наук, Москва, ИЛИ РАН, 2005, стр. 209-211.

5. H.H. Левченко, A.C. Окунев. Вопросы аппаратно-программной реализации условных конструкций в вычислительной системе, управляемой потоком данных //«Проблемы и методы информатики». II научная сессия Института проблем информатики Российской академии наук, Москва, ИЛИ РАН, 2005, стр. 203-206 (автору диссертации принадлежит описание аппаратуры для реализации условных конструкций и разработка новых типов токенов).

6. H.H. Левченко, A.C. Окунев, Г.О. Чумаченко, И.К. Хайлов. Варианты аппаратной поддержки многовходовых узлов в вычислительной системе с автоматическим распределением ресурсов // Проблемы и методы информатики. П научная сессия Института проблем информатики Российской академии наук, Москва, ИЛИ РАН, 2005, стр. 206-208 (автору диссертации принадлежат результаты, относящиеся к первому варианту аппаратной реализации многовходовых узлов в ассоциативной памяти вычислительной системы, а также - разработка формата «М-токена»),

7. A.C. Окунев. Об одном методе подсчета глобальной кратности в вычислительной системе с автоматическим распределением ресурсов/«Методы и средства обработки информации». Труды второй Всероссийской научной конференции/ - М.: Издательский отдел факультета ВМиК МГУ им. М.В. Ломоносова, 2005, стр. 282-287.

8. A.C. Окунев, H.H. Левченко. Некоторые вопросы обеспечения

отказоустойчивости и реконфигурация в вычислительной системе с автоматическим распределением ресурсов/ Методы и средства обработки информации. Труды второй Всероссийской научной конференции/ - М.: Издательский отдел факультета ВМиК МГУ им. М.В. Ломоносова, 2005, стр. 478-483 (автору диссертации принадлежит описание первого варианта восстановления системы после сбоя).

9. A.C. Окунев, Е.С. Градов, H.H. Левченко Исследование вариантов обеспечения отказоустойчивости и реконфигурация в вычислительной системе с автоматическим распределением ресурсов // Научно-теоретический журнал «Искусственный интеллект» 4, 2005 ГГТТНТ «Наука i освгга», 2005, стр. 230-239 (автору диссертации принадлежит описание механизма восстановления системы после сбоя с использованием буферных регистров).

10. Е.С. Градов, A.C. Окунев, H.H. Левченко. Аппаратная реализация механизма восстановления исполнительных устройств после сбоя или отказа в вычислительной системе с автоматическим распределением ресурсов // Интеллектуальные и многопроцессорные системы 2005. Материалы Международной научной конференции. Т.1. - Таганрог: изд-во ТРТУ, 2005, стр. 253-259 (автору диссертации принадлежат результаты, относящиеся к первому варианту аппаратной реализации механизма восстановления системы после сбоя).

11. A.C. Окунев. Аппаратно-программные средства управления в вычислительной системе с автоматическим распределением ресурсов. // Интеллектуальные и многопроцессорные системы 2005. Материалы Международной научной конференции. Т.1. - Таганрог: изд-во ТРТУ, 2005. стр. 259-263.

12. A.C. Окунев Классификация команд управления в вычислительной системе с автоматическим распределением ресурсов // Системы и средства информатики. Специальный выпуск. Методы и средства разработки информационно-вычислительных систем и сетей. Москва, ИЛИ РАН, 2005 (в печати).

Список сокращений

№ад. - номер задачи

АЗУ - ассоциативное запоминающее устройство

АП - ассоциативная память

Асл. - адрес программы узла в памяти команд

БГП - буфер готовых пар

ВСАРР - вычислительная система с автоматическим распределением ресурсов

ВУ - вычислительный узел (кольцо)

ИИК - инструментальный испытательный комплекс

ИУ - исполнительное устройство

КМ - коммутатор

МАП - модуль ассоциативной памяти

МООЗУ - модуль ООЗУ

ООЗУ - общее оперативное запоминающее устройство

ПБРМ - программная блочно-регистровая модель

ЦУУП - центральное устройство управления памятью

Принято к исполнению 20/10/2005 Исполнено 21/10/2005

Заказ № 1162 Тираж: 100 экз.

ООО «11-й ФОРМАТ» ИНН 7726330900 Москва, Варшавское ш., 36 (095) 975-78-56 (095) 747-64-70 www.autoreferat.ra

* 190 96

РНБ Русский фонд

2006-4 15131

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЗОР ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ НЕТРАДИЦИОННОЙ АРХИТЕКТУРЫ, ВЫЧИСЛИТЕЛЬНЫЙ ПРОЦЕСС В КОТОРЫХ УПРАВЛЯЕТСЯ ПОТОКОМ ДАННЫХ.

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

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

1.3. Проблема переполнения памяти токенов в вычислительных системах, управляемых потоком данных и способы ее решения.

1.3.1. Основные причины переполнения памяти совпадений.

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

1.3.2.1. Принципы управления распределением ресурса памяти в проекте MIT TTDA.

1.3.2.2. Методы ограничения параллелизма программ в проекте MDFM.

Выводы к первой главе.

ГЛАВА 2. РАЗРАБОТКА МЕТОДОВ ПРЕОДОЛЕНИЯ ПЕРЕПОЛНЕНИЯ АП ВСАРР И РЕАЛИЗАЦИЯ ВИРТУАЛЬНОЙ ПАМЯТИ ТОКЕНОВ.

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

2.1.1. Представление информации в ВСАРР.

2.1.2. Общая структура ВСАРР.

2.1.3. Функционирование отдельных устройств ВСАРР.

2.2. Исследование проблемы переполнения ассоциативной памяти ВСАРР и методы ее решения.

2.2.1. Основные причины переполнения ассоциативной памяти.

2.2.2. Методы решения проблемы переполнения ассоциативной памяти ВСАРР.

2.3. Построение иерархии памяти ВСАРР.

2.3.1. Использование буферов токенов и пар в ВСАРР.

2.3.2. Блокировка вычислительного процесса в ВСАРР.

2.3.2.1. Блокировка вычислительного процесса в результате переполнения буферов токенов и пар.

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

2.3.3. Построение иерархии памяти ВСАРР.

2.3.4. Статистика.

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

2.4.1. Механизм реализации виртуальной памяти токенов.

2.4.2. Аппаратная поддержка многозадачного режима работы системы.

2.4.2.1. Многозадачный режим работы без подзадач.

2.4.2.2. Многозадачный режим работы с включением номера подзадачи в ключ

2.4.2.3. Многозадачный режим работы с использованием областей.

2.4.2.4. Алгоритм работы ЦУУП по откачке и подкачке токенов.

2.5. Аппаратно-программные методы регулирования параллелизма в ВСАРР.

Выводы ко второй главе.

ГЛАВА 3. АЛГОРИТМЫ ВЫПОЛНЕНИЯ КОМАНД УПРАВЛЕНИЯ ЗАДАЧАМИ И РАБОТЫ ЦУУП, РЕАЛИЗУЮЩИХ МНОГОЗАДАЧНЫЙ РЕЖИМ РАБОТЫ СИСТЕМЫ И ВИРТУАЛЬНУЮ ПАМЯТЬ ТОКЕНОВ.

3.1. Специальные команды управления задачами.

3.1.1. Описание команд управления задачами и их классификация.

3.1.2. Алгоритмы выполнения команд управления задачами.

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

3.2. Структура и режимы функционирования ЦУУП.

3.2.1. Основные функциональные блоки ЦУУП.

3.2.2. Взаимодействие ЦУУП с адаптером ООЗУ и модулями АП.

3.2.3. Основные режимы работы ЦУУП.

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

3.3.1. Аппаратная поддержка механизма подсчета глобальной кратности.

3.3.2. Аппаратная поддержка многовходовых узлов.

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

Выводы к третьей главе.

ГЛАВА 4. ИССЛЕДОВАНИЕ ФУНКЦИОНИРОВАНИЯ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ НА ИНСТРУМЕНТАЛЬНОМ ИСПЫТАТЕЛЬНОМ КОМПЛЕКСЕ ВСАРР.

4.1. Имитационная модель системы.

4.2. Программная блочно-регистровая модель системы.

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

4.3.1. Описание задач, на которых проводились исследования.

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

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

4.4.1. Структура макета ВСАРР и конструктивные решения для него.

4.4.2. Перспективы развития макета ВСАРР.

Выводы к четвертой главе.

Актуальность темы диссертации

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

Для решения этих задач требуются суперкомпьютеры с реальной производительностью 1012-1016 операций в секунду. Причем с каждым годом требования, предъявляемые к вычислительной технике, на которой решаются подобные задачи, возрастают [8,12,16].

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

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

- временные потери, возникающие при обмене данными между процессорами.

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

В Англии, США и Японии проводились исследования архитектур, в которых вычислительный процесс управляется потоком данных [35,40,41,46,59]. Особенностью таких архитектур является возможность одновременного выполнения всех операций, для которых в данный момент готовы операнды, что обеспечивает предельную степень параллелизма, имеющегося у конкретной задачи. Однако, результаты данных исследований, не нашли широкого применения. Одной из причин являлось то, что не были решены вопросы создания виртуальной памяти и поддержки работы в многозадачном режиме [45].

В отделе «Проблем построения информационно-вычислительных систем высокого параллелизма» Института проблем информатики Российской академии наук под руководством академика [B.C. Бурцева] разработаны новые принципы организации вычислительного процесса и на их основе спроектирована вычислительная система с автоматическим распределением ресурсов, использующая модель вычислений, управляемых потоком данных с динамически формируемым контекстом вычислений. В настоящее время работа над данным проектом продолжается [7].

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

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

Для достижения поставленной цели в работе решаются следующие основные задачи:

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

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

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

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

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

Объект и предмет исследования

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

Методы исследования

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

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

Основные научные результаты работы состоят в следующем:

1. На основе проведенного анализа архитектуры ВСАРР разработаны методы организации работы системы в многозадачном режиме.

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

3. Впервые разработаны подходы к созданию ВСАРР, работающей в реальном масштабе времени, обеспечивающие восстановление работоспособности системы с контрольных точек и обработку прерываний, возникающих при сбоях и отказах отдельных устройств.

4. Впервые разработана структура и принципы функционирования центрального устройства управления памятью (ЦУУП), обеспечивающего выполнение специальных команд управления задачами, организацию виртуальной памяти и взаимодействие ВСАРР с операционной системой.

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

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

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

Практическая значимость

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

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

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

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

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

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

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

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

Положения, выносимые на защиту

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

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

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

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

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

Реализация результатов работы

Новые теоретические положения и технические решения апробированы на инструментальном испытательном комплексе ВСАРР. Результаты работы реализованы в Институте проблем информатики РАН (ИПИ РАН) в отделе «Проблем построения информационно-вычислительных систем высокого параллелизма» при исследовании и разработке вычислительной системы с автоматическим распределением ресурсов и при реализации проекта по созданию макета вычислительной машины данной архитектуры. Апробация работы

Основные положения и результаты работы докладывались и обсуждались на научных семинарах в ИПИ РАН в 1999-2005 гг., а также на конференциях и научных форумах: на международной конференции «Информационные технологии в науке, образовании, телекоммуникации, бизнесе» (г. Гурзуф, 2001), на международной научно-технической конференции «Интеллектуальные и многопроцессорные системы ИМС'2003» (пос. Дивноморское, 2003), на международной научно-практической конференции «Искусственный интеллект

2004. Интеллектуальные и многопроцессорные системы - 2004» (пос. Кацивели, Крым, 2004), на «II Научной сессии Института проблем информатики Российской академии наук: Проблемы и методы информатики» (Москва, 2005), на международной научно-технической конференции «Интеллектуальные и многопроцессорные системы ИМС'2005» (пос. Дивноморское, 2005), на второй Всероссийской научно-технической конференции «Методы и средства обработки информации МСО-2005» (Москва, 2005).

Некоторые решения, созданные в рамках диссертации в виде имитационной модели, демонстрировались на Всемирной выставке по информационным технологиям CeBIT-2003, Ганновер, Германия.

Исследование разработанных методик, алгоритмов и схемотехнических решений проводилось в Институте проблем информатики РАН на инструментальном испытательном комплексе. Структура и объем диссертации

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

Основные результаты диссертационной работы

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

2. На основе проведенных исследований ВСАРР предложены методы решения проблемы переполнения ассоциативной памяти.

3. Проведены исследования, связанные с построением иерархии памяти ВСАРР.

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

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

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

7. Исследовано прохождение ряда программ на инструментальном испытательном комплексе, которое подтвердило правильность разработанных методов управления задачами и построения виртуальной памяти ВСАРР.

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

ЗАКЛЮЧЕНИЕ

Дальнейшие исследования целесообразно вести в следующих направлениях:

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

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

1. Антонов А.П. «Язык описания цифровых устройств AlteraHDL. Практический курс», - М.: ИП РадиоСофт, 2001.

2. Антонов А.П., Мелехин В.Ф., Филиппов А.С. Обзор элементной базы фирмы Altera. СПб.: Файнстрит, 1997.

3. Березко A.M. Новые концепции в архитектуре потоковых машин с тегированием данных // Отчет отдела системного программирования ВЦКП РАН. М.:1991.

4. Березко A.M. Принципы действия и архитектура манчестерской потоковой машины//Отчет по теме «Анализ современного состояния архитектур вычислительных машин потока данных». М., 1988.

5. Бурцев B.C. Выбор новой системы организации выполнения высокопараллельных вычислительных процессов, примеры возможных архитектурных решений построения суперЭВМ // Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ. М.: 1997. -С.41.

6. Бурцев B.C. Научная школа академика С.А. Лебедева в развитии вычислительной техники // С.А. Лебедев. К 100-летию со дня рождения основоположника отечественной электронной вычислительной техники. Отв. ред. B.C. Бурцев. М.: ФИЗМАТЛИТ, 2002. С. 238-252.

7. Бурцев B.C. Новые принципы организации вычислительных процессов высокого параллелизма // Материалы Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы 2003». Т.1. Таганрог: Изд-во ТРТУ, 2003.

8. Бурцев B.C. О необходимости создания суперЭВМ в России//Сб. статей «Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ», М., 1997

9. Бурцев B.C. Перспективы развития вычислительной техники//Сб. статей «Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ. МВК Эльбрус». М., 1998.

10. Бурцев B.C. Система массового параллелизма с автоматическим распределением аппаратных средств суперЭВМ в процессе решения задачи //

11. Сб. Вычислительные машины с нетрадиционной архитектурой. СуперЭВМ. -Вып. 2. М.: ВЦКП РАН, 1994. - С.3-37.

12. Бурцев B.C., «Тенденции развития высокопроизводительных систем и многопроцессорные вычислительные комплексы», в сб.статей «Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ. МВК Эльбрус», Москва, 1998.

13. Воеводин В.В. Суперкомпьютеры: вчера, сегодня, завтра. // Сборник научно-популярных статей «Российская наука на заре нового века». Под ред. академика В.П. Скулачева. М.: научный мир, 2001. С. 475-483.

14. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002.

15. Каляев А.В., Левин И.И. Многопроцессорные системы с перестраиваемой архитектурой. Концепция развития и применения // Наука производству. -1999.-№11.-С. 11-18.

16. Комолов Д.А. и др. САПР фирмы Altera МАХ + Plus II и Quartus П//РадиоСофт. 2002.

17. Корнеев В.В. Архитектуры с распределенной разделяемой памятью // Открытые Системы. 2001. - №3. - С.15-23.

18. Мокрушин JI.A. Концепция компьютеров потока данных: Обзор-реферат. // Л.: ЛЭТИ, каф. ИИТ, 1990

19. Окунев А.С., Левченко Н.Н. Методы аппаратной реализации многовходовых узлов вычислительной системы с автоматическим распределением ресурсов // Научно-теоретический журнал «Искусственный интеллект» 3, 2004 1ПШ1 «Наука i освгга», 2004, стр. 149-156.

20. Разевиг В.Д. Система проектирования цифровых устройств OrCAD. -М.:"Солон-Р", 2000.

21. Стешенко В.Б. «ПЛИС фирмы ALTERA: проектирование устройств обработки сигналов.», М.: Додэка, 2000.

22. Стешенко В.Б. ПЛИС фирмы "Altera": Элементная база, система проектирования и языки описания аппаратуры. М.: "Додэка-XXI", 2002.

23. Угрюмов Е.П. Цифровая схемотехника. 2-е изд., перераб. и доп., BHV, 2004.

24. Фортов В.Е., Левин Вл.К., Савин Г.И., Забродин А.В., Каратанов В.В., Елизаров Г.С., Корнеев В.В., Шабанов Б.М. Суперкомпьютер МВС-ЮООМ и перспективы его применения. // Наука и промышленность России. 2001. -№11. -С. 49-52.

25. Хетагуров Я.А. Основы проектирования управляющих вычислительных систем. М.: Радио и связь, 1991.

26. Шабанов Б.М., Яицков А.С. VHDL язык описания аппаратуры. Учебное пособие. Москва, МИЭТ, 2003.

27. Altera Corporation. APEX 20К Programmable Logic Device Family. Data Sheet. August 1999. ver.2.02.

28. Altera Corporation. Stratix device handbook. Volume 1. May 2003.

29. Arvind, Dahbura A.T., Caro A. Computer Architecture Research and the Real World//Computation Structures Group Memo 397, MIT Laboratory for Computer Science, Cambridge, MA, 1997, April 23.

30. Arvind, Nikhil R.S. Executing a program on the MIT tagged-token dataflow architecture//Lect. Notes Comput. Sc. 259 (1987). P. 1-29.

31. Arvind, Nikhil R.S., Executing a program on the MIT Tagged-Token Dataflow Architecture/ЛЕЕЕ Transactions of computers. 1990. March. V. 39, no. 3.

32. Arvind, Stephen Brobst. The evolution of dataflow architectures: from static dataflow to P-RISC/TInternational Journal of High Speed Computing. 1993. V. 5, no. 2. P. 125-153.

33. Arvind, Thomas R.E. I-structures: An efficient data type for parallel machines//Tech. Rep. TM 178, Computat. Structures Group, MIT Lab. for Comput. Sci., 545, Technology Square, Cambrige, MA 02139. 1980. Sept.

34. Barrington D.A., Culler D.E. DATAFLOW ARCHITECTURES//MIT Laboratory for Computer Science, 1986, February 2.

35. Ben Lee, Hurson A. R. Dataflow Architectures and Multithreading//Computer. 1994. Aug. V. 27, no. 8. P. 27-39.

36. Computing, ed. L. Bic and J.-L. Gaudiot, Prentice Hall, 1991. P.35-91

37. Culler D., Papadopoulos G. The Explicit Token Store//Journal of parallel and distributed computing. 1990. № 10. P. 289-308.

38. Culler D.E. Resource Management for the Tagged Token Dataflow Architecture//MIT. 1980. Jan.

39. David E. Culler, Klaus E. Schauser, and Thorsten von Eicken. Two Fundamental Limits on Dataflow Multiprocessing // IFIP WG 10-3 Parallel Architectures and Compilation Techniques, Jan 1992.

40. Dennis J., Data Flow Supercomputers // Computer. Vol.13. - No.l 1. Nov, 1980. -P.48-56

41. Dennis J., Misunas D. A preliminary Architecture for Basic Data-Flow Processor//Project MAC, MIT, Houston, TX. 1975. Jan. P. 126-132.

42. Dennis J.B. The Evolution of «Static» Data-Flow Architecture//Advanced Topics in Dataflow Computing, ed. Bic L. and Gaudiot J.-L., Prentice Hall, 1991.

43. Feo J.T., Cann D.C., Oldehoeft R.R. A Report on the SISAL Language Project//Journal of Parallel and Distributed Computing, 10:349-366. 1990. Dec.

44. Gravlen 0. «The Evolution of Dataflow Computers Project Paper for 45214 Computer Architecture». University of Trondheim, 1994.

45. Gurd J. R., Kirkham С. C., Watson I. The Manchester Prototype Dataflow Computer//In S. S. Thakkar, editor, Selected Reprints on Dataflow and Reduction Architectures. IEEE Computer Society Press, Los Alamitos, CA, 1987. P. 111-129.

46. Gurd J.R. The Manchester dataflow machine//Future Generations Computer Systems 1. 1985. P. 201-212.

47. Herath J., Yamaguchi Y., Saito N., Yuba T. Dataflow Computing Models, Languages, and Machines for Intelligence Computations//IEEE Transactions on Software Engineering. 1988. Dec. V. 14, no. 12.

48. Hiroshi Nagase, Masakuni Kameya, Takashi Kawanami, Tomoki Shiono. Dataflow Computer which Accelerates Execution of Sequential Programs by Firing Instruction Precedently//System and Computers in Japan. 2002. V. 33, no. 9. P. 6877.

49. Iannucci R. Toward a Dataflow/von Neumann Hybrid Architecture//In 15th Annual International Symposium on Computer architecture. 1988. P. 131-140.

50. Jagannathan R., Dataflow Models//Parallel and Distributed Computing Handbook:

51. Editor Zomaya E.Y., McGraw-Hill, 1996.

52. Kahaner D.K. Parallel processing research in Japan//Supplement. 1991. May.

53. Kaufmann M. Computer Architecture. A Quantitative Approach, 3rd Edition, 2002.

54. Michael L. Dertouzos. The Future of Computing//Scientific American. 1999. August 19.

55. Nikhil R.S. Dataflow Programming Languages//The 13th IMACS World Congress on Computation and Applied Mathematics, Trinity College, Dublin, Ireland, July 22-26, 1991.

56. Null L., Lobur J. The essentials of computer organization and architecture//Jones and Bartlett Publishers, Inc. 2003.

57. Papadopoulos G.M., Traub K.R. Multithreading: A revisionist view of dataflow architectures/An Proceedings of the 18th Annual International Symposium on Computer Architecture//IEEE Computer Society. 1991. P. 342-351.

58. Papadopoulos M., Culler D. Monsoon: an Explicit Token-Store Architecture//Proc. of 17th Intl. Symposium on Computer Architecture (ISCA-17), May 1990. P. 82-91.

59. Robic В., Silc J., Ungerer T. Beyond dataflow//.!. Computing and Information Technology, 8(2):89-101. 2000.

60. Saphir W., Woo A., Yaroww M. The NAS Parallel Benchmark 2.1 Results//Report NAS-96-010, August 1996.

61. Shimada Т., Hiraki K., Sekiguchi S. A Dataflow Supercomputer for Scientific Computations: The SIGMA-1 System//Translated into English by Eoyang C, and published in The Institute for Supercomputing Research Vector Register, 11.15. 1988. P. 3-9.

62. Silc J., Robic B. Did Processor Architecture Make the Best of Dataflow?//PDPTA'2000.

63. Silc J., Robic В., Ungerer T. Asynchrony in parallel computing: From dataflow to multithreading//Parallel and Distributed Computing Practices. 1998. 1(1): 3-30.

64. Toshitsugu Yuba, Toshio Shimada, Yoshinori Yamaguchi, Kei Hiraki, Shuichi

65. Sakai. Dataflow computer development in Japan//4th International Conference on Supercomputing, Amsterdam, The Netherlands, 1990.

66. Traub K.R., Popadopoulos G.M., Beckerle M.J., Hicks J.E., Young J. Overview of the Monsoon Project//Proceedings of the 1991 IEEE International Conference on Computer Design, Cambridge, MA. 1991. Oct.

67. Veen A.H. Dataflow machine architecture//ACM Computing Surveys (CSUR). 1986. Dec. V. 18, Issue 4.

68. W. Ackerman. Data flow languages. IEEE Comput. 15, 2, 15—25, 1982.

69. Watson I., Gurd J.R. A prototype data flow computer with token labeling//Proc. National Сотр. Conf., Jun. 1979. P. 623-628.

70. Yamaguchi,Y. SakaiS. An Architectural Design of a Highly Parallel Dataflow Machine//To appear in IFIP'89. 1989.

71. Yuba Toshitsugu. Research and Development Efforts on Dataflow Computer Architecture in Japan//Journal of Information Processing Abstract. 2002. V. 09, no. 02.1. ПЕРЕЧЕНЬ СОКРАЩЕНИЙад. номер задачи1. ТЧподзад. номер подзадачи

72. АЗУ ассоциативное запоминающее устройство1. АП ассоциативная память

73. АТЗ аппаратная таблица задач

74. АТЗиП аппаратная таблица задач и подзадач

75. АТП аппаратная таблица подзадач

76. МАП модуль ассоциативной памяти

77. Асл. адрес программы узла в памяти команд1. БГП буфер готовых пар

78. ВСАРР вычислительная система с автоматическим распределением ресурсов

79. ВУ вычислительный узел (кольцо)

80. ИИК инструментальный испытательный комплекс

81. ИУ исполнительное устройство1. КМ коммутатор

82. ООЗУ общее оперативное запоминающее устройство1. МООЗУ модуль ООЗУ

83. ПБРМ программная блочно-регистровая модель

84. ЦУУП центральное устройство управления памятью

85. AHDL Altera HDL язык функционального описания электронных структур

86. MDFM Manchester Data-Flow Machine

87. MIT Массачусетский технологический институт

88. MIT TTDA MIT Tagged-Token Dataflow Machine

89. VHDL Very high speed integrated circuit Hardware Description Languageязык функционального описания электронных структур1. КОП код операции

90. НМД накопитель на магнитном диске1. ОС операционная система1. ПК память команд1561. Пконст. память констант

91. ПЛИС программируемые логические интегральные схемы

92. ПО программное обеспечение1. Прасш. память расширения1. ПЭ процессорный элемент

93. САПР система автоматизированного проектирования

94. ТЭЗ типовой элемент замены1. УУ устройство управления