Novel technique for sea of gates global routing

Bharat Krishna, C. Y Roger Chen, Naresh K. Sehgal

Research output: Chapter in Book/Entry/PoemConference contribution


We present a novel global routing and cross-point assignment methodology for sea-of-gates (SOG) designs. Using the proposed congestion driven spanning trees (CDST), and continuously analyzing the congestion at all steps, nets are incrementally globally routed in one of the six well thought of heuristic steps of our methodology. This eliminates the need for rip-up and re-route and enables our approach to achieve good completion rates. We tested our flow on a number of testcases from the industry. The net lengths produced by our flow were compared to the theoretical lower-bound (steiner tree) and were found to be at most 4% worse. We compared the results of creating the net segments by the classical MST verses the CDST and observed an 80% improvement in the number of incomplete nets. Completing the detailed routing using a commercially available detailed router validated the results of the proposed global routing and cross-point assignment.

Original languageEnglish (US)
Title of host publicationProceedings of the IEEE Great Lakes Symposium on VLSI
PublisherIEEE Computer Society
Number of pages4
StatePublished - 2000
EventGLSVLSI 2000: 10th Great Lakes Symposium on VLSI - Chicago, IL, USA
Duration: Mar 2 2000Mar 4 2000


OtherGLSVLSI 2000: 10th Great Lakes Symposium on VLSI
CityChicago, IL, USA

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Novel technique for sea of gates global routing'. Together they form a unique fingerprint.

Cite this