A crosstalk-aware timing-driven router for FPGAs

ABSTRACT

As integrated circuits are migrated to more advanced technologies, it has become clear that crosstalk is an important physical phenomenon that must be taken into account. Crosstalk has primarily been a concern for ASICs, multi-chip modules, and custom chips, however, it will soon become a concern in FPGAs. In this paper, we describe the first published crosstalk-aware router that targets FPGAs. We show that, in a representative FPGA architecture implemented in a 0.18mm technology, the average routing delay in the presence of crosstalk can be reduced by 7.1% compared to a router with no knowledge of crosstalk. About half of this improvement is due to a tighter delay estimator, and half is due to an improved routing algorithm.

REFERENCES

• 1: The National Technology Roadmap for Semiconductors, Semiconductor Industry Association, 1994.
• 2: U. Choudhury, A. Sangiovanni-Vincentelli, "Constraint-Based Channel Routing for Analog and Mixed Analog/Digital Circuits," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 12, No. 4, April 1993, pages 497-510.
• 3: A. Vittal, M. Marek-Sadowska, Crosstalk Reduction for VLSI, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 16, No. 3, March 1997, pages 290-298.
• 4: P. Saxena, C.L. Liu, A Postprocessing Algorithm for Crosstalk-Driven Wire Preturbation, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 19, No. 6, June 2000, pages 691-702.
• 5: T. Gao, C.L. Liu, Minimum Crosstalk Channel Routing, IEEE Transactions on Computer-Aided Design, Vol. 15, No. 5, May 1996, pages 465-474.
• 6: T. Miyoshi, S. Wakabayashi, T. Koide, N. Yoshida, An MCM Routing Algorithm Considering Crosstalk, in Proceedings of the International Symposium on Circuits and Systems, May 1995, volume 1, pages 211-214.
• 7: Hai Zhou , D. F. Wong, An optimal algorithm for river routing with crosstalk constraints, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.310-315, November 10-14, 1996, San Jose, California, United States
• 8: D. Wang , E. S. Kuh, A performance-driven MCM router with special consideration of crosstalk reduction, Proceedings of the conference on Design, automation and test in Europe, p.466-470, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 9: K. Jhang, S. Ha, C.S. Jhon, COP: A Crosstalk Optimizer for Gridded Channel Routing, IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, Vol. 15, No. 4, April 1996, pages 424-429.
• 10: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 11: Carl Ebeling , Larry McMurchie , Scott A. Hauck , Steven Burns, Placement and routing tools for the Triptych FPGA, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.4, p.473-482, Dec. 1995 [doi>10.1109/92.475966]
• 12: Tong Xiao , Malgorzata Marek-Sadowska, Efficient Delay Calculation in Presence of Crosstalk, Proceedings of the 1st International Symposium on Quality of Electronic Design, p.491, March 20-22, 2000
• 13: B. Franzini , C. Forzan , D. Pandini , P. Scandolara , A. Dal Fabbro, Crosstalk Aware Static Timing Analysis: A Two Step Approach, Proceedings of the 1st International Symposium on Quality of Electronic Design, p.499, March 20-22, 2000
• 14: Peivand F. Tehrani , Shang Woo Chyou , Uma Ekambaram, Deep Sub-Micron Static Timing Analysis in Presence of Crosstalk, Proceedings of the 1st International Symposium on Quality of Electronic Design, p.505, March 20-22, 2000
• 15: Murat R. Becer , Ibrahim N. Hajj, An Analytical Model for Delay and Crosstalk Estimation with Application to Decoupling, Proceedings of the 1st International Symposium on Quality of Electronic Design, p.51, March 20-22, 2000
• 16: M. Imran Masud , Steven J. E. Wilton, A New Switch Block for Segmented FPGAs, Proceedings of the 9th International Workshop on Field-Programmable Logic and Applications, p.274-281, August 30-September 01, 1999
• 17: J.Rose, S. Brown, Flexibility of Interconnection Structures for Field-Programmable Gate Arrays, IEEE JSSC, Vol. 26, No. 3, March 1991, pages 277-282. .
• 18: J. Cong, Y. Ding, FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs, IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, vol. 13, no. 1, January 1994, pages 1-12.
• 19: 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]

INDEX TERMS

Primary Classification:
  B. Hardware

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Experimentation

Keywords:
crosstalk, field-programmable gate arrays, routing algorithms