Time-constrained code compaction for DSPs

ABSTRACT

Abstract: DSP algorithms are, in most cases, subject to hard real-time constraints. In the case of programmable DSPs, meeting those constraints must be ensured by appropriate code generation techniques. For processors offering instruction-level parallelism, the task of code generation includes code compaction. The exact timing behavior of a DSP program is only known after compaction. Therefore, real-time constraints should be taken into account during the compaction phase. While most known DSP code generators rely on rigid heuristics for that phase, this paper proposes a novel approach to local code compaction based on an integer programming model, which obeys exact timing constraints. Due to a general problem formulation, the model also obeys encoding restrictions and possible side-effects.

REFERENCES

• 1: DSP56156 User's Manual, Motorola Inc. 1992
• 2: C. Liem, T. May, P. Paulin: Instruction-set matching and selection for DSP and ASIP code generation, European Design & Test Conference (ED & TC), 1994
• 3: A. Fauth, A. Knoll: Translating signal flowcharts into microcode for custom digital signal processors, Proc. ICSP, 1993
• 4: B. Wess: Optimizing signal flow graph compilers for digital signal processors, Proc. ICSPAT 1994
• 5: Johan Van Praet , Gert Goossens , Dirk Lanneer , Hugo De Man, Instruction set definition and instruction selection for ASIPs, Proceedings of the 7th international symposium on High-level synthesis, p.11-16, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 6: R. Leupers, R. Niemann, P. Marwedel: Methods for retargetable DSP code generation, IEEE Workshop on VLSI Signal Processing, 1994
• 7: Peter Marwedel , Gert Goossens, Code Generation for Embedded Processors, Kluwer Academic Publishers, Norwell, MA, 1995
• 8: Rajesh K. Gupta , Giovanni De Micheli, Constrained software generation for hardware-software systems, Proceedings of the 3rd international workshop on Hardware/software co-design, September 22-24, 1994, Grenoble, France
• 9: Pai Chou , Gaetano Borriello, Software scheduling in the co-synthesis of reactive real-time systems, Proceedings of the 31st annual conference on Design automation, p.1-4, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196247]
• 10: Adwin H. Timmer , Marino T.J. Strik , Jef L. van Meerbergen , Jochen A.G. Jess, Conflict modelling and instruction scheduling in code generation for in-house DSP cores, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.593-598, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217595]
• 11: 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
• 12: C. H. Gebotys, M. I. Elmasry: Global optimization approach for architectural synthesis, IEEE Trans. on CAD, Vol. 12, No. 9, 1993
• 13: Birger Landwehr , Peter Marwedel , Rainer Dömer, OSCAR: optimum simultaneous scheduling, allocation and resource binding based on integer programming, Proceedings of the conference on European design automation, p.90-95, September 19-23, 1994, Grenoble, France
• 14: Davidson, D. Landskov, B. D. Shriver, P. W. Mallet: Some experiments in local microcode compaction for horizontal machines, IEEE Trans. on Computers, vol. 30, No. 7, 1981
• 15: Lothar Nowak, Graph based retargetable microcode compilation in the MIMOLA design system, Proceedings of the 20th annual workshop on Microprogramming, p.126-132, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255329]
• 16: TMS320C2x User's Guide, Rev. B, Texas Instruments, 1990
• 17: R. Leupers , P. Marwedel, A BDD-based frontend for retargetable compilers, Proceedings of the 1995 European conference on Design and Test, p.239, March 06-09, 1995

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Systems specification methodology

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

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

General Terms:
Algorithms, Design, Experimentation, Languages

Keywords:
automatic programming, code generation techniques, digital signal processing algorithms, digital signal processing chips, encoding restrictions, exact timing behavior, hard real-time constraints, instruction-level parallelism, integer programming, integer programming model, local code compaction, programmable DSP, real-time systems, rigid heuristics, side-effects, source coding, time-constrained code compaction, timing