Первоначальной мотивацией для исследований потока данных было использование массового параллелизма. Поэтому была проделана большая работа по разработке способов программирования параллельных процессоров. Однако одна из школ считала, что традиционные процессоры "фон Неймана" по своей природе непригодны для эксплуатации параллелизма. Два основных критических замечания в адрес аппаратного обеспечения фон Неймана касались его глобального счетчика программ и глобальной обновляемой памяти.
Альтернативным предложением была архитектура потока данных, которая устраняет оба этих слабых места, используя только локальную память и выполняя инструкции, как только становятся доступными их операнды. Название Dataflow происходит от концептуального представления, что программа в компьютере Dataflow представляет собой направленный граф и что данные текут между командами по его дугам. Архитектура аппаратуры Dataflow выглядела многообещающе, и был создан и изучен ряд физических реализаций.
Столкнувшись с аппаратными достижениями, исследователи обнаружили проблемы в компиляции обычных обязательных языков программирования для работы на аппаратных средствах обработки данных, особенно тех, которые связаны с побочными эффектами и локализацией. Они обнаружили, что, ограничивая определенные аспекты этих языков, такие как задания, они могут создавать языки, которые более естественно вписываются в архитектуру потока данных и поэтому могут работать на них гораздо более эффективно. Это так называемые языки программирования потока данных, разработавшие различные свойства и стили программирования в результате того, что они были скомпилированы в графики потока данных - "машинный язык" компьютеров потока данных.
МОДЕЛЬ ИСПОЛНЕНИЯ ПОТОКА ДАННЫХ
Модель Pure Dataflow
В модели исполнения потока данных программа представлена в виде направленного графика. Узлы графа представляют собой примитивные команды, такие как арифметические операции или операции сравнения. Направленные дуги между узлами представляют собой зависимости данных между инструкциями. Концептуальные данные текут как токены по дугам, которые ведут себя как неограниченные очереди первого входа, первого выхода (FIFO). Считается, что дуги, идущие к узлу, являются входными дугами для этого узла, в то время как дуги, идущие дальше, являются выходными дугами из этого узла.
Когда программа запускается, специальные узлы активации помещают данные на определенные ключевые входные дуги, вызывая срабатывание остальной части программы.
- Всякий раз, когда определенный набор входных дуг узла (называемый огневым набором) имеет данные о нем, считается, что узел является огнеопасным.
- Огнеупорный узел выполняется в неопределенное время после того, как он становится огнеупорным.
- В результате он удаляет маркер данных с каждого узла в наборе запуска, выполняет свою операцию и размещает новый маркер данных на некоторых или всех своих выходных дугах.
- Затем он перестает исполняться и ждет, пока снова станет огнеопасным.
С помощью этого метода, команды запланированы к исполнению, как только их операнды становятся доступными. Это контрастирует с моделью исполнения фон Неймана, в которой команда выполняется только тогда, когда до нее доходит счетчик программ, независимо от того, может ли она быть выполнена раньше этого.
Ранние версии аппаратной архитектуры Dataflow
Хотя теоретически поток данных кажется хорошим, практическая реализация модели чистого потока данных оказалась трудной задачей. Это объясняется рядом причин, прежде всего тем, что чистая модель делает предположения, которые не могут быть воспроизведены в реальном мире.
- Во-первых, предполагается, что дуги - это очереди FIFO неограниченной емкости, но создание неограниченной памяти невозможно в практическом смысле. Таким образом, реализация любого потока данных сильно привязана к методам хранения токенов.
- Во-вторых, предполагается, что любое количество команд может выполняться параллельно, в то время как на самом деле количество элементов обработки будет ограниченным. Эти ограничения означают, что никакая аппаратная реализация модели потока данных не будет точно отражать чистую модель.
Действительно, этот факт может внести тонкие, но важные изменения в чистую модель потока данных, что означает, что реализация может зайти в тупик в тех случаях, когда чистая модель не предсказывает тупиковой ситуации.
Полезно подвести итоги ранней разработки аппаратного обеспечения потока данных, чтобы подкрепить этот момент.
Статическая архитектура.
Когда в 1970-х годах началось строительство вычислительных машин для обработки данных, были исследованы два различных подхода к решению вышеупомянутых проблем. Статическая архитектура была предложена Деннисом и Мисунасом. При такой архитектуре конструкция дуг FIFO заменяется более простым дизайном, в котором каждая дуга может содержать не более одного токена данных. Правило обжига для узла, таким образом, заключается в том, что маркер должен присутствовать на каждой входной дуге, и что на выходной дуге не должно быть маркеров. Для реализации этого к графику потока данных неявно добавляются дуги подтверждения, которые идут в обратном направлении по отношению к каждой существующей дуге и несут токен подтверждения.
Главная сильная сторона статической архитектуры заключается в том, что очень просто и быстро определить, является ли узел огнеопасным или нет. Кроме того, это означает, что память может быть выделена для каждой дуги во время компиляции, так как каждая дуга всегда будет содержать только 0 или 1 маркер данных. Это означает, что нет необходимости создавать сложное аппаратное обеспечение для управления очередями токенов данных: каждая дуга может быть привязана к определенному участку хранилища памяти.
Сам граф хранится в компьютере в виде серии шаблонов, каждый из которых представляет собой узел графа.
- Шаблон содержит операционный-код узла, объем памяти для хранения значения токена данных на каждой входной дуге с флагом присутствия для каждой из них и список адресов назначения для выходных токенов.
- Каждый шаблон, который является огнеопасным (флаг присутствия для каждого входа установлен, а флаг присутствия для каждого выхода не установлен), имеет свой адрес в очереди команд.
- Затем блок извлечения повторно удаляет каждый шаблон из этой очереди и посылает пакет операций соответствующему блоку управления.
- Тем временем шаблон очищается, чтобы подготовить его к следующему набору маркеров данных.
- Результат передается из операционного блока в блок обновления, который помещает результаты на правильные принимающие дуги путем считывания целевых адресов в шаблоне.
- Затем он проверяет каждый шаблон на огнестойкость и помещает его в очередь инструкций для завершения цикла.
К сожалению, у статической модели есть серьезные проблемы. Дополнительные дуги подтверждения увеличивают трафик данных в системе, не принося пользу вычислениям. По данным Arvind and Culler, трафик может увеличиться в 1,5-2,0 раза. Поскольку узлу необходимо дождаться появления токенов подтверждения, прежде чем он сможет снова работать, время между очередными включениями узла увеличивается. Это может повлиять на производительность, особенно в ситуациях линейных вычислений, которые не имеют большого параллелизма.
Пожалуй, самое главное, что статическая архитектура также сильно ограничивает выполнение циклов. В некоторых случаях ограничение по одной дуге означает, что вторая итерация цикла не может начаться до тех пор, пока предыдущая почти не будет завершена, ограничивая тем самым параллелизм простой прокладкой трубопровода и предотвращая действительно параллельное выполнение итераций цикла. Несмотря на эти ограничения, был построен и изучен ряд статических компьютеров для обработки данных.