1. Микропроцессоры. Определение, классификация, закономерности развития, области применения

29. Машины, управляемые потоком данных. Принципы действия и особенности их построения. Графический метод представления программ

Впервые идея вычислений, управляемых потоком данных, была предложена в 1960-х годах Карпом и Миллером. Основоположником архитектуры, языка программирования и практической реализации машин, управляемых потоком данных, является Деннис. Его работы, выполненные в 1970-е годы, положили начало многим исследованиям в данном направлении.

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

Вершины на различных стадиях выполнения операции - команда не готова к выполнению (а – в); команда готова к выполнению (г); команда выполнена (д):

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

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

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

Типовые вершины потоковых графов - двухвходовая операционная вершина (а); одновходовая операционная вершина (б); вершина ветвления (в); вершина слияния (г); TF-коммутатор (д); T-коммутатор (е); F-коммутатор (ж); арбитр (з):

Известные потоковые вычислительные системы могут быть отнесены к двум основным типам: статические и динамические системы. Статические системы работают по принципу «один токен на дугу»,за счет чего достигается относительная простота реализации блока обнаружения активированных узлов. Преимуществом динамических потоковых вычислительных систем перед статическими системами является более высокая производительность, достигаемая за счет присутствия на дуге множества токенов.

Архитектура статической потоковой вычислительной системы, предложенная Деннисом:

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

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

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