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.
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 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
                                    Меня умиляет, когда материал из университетских лекций постят на хабре.

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