Оптимальная трассировка памяти для DAG оценок зависимостей

Я ищу алгоритм, который оптимизирует порядок оценок в DAG, так что используется наименьшая память. Это может быть немного сложнее объяснить, поэтому я приведу пример, что я имею в виду. Учтите, что у вас есть DAG с несколькими корнями, что представляет собой некоторую форму порядка оценки зависимостей. Поэтому каждый ребенок node может выполнять свое действие только после того, как его родители выполнили. Кроме того, мы можем освободить из памяти каждый node, который нам больше не нужен. Задача состоит в том, чтобы найти оптимальный последовательный график оценки, чтобы наименьшая память использовалась в любое время. Например, рассмотрим приведенный ниже график:

Evaluation Graph

И два графика:

load A - 1 node in memory
load B - 2 
eval C - 3
eval D - 4
eval F - 5
unload C - 4
eval H - 5
unload A,F - 3
eval E - 4
eval G - 5
unload D,E - 3
eval I - 4
unload B,G - 2
eval J - 3
unload H,I

Maximum memory trace - 5

И этот:

load A - 1 node in memory
load B - 2 
eval C - 3
eval D - 4
eval E - 5
eval F - 6
unload C - 5
eval G - 6
unload D,E - 4
eval H - 5
unload A,F - 3
eval I - 4
unload B,G - 2
eval J - 3
unload H,I - 1
unload C - 4
eval H - 5
unload A,F - 3
eval E - 4
eval G - 5
unload D,E - 3
eval I - 4
unload B,G - 2
eval J - 3
unload H,I

Maximum memory trace - 6

Предполагая, что все узлы занимают одну и ту же память, есть ли алгоритм, который делает это оптимально? Первый из них похож на первый шаг по глубине, а второй - как обход первого дыхания, но я не знаю, оптимальны ли они и почему.

PS:

Просто, чтобы уточнить, как отметил в своем комментарии @Evgeny Kluev, это очень похоже на Register Allocation, которое можно эффективно решить с помощью эвристических алгоритмов алгоритма грациозного графа. Однако распределение регистров является более простой проблемой, поскольку предполагает, что вы знаете порядок вычислений и, следовательно, можете рассчитать жизнеспособность каждой переменной. После этого вы можете легко построить граф вывода и выполнить раскраску графика. В нашем случае мы хотим, чтобы , а также оптимизировали порядок вычислений. Это, конечно, требует некоторых предположений, например, что у нас нет указателей и только базовые структуры данных (что и представляют мои узлы). Очевидно, что поскольку раскраска графа NP-полная, эта проблема по крайней мере NP-полная. То, что я ищу, - это какой-то алчный/эвристический алгоритм, который дает хорошее решение для некоторых не слишком дегенеративных случаев.

Ответы

Ответ 1

На самом деле, в некотором смысле эта проблема проще, чем проблема окраски графа, потому что решающая версия этой проблемы является частным случаем версии решения Комбинированного распределения регистров и инструкций Задача планирования (CRISP), которая проще решить, чем проблема окраски графа (по крайней мере, когда точное решение не требуется).

Решение этой проблемы можно сформулировать так: существует ли расписание, использующее не более m слотов памяти?

Сокращение до CRISP

Обратите внимание, что ниже я буду использовать терминологию из указанной статьи.

Для каждого node v в вашей проблеме допустим ввести в CRISP виртуальный регистр r v и команду x v, инструкция записывает в регистр r v и читает каждый регистр r u, соответствующий родительскому node u node v. Кроме того, для каждого ребра (u, v) DAG вводится ребро (x u, x v) в графике зависимостей CRISP. Время выполнения каждой команды равно 1, латентность каждого края зависимостей равна 0, а стоимость разлива равна ∞. Количество доступных физических регистров равно m.

Если в CRISP есть расписание на длительность не более, чем число узлов, то в исходной задаче есть соответствующее расписание, в котором используется не более m слотов памяти. Мы закончили.

Если память, используемая родителем, не может быть повторно использована детьми

Приведенная выше редукция предполагает, что память, используемая родителем, может повторно использоваться дочерними элементами, когда родитель больше не нужен. Если это не разрешено, необходимы следующие изменения:

Добавьте еще одну инструкцию y v для каждого node v. Теперь x v записывает только r v, а y v читает каждый r u, соответствующий родительскому u. Добавить границу графа зависимостей (x v, y v). Установите время выполнения каждой команды на 0,5. Это все.

Обратите внимание, что разделение записи регистров и чтения между различными инструкциями требуется для предотвращения повторного использования родительских регистров, когда это не разрешено.

Алгоритм

В статье, которая упоминается в начале, описывается эффективный алгоритм для решения CRISP. Он также может быть использован для решения этой проблемы — просто используйте приведенное выше сокращение и попробуйте каждый m, начиная с 1, пока не будет найдено решение.

Отметим также, что алгоритм параметризуется двумя параметрами: α и β, где α - вес для регулирования давления в регистре, а β - вес для команды управления parallelism. Для этой задачи установите α в 1 и β в 0, так как команда parallelism не нужна для этой проблемы.