A generalized network flow based algorithm for power-aware FPGA memory mapping

ABSTRACT

In this paper, we present a generalized network flow based algorithm for power-aware FPGA memory mapping. Our algorithm not only maps user-defined logical memories to physical embedded memory blocks under the memory resource constraint but also achieves minimum power consumption. The experimental results show that our algorithm was always able to efficiently generate optimal solutions for all test cases while an existing greedy method could do so only for about one third of the test cases.

REFERENCES

• 1: David Karchmer , Jonathan Rose, Definition and solution of the memory packing problem for field-programmable systems, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.20-26, November 06-10, 1994, San Jose, California, United States
• 2: William K. C. Ho , Steven J. E. Wilton, Logical-to-Physical Memory Mapping for FPGAs with Dual-Port Embedded Arrays, Proceedings of the 9th International Workshop on Field-Programmable Logic and Applications, p.111-123, August 30-September 01, 1999
• 3: Russell Tessier , Vaughn Betz , David Neto , Thiagaraja Gopalsamy, Power-aware RAM mapping for FPGA embedded memory blocks, Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA [doi>10.1145/1117201.1117229]
• 4: Altera Corporation, Stratix II Device Handbook vol. 2, August 2006.
• 5: Xilinx Corporation, Virtex-4 User Guide, April, 2007.
• 6: Altera Corporation, Achieving Low Power in 65-nm Cyclone III FPGAs, March, 2007.
• 7: Mentor Graphics Corporation, FPGA Resource Management, January, 2007.
• 8: Altera Corporation, Quartus II Handbook, May, 2007.
• 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: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 11: P. A. Jensen, Operations Research Models and Methods. Available: http://www.me.utexas.edu/~jensen/ORMM/

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Experimentation

Keywords:
FPGA, dynamic power, memory mapping