Maximum flow analysis for electronic circuit design

Details Maximum flow analysis for electronic circuit design Maximum flow analysis for electronic circuit design

2006-08-08

2006-08-08

Whitmore, Stacy A. (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000

Reexamination Certificate

active

07089526

ABSTRACT:
Disclosed are improved methods and mechanisms for congestion and maximum flow analysis for routing an integrated circuit design. In one approach, maximum flow analysis is performed by tessellating a portion of a layout to form space tiles, which are used to interpret a flow graph. The flow graph comprises a set of vertices and edges. The capacity of edges in the flow graph is used to identify the maximum flow for that portion of the layout. In another approach, an edge walk is performed against a set of space tiles, in which a nearest neighbor determination is determined for each edge to perform maximum flow analysis.

REFERENCES:
patent: 5157618 (1992-10-01), Ravindra et al.
patent: 5911061 (1999-06-01), Tochio et al.
patent: 6075933 (2000-06-01), Pavisic et al.
patent: 6219823 (2001-04-01), Hama et al.
patent: 6230306 (2001-05-01), Raspopovic et al.
patent: 6253363 (2001-06-01), Gasanov et al.
patent: 6289495 (2001-09-01), Raspopovic et al.
patent: 6324675 (2001-11-01), Dutta et al.
patent: 6349403 (2002-02-01), Dutta et al.
patent: 6625611 (2003-09-01), Teig et al.
patent: 6668365 (2003-12-01), Harn
patent: 6701306 (2004-03-01), Kronmiller et al.
patent: 6785874 (2004-08-01), Tsukuda
patent: 6845495 (2005-01-01), Andreev et al.
patent: 6857115 (2005-02-01), Dasasathyan et al.
patent: 2002/0059194 (2002-05-01), Choi et al.
patent: 2003/0066045 (2003-04-01), Teig et al.
patent: 2004/0044980 (2004-03-01), Tsukuda
Hu, Jiang et al., “A survey on multi-net global routing for integrated circuits”, http://www.ece.umn.edu/users/sachin/PUBS/integration01.pdf, 1998, pp. 1-68.
Sarker, Probir, et al., “Routability-driven repeater block planning interconnect-centric floorplanning”, Apr. 2000, IEEE, International Symposium on Physical Design archive Proceedings of the 2000 international symposium on Physical design. pp. 186-191.
Brenner, Ulrich, et al., “An effective congestion driven placement framework”, 2002, ACM Press, International Symposium on Physical Design archive Proceedings of the 2002 international symposium on Physical design. pp. 6-11.
Dinitz, Y., et al,. On the single-source unsplittable flow problem, IEEE, Nov. 1998, pp. 290-299.
Ahuja, R.K. et al., eds.,Network Flows. Theory, Algorithms, and Applications(1993) pp. 510-542, Prentice Hall, Upper Saddle River, NJ.
Al-Yamani, A. et al. “HPTS: Heterogeneous Parallel Tabu Search for VLSI Placement”Proceedings of the 2002 Congress on Evolutionary Computation(May 12-17, 2002). 1:351-355.
Anderson, R. et al. “An O(n log n) Algorithm for 1-D Tile Compaction”ICCAD-89—International Conference on Computer-Aided Design(Nov. 5-9, 1989) pp. 144-147.
Balasa, F. et al. “Efficient Solution Space Exploration Based on Segment Trees in Analog Placement with Symmetry Constraints” inIEEE/ACM International Conference on Computer Aided Design(Nov. 10-14, 2002) pp. 497-502.
Barzaghi, M. et al. “Hierarchical Management of VLSI Cells at Different Description Levels”Proceedings of the 6thMediterranean Electrotechnical Conference(May 22-24, 1991) 1:327-330.
Benetis, R. et al. “Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects”Proceedings of the International Database Engineering and Applications Symposium(IDEAS'02) (Jul. 17-19, 2002) pp. 44-53.
Bern, J. et al. “Some Heuristics for Generating Tree-like FBDD Types”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems(Jan. 1996) 15(1):127-130.
Bhattacharya, S. and W.-T. Tsai “Area Efficient Binary Tree Layout”1stGreat Lakes Symposium on VLSI(Mar. 1-2, 1991) pp. 18-24.
Blust, G. and D.P. Mehta “Corner Stitching for L-shaped Tiles”Proceedings of the 3rdGreat Lakes Symposium on VLSI, Design Automation of High Performance VLSI Systems(Mar. 5-6, 1993) pp. 67-68.
Borah, M. et al. “An Edge-Based Heuristic for Steiner Routing”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems(Dec. 1994) 13(12):1563-1568.
Brück, R. and H. Wronn “—geoADDICTION—Flexible Handling of Geometries in IC-Layout Tools”ISCAS '88—IEEE International Symposium on Circuits and Systems(Jun. 7-9, 1988) 1:723-726.
Cadence Design Systems, Inc.IC Shape-Based Technology Chip Assembly User GuideProduct Version 11.0 (Nov. 2001).
Carlson, E.C. and R.A. Rutenbar “A Scanline Data Structure Processor for VLSI Geometry Checking”IEEE Transactions on Computer-Aided Design(Sep. 1987) 6(5):780-794.
Cheung, P. and J. Hesketh “Design Automation Tools for Tile-Based Analogue Cells”IEE Colloquium on New Directions in VLSI Design(Nov. 27, 1989) pp. 3/1-3/5.
Chiang, C. and C.-S. Chiang “Octilinear Steiner Tree Construction”MWSCAS-2002—The 2002 45thMidwest Symposium on Circuits and Systems(Aug. 4-7, 2002) 1:603-606.
Christian, B.S. et al. “A VLSI Interval Router for High-Speed Networks”Canadian Conference on Electrical and Computer Engineering(May 26-29, 1996) 1:154-157.
Cong, J. et al. “Multilevel Approach to Full-Chip Gridless Routing”ICCAD 2001—IEEE/ACM International Conference on Computer-Aided Design(Nov. 4-8, 2001) pp. 396-403.
Curatelli, F. et al. “Efficient Management of Complex Elements in Physical IC Design”Proceedings of the IEEE International Symposium on Circuits and Systems(May 1-3, 1990) 1:456-459.
Das, S. and B.B. Bhattacharya “Channel Routing in Manhattan-Diagonal Model”Proceedings of the 9thInternational Conference on VLSI Design(Jan. 3-6, 1996) pp. 43-48.
Dasgupta, P. et al. “Multiobjective Search in VLSI Design”Proceedings of the 7thInternational Conference on VLSI Design(Jan. 1994) pp. 395-400.
Dasgupta, P. et al. “Searching Networks With Unrestricted Edge Costs”IEEE Transactions on Systems, Man and Cybernetics-Part A: Systems and Humans(Nov. 2001) 31(6):497-507.
Dijkstra, E.W. “A Note on Two Problems in Connexion with Graphs”Numerische Mathematik(1959) 1:269-271
de Dood, P. et al. “A Two-Dimensional Topological Compator With Octagonal Geometry”28thACM/IEEE Automation Conference(1991) pp. 727-731.
Doong, K. Y.-Y. et al. “Infrastructure Development and Integration of Electrical-Based Dimensional Process Window Checking”IEEE Transactions on Semiconductor Manufacturing(May 2004) 17(2):123-141.
Dutt, S. “New Faster Kernighan-Lin-Type Graph-Partitioning Algorithms”ICCAD-93—IEEE/ACM International Conference on Computer-Aided Design(Nov. 7-11, 1993) pp. 370-377.
Façanha, H.S. et al. “Layout Tool for High Speed Electronic and Optical Circuits”IEE Colloquium on Analogue IC Design: Obstacles and Opportunities(Jun. 18, 1990) pp. 3/1-3/5.
Façanha, H.S. et al. “Data structures for physical representation of VLSI”Software Engineering Journal(Nov. 1990) 5(6):339-349.
Fang, J.P. and S.J. Chen “Tile-Graph-Based Power Planning”ISCAS'03—Proceedings of the 2003 International Symposium on Circuits and Systems(May 25-28, 2003) 5:V-501 - V-504.
Faroe, O. et al. “Local Search for Final Placement in VLSI Design”ICCAD 2001—IEEE/ACM International Conference on Computer-Aided Design(Nov. 4-8, 2001) pp. 565-572.
Gannett, J.W. “Shortfinder: A Graphical CAD Tool for Locating Net-to-Net Shorts in VLSI Chip Layouts”IEEE Transactions on Computer-Aided Design(Jun. 1990) 9(6):669-674.
Grgek, M. et al. “Performance Comparison of Several Data Structures for Storing VLSI Geometry”The IEEE Region 8 EUROCON 2003, Computer as a Tool(Sep. 22-24, 2003) 1:156-159.
Guibas, L.J. and J. Stolfi “On Computing All North-East Nearest Neighbors in the L1Metric”Information Processing Letters(Nov. 8, 1983) 17:219-223.
Hettiaratchi, S. and P.Y.K. Cheung “A novel implementation of tile-based address mapping”Date'04—Proceedings of the Design, Automation and Test in Europe Conferenc

Affiliated with

Also associated with

Rating

Maximum flow analysis for electronic circuit design does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Maximum flow analysis for electronic circuit design, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum flow analysis for electronic circuit design will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3619750