An Approach to Scheduling in a Hardware-Software Co-Design Toolchain

Typ
Examensarbete för masterexamen
Master Thesis
Program
Publicerad
2011
Författare
Frolov, Nikita
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
Much like VLIW, statically scheduled architectures that expose all control signals to the compiler offer much potential for highly parallel, energy-efficient performance. A cornerstone to effective compilation for such architectures is an effective solution to the phase ordering problem, i.e., planning the cooperation between instruction scheduling and register allocation. Existing heuristic algorithms that approach this problem are hard to analyze and to break down to reusable concepts that might lead to better algorithms, which is one of the major obstacles for adoption of VLIW architectures. An approach based on a combination of a domain-specfic language (DSL) embedded in a higherorder language and a constraint satisfiability engine makes it possible to structure the problem and abstract away from generic search space exploration methods. Bau is a novel compilation infrastructure that leverages the LLVM compilation tools and the MiniSAT solver to generate effient code for one such exposed architecture, FlexCore. A compiler construction library is built that allows the compiler writer to express scheduling and resource constraints declaratively, as a set of constraints in a DSL, each describing one property of a valid schedule. It provides a framework to rapidly modify aspects of a backend and explore tradeoffs between compilation time and quality of compiled code. A compiler implemented using this library can generate programs that are 1.2{1.5 times more compact than ones generated either by a baseline MIPS R2K compiler or a basic-block-based, sequentially phased scheduler. However, further optimization of the instruction lowering pass is needed to improve performance.
Beskrivning
Ämne/nyckelord
Datorteknik , Computer Engineering
Citation
Arkitekt (konstruktör)
Geografisk plats
Byggnad (typ)
Byggår
Modelltyp
Skala
Teknik / material
Index