Пример 2
Пример (2) выражения a + b^c+d+e
1. S.S1 а
2. S.S2 Ъ
3. S.S3 с
4. S.S4 S.S2*S.S3
5. S.S5 S.S1+S.S4 (7)
6. S.S6 d
7. S.S7 S.S5+S.S6
8. S.S8 е
9. S.S9 S.S8+S.S7
легко видеть, что мы не можем практически переставить никакие команды, чтобы уменьшить задержки выполнения команд 5, 7, 9.
Целью планирования по балансу является получение такого дерева, которое обеспечивало лучшие возможности для последующей перестановки команд, которые могли быть получены обычной генерацией по этому дереву.
Для получения такого дерева вводится некоторая весовая функция на дереве. Эта функция позволяет оценить любую ветвь или поддерево. Функция строится с учетом каждого узла дерева, которое фактически эквивалентно некоторому функци ональному устройству со своим временем выполнения команды. Весовая функция на ветви, входящей в некоторый узел или на этом же узле, точнее говоря, принимается равной максимальному значению функций на всех ветвях сыновьях, плюс время выполнения команды в этом же узле. Мы стремимся построить такое дерево, которое соответствует минимальной весовой функции по всем возможным деревьям. При этом ищем его в виде сбалансированного дерева. Это означает, что для любых двух поддеревьев, исходящих из одного узла их весовые функции будут или равны, или иметь разницу минимальную из всех возможных. Время всех однотипных листовых узлов принимается равным.
Здесь подразумевается, что время выполнения команды умножения соответствует приблизительно времени выполнения 2-х команд сложения, вторая из которых использует результат первой.
Рассматривая полученное дерево, можно также сказать, что при генерации команд по оптимизированному дереву будет обеспечена возможность независимого параллельного запуска большего числа функциональных устройств, чем по исходному дереву.
Тем самым мы имеет большую свободу в перестановке команд.
Замечание: Если бы в качестве оптимизационной задачи становилась задача обеспечения кода с максимальной степенью совмещения работы функциональных устройств, то, вероятно, можно было бы прийти к аналогичному виду оптимизации, воз можно с другой весовой функцией. В нашем же случае это не определялось в качестве критерия, хотя планирование по балансу улучшает в определенной мере дерево и по совмещению функциональных устройств.
Метки: пример