High-level synthesis under multi-cycle interconnect delay

ABSTRACT

As process technology goes into deep submicron range, interconnect delay becomes dominant among overall system delay, occupying most of the system clock cycle time. Interconnect delay is now a crucial factor that needs to be considered even during high-level synthesis. In this paper, we propose a concurrent scheduling and binding algorithm that takes interconnect delay into account. We first define our distributed target architecture, which minimizes the effect of interconnect delay on clock cycle time. We no longer assume that interconnect delay between functional units is a part of one clock cycle. Interconnect delay can span over multiple clock cycles. We incorporate the concept of multi-cycle interconnect delay into scheduling and binding process, to reduce the critical path length and therefore the system latency. We show that by introducing interconnect delay, we can obtain latency improvement of up to 54 % and of 37% on the average.

REFERENCES

• 1: Jan M. Rabaey, Digital integrated circuits: a design perspective, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 2: E. G. Friedman, "Substrate Coupling and Interconnect Noise in Mixed-Signal and High Speed Digital ICs," IEEE CAS Workshop on Mixed-Signal Integrated Circuit Design, Dec., 1999.
• 3: Dennis Sylvester , Kurt Keutzer, Getting to the bottom of deep submicron, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.203-211, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288614]
• 4: Yehea I. Ismail , Eby G. Friedman , Jos&eaucte; L. Neves, Figures of merit to characterize the importance of on-chip inductance, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.4, p.442-449, Dec. 1999 [doi>10.1109/92.805751]
• 5: International Technology Roadmap for Semiconductors, Semiconductor Industry Association, 1999.
• 6: 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
• 7: S. Park and K. Choi, "Latency minimisation by system clock optimisation," IEE Electronics Letters, vol. 34, pp. 862-864, 1998.
• 8: Sanghun Park , Kiyoung Choi, Performance-driven scheduling with bit-level chaining, Proceedings of the 36th ACM/IEEE conference on Design automation, p.286-291, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309932]
• 9: S. Park, K. Kim, H. Chang, J. Jeon, and K. Choi, "Backward- Annotation of Post Layout Delay Information into High-Level Synthesis Process for Performance Optimization," Proc. of 6th International Conference on VLSI and CAD, pp. 25-28, Oct. 1999.
• 10: 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]
• 11: R. Camposano, "Path-Based Scheduling for Synthesis," IEEE Transactions on Computer Aided Design, pp. 154-157, 1996.
• 12: 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]
• 13: J. M. Rabaey , C. Chu , P. Hoang , M. Potkonjak, Fast Prototyping of Datapath-Intensive Architectures, IEEE Design & Test, v.8 n.2, p.40-51, April 1991 [doi>10.1109/54.82037]
• 14: M. McFarland, "A Fast Floor Planning Algorithm for Architectureal Evaluation," Proceedings of the International Conference on Computer Design, pp. 96-99, Oct. 1989.
• 15: R. Camposano, "Path-Based Scheduling for Synthesis," IEEE Transactions on CAD, vol. 10, no. 1, pp. 85-93, Jan. 1991.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

  C. Computer Systems Organization

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Design, Measurement, Performance, Theory