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

Abstract

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.