Машины, управляемые потоком данных

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

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

Суть идеи dataflow модели в том, что программа представляется графом потока данных, пример которого показан на рис. 9.13.

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

Рис. 9.13. Граф потока данных и структура потоковых машин

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

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

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

Было создано несколько машин, управляемых потоком данных, как со статической, так и с динамической архитектурами. Наиболее известными являются мультипроцессор Дениса (Массачусетский технологический институт), система DDP и LAU (исследовательский центр СЕRТ), достаточно подробно описанные в литературе.

СИСТОЛИЧЕСКИЕ СИСТЕМЫ

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

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

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

Рис. 9.14. Пример построения систолической структуры

Систолические архитектуры обладают следующими достоинствами:

• минимизируются обращения к памяти, что позволяет согласовать скорость работы памяти со скоростью обработки;

• упрощается решение проблем ввода/вывода вследствие уменьшения конфликтов при обращении к памяти;

• эффективно используются технологические возможности СБИС за счет регулярности структуры систолической матрицы.

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

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