Code generation of nested loops for DSP processors with heterogeneous registers and structural pipelining

ABSTRACT

We propose a microcode-optimizing method targeting a programmable DSP processor. Efficient generation of microcodes is essential to better utilize the computation power of a DSP processor. Since most state-of-the-art DSP processors feature some sort of irregular architectures and most DSP applications have nested loop constructs, their code generation is a nontrivial task. In this paper, we consider two features frequently found in contemporary DSP processors — structural pipelining and heterogeneous registers. We propose a code generator that performs instruction scheduling and register allocation simultaneously. The proposed approach has been implemented and evaluated using a set of benchmark core algorithms. Simulation of the generated codes targeted towards the TI TMS320C40 DSP processor shows that our system is indeed more effective compared with a commercial optimizing DSP compiler.

REFERENCES

• 1: TEXAS INSTRUMENTS, INC., 1991. TMS320 Floating-Point DSP Optimizing C Compiler. Texas Instruments, Austin, TX.
• 2: TEXAS INSTRUMENTS, 1991. TMS320C4x. Texas Instruments, Austin, TX.
• 3: TEXAS INSTRUMENTS, 1991. TMS320C4x C Source Debugger. Texas Instruments, Austin, TX.
• 4: Guido Araujo , Sharad Malik, Optimal code generation for embedded memory non-homogeneous register architectures, Proceedings of the 8th international symposium on System synthesis, p.36-41, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224493]
• 5: Guido Araujo , Sharad Malik , Mike Tien-Chien Lee, Using register-transfer paths in code generation for heterogeneous memory-register architectures, Proceedings of the 33rd annual conference on Design automation, p.591-596, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240630]
• 6: David G. Bradlee , Susan J. Eggers , Robert R. Henry, Integrating register allocation and instruction scheduling for RISCs, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.122-131, April 08-11, 1991, Santa Clara, California, United States
• 7: P. Briggs , K. D. Cooper , K. Kennedy , L. Torczon, Coloring heuristics for register allocation, ACM SIGPLAN Notices, v.24 n.7, p.275-284, July 1989
• 8: BUCK, J., HA, S., LEE, E. A., AND MESSERSCHMITT, D. G. 1991. Ptolemy: A platform for heterogeneous simulation and prototyping. In Proceedings of the European Conference on Simulation. 155-182.
• 9: David Callahan , Brian Koblenz, Register allocation via hierarchical graph coloring, ACM SIGPLAN Notices, v.26 n.6, p.192-203, June 1991
• 10: Frederick Chow , John Hennessy, Register allocation by priority-based coloring, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.222-232, June 17-22, 1984, Montreal, Canada
• 11: DAVIDSON, S., LANDSKOV, D., SHRIVER, B. D., AND MALLETT, P.W. 1981. Some experiments in local microcode compaction for horizontal machines. IEEE Trans. Comput. C-30, 7 (July), 460-477.
• 12: Paul M. Embree , Bruce Kimble, C language algorithms for digital signal processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 13: Philip B. Gibbons , Steven S. Muchnick, Efficient instruction scheduling for a pipelined architecture, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.11-16, June 25-27, 1986, Palo Alto, California, United States
• 14: J. R. Goodman , W.-C. Hsu, Code scheduling and register allocation in large basic blocks, Proceedings of the 2nd international conference on Supercomputing, p.442-452, June 1988, St. Malo, France [doi>10.1145/55364.55407]
• 15: Gert Goossens , Dirk Lanneer , Marc Pauwels , Francis Depuydt , Koen Schoofs , Augusli Kifli , Marco Cornero , Paolo Petroni , Francky Catthoor , Hugo De Man, Integration of medium-throughput signal processing algorithms on flexible instruction-set architectures, Journal of VLSI Signal Processing Systems, v.9 n.1-2, p.49-65, Jan. 1995 [doi>10.1007/BF02406470]
• 16: John L. Hennessy , Thomas Gross, Postpass Code Optimization of Pipeline Constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.422-448, July 1983 [doi>10.1145/2166.357217]
• 17: Chu-Yi Huang , Yen-Shen Chen , Youn-Long Lin , Yu-Chin Hsu, Data path allocation based on bipartite weighted matching, Proceedings of the 27th ACM/IEEE conference on Design automation, p.499-504, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123350]
• 18: W. W. Hwu , P. P. Chang, Exploiting parallel microprocessor microarchitectures with a compiler code generator, Proceedings of the 15th Annual International Symposium on Computer architecture, p.45-53, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 19: KIM, B. M. AND BARNWELL, T. P. 1990. Resource allocation and code generation for pointer based pipelined dsp multiprocessors. In Proceedings of the International Conference on Proceedings of the International Conference on Circuits and Systems (May 1990). 2685-2688.
• 20: David J. Kolson , Alexandru Nicolau , Nikil Dutt , Ken Kennedy, Optimal register assignment to loops for embedded code generation, Proceedings of the 8th international symposium on System synthesis, p.42-47, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224494]
• 21: F. J. Kurdahi , A. C. Parker, REAL: a program for REgister ALlocation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.210-215, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37920]
• 22: HENDREN, L.J. 1992. Register Allocation using Cyclic Interval Graphs: A New Approach to an Old Problem.
• 23: Tsing-Fa Lee , Allen C.-H. Wu , Daniel D. Gajski , Youn-Long Lin, An effective methodology for functional pipelining, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.230-233, November 1992, Santa Clara, California, United States
• 24: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang , Albert Wang, Code optimization techniques for embedded DSP microprocessors, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.599-604, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217596]
• 25: Clifford Liem , Trevor May , Pierre Paulin, Register assignment through resource classification for ASIP microcode generation, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.397-402, November 06-10, 1994, San Jose, California, United States
• 26: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 27: Pierre G. Paulin , Clifford Liem , Trevor C. May , Shailesh Sutarwala, DSP design tool requirements for embedded systems: a telecommunications industrial perspective, Journal of VLSI Signal Processing Systems, v.9 n.1-2, p.23-47, Jan. 1995 [doi>10.1007/BF02406469]
• 28: José Luis Pino , Soonhoi Ha , Edward A. Lee , Joseph T. Buck, Software synthesis for DSP using Ptolemy, Journal of VLSI Signal Processing Systems, v.9 n.1-2, p.7-21, Jan. 1995 [doi>10.1007/BF02406468]
• 29: Shlomit S. Pinter, Register allocation with instruction scheduling, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.248-257, June 21-25, 1993, Albuquerque, New Mexico, United States
• 30: Ioannis Pitas, Digital image processing algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 31: RIMEY, K. AND HILFINGER, P. 1988. A compiler for application-specific signal processors. In VLSI Signal Processing III. 341-351.
• 32: Tom Wilson , Gary Grewal , Ben Halley , Dilip Banerji, An integrated approach to retargetable code generation, Proceedings of the 7th international symposium on High-level synthesis, p.70-75, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Keywords:
DSP, code generation