Non-orthogonal structures and space tiles for layout,...

Details Non-orthogonal structures and space tiles for layout,... Non-orthogonal structures and space tiles for layout,...

2006-08-22

2006-08-22

Kik, Phallaka (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000

Reexamination Certificate

active

07096445

ABSTRACT:
Disclosed is an improved approach for maintaining the structures for objects in a layout. A single type of structure is maintained that can be used to store or track a polygon of any shape, as long as the shape possesses a supported number of sides. The structure is capable of supporting irregular polygons or objects having angled edges. In one approach, the structure maintains information about each polygon as if that polygon is an octagon. Therefore, any polygon having eight or less orthogonal or diagonal sides can be supported using this structure.

REFERENCES:
patent: 4933889 (1990-06-01), Meshkat et al.
patent: 5157618 (1992-10-01), Ravindra et al.
patent: 5550748 (1996-08-01), Xiong
patent: 5617322 (1997-04-01), Yokota
patent: 5689433 (1997-11-01), Edwards
patent: 5774696 (1998-06-01), Akiyama
patent: 5822214 (1998-10-01), Rostoker et al.
patent: 5911061 (1999-06-01), Tochio et al.
patent: 6035108 (2000-03-01), Kikuchi
patent: 6128767 (2000-10-01), Chapman
patent: 6166441 (2000-12-01), Geryk
patent: 6230306 (2001-05-01), Raspopovic et al.
patent: 6247853 (2001-06-01), Papadopoulou et al.
patent: 6253363 (2001-06-01), Gasanov et al.
patent: 6289495 (2001-09-01), Raspopovic et al.
patent: 6301686 (2001-10-01), Kikuchi et al.
patent: 6317864 (2001-11-01), Kikuchi et al.
patent: 6324675 (2001-11-01), Dutta et al.
patent: 6349403 (2002-02-01), Dutta et al.
patent: 6412097 (2002-06-01), Kikuchi et al.
patent: 6484305 (2002-11-01), Syo
patent: 6625611 (2003-09-01), Teig et al.
patent: 6668365 (2003-12-01), Harn
patent: 6680150 (2004-01-01), Blatchford et al.
patent: 6701306 (2004-03-01), Kronmiller et al.
patent: 6785874 (2004-08-01), Tsukuda
patent: 6829757 (2004-12-01), Teig et al.
patent: 6845495 (2005-01-01), Andreev et al.
patent: 6948146 (2005-09-01), Allen et al.
patent: 6952815 (2005-10-01), Teig et al.
patent: 6957410 (2005-10-01), Teig et al.
patent: 6976237 (2005-12-01), Teig et al.
patent: 2002/0059194 (2002-05-01), Choi et al.
patent: 2002/0157075 (2002-10-01), Teig et al.
patent: 2002/0166105 (2002-11-01), Teig et al.
patent: 2002/0170027 (2002-11-01), Teig et al.
patent: 2002/0174412 (2002-11-01), Teig et al.
patent: 2002/0199165 (2002-12-01), Teig et al.
patent: 2003/0005399 (2003-01-01), Igarashi et al.
patent: 2003/0023935 (2003-01-01), McManus et al.
patent: 2003/0066042 (2003-04-01), Teig et al.
patent: 2003/0070152 (2003-04-01), Muller
patent: 2003/0088841 (2003-05-01), Teig et al.
patent: 2003/0115566 (2003-06-01), Teig
patent: 2003/0121015 (2003-06-01), Teig et al.
patent: 2004/0044980 (2004-03-01), Juengling
patent: 2004/0139417 (2004-07-01), Allen et al.
patent: 03127277 (1991-05-01), None
Bhattacharya et al., “Quadtree interconnection network layout”, Proceedings of the Second Great Lake Symposium on VLSI, Feb. 28, 1992, pp. 74-81.
Conway et al., “A New Template Based Approach to Module Generation”, IEEE International Conference on Computer-Aided Design, Nov. 11, 1990, pp. 528-531.
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), pp. 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) pp.: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), pp. 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), pp. 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), pp. 1:723-726.
Cadence Design Systems, Inc.IC Shape-Based Technology Chip Assembly User GuideProduct Version 11.0 (Nov. 2001), pp. 1-125.
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) pp. 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) pp. 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 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 200

Affiliated with

Also associated with

Rating

Non-orthogonal structures and space tiles for layout,... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Non-orthogonal structures and space tiles for layout,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-orthogonal structures and space tiles for layout,... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3701888