Patent ID: 6324675
Filing Date: 2001-11-27
Classification: G06F

Abstract:
A computer controlled routing method comprising the steps of:a) producing a wire solution for an integrated circuit layout having a plurality of objects by traversing a plurality of source pin and target pin pairs and performing a gridless routing procedure to model a wire connection between each traversed source pin and target pin pair, said step a) comprising the steps of:a1) determining a first plurality of paths between a given source pin and a given target pin wherein each path comprises lanes, wherein said lanes reside in at least one of a plurality of layers of said integrated circuit layout;a2) pruning said first plurality of paths to produce a path subset, wherein said pruning is based on the location of a path of said plurality relative to an object of said plurality;a3) determining the lowest cost path of said path subset by applying a cost function to each path of said path subset wherein said cost function considers only objects within the same layer as each lane; anda4) modeling a wire connection between said source pin and said target pin based on said lowest cost path determined at step a3) wherein said wire connection is allowed to overlap with other wire connections and with selected objects;a5) repeating said step a1) through said step a4) for additional source pins and target pins;b) repeating step a) provided said wire solution contains less number of overlaps as a prior iteration of step a; andc) reporting the last computed wire solution as a final wire solution.