Владимир Прус / Евгений Балашов, 5й курс, mod-sem

На этом форуме публикуются и уточняются постановки задач студентам, а также отслеживается ход их выполнения

Модератор: staff

Закрыто
Бычков Иван
Аспирант
Сообщения: 179
Зарегистрирован: 23 сен 2008 01:19 pm

Владимир Прус / Евгений Балашов, 5й курс, mod-sem

Сообщение Бычков Иван »

Тема работы

Процессорозависимые оптимизации для процессора NM6403.

Актуальность

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

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

План работы
  • Тестирование и исправление ошибок кодогенератора на представительном наборе тестов
  • Знакомство с литературой по распределению регистров
  • Выбор перспективных методов и их возможных модификаций
  • Реализация и тестирования
Ожидаемые результаты

Минимум -- кодогенератор с "нормальным" распределением регистров. Максимум -- то же, плюс планирование инструкций в рамках линейных участов и циклов.

Здесь есть большая вилка, поскольку сложность задачи пока еще не полностью понятна.
Евгений Балашов
Выпускник
Сообщения: 1
Зарегистрирован: 12 дек 2008 09:34 pm

Сообщение Евгений Балашов »

Отчет о состоянии научной работы на конец 9го семестра.

Сделано за этот семестр:
1. Описаны все ограничения на регистры, существующие в архитектуре.
2. Изучен ряд методов распределения регистров, применяющихся к архитектурам для встроенных систем.
o Метод, основанный на раскраске графов, адаптированный с учетом регистровых пар: каждый регистр, соответствующий регистровой паре заменяется двумя регистрами, каждый из которых связан дугой со свой парой и со всеми регистрами, с которыми был связан исходный виртуальный регистр.
o Метод, основанный на раскраске обобщенного графа взаимодействия регистров – классический алгоритм, основанный на раскраске адаптируется для учета регистровых классов. Каждому узлу в графе взаимодействия регистров ставится в соответствие его регистровый класс и при вычислении критерия раскрашиваемости вершины учитывается возможное количество конфликтов с соседними узлами.
o Сведение задачи распределения регистров к задаче линейного программирование. В этом методе все конфликты, возникающие в архитектуре задаются в виде весовых функций (функции строятся для каждого виртуального регистра и для каждой пары взаимодействующих виртуальных регистров), после чего все функции переписываются в матричном виде и задача сводится задаче линейного программирования, которую можно решать различными эвристическими алгоритмами.
3. Предложены несколько подходов для адаптации этих алгоритмов к процессору NM6403.
Основная проблема адаптации алгоритмов к NM6403 – регистровые банки, остальные ограничения уже учтены так или иначе в алгоритмах.
o Для методов, основанных на раскраске графов, предлагается помечать подграфы, которые должны принадлежать одному регистровому банку. После этого преобразованиями графа сводить его к графу, в котором возможна раскраска с учетом ограничения на регистровые банки.
o Для метода, основанного на линейном программировании возможно указание конфликта между виртуальными регистрами, использующимися внутри отдельной инструкции процессора. Это усложняет процесс построения весовых функций, но позволяет описать необходимые ограничения.

Дальнейшие планы по научной работе
• Адаптация одного из существующих методов для архитектуры NM6403 (формулировка алгоритма).
• Реализация и отладка алгоритма в рамках системы LLVM.
• Тестирование полученного распределителя регистров (тестирование на корректность выдаваемого кода, сравнение со штатным компилятором для NM6403).

Литература:
1. А. Ахо, Р. Сети, Д. Ульман. Компиляторы: принципы, технологии и инструменты. М.: «Вильямс», 2003. – 768 с.
2. Chris Lattner. Introduction to the LLVM Compiler Infrastructure [PDF] (http://llvm.org/pubs/2006-04-25-GelatoLLVMIntro.pdf)
3. Архитектура процессора Л1879ВМ1 (NM6403). [PDF] (http://www.module.ru/files/nm6403arch-r.pdf)
4. Нейропроцессор NM6403. Введение в архитектуру. [PDF] (http://www.module.ru/files/nm6403ao11b-r.pdf)
5. D. Koes, S. С. Goldstein. A Progressive Register Allocator for Irregular Architectures [PDF] (http://www.cs.cmu.edu/~seth/papers/koes-cgo05.pdf)
6. J. Runeson, Sven-Olof Nystr¨om. Retargetable Graph-Coloring Register Allocation for Irregular Architectures [PDF] (http://user.it.uu.se/~svenolof/wpo/AllocSCOPES2003.pdf)
7. A. Sudarsanam and S. Malik. Simultaneous Reference Allocation in Code Generation for Dual Data Memory [PDF] (http://portal.acm.org/citation.cfm?id=335043.335047)
8. B. Scholz, E. Eckstein. Register Allocation for Irregular Architectures [PDF] (http://portal.acm.org/citation.cfm?id=513829.513854)
9. T. Kong, K. D. Wilken. Precise Register Allocation for Irregular Architectures [PDF] (http://www.princeton.edu/~echi/register ... rarchs.pdf)
10. J. C. Y. Paek, D. Whalley. Efficient Register and Memory Assignment for Non-orthogonal Architectures via Graph Coloring and MST Algorithms [PDF] (http://portal.acm.org/citation.cfm?id=513829.513853)
11. P.Briggs Register Allocation via Graph Coloring [PDF] (http://citeseer.ist.psu.edu/102127.html)
12. GJ Chaitin Register allocation & spilling via graph coloring[PDF] (http://www.cs.ucsd.edu/~paturi/cse202/p ... haitin.pdf)
Никита Ющенко
Сотрудник
Сообщения: 155
Зарегистрирован: 25 авг 2004 01:02 pm

Сообщение Никита Ющенко »

Отчёт был бы неплохим, если бы был написан студентом 3-го или 4-го курса. Разобрался с предметной областью, предложил направления модификации, осталось уточнить до конкретного алгоритма, реализовать и поисследовать. Выглядит добротно.

Но вот для дипломника сделано откровенно мало, а осталось много - и имеются риски (а что если на практике предложенные идея окажутся плохи). Следует резко ускориться - прямо сейчас. Иначе можно просто не успеть.
Закрыто