Редукция - граф
Cтраница 1
Редукция графа сохраняет его прямой порядок. [1]
Редукция графов естественным образом является ленивой; следующий редекс находится с помощью спуска по левому гребню графа, пока не будет найдена вершина функции. [2]
Редукция графов может быть параллельной, с помощью размещения отдельных редексов на отдельных процессах для вычисления. [3]
Редукция графов происходит с помощью именно этих макросов. Макрос EVAL инициализирует вычисление выражения, которое в ленивой системе является требуемым результатом, если его вычисление не будет специальным образом форсировано. EVAL служит для вычисления выражений верхнего уровня ( см. разд. Выполнение UNWIND и RET всегда отчасти аналогично применению EVAL. Применение примитивных функций происходит по В-схеме ( см. разд. [4]
В редукции графа ( М, N, Т) контуров не содержится. Если граф ( М, N, Т) сам не содержит контуров, то при редукции он не изменяется. [5]
Хотя параллельная редукция графов находится в детском возрасте, она представляет очень интересный новый подход к параллельным вычислениям. Во время написания этой книги исследования по параллельной редукции графов и разработке машины такой редукции активно проводились несколькими группами во всем мире Машины, описанные в [27, 44, 54] и [71], все являются или машинами чистой редукции графов, или основываются в своих операциях во многом на принципах редукции графов. [6]
При редукции графа нормального порядка мы находим следующий ре-декс путем сканирования графа в глубину слева направо. Чтобы сначала вычислить аргументы, мы должны от каждой - воршины графа идти вправо, пока это возможно. Таким образом, необходим просмотр графа в глубину справа налево. [7]
Далее начинается редукция графа, которая приводит к графу, изображенному на рис 44 Фиктивные дуги изображены на этих двух графах штриховыми линиями. В реальных задачах фиктивных дут обычно оказывается значительно меньше. [8]
В качестве альтернативы для редукции графов, где вычисление выражения инициируется, только когда требуется его значение, можно придумать графовую модель, в которой выражение вычисляется при первой возможности; другими словами, применение функции в такой модели имеет место, как только аргументы этой функции становятся доступными. При этом вычисление начинается при наличии аргументов, а не тогда, когда имеется запрос, а результирующая модель вычислений называется потоковой. Потоковая модель естественным образом является управляемой данными и может рассматриваться как оптимизированная форма энергичной редукции графов. Потоковые реализации описываются в гл. [9]
Мы начинаем наше обсуждение редукции графов с рассмотрения функции, выполняющей редукцию, в качестве интерпретатора графов функциональных выражений. Перед выполнением редукции необходимо сначала установить местоположение вершины следующего редекса и определить, представляет эта вершина Р - или б-редекс. [10]
Поскольку наиболее естественная реализация основана на редукции графов, модель вычислений является ленивой, а так как отсутствуют переменные, то нет необходимости рассматривать вопрос об их именах и контексте. К сожалению, даже очень простое Х - выражение имеет сложный эквивалент в КЛ и, хотя отсутствуют переменные, уменьшение накладных расходов из-за отсутствия контекста эффективно компенсируется необходимостью передавать выражения аргументов в качестве параметров. Таким образом, этот сырой подход не применим на практике без оптимизации с целью повышения эффективности. [11]
 |
Проблема свободных переменных в редукции графов. [12] |
Читатель мог заметить, что при редукции графа выражения вполне возможно присутствие в этом графе множества редексов в любой момент времени. [13]
На этом заканчивается наше обсуждение реализации редукции графов с помощью фиксированного набора комбинаторов. Этот подход является, несомненно, математически элегантным, устраняет проблему свободных переменных и может быть реализован относительно эффективно. Набор комбинаторов Тернера делает данный подход жизнеспособным для некоторых практических реализаций функциональных языков, а различные дальнейшие расширения этого фиксированного набора ком - бинаторов привели к значительному повышению эффективности. Проблемой, неотъемлемо присущей данному подходу, является небольшой размер структурного элемента вычислений. Так, этот размер предельно мал в случае S, К, 1 - представления, и это приводит к чрезмерно большим накладным расходам при вычислении. [14]
Спуск является первой операцией, выполняемой при редукции графа, представляющего выражение верхнего уровня или новый подграф, и поэтому он использует новый сегмент стека, называемый фреймом стека, который начинается в текущей вершине стека ( ВС) и, таким образом, строится на вершине предыдущего фрейма стека. В процессе спуска позиция основания нового фрейма стека запоминается для дальнейшего использования и указатели на каждую - вершину левого гребня ( под) графа последовательно проталкиваются в стек. Число - вершин гребня является поэтому глубиной фрейма стека по завершению спуска. [15]
Страницы: 1 2 3 4