×

Towards optical steiner tree routing in the presence of rectilinear obstacles

  • US 5,491,641 A
  • Filed: 10/04/1993
  • Issued: 02/13/1996
  • Est. Priority Date: 10/04/1993
  • Status: Expired due to Term
First Claim
Patent Images

1. An apparatus for constructing an approximate Minimum Rectilinear Steiner Tree (MRST) which constitutes an interconnective routing path for a net of pins on edges of rectilinear components of an integrated circuit such that said routing path extends between said components, comprising:

  • first processing means for constructing an escape graph for said net in accordance with locations of said components, wherein said escape graph includes points which are formed by the intersection of lines from said pins and said edges of said components; and

    second processing means for constructing said approximate MRST, the second processor comprising;

    third processing means for constructing Voronoi regions in said escape graph; and

    for constructing a first graph including said pins, and edges connecting two of said pins respectively in said escape graph which extend between adjacent Voronoi regions;

    fourth processing means for constructing a second graph as a minimum spanning tree of said first graph;

    fifth processing means for constructing a third graph as a subgraph of said second graph including shortest paths in said escape graph corresponding to edges in said second graph;

    sixth processing means for constructing a fourth graph as a minimum spanning tree of said third graph; and

    seventh processing means for constructing said approximate MRST from said fourth graph by deleting said points which constitute end points in said fourth graph and do not correspond to said pins.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×