Оптимизация циклов методом наложения итераций
| Вид материала | Документы |
- Решение алгебраических уравнений высоких степеней. Решение нелинейных уравнений методом, 9.13kb.
- Пояснительная записка к курсовому проекту на тему «Оптимизация функции двух переменных, 137.41kb.
- Приказ от 10 марта 1998 г. N 19 об утверждении методических указаний о порядке выдачи, 128.89kb.
- Исследование сложных процессов методом дта, 38.19kb.
- CA09 Экономическая сущность «циклов Кузнеца» и их влияние на развитие экономики, 127.11kb.
- Вопросы по макроэкономике, 21.91kb.
- Пивоваров И. А. Н. Д. Кондратьев и проблемы исследования динамики социально-экономических, 113.84kb.
- Контрольная работа по курсу «Линейной алгебры и математического программирования», 99.84kb.
- Optimization Toolbox – Оптимизация, 780.37kb.
- Развития мировой экономики а. В. Легчилкин, 157.84kb.
ОПТИМИЗАЦИЯ ЦИКЛОВ МЕТОДОМ НАЛОЖЕНИЯ ИТЕРАЦИЙ
В ДИНАМИЧЕСКОМ ДВОИЧНОМ ТРАНСЛЯТОРЕ ДЛЯ АРХИТЕКТУРЫ “ЭЛЬБРУС-3М”
Гимпельсон В.Д.
E-mail: gimpelso@mcst.ru
Динамическая двоичная трансляция является мощным и универсальным средством, позволяющим исполнять двоичные коды созданные для одной микропроцессорной архитектуры на другой архитектуре. Примерами новых EPIC-архитектур могут служить микропроцессоры Crusoe фирмы Transmeta и микропроцессоры Itanium фирмы Intel. Для достижения высокой производительности двоичного транслятора необходимо максимально полно задействовать все аппаратные возможности, предоставляемые архитектурой.
Оптимизация циклов методом наложения итераций или конвейеризация циклов является одним из самых эффективных алгоритмов для извлечения максимально возможной параллельности в циклах. В докладе приводится описание программного метода наложения итераций цикла реализованного в двоичном компиляторе с исходной архитектуры x86 на целевую архитектуру “Эльбрус-3М”.
Отличием двоичных компиляторов от языковых, является наложение существенных дополнительных семантических ограничений на результирующий код, таких как возможность точного восстановления контекста, проявление всех прерываний и т.д. Поэтому одной из задач поставленных перед рассматриваемым алгоритмом является максимально универсальное и гибкое встраивание в инфраструктуру и аналитические структуры данных двоичного компилятора. Данная задача была решена и потребовались лишь минимальные доработки в других частях компилятора. Это позволило оставить неизменным и фактически переиспользовать ранее найденные решения для обеспечения точной семантики исходной архитектуры.
Ещё одним обязательным условием для двоичных компиляторов является время, затрачиваемое на компиляцию кода. Это ограничение было выдержано. Были использованы только алгоритмы полиномиальной сложности с невысокими степенями.
Центральным местом рассматриваемого алгоритма конвейеризации циклов является разметка времён планирования на графе зависимостей расширенном обратными зависимостями. Эта информация является главным аналитическим звеном алгоритма. В докладе приводится описание алгоритма разметки времён, а также доказывается его корректность и оптимальность.
Интересной задачей оказалось сочетание технологии вращающихся регистров, которая позволяет значительно увеличить эффективность алгоритма, и задачи обеспечение точного контекста. В результате анализа была предложена доработка в аппаратуре, позволяющая решить эту задачу просто и эффективно.
В заключении рассматриваются возможные направления дальнейшего развития оптимизации циклов методом наложения итераций, а также приводится экспериментальные данные, полученные в рамках проекта двоичного компилятора с архитектуры x86 на архитектуру “Эльбрус-3М”.