[Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]

Journal of Inforamtion Science and Engineering, Vol.14 No.1, pp.139-165 (March 1998)
Simulated Evolution Based Parallel Code Generation
for Programmable DSP Processors*

Yin-Tsung Hwang and Jer-Sho Hwang
Institate of Electronic and Information Engineering
National Yunlin University of Science and Technology
Yunlin, Taiwan 640, R.O.C

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.

Keywords: code generation, compiler, digital signal processors, instruction scheduling, memory assignment, register allocation, simulated evolution

Received May 1, 1997; revised December 10, 1997.
Communicated by PeiZong Lee.
* This research was financially supported by NSC projects 85-2213-E-224-020 and 86-2221-E-224-007.