Importance

Loading Importance Indicators...

Abstract

An object of the present invention is to provide for a method and apparatus to partition high fanout nets into smaller subnets. Said method includes the steps of identifying elementary pairs of pins in the net, each such elementary pair defining a line; eliminating lines such that a planar graph is formed; eliminating further lines such that a spanning tree is formed, said spanning tree connecting each pin in the net; identifying basic elements, each basic element forming a portion of said spanning tree; and constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements. Said elementary pairs are identified by determining for each pin in said net a relative x-coordinate and a relative y-coordinate, constructing for each pin a combined binary coordinate as a function of the pin's relative x-coordinate and relative y-coordinate, ordering the pins in accordance with their respective combined binary coordinates, iteratively combining the pins until one pin remains, and iteratively expanding the pins.

Loading the Abstract Image...

First Claim