В работе [44] рассматривается метод, позволяющий для заданной иерархии вложенных конструкций if-then-else выбрать оптимальные (по средней скорости выполнения результирующей программы) способы реализации.
Поддержка условного выполнения делает особенно эффективным планирование в древовидных областях [32], [31]. Для каждого линейного участка древовидной области вычисляется предикат, который приписывается всем командам этого участка. В результате исключается большая часть условных переходов и появляется возможность планировать параллельное исполнение различных ветвей дерева.
Метод доминантного параллелизма при планировании в древовидных областях
Недостаток метода "дублирования хвостов" заключаются в генерации избыточного кода. При использовании упреждающего исполнения это приводит к нерациональному расходованию вычислительных ресурсов и может замедлить исполнение. В ряде случаев планировщик способен исключить отрицательные последствия при помощи метода доминантного параллелизма (dominator parallelism) [31]. Если команды из некоторого линейного участка BBi и его копии BBi' можно поднять в доминирующий участок BBk (являющийся общим предком BBi и BBi'), то можно оставить только по одному экземпляру команд. Пример ситуации, когда этот прием применим, показан на рис. 17.
Рис. 17. Доминантный параллелизм. Командy r6=0 из линейного участка BB5 и его копии BB5' можно поднять в BB2 (или BB1) и исключить их дублирование
Планирование по прогнозу значений данных
Упреждающее выполнение команд по прогнозу данных (data speculation) широко применяется в динамическом аппаратном планировании в суперскалярных процессорах. Смысл этого приема заключается в том, что значение объекта используется до того, как оно записано, в предположении, что значение останется прежним. Разумеется, если значение все-таки изменяется, процессор обеспечивает перевычисление команд, выполненных с упреждением. EPIC-архитектуры предоставляют аппаратную поддержку для использования аналогичного механизма при статическом планировании в компиляторе по отношении к объектам, хранящимся в памяти, см. [36] или [60].
... ...
MEM(R0) = R1 R2=MEM(R3)' ; упреждающее
... ; чтение
R2=MEM(R3) ...
R4=R2+R2 MEM(R0)=R1
... check(address(R3)),L1
R4=R2+R2
a) b)
Рис. 18. Перестановка операций чтения и записи с использованием аппаратной поддержки упреждающего чтения
При наличии таких аппаратных средств компилятор получает возможность переупорядочивать команды чтения и записи памяти. Это может быть полезно по нескольким причинам:
как можно раньше выполнить команды считывания из памяти, лежащие на критическом пути;
использовать свободную позицию в командном слове,
исключить задержки, связанные с чтением данных из памяти.
На рис. 18a показан пример последовательности вычислений, содержащий команды записи в память (MEM(R0) = R1) и чтения из памяти (R2=MEM(R3)). Компилятор, вообще говоря, не имеет права запланировать чтение раньше записи, если он не имеет точной информации о том, что команда записи не перепишет считываемое значение.
Аппаратная поддержка упреждающего считывания из памяти может состоять из следующих средств (см. [13], [36]):
имеется команда упреждающего считывания, которая считывает значение по указанному адресу и запоминает этот адрес во внутренней таблице процессора;
при записи в память и при обычном считывании содержимое таблицы проверяется, и если в ней присутствует указанный адрес, то соответствующий элемент таблицы помечается как недействительный (или просто исключается)
имеется команда, позволяющая узнать, не было ли записи по заданному адресу с момента упреждающего считывания по этому адресу; если запись была, то выполнить переход по указанному адресу. Подразумевается, что по этому адресу должен находиться компенсирующий код.
На рис. 18b показан пример перестановки чтения и записи памяти с использованием этих средств. Команда чтения (в упреждающем режиме) помещается до команды записи. На месте прежнего положения команды считывания (до использования результата) помещена команда проверки адреса. Если оказалось, что по этому адресу была произведена запись, то управление передается по метке L1, где размещается сгенерированный компилятором компенсирующий код.
Особенности генерации кода для ЦПОС
Особенности генерации эффективного кода для ЦПОС связаны как с нерегулярностью схем кодирования, так и с другими характерными чертами этих процессоров, такими как наличие специализированных команд, нескольких пространств памяти и др. В этом разделе представлены специфические подходы, применяемые в компиляторах для ЦПОС.
Наиболее важной в контексте компиляции для ЦПОС представляется задача планирования (сжатия) кода. Специфика планирования для VLIW-процессоров с нерегулярными схемами кодирования связана с многочисленными ограничениями на параллельное исполнение команд, из-за которых существенно снижаются возможности использования внутреннего параллелизма программы при генерации кода. В ЦПОС также в меньшей степени представлены аппаратные расширения для поддержки параллелизма - условное выполнение, поддержка упреждающего выполнения. При этом именно для данного класса процессоров, в силу специфики областей применения, генерация оптимального кода имеет особенно важное значение.
В силу перечисленных причин в компиляторах для ЦПОС вместо эвристического глобального планирования более разумным представляется применение алгоритмов для поиска точного оптимального решения в пределах линейных участков.
В [45] приводятся следующие аргументы в пользу локального планирования:
Методы глобального планирования так или иначе опираются на локальные методы, которые сами по себе в контексте компиляции для ЦПОС еще недостаточно изучены и разработаны. Поэтому разумно начать с их детального исследования и оценки.
Популярные глобальные методы разрабатывались для регулярных VLIW-процессоров с высоким уровнем аппаратного параллелизма и проявили свою высокую эффективность для этого класса архитектур, в то время как в ЦПОС уровень параллелизма как правило значительно ниже из-за ограничений кодирования.
В глобальном планировании для сохранения корректности программы в нее приходится добавлять компенсирующий код. Это может привести к существенному увеличению размера программы, что неприемлемо, если объем памяти ограничен.
К этому можно добавить, что:
Преимущества глобального планирования экспериментально подтверждены для программ нечисленного характера; для программ численных расчетов выигрыш от глобального планирования, вероятно, не столь значителен.
Применение глобального планирования наиболее эффективно при наличии аппаратных расширений для его поддержки.
В [45] рассматривается подход к задаче локального планирования для определенного класса ЦПОС, основанный на методах целочисленного линейного программирования (см. [10]) и позволяющий находить кратчайший выходной код для процессора с заданными ограничениями на параллельное исполнение команд. Хотя время нахождения решения экспоненциально зависит от длины линейного участка, по мнению авторов, применение подобных подходов в компиляции для ЦПОС оправдано. Важная положительная черта предлагаемого метода заключается в поддержке вариантов команд - если процессор предоставляет несколько различных типов команд для выполнения одной и той же операции, то при поиске оптимального решения обеспечивается перебор вариантов.
В [23] и [29] также представлены реализации локальной оптимизации кода для ЦПОС на основе методов линейного программирования. В этих реализациях совмещается решение задач распределения регистров, распараллеливания и выбора команд (code selection) с учетом наличия в процессоре составных операций типа A=A+B*C.
Другая проблема, обусловленная нерегулярным характером кодирования, - способ представления ограничений на параллельное исполнение команд в планировщике. Если в регулярных ILP-архитектурах эти ограничения достаточно легко описать и представить в виде общего числа функциональных устройств каждого вида и наборов устройств, занимаемых каждой командой, то для процессоров с нерегулярным кодированием их рациональное представление составляет более сложную задачу. В [59] описывается подход, позволяющий свести нерегулярный набор ограничений к регулярному представлению путем определения набора искусственных аппаратных ресурсов и приписывания соответствующего мультимножества ресурсов каждому виду команд процессора. Недостатком предлагаемой реализации является то, что ее применимость ограничена слишком жесткими предположениями о структуре системы команд.
Характерной особенностью многих ЦПОС является малое число регистров, их специализация или кластерная организация. Это также требует особых подходов при распараллеливании и выборе кода ([16], [43]).
Как показано в [23], применение некоторых оптимизаций, считающихся машиннонезависимыми (таких как свертка констант, исключение общих подвыражений), в контексте компиляций для ЦПОС требует особых подходов с учетом специфики организации командного слова и числа доступных регистров в конкретном целевом процессоре.
Поскольку при программировании для ЦПОС обычно налагаются ограничения на размер кода, то при реорганизациях циклов и встраивании функций необходимо учитывать этот фактор. С этой точки зрения интересна работа [42], где рассматривается методика встраивания функций с контролируемым ростом объема кода. Аналогичные методики могут быть полезны и для преобразований циклов.
Важно понимать, что проблема генерации оптимального кода для ЦПОС не сводится только к задаче сжатия кода с учетом возможностей параллельного исполнения. Хороший компилятор для ЦПОС должен уметь эффективно использовать их архитектурные особенности - решать задачу оптимального размещения программных данных в пространствах памяти [41], поддерживать языковые расширения для указания пространства памяти в декларациях переменных [33], решать задачу выбора кода с учетом имеющегося набора команд в процессорах с системами команд для специальных приложений - Application Specific Instruction Set Processors (ASIP), (см. [16],[17]), выделять циклические буферы, оптимизировать способы адресации при обращениях к памяти (см. [29], [41], [46]) и др.