Simultaneous FU and register binding based on network flow method

ABSTRACT

With the rapid increase of design complexity and the decrease of device features in nano-scale technologies, interconnection optimization in digital systems becomes more and more important. In this paper we develop a simultaneous FU and register (SFR) binding algorithm for multiplexer optimization based on min-cost network flow. Unlike most of the prior approaches in which functional unit binding and register binding are performed sequentially, our approach performs these two highly correlated tasks gradually and concurrently. We also present an ILP formulation of the combined functional unit and register binding problem for the optimality study of heuristics. Experimental results show that when compared to traditional binding algorithms, our simultaneous resource binding algorithm is close to optimal solutions for small-size designs (only 5% more MUX) and achieves significant reduction for MUX area (12%) and timing (10%) for a set of real-life benchmark designs.

References

1. Xilinx Web Site, http://www.xilinx.com.
2. J. M. Chang and M. Pedram, "Register Allocation and Binding for Low Power," Design Automation Conference, 1995.
3. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs, 1993.
4. D. Chen, J. Cong, and Y. Fan, "Low-Power High-Level Synthesis for FPGA Architectures," International Symposium on Low Power Electronics and Design, Seoul, Korea, pp. 134--139, Aug. 2003.
5. D. Chen, and J. Cong, "Register Binding and Port Assignment for Multiplexer Optimization," ASPDAC, pp. 68--73, January 2004.
6. D. Chen, J. Cong, and J. Xu, "Optimal Module and Voltage Assignment for Low-Power," ASPDAC, pp. 850~855, 2005.
7. J. Cong, Y. Fan, G. Han, W. Jiang, and Z. Zhang, "Platform-Based Behavior-Level and System-Level Synthesis," Proceedings of IEEE International SOC Conference, pp. 199--202, Sept. 2006.
8. C. Y. Huang, et al. "Data Path Allocation Based on Bipartite Weighted Matching," Design Automation Conference, 1990.
9. T. Kim and C. L. Liu, "An Integrated Data Path Synthesis Algorithm Based on Network Flow Method," Proc. of the IEEE Custom Integrated Circuits Conference, 1995.
10. F. Li, D. Chen, L. He and J. Cong, "Architecture Evaluation for Power-efficient FPGAs," ACM International Symposium on FPGA, Feb. 2003.
11. C. G. Lyuh and K. Taewhan, "High-level Synthesis for Low-Power Based on Network Flow Method," IEEE Trans. on VLSI Systems. 2003. 11(3): 364~375.
12. Barry Pangrle, "On the Complexity of Connectivity Binding," IEEE Tran. on Computer-Aided Design, Vol. 10, No. 11, Nov. 1991.
13. B. M. Pangrle, "Splicer: A Heuristic Approach to Connectivity Binding," Design Automation Conference, pp. 536--541, Jun. 1988.
14. P. G. Paulin, J. P. Knight, and E. F. Girczyc, "HAL: A Multi-Paradigm Approach to Automatic Data Path Synthesis," Design Automation Conference, pp. 263--270, Jul. 1986.
15. M. Rim, R. Jain, and R. D. Leone, "Optimal Allocation and Binding in High-Level Synthesis," Design Automation Conference, 1992.
16. A. Singh and M. Marek-Sadowska, "Efficient Circuit Clustering for Area and Power Reduction in FPGAs," ACM International Symposium on FPGA, Feb. 2002.
17. M. B. Srivastava and M. Potkonjak, "Optimum and Heuristic Transformation Techniques for Simultaneous Optimization of Latency and Throughput," Trans. on VLSI Systems, 1995.
18. J. Stephenson and P. Metzgen, "Logic Optimization Techniques for Multiplexers," Altera Literature, 2004.
19. C-J. Tseng and D. P. Siewiorek, "Automated Synthesis of Data Path in Digital Systems," IEEE Tran. on CAD of ICAS, Vol. CADJ, No. 3, pp 379--395, Jul. 1986.
20. H. W. Zhu and C. C. Jong, "Interconnection Optimization in Data Path Allocation Using Minimal Cost Maximal Flow Algorithm," Microelectronics, Vol. 33, No. 9, pp 749--59, Sept. 2002.

Index Terms

• Hardware

  • Electronic design automation

    • High-level and register-transfer level synthesis

      • Datapath optimization

    • Logic synthesis

      • Circuit optimization

  • Hardware validation

• Mathematics of computing

  • Mathematical analysis

    • Mathematical optimization

      • Continuous optimization

        • Linear programming

      • Mixed discrete-continuous optimization

        • Integer programming

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization

      • Continuous optimization

        • Linear programming

      • Mixed discrete-continuous optimization

        • Integer programming