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

Чумаченко, Георгий Олегович

Вычислительные машины и системы

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

кандидата технических наук: Чумаченко, Георгий Олегович
город: Москва
год: 2005
специальность ВАК РФ: 05.13.15

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

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

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

Чумаченко Георгий Олегович

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

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

АВТОРЕФЕРАТ

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

Москва - 2005

Работа выполнена в Институте проблем информатики РАН.

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

Всеволод Сергеевич Бурцев

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

доктор технических наук, профессор, член-корреспондент РАН, Юрий Иванович Митропольский

кандидат технических наук,

доцент МИФЩгосударственный университет),

Александр Леонидович Зорин

Ведущая организация:

Институт точной механики и вычислительной техники им. С.А. Лебедева

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

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

Автореферат разослан " % " г.

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

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

профессор (у С.Н. Гринченко

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

Актуальность темы

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

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

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

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

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

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

Для эффективной организации параллельных вычислений в гибридной динамической модели с ДФК должен присутствовать ряд механизмов, с помощью которых программист имеет возможность эффективного управления параллельными вычислительными процесса;» Г^щш^ЩЩ^^^^аюш механизмам

«отлипал i

КИ&ДПОТЕКА. I

■ 141 л Л

относятся механизм управления потока данными, механизм сборки «мусора» и событийный механизм.

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

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

Целью диссертационной работы является исследование и разработка принципов эффективного функционирования механизмов управления параллельными вычислительными процессами гибридной динамической модели с ДФК с использованием ассоциативной памяти.

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

1. Исследование принципиально новой модели вычислений - гибридной динамической модели с ДФК.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• проведен анализ механизмов управления параллельными вычислительными процессами рассматриваемой модели, на основе которого впервые предложено реализовать данные механизмы на аппаратном уровне при помощи системы команд АП, выполняемых Блоком управления АП;

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

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

• разработана структура и принципы функционирования Блока управления модуля АП;

• разработанные аппаратные решения реализованы в макете модуля АП, входящего в состав макета ВСАРР;

• разработанная система команд АП используется в поведенческой модели ВСАРР;

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

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

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

1. Разработанные в диссертационной работе принципы аппаратной

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

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

2. Разработанная в диссертационной работе система команд АП вошла в систему команд ВСАРР, которая является практической реализацией основных принципов гибридной динамической модели с ДФК.

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

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

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

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

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

3. Созданный с применением ПЛИС макет Блока управления модуля АП, входящий в состав макета ВСАРР.

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

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

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

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

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

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

Публикации

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

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

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

Работа изложена на 142 страницах машинописного текста, включая 39 рисунков и 10 таблиц.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- жесткое закрепление ячеек памяти токенов(памяти фреймов) за каждой активацией функции;

- неопгимальные алгоритмы распределения параллельных вычислительных процессов по процессорным элементам;

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

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

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

На протяжении последних нескольких лет под руководством академика 1В.С. Бурцева! ведется разработка принципиально новой архитектуры потока данных - ВСАРР, в основу которой положена гибридная динамическая модель с ДФК. Данная модель обладает принципиально новыми свойствами, позволяющими организовывать параллельные вычисления без накладных расходов, свойственных другим моделям вычислений, управляемых потоком данных. '

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

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

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

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

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

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

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

Кратность токена определяет количество раз(п), которое токен может провзаимодействоватъ с множеством токенов, поступающих на противоположные входы активаций узлов и инициировать их выполнение. Каждое взаимодействие одного токена с другим приводит к тому, что его кратность уменьшается на величину, равную значению кратности совпавшего с ним по ключу второго токена. Если в результате взаимодействий с другими токенами кратность токена становится равной 0, то токен прекращает свое существование. Токен может быть однократным(п=1), многократным(1<го*») и с бесконечной кратностью(п=со).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таким образом, в данной диссертации считается, что АП состоит из двух частей(рис.1)\

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

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

Рисунок 1. Функциональная схема ассоциативной памяти

* Поэтому, в дальнейшем по тексту, говоря о выполнении некоторых

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

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

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

4. Команда «Подсчет количества событий». При помощи данной команды реализуется событийный механизм, заключающийся в подсчете количества токенов с определенным ключом, отображающих факт совершения события заданного типа

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

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

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

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

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

Таблица 1. Комбинации токенов, инициирующие команды АП

Команда Первый токен Второй токен

«Синхронизация запуска подпрограммы узла по входным данным» «Стандартный» «Стандартный»

«Безразличный» «Безразличный»

«Аппаратная косвенная переадресация токена» «Аппаратная косвенность» «Стандартный», «Безразличный»

«Аппаратно-программная косвенная переадресация токена» «Аппаратно-программная косвенность» «Стандартный», «Безразличный»

«Стирание токена» «Стирание» «Стандартный», «Безразличный», «Событие», «Счетчик», «Аппаратная косвенность», «Аппаратно-программная косвенность»

«Чистка АП» «Чистка»(может быть только верхним токеном) «Стирание», «Стандартный», «Безразличный», «Событие», «Счетчик», «Аппаратная косвенность», «Аппаратно-программная косвенность»

«Подсчет количества событий» «Счетчик» «Событие»

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

Таблица 2. Принципы взаимодействия токеяов с различным значением кратности

Первый токен Второй токен Количество выполняемых команд

Однократный Однократный Одна одиночная команда АП

Однократный Многократный Одна одиночная команда АП

Многократный Многократный п одиночных команд АП, где п - наименьшее значение кратности одного из токенов

Многократный С бесконечной кратностью п одиночных команд АП, где п - значение кратности многократного токена

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

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

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

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

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

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

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

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

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

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

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

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

о коммутаторы пар и токенов, которые соединяют между собой

исполнительные устройства и модули ассоциативной памяти о общее оперативное запоминающее устройство(ООЗУ) и его

адаптеры о ХОСТ-машина

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

| гим'ш.

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

Коммутатор пар

§ |

Коммутатор токенов

Адаптер ООЗУ

Адаптер Адаптер

ООЗУ ООЗУ

Коммутатор модулей ООЗУ

Модуль ООЗУ

Модуль

ООЗУ

Модуль

ООЗУ

Хост-машина

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

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

Для обеспечения необходимой пропускной способности АП ВСАРР строится по модульному принципу. Количество модулей АП определяется по формуле

\Г Т"> - ^ЛП - ^ВСАРР

М илп ~~ ,

ТшП ^ АЗУ ^тм хзу

где Тш - требуемый темп работы АП, пар/сек;

Рцсарр - совокупная производительность ВСАРР, оп/сек;

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

Тшп = тЛЗУ - физически возможный темп работы одного МАЛ, пар/сек;

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

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

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

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

выполнение разнообразных сервисных функций;

Аппаратную поддержку выполнения описанных выше функций осуществляет Микропроцессор регуляции параллелюма(}ШРЩ.

Для выполнения перечисленных выше функций в качестве буферной памяти используется общее оперативное запоминающее устройство^ООЗУ). Обращение к ООЗУ ведется через Адаптеры ООЗУ, которые выполняют специальные управляющие команды, выдаваемые МПРП.

С точки зрения производительности и особенностей выполнения команд АП Блок ассоциативного сравнения АЩрисунок 1)должен отвечать следующим требованиям:

- должен осуществлять выполнения операции поиска с максимально возможной скоростью, так как темп проведения операции поиска определяет темп выполнения команд в МАП и напрямую влияет на загрузку ИУ

- должен поддерживать проведение операции поиска с учетом масок как верхнего, так и нижних токенов.

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

Всем данным характеристикам лучше всего отвечает Блок ассоциативного сравнения, построенный на основе аппаратного ассоциативного запоминающего устройства^АЗУ).

Идея применения в памяти токенов АЗУ для сравнения тэгов токенов в ИКС архитектуры потока данных неоднократно выдвигалась ранее в 70-80-е годы XX столетия, однако в рассматриваемый период АЗУ обладали малыми объемами, низкой скоростью работы и высокой стоимостью.

На современном этапе развития микроэлектронной промышленности многие компании по производству электронных компонентов(ГОТ, Mosaid Semiconductors, Motorola и др.) наладили выпуск телекоммуникационных сопроцессоров, также называемых IP-сопроцессорами, которые фактически являются АЗУ с введенным в них специализированным управлением.

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

Структура и общие принципы функционирования МАП

Общая структурная схема МАП представлена на рисунке 4.

Рисунок 4. Структурная схема МАП.

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

Кратко рассмотрим последовательность обработки токена в конвейере МАП, а также назначение основных блоков МАП.

Токены, посылаемые от ИУ через коммутатор токенов на вход МАПа, поступают во Входной блок МАЩВБ МАП). Основным назначением ВБ МАП является коммутация двух потоков токенов, поступающих на вход МАП от коммутатора токенов и от Регистрового буфера токенов с прерванным откликом(РБТПО), в единый входной поток токенов.

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

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

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

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

Блок выполнения команд(БВК) является одним из центральных блоков МАП. Именно в нем происходит выполнение алгоритмов всех команд АП. БВК дешифрирует типы полученных верхнего и нижнего токенов и на основе результата дешифрации выполняет соответствующую команду. В зависимости от выполняемой команды БВК производит следующие действия:

- изменяет кратность верхнего токена или инициирует его стирание;

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

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

Если в результате выполнения команды кратность нижнего токена не стала равна 0, то БВК инициирует перезапись кратности этого нижнего токена в ОЗУ(п токена). Если в результате выполнения команды верхний токен не был стерт или

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

Принцип прерывания обработки множественного отклика

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

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

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

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

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

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

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

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

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

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

Размерность матриц Количество колец(пар ИУ-МАП) в системе Количество тактов, затраченных на выполнение программы Средняя загрузка ИУ

10x10 32 736 92%

20x20 32 5526 99%

30x30 32 18553 99%

40x40 32 43947 100%

50x50 32 85829 100%

Таблица 4. Результаты выполнения программы умножения матриц с использованием команд АП «Стирание токена» и «Аппаратно-программная косвенная переадресация гокена»

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

10x10 32 628 92% 14,67%

20x20 32 4622 98% 16,36%

30x30 32 15401 99% 16,99%

40x40 32 36346 100% 17,30%

50x50 32 70824 100% 17,48%

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

Размерность массива А Количество колец(пар ИУ-МАП) в системе Количество тактов, затраченных на выполнение программы Средняя загрузка ИУ

20 4 1128 91%

40 4 4283 98%

60 4 9612 99%

80 4 17113 99%

100 4 26430 100%

Таблица 6. Результаты выполнения программы пузырьковой сортировки с использованием команды АП «Аппаратно-программная косвенная переадресация токена»

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

20 4 680 92% 39,72%

40 4 2460 98% 42,56%

60 4 5391 99% 43,91%

80 4 9461 99% 44,71%

100 4 14786 100% 44,06%

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

Из таблиц 3-6 видно, что загрузка исполнительных устройств близка к 100%, что обеспечивает выполнение программы на заданной конфигурации за минимальное время. Данный факт говорит, что заложенные в гибридной динамической модели с ДФК принципы организации параллёльных вычислительных процессов позволяют создавать максимально параллельные программы, с большим количеством параллельных вычислительных процессов, что гарантирует постоянную загрузку работой процессорных элементов -исполнительных устройств.

Кроме этого, данные, приведенные в таблицах 3-6, показывают, что применение в программах команд АП, аппаратно реализующих все основные

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

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

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

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

a. накладные расходы на выделение контекста для параллельной активации функции;

b. жесткое закрепление ячеек памяти токенов(памяти фреймов) за каждой активацией функции;

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

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

3. Проведен анализ механизмов управления параллельными вычислительными процессами гибридной динамической модели с ДФК, на основе которого впервые предложено реализовать данные механизмы на аппаратном уровне в Блоке управления АЛ.

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

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

6. Исследована структура и основные принципы функционирования ВСАРР, в составе которой АП играет центральную роль.

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

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

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

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

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

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

1. Чумаченко Г.О., Долгов A.B., Белялев A.B. Параллельные вычисления в локальных сетях // "XXVII Гагаринские чтения". Тезисы докладов Международной молодежной научной конференции. Том 5., - М.: Латмэс, 2001, с. 85.

2. Чумаченко Г.О. Применение технологии отложенных токенов для организации иерархии памяти суперпроцессора нетрадиционной архитектуры // Интеллектуальные и многопроцессорные системы 2003. Материалы Международной научной конференции. Т.1. - Таганрог: изд-во ТРТУ, 2003. С. 203-206.

3. Чумаченко Г.О. Технология отложенных токенов для преодоления ситуаций блокировки по переполнению буферов в суперпроцессоре нетрадиционной архитектуры // Методы и средства обработки информации 2003. Труды Первой Всероссийской научной конференции. - М.: Московский государственный университет ми. М.В. Ломоносова, 2003, с. 157

4. Чумаченко Г.О. Проблемы управления ресурсом АП в вычислительных системах потока данных // Системы и средства информатики. Специальный выпуск. Методы и средства разработки информационно-вычислительных систем и сетей. Москва, ИЛИ РАН, 2004, стр. 198-213.

5. Чумаченко Г.О. Иерархия памяти вычислительной системы с автоматическим распределением ресурсов // Международная научно-техническая конференция «Искусственный интеллект. Интеллектуальные и многопроцессорные системы - 2004. пос. Кацивели, Крым, 2004» // Материалы Международной научно-технической конференции, том 1, Таганрог - Донецк, 2004, стр. 92-96.

6. Чумаченко Г.О. Особенности функционирования памяти совпадений в структуре вычислительной системы с автоматическим распределением ресурсов // Проблемы и методы информатики. II научная сессия Института

проблем информатики Российской академии наук, Москва, ИГГИ РАН, 2005, стр. 211-213.

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

Принято к исполнению 07/09/2005 Исполнено 08/09/2005

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

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

If 16О 75

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

2006-4 ¡

15058

'Г

Оглавление автор диссертации — кандидата технических наук Чумаченко, Георгий Олегович

Введение.

Глава 1. Исследование модели вычислений, управляемых потоком данных.

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

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

1.3 Эволюция модели вычислений, управляемых потоком данных.

1.3.1 Статическая модель вычислений, управляемых потоком данных.

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

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

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

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

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

2.1.1 Структура программы и принцип ее выполнения.

2.1.2 Принципы управления контекстом параллельных вычислительных процессов.

2.1.3 Принципы многократной рассылки операндов.

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

2.1.5 Принципы распределения параллельных вычислительных процессов по процессорным элементам.

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

2.2 Постановка задачи и пути ее решения.

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

2.3.1 Система команд ассоциативной памяти.

2.3.2 Общий принцип выполнения команда АП.

2.3.3 Исследование особенностей выполнения команд АП, обусловленных наличием кратности.

2.4 Алгоритмы выполнения команд ассоциативной памяти.

2.4.1 Принципы выполнения команды «Синхронизация запуска подпрограммы узла по входным данным».

2.4.2 Принципы выполнения команды «Аппаратная косвенная переадресация токена»

2.4.3 Принципы выполнения команды «Аппаратно-программная косвенная переадресация токена».

2.4.4 Принципы выполнения команды «Подсчет количества событий».

2.4.5 Принципы выполнения команды «Стирание токена».

2.4.6 Принципы выполнения команды «Чистка ассоциативной памяти».

2.4.7 Обобщение вариантов взаимодействия токенов различных типов. Таблица взаимодействия токенов.

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

Глава 3. Принципы функционирования аппаратуры ассоциативной памяти ВСАРР.

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

3.2 Исследование особенностей функционирования Блока ассоциативного сравнения ассоциативной памяти ВСАРР.

3.3 Разработка структуры ассоциативной памяти ВСАРР.

3.3.1 Принципы модульного построения ассоциативной памяти ВСАРР.

3.3.2 Метод распределения токенов по модулям ассоциативной памяти.

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

3.4 Принципы функционирования аппаратуры модуля ассоциативной памяти ВСАРР

3.4.1 Структурная схема и общий алгоритм функционирования МАП.

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

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

3.4.4 Принципы прерывания обработки множественного отклика.

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

3.4.6 Принципы работы БВК при выполнении команд АП, взаимозависимых между собой по кратности нижнего токена.

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

Глава 4. Создание макета модуля ассоциативной памяти вычислительной системы с автоматическим распределением ресурсов.

4.1 Выбор элементной базы макета. Обоснование использования ПЛИС как элементной базы макета.

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

4.3 Инструментальная среда и методология проектирования макета.

4.4 Макет модуля ассоциативной памяти ВСАРР.

4.4.1 Конструктивное исполнение модуля ассоциативной памяти.

4.4.2 Функциональность Блока управления макета МАП.

4.4.3 Инициализация макета ВСАРР и начало работы.

4.4.4 Методы отладки макета модуля ассоциативной памяти.

4.5 Перспективы развития макета модуля ассоциативной памяти.

4.6 Поведенческая модель ВСАРР.

4.7 Краткий обзор средств системы программирования для ВСАРР.

4.8 Результаты проверки эффективности использования команд ассоциативной памяти на примере тестового набора программ.

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

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

Введение 2005 год, диссертация по информатике, вычислительной технике и управлению, Чумаченко, Георгий Олегович

Актуальность темы

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

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

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

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

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

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

1. Исследование принципиально новой модели вычислений - гибридной динамической модели с ДФК.

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

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

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

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

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

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

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

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

• разработана структура и принципы функционирования Блока управления модуля АП;

• разработанные аппаратные решения реализованы в макете модуля АП, входящего в состав макета ВСАРР;

• разработанная система команд АП используется в поведенческой модели ВСАРР;

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

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

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

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

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

3. Созданный с применением ПЛИС макет Блока управления модуля АП, входящий в состав макета ВСАРР.

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

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

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

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

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

Публикации

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

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

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

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

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

- жесткое закрепление ячеек памяти токенов (памяти фреймов) за каждой активацией функции;

- неоптимальные алгоритмы распределения готовых к выполнению параллельных вычислительных процессов по процессорным элементам.

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

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

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

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

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

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

Заключение

Библиография Чумаченко, Георгий Олегович, диссертация по теме Вычислительные машины и системы

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

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

3. Tadayon P., «Thermal Challenges During Microprocessor Testing», Intel Technology Journal, Sort Test Technology Development, Intel Corporation, Quarter 3, 2000

4. Таненбаум Э., Архитектура компьютера, СПб.:Питер, 2002

5. Таненбаум Э., Современные операционные системы,2-е изд., СПб.:Питер, 2002

6. Van der Wijngaart R.F., The NAS Parallel Benchmark Version 2.4, Report NAS-02-007, October 2002

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

8. Митрофанов В., Слуцкин А., Ларионов К., Эйсымонт Л. Направления развития отечественных высокопроизводительных систем/Юткрытые системы. 2003. № 5.

9. Arvind and R. A. Iannucci. Two Fundamental Issues in Multiprocessing. In Proc. of DFVLR Conf. 1987 on Par. Proc. in Science and Eng., Bonn-Bad Godesberg, W. Germany, June 1987.

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

11. Dennis J., Misunas D., A preliminary Architecture for a Basic Data-Flow Processor, In Proceedings of the 2nd annual symposium on Computer architecture, pp.126 132, ACM Press New York, NY,1975

12. Dennis J., First version of a Dataflow Procedure Language, In G. Goos and J. Hartmanis, editors, Proceeding of the Programming Symposium, Paris, 1974, Springer-Verlag, Berlin, 1974. Lecture notes in Computer Science 19.

13. Jagannathan R., Dataflow Models, «Parallel and Distributed Computing Handbook» (Editor E.Y.Zomaya), McGraw-Hill, 1995

14. Arvind, Brobst S., The Evolution of Dataflow Architectures from Static Dataflow to P-RISC, In Proceeding of Workshop on Massive Parallelism: Hardware, Programming and Application, Amalfi, Italy, October 1989.

15. Comte D., Hifdi F.,LAU multiprocessor: Microfunctional description and technologic choise,in Proc. 1-st Eur.Conf.Parallel and Distrib.proc.,Feb.l979, pp.8-15

16. Comte D., Hifdi F., Syre J.C, The data driven LAU multiprocessor system: Results and perspective, in Proc. World Comput.Congress IFIP'80, Oct. 1980, pp. 175-180

17. Chong Y.M., Data flow chip optimizes image processing, Comput.Design, October, 1984, pp. 97-103

18. Arvind, Gostelow K. P., The U-interpreter, IEEE Computer, February, 1982, pp.42-49

19. Arvind, Kathail V., Pingali K., A Dataflow Architecture with Tagged Tokens. Technical Report TM 174, Computation Structure Group, MIT Laboratory for Computer Science, 545 Technology Square, Cambri

20. J.G.D. da Silva, A Pseudo-Associative Matching Store for the Manchester Prototype Dataflow Computer, Ph.D. Thesis, Department of Computer Science, University of Manchester, February 1982

21. Papadopoulos G.M., Implementation of a General-Purpose Dataflow Multiprocessor. Ph.D. thesis, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambrige, MA 02139, 1988

22. Gurd J.R., The Manchester Dataflow Machine, Computer Physics Communications, Vol.37, pp. 49-62, July, 1985

23. Arvind and V. Kathail, A multiple processor dataflow machine that supports generalized procedures, in Proc. 8th ISCA, May 1981, pp 291-302.

24. Hiraki K., Nishida K., Sekiguchi S, Shimada Т., Status report of SIGMA-1: A dataflow supercomputer, Advanced topics in dataflow computing, J.-L. Gaudiot and L.Bic, eds., Prentice Hall, 1991,pp. 207-223

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

26. Papadopoulos G.M., Culler D. E., Monsoon: an Explicit Token-Store Architecture, in Proc. 17th ISCA, June 1990, pp. 82-91

27. Traub K.R., Papadopoulos G.M., Beckerle M.J., Hicks J.E., Young J., Overview of the Monsoon Project, in Proc. 1991 Intl. Conf. Comput. Design, 1991, pp. 150 155.

28. Grafe V.G., Hoch J.E., The Epsilon-2 Multiprocessor System, J. Parall. Distr. Comput., 10 (1991), pp. 309-318

29. Ang B.S., Arvind, Chiou D., StarT the next Generation: Integrating Global Caches and Dataflow Architecture, Advanced Topic in Dataflow Computing and Multithreading, G.R. Gao, L. Bic and J.-L. Gaudiot, eds, IEEE Computer Society Press, 1995, pp. 19-54

30. Culler D. E., Managing Parallelism and Recourses of Scientific Dataflow Programs, Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambrige, June 1989

31. Bic L., Al-Mouhamed M., The EM-4 under implicit parallelism, in Proc. 1993, Intl. Conf. Supercomputing, July 1993,

32. Nikhil R.S., Papadopoulos G.M., Arvind,*T:A multithreaded massively parallel architecture, in Proc. 19th ISC A, May 1992, pp. 156-167

33. Young J., Context Management in the ID Run Time System, Computation Structure Group Memo 319, Massachusetts Institute of Technology, Cambrige, September 1990

34. Brobst S., Hicks J., Papadopoulos G., Young J., ID Run-time system, Computation Structure Group Memo 311, November, 1990

35. Chiou D.T., Frame Memory Management for the Monsoon Dataflow Computer. Master's thesis, MIT, EECS, Laboratory for Computer Science, Cambridge, MA, Sept. 1992

36. Arvind, Nikhil R.S., Executing a program on the MIT Tagged-Token Dataflow Architecture, IEEE Transactions of computers, Vol. 39, №3, March 1990

37. Ianucci R.A., Toward Dataflow/von Neumann Hybrid Architecture, In Proceedings 19th Annual International Symposium on Computer Architecture, pp.131-140, ACM Press, 1988

38. Hicks J., Chiou D., Ang B.S., Arvind, Performance Studies of Id on the Monsoon Dataflow System, Journal of Parallel and Distributed Computing, 18 (3):273-300, 1993

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

40. Hiraki К., Sekiguchi S., Shimada Т., Load Scheduling Scheme Using Inter-PE Network. Technical Report, Computer Science Division, Electrotechnical Laboratory, 1-1-4 Umezono, Sakura-mura, Niihari-gun, Ibaraki, 305, Japan, 1987.

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

42. Network Search Engine 256K Entries, Advanced information IDT 75K72100, Datasheet, http:/Avwwl.idt.com/pcms/products.taf?catID=58523

43. SiberCAM Ultra-18M SCT1842, Product brief datasheet, httr)://www.sibercore.com/ MOSAID Class-IC DC 18288 Network Search Engine 18 Mbit Ternary CAM, Datasheet, http://www.mosaid.com/corporate/home/index.php

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

45. T 75K72100 Dynamic Power Management, Application Note AN-274, http://wwwl.idt.com/pcms/products.taf?catID=58523

46. Янкевич E.A., Организация параллельных вычислительных процессов в исполнительных устройствах машины нетрадиционной архитектуры, диссертация на соискание ученой степени кандидата технических наук, ИПИ РАН, Москва, 2003

47. Окунев А.С., Об одном методе подсчета глобальной кратности в вычислительной системе с автоматическим распределением ресурсов // Методы и средстваобработки информации 2005. Труды Всероссийской научной конференции. М.:

48. Московский государственный университет ми. М.В. Ломоносова, 2005

49. Шнитман В.З., Кузнецов С.Д. Аппаратно-программные платформы корпоративныхинформационных систем Электронный ресурс. // Центр Информационных

50. Технологий. 1996. - Режим доступа:http://citforum.ru/hardware/appkis/contents.shtml. Загл. с экрана.

51. Шнитман В.З., Кузнецов С.Д. Серверы корпоративных баз данных Электронныйресурс. // Центр Информационных Технологий. 1997. - Режим доступа:http://citforum.ru/database/skbd/contents.shtml. Загл. с экрана.

52. Кнут Д., Искусство программирования, том 3. Сортировка и поиск, 2-е изд., М.:

53. Издательский дом "Вильяме", 2000.

54. Beckerle M.J. Overview of the START (*T) multithreaded computer//Proc. COMPCON'93,1993. P. 148-156.

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

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

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

58. Watson I., Gurd J.R., A prototype data flow computer with token labeling, in Proc. National Comput. Conf., June, 1979, pp. 623-628

59. Watson I., Gurd J.R., A practical data flow computer, IEEE Computer, 15 (Feb. 1982), pp.51-57

60. Бурцев B.C., Система массового параллелизма с автоматическим распределением аппаратных средств суперЭВМ в процессе решения задачи, сборник научных трудов «Вычислительные машины с нетрадиционной архитектурой», Выпуск 2, ВЦКП РАН, Москва, 1994

61. ПВС параллельная вычислительная система

62. ДФК -динамически формируемый контекст

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

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

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

66. ЭВМ -электронная вычислительная машина1. ПТ память токенов

67. ИУ — исполнительное устройство1. ОС операционная система1. ПЭ процессорный элемент1. ПК память команд

68. МПРП микропроцессор регуляции параллелизма

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

70. АЗУ ассоциативное запоминающее устройство1. ВБ МАП входной блок МАП

71. РБТПО регистровый буфер токенов с прерванным откликом

72. БПОВТ блок предварительной обработки верхнего токена

73. ИБ АО интерфейсный блок АЗУ и ОЗУ

74. СФСА схема формирования свободных адресов

75. PC АЗУ регистр совпадении АЗУ

76. БОО блок обработки откликов

77. БВК блок выполнения команд1. ФП формирователь пар

78. БТПО буфер токенов с прерванным откликом

79. АБТПО ассоциативный буфер токенов с прерванным откликом

80. БПД блок предварительной дешифрации1. БСК блок сравнения ключей

81. ИНВТ идентификационный номер верхнего токена

82. АБК ассоциативный буфер кратности

83. ОЗУ МАП оперативное запоминающее устройство модуля ассоциативнойпамяти

84. СБИС сверх большая интегральная схема

85. ТЭЗ -типовой элемент замены

86. БУ МАП блок управления модуля ассоциативной памяти

Похожие работы

Информатика, вычислительная техника и управление
05.13.00