Architecture and synthesis for multi-cycle communication

ABSTRACT

For multi-gigahertz designs in nanometer technologies, data transfers on global interconnects take multiple clock cycles. In this paper, we propose a regular distributed register (RDR) micro-architecture for multi-cycle on-chip communication. An RDR architecture structurally consists of a two-dimensional array of islands, each of which contains a cluster of computational logic and local register files. We also propose a new synthesis methodology based on the RDR architecture. Novel layout-driven architectural synthesis algorithms have been developed for RDR. Application of these algorithms to several real-life benchmarks demonstrates 44% improvement on average in terms of the clock period and 37% improvement on average in terms of the final latency.

REFERENCES

• 1: Jason Cong, Timing closure based on physical hierarchy, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505429]
• 2: Semiconductor Industry Association, The National Technology Roadmap for Semiconductors, 1997.
• 3: Semiconductor Industry Association, International Technology Roadmap for Semiconductors, 2001.
• 4: J. T. Udding, "A Formal Model for Defining and Classifying Delay-Insensitive Circuits," Distributed Computing, vol. 1(4), pp. 197--204, 1986.
• 5: Daniel Marcos Chapiro, Globally-asynchronous locally-synchronous systems (performance, reliability, digital), 1985
• 6: Jason Cong , Sung Kyu Lim, Physical planning with retiming, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 7: Deshanand P. Singh , Stephen D. Brown, Integrated retiming and placement for field programmable gate arrays, 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.503059]
• 8: Jason Cong , Chang Wu, FPGA synthesis with retiming and pipelining for clock period minimization of sequential circuits, Proceedings of the 34th annual conference on Design automation, p.644-649, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266309]
• 9: 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]
• 10: 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
• 11: 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]
• 12: F. Mo and R. K. Brayton, "Regular Fabrics in Deep Sub-Micron Integrated-Circuit Design," 11th IEEE/ACM International Workshop on Logic & Synthesis, pp. 7--12, 2002.
• 13: P. Paulin and J. Knight, "Force-Directed Scheduling for Behavioral Synthesis of ASICs," in IEEE Trans. on CAD, vol. 8(6), pp. 661--679, June 1989.
• 14: W. H. Chen, C. Smith and S. Fralick, "A Fast Computational Algorithm for the Discrete Cosine Transform," in IEEE Trans. on Communications, vol. 25(9), pp. 1004--1009, Sept. 1977.
• 15: Chin-Chih Chang , Jason Cong , Zhigang (David) Pan, Physical hierarchy generation with routing congestion control, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505399]
• 16: Alexander Marquardt , Vaughn Betz , Jonathan Rose, Timing-driven placement for FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.203-213, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329208]
• 17: Yung-Ming Fang , D. F. Wong, Simultaneous functional-unit binding and floorplanning, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.317-321, November 06-10, 1994, San Jose, California, United States
• 18: Min Xu , F. J. Kurdahi, Layout-driven RTL binding techniques for high-level synthesis, Proceedings of the 9th international symposium on System synthesis, p.33, November 06-08, 1996
• 19: Yu-Kwong Kwok , Ishfaq Ahmad, Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.506-521, May 1996 [doi>10.1109/71.503776]
• 20: Altera Web Site, http://www.altera.com.
• 21: 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]

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
RDR, binding, deep sub-micron, interconnect, multi-cycle communication, placement, scheduling, timing closure