Новосибирский государственный университет

Факультет информационных технологий

ICT SBRAS

Словарь терминов в коллекции "Вычислительные системы"

Редукционные вычислительные системы

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

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

В редукционной ВС вычисления производятся по запросу на результат операции.

Предположим, что вычисляется выражение a = (b+1)×c-d/c. В случае потоковых моделей процесс начинается с самых внутренних операций, а именно с параллель¬ного вычисления (b+1) и d/c. Затем выполняется операция умножения (b+1)×c и, наконец, самая внешняя операция - вычитание. Такой род вычислений часто называют энергичными вычислениями (eager evaluation).

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

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

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

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

Ключевые термины, связанные с термином "редукционные вычислительные системы":

  1. Управление вычислениями по запросу

Ключевые термины:  demand driven;   управление вычислениями по запросу;   лямбда-исчисление;   функциональное программирование;


Контекстный поиск: Задайте образец для поиска:
    

|Список основных тем курса|
   
Федотова Ольга
[SBRAS]

НГУ
ФИТ НГУ
ИВТ СО РАН
© 2012-2024, Новосибирский государственный университет, Новосибирск
© 2004-2024, Институт вычислительных технологий СО РАН, Новосибирск
© 2004-2024, Федотов А.М.
    Дата последней модификации: 15.08.2013