Low energy memory and register allocation using network flow

ABSTRACT

This paper presents for the first time low energy simultaneousmemory and register allocation. A minimum cost network flowapproach is used to efficiently solve for minimum energy dissipationsolutions in polynomial time. Results show that estimatedenergy improvements of 1.4 to 2.5 times over previous researchare obtained. This research is important for industry since energydissipation is minimized without requiring an increase in cost.

REFERENCES

• 1: K.Keutzer, "The Impact of CAD on the Design of Low Power Digital Circuits", IEEE Symposium on Low Power Electronics, 1994, p42-45.
• 2: S.Wuytack,F.Catthoor,F.Franssen,L.Nachtergaele, H.DeMan, "Global Communication and Memory Optimizing Transformations For Low Power Systems", International Workshop on Low Power Design, 1994, p 203-208.
• 3: A.Chandrakasan,et.al."Optimizing Power Using Transformations", IEEE Transactions on CAD, Jan 1995,Vol14,No.1, p12- 31.
• 4: Amir H. Farrahi , Gustavo E. Téllez , Majid Sarrafzadeh, Memory segmentation to exploit sleep mode operation, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.36-41, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217503]
• 5: 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
• 6: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 7: Fred C. Chow , John L. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.501-536, Oct. 1990 [doi>10.1145/88616.88621]
• 8: Jui-Ming Chang , Massoud Pedram, Register allocation and binding for low power, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.29-35, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217502]
• 9: Vivek Tiwari , Sharad Malik , Andrew Wolfe, Power analysis of embedded software: a first step towards software power minimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.2 n.4, p.437-445, Dec. 1994 [doi>10.1109/92.335012]
• 10: 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]
• 11: Sven Wuytack , Francky Catthoor , Lode Nachtergaele , Hugo De Man, Power exploration for data dominated video applications, Proceedings of the 1996 international symposium on Low power electronics and design, p.359-364, August 12-14, 1996, Monterey, California, United States
• 12: Wei-Kai Cheng , Youn-Long Lin, A transformation-based approach for storage optimization, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.158-163, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217523]
• 13: P.Landman, J.Rabaey, "Activity-Sensitive Architectural Power Analysis", IEEE Transactions on CAD,Vol.15,No.6, June 1996.
• 14: P.A.Beerel, USC, Panel Presentation on "Where Does the Power GOT" at International Symposium on Low Power Design, April 1995.
• 15: Lee,Tiwari, "A Memory Allocation Technique for Low- Energy Embedded DSP Software", Symposium on Low Power Electronics, Oct, 1995, p24-5.
• 16: Lidsky,Rabaey, "Low-Power Design of Memory Intensive Functions", IEEE Symposium on Low Power Electronics, 1994, p16-7.
• 17: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 18: Herman Schmit , Donald E. Thomas, Array mapping in behavioral synthesis, Proceedings of the 8th international symposium on System synthesis, p.90-95, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224508]
• 19: P. Panda , N. Dutt, Low-power mapping of behavioral arrays to multiple memories, Proceedings of the 1996 international symposium on Low power electronics and design, p.289-292, August 12-14, 1996, Monterey, California, United States
• 20: C.Gebotys, "Low Energy Memory Component Design for Cost-Sensitive High Performance Embedded Systems", IEEE Custom Integrated Circuits Conference, p397-400, 1996.
• 21: Catherine H. Gebotys , Robert J. Gebotys, Performance-Power Optimization of Memory Components for Complex Embedded Systems, Proceedings of the 30th Hawaii International Conference on System Sciences: Advanced Technology Track, p.152, January 03-06, 1997

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  J. Computer Applications

General Terms:
Design, Experimentation, Measurement, Performance, Theory