A dynamic programming approach to complex allocation in a DSP pipelined processor

This paper describes a deterministic non-serial dynamic programming technique applicable to a code optimization problem for the Star Core 140 (SC140) DSP processor. The code optimization problem analyzed is an optimal register allocation problem that minimizes the expected number of execution sets with a two-word prefix for the SC140 core applications based on two probabilistic allocation policies. We introduce two basic algorithms, a linear bridging algorithm and a non-linear bridging algorithm (supporting loops), that solve the specific register allocation problem for an assembly language code block. All algorithms and methods are applied to a variety of SC140 assembly code applications. The optimized assembly language codes generated show an average of 68%, improvement in overheads and an average of 4.44% code size reduction at a very small increase in the CPU time costs. The basic principles and methods developed throughout this research are general and are applicable to other pipelined processors.