Содержание к диссертации
Введение
Глава 1, Исследование модели вычислений, управляемых потоком данных 10
1.1 Проблемы повышения производительности вычислительных систем фон-неймановской архитектуры 10
1.2 Основные принципы модели вычислений, управляемых потоком данных 14
1.3 Эволюция модели вычислений, управляемых потоком данных 17
13.1 Статическая модель вычислений, управляемых потоком данных 17
13.2 Динамическая модель вычислений, управляемых потоком данных 20
1.4 Анализ факторов, влияющих на параллелизм вычислительных процессов в ПВС на
базе динамической модели 30
1.5 Выводы к первой главе 32
Глава 2. Разработка принципов функционирования ассоциативной памяти для управления параллельными вычислительными процессами 34
2.1 Исследование гибридной динамической модели вычислений, управляемых потоком данных, с динамически формируемым контекстом , 34
2.1.1 Структура программы и принцип ее выполнения 34
2.1.2 Принципы управления контекстом параллельных вычислительных процессов.36
2.1.3 Принципы многократной рассылки операндов..., 38
2.1.4 Принципы определения готовности параллельных вычислительных процессов к запуску 41
2.1.5 Принципы распределения параллельных вычислительных процессов по процессорным элементам 44
2.1.6 Механизмы управления параллельными вычислительными процессами 45
2.2 Постановка задачи и пути ее решения 47
2.3 Обшие принципы реализации механизмов управления параллельными вычислительными процессами в ассоциативной памяти 54
2.3.1 Система команд ассоциативной памяти 54
2.3-2 Общий принцип выполнения команда АП 55
2.3.3 Исследование особенностей выполнения команд АП, обусловленных наличием кратности 57
2.4 Алгоритмы выполнения команд ассоциативной памяти 60
2.4.1 Принципы выполнения команды «Синхронизация запуска подпрограммы узла по входным данным» 60
2.4.2 Принципы выполнения команды «Аппаратная косвенная переадресация токена» 64
2.4.3 Принципы выполнения команды «Аппаратно-программная косвенная переадресация токена» 68
2.4.4 Принципы выполнения команды «Подсчет количества событий» ., 71
2.4.5 Принципы выполнения команды «Стирание токена» 74
2.4.6 Принципы выполнения команды «Чистка ассоциативной памяти» 76
2.4.7 Обобщение вариантов взаимодействия токенов различных типов. Таблица взаимодействия токенов 77
2.5 Выводы к второй главе 80
Глава 3. Принципы функционирования аппаратуры ассоциативной памяти ВСАРР 83
3.1. Структура и принципы функционирования вычислительной системы с автоматическим распределением ресурсов 83
3.2 Исследование особенностей функционирования Блока ассоциативного сравнения ассоциативной памяти ВСАРР. 85
3.3. Разработка структуры ассоциативной памяти ВСАРР 88
3.3.1. Принципы модульного построения ассоциативной памяти ВСАРР 88
3.3.2 Метод распределения токенов по модулям ассоциативной памяти 90
3.3.3. Особенности использования механизма маскирования полей ключа токена, обусловленные модульным построением ассоциативной памяти 90
3.4 Принципы функционирования аппаратуры модуля ассоциативной памяти ВСАРР .92
3.4.1 Структурная схема и общий алгоритм функционирования МАП 92
3.4.2 Реализация механизма блокировки взаимодействия токенов различных типов -99
3.4.3 Обработка исключительных ситуаций в ассоциативной памяти 102
3.4.4 Принципы прерывания обработки множественного отклика 105
3.4.5 Принципы выполнения команд АП, взаимозависимых между собой по ключу верхнего токена 108
3.4.6 Принципы работы БВК при выполнении команд АП, взаимозависимых между собой по кратности нижнего токена 111
3.5 Выводы к третьей главе 114
Глава 4. Создание макета модуля ассоциативной памяти вычислительной системы с автоматическим распределением ресурсов 116
4.1 Выбор элементной базы макета. Обоснование использования ПЛИС как элементной базы макета 116
4.2 Структура макета ВСАРР и конструктивные решения для него 117
4.3 Инструментальная среда и методология проектирования макета 120
4.4 Макет модуля ассоциативной памяти ВСАРР 121
4.4.1 Конструктивное исполнение модуля ассоциативной памяти 121
4.4.2 Функциональность Блока управления макета МАП 122
4.4.3 Инициализация макета ВСАРР и начало работы 123
4.4.4 Методы отладки макета модуля ассоциативной памяти , 124
4.5 Перспективы развития макета модуля ассоциативной памяти 125
4.6 Поведенческая модель ВСАРР 127
4.7 Краткий обзор средств системы программирования для ВСАРР 129
4.8 Результаты проверки эффективности использования команд ассоциативной памяти на примере тестового набора программ 130
4.8.1 Результаты выполнения тестовой задачи умножения матриц 130
4.8.2 Результаты выполнения тестовой задачи пузырьковой сортировки 143
4.8.3 Общие выводы по проведенному тестированию 151
4.9 Выводы к четвертой главе.. 152
Заключение 153
Список литературы 155
Перечень сокращений 161
- Основные принципы модели вычислений, управляемых потоком данных
- Принципы определения готовности параллельных вычислительных процессов к запуску
- Особенности использования механизма маскирования полей ключа токена, обусловленные модульным построением ассоциативной памяти
- Структура макета ВСАРР и конструктивные решения для него
Введение к работе
Актуальность темы
Современные вычислительные системы (ВС) обладают колоссальной производительностью и позволяют решать очень сложные научные и инженерные задачи. Однако по-прежнему существует целый круг задач, для которых производительности существующих ВС не хватает - по некоторым оценкам, для решения многих задач, стоящих на данный момент перед человечеством, необходимы ВС с производительностью 1014 - 1015 операций в секунду. Наиболее перспективным способом увеличения производительности ВС является распараллеливание вычислений, так как технологический путь развития имеет принципиальные физические ограничения.
Центральной проблемой распараллеливания вычислений является выбор базовой модели параллельных вычислений. Подавляющее большинство современных параллельных вычислительных систем (ЛВС) построено на принципах фон-неймановской модели, однако эти ПВС характеризуются крайне низкой эффективностью загрузки процессоров - около 12-15% на задачах проблемного характера. Низкая загрузка процессоров ПВС традиционной архитектуры обусловлена большими накладными расходами на синхронизацию параллельных вычислительных процессов и проблемой когерентности кэш-памяти процессоров. В связи с этим интенсивно исследуются другие модели - асинхронные, потоковые, функциональные, реляционные и др., более естественно отражающие идею параллельных вычислений. Одной из наиболее перспективных моделей является модель вычислений, управляемых потоком данных.
В отделе «Проблем построения информационно-вычислительных систем высокого параллелизма» Института проблем информатики Российской Академии Наук под руководством академика B.C. Бурцева проводится разработка и исследование новых принципов организации вычислительного процесса, воплощенных в гибридной динамической модели с динамически формируемым контекстом (ДФК), в которой вычисления управляются потоком данных. Практической реализацией принципов данной модели является проект по созданию вычислительной системы с автоматическим распределением ресурсов (ВСАРР).
Основной целью создания гибридной динамической модели с ДФК является разработка принципов, позволяющих, с одной стороны, создавать программы с максимальной степенью параллелизма, а с другой - эффективно реализовывать данный параллелизм при выполнении программы на аппаратуре ВСАРР. Поэтому, от других моделей вычислений данную модель отличает ряд оригинальных свойств, обуславливающих; эффективную организацию параллельных вычислительных процессов за счет снижения накладных расходов на их создание - эффективную реализацию параллелизма вычислительных процессов за счет аппаратного автоматического распределения ресурсов. Для эффективной организации параллельных вычислений в гибридной динамической модели с ДФК должен присутствовать ряд механизмов, с помощью которых программист имеет возможность эффективного управления параллельными вычислительными процессами, К таким механизмам относятся механизм управления потоками данных, механизм сборки «мусора» и событийный механизм.
Актуальность данной диссертации определяется важностью задачи реализации механизмов управления параллельными вычислительными процессами таким образом, чтобы они максимально эффективно выполняли свои функции с минимальными накладными расходами. Для достижения данной цели впервые было предложено реализовать данные механизмы на аппаратном уровне с использованием ассоциативной памяти (АП).
Цель и задачи работы
Целью диссертационной работы является исследование и разработка принципов эффективного функционирования механизмов управления параллельными вычислительными процессами гибридной динамической модели с ДФК с использованием ассоциативной памяти.
Для достижения поставленной цели в работе были сформулированы и решены следующие задачи:
1. Исследование принципиально новой модели вычислений - гибридной динамической модели с ДФК,
2. Анализ механизмов управления параллельными вычислительными процессами в гибридной динамической модели с ДФК и сравнение вариантов программной и аппаратной реализации их выполнения,
3. Разработка принципов эффективной аппаратной реализации механизмов управления параллельными вычислительными процессами с использованием АП.
4. Разработка системы команд АП, аппаратно реализующей механизмы управления параллельными вычислительными процессами.
5. Разработка структуры и принципов функционирования Блока управления АП, обеспечивающего выполнение системы команд АП.
6. Практическая реализация разработанных аппаратных решений в макете модуля АП? входящего в состав макета ВСАРР.
7. Проверка на поведенческой модели ВСАРР эффективности предложенных принципов аппаратной реализации в Блоке управления АП выполнения механизмов управления параллельными вычислительными процессами на примере выполнения тестовых программ.
Объект и предмет исследования
Объектом исследования являются гибридная динамическая модель с ДФК и ее практическая реализация - ВСАРР. Предметом исследования являются принципы эффективного функционирования механизмов управления параллельными вычислительными процессами за счет аппаратной реализации их выполнения в Блоке управления АП.
Методы исследования
Исследования проводились с использованием метода анализа и сравнения, теории
организации параллельных вычислений, теории построения высокопроизводительных
вычислительных систем, теории проектирования ЭВМ и методик проектирования
сложных вычислительных комплексов с применением систем автоматизированного
проектирования, метода эмпирического исследования (эксперимента). Аппаратная
реализация макета модуля АП велась в соответствии с принципами нисходящего
і проектирования с использованием объектно-ориентированного подхода.
Научная новизна
Научная новизна данной работы заключается в том, что впервые предложено реализовать аппаратное выполнение в АП всех основных механизмов управления параллельными вычислительными процессами гибридной динамической модели с ДФК-Основные научные результаты работы состоят в следующем:
• проведен анализ гибридной динамической модели с ДФК, в результате которого определено, что принципы организации вычислительного процесса данной модели позволяют реализовать максимальный параллелизм вычислительных процессов программы за счет снижения накладных расходов на их организацию и аппаратного автоматического распределения ресурсов;
• проведен анализ механизмов управления параллельными вычислительными процессами рассматриваемой модели, на основе которого впервые предложено реализовать данные механизмы на аппаратном уровне при помощи системы команд АП, выполняемых Блоком управления АП;
• впервые разработана система команд АПТ аппаратно реализующая механизмы управления параллельными вычислительными процессами гибридной динамической модели с ДФК;
• впервые разработаны алгоритмы выполнения команд АП и введены специальные типы токенов, инициирующих выполнение команд АП.
• разработана структура и принципы функционирования Блока управления модуля АП;
• разработанные аппаратные решения реализованы в макете модуля АП, входящего в состав макета ВСАРР;
• разработанная система команд АП используется в поведенческой модели ВСАРР;
• проведено исследование прохождение тестовых программ на поведенческой модели, которое показало как преимущество принципиально нового принципа организации параллельных вычислительных процессов во ВСАРР, так н эффективность использования предлагаемой в данной диссертации системы команд АП.
Практическая значимость
Практическая значимость работы заключается в следующем:
Разработанные в диссертационной работе принципы аппаратной реализации механизмов управления параллельными вычислительными процессами повышают эффективность выполнения программ за счет снижения накладных расходов на управление параллельными вычислительными процессами. Разработанная в диссертационной работе система команд АП вошла в систему команд ВСАРР, которая является практической реализацией основных принципов гибридной динамической модели с ДФК Разработанные в диссертационной работе принципы аппаратного управления параллельными вычислительными процессами могут использоваться при разработке широкого класса ПВС архитектуры потока данных. Реализация макета Блока управления модуля АП, входящего в макет ВСАРР, позволила оценить и отработать аппаратные решения, направленные на повышение эффективности функционирования данного блока.
Положения, выносимые на защиту;
1. Анализ механизмов управления параллельными вычислительными процессами в гибридной динамической модели с ДФК и вариантов их реализации.
2. Предложенные принципы аппаратной реализации механизмов управления параллельными вычислительными процессами при помощи системы команд АП, выполняемых Блоком управления АП,
3. Созданный с применением ПЛИС макет Блока управления модуля АП, входяший в состав макета ВСАРР.
4. Результаты выполнения на поведенческой модели ВСАРР тестовых программ, иллюстрирующих эффективность использования предложенных команд АП.
Реализация результатов работы
Разработанные теоретические положения и новые технические решения экспериментально апробированы на макете ВСАРР. Результаты работы реализованы в Институте проблем информатики РАН (ИПИ РАН) в отделе Проблем построения информационно-вычислительных систем высокого параллелизма при исследовании и разработке архитектуры ВСАРР, а также при реализации проекта по созданию макета и поведенческой модели данной вычислительной системы.
Апробация работы
Основные положения и результаты работы докладывались и обсуждались на научных семинарах в ИПИ РАН 2001-2005 гг., а также на ряде международных и всероссийских конференций в период с 2001 года по 2005 года: на международной молодежной научной конференции «XXVII Гагаринские чтения» (МАТИ-РГТУ, Москва, 2001); на Всемирной выставке по информационным технологиям СеВГГ-2003 (Ганновер, Германия, 2003); на мевдународной научно-технической конференции «Интеллектуальные и многопроцессорные системы ИМС2003» (пос. Дивноморское, 2003); на Первой Всероссийской научной конференции «Методы и средства обработки информации-2003» (МГУ, Москва, 2003); на международной научно-технической конференции «Искусственный интеллект. Интеллектуальные а многопроцессорные системы - 2004» (пос» Кацивели, Крым, 2004); на «II Научной сессии Института проблем информатики Российской академии наук; Проблемы и методы информатики» (Москва, 2005),
Публикации
По материалам диссертационной работы опубликовано 7 печатных работ, список которых приводится в конце автореферата.
Структура и объем диссертации
Диссертационная работа состоит из введения, четырех глав и списка литературы из 70 наименований.
Работа изложена на 162 страницах машинописного текста, включая 39 рисунков и 10 таблиц.
Аннотация диссертационной работы по главам
В первой главе диссертационной работы проведен анализ проблем развития высокопроизводительных ПВС традиционной архитектуры, основанных на фон-неймановской модели вычислений. Рассмотрена модель вычислений с управлением потоком данных как одна из наиболее эффективных моделей параллельных вычислений. Проведен анализ истории развития данной модели, начиная от статической модели и заканчивая гибридной динамической моделью, которая является наиболее перспективной, В заключение главы проведен анализ факторов, влияющих на параллелизм вычислительных процессов в динамической модели вычислений, управляемых потоком данных.
Во второй главе проведено исследование принципиально новой модели вычислений - гибридной динамической модели с ДФК. Рассмотрены основные механизмы управления параллельными вычислительными процессами и проведен анализ программного и аппаратного вариантов их реализации, на основе которого предложено реализовать выполнение данных механизмов аппаратно в АП. Предложены общие принципы аппаратной реализации механизмов управления параллельными вычислительными процессами, выполненной как система команд АП. Подробно рассмотрены назначение команд АП и алгоритмы их выполнения.
В третьей главе содержится описание аппаратных решений по реализации системы команд АП. Рассмотрена структура ВСАРР, в состав которой входит АП» и разработана модульная структура АП ВСАРР. Рассмотрена структура и принципы функционирования МАП, Предлагается ряд аппаратных решений, позволяющих разрешать конфликты, возникающие по причине конвейерного принципа выполнения команд АП,
В четвертой главе приведены материалы по разработке макета МАП, входящего в состав макета ВСАРР. Рассмотрены используемые для разработки макета элементная база и методы его проектирования, а также особенности реализации разработанных в третьей главе аппаратных решений в макете МАП и методы его отладки» Для иллюстрации эффективности предлагаемых в диссертации принципов аппаратной реализации механизмов управления параллельными вычислительными процессами, в четвертой главе приводятся результаты выполнения на программной модели ВСАРР тестовых программ.
В заключение работы обобщены основные результаты проведенных автором исследований и разработок, сформулированы основные выводы по работе в целом.
Основные принципы модели вычислений, управляемых потоком данных
Теоретически, изложенный выше подход распараллеливания с использованием фон-неймановской модели организации вычислительного процесса, за счет выполнения п параллельных процессов на п процессорах ВС, каждый из которых работает с производительностью РПроц, при условии должного уровня параллелизма задачи может дать увеличение производительности, прямо пропорциональное количеству процессоров (п) в ПВС фон-неймановской архитектуры - n Pnpoith Однако опыт параллельного программирования и выполнения параллельных программ на ПВС фон-неймановской архитектуры показал, что фон-неймановская модель организации вычислительного процесса обладает существенными недостатками при ее применении для параллельных вычислений [68].
Основным недостатком ПВС фон-неймановской архитектуры является крайне низкая эффективность загрузки процессоров. Результаты тестирования высокопроизводительных вычислительных многомашинных и многопроцессорных комплексов при помощи известных пакетов тестирующих программ SPEC и NAS Parallel Benchmark[6, 7]. Данные тесты показывают, что на рассматриваемом классе задач, которые являются весьма представительными, эффективность загрузки процессоров современных ПВС фон-неймановской архитектуры колеблется в пределе от 5 до 35%[8,9].
Одной из основных причин низкой загрузки процессоров ПВС фон-неймановской архитектуры являются временные накладные расходы из-за необходимости синхронизации работы параллельных вычислительных процессов с общими данными»
В многопроцессорных ПВС синхронизация параллельных вычислительных процессов обеспечивается за счет применения блокирующих переменных (семафоров, мьютексов), ассоциированных с общими, разделяемыми данными или ресурсами. Перед тем, как обратится к общим данным, процесс обязан проверить состояние блокирующей переменной, и только в случае, если она свободна, занять ее и получить доступ к общим данным. В том случае, если блокирующая переменная занята, процесс должен ожидать ее освобождения. Такое ожидание может быть двух типов: ожидание с активным опросом и ожидание с переключением процессов.
При ожидании с активным опросом (спин-блокировка) процессы, ожидающие доступа к заблокированным общим данным, постоянно опрашивают блокирующую переменную. Данный способ обеспечивает наиболее быстрый доступ ожидающего процесса к освободившемуся общему ресурсу, однако обладает значительными накладными расходами в виде тактов процессора, затраченных на опрос блокирующей переменной - во время данного опроса процессор не выполняет полезной вычислительной работы. При ожидании с переключением процессов процесс, не получивший доступа к общим данным, снимается с выполнения на процессоре и переводится в состояние ожидания освобождения нужного ему общего ресурса. В этом случае нет накладных расходов на опрос блокирующей переменной, однако присутствуют значительные накладные расходы, связанные с переключением задач на процессоре[5].
Таким образом, оба случая обладают значительными накладными расходами, приводящими к падению реальной производительности многопроцессорной ПВС фон-неймановской архитектуры.
Кроме этого, на синхронизацию параллельных процессов в многопроцессорных ПВС значительным образом влияет проблема когерентности кэш-памяти процессоров. Кэш-память процессора предназначена для нивелирования разности скоростей работы процессора и основной памяти ВС,
При введении кэш-памяти в процессоры многопроцессорной ПВС возникает новая и очень сложная проблема поддержки когерентности содержимого кэш-памяти. Если некоторый процессор изменяет значение переменной, копия которой записана в кэшпамять многих процессоров ПВС, то после данного изменения верное значение переменной содержится только в кэш-памяти процессора, изменившего его. При этом копии данной переменной в кэш-памяти других процессоров объявляются недействительными. Это приводит к тому, что при обращении к данной переменной процессоры, в кэш-памяти которых копии данной переменной были объявлены недействительными, вынуждены обращаться за ее значением в основную память, причем» не ранее того момента, когда значение переменной будет обновлено в памяти. Все это приводит к простою процессоров и падению числа команд, реально выполненньк в единицу времени[10].
При использовании метода активного ожидания для опроса блокирующей переменной, как правило, используется специальная команда TEST-AND-SET[5, 10], которая единым неделимым действием проверяет состояние блокирующей переменной и в любом случае устанавливает ее в состояние блокировки. В том случае, если блокирующая переменная до установки в состояние блокировки была в свободном состоянии, процесс, выполняющийся на данном процессоре, получает доступ к разделяемому ресурсу. Если до установки блокирующей переменной в состояние блокировки она уже находилось в этом состоянии, то, соответственно, общий ресурс занят и процесс продолжает опрос блокирующей переменной. Таким образом, каждый процессор, участвующий в опросе, в любом случае производит модификацию блокирующей переменной, что приводит к необходимости поддерживать когерентность значения данной переменной в кэш-памяти всех процессоров со всеми вытекающими отсюда накладными расходами[5]. Проблема когерентности кэш-памяти также накладывает определенные физические ограничения на масштабируемость многопроцессорных ПВС[4,10].
В многомашинных ПВС синхронизация параллельных процессов, работающих на различных узлах, осуществляется при помощи передачи сообщений. В том случае, если узлы многомашинной ПВС - многопроцессорные, то синхронизация параллельных процессов внутри одного узла происходит как в обычной многопроцессорной системе. В целом, общие принципы синхронизации в многомашинных ПВС такие же, как и в многопроцессорных ПВС, Поэтому, для синхронизации параллельных процессов в многомашинной ПВС свойственны такие же проблемы, как и в многопроцессорных ПВС.
Таким образом» фон-неймановская модель организации вычислительного процесса имеет существенные недостатки при ее применении для параллельных вычислений. В связи с этим интенсивно исследуются другие модели - асинхронные, потоковые, функциональные, реляционные и др., более естественно отражающие идею параллельных вычислений. Одной из таких моделей является модель вычислений, управляемых потоком данных.
Принципы определения готовности параллельных вычислительных процессов к запуску
В соответствии с основными принципами модели вычислений, управляемых потоком данных, выполнение команды, на вход которой поступили все входные токены, приводит к поглощению токенов с ее входных дуг (см. раздел 1.2). Применительно к рассматриваемой гибридной динамической модели вычислений с ДФК это означает, что выполнение активации узла приводит к поглощению токенов с ее входных дуг. Однако токен с замаскированными полями, фактически, заменяет собой множество токенов, поступающих на входы совокупности активаций узлов. Поэтому, он должен обладать некоторым свойством, позволяющим ему взаимодействовать с множеством токенов, поступающих на противоположные входы активаций узлов (рис. 2.5,6). Таким свойством является кратность токена.
Токен может обладать кратностью от 1 до бесконечности. Если токен имеет значение кратности, равное 1, то он называется однократным токеном. Если значение его кратности больше 1, но имеет конкретное значение, не равное бесконечности, то он называется многократным токеном. Если значение кратности токена больше I и равно бесконечности, то он называется токеном с бесконечной кратностью.
Значение кратности токена передается в специальном поле «Кратность». Исключением является только бесконечная кратность, которая кодируется специальной комбинацией в поле токена «Тип токена» (рис.2Л).
Кратность токена определяет количество однократных токенов, с которыми данный токен может провзаимодействовать. При каждом взаимодействии с однократным токеном кратность данного токена уменьшается на 1. В случае если в результате взаимодействий с другими токенами кратность токена становится равной 0, то данный токен прекращает свое существование. Варианты взаимодействия между собой токенов с различными значениями кратности будут рассмотрены в разделе 2.3.3.
Таким образом, с помощью маски и кратности множество токенов, необходимых для передачи одного и того же значения на входы множества активаций узлов, можно заменить одним токеном. Следовательно, маска и кратность являются мощным инструментом многократной рассылки операндов, свободным от накладных расходов, свойственных программному методу рассылки. Кроме этого, наличие кратности у токена приводит к экономии ресурса ячеек ассоциативной памяти (вместо v ячеек занимается одна, где v - значение кратности токена) и снижению количества обращений к ней.
Как и в других динамических моделях, определение готовности параллельных вычислительных процессов к запуску в гибридной динамической модели с ДФК осуществляется на основе наличия всех входных данных для этого процесса. Другими словами, для каждого параллельного вычислительного процесса осуществляется синхронизация его запуска по входным данным. Выполнение данной функции, как и в других динамических моделях, осуществляется памятью токенов (ПТ).
Как следует из раздела 2.1.1, в качестве элементарной единицы параллельных вычислений, для которой необходимо осуществлять синхронизацию запуска по данным, в гибридной динамической модели с ДФК является подпрограмма узла, а точнее, ее конкретная активация.
Поступление токенов на вход подпрограммы узла отображается их поступлением на вход ПТ. Очевидно, что токены, предназначенные для одной и той же активации данного узла, обладают совпадающими значениями тэга и «Асл», то есть ключа. Поэтому для каждого токена, поступающего на вход ПТ, проводится поиск записанных в ПТ токенов, ключи которых совпадают с его ключом.
При поступлении токена на вход ПТ по его ключу проводится операция поиска, в процессе которой происходит сравнение ключа данного токена с ключами всех токенов, записанных в ПТ. Сравнение происходит с учетом маски токена, поступившего на вход ассоциативной памяти, и маски записанных в ассоциативную память токенов. В дальнейшем по тексту токен, поступивший на вход ПТ, будет называться верхним токеном, а токен, записанный в ассоциативную память - нижним токеном.
Если в результате проведения операции поиска произошло совпадение ключа верхнего токена с ключом нижнего токена, то это означает, что на оба входа данного узла поступили токены с совпадающими тэгами. В этом случае на основе верхнего и нижнего токенов, совпавших по ключу, формируется специальная структура данных, называемая парой. Из сказанного выше следует, что ПТ является памятью с выборкой по содержимому. Поэтому, в качестве ПТ в гибридной динамической модели с ДФК используется ассоциативная память (АП).
Формируемая в результате совпадения по ключу верхнего и нижнего токенов пара состоит из следующих полей (рис 2.6): поля «Данное 1» и «Данное 2», в которых передаются оба входных операнда подпрограммы узла из совпавших по ключу токенов_ поле «Ай,», в котором передается адрес подпрограммы узла, которая должна быть запущена поле «Контекст», в котором передается контекст, в котором используются передаваемые в паре операнды поле «№ задачи» ключ Фактически, пара является информационной структурой, полностью описывающей готовую к выполнению активацию узла: в полях «Данное 1» и «Данное 2» передаются входные операнды, а в полях «№ задачи», «Контекст» и «Ащ» - виртуальный адрес данной активации узла. Сформированная пара поступает на исполнительное устройство, где инициирует выполнение данной активации узла. Подробно вопрос распределения пар по процессорным элементам рассмотрен в разделе 2.1.5. По аналогии с токеном, совокупность полей пары «№ задачи», «Контекст» и «Ася» будем называть ключом пары. Принципы формирования ключа пары будут рассмотрены в разделе 2.4.1. Случай отсутствия совпадений соответствует ситуации, когда на вход узла поступил токен с некоторым значением тэга и при этом на противоположном входе отсутствует токен с совпадающим тэгом. В этом случае верхний токен должен быть записан в ассоциативную память, где будет ожидать поступления на вход ассоциативной памяти токена с совпадающим ключом.
В отличие от рассмотренных в первой главе динамических моделей, гибридная динамическая модель с ДФК не подразумевает резервирование определенного количества ячеек АП для активации узла или нескольких узлов. При необходимости записи токена в АП он просто записывается в любую свободную ячейку. Таким образом, выделение ячеек ассоциативной памяти для хранения токенов, расположенных на входных дугах узлов и ожидающих поступления на противоположные входы токенов с совпадающими тэгами, происходит в динамике вычисления по мере необходимости и выполняется автоматически с максимально возможной скоростью па аппаратном уровне.
Такой подход, в противоположность подходу с жестким закреплением строго определенного количества ячеек памяти токенов, обладает высоким быстродействием и свободен от накладных расходов, связанных с выделением некоторого ресурса памяти токенов или памяти фреймов под активацию функции (разделы 1.3.2.4 и 1.4). Кроме этого, используемый метод позволяет более рационально использовать ресурс ассоциативной памяти, так как не приводит к ситуации, когда в памяти токенов может быть достаточно для запуска активации функции свободных ячеек, которые не могут быть использованы для начала выполнения очередной активации функции, так как они жестко ассоциированы с другими активациями и считаются свободными только после окончания их выполнения (см. раздел 1.4).
Особенности использования механизма маскирования полей ключа токена, обусловленные модульным построением ассоциативной памяти
При программировании иногда можно полезно и эффективно использовать свойство независимости результатов выполнения подпрограммы узла от ориентации поступающих на узел операндов относительно его входов. В этом случае входы узла, по сути, обезличены и однородны, и при посылке токенов на них в самих токенах можно не указывать, на какой именно вход поступает данный токен. Другими словами, при посылке токенов на входы такого узла можно не использовать признак Д1/Д2, так как он теряет свой смысл.
Для использования свойства независимости результатов выполнения подпрограммы узла от ориентации поступающих на нее операндов используется токен «Безразличный». Токены «Безразличный» предназначены для передачи операндов на входы узлов, чьи подпрограммы обладают свойством коммутативности» и токены данного типа не ориентированы относительно входов узла -признак Д1/Д2 для этого токена не используется.
Следовательно, при передаче операндов на вход узла с помощью токенов «Безразличный», подпрофамма узла должна запускаться на выполнение тогда, когда два токена «Безразличный» с совпадающими тэгами поступили на два входах узла, причем совершенно не важно, на каком конкретно входе присутствует каждый из этих токенов. Это означает, что команда «Синхронизация запуска подпрограммы узла по входным данным» при использовании токенов «Безразличный» запускается на выполнение при совпадении по ключу двух токенов «Безразличный» — значение признака ДУД2 данных токенов не имеет значения.
Выполнение команды «Синхронизация запуска подпрограммы узла по входным данным» с использованием токенов «Безразличный» во всем совпадает с выполнением «Синхронизация запуска подпрограммы узла по входным данным» при использованием токенов «Стандартный», за исключением расстановки значенні! полей «Данное» совпавших по ключу токенов «Безразличный» по полям пары «Данное 1» и «Данное 2». Поскольку подпрограмма узла, на которую операнды направляются с помощью токенов «Безразличный», обладает свойством коммутативности, то порядок расстановки может быть произвольным. Для определенности, при образовании пары в результате взаимодействия токенов «Безразличный» поля пары «Данное 1» и «Данное 2» заполняются в следующем порядке: в поле пары «Данное 1» копируется значение операнда из поля «Данное» верхнего токена, а в поле пары «Данное 2» - значение операнда из поля «Данное» нижнего токена.
Различные варианты совпадения между собой по ключу токенов «Безразличный» со всеми возможными значениями кратности обрабатываются в соответствии с принципами, изложенными в разделе 2.3.3.
При помощи команды «Аппаратная косвенная переадресация токена» реализуется механизм управления потоками данных. Как следует из раздела 2.2, переадресация потока данных, которые в гибридной динамической модели с ДФК передаются в виде токенов «Стандартный» и «Безразличный», реализуется через замену значения ключа у токенов данных типов. При этом отметим, что замене подвергаются только поля «Контекст» и «Асл», так как изменение значения поля «№ задачи» относится к системным действиям по межзадачному взаимодействию и осуществляется только на уровне ОС.
Как говорилось в разделе 2.2, для реализации механизма управления потоками данных в АП необходимо передать: 1) ключ или диапазон ключей (диапазон ключей задается с помощью механизма маскирования полей ключа), характеризующих активации узлов, с которых надо осуществить переадресацию; 2) новое значение ключа -виртуального адреса активации узла, на которую необходимо осуществить переадресацию; 3)управляющее воздействие, инициирующее замену ключа у найденных токенов. Для передачи в АП данной информации вводится токен «Аппаратная косвенность».
В ключе токена «Аппаратная косвенность» передается значение ключа или, с помощью маски, диапазона ключей, характеризующих совокупность активаций узлов, с которых необходимо осуществить переадресацию потока данных, а в поле «Данное» -новое значение ключа, то есть, виртуального адреса активации узла, на вход которой необходимо осуществить переадресацию.
Так как в ключе токепа «Аппаратная косвенность» передается значение ключа или, с помощью маски, диапазона ключей, характеризующих совокупность активаций узлов, с которых необходимо осуществить переадресацию потока данных, то, значит, он имеет совпадающий ключ с токеном «Стандартный» или «Безразличный», который необходимо переадресовать. Поэтому, команда «Аппаратная косвенная переадресация токена» запускается на выполнение при совпадении по ключу токена «Аппаратная косвенность» и токена «Стандартный» или токена «Безразличный».
В дальнейшем будет рассматриваться только случай совпадения по ключу токенов «Аппаратная косвенность» и «Стандартный», подразумевая, что все сказанное будет справедливо и для случая совпадения по ключу токенов «Аппаратная косвенность» и «Безразличный»,
Результатом выполнения команды «Аппаратная косвенная переадресация токена» является создание нового токепа «Стандартный», все поля которого, за исключением ключа, скопированы с полей токена «Стандартный», совпавшего по ключу с токеном «Аппаратная косвенность». В ключ нового токена «Стандартный» подставляется значение, взятое из поля «Данное» токена «Аппаратная косвенность», которое является виртуальным адресом активации узла, на которую осуществляется переадресация. Для того, чтобы созданный в процессе выполнения команды «Аппаратная косвенная переадресация токена» токен «Стандартный» с новым значением ключа поступил на вход активации узла, на которую он был переадресован, он перезапускается на вход АП. Различные варианты совпадения между собой по ключу токенов «Аппаратная косвенность» и «Стандартный» со всеми возможными значениями кратности обрабатываются в соответствии с принципами, изложенными в разделе 2.3.3. Однако особого внимания заслуживают четыре случая: совпадение по ключу многократного токена «Аппаратная косвенность» с токеном «Стандартный» с бесконечной кратностью; совпадение по ключу токена «Аппаратная косвенность» с бесконечной кратностью с токеном «Стандартный» с бесконечной кратностью; совпадение по ключу многократного токена «Аппаратная косвенность» с токеном «Безразличный» с бесконечной кратностью; совпадение по ключу токена «Аппаратная косвенность» с бесконечной кратностью с токеном «Безразличный» с бесконечной кратностью. Для рассматриваемых случаев токены «Стандартный» и «Безразличный» эквивалентны, поэтому ниже будем рассматривать только варианты совпадения по ключу токена «Аппаратная косвенность» с токеном «Стандартный» имея в виду4 что все сказанное также относится к вариантам совпадения по ключу токена «Аппаратная косвенность» с токеном «Безразличный»»
Структура макета ВСАРР и конструктивные решения для него
Исполнительные устройства (ИУ) предназначены для выполнения готовых активаций подпрограмм узлов. Готовые к вычислению активации узлов описываются специальной информационной структурой - парой (рис. 3.3). Пары формируются МАПами и через коммутатор пар автоматически на аппаратном уровне распределяются по свободным ИУ (см. раздел 2.1.5). С учетом того, что поступающие на ИУ пары буферизируются во входном буфере, свободным считается ИУ, во входном буфере которого присутствует свободное место.
В структуре ИУ присутствует специальная память - память команд (ПК), в которой записаны подпрограммы всех узлов, причем содержимое ПК всех ИУ абсолютно одинаково, то есть, все ИУ равнозначны. Подпрограмма каждого узла адресуется в ПК адресом, который передается в поле пары «Асл» (структуру пары см. в разделе 2.1.4).
Получая пару от коммутатора пар, ИУ выбирает из ее поля «Асл» адрес подпрограммы узла и производит обращение к первой команде подпрограммы узла в ПК. С этого момента начинается выполнение подпрограммы узла по традиционному фон-неймановскому принципу.
Результатом выполнения подпрограммы узла на ИУ является выдача токенов на входы других узлов. В аппаратуре ВСАРР это отображается тем, что в процессе выполнения подпрограммы активированного узла на ИУ формируются и выдаются через коммутатор токенов на вход МАП токены с результатами выполнения подпрограммы узла. В поле «Aw» этих токенов подставляются значения адресов подпрограмм тех узлов, на входы которых они должны поступить.
Стоит отметить, что ИУ ВСАРР имеют многопоточную структуру и одно ИУ может одновременно обрабатывать 4 пары[53]. Коммутатор токенов предназначен для соединения выходов ИУ с входами МАП. Принцип распределения токенов по МАП описан в разделе 3.3.2. Хост-машина является специализированным вспомогательным компьютером в структуре ВСАРР, выполняющим следующие основные функции: организация процессов ввода-вывода данных во ВСАРР; организация межзадачного обмена данными; организация откачки-подкачки токенов из МАПов в случае их переполнения и с целью ротации выполняемых на ВСАРР программ. Аппаратную поддержку выполнения описанных выше функций осуществляет микропроцессор регуляции параллелизма (МПРП). Для выполнения перечисленных выше функций в качестве буферной памяти используется общее оперативное запоминающее устройство. Обращение к ООЗУ ведется через Адаптеры ООЗУ, управляемые от МПРП. В разделе 2.3 было сказано о том, что АП состоит из двух частей (рис. 2.7): Блока ассоциативного сравнения, реализующего сравнение ключа токена, поступившего на вход АП, с ключами записанных в АП токенов, и Блока управления, аппаратно реализующего механизмы управления параллельными вычислительными процессами.
Одной из основных особенностей гибридной динамической модели с ДФК, основные принципы которой реализуются во ВСАРР, является применение механизма маскирования (см. раздел 2.1.3). Например, для совпадения по ключу одного многократного токена д: с некоторой совокупностью токенов, образующих множество Y, может потребоваться замаскировать определенные поля ключа токена х. При этом, заранее неизвестно, в какой последовательности будут поступать токен х и токены из множества У - это определяется в динамике выполнения программы. Если к моменту поступления на вход АП токена JC в ней уже могут содержаться все токены из множества Y, то операция поиска должна проходить с учетом маски верхнего токена х. Если к моменту поступления на вход АП токена из множества У в ней уже записан токен х, то операция поиска должна проходить с учетом маски нижнего токена х. Из этого следует, что Блок ассоциативного сравнения должен поддерживать проведение операции поиска с учетом масок как верхнего, так и нижних токенов.
Следствием применения механизма маскирования полей ключа и кратности токена также является возможность возникновения при проведении операции поиска множественного отклика (см. раздел 23.3). Таким образом, Блок ассоциативного сравнения должен поддерживать фиксацию возникновения множественного отклика в ответ на проведение операции поиска. Кроме этого, Блок ассоциативного сравнения должен обеспечивать выдачу Блоку управления АП информации обо всех адресах совпадения, принадлежащих одному множественному отклику. Это необходимо для последовательного выполнения взаимодействий верхнего токена, вызвавшего данный множественный отклик, со всеми совпавшими с ним по ключу нижними токенами (см. раздел 2.3.3).
Всем данным характеристикам лучше всего отвечает Блок ассоциативного сравнения, построенный на основе аппаратного ассоциативного запоминающего устройства (АЗУ). Особенно критично применение АЗУ для проведения операции поиска с учетом масок верхнего и нижнего токенов. Способы сравнения ключей с использованием обычной прямоадресуемой памяти, в частности, основанные на хешировании [22], могут дать приемлемый результат для сравнения ключей без масок. Однако, в случае необходимости сравнения ключей с учетом масок, причем как записанных в память, так и поступающих на ее вход токенов, использование техники хеширования бесполезно, В данном случае, сравнение сводится, фактически, к последовательному сравнению ключей методом перебора, что приведет к чрезвычайно медленной работе ассоциативной памяти.
Как уже говорилось в разделе 2.1.4, идея применения в памяти токенов АЗУ для сравнения тэгов токенов в ПВС архитектуры потока данных неоднократно выдвигалась ранее [24, 21, 20], однако уровень микроэлектронной промышленности того периода не мог обеспечить производство АЗУ с приемлемым объемом, скоростью работы и стоимостью. В то же время, на современном этапе развития микроэлектронной промышленности и повышенной потребности в телекоммуникационном оборудовании многие компании по производству электронных компонентов наладили выпуск телекоммуникационных сопроцессоров, также называемых IP-сопроцессорами, построенных на основе АЗУ. АЗУ, реализованная в данных сопроцессорах, обладает следующими характеристиками:
