Compatibility path based binding algorithm for interconnect reduction in high level synthesis

ABSTRACT

This paper describes a register and functional unit (FU) binding algorithm in high level synthesis. Our algorithm targets the reduction of multiplexer inputs. Since multiplexers connect multiple inputs to FUs or registers, the multiplexer count is a good indicator of the interconnect complexity. Reducing the number of multiplexer inputs results in reducing interconnect cost. Specifically, our algorithm constructs a weighted and ordered compatibility graph, and binds operations that form a long path in the graph together. As a result, operations with many flow dependencies and common inputs are bound to same FU, leading to a small number of FU inputs. In addition, the operation variables generated by a single FU are assigned to the same register so that connections between FUs and registers are reduced. We have implemented our algorithm within a MATLAB to Verilog conversion tool, and applied it to a suite of benchmark programs. Our experimental results have shown that the proposed scheme achieves 11.8%, 43.6% and 58.8% multiplexer input count reduction on average over weighted bipartite matching algorithm, k-cofamily algorithm and left edge algorithm, respectively. To assess the impact on interconnect reduction, we have generated layouts of the circuits from our Verilog description. It is shown that our approach delivers a 10.1% reduction in total wire-length of global interconnects with minor area overhead of register and FUs in comparison to the best previously proposed scheme.

REFERENCES

• 1: I. Ahmad and C. Y. R. Chen. Post-processor for data path synthesis using multiport memories. In Proceedings of ICCAD, November 1991.
• 2: Hassan Al Atat , Iyad Ouaiss, Register Binding for FPGAs with Embedded Memory, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.167-175, April 20-23, 2004
• 3: Annie Avakian , Iyad Ouaiss, Optimizing Register Binding in FPGAs Using Simulated Annealing, Proceedings of the 2005 International Conference on Reconfigurable Computing and FPGAs (ReConFig'05) on Reconfigurable Computing and FPGAs, p.16, September 28-30, 2005 [doi>10.1109/RECONFIG.2005.27]
• 4: 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
• 5: 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]
• 6: J. Cong, Y. Fan, G. Han, X. Yang, and Z. Zhang. Architecture and synthesis for on-chip multicycle communication. IEEE Transactions on CAD of integrated circuits and systems, 2004.
• 7: Jason Cong , Yiping Fan , Wei Jiang, Platform-based resource binding using a distributed register-file microarchitecture, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233648]
• 8: Jason Cong , Yiping Fan , Xun Yang , Zhiru Zhang, Architecture and synthesis for multi-cycle communication, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640040]
• 9: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 10: Daniel D. Gajski , Nikil D. Dutt , Allen C.-H. Wu , Steve Y.-L. Lin, High-level synthesis: introduction to chip and system design, Kluwer Academic Publishers, Norwell, MA, 1992
• 11: 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]
• 12: Adam Kaplan , Philip Brisk , Ryan Kastner, Data communication estimation and reduction for reconfigurable systems, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775987]
• 13: Ryan Kastner , Wenrui Gong , Xin Hao , Forrest Brewer , Adam Kaplan , Philip Brisk , Majid Sarrafzadeh, Layout driven data communication optimization for high level synthesis, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 14: Daehong Kim , Jinyong Jung , Sunghyun Lee , Jinhwan Jeon , Kiyoung Choi, Behavior-to-placed RTL synthesis with performance-driven placement, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 15: Taewhan Kim , C. L. Liu, Utilization of multiport memories in data path synthesis, Proceedings of the 30th international conference on Design automation, p.298-302, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164900]
• 16: T. Kim and C. L. Liu. An integrated data path synthesis algorithm based on network flow method. In Proceedings of CICC, May 1995.
• 17: F. J. Kurdahi , A. C. Parker, REAL: a program for REgister ALlocation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.210-215, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37920]
• 18: X. Liu and M. C. Papaefthymiou. Design of a 20-mb/s 256-state viterbi decoder. IEEE Transactions on VLSI Systems, 2003.
• 19: Renu Mehra , Lisa M. Guerra , Jan M. Rabaey, Low-power architectural synthesis and the impact of exploiting locality, Journal of VLSI Signal Processing Systems, v.13 n.2-3, p.239-258, Aug./Sept. 1996 [doi>10.1007/BF01130408]
• 20: R. Mehra, L. M. Guerra, and J. M. Rabaey. A partitioning scheme for optimizing interconnect power. IEEE Journal of Solid-State Circuits, 1997.
• 21: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 22: C. A. Papachristou , H. Konuk, A linear program driven scheduling and allocation method followed by an interconnect optimization algorithm, Proceedings of the 27th ACM/IEEE conference on Design automation, p.77-83, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123231]
• 23: 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
• 24: 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]
• 25: L. Stok, Interconnect optimisation during data path allocation, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
• 26: Junhyung Um , Jae-hoon Kim , Taewhan Kim, Layout-driven resource sharing in high-level synthesis, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.614-618, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774663]
• 27: Jen-Pin Weng , Alice C. Parker, 3D scheduling: high-level synthesis with floorplanning, Proceedings of the 28th conference on ACM/IEEE design automation, p.668-673, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127748]