Вычислительные системы с управлением вычислениями по запросу

В системах с управлением от потока данных каждая команда, для которой имеются все необходимые операнды, немедленно выполняется. Однако для получения окончательного результата многие из этих вычислений оказываются ненужными. Более прагматичен подход, когда вычисления инициируются не по готовности данных, а на основе запроса на данные. Такая организация вычис-лительного процесса называется управлением вычислениями по запросу (demand-driven control). В ее основе лежит представление вычислительного процесса в виде графа, как и в потоковой модели (data-driven control). В потоковой модели верхние узлы графа запускаются раньше, чем нижние (нисходящая обработка). Механизм управления по запросу состоит в обработке вершин потокового графа снизу вверх путем разрешения запуска узла, лишь когда требуется его результат. Данный процесс получил название редукции графа, а ВС, оперирующая в режиме снизу вверх (рис. 14.1, г), называется редукционной вычислительной системой.

Математическую основу редукционных ВС составляет лямбда-исчисление, а программы для них пишутся на функциональных языках программирова- ния (FP, Haskell). На функциональном языке все программы представляются в виде выражений, а процесс выполнения программы заключается в определе- нии их значений. Это называется оценкой выражения. Она производится по- средством повторения операции выбора и упрощения тех частей выражения, которые можно свести от сложного к простому. Такая часть выражения назы-вается редексом, а операция упрощения – редукцией. Выражение, не содержа- щее редекса, называется нормальной формой. Процесс редукции завершается, когда преобразованное выражение становится нормальной формой.

В редукционной ВС вычисления производятся по запросу на результат операции. Предположим, что вычисляется выражение . В случае потоковых моделей процесс начинается с самых внутренних операций, а имен- но с параллельного вычисления и . Затем выполняется операция ум-ножения и самая внешняя операция – вычитание. Такие вычисления называются энергичными вычислениям и (eager evaluation).

При вычислениях, управляемых запросами, все начинается с запроса на результат , который включает в себя запрос на вычисление выражений и , а те в свою очередь формируют запрос на вычисление , т.е. на операцию самого внутреннего уровня. Результат возвращается в по- рядке, обратном поступлению запросов. Отсюда название ленивые вычисления (lazy evaluation), поскольку операции выполняются только тогда, когда их ре-зультат требуется другой команде. Редукционные вычисления согласуются с концепцией функционального программирования, упрощающей распараллели- вание программ.

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

Рис. 14.16. Пример вычисления выражения на редукционной ВС:

а – исходное положение; б – после первого шага редукции

Известны два типа моделей редукционных систем: строчная и графовая, отличающиеся тем, что именно передается в функцию – скопированные значе- ния данных или только указатели на места их хранения.

В строчной редукционной модели каждый запросивший узел получает от-дельную копию выражения для собственной оценки. Длинное строковое выра-жение рекурсивным образом сокращается (редуцируется) до единственного зна-чения. Каждый шаг редукции содержит оператор, сопровождаемый ссылкой на требуемые входные операнды. Оператор приостанавливается, пока оценивают- ся входные параметры.

На рис. 14.17 показан процесс вычислений с помощью строчной редук- ции. Если требуется значение (рис. 14.17, а), то копируется граф программы, определяющий вычисление (рис. 14.17, б). При этом за-пускается операция умножения. Поскольку это вычисление невозможно без предварительного расчета двух параметров, то запускаются вычисления «+» и «–», в результате чего образуется редуцированный граф с ветвями «6» и «2», показанный на рис. 14.17, в. Результат получается путем дальнейшей редук- ции (рис. 14.17, г).

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

В графовой редукционной модели выражение представлено как ориенти-рованный граф. Граф сокращается по результатам оценки ветвей и подграфов. В зависимости от запросов возможно параллельное оценивание и редукция различных частей графа или подграфов. Запросившему узлу, который управ- ляет всеми ссылками на граф, возвращается указатель на результат редукции. «Обход» графа и изменение ссылок продолжаются, пока не будет получено значение результата, копия которого возвращается запросившей команде.

Рис. 14.18 иллюстрирует пример вычислений с помощью графовой ре- дукции. В этой модели, когда требуется найти значение , определение вы- числения не копируется, а передается указатель определяющей программы. При достижении узла «´» направление переданного указателя меняется на противоположное, чтобы запомнить место, из которого будет выдаваться ре-зультат вычисления (рис. 14.18, б). Далее путем повторения операции смены направления текущего указателя на обратное получается граф, показанный на рис. 14.18, в. Теперь операции «+» и «–» можно выполнять, граф редуцирует- ся сначала до изображенного на рис. 14.18, г, а затем – на рис. 14.18, д.

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

Контрольные вопросы

1. Перечислите и охарактеризуйте возможные механизмы управления вы-числительным процессом.

2. В чем состоит идея управления от потока данных?

3. Какие элементарные операторы могут быть взяты в качестве вершин потокового графа?

4. Каким образом осуществляется передача данных между узлами потоко- вого графа?

5. В чем состоит принципиальное различие между статической и динами-ческой потоковой архитектурами?

6. Выполнение какого условия, кроме наличия входных данных, требуется для активации операции в статической потоковой ВС?

7. Опишите структуру пакетов действий и пакетов результата в статической потоковой ВС и поясните назначение полей этих пакетов.

8. Какой смысл вкладывается в понятие «окрашенный токен»?

9. Сохраняется ли в потоковых ВС принцип локальности по обращению, свойственный вычислительным системам фон-неймановского типа?

10. Определите понятие thread применительно к макропотоковой обработке.

11. В чем заключаются преимущества макропотоковой обработки над обыч- ной потоковой?

12. Каким образом и при каких условиях гиперпотоковая обработка способ-ствует повышению производительности процессора?

13. Почему вычислительные системы с управлением по запросу называют редукционными?

14. Какой математический аппарат лежит в основе редукционных ВС? Пояс-ните основные положения этого аппарата.

15. Поясните различия между строковой и графовой моделями редукции.

Дата добавления: 2014-01-04