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

В вычислительной технике на современном этапе сложилось две основные парадигмы: управление вычислительным процессом (ВП) потоком команд (control flow) и потоком данных (dataflow).

Отличие этих подходов можно проиллюстрировать с помощью теории графов. Представим вычислительный процесс с помощью ориентированного графа G (его еще называют потоковым графом), вершины которого V будут обозначать операции над данными (вычислительные узлы), а дуги — передаваемые результаты вычислений и операнды (начало дуги — выдача результата выполнения операции вычислительным узлом, конец — получение операнда следующим вычислительным узлом). Каждую вершину и каждую дугу пометим уникальным идентификатором idпричем, у дуг, по которым предаются одни и те же данные для разных потребителей, идентификаторы будут совпадать. Каждой вершине также припишем тип операции о, который принадлежит к множеству всех возможных операций О (о э О).

Вычислительная система (ВС) может реализовывать данный граф по-разному (рис. 1). Так, в командной парадигме (фон неймановская архитектура) машинные команды — это не что иное как описание вершины потокового графа (описание самой вершины и инцидентных ей информационных дуг). Формат команды следующий: код операции, адрес операнда 1, адрес операнда 2, адрес ячейки памяти для сохранения результата. Код операции — это ни что иное, как описание действия, что производится над данными в вершине графа (тип команды принадлежит множеству всех возможных команд О). Адреса же операндов и результата нужны исключительно для того, чтобы описать смежные дуги потокового графа: номера ячеек памяти, где хранятся операнды, по сути, являются уникальными идентификаторами id инцидентных вершине-оператору узлу графа, т. е. память (оперативная и регистровая) в фон неймановской архитектуре — это не только место для хранения данных, но и способ связывания вершин потокового графа. Потому, если в процессоре фон неймановской архитектуры присутствует несколько исполнительных устройств, то передача данных от одного устройства другому возможна только через ячейку памяти, что значительно усложняет систему и снижает ее производительность. Компьютер классической фон неймановской архитектуры по определению работает в последовательном режиме: получается, что на потоковый граф накладывается еще один граф — граф последовательности выполнения команд (или траектория выполнения (trace)). Узел командного графа активизируется, когда до него доходит последовательность выполнения (адрес текущей выполняемой команды находится в регистре команд К процессора). Связи между вершинами командного графа будем называть управляющими связями (связи в потоковом графе будем именовать связями по данным). Поэтому на программиста в том числе ложится и задача выбора оптимальной последовательности обхода узлов графа (т.е. формирование командного графа), т.к. алгоритм без командного графа в классической архитектуре описать нельзя.

Рис. 1 — Управление вычислениями потоком команд и потоком данных Командная парадигма из-за своей негибкости значительно снижает производительность ВС. Например, ограничивается формат графа программы: как правило, из узла графа программы может выходить не более одной дуги с результатом и входить не более двух дуг с операндами. Такое ограничение вызвано тем фактом, что описываются именно узлы графа [2] и с архитектурными особенностями фон неймановской ВС.

Альтернативная парадигма — управление вычислениями с помощью потока данных (теоретические основы dataflow были заложены в 1960;х годах Карпом и Миллером). В данном случае акцент делается не на описание узлов, а на описание дуг графа [2,5]. Вычисления активизируются в то время, когда к узлу графа приходят все необходимые для вычисления операнды (рис. 1). Операнды передаются поодиночке, оформленные в виде токенов (операнд + служебная информация, относящаяся к операнду). Данная парадигма изначально параллельная, т.к. не накладывает ограничений на количество одновременно активированных (находящихся в состоянии вычисления) узлов графа, т.к. в ней, в отличие от фон неймановской ВС, нет такого узкого места, как счетчик команд.

Первая реальная dataflow-машина была реализована в 75 году прошлого века Джеком Деннисом (Jack Dennis) из Массачусетского технологического института. Графическая модель описания работы dataflow-систем была предложена сотрудником Стэнфордского университета Дуайном Адамсом (Duane Adams) в его диссертационной работе.

Однако в настоящее время наиболее популярной остается изначально последовательная control flow парадигма. Это объясняется тем, что командный подход появился в истории развития вычислительной техники (ВТ) первым, т.к. он позволяет свести к минимуму аппаратуру ВС (на заре развития ВТ экономия вычислительного оборудования была чрезвычайно актуальна). В свое время фон неймановская архитектура обеспечила стремительный прорыв, однако сейчас она стала существенным сдерживающим фактором в развитии ВТ из-за того, что не позволяет производить эффективное распараллеливание ВП. Стараниями современных разработчиков изначально последовательная архитектура была искусственно приспособлена для параллельных вычислений, и родились следующие решения: конвейер командRISC — архитектуравекторный процессорсуперскалярная архитектурапредсказание переходовпредикация ветвления (branch predication) — отсроченное ветвление (delaying branching) — изменение последовательности команд, подаваемых на конвейер команд (совокупность методов, позволяющих передавать команды в исполнительные блоки в порядке, отличном от предписанного программой), (out-of-order execution) и упорядоченное (предписанное программой) завершение (in-order completion) — WLIV (very large instruction word — сверхдлинное командное словотехнология параллельной обработки с явным параллелизмом EPIC (Explicitly Parallel Instruction compiling) — мультискалярная архитектурамультитрединги т.д., и т. п. Список этот можно продолжать довольно долго [28, 43]. Однако несмотря на такое разнообразие архитектур и приемов ядро всех подобных вычислительных систем остается фон неймановскимдаже суперскалярный процессор, арифметико-логическое устройство которого распадается на несколько независимо работающих функциональных устройств (ФУ), не уходит от фон Неймана слишком далеко, ибо он использует фон-неймановскую командную систему.

Попытки создания конкурентоспособных ВС с управлением потоком данных, как уже говорилось, предпринимались начиная с середины с середины 70-х годов прошлого века. Бум разработок в этой области пришелся на 70−90 годы прошлого века, однако впоследствии интерес к подобным разработкам значительно утих. Причиной тому послужил тот факт, что dataflow-системы не смогли составить серьезную конкуренцию по показателю цена/производительность (или объем оборудования / производительность) машинам классической архитектуры. Однако за этот довольно небольшой временной промежуток наметились основные классы систем dataflow. Интерес к системам dataflow стал возрождаться лишь в последнее время с появлением производительных программируемых логических интегральных схем (ПЛИС или FPGA), позволивших реализовать потоковый граф аппаратно.

Заключение

.

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

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

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

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

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

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

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

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

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

8. С помощью разработанной среды создания и запуска ОА-образа решены некоторые прикладные задачи: для Центра психолого-педагогической реабилитации «Строгино» разработан и успешно функционирует программно-аппаратный комплекс «Термопульсатор», создана программная модель АПК «Шестиногий шагающий аппарат», ведется разработка программной модели суперкомпьютерной системы с управлением потоком данных в рамках НИР «Исследование и разработка архитектуры и среды программирования перспективной суперкомпьютерной системы на основе динамической модели вычислений с управлением потоком данных».

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