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: 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]
• 3: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 4: Deming Chen , Jason Cong , Yiping Fan, Low-power high-level synthesis for FPGA architectures, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871541]
• 5: Deming Chen , Jason Cong, Register binding and port assignment for multiplexer optimization, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
• 6: Deming Chen , Jason Cong , Junjuan Xu, Optimal module and voltage assignment for low-power, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1121054]
• 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: Chu-Yi Huang , Yen-Shen Chen , Youn-Long Lin , Yu-Chin Hsu, Data path allocation based on bipartite weighted matching, Proceedings of the 27th ACM/IEEE conference on Design automation, p.499-504, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123350]
• 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: Fei Li , Deming Chen , Lei He , Jason Cong, Architecture evaluation for power-efficient FPGAs, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611844]
• 11: Chun-Gi Lyuh , Taewhan Kim, High-level synthesis for low power based on network flow method, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.3, p.364-375, June 2003 [doi>10.1109/TVLSI.2003.810796]
• 12: Barry Pangrle, "On the Complexity of Connectivity Binding," IEEE Tran. on Computer-Aided Design, Vol. 10, No. 11, Nov. 1991.
• 13: Barry M. Pangre, Splicer: a heuristic approach to connectivity binding, Proceedings of the 25th ACM/IEEE conference on Design automation, p.536-541, June 12-15, 1988, Atlantic City, New Jersey, United States
• 14: P. G. Paulin , J. P. Knight , E. F. Girczyc, HAL: a multi-paradigm approach to automatic data path synthesis, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.263-270, July 1986, Las Vegas, Nevada, United States
• 15: M. Rim , R. Jain , R. De Leone, Optimal allocation and binding in high-level synthesis, Proceedings of the 29th ACM/IEEE conference on Design automation, p.120-123, June 08-12, 1992, Anaheim, California, United States
• 16: Amit Singh , Malgorzata Marek-Sadowska, Efficient circuit clustering for area and power reduction in FPGAs, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503058]
• 17: Mani B. Srivastava , Miodrag Potkonjak, Optimum and heuristic transformation techniques for simultaneous optimization of latency and throughput, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.1, p.2-19, March 1995 [doi>10.1109/92.365450]
• 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

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Optimization
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

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

General Terms:
Algorithms, Design, Performance, Theory