Optimal routing algorithms for pin clusters in high-density multichip modules

Muhammet Mustafa Ozdal, Martin D. F. Wong, Philip S. Honsinger

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

5 Citations (Scopus)


As the circuit densities and transistor counts are increasing, the package routing problem is becoming more and more challenging. In this paper, we study an important routing problem encountered in typical high-end MCM designs: routing within dense pin clusters. Pin clusters are often formed by pins that belong to the same functional unit or the same data bus, and can become bottlenecks in terms of overall routability. Typically, these clusters have irregular shapes, which can be approximated with rectilinear convex boundaries. Since such boundaries have often irregular shapes, a traditional escape routing algorithm may give unroutable solutions. In this paper, we study how the positions of escape terminals on a convex boundary affect the overall routability. For this purpose, we propose a set of necessary and sufficient conditions to model routability outside a rectilinear convex boundary. Given an escape routing solution, we propose an optimal algorithm to select the maximal subset of nets that are routable outside the boundary. After that, we focus on an integrated approach to consider routability constraints (outside the boundary) during the actual escape routing algorithm. Here, we propose an optimal algorithm to find the best escape routing solution that satisfies all routability constraints. Our experiments demonstrate that we can reduce the number of layers by 17% on the average, by using this integrated methodology.

Original languageEnglish
Title of host publicationProceedings of the 2005 International Conference on Computer-Aided Design
Place of PublicationUnited States
Number of pages8
Publication statusPublished - Nov 2005
EventIEEE/ACM International Conference on Computer-Aided Design, ICCAD 2005 - San Jose, United States
Duration: 6 Nov 200510 Nov 2005
https://ieeexplore.ieee.org/xpl/conhome/10431/proceeding (Conference proceedings)


ConferenceIEEE/ACM International Conference on Computer-Aided Design, ICCAD 2005
Country/TerritoryUnited States
CitySan Jose
Internet address

Scopus Subject Areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Optimal routing algorithms for pin clusters in high-density multichip modules'. Together they form a unique fingerprint.

Cite this