Method and apparatus for pre-computing routes for multiple wiring models
Patent 6687893 Issued on February 3, 2004. Estimated Expiration Date: January 7, 2022. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
Some embodiments provide a method of pre-computing routes for nets in a region of an integrated circuit ("IC") layout. The method initially defines a set of partitioning lines for partitioning the region into a plurality of sub-regions during a routing operation. For a particular set of potential sub-regions, the method then identifies a first set of routes based on a first wiring model and a second set of routes based on a second wiring model. Each identified set of routes traverses the particular set of potential sub-regions. The method then stores the identified routes.
Other References
A.H. Farrahi, et al., Quality of EDA CAD Tools: Definitions, Metrics and Directions, Quality Electronic Design, 2000, Proceedings of the first International Symposium on Mar. 2000, pp 395-405
A. Vannelli, et al., An adaptation of the interior point method for solving the global routing problem, Feb. 1991, IEEE pp 193-203
B. Berger, et al., Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing, Journal of the Association for Computing Machinery, pp. 500-542, Mar. 1995
C. Chiang, et al., Wirability of Knock-Knee Layouts with 45° Wires, IEEE Transactions on Circuits and Systems, vol. 38, Issue 6, pp 613-624, Jun. 1991
G. Overtone, EDA Underwriter 2 Finding Space in a Multi Layer Board, Electronic Engineering, Morgan-Grampian LTD, vol. 67, No. 819, pp 29-30
G.D. Hachtel et al., Linear Complexity Algorithms for Hierarchical Routing, 1/89, IEEE pp 64-80
J.D. Cho, et al., Four-Bend Top Down Global Routing, IEEE, pp 793-802, 1998
J. Su et al., Post Route Optimization for Improved Yield Using Rubber-Band Wiring Model, 1997 International Conference on Computer-Aided Design, pp 700-706, Nov. 1997
J. Vicente, RSR: A New Rectilinear Steiner Minimum Tree Approximation for FPGA Placement and Global Routing, Proceedings of the 24th Euro Micro Conference, pp 192-195, Aug. 1998
K. Powers et al., The 60° Grid: Routing Channels in Width d/square root 3, VLSI, 1991, Proceedings., First Great Lakes Symposium on Kalamazoo, MI, USA, pp 214-291, Mar. 1991
M. Alexander et al., Performance-Oriented Placement and Routing for field-programmable gate arrays, Proceedings of the European Design Automation Conference, pp 80-85, 1995
M. Alexander et al., Placement and Routing for Performance-Oriented FPGA Layout, VLSI Design, vol. 7, No. 1, 1998
M. Igarashi et al., A Diagonal-Interconnect Architecture and Its Application to RISC Core Design, 2002 IEEE Solid-State Circuits Conference, pp 210-460, Feb. 2002
P. Dood, et al., A Two-Dimensional Topological Compactor with Octagonal Geometry, 28th ACM/IEEE Design Automation Conference, pp 727-731, Jul. 1991
P. Parakh, et al., Congestion Driven Quadratic Placement, Proceedings of Design Automation Conference, 1998, pp 275-278
R. Putatunda et al., VITAL: Fully Automatic Placement Strategies for Very Large Semicustom Designs, Proceedings of the International Conference on Computer Design: VLSI in Computers and Processors, pp 434-439 Oct. 1988
S. Dutt, et al., Probability-Based Approaches to VLSI Circuit Partitioning, IEEE Trans. On Computer Aided Design of IC's and Systems, vol. 19, No. 5, May 2000, pp 534-549
Y. Sekiyama et al., Timing-Oriented Routers for PCB Layout Design of High-Performance Computers, International Conference on Computer Aided Design, pp 332-335, Nov. 1991
C. Leiserson et al., Algorithm for Routing and Testing Routability of Planar VLSI Layouts, pp 69-78, May 1985
S. Das et a., Channel Routing in Manhattan-Diagonal Model, 9th International Conference on VLSI Design, Jan. 1996. pp 43-48
W. Wei-Ming Dai et a., Routability of a Rubber-Band Sketch. 28th ACM/IEEE Design Automation Conference, 1991. pp 45-65
H. Chen, Routing L-Shaped Channels in Nonslicing-Structure Placement. 24th ACM/IEEE Design Automation Conference, pp 152-165, 1987
I. Tollis, Techniques for Wiring in Non-Square Grids, pp 66-69. May 1989
E. Lodi et al., A 2d Channel Router for the Diagonal Model, pp 111-125, Apr. 1991
E. Lodi et al., Routing in Times Square Mode, pp 41-48, Jun. 1990
K. Cheng-Kok et al., Manhattan or Non Manhattan? A Study of Alternative VLSI Routing Architectures. pp 47-52, 2000
E. Lodi et al., Routing Multiterminal Nets in a Diagonal Model, pp 899-902, 1988
D. Staepelaere et al., Surf: A Rubber-Band Routing System for Multichip Modules. pp 18-26, 1993
S. Das et al., Routing of L-Shaped Channels, Switch boxes and Staircases in Manhattan-Diagonal Model, pp 65-70m Jan. 1998
W. Schiele et al., A Gridless Router for Industrial Design Rule, 27th ACM/IEEE Design Automation Conference, pp 626-631, 1990
J. Nester, A New Look at Hardware Maze Routing, Proceedings of the 12th ACM Symposium on Great Lakes Symposium on VLSI, pp 142-147, Apr. 200
January 7, 2022. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
