Interconnect and communication synthesis for distributed register-file microarchitecture

ABSTRACT

Distributed register-file microarchitecture (DRFM) which comprises multiple uniform blocks (called islands), each containing a dedicated register file, functional unit(s) and data-routing logic, has been known as a very attractive architecture for implementing designs with platform-featured on-chip memory or register-file IP blocks. In comparison with the discrete-register based architecture, DRFM offers a higher degree of opportunity of reducing the cost of global (inter-island) connections by confining as many the computations to the inside of the islands as possible. Consequently, for DRFM architecture, two important problems to be solved effectively in high-level synthesis are: (problem 1) scheduling and resource binding for minimizing inter-island connections, and (problem 2) data transfer (i.e., communication) scheduling through the inter-island connections for minimizing the access conflicts among the data transfers. This work proposes novel solutions to the two problems. Specifically, for problem 1 previous work solves it in two separate steps: (i) scheduling and (ii) then determining the inter-island connections by resource binding to islands. However, in our algorithm called DFRM-int, we place primary importance on the cost of interconnections. Consequently, we minimize the cost of interconnections first to fully exploit the effects of scheduling on interconnect and then to schedule the operations later. For problem 2, previous work tries to solve the access conflicts by forwarding data directly to the destination island. However, in our algorithm called DFRM-com, we devise an efficient technique of exploring an extensive design space of data forwarding indirectly as well as directly to find a near-optimal solution. By applying our proposed synthesis approach DFRM-int+DFRM-com we are able to reduce the inter-island connections by 18.1% more, compared to that by the DRFM approach in [4], even completely eliminating register-file access conflicts, which could never been resolved by [4], without any latency increase.

REFERENCES

• 1: Altera website. http://www.altera.com.
• 2: Xilinx website. http://www.xilinx.com.
• 3: Jason Cong , Yiping Fan , Guoling Han , Xun Yang , Zhiru Zhang, Architecture and synthesis for multi-cycle on-chip communication, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA [doi>10.1145/944645.944667]
• 4: 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]
• 5: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Papers on Twenty-five years of electronic design automation, p.241-247, June 1988 [doi>10.1145/62882.62910]
• 6: Hyuk-Jae Jang , Barry M. Pangrle, A grid-based approach for connectivity binding with geometric costs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.94-99, November 07-11, 1993, Santa Clara, California, United States
• 7: Jinhwan Jeon , Daehong Kim , Dongwan Shin , Kiyoung Choi, High-level synthesis under multi-cycle interconnect delay, Proceedings of the 2001 conference on Asia South Pacific design automation, p.662, January 2001, Yokohama, Japan [doi>10.1145/370155.370576]
• 8: 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
• 9: Taewhan Kim , C. L. Liu, A new approach to the multiport memory allocation problem in data path synthesis, Integration, the VLSI Journal, v.19 n.3, p.133-160, Nov. 1995 [doi>10.1016/0167-9260(95)00009-5]
• 10: Eric Kusse , Jan Rabaey, Low-energy embedded FPGA structures, Proceedings of the 1998 international symposium on Low power electronics and design, p.155-160, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280873]
• 11: Hae-Dong Lee , Sun-Young Hwang, A scheduling algorithm for multiport memory minimization in datapath synthesis, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.16-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224847]
• 12: Chun-Gi Lyuh , Taewhan Kim , Ki-Wook Kim, Coupling-aware high-level interconnect synthesis for low power, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.609-613, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774662]
• 13: Nir Magen , Avinoam Kolodny , Uri Weiser , Nachum Shamir, Interconnect-power dissipation in a microprocessor, Proceedings of the 2004 international workshop on System level interconnect prediction, February 14-15, 2004, Paris, France [doi>10.1145/966747.966750]
• 14: P. G. Paulin and J. P. Knight. Force-directed scheduling for the behavioral synthesis of asics. IEEE Trans, on CAD of Integrated Circuits and Systems, 8(6):661--679, 1989.
• 15: 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]
• 16: Shantanu Tarafdar , Miriam Leeser , Zixin Yin, Integrating floorplanning in data-transfer based high-level synthesis, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.412-417, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289063]
• 17: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 18: Junhyung Um , Taewhan Kim, Resource Sharing Combined with Layout Effects in High-Level Synthesis, Journal of VLSI Signal Processing Systems, v.44 n.3, p.231-243, September 2006 [doi>10.1007/s11265-006-8537-7]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Automatic synthesis

General Terms:
Algorithms, Design

Keywords:
communication, distributed register file, synthesis