Loop fusion for memory space optimization

ABSTRACT

Portable or embedded systems as well as submicronic technologies have made the power consumption criterium crucial. Memory is known to be extremely power consuming. Moreover multimedia applications are memory intensive applications. Therefore, we propose new techniques to optimize a behavioral description of multimedia applications before the hardware/software partitioning (Codesign). These transformations are performed on "for" loops that constitute the main parts which handle the arrays of the multimedia code. This paper presents an optimal algorithm to reduce the use of temporary arrays by loop fusion. Although the algorithm is not polynomial, experiments have shown that it is very efficient.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994 [doi>10.1145/197405.197406]
• 3: Henry Chang , Larry Cooke , Merrill Hunt , Grant Martin , Andrew J. McNelly , Lee Todd, Surviving the SOC revolution: a guide to platform-based design, Kluwer Academic Publishers, Norwell, MA, 1999
• 4: Eddy De Greef,Storage Size Reduction for Multimedia Application ,Ph.D.thesis,Katholieke Universiteit Leuven -IMEC,Jan.1998.
• 5: Miguel Miranda , Francky Catthoor , Martin Janssen , Hugo de Man, ADOPT: Efficient Hardware Address Generation in Distributed Memory Architectures, Proceedings of the 9th international symposium on System synthesis, p.20, November 06-08, 1996
• 6: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Architectural exploration and optimization of local memory in embedded systems, Proceedings of the 10th international symposium on System synthesis, p.90-97, September 17-19, 1997, Antwerp, Belgium
• 7: Preeti Ranjan Panda,Nikil Dutt,and Alexandru Nicolau,Memory Issues in Embedded Systems-On-Chip ,Klu er Academic Publishers,1999, ISBN 0 -7923 -8362 -1.
• 8: Bo en Alpern,Larry Carter,Ephraim Feig,and Ted Selker,"The uniform memory hierarchy model of computation,"Algorithmica ,vol.12,pp.72 -109,1994.
• 9: Chidamber Kulkarni,Cache Optimization for Multimedia Applications ,Ph.D.thesis,Katholieke Universiteit Leuven -IMEC,Feb.2001.
• 10: Kathryn S. McKinley , Steve Carr , Chau-Wen Tseng, Improving data locality with loop transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.424-453, July 1996 [doi>10.1145/233561.233564]
• 11: Steven Mark Carr, Memory-hierarchy management, Rice University, Houston, TX, 1993
• 12: Ken Kennedy , Kathryn S. McKinley, Maximizing Loop Parallelism and Improving Data Locality via Loop Fusion and Distribution, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.301-320, August 12-14, 1993
• 13: Guang R. Gao , R. Olsen , Vivek Sarkar , Radhika Thekkath, Collective Loop Fusion for Array Contraction, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.281-295, August 03-05, 1992
• 14: Alain Darte, On the complexity of loop fusion, Parallel Computing, v.26 n.9, p.1175-1193, Aug. 2000 [doi>10.1016/S0167-8191(00)00034-X]
• 15: Michel Gondran , Michel Minoux , Steven Vajda, Graphs and algorithms, John Wiley & Sons, Inc., New York, NY, 1984
• 16: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 17: Michel Berkelaar,"Lp solve Mixed Integer Linear Programming solver 3.2,"Available at ftp://ftp.es.ele.tue.nl/pub/lp_solve/.
• 18: Antoine Fraboulet , Guillaume Huard , Anne Mignotte, Loop Alignment for Memory Accesses Optimization, Proceedings of the 12th international symposium on System synthesis, p.71, November 01-04, 1999

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Memory technologies

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware; Microprocessors and microcomputers
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Experimentation, Performance