информационный портал по вопросам биомедицинской инженерии

Сейчас на сайте 0 пользователей и 2 гостя.

Вход в систему

аватар: АЛЬ-факих али мохаммед
Содежание 
 
введение 
1.     Вычислительная  модель  потоковой  обработки.
2.     Архитектура  потоковых  вычислительных  систем.
3.     Статические  потоковые  вычислительные  системы.
4.     Динамические  потоковые  вычислительные  системы.
5.     Архитектура  потоковых  систем  с  помеченными  токенами.
6.     Архитектура  потоковых  систем  с  явно  адресуемыми  токенами.
7.     Макропотоковые  вычислительные  системы.
8.     Гиперпотоковая  обработка.
9.     Вычислительные  системы  с  управлением  вычислениями  по  запросу.
В традиционных многопроцессорных системах одновременно могут выпол-няться несколько командных последовательностей в естественном порядке, то есть в порядке размещения каждой из них в памяти. Это обеспечивается нали-  чием в каждом процессоре счетчика команд. Выполнение команд в каждом про-цессоре – поочередное и потому достаточно медленное. Для получения выигры-ша программист или компилятор должны определить независимые команды, которые могут быть поданы на отдельные процессоры, причем так, чтобы ком-муникационные  издержки  были  не  слишком  велики.
Традиционные фон-неймановские ВС, управляемые с помощью программ-ного счетчика, называются вычислительными системами, управляемыми после-довательностью команд (control flow computer). Если программа, состоящая из команд, хранится в памяти, то возможны следующие альтернативные механиз-  мы  ее  исполнения:
§        команда выполняется после того, как выполнена предшествующая ей ко-манда  последовательности;
§        команда  выполняется,  когда  становятся  доступны  ее  операнды;
§        команда выполняется, когда другим командам требуется результат ее вы-полнения.
Первый метод соответствует традиционному механизму с управлением по-следовательностью команд; второй механизм известен как управляемый данными (data driven) или потоковый (dataflow); третий метод называется механизмом управления по запросу (demand driven).
Рис. 1. Возможные вычислительные модели: а – фон-неймановская;                  
  б – потоковая; в – макропотоковая; г –  редукционная
Общие идеи нетрадиционных подходов к организации вычислительного процесса  показаны  на  рис. 1.
 
1.     Вычислительная  модель  потоковой  обработки
 
Идеология потоковой обработки, т.е. вычислений, управляемых потоком данных, была разработана в 60-х годах Карпом и Миллером. В потоковой вы-числительной модели для описания вычислений используется ориентированный граф потоков данных (dataflow graph). Этот граф состоит из узлов или вершин, отображающих операции, и ребер или дуг, показывающих потоки данных меж-  ду  теми  вершинами  графа,  которые  они  соединяют.
Узловые операции выполняются, когда по дугам в узел поступила вся необходимая информация. Обычно узловая операция требует одного или двух операндов, а для условных операций необходимо наличие входного логического значения. По выполнении операции формируется один или два результата. Та- ким образом, у каждой вершины может быть от одной до трех входящих дуг и одна или две выходящих. После активации вершины и выполнения узловой операции (это называется инициированием вершины) результаты передаются по ребрам к ожидающим вершинам. Процесс повторяется, пока не будут иниции-рованы все вершины и получен окончательный результат. Одновременно может быть инициировано несколько узлов, при этом параллелизм в вычислительной модели  выявляется  автоматически.
Рис. 2. Граф  потоков  данных  для  выражения  A / B + B ´ C
 
На рис. 2 показан простой потоковый граф для вычисления выражения f=A/B + B ´ C. Входами служат переменные A, B, и C, изображенные вверху гра-фа. Дуги между вершинами показывают тракты узловых операций. Направление вычислений – сверху вниз. Используются три вычислительные операции: сло-жение, умножение и деление. Вершина «Копирование» предназначена для фор-мирования дополнительной копии переменной B, так как она требуется в двух узлах.  
Данные (операнды, результаты), перемещаемые вдоль дуг, содержатся в опознавательных информационных кадрах, маркерах специального формата – «токенах» (иначе «фишках» или маркерах доступа). Рис.3. иллюстрирует дви-жение токенов между узлами. После поступления на граф входной информации маркер, содержащий значение A, направляется в вершину деления; токен с пере-менной B – в вершину копирования; токен с переменной C – в вершину умно-жения. Активирована может быть только вершина «Копирование», поскольку у нее лишь один вход и на нем уже присутствует токен. Когда токены из вер-       шины «Копирование» будут готовы, узлы умножения и деления также получат       все необходимые маркеры доступа и могут быть инициированы. Последняя вершина ждет завершения операций умножения и деления, то есть когда на ее входе  появятся  все  необходимые  токены.


Рис. 3. Движение  маркеров  при  вычислении  
A / B + B ´ C: а – после  подачи входных  данных; б – после  копирования; в – после  умножения  и  деления;         г – после  суммирования

Практические вычисления требуют дополнительных возможностей, напри-мер при выполнении команд условного перехода. По этой причине в потоковых графах  предусмотрены  вершины-примитивы  нескольких  типов  (рис. 4):

Рис. 4. Примитивы  узлов: а – двухвходовая  операционная  вершина;  
  б – одновходовая  операционная  вершина;  в – вершина  ветвления;     г – вершина  слияния;  д – TF-коммутатор;  е – T-коммутатор;    ж – F-коммутатор;  з – вентиль;  и – арбитр
§        двухвходовая операционная вершина – узел с двумя входами и одним вы-ходом. Операции производятся над данными, поступающими с левой и правой  входных  дуг,  а  результат  выводится  через  выходную  дугу;
§        одновходовая операционная вершина – узел с одним входом и одним вы-ходом. Операции выполняются над входными данными, результат выво-дится  через  выходное  ребро;
§        вершина ветвления – узел с одним входом и двумя выходами. Осуществляет копирование входных данных и их вывод через две выходные дуги. Путем комбинации таких узлов можно строить вершины ветвления на m выходов;
§        вершина слияния – узел с двумя входами и одним выходом. Данные по-ступают только с какого-нибудь одного из двух входов. Входные данные без изменения подаются на выход. Комбинируя такие узлы, можно стро-   ить  вершины  слияния  с  m  входами;
§        вершина управления – существует  в  перечисленных  ниже  трех  вариантах:
ú        TF-коммутатор – узел с двумя входами и одним выходом. Верхний  вход – это дуга данных, а правый – дуга управления (логические дан-ные). Если значение правого входа истинно (T – True), то входные дан-ные выводятся через левый выход, а при ложном значении на правом входе  (F – False)  данные  следуют  через  правый  выход;
ú        вентиль – узел с двумя входами и одним выходом. Верхний вход – дуга данных, а правый – дуга управления. При истинном значении на входе управления  данные  выводятся  через  выходную  дугу; 
арбитр – узел с двумя входами и двумя выходами. Все дуги являются  дугами данных. Первые поступившие от двух входов данные следуют через левую дугу, а прибывшие впоследствии – через правую выходную дугу. Активация вершины происходит в момент прихода данных с какого-либо одного входа.
Процесс обработки может выполняться аналогично конвейерному режиму: после обработки первого набора входных сигналов на вход графа может быть подан второй и т.д. Отличие состоит в том, что промежуточные результаты (токены) первого вычисления не обрабатываются совместно с промежуточными результатами второго и последующих вычислений. Результаты обычно требуются в  последовательности  использования  входов.
Существует множество случаев, когда определенные вычисления должны повторяться с различными данными, особенно в программных циклах. Про-граммные циклические процессы в типовых языках программирования могут быть воспроизведены путем подачи результатов обратно на входные узлы. При формировании итерационного кода часто применяются переменные цикла, уве-личиваемые после каждого прохода тела цикла. Последний завершается, когда переменная цикла достигает определенного значения. Метод применим и при потоковой  обработке  (рис. 5).
Рис. 5. Циклы  при  потоковой  обработке
 
 
Все известные потоковые вычислительные системы можно разделить на два основных типа: статические и динамические. В свою очередь, динамические потоковые ВС обычно реализуются по одной из двух схем: архитектуре с помеченными  токенами  и  архитектуре  с  явно  адресуемыми  токенами.
2. Архитектура  потоковых  вычислительных  систем
 
В потоковых ВС программа вычислений соответствует потоковому графу, который хранится в памяти системы в виде таблицы. На рис.6 показаны пример  графа  потоковой  программы  и  содержание  адекватной  ему  таблицы.
 
Рис. 6. Пример  формы  хранения  потоковой  программы:
 а – потоковый  граф; б – память  функционального  блока
Принципиальная схема потоковой ВС (рис. 7) включает в себя блок уп-равления (CS), где хранится потоковый граф, который используется для выбор-  ки обрабатываемых команд, а также функциональный блок (FS), выполняющий команду,  переданную  из  CS, и  возвращающий  результат  ее  выполнения  в CS.
Рис. 7. Структура  потоковой  вычислительной  системы
Блоки CS и FS работают асинхронно и параллельно, обмениваясь много-численными пакетами команд и результатами их выполнения. В пакете результата, поступающем из блока FS, содержится значение результата (val) и адрес команды, для которой пакет предназначен (des). На основании этого ад-   реса блок CS проверяет возможность обработки команды. Команда может быть однооперандной или двухоперандной. В последнем случае необходимо под-тверждение наличия обоих операндов (opr 1 и opr 2), для чего устанавливается специальный признак. Блок управления загрузкой (LC) каждый раз при акти-вировании определенной функции загружает из памяти программ код этой функции.
Для повышения степени параллелизма блоки CS и FS строятся по мо-дульному принципу, а графы потоковой программы распределяются между мо-дулями  с  помощью  мультиплексирования.
 
3. Статические  потоковые  вычислительные  системы
 
Статическая потоковая архитектура, известная также под названием «единственный-токен-на-дугу» (single-token-per-arc dataflow), была предложена Деннисом в 1975 году. В ней допускается присутствие на ребре графа не бо-      лее чем одного токена. Это выражается в правиле активации узла: вершина активируется, когда на всех ее входных дугах присутствует по токену и ни на одном из ее выходов токенов нет. Для указания вершине о том, что ее выход-    ной токен уже востребован последующим узлом графа, используется механизм подтверждения с квитированием связи (рис. 8). Его суть состоит в посылке процессорами в ответ на инициирование узлов графа специальных контроль-   ных  токенов.
Рис. 8. Механизм  подтверждения  с  квитированием
Типовая  статическая  потоковая  архитектура  представлена  на  рис. 9.

Рис. 9. Структура  процессорного  элемента  типовой  статической      потоковой  системы
 
Память действий – это узел потоковой машины, хранящий потоковый  граф и циркулирующий на нем поток данных. Он состоит из двух блоков па- мяти: команд/данных и управляющей памяти. Вершина графа представлена в памяти  команд/данных  кадром,  содержащим  следующие  поля:
§        код  операции;
§        операнд  1;
§        …
§        операнд  N;
§        вершина/дуга  1;
§        …
§        вершина/дуга  K.
Каждому кадру в памяти команд/данных соответствует кадр в управляю-щей памяти, содержащий биты наличия для всех операндов и всех полей «вершина/дуга». Бит наличия операнда устанавливается в единицу, если этот операнд доступен, т.е. если токен, содержащий данный операнд, уже поступил   по входной дуге графа. Для поля «вершина/дуга» установленный бит наличия означает, что выходная дуга, ассоциированная с данным полем, не содержит токена. Вершина графа, описанная в памяти команд/данных, может быть акти-вирована, т.е. операция может быть выполнена, если все биты наличия в соот-ветствующем кадре памяти управления установлены в единицу. Когда данная ситуация распознается блоком обновления, он помещает пакет команды в оче-редь команд. Опираясь на очередь команд и содержимое памяти действий, блок выборки составляет пакет операции и направляет его в один из функциональ-  ных блоков. После выполнения требуемой операции функциональный блок соз-дает пакет результата и передает его в блок обновления, который в соответст-   вии  с  полученным  результатом  изменяет  содержимое  памяти  действий.
Основное преимущество статической модели потоковых вычислений за-ключается  в  упрощенном  механизме  обнаружения  активированных  узлов.
Недостатки  статической  модели:
§        не  допускает  параллельного  выполнения  независимых  итераций  цикла;
§        колебания  трафика  токенов;
§        отсутствие в современных языках программирования поддержки описан-ного  режима  обработки  данных.
Архитектуру первой системы, строго соответствующей модели потоковых вычислений  типа «единственный-токен-на-дугу», предложил Деннис (рис. 10).
Рис. 10. Статическая  потоковая  архитектура  по  Деннису
 
Система представляет собой кольцо из процессорных элементов и эле-ментов памяти, в котором информация передается в форме пакетов. Процес-сорные элементы получают пакеты действий (activity templates) в виде: Код операции • Операнды • Адресат, где точка обозначает операцию составления целого слова из его частей. «Код операции» определяет подлежащую выполне-нию операцию, «Операнды» – используемые в операции числа, а «Адресат» – указывает место, куда должен быть направлен результат операции. При этом в полях операндов задаются не адреса ячеек памяти, а непосредственно числа, которые должны участвовать в операции. Преимущество такого подхода состо-  ит в том, что в каждый момент времени операнды могут быть использованы только одной выбранной вершиной, а недостаток – невозможность включения      в команду в качестве операндов сложных структур данных, даже простых векторов  и  массивов.
Пакет результата имеет вид: Значение • Адресат, где в поле «Значение» содержится значение результата, полученное после выполнения операции. Эти пакеты передаются по маршрутизирующей сети в ячейки команды блока па-       мяти, указанные в их поле «Адресат». Когда получены все входные пакеты (токены), ячейка команды порождает пакет операции. Обычно для генерации пакета операции ячейке команды нужны два входных пакета с операндами. За- тем пакет операции маршрутизируется к одному из процессорных элементов (ПЭ). Если все процессорные элементы идентичны (гомогенная система), то может быть выбран любой свободный ПЭ. В негомогенных системах со спе-циализированными ПЭ, способными выполнять только определенные функции, выбор нужного ПЭ производится по коду операции, заключенном в пакете операции.
4. Динамические  потоковые  вычислительные  системы
 
Производительность потоковых систем существенно возрастает, если они   в состоянии поддерживать дополнительный уровень параллелизма, соответст-вующий одновременному выполнению отдельных итераций цикла или парал-лельной обработке пар элементов в векторных операциях. Кроме того, в сов-ременных языках программирования активно используются реентерабельные процедуры, когда в памяти хранится только одна копия кода процедуры, но эта копия является повторно входимой (реентерабельной). Это означает, что к про-цедуре можно еще раз обратиться, не дожидаясь завершения действий в со-ответствии с предыдущим входом в данную процедуру. Отсюда желательно, чтобы все обращения к реентерабельной процедуре также обрабатывались па-раллельно. Задача обеспечения дополнительного уровня параллелизма решается  в динамических потоковых ВС и реализуется двумя вариантами архитектуры потоковой ВС: архитектуры с помеченными токенами и архитектуры с явно адресуемыми  токенами.
 
5. Архитектура  потоковых  систем  с  помеченными  токенами
 
В архитектуре с помеченными токенами (tagged-token architecture) память хранит один экземпляр потокового графа. Каждый токен содержит тег (фишку), состоящий из адреса команды, для которой предназначено заключенное в то-     кене значение, и другой информации, определяющей вычислительный кон-   текст, в котором данное значение используется, например номера итерации     цикла. Этот контекст называется «цветом значения», а токен – «окрашенным»,     в силу чего метод имеет еще одно название – метод окрашенных токенов. Каждая дуга потокового графа может содержать произвольное число токенов с различными тегами. Основное правило активирования вершины в динамичес-  ких потоковых ВС имеет вид: вершина активируется, когда на всех ее входных дугах  присутствуют  токены  с  идентичными  тегами.

Рис. 11. Структура  процессорного  элемента  типовой  потоковой  системы      с  помеченными  токенами
 
Типовая архитектура потоковой системы с помеченными токенами показа-на на рис. 11. Для обнаружения одинаково окрашенных токенов (токенов с одинаковыми тегами) в конвейер процессорного элемента введен согласующий блок. Этот блок получает очередной токен из очереди токенов и проверяет, нет  ли в памяти согласования его партнера (токена с идентичным тегом). Если такой партнер не обнаружен, принятый токен заносится в память согласования. Если  же токен-партнер уже хранится в памяти, то блок согласования извлекает его оттуда и направляет оба токена с совпавшими тегами в блок выборки. На ос-     нове общего тега блок выборки находит в памяти команд/данных соответст-вующую команду и формирует пакет операции, который затем направляет в функциональный блок. Функциональный блок выполняет операцию, создает то-кены  результата  и  помещает  их  в  очередь  токенов.
Чтобы учесть возможные ситуации – циклы, элементы массивов, функции  и рекурсии, – тег каждого токена должен включать в себя три поля: Уровень итерации • Имя  функции • Индекс.
В каждом поле может содержаться число, начиная с нуля. Поле «Уровень итерации» хранит порядковый номер текущей итерации цикла; поле «Имя функ-ции» идентифицирует вызов функции; поле «Индекс» указывает на определен-  ный  элемент  массива.  Первые  два  поля  могут  быть  объединены  в  одно.
Индивидуальные поля тега трактуются как числовые значения, пересыла-емые от одной вершины к другой. Минимальным требованием к динамической потоковой ВС является наличие операций, позволяющих извлечь значение, содержащееся в каждом поле, или установить в любом поле иное значение. Например, операция «Прочитать поле токена» берет токен и формирует из него другой токен, где определенное поле заполнено содержимым аналогичного поля из входного токена. Операция «Установить поле токена» формирует выходной токен, совпадающий с входным, за исключением указанного поля, куда заносится значение, заданное в данной операции в виде литерала. Применительно к полю «Уровень итерации» могут быть предусмотрены операции инкремента и де-кремента.


 

Рис. 12. Архитектура  манчестерской  потоковой  вычислительной  системы
На рис. 12 приведена структура динамической потоковой ВС с архи-   тектурой окрашенных токенов, созданной в Манчестерском университете Гур-дом и Ватсоном в 1980 году. В этой ВС используется конвейерная кольцевая архитектура, и вычислительные функции отделены от функций согласования токенов и тегов. Каждый процессор обрабатывает пакеты длиной в 166 бит, содержащие два численных операнда, тег, код операции и один или два адре-      са следующей команды или команд. С каждым пакетом ассоциирован флаг «Система/ Вычисление», позволяющий отличить выполняемый пакет (пакет, который должен быть обработан процессором) и пакет, несущий системное сообщение (например, «Загрузить команду в память»). Численными операндами могут быть 32-разрядные целые числа, либо числа в формате с плавающей запятой.
Обработав выполняемый пакет, процессор генерирует один или два паке-  та (токена) результата. Пакет результата состоит из 96 битов и содержит один численный операнд, тег и адрес пункта назначения результата. Каждый пакет результата поступает на ключ, обеспечивающий либо ввод данных от внеш-      него источника, либо вывод на внешний объект (периферийное устройство). Поскольку токен результата должен быть передан на другую вершину потоко-вого графа, то он сначала направляется в очередь токенов, а оттуда – в блок согласования токенов. Здесь производится поиск других токенов, необходимых для инициирования вершины. Поиск ведется аппаратно, посредством сравнения пункта назначения и тега входного токена с аналогичными параметрами всех хранящихся в памяти токенов. Если совпадение произошло, из пары токенов формируется пакет, в противном случае входной токен запоминается  в блоке согласования токенов до момента, когда поступит согласующийся с ним токен. Пары токенов и токены с одним операндом передаются в память программ, содержащую узловые команды, и формируется полный выполняемый пакет. Выполняемые пакеты по возможности направляются в свободный процессор в массиве  из  15  процессоров.
Основное преимущество динамических потоковых систем – это более высокая производительность, достигаемая за счет присутствия на дуге множе- ства токенов. При этом основной проблемой является эффективная реализация блока, который собирает токены с одинаковыми тегами, т.е. с совпадающим цветом. В плане производительности этой цели наилучшим образом отвечает ассоциативная память. Однако такое решение является слишком дорогостоя- щим, поскольку число токенов, ожидающих совпадения тегов, достаточно ве-   лико. По этой причине в большинстве ВС вместо ассоциативных запоминаю-   щих  устройств  используются  обычные  адресные  ЗУ.
6. Архитектура  потоковых  систем  с  явно  адресуемыми  токенами
 
Значительным шагом в архитектуре потоковых ВС стало изобретение ме- ханизма явной адресации токенов (explicit token-store), имеющего и другое наз-вание – непосредственное согласование (direct matching). В основе этого меха-низма лежит то, что все токены в одной и той же итерации цикла и в одном и    том же вхождении в реентерабельную процедуру имеют идентичный тег (цвет). При инициализации очередной итерации цикла или очередном обращении к процедуре формируется кадр токенов, содержащий токены, относящиеся к дан-ной итерации или данному обращению, т.е. с одинаковыми тегами. Использо-    вание конкретных ячеек внутри кадра задается на этапе компиляции. Каждо-      му кадру выделяется отдельная область в специальной памяти кадров (frame memory), причем раздача памяти под каждый кадр происходит на этапе вы-полнения  программы.
В схеме с явной адресацией токенов любое вычисление полностью опи-   сывается указателем команды (IP, Instruction Pointer) и указателем кадра (FP, Frame Pointer). Этот кортеж <FP, IP> входит в тег токена, а сам токен выглядит следующим  образом:  Значение • FP.IP.
Команды, реализующие потоковый граф, хранятся в памяти команд и      имеют  формат:  Код операции • Индекс в памяти кадров • Адресат.
Поле «Индекс в памяти кадров» определяет положение ячейки с нужным токеном внутри кадра, т.е. какое число нужно добавить к FP, чтобы получить адрес этого токена. Поле «Адресат» указывает на местоположение команды, ко-торой должен быть передан результат обработки данного токена. Адрес в этом поле также задан в виде смещения, т.е. числа, которое следует прибавить к текущему значению IP, чтобы получить исполнительный адрес команды наз-начения в памяти команд. Если потребителей токена несколько, то в поле «Адресат» заносится несколько значений смещения. На рис. 13 показан прос-той  пример  кодирования  потокового  графа  и  токенов  на  его  дугах.

Рис. 13. Кодирование  в  архитектуре  с  явной  адресацией  токенов:    
    а – активизация  вершины  вычитания; б – активизация  вершин  умножения  и  сложения; в – кодирование  потокового  графа
 Каждому слову в памяти кадров придан бит наличия, единичное значе-  ние которого удостоверяет, что в ячейке находится токен, ждущий согласова-  ния, т.е. что одно из искомых значений операндов уже имеется. Как и в архи-тектуре с окрашенными токенами, определено, что вершины могут иметь мак-   симум две входные дуги. Когда на входную дугу вершины поступает токен      <v1, <FP, IP>>, в ячейке памяти кадров с адресом FP + (IP.I) проверяется бит наличия. Здесь IP.I означает содержимое поля I в команде, хранящейся по ад- ресу, указанному в IP. Если бит наличия сброшен (ни один из пары токенов      еще не поступал), то поле значения пришедшего токена (v1) заносится в ана-лизируемую ячейку памяти кадров, а бит наличия в этой ячейке устанавлива-      ется  в  единицу, фиксируя  тот  факт, что  первый  токен  из  пары  уже  доступен:
(FP + (IP.I)).значение := v1
(FP + (IP.I)).наличие := 1
Этот случай отражен на рис. 13, а, когда на вершину SUB по левой входной  дуге  поступил  токен  <35, <FP, IP>>. 
Если токен <v2, <FP, IP>> приходит на узел, для которого уже хранится значение v1, то команда, представляющая данную вершину, может быть акти-вирована и выполнена с операндами v1 и v2. В этот момент значение v1 из-влекается из памяти кадров, бит наличия сбрасывается, и на функциональный блок, предназначенный для выполнения операции, передается пакет команды  <v1, v2, FP, IP, IP.0P, IP.D>, содержащий операнды (v1 и v2), код операции  (IP.0P) и адресат ее результата (IP.D). Входящие в этот пакет значения FP и IP нужны, чтобы  вместе  с  IP.D  вычислить  исполнительный  адрес  адресата. После.
Рис. 14. Структура  процессорного  элемента  типовой  потоковой  системы      с  явной  адресацией  токенов
выполнения операции функциональный блок пересылает результат в блок фор-мирования токенов. Рис. 13, б демонстрирует ситуацию, когда токен уже пришел и на второй вход вершины SUB. Операция становится активируемой         и после ее выполнения результат передается на вершины ADD и  MUL, кото-      рые  ожидают  входных  токенов  в  ячейках  FP+3  и  FP+4  соответственно.
Типовая архитектура системы с явной адресацией токенов показана на    рис. 14. Функция согласования токенов стала достаточно короткой операци- ей, что позволило внедрить ее в виде нескольких ступеней процессорного кон-вейера.
7. Макропотоковые  вычислительные  системы
 
Рассмотренный ранее механизм обработки с управлением от потока дан-ных функционирует на уровне команд и относится к потоковой обработке низкого уровня (fine-grain dataflow). Данному подходу сопутствуют большие из-держки при пересылке операндов. Для уменьшения коммуникационных издер-жек необходимо применять потоковую обработку на процедурном уровне, т.е. укрупненную  потоковую  или  макропотоковую  обработку  (multithreading).
Макропотоковая модель совмещает локальность программы, характерную для фон-неймановской модели, с толерантностью к задержкам на переключение задач, свойственной потоковой архитектуре. Это достигается за счет того, что вершина графа представляет собой не одну команду, а последовательность из нескольких команд, называемых нитью (thread). По этой причине макропото-    ковая организация часто называется крупнозернистой потоковой обработкой (coarse-grained dataflow). Макропотоковая обработка сводится к потоковому вы-полнению нитей, в то время как внутри отдельной нити характер выполнения фон-неймановский. Порядок обработки нитей меняется динамически в процессе вычислений, а последовательность команд в пределах нити определена при ком-пиляции  статически. Структура  макропотоковой  ВС  представлена  на  рис. 15.
Рис. 15. Структура  процессорного  элемента  типовой  макропотоковой  системы
Отличие макропотоковой системы от обычной потоковой ВС состоит в организации внутреннего управляющего конвейера, где последовательность вы-полнения команд задается счетчиком команд, как в фон-неймановских маши-  нах.  Этот  конвейер  идентичен  обычному  конвейеру  команд.
В макропотоковой архитектуре (рис. 1, в) каждый узел графа пред-ставляет команду, а каждая закрашенная область – одну из нитей. Если команда приостанавливается, останавливается и соответствующая нить, в то время как выполнение  других  нитей  может  продолжаться.
Существуют две формы макропотоковой обработки: без блокирования и с блокированием. В модели без блокирования выполнение нити не может быть начато, пока не получены все необходимые данные. Будучи запущенной, нить выполняется до конца без приостановки. В варианте с блокированием запуск     нити может быть произведен до получения всех операндов. Когда требуется отсутствующий операнд, нить приостанавливается (блокируется), а возобновле-ние выполнения откладывается на некоторое время. Процессор запоминает всю необходимую информацию о состоянии и загружает на выполнение другую готовую нить. Модель с блокированием обеспечивает более гибкий подход к формированию нитей за счет дополнительной аппаратуры для хранения блоки-рованных нитей. Это выражается в возможности использования более длинных нитей.
Возможна также потоковая обработка переменного уровня, когда узлы соответствуют как простым операциям, так и сложным последовательным процедурам. Этот случай называется комбинированной обработкой с потоками данных и потоками управления (combined dataflow/control flow).
8. Гиперпотоковая  обработка
 
В основе гиперпотоковой технологии (hyperthreading), разработанной фир-мой Intel и впервые реализованной в микропроцессоре Pentium 4, лежит то, что современные процессоры являются суперскалярными и многоконвейерными,    т.е. выполнение команд в них идет параллельно, по этапам и на нескольких конвейерах сразу. Гиперпотоковая обработка раскрывает этот потенциал таким образом, чтобы функциональные блоки процессора были максимально загру-жены. Эта цель достигается за счет сочетания соответствующих аппаратных и программных  средств.
Выполняемая программа разбивается на 2 параллельных потока (threads). Задача компилятора (на стадии подготовки программы) и операционной систе- мы (на этапе выполнения программы) заключается в формировании таких пос-ледовательностей независимых команд, которые процессор мог бы обрабаты-  вать параллельно, заполняя функциональные блоки, не занятые одним из пото-ков,  подходящими  командами  из  другого  независимого  потока.
Операционная система, поддерживающая гиперпотоковую технологию, воспринимает физический суперскалярный процессор как два логических про-цессора и организует поступление на эти два процессора двух независимых потоков  команд.
Процессор с поддержкой технологии hyperthreading эмулирует работу двух одинаковых логических процессоров, принимая команды, направленные для каждого из них. Это не означает, что в процессоре имеются два вычислитель-   ных ядра – оба логических процессора конкурируют за ресурсы единственного вычислительного ядра. Следствием конкуренции является более эффективная загрузка  всех  ресурсов  процессора.
В процессе вычислений физический процессор рассматривает оба потока команд и по очереди запускает на выполнение команды то из одного, то из другого, или сразу из двух, если есть свободные вычислительные ресурсы. Ни один из потоков не считается приоритетным. При остановке одного из потоков     в ожидании какого-либо события или в результате зацикливания процессор полностью переключается на второй поток. Принципиальное отличие гипер-потоковой обработки от макропотоковой состоит в возможности чередования команд  из  разных  потоков.
Наличие только одного вычислительного ядра не позволяет достичь уд-военной производительности, однако за счет большей отдачи от всех внутренних ресурсов общая скорость вычислений существенно возрастает. Особенно это за-метно, когда потоки содержат команды разных типов. В этом случае замедление обработки в одном из потоков компенсируется увеличением объема работ, вы-полненных в другом потоке. Эффективность технологии hyperthreading зависит  от работы операционной системы, поскольку именно она осуществляет разде-ление  команд  на  потоки.
Рассмотрим особенности реализации гиперпотоковой технологии в про-цессоре Pentium 4 Xeon. Процессор способен параллельно обрабатывать два      потока в двух логических процессорах. Чтобы выглядеть для операционной сис-темы и пользователя как два логических процессора, физический процессор должен поддерживать информацию одновременно для двух отдельных и не-зависимых потоков, распределяя между ними свои ресурсы. В зависимости от вида ресурса применяются три подхода: дублирование, разделение и совместное использование.
Дублированные ресурсы. Для поддержания двух полностью независи- мых контекстов на каждом из логических процессоров некоторые ресурсы про-цессора необходимо дублировать. Это относится к счетчику команд (IP, Instruction Pointer), позволяющему каждому из логических процессоров отсле-живать адрес очередной команды потока. Для параллельного выполнения не-скольких процессов необходимо столько IP, сколько потоков команд необхо- димо отслеживать одновременно, т.е. у каждого логического процессора дол-   жен быть свой счетчик команд. В процессоре Xeon максимальное количество потоков команд равно двум, поэтому требуется два счетчика команд. Кроме то-  го, в процессоре имеются две таблицы распределения регистров (RAT, Register Allocation Table), каждая из которых обеспечивает отображение восьми регист-ров общего назначения (РОН) и восьми регистров с плавающей запятой (РПЗ), относящихся к одному логическому процессору, на совместно используемый регистровый файл из 128 РОН и 128 РПЗ. Таким образом, RAT – это дубли-рованный  ресурс,  управляющий  совместно  используемым  регистровым  фай-лом.
Разделенные ресурсы. В качестве разделенных ресурсов в Xeon высту-   пают очереди (буферная память, организованная по принципу FIFO), располо-женные между основными ступенями конвейера. Эти ресурсы разделяются ста-тически: каждая буферная память (очередь) разбивается пополам, и за каждым  логическим  процессором  закрепляется  своя  половина  очереди.
Другим видом очередей являются три очереди диспетчеризации команд, разделяемые динамически. Вместо того чтобы из предусмотренных в каждой очереди двенадцати входов фиксировано назначить входы 0-5 логическому процессору (ЛП) 0, а входы 6-11 – логическому процессору 1, каждому ЛП разрешается использовать любые входы очереди, лишь бы их общее число не превысило шести. Отсутствие привязки потоков к конкретным входам очереди позволяет не принимать во внимание наличие двух потоков и расценивать обе половины как единую очередь. Очередь диспетчеризации команд просматривает каждую команду в общей очереди, оценивает зависимости между командами, проверяет доступность ресурсов, необходимых для выполнения команды, и планирует команду к исполнению. Таким образом, выдача команд на исполне- ние не зависит от того, какому потоку они принадлежат. Динамическое раз-деление очередей диспетчеризации команд предотвращает монополизацию оче-редей  каким-либо  одним  из  логических  процессоров.
Для обеспечения максимальной производительности при обработке про-цессором Xeon только одного потока ему предоставляются все ресурсы про-цессора. В динамически разделяемых очередях снимаются ограничения на ко-личество входов, доступных одному потоку, а в статически разделяемых оче-    редях  отменяется  их  разбиение  на  две  половины.
Совместно используемые ресурсы. Первую группу общих ресурсов об-разуют функциональные блоки: целочисленные операционные устройства, бло- ки операций с плавающей запятой и блоки обращения (чтения/записи) к памя-   ти. Эти ресурсы «не знают», из какого ЛП поступила команда. То же самое относится и к регистровому файлу – второму виду совместно используемых ресурсов.
Общие ресурсы одновременно являются и силой гиперпотоковой техно-логии, и ее слабостью. Проблема возникает, когда один поток монополизирует ключевой ресурс (такой, как блок операций с плавающей запятой), чем блоки-рует другой поток, вызывая его остановку. Задача предотвращения таких ситу-аций возлагается на компилятор и операционную систему, которые должны образовать потоки, состоящие из команд с максимально различающимися тре-бованиями к совместно используемым ресурсам. Например, один поток может содержать команды, нуждающиеся главным образом в блоке для операций с плавающей запятой, а другой – состоять преимущественно из команд целочис-ленной  арифметики  и  обращения  к  памяти.
Третий вид общих ресурсов – кэш-память. Процессор Xeon работает с    кэш-памятью трех уровней (L1, L2 и L3) и кэш-памятью трассировки. Оба ло-гических процессора совместно используют одну и ту же кэш-память и хра-нящиеся в ней данные. Если поток, обрабатываемый логическим процессором     0, хочет прочитать некоторые данные, кэшированные логическим процессором   1, он может взять их из общего кэша. Использование в гиперпотоковом про-цессоре одной и той же кэш-памяти сразу двумя логическими процессорами приводит к возрастанию вероятности конфликтов и снижения производитель-ности.
Любой вид кэш-памяти одинаково трактует все обращения для чтения     или записи вне зависимости от того, какой из логических процессоров данное обращение производит. Это позволяет любому потоку монополизировать лю-   бой из кэшей, причем никакой защитой от монополизации, как это имеет мес-     то в случае очередей диспетчеризации команд, процессор не обладает. Физичес-кий процессор не в состоянии заставить логические процессоры сотрудничать   при  их  обращении  к  кэшам.
Среди совместно используемых ресурсов в технологии hyperthreading    кэш-память является наиболее критичным местом и конфликты за обладание     этим ресурсом сказываются на общей производительности процессора наибо-    лее  ощутимо.
В настоящий момент аппаратная поддержка технологии заложена в мик-ропроцессоры Pentium 4. Программная поддержка технологии предусмотрена в операционных  системах  Windows  2000,  Windows XP  и  Windows.NET Server.
9. Вычислительные  системы  с  управлением  вычислениями  по  запросу
 
В системах с управлением от потока данных каждая команда, для которой имеются все необходимые операнды, немедленно выполняется. Однако для получения окончательного результата многие из этих вычислений оказываются ненужными. Более прагматичен подход, когда вычисления инициируются не по готовности данных, а на основе запроса на данные. Такая организация вычис-лительного процесса называется управлением вычислениями по запросу (demand-driven control). В ее основе лежит представление вычислительного процесса в виде графа, как и в потоковой модели (data-driven control). В потоковой модели верхние узлы графа запускаются раньше, чем нижние (нисходящая обработка). Механизм управления по запросу состоит в обработке вершин потокового графа снизу вверх путем разрешения запуска узла, лишь когда требуется его результат. Данный процесс получил название редукции графа, а ВС, оперирующая в режиме снизу  вверх (рис. 1, г), называется  редукционной  вычислительной  системой.
Математическую основу редукционных ВС составляет лямбда-исчисление,  а программы для них пишутся на функциональных языках программирова-       ния (FP, Haskell). На функциональном языке все программы представляются         в виде выражений, а процесс выполнения программы заключается в определе- нии их значений. Это называется оценкой выражения. Она производится по-   средством повторения операции выбора и упрощения тех частей выражения, которые можно свести от сложного к простому. Такая часть выражения назы-вается редексом, а операция упрощения – редукцией. Выражение, не содержа-  щее редекса, называется нормальной формой. Процесс редукции завершается, когда  преобразованное  выражение  становится  нормальной  формой.
В редукционной ВС вычисления производятся по запросу на результат операции. Предположим, что вычисляется выражение . В случае потоковых моделей процесс начинается с самых внутренних операций, а имен-   но с параллельного вычисления  и . Затем выполняется операция ум-ножения  и самая внешняя операция – вычитание. Такие вычисления называются  энергичными  вычислениям и (eager  evaluation).
При вычислениях, управляемых запросами, все начинается с запроса на результат , который включает в себя запрос на вычисление выражений   и , а те в свою очередь формируют запрос на вычисление ,    т.е. на операцию самого внутреннего уровня. Результат возвращается в по-       рядке, обратном поступлению запросов. Отсюда название ленивые вычисления      (lazy evaluation), поскольку операции выполняются только тогда, когда их ре-зультат требуется другой команде. Редукционные вычисления согласуются с концепцией функционального программирования, упрощающей распараллели- вание  программ.
На рис. 16 показан процесс вычисления с помощью редукционной ВС значения выражения  для . Программа редукции состоит из распознавания редексов с последующей заме- ной их вычисленными значениями. Таким образом, в конечном итоге вся программа  редуцируется  до  результата.

Рис. 16. Пример  вычисления  выражения  на  редукционной  ВС:
а – исходное  положение;  б – после  первого  шага  редукции
Известны два типа моделей редукционных систем: строчная и графовая, отличающиеся тем, что именно передается в функцию – скопированные значе- ния  данных  или  только  указатели  на  места  их  хранения.
В строчной редукционной модели каждый запросивший узел получает от-дельную копию выражения для собственной оценки. Длинное строковое выра-жение рекурсивным образом сокращается (редуцируется) до единственного зна-чения. Каждый шаг редукции содержит оператор, сопровождаемый ссылкой на требуемые входные операнды. Оператор приостанавливается, пока оценивают-   ся  входные  параметры.
На рис. 17 показан процесс вычислений с помощью строчной редук-  ции. Если требуется значение  (рис. 17, а), то копируется граф программы, определяющий вычисление  (рис. 17, б). При этом за-пускается операция умножения. Поскольку это вычисление невозможно без предварительного расчета двух параметров, то запускаются вычисления «+» и    «–», в результате чего образуется редуцированный граф с ветвями «6» и «2», показанный на рис. 17, в. Результат получается путем дальнейшей редук-     ции  (рис. .17, г).
Рис. 17. Процесс  вычислений  в  модели  со  строчной  редукцией:
   а – исходный  граф;  б, в – последовательно  редуцированные  графы;    г – результат  редукции
 
 
 
В графовой редукционной модели выражение представлено как ориенти-рованный граф. Граф сокращается по результатам оценки ветвей и подграфов.     В зависимости от запросов возможно параллельное оценивание и редукция      различных частей графа или подграфов. Запросившему узлу, который управ-   ляет всеми ссылками на граф, возвращается указатель на результат редукции. «Обход» графа и изменение ссылок продолжаются, пока не будет получено значение  результата,  копия  которого  возвращается  запросившей  команде.
Рис. 18 иллюстрирует пример вычислений с помощью графовой редукции. В этой модели, когда требуется найти значение , определение вы числения  не копируется, а передается указатель определяющей программы. При достижении узла «´» направление переданного указателя меняется на   противоположное, чтобы запомнить место, из которого будет выдаваться ре-зультат вычисления (рис. 18, б). Далее путем повторения операции смены направления текущего указателя на обратное получается граф, показанный на       рис. 18, в. Теперь операции «+» и  «–» можно выполнять, граф редуцируется  сначала  до  изображенного  на  рис. 18, г,  а  затем – на  рис. 18, д.


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

 

источник информации
http://eunu04.narod.ru/ComputerSystems/lec14.htm
 
 
 

Комментарии

Отправить комментарий

Содержание этого поля является приватным и не предназначено к показу.
  • Доступны HTML теги: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd> <img> <table> <td> <tr> <hr> <div> <span> <h1> <h2> <h3> <h4> <h5> <h6> <p> <pre> <adress> <center>
  • Строки и параграфы переносятся автоматически.

Подробнее о форматировании

10 + 1 =
Решите эту простую математическую задачу и введите результат. Например, для 1+3, введите 4.

Комментарии