22 мая: Генерация кода как задача математического программирования

Самборский Сергей Владиславович

Самборский Сергей Владиславович

Самборский Сергей Владиславович — старший научный сотрудник НИИСИ РАН (сектор автоматизации программирования), выпускник мех.-мат. факультета МГУ, занимается инструментальными средствами для разрабатываемых процессоров. Вьюкова Надежда Ивановна — старший научный сотрудник НИИСИ РАН, выпускник мех.-мат. факультета МГУ. Галатенко Владимир Антонович — старший научный сотрудник, доктор физ-мат наук, заведующий сектором автоматизации программирования. Область научных интересов: средства программирования, эффективные алгоритмы, математическое программирование и задачи оптимизации.

Традиционно генерация кода для линейного или циклического участка программы делится в компиляторах на три последовательно выполняемые задачи: выбор инструкций процессора, составление расписания и распределение регистров.
Этот подход обеспечивает качественный код как для традиционных RISC-процессоров с «однородной/симметричной» системой команд и большим числом взаимозаменяемых регистров, так и для современных процессоров, выполняющих распараллеливание и переупорядочивание выполнения команд собственным планировщиком, а также имеющих необходимый для этого механизм переименования регистров.
С другой стороны, последовательный подход к генерации кода плохо приложим к процессорам для встроенных систем и обработки сигналов. Эти процессоры обычно имеют короткие команды, а значит не позволяют использовать большое количество регистров, и не имеют механизмов переименования и переупорядочивания. Кроме того, для них характерны специализированные расширения системы команд.
Предлагается подход, основанный на том, что задачи выбора команд (из некоторого заранее подготовленного множества) и составления расписания могут быть вместе сформулированы на языке целочисленного линейного программирования (ЦЛП). Кроме того, можно сразу учитывать ограничение на число используемых регистров разных типов, так чтобы сделать тривиальным последующее распределение регистров. Более того, включив в исходное множество команд инструкции для сохранения и восстановления виртуальных регистров, можно при нехватке физических регистров автоматически получить оптимальный spill-код.
Среди преимуществ данного подхода можно указать: наиболее полное использование параллельного исполнения инструкций процессором, возможность автоматически использовать специализированные проблемно-ориентированные расширения системы команд процессора, и, в некоторых ситуациях, оптимизацию вычисления преобразованиями, основанными на математических тождествах.

Вы можете присылать свои вопросы как до доклада, так и во время него, по электронной почте sdat@ispras.ru или в твиттер @sdat_seminar. Но лучше всего прийти к нам на семинар лично в МГУ. На входе действует пропускная система, поэтому для оформления пропуска заранее пришлите, пожалуйста, свою фамилию, имя и отчество на sdat@ispras.ru (не забудьте взять с собой паспорт).

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>