Near-Optimal Instruction
Selection for Resource Constrained Embedded Architectures
Tuesday October 16, 2007
Hamerschlag Hall D-210
4:30 pm
Dave Koes
Carnegie Mellon University
Code size, although often ignored in the workstation space, is an important optimization
goal when targeting embedded processors. Embedded designs often have a small, fixed amount
of on-chip memory to store and execute code with.
A small difference in code size could necessitate a costly redesign. Instruction selection
is an important part of code size optimization since the instruction selector is
responsible for effectively exploiting the complexity of the target instruction set.
Although instruction selection on tree expressions is a well understood and easily solved
problem, instruction selection on directed acyclic graphs is NP-complete.
In this paper we present NOLTIS, a near-optimal, linear time instruction selection
algorithm for DAG expressions. NOLTIS is easy to implement, fast, and effective with
demonstrated average code size improvements of up to 9.5%.
Dave doesn't think computers are fast enough or that compilers are good enough. After
working as a compiler writer for Green Hills Software in dreary Santa Barbara, CA, he
entered grad school in an attempt to remedy that situation.
He is an Nth year graduate student in the computer science department with a thesis topic
on the principled integration of register allocation and instruction selection in a
progressive backend optimizer.
There is a high probability that cookies will be provided at his talk and an even higher
probability that his presentation will contain an above average number of baby pictures.
His advisor is Seth Goldstein.
|