Simulated evolution based parallel code generation for programmable DSP processors

Modern digital signal processors are capable of performing multiple pipelined instructions concurrently. However, strict and complicated coding rules must be observed to achieve full performance. These include efficient multi-operands accesses, smart use of data and address registers, and novel instruction scheduling to support parallel execution without pipeline conflicts. In this paper, an iterative code generation scheme based on the framework of simulated evolution is devised. In each iteration, the instruction scheduling derived from the previous iteration is first evaluated. The inferior part is probabilistically discarded and rescheduled. On the other hand, register allocation and memory assignment are also performed iteration-wise subject to the new schedule, and the results are fed back to the next iteration's instruction scheduling. This can effectively solve the mutual dependence problem between the scheduling and allocation phases. The iteration process proceeds until a valid schedule is derived. To make the system retargetable, we have also derived and summarized coding constraints from various digital signal processor architectures. Basic resolutions to these constraints are proposed and have been successfully integrated into our code generation scheme. In our implementation, we chose the TI TMS320C30 as the target processor. The results of eleven tested benchmark programs, covering algorithms from filtering to transform computation, indicate that our scheme can double the performance of TI's complimentary C30/40 optimizing C compiler in terms of code size and can generate very efficient assembly codes.