Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2007-05-22
2007-05-22
Chiang, Jack (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
10342637
ABSTRACT:
Disclosed are methods and mechanisms for implementing tessellation-based processing of an integrated circuit design. Tessellation based routing of objects on an integrated circuit layout can be performed by identifying a spacing rule for tessellating at least a portion of the integrated circuit layout, forming one or more plane figures in the tessellation having one or more edges compliant with the spacing rule, the edges of the one or more plane figures forming a contour derived from a shape of a blockage object, and identifying a routing path along at least part of the one or more edges. Packing and pushing of objects may be performed using this approach.
REFERENCES:
patent: 5157618 (1992-10-01), Ravindra et al.
patent: 5911061 (1999-06-01), Tochio 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: 2002/0059194 (2002-05-01), Choi et al.
patent: 2004/0044980 (2004-03-01), Juengling
Johnson, Howard; “Breaking up a pair,” EDN, (Nov. 9, 2000), 1 pg.
“Supermax ECAD Documentation v9.2,” Copyright 1985-2003; 1 pg.; “Supermax ECAD Version 9 Features,” 2 pgs.; http://www.dde-eda.com/v9features.html; “chshape,” 3 pgs.; http://www.dde-eda.com/ecadman/ipl/chshape.html; “Design Properties,” 10 pgs., http://dde-eda.com/ecadman/ipl/objectref/dp-mnop.html.
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. “AnO(nlogn) 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. Metha “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 “—geoADDITION—Flexible Handling of Geometrics 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 Cirucits 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 Compactor 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—1993 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 Tranactions 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 Conference and Exhibition(Feb. 16-20, 2004) 1:306-310.
Hsiao, P.-Y. and W.-S. Feng “Using a Multiple Storage Quad Tree on a Hierarchical VLSI Compaction Scheme”IEEE Transactions on Computer-Aided Design(May 1990) 9(5):522-536.
Hsiao, P.-Y. et al. “Optimal tile partition for space region of integrated circuits geometry”IEEE Proceedings-E(May 1993) 140(3):145-153.
Hur, S.-W. and J. Lillas “Relaxation and Clustering in a Local Search Framework: Applicati
Chyan David Dah-Juh
Raj Satish Samuel
Bingham & McCutchen LLP
Cadence Design Systems Inc.
Chiang Jack
LandOfFree
Method and mechanism for implementing tessellation-based... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and mechanism for implementing tessellation-based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and mechanism for implementing tessellation-based... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3733746