skip to main content
10.1109/ICCAD.2004.1382608acmconferencesArticle/Chapter ViewAbstractPublication PagesiccadConference Proceedingsconference-collections
Article

True crosstalk aware incremental placement with noise map

Published: 07 November 2004 Publication History

Abstract

Crosstalk noise has become an important issue as technology scales down for timing and signal integrity closure. Existing works to fix crosstalk noise are mostly done at the routing or post routing stage, which may be too late. Since placement determines the overall routing congestion, which correlates with the coupling capacitance, which in turn correlates with the crosstalk noise, placement shall be a good level to do early noise mitigation. The only existing work for the crosstalk aware placement (to our best knowledge) is by Lou and Chen (2004), which uses the coupling capacitance map to guide placement. However, crosstalk is determined not only by the coupling capacitance, but also by many other factors, such as the driver resistance of the victim net and the coupling location (near source vs near sink coupling) (Cong et al., 2001). We introduce a concept of noise map which takes those factors into account. Guided by this accurate noise map explicitly, we propose an incremental placement technique to mitigate noise without disturbing the global placement order. Our incremental placement has two key steps, namely noise aware cell inflation and local refinement. Experimental results on industrial circuits show that our approach is able to reduce the number of top noise nets by 25% and improve the timing (300ps on the worst slack), with no wire length penalty or CPU overhead. Our incremental approach is also able to maintain the placement stability.

References

[1]
{1} J. Lou and W. Chen, "Crosstalk-aware placement," IEEE Design & Test of Computers, pp. 24-32, Jan. 2004.
[2]
{2} J. Cong, D. Z. Pan, and P. V. Srinivas, "Improved crosstalk modeling for noise constrained interconnect optimization," in Proc. Asia and South Pacific Design Automation Conf., Jan. 2001.
[3]
{3} Semiconductor Industry Association, International Technology Roadmap for Semiconductors, 2003, http://public.itrs.net/.
[4]
{4} I. H. R. Jiang, Y. W. Chang, and J. Y. Jou, "Crosstalk driven interconnect optimization by simultaneous gate and wire sizing," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 999-1010, Sept. 2000.
[5]
{5} T. Xiao and M. Marek-Sadowska, "Gate sizing to eliminate crosstalk induced timing violation," in Proc. IEEE Int. Conf. on Computer Design, pp. 186-191, 2001.
[6]
{6} C. J. Alpert, A. Devgan, and S. T. Quay, "Buffer insertion for noise and delay optimization," in Proc. Design Automation Conf., pp. 362-367, 1998.
[7]
{7} C.-P. Chen and N. Menezes, "Noise-aware repeater insertion and wire sizing for on-chp interconnect using hierarchical moment-matching," in Proc. Design Automation Conf., pp. 502-506, June 1999.
[8]
{8} U. Brenner and A. Rohe, "An effective congestion driven placement framework," in Proc. Int. Symp. on Physical Design, pp. 6-11, 2002.
[9]
{9} A. E. Caldwell, A. B. Kahng, and I. L. Markov, "Can recursive bisection alone produce routable, placements?," in Proc. Design Automation Conf., pp. 477-482, 2000.
[10]
{10} X. Yang, B.-K. Choi, and M. Sarrafzadeh, "Routability-driven white space allocation for fixed-die standard-cell placement," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 410-419, Apr. 2003.
[11]
{11} M. R. Becer, D. Blaauw, R. Panda, and I. N. Hajj, "Early probabilistic noise estimation for capacitively coupled interconnects," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 337-345, Mar. 2003.
[12]
{12} A. Odabasioglu, M. Celik, and L. T. Pileggi, "Prima: passive reduced-order interconnect macromodeling algorithm," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 645-653, Aug. 1998.
[13]
{13} S. N. Adya, I. Markov, and P. Villarrubia, "On whitespace and stability in mixed-size placement and physical synthesis," in Proc. Int. Conf. on Computer Aided Design, pp. 311-318, 2003.
[14]
{14} C. Chiang, C. K. Wong, and M. Sarrafzadeh, "A weighted steiner tree-based global router with simultaneous length and density minimization," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 1461-1469, Dec. 1994.
[15]
{15} B. S. Ting and B. N. Tien, "Routing techniques for gate array," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 301-312, Oct. 1983.
[16]
{16} R. C. C. IV, J. Li, and C. K. Cheng, "A global router with a theoretical bound on the optimal solution," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 208-216, Feb. 1996.
[17]
{17} T. Sakurai, "Closed-form expressions for interconnection delay, coupling, and crosstalk in VLSIs," IEEE Trans. on Electron Devices, vol. 40, pp. 118-124, 1993.
[18]
{18} A. Vittal and M. Marek-Sadowska, "Crosstalk reduction for VLSI," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 16, pp. 290-98, 1997.
[19]
{19} H. Kawaguchi and T. Sakurai, "delay and noise formulas for capacitively coupled distributed RC lines," in Proc. Asia and South Pacific Design Automation Conf., pp. 35-43, Jan. 1998.
[20]
{20} A. Devgan, "Efficient coupled noise estimation for on-chip interconnects," in Proc. Int. Conf. on Computer Aided Design, pp. 147-153, Nov. 1997.
[21]
{21} A. Vittal, L. Chen, M. Marek-Sadowska, K.-P. Wang, and S. Yang, "Crosstalk in VLSI interconnections," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 18, no. 2, pp. 1817-24, 1999.
[22]
{22} A. B. Kahng, S. Muddu, and D. Vidhani, "Noise and delay uncertainty studies for coupled rc interconnects," in IEEE International ASIC/SOC Conference, pp. 3-8, 1999.
[23]
{23} C. J. Alpert, G.-J. Nam, and P. G. Villarrubia, "Effective free space management for cut-based placement via analytical constraint generation," IEEE Trans. on Computer-Aided Design of integrated Circuits and Systems, pp. 1343-1353, Oct. 2003.
[24]
{24} H. Eisenmann and F. M. Johannes, "Genetic global placement and floorplanning," in Proc. Design Automation Conf., pp. 269-274, 1998.
[25]
{25} M. Wang, X. Yang, and M. Sarrafzadeh, "Dragon2000: Standard-cell placement tool for large industry circuits," in Proc. Int. Conf. on Computer Aided Design, pp. 260-263, 2000.
[26]
{26} P. Villarrubia, G. Nusbaum, R. Masleid, and P. T. Patel, "IBM RISC chip design methodology," in Proc. IEEE Int. Conf. on Computer Design, pp. 143-147, 1989.

Cited By

View all
  • (2015)Crosstalk-aware multi-bit flip-flop generation for power optimizationIntegration, the VLSI Journal10.1016/j.vlsi.2014.08.00248:C(146-157)Online publication date: 1-Jan-2015
  • (2010)Technology mapping with crosstalk noise avoidanceProceedings of the 2010 Asia and South Pacific Design Automation Conference10.5555/1899721.1899790(319-324)Online publication date: 18-Jan-2010
  • (2007)High-performance routing at the nanometer scaleProceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326175(496-502)Online publication date: 5-Nov-2007
  • Show More Cited By
  1. True crosstalk aware incremental placement with noise map

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      ICCAD '04: Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design
      November 2004
      913 pages
      ISBN:0780387023

      Sponsors

      Publisher

      IEEE Computer Society

      United States

      Publication History

      Published: 07 November 2004

      Check for updates

      Qualifiers

      • Article

      Conference

      ICCAD04
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 457 of 1,762 submissions, 26%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 15 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2015)Crosstalk-aware multi-bit flip-flop generation for power optimizationIntegration, the VLSI Journal10.1016/j.vlsi.2014.08.00248:C(146-157)Online publication date: 1-Jan-2015
      • (2010)Technology mapping with crosstalk noise avoidanceProceedings of the 2010 Asia and South Pacific Design Automation Conference10.5555/1899721.1899790(319-324)Online publication date: 18-Jan-2010
      • (2007)High-performance routing at the nanometer scaleProceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326175(496-502)Online publication date: 5-Nov-2007
      • (2006)Crosstalk-aware domino logic synthesisProceedings of the conference on Design, automation and test in Europe: Proceedings10.5555/1131481.1131841(1312-1317)Online publication date: 6-Mar-2006
      • (2005)Computational geometry based placement migrationProceedings of the 2005 IEEE/ACM International conference on Computer-aided design10.5555/1129601.1129610(41-47)Online publication date: 31-May-2005
      • (2005)Diffusion-based placement migrationProceedings of the 42nd annual Design Automation Conference10.1145/1065579.1065712(515-520)Online publication date: 13-Jun-2005

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media