Simultaneous reference allocation in code generation for dual data memory bank ASIPs

ABSTRACT

We address the problem of code generation for DSP systems on a chip. In such systems, the amount of silicon devoted of program ROM is limited, so application software must be sufficiently dense. Additionally, the software must be written so as to meet various high-performance constraints, which may include hard real-time constraints. Unfortunately, current compiler technology is unable to generate high-quality code for DSPs, whose architectures are highly irregular. Thus, designers often resort to programming application software in assembly—a time-consuming task. In this paper, we focus on providing support for architectural feature of DSPs that makes code generation difficult, namely multiple data memory banks. This feature increases memory bandwith by permitting multiple data memory accesses to occur in parallel when the referenced variables belong to different data memory banks and the registers involved conform to a strict set of conditions. We present an algorithm that attempst to maximize the benefit of this architectural feature. While previous approaches have decoupled the phases of register allocation and memory bank assignment, thereby compromising code quality, our algorithm performs these two phases simultaneously. Experimental results demonstrate that our algorithm not only generates high-quality compiled code, but also improves the quality of completely-referenced code.

REFERENCES

• 1: Alfred V. Aho , Mahadevan Ganapathi , Steven W. K. Tjiang, Code generation using tree matching and dynamic programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.491-516, Oct. 1989 [doi>10.1145/69558.75700]
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: Jennifer M. Anderson , Monica S. Lam, Global optimizations for parallelism and locality on scalable parallel machines, ACM SIGPLAN Notices, v.28 n.6, p.112-125, June 1993
• 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: Guido Araujo , Ashok Sudarsanam , Sharad Malik, Instruction Set Design and Optimizations for Address Computation in DSP Architectures, Proceedings of the 9th international symposium on System synthesis, p.105, November 06-08, 1996
• 7: CHAITIN, G., AUSLANDER, M., CHANDRA, A., COCKE, J., HOPKINS, M., AND MARKSTEIN, P. 1981. Register allocation via coloring. Comput. Lang. 6, 1, 47-57.
• 8: Christopher W. Fraser , David R. Hanson , Todd A. Proebsting, Engineering a simple, efficient code-generator generator, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.213-226, Sept. 1992 [doi>10.1145/151640.151642]
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: KnFKA, S. 1990. An assembly source level global compacter for digital signal processors. In Proceedings of the International on Acoustics, Speech, and Signal Processing,
• 11: KIRKPATRICK, S., GELATT, C. D., JR., AND VECCHI, M. P. 1983. Optimization by simulated annealing. Science 220, 4598 (May), 671-680.
• 12: David Landskov , Scott Davidson , Bruce Shriver , Patrick W. Mallett, Local Microcode Compaction Techniques, ACM Computing Surveys (CSUR), v.12 n.3, p.261-294, Sept. 1980 [doi>10.1145/356819.356822]
• 13: LANNEER, D., PRAET, J., SCHOOFS, K., GEURTS, W., THOEN, F., GOOSSENS, G., AND KIFLI, A. 1995. Chess: Retargetable code generation for embedded DSP rocessors. In Code Generation for Embedded Processors, P. Marwedel and J. Goosens, Eds. Kluwer Academic Publishers, Hingham, MA.
• 14: R. Leupers , P. Marwedel, Instruction selection for embedded DSPs with complex instructions, Proceedings of the conference on European design automation, p.200-205, September 1996, Geneva, Switzerland
• 15: Rainer Leupers , Wolfgang Schenk , Peter Marwedel, Retargetable assembly code generation by bootstrapping, Proceedings of the 7th international symposium on High-level synthesis, p.88-93, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 16: J. Li , M. Chen, Compiling Communication-Efficient Programs for Massively Parallel Machines, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.361-376, July 1991 [doi>10.1109/71.86111]
• 17: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang, Instruction selection using binate covering for code size optimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.393-399, November 05-09, 1995, San Jose, California, United States
• 18: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang , Albert Wang, Storage assignment to decrease code size, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.186-195, June 18-21, 1995, La Jolla, California, United States
• 19: LIAO, S., DEVADAS, S., KEUTZER, K., TJIANG, S., WANG, A., ARAUJO, G., SUDARSANAM, A., MALIK, S., ZIVOJNOVIC, V., AND MEYR, H. 1996. Code generation and optimization techniques for embedded digital signal processors. In Hardware/Software Co-Design, G. D. Micheli and M. Sami, Eds. Kluwer Academic Publishers, Hingham, MA, 165-186.
• 20: MOTOROLA 1990. DSP56000/DSP56001 Digital Signal Processor User's Manual. Motorola Inc., Phoenix, AZ.
• 21: Pierre G. Paulin , Clifford Liem , Trevor C. May , Shailesh Sutarwala, CodeSyn: a retargetable code synthesis system (abstract), Proceedings of the 7th international symposium on High-level synthesis, p.94, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 22: POWELL, D., LEE, E., AND NEWMAN, W. 1992. Direct synthesis of optimized DSP assembly code from signal flow block diagrams. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing 5, 553-556.
• 23: Mazen A. R. Saghir , Paul Chow , Corinna G. Lee, Exploiting dual data-memory banks in digital signal processors, ACM SIGOPS Operating Systems Review, v.30 n.5, p.234-243, Dec. 1996
• 24: Ashok Sudarsanam , Sharad Malik, Memory bank and register allocation in software synthesis for ASIPs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.388-392, November 05-09, 1995, San Jose, California, United States
• 25: TEXAS-INSTRUMENTS 1993. TMS320C2x User's Guide. Revision C. Texas Instruments, Austin, TX.
• 26: TESS, B. 1991. Automatic code generation for integrated digital signal processors. In Proceedings of the 1991 IEEE International Symposium on Circuits and Systems (Singapore, June 11-14), 33-36.
• 27: TESS, B. 1992. Automatic instruction code generation based on trellis diagrams. In Proceedings of the International Conference on Circuits and Systems, 645-648.
• 28: ZIVOJNOVIC, V., VELARDE, J. M., AND SCHL GER, C. 1994. DSPstone: A DSP-oriented benchmarking methodology. In Proceedings of the Fifth International Conference on Signal Processing Applications and Technology (Oct.).

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers; Code generation

General Terms:
Design, Languages

Keywords:
code generation, code optimization, graph labelling, memory bank assignment, register allocation