Cтраница 4
Хотя параллельная редукция графов находится в детском возрасте, она представляет очень интересный новый подход к параллельным вычислениям. Во время написания этой книги исследования по параллельной редукции графов и разработке машины такой редукции активно проводились несколькими группами во всем мире Машины, описанные в [27, 44, 54] и [71], все являются или машинами чистой редукции графов, или основываются в своих операциях во многом на принципах редукции графов. [46]
Хотя параллельная редукция графов находится в детском возрасте, она представляет очень интересный новый подход к параллельным вычислениям. Во время написания этой книги исследования по параллельной редукции графов и разработке машины такой редукции активно проводились несколькими группами во всем мире Машины, описанные в [27, 44, 54] и [71], все являются или машинами чистой редукции графов, или основываются в своих операциях во многом на принципах редукции графов. [47]
Данная модель естественным образом является ленивой, так что вычисляются только те подвыражения, значения которых необходимы. Другими словами, мы говорим, что данная модель вычисления является управляемой запросами, имея в виду, что вычисление выражения начинается, только когда его значение явным образом затребовано. Основная модель редукции графов описывается в гл. [48]
В предыдущей главе была рассмотрена основанная на использовании стеков абстрактная машина для вычисления функциональных выражений, написанных в соответствии с нотацией А-исчисления. Как мы видели, эта машина наиболее удобна для реализации вычислений аппликативного порядка, соответствующих вызовам по значению Расширение области применения машины с целью поддерживать вызовы по необходимости требует введения дополнительных структур для явного представления задержек В этой главе будет рассмотрен совсем другой подход к вычислению лямбда-выражений, при котором мы допускаем представление выражений в виде графов, а не в виде линейных текстовых строк. Результирующая модель вычислений по очевидным причинам называется редукцией графов. Одно очевидное преимущество заключается в том, что в графовом представлении легко выразить разделение; нам не нужна дополнительная структура, такая, как контекст, для запоминания связей ( разделяемых) переменных, поскольку на ( разделяемый) подграф можно ссылаться любое число раз с помощью указателей. Второе преимущество данного представления в том, чю вычисление нормального порядка в этом случае легко представляется и относительно эффективно реализуется. Все это делает редукцию графов особенно естественным инструментом Для поддержки вызовов по необходимости и, следовательно, ленивого вычисления в функциональных языках. [49]
Если при этом фиксированный трехвалентный элемент графа G содержит вершину степени 3, инцидентную треугольнику, то редукция уменьшает число ребер графа G по крайней мере на одно ребро. Если же граф G не содержит такой вершины, то покажем, что в этом случае существует конечная последовательность редукций, приводящих к графу, содержащему вершину степени 3, инцидентную треугольнику. Очевидно, что каждый граф G, полученный редукцией планарного трехсвязного графа G, также планарен и трех-связен. [50]
В качестве альтернативы для редукции графов, где вычисление выражения инициируется, только когда требуется его значение, можно придумать графовую модель, в которой выражение вычисляется при первой возможности; другими словами, применение функции в такой модели имеет место, как только аргументы этой функции становятся доступными. При этом вычисление начинается при наличии аргументов, а не тогда, когда имеется запрос, а результирующая модель вычислений называется потоковой. Потоковая модель естественным образом является управляемой данными и может рассматриваться как оптимизированная форма энергичной редукции графов. Потоковые реализации описываются в гл. [51]
И наш интерпретатор, и SECD-машина являются основанными на контексте, так что фактические параметры функции запоминаются в отдельном контексте, а не подставляются физически в тело функции. Альтернативой этому является использование двумерного графового представления выражений. Вычислитель, редуцирующий выражения в этой форме к их конечным значениям, называется редуктором графов а общая модель вычислений - редукцией графов. [52]
Однако можно ввести дополнительные комбинаторы, уменьшающие сложность результирующих комбинаторных выражений, и в разд. Затем мы увидим, как различными способами с помощью У-комбинатора могут обрабатываться рекурсивные определения. В графовой форме У имеет особенно эффективное представление, ведущее к очень элегантной обработке произвольных рекурсивных определений; более того, рекурсия может выражаться подобным образом в других формах редукции графов, которые были рассмотрены в предыдущей главе. В заключение мы по-другому посмотрим на реализацию, использующую фиксированный набор комбинаторов, и опишем метод, основанный на так называемых строках направляющих. Он дает интуитивное понимание того, как работают фиксированные комбинаторы, а также предлагает более эффективный путь их представления. [53]
Впервые мысль о применимости абстрактной интерпретации для анализа строгости была высказана в [69], который использовал эту методику также для исследования проблемы установления условной конечности времени вычисления выражения. Основной задачей здесь является повышение эффективности ленивой реализации функционального языка путем поиска возможности доступа к аргументам по значению, а не по необходимости без изменения условий окончания работы программы. Как мы видели в предыдущих главах, это устраняет необходимость в создании задержек для аргументов в SECD-машине и в то же время уменьшает количество структур данных, создаваемых во время прогона программы и обрабатываемых в дальнейшем сборщиком мусора. Более того, если при параллельной редукции графов известна строгость каждой определенной пользователем функций, то это позволяет производить вычисление строгих аргументов параллельно с вычислением функции, увеличивая тем самым степень параллелизма. [54]