litceysel.ru
добавить свой файл
1

Доклад

“Применение рандомизированных методов
при планировании инструкций
с использованием
профиля микроархитектуры”

Кодизайн


В настоящее время бурно развивается область кодизайна, или совместной программно-аппаратной разработки (HSC, Hardware/Software Codesign). Появление данной области относят к началу 90-х годов, когда термин <кодизайн> был введен в обиход для описания совокупности проблем проектирования интегральных схем. В это время дело шло к появлению кристаллов, которые могли вместить и центральный процессор, и другие требуемые подсистемы. Одни из первых программных систем, поддерживающих кодизайн, были разработаны в Стэндфордском университете и техническом университете города Брауншвейг. Эти системы предназначались для поддержки проектирования микропроцессорных систем, включающих, помимо центрального процессора, дополнительную интегральную схему (например, плату MPEG-кодирования), ориентированную на приложения (ASIC, Application-Specific Integrated Circuit). Ближе к концу 90-х годов направление кодизайна приобрело зрелость. Был разработан ряд важных алгоритмов, появились программные системы, поддерживающие разработку сложных микропроцессорных архитектур с произвольной топологией внутренних соединений и произвольным комбинированием центральных процессоров и ASIC. В настоящее время кодизайн становится основным подходом к созданию различных <систем на кристалле> (SoC, System on Chip), в особенности тех, которые базируются на вентильных матрицах с эксплуатационным программированием (FPGA, Field Programmable Gate Array). Использование методов кодизайна позволяет заметно сократить время выхода на рынок, а также уменьшить сложность создания и цену интегральных схем.

Технология PADLA

В рамках технологии предлагается способ автоматизированного получения прототипа, основанный на извлечении макроархитектуры аппаратной платформы из реализации на языке высокого уровня. Такой подход позволяет исключить стадию настройки средств разработки на целевую платформу, поскольку система команд и код реализации для нее порождаются одновременно. Кроме того, помимо собственно прототипирования рассматриваются задачи оптимизации, решение которых может быть автоматизировано в рамках данного подхода.

Выбор и оптимизация архитектуры – Design Space Exploration


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

Планирование инструкций


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

Локальное и глобальное планирование.

LS (List Scheduling)


Среди методов планирования для конвейерных архитектур хорошо зарекомендовал себя List Scheduling [Gib86]. Это эвристический метод, основанный на графах (graph-based). Его недостаток – отсутствие фазы распределения регистров, которая должна выполняться либо до, либо после планирования инструкций. В нашем случае распределение регистров выполняет Padla-компилятор. Он определяет число регистров, при котором не возникнет антизависимостей в целевой программе, и находит наилучшее для программы распределение регистров. Недостаток метода не играет роли в случае PADLA т.к. число регистров подбирается при генерации микроархитектуры.

Используется наиболее часто. За быстрое время дает неплохой результат. Хорошо работает для кода, сгенерированного компилятором.


Существует две разновидности:

  • operation driven

  • instruction driven

Сложность O(n).

Применяемые эвристики


1. height – the maximum number of arcs from this node to any sink node.

2. on_critical_path – the operation is on the longest path in the DDD.

3. on_schedule_critical_path. – the operation is on the longest path in the DDD when operation timings are considered.


4. lexical_order – ordering of nodes from source. Fisher [10] suggests that program lexical order is not a good metric for list scheduling priority, but it can be used for non-ILP architectures to produce a default ordering.

5. branch_node– the node is a branch node, especially useful in the presence of delayed, restricted branching mechanisms. This has been used to increase the chance a branch node will be placed before other operations.

6. resource_usage_of_this_type – the amount of use of this node’s resource in this DDD. The more contention for resources, the earlier a node should be placed in order to free the resource as soon as possible for reuse.

7. used_and_defined_resources – as above, nodes that use more resources than others should be scheduled so they do not interfere with others needing those resources.

8. least_recently_used_resource – a method of forming round-robin reference to resources.

9. field_usage_of_this_type – as with resources, try to minimize instruction field conflicts.

10. fields_used.

11. least_recently_used_field.

12. successors – the more successors a node has, the earlier it should be scheduled, allowing its successors to become data ready as early as possible. This exposes more parallelism to the scheduler.

13. restricted_successors – the more restricted successors 3. a node has, the earlier it should be scheduled so timing is more flexible within the DDD.

14. total_restricted_successors – total of the timings for all restricted successors

15. shortest_restricted_successor

16. distance_from_successors – a measure of how restricted the edges to the successors are.

17. predecessors – the more predecessors a node has, the later it should be scheduled, allowing its predecessors to become data ready as early as possible. This exposes more parallelism to the scheduler.

18. restricted_predecessors – the more restricted predecessors a node has, the later it should be scheduled so timing is more flexible within the DDD.


19. total_restricted_predecessors – total of all restricted predecessors.

20. shortest_restricted_predecessor

21. distance_from_predecessors – a measure of how restricted the edges to the predecessors are.

22. schedule_spread – the number of instructions in which an operation can be placed. The greater the spread, the more flexibility for placement.

23. average_restricted_successor_gap – the average of _(e) for all the restricted successors.

24. average_restricted_predecessor_gap – the average of _(e) for all the restricted successors.

IR (Iterative Repair)


Формируется исходный план без учета конфликтов.

На каждой итерации выбирается первая операция, вызывающая конфликт, производится unscheduling (ее и дочерних узлов), затем rescheduling, далее следующая итерация.

RBF (Randomized Backward-Forward)


Выполняется сначала LS-планирование вперед, потом назад. И так N-раз.

Критерии оптимизации


  • время

  • размер

  • энергопотребление

  • цена



Направления исследований

Стохастические алгоритмы


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

Генетические алгоритмы


В каждой популяции выбираются наилучшие планы, и выполняется скрещивание.

Рандомизированные алгоритмы


Выбираем несколько параметров процессора (например, число конвейеров или число ALU) и ищем глобальный минимум для функции оценки выбранной характеристики программы. Делаем измерения (выполняем планирование) и по результатам настраиваем веса эвристик и параметры процессора.

yn = F(wn, xn) + vn


f(x) = интеграл F(w, x) Pw(dw) по Rn, где

y – выбранный измеряемый критерий (к-во операций, задержки, энергопотребление, …);

x – параметры эвристик;

w – исходная программа.

Библиография





  • [Bra91a] Bradlee, Eggers , Henry, The Marion System for Retargetable Instruction Scheduling, 1991;

  • [Cof76] Coffman. Computer and Job-Shop Scheduling Theory, 1976;

  • [Coo98] Cooper, Schielke, Subramanian. An Experimental Evaluation of List Scheduling, 1998;

  • [Geb92] Gebotys, Elmasry. Optimal VLSI Architectural Synthesis, 1992;

  • [Geb93] Gebotys, Elmasry. Global Optimization Approach for Architectural Synthesis, 1993;

  • [Gib86] Gibbons, Muchnick. Efficient instruction scheduling for a pipelined architecture, 1986;

  • [Had98] Hadjiyiannis, ISDL: Instruction Set Description Language, 1998;

  • [Hal99] Halambi, Grun, Ganesh, Nicolau, Expression: A Language for Architecture Exploration through Compiler/Simulator Retargetability, 199l;

  • [Kas00a] Kastner, A Hardware and Assembly Description Language. Number TDL 1.4, 2000;

  • [Kas00b] Kastner, PROPAN: A Retargetable System for Postpass Optimizations and Analyses, 2000;

  • [Kas01] Kastner, ILP-based Approximations for Retargetable Code Optimization, 2001;

  • [Mos97a] Moss, Utgoff, Brodley. Learning to Schedule Straight-Line Code, 1997;

  • [Mos97b] Moss, Cavazos.Learning Policies for Local Instruction Scheduling, 1997;

  • [Sch00] Schielke. Stochastic Instruction Scheduling, 2000;

  • [Qin02] Qin, Malik, Architecture Description Languages for Retargetable Compilation, 2002.