Оптимальное упорядочение деревьев: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Оптимальное упорядочение деревьев''' (''[[Optimal ordering for trees]]'') | '''Оптимальное упорядочение деревьев''' (''[[Optimal ordering for trees]]'') — | ||
Существует простой [[алгоритм]] определения оптимального порядка, в котором | Существует простой [[алгоритм]] определения оптимального порядка, в котором | ||
следует осуществлять вычисления, образующие линейный участок | следует осуществлять вычисления, образующие линейный участок | ||
| Строка 7: | Строка 7: | ||
Алгоритм состоит из двух частей. Первая помечает каждую [[вершина|вершину]] дерева, двигаясь снизу вверх, некоторым числом, которое обозначает минимальное количество регистров, необходимое для | Алгоритм состоит из двух частей. Первая помечает каждую [[вершина|вершину]] дерева, двигаясь снизу вверх, некоторым числом, которое обозначает минимальное количество регистров, необходимое для | ||
вычисления [[поддерево|поддерева]] с данным [[корень|корнем]] при условии, что не делается запоминаний промежуточных результатов. Вторая часть | вычисления [[поддерево|поддерева]] с данным [[корень|корнем]] при условии, что не делается запоминаний промежуточных результатов. Вторая часть — это [[обход графа|обход дерева]], порядок которого управляется вычисленными [[метка|метками]] вершин. Выходной код генерируется во время указанного обхода дерева. Содержательно алгоритм, обрабатывая два операнда бинарной операции, сначала работает над вычислением того из них, который | ||
требует больше регистров (более трудный операнд). Если потребность в регистрах у обоих операндов совпадает, то каждый из операндов может быть обработан первым. | требует больше регистров (более трудный операнд). Если потребность в регистрах у обоих операндов совпадает, то каждый из операндов может быть обработан первым. | ||
| Строка 15: | Строка 15: | ||
регистров являются ''[[NP-Полная задача|<math>\mathcal NP</math>-Полными]]''. | регистров являются ''[[NP-Полная задача|<math>\mathcal NP</math>-Полными]]''. | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998. | |||
Текущая версия от 15:03, 31 мая 2011
Оптимальное упорядочение деревьев (Optimal ordering for trees) — Существует простой алгоритм определения оптимального порядка, в котором следует осуществлять вычисления, образующие линейный участок программы для случая, когда они представлены в виде дерева. Оптимальность здесь понимается в том смысле, что порядок задает самую короткую последовательность команд машины из всех возможных для данного дерева.
Алгоритм состоит из двух частей. Первая помечает каждую вершину дерева, двигаясь снизу вверх, некоторым числом, которое обозначает минимальное количество регистров, необходимое для вычисления поддерева с данным корнем при условии, что не делается запоминаний промежуточных результатов. Вторая часть — это обход дерева, порядок которого управляется вычисленными метками вершин. Выходной код генерируется во время указанного обхода дерева. Содержательно алгоритм, обрабатывая два операнда бинарной операции, сначала работает над вычислением того из них, который требует больше регистров (более трудный операнд). Если потребность в регистрах у обоих операндов совпадает, то каждый из операндов может быть обработан первым.
В общем случае, когда луч может содержать общие подвыражения и представляется дэгом, задача генерации кода существенно усложняется: задачи оптимальной генерации кода по дэгу для одноадресной машины, а также для машины с неограниченным числом регистров являются [math]\displaystyle{ \mathcal NP }[/math]-Полными.
Литература
- Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.