Пользователь
0,0
рейтинг
23 июня 2011 в 11:45

Разработка → Dataflow-архитектуры. Часть 1


Вторая часть статьи.
Большинство современных вычислительных машин, будь то суперкомпьютер Fujitsu K, обычная персоналка или даже калькулятор, объединяет общий принцип работы, а именно модель вычислений, основанная на потоке управления (Controlflow). Однако, эта модель не является единственно возможной. В некотором роде ее противоположностью является модель вычислений, управляемая потоком данных, или просто Dataflow. О ней я и хочу сейчас рассказать.


Архитектуру потока управления часто называют фон-неймановской (в честь Джона фон Неймана). Это не совсем правильно, так как архитектура фон Неймана — лишь подмножество архитектур потока управления. Существуют не-неймановские архитектуры потока управления, например гарвардская, которую сейчас можно встретить разве что в микроконтроллерах.

В рамках архитектуры потока управления (controlflow) вычислительная машина состоит из двух основных узлов: процессора и памяти. Программа представляет собой набор инструкций, хранящихся в памяти в порядке выполнения. Данные, с которыми работает программа, также хранятся в памяти в виде набора переменных. Адрес инструкции, которая выполняется в настоящий момент, хранится в специальном регистре, в x86 он так и называется — Instruction Pointer (IP). Момент начала выполнения инструкции определяется моментом завершения предыдущей (мы сейчас рассматриваем упрощенную модель без всяких Out-of-Order). Система очень простая, понятная и знакомая большинству читателей. Так зачем же придумывать что-то еще?

Врожденные проблемы controlflow


Дело в том, что архитектура control flow имеет ряд врожденных недостатков, полностью избавиться от которых невозможно, так как они проистекают из самой организации вычислительного процесса, можно только уменьшить негативный эффект с помощью различных костылей технических решений. Перечислим основные проблемы:
  • Перед выполнением инструкции ее операнды необходимо загрузить из памяти в регистры процессора, а после выполнения — выгрузить результат обратно в память. Шина процессор-память становится узким местом: процессор простаивает часть времени, ожидая загрузки данных. Проблема с переменным успехом решается при помощи упреждающей выборки и нескольких уровней кэш-памяти.
  • Построение многопроцессорных систем сопряжено с рядом трудностей. Существуют две основные концепции таких систем: с общей и с распределенной памятью. В первом случае сложно физически обеспечить совместный доступ многих процессоров к одному ОЗУ. Во втором случае возникают проблемы когерентности данных и синхронизации. С ростом числа процессоров в системе все больше ресурсов тратится на обеспечение синхронизации и все меньше — на собственно вычисления [03].
  • Никто не гарантирует, что на момент выполнения какой-либо инструкции ее операнды будут находиться в памяти по указанным адресам. Инструкция, которая должна записать эти данные, может оказаться, еще не выполнилась. В многопоточных приложениях существенная доля ресурсов и нервов программиста тратится на обеспечение синхронизации потоков.


Знакомьтесь — Dataflow



Нет устоявшегося русского перевода для термина Dataflow architecture. Можно встретить варианты «потоковая архитектура», «архитектура потока данных», «архитектура с управлением потоком данных» и подобные им.

В архитектурах с управлением потоком данных (Dataflow) [01] отсутствует понятие «последовательность инструкций», нет Instruction Pointer'а, отсутствует даже адресуемая память в привычном нам смысле. Программа в потоковой системе — это не набор команд, а вычислительный граф. Каждый узел графа представляют собой оператор или набор операторов, а ветви отражают зависимости узлов по данным. Очередной узел начинает выполняеться как только доступны все его входные данные. В этом состоит один из основных принципов dataflow: исполнение инструкций по готовности данных.
Вот для примера граф вычисления корней квадратного уравнения. Синие круги — операторы, оранжевые квадраты — входные данные, зеленые — выходные, желтые — константы. Черные стрелки обозначают передачу численных данных, синие — булевых.


Аппаратная реализация


В потоковых машинах данные передаются и хранятся в виде т.н. токенов (token). Токен — это структура, содержащая собственно передаваемое значение и метку — указатель узла назначения. Простейшая потоковая вычислительная система состоит из двух устройств: исполнительного (execution unit) и устройства сопоставления (matching unit) [11].


Исполнительное устройство служит для выполнения инструкций и формирования токенов с результатами операций. Как правило, оно включает в себя память команд, доступную только для чтения. Готовность входных данных узла определяется по наличию набора токенов с одинаковыми метками. Для поиска таких наборов и служит устройство сопоставления. Обычно оно реализуется на базе ассоциативной памяти. Используется либо «настоящяя», аппаратная ассоциативная память (CAM — content-addressable memory), либо структуры, работающие аналогично, например, хэш-таблицы.
Одним из основных достоинств dataflow-архитектуры является ее масштабируемость: не составляет труда собрать систему, содержащую множество устройств сопоставления и исполнительных устройств. Устройства объедиянются простейшим коммутатором, причем для адресации токенов служат их метки. Весь диапазон номеров узлов просто распределяется равномерно между устройствами. Никаких дополнительных мер для синхронизации вычислительного процесса, в отличие от многопроцессорной controlflow-архитектуры, не требуется.


Статическая dataflow-архитектура


Описанная выше схема называется статической (static dataflow). В ней каждый вычислительный узел представлен в единственном экземпляре, число узлов заранее известно, также заранее известно число токенов, циркулирующих в системе. В качестве примера реализации статической архитектуры можно привести MIT Static Dataflow Machine [12] — потоковый компьютер, созданный в Массачусетском технологическом институте в 1974 году. Машина состояла из множества обрабатывающих элементов (Processing Element), связанных коммуникационной сетью. Схема одного элемента показана на рисунке:


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

Динамическая dataflow-архитектура


В динамической потоковой архитектуре (dynamic dataflow) каждый узел может иметь множество экземпляров. Для того, чтобы различать токены, адресованные в разные экземпляры одного узла, в структуру токена вводится дополнительное поле — контекст. Сопоставление токенов теперь ведется не только по меткам, но и по значениям контекста. По сравнению со статической архитектурой появляется целый ряд новых возможностей.
  • Рекурсия. Узел может направлять данные в свою копию, которая будет отличаться контекстом (но при этом иметь ту же метку).
  • Поддержка процедур. Процедурой в рамках данной модели вычислений будет последовательность узлов, связанных между собой и имеющая входы и выходы. Можно одновременно вызывать несколько экземпляров одной и той же процедуры, которые будут отличаться контекстом.
  • Распараллеливание циклов. Если между итерациями цикла нет зависимости по данным, можно обрабатывать сразу все итерации одновременно. Номер итерации, как вы уже наверное догадались, будет содержаться в поле контекста.

Одной из первых реализаций динамической потоковой архитектуры была система Manchester Dataflow Machine (1980 год) [13]. Машина содержала аппаратные средства для организации рекурсий, вызова процедур, раскрытия циклов, копирования и объединения ветвей вычислительного графа. Также в отдельный модуль была вынесена память команд (instruction store unit). На рисунке показана схема одного элемента машины:


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

Продолжение следует


В следующей части статьи: почему dataflow архитектуры не настолько хороши, как здесь расписано? Как скрестить ужа с ежом потоковую систему с классической? Как, и главное, на чем пишутся программы под dataflow-системы?
Stay tuned…


Литература


Общие вопросы dataflow


[01] — Dataflow architectures, Jurij Silc
[02] — Баканов В.М. Потоковые (Dataflow) вычислители: управление интенсивностью обработки данных
[03] — Параллелизация обработки данных на вычислителях потоковой (Dataflow) архитектуры. Журнал «Суперкомпьютеры top50».

Аппаратные реализации


[11] — Dataflow architectures, Arvind David E. Culler
[12] — Preliminary Architecture for a Basic Data-Flow Processor, Jack B. Dennis and David P. Misunas
[13] — A Multilayered Data Flow Computer Architecture, J.R. Gurd, I. Watson.
Dmitry Yakhontov @Ocelot
карма
391,5
рейтинг 0,0

Самое читаемое Разработка

Комментарии (36)

  • –22
    Кr'айне интеr'есно! Ждём-с пr'одолжения с самым интеr'есным :)
    • 0
      А ведь всего-то попросил продолжения :)))
      • +5
        — Одного не могу понять — почему мой козырный туз не сыграл?!
        — Расклад батенька — расклад.
        (с)
  • +5
    Очень хотелось бы послушать про реализацию (в том числе и про распараллеливание) циклов в потоковых системах…
  • 0
    Я получил инвайт 2 года назад за похожий пост. У вас намного развернутее.
    • 0
      Ага, прочел ваш пост. Странно, что не находил его в процессе подготовки статьи. Немножко сумбурно, но кратко и по делу :)
  • 0
    Было бы интересно узнать про сравнительную производительность Dataflow и Controlflow систем.
    • +4
      Их очень сложно сравнивать, поскольку одни задачи хорошо идут на dataflow и плохо на controlflow, а другие — наоборот. В своих статьях разработчики стремятся выбрать тесты, которые по максимуму используют преимущества их системы. Получаются вот такие красивые, но малообъективные картинки:

      (Взято отсюда)
  • 0
    случаем Дикарев Н.И. Вам не знаком?
    • 0
      Лично — нет, а работы его читал
  • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      как бы архитектура ПЛИСов и заложена на dataflow-основе.
      под control-flow её конечно вполне можно подвести (использование clock'a), но базовые задачи решаются без этого.
    • +1
      Dataflow-системы часто и реализуют на ПЛИСах, во второй части попробую этот вопрос осветить
  • 0
    Что то мне подсказывает, что dataflow лучше подходит для создания систем ИИ. А есть ли какие-то эмуляторы этой системы на ПК или специализированные языки программирования, чтобы вот прям взять сейчас и попробовать? Было бы интересно посмотреть на конкретные примеры программ. В общем жду следующую статью.
    • +1
      LabVIEW можете попробовать… Там в общем-то практически всё на концепцию dataflow завязано.
    • +3
      Разным людям на протяжении полувека что-то подсказывало, что для создания систем ИИ подходит то одно, то другое, то Lisp, то Prolog, то ещё что-то. Но вот ИИ за это время так и не родился. Может, дело не в инструментах? А в алгоритмах? Или даже в осознании того, чем является собой «интеллект».
      • 0
        Лично мне подсказывает то соображение, что стандартная модель выполнения программ может не очень для этого подходить. Данные в такой системе нужно организовывать как то по другому. На уровне каких-то образов, где данные перемешаны с методами. И вот описание dataflow сильно напоминает что-то такое.
        • 0
          Данные перемешаны с методами — это очень напоминает язык MUMPS используется в СУБД Cache (к примеру). По правде сказать — принципиальных отличий в организации самих данных там нет. Поэтому для ИИ — сам факт микса данных и методов, может не многое дать.
          • 0
            Ничего себе, MUMPS вспомнили! Я между прочим как раз занимаюсь поддержкой одного сервера на базе Cache. Но там на самом деле данные четко отделены от методов, так что я не совсем понимаю, что вы имеете ввиду. Текстовые строки можно интерпретировать как команды на лету, да. Но эта фича является скорее опасной, чем полезной.
            • +1
              Мампс я не вспомнил — а седьмой год на нём программирую. Если данные в каше чётко отделены от методов — то это означает что скорее всего данные хранятся в SQL или (тяжёлый случай) в объектах. Однако отделение их от методов только логическое — физически и SQL-таблицы и объякты и программы — хранятся в глобалах (полезное свойство кстати, если удалите какую-то программу или измените её а в гите или другой системе контроля версий ничего не сохраните — всегда есть возможность посмотреть несколько старых версий программы в глобале). Я не говорю уже о более интересной реализации когда правила, которые являются либо методами, либо вызовом подпрограмм, записываются в глобалы как правила, и выполняются в зависимости от контекста. Естественно и здесь, присутствует разделение на данные и методы, но это разделение уже определяется именно вами, как разработчиком, и границы становятся очень размытыми. Да безопасность необходимо обеспечивать самому. Что бы увидеть где хранятся программы кликните в портале управления -> глобалы (радиобаттон базы данных) выберите вашу БД, и поставьте чек бокс «Система» — неоткомпилированные программы хранятся в глобале ^rMAC к этому глобалу вы можете сами обратится — то есть по сути писать код для каше можно и без студии (но это для любителей экзотики)… вообщем много интересного обнаружите — нулевая версия — это текущаяя — 1я версия самая старая и т.д.
              • 0
                Просто я не ожидал встретить человека, который связан с этой СУБД. О каше так редко говорят, что кажется, будто ее вообще не существует.
                Я изучал язык давно, еще когда у нас стояла не Cache а MSM под дос (там программы вообще редко когда компилировались как это делается сейчас в студии), и я не разработчик, хотя в коде немного разбираюсь и пограммы писать приходилось. А сейчас даже не знаю куда развивается эта технология. Наша система собирает аэронавигационную информацию и работает на достаточно старом дистрибутиве, но данные хранятся в глобалях с их нереляционной организацией.
                А можете подробнее рассказать про правила (или ссылку дать)? А то я не совсем понимаю, что имеется ввиду.
                То, что вы посоветовали посмотреть, я гляну когда буду на работе — не знал, что версии хранятся.
                • 0
                  Хранение версий регулируется настройками самой системы, которые кстати тоже хранятся в глобалах, а если у вас старый дистрибутив, то там вполне эти настройки могут либо отсутствовать либо хранится только свежая, нулевая версия (но она должна быть в любом случае). Рассказать про правила, в комментарии вряд ли получится, планировал по этому поводу статью написать, но процесс этот длительный. Два года назад запостил habrahabr.ru/blogs/personal/59380/ однако сейчас она сильно устарела, хотя код описанный в ней всё ещё используется. В двух словах рабочий кусок кода обрабатывающий задачу:

                  processingTask(priority,task)private s $zt=«errTask» new t s t(«i»)="" f { s t(«i»)=$o($$$iRule(«Task»,ontology,type,action,t(«i»))) q:t(«i»)=""
                  s t(«cmd»)=$g($$$iRule(«Task»,ontology,type,action,t(«i»)),"") x:t(«cmd»)'="" t(«cmd») } g endTask


                  где в глобале $$$iRule описан определённый набор действий, для конкретного типа заданной онтологии указанного action — этот набор действий может быть простым вызовм программы «d program^program» а может быть просто куском кода, в котором реализуется определённый функционал, однако в самом глобале правил $$$iRule — можно хранить очень многое — от количества процессов обрабатывающих задачи определённого приоритета — до перечня полей структур бизнес-данных… Но основная идея заимствуется у разработчиков каше — все хранить в данных, где нельзя использовать глобал — используется файл.
                • +1
                  да ещё посмотрите в глобал ^rMACSAVE может быть интересно…

                  А если не секретно — то было бы очень интересно взглянуть на реализацию структуры данных вашей системы, пусть и старой — потому что честно сказать, кроме как на своей работе — вживую никогда не видел человеку разрабатывающего под каше. Да и здесь таких немного.
                  • 0
                    Я вам отвечу в личку когда буду на работе
      • +1
        ИИ не родился, но зато мы получили Lisp и Prolog.
        «Зачастую средства оправдывают цель: цель продвигает технологию, а технология выживает даже если цели не достигаются». (Алан Дж. Перлис)
  • 0
    Лет 7 назад в университете делал что-то очень похожее на Delphi (программную реализацию, конечно, не в железе). Хотел реализовать визуальную сборку схемы вычислений в программе из функциональных модулей. Слыхом не слыхивал про тему этого топика, но программу назвал Dataflow :)
    Тогда, увы, толком не доделал (переоценил свои силы), но после текущего проекта собирался реализовать еще раз, на этот раз применительно к вебу. И как раз распараллеливание считаю очень полезным качеством этой схемы, потому что можно реализовать в облаке с отличной масштабируемостью. Было не очень понятно как реализовать параллельную обработку запросов, теперь ясно, почему, надо бы поковырять преимущества и недостатки, пока свои шишки не набил )
    • +1
      Может быть, удастся избежать еще большего количества шишек, если посмотреть на уже существующие программные реализации? Например, RiDE или ParalleX.
      • 0
        На первый взгляд очень интересно, спасибо.
  • 0
    Мне кажется в коммутаторе собака зарыта.
    • +1
      Знаете, когда начинаешь вплотную заниматься этой темой, выясняешь, что буквально в каждом элементе по собаке зарыто. А кое-где и не по одной!
  • 0
    А ещё мне кажется что это чем-то похоже на систолические матричные структуры, но пока не пойму чем?
    (Что-то мне сильно много кажется.)
  • +1
    На схеме 1 с графом вычислений ошибка в 3-ем слое. Операция вычитания не ассоциативная, нужно указать порядок операндов. Так возникает неверное представление о ходе вычислений
    • 0
      Исправлено. Для некоммутативных узлов первый операнд слева, а второй — справа.
      • 0
        Спасибо. Однако будет понятней, если операцию вычитания заменить на отрицание + сложение. Тогда неопределенность будет устранена полностью
        • 0
          Рисунок еще раз переделывать уже не буду, т.к. это всего лишь иллюстрация принципа. А вообще вы правы, и дело тут даже не в понятности. В dataflow системах стремятся избегать узлов с некоммутативными входами, так как появляется задача научить систему отличать «левый» операнд от «правого»: добавляются лишние поля в контекст, усложняется устройство сопоставления… Зачем нам лишние проблемы, проще заменить вычитание умножением на (-1) и сложением.
  • 0
    Меня умиляет, когда материал из университетских лекций постят на хабре.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.