Identifying overconstraints using port abstraction graphs

Details Identifying overconstraints using port abstraction graphs Identifying overconstraints using port abstraction graphs

1996-03-05

1996-12-03

Teska, Kevin J.

Boots, shoes, and leggings

364488, 364489, 364491, G06F 1750

Patent

active

055814743

ABSTRACT:
Overconstraints in a system, such as an electrical circuit layout, are identified using port abstraction graphs. Intercell pitchmatching constraints are represented by meta-edges between cells. Classes of edges which can be represented by a support edge are created, and the value of the class edges are increased to the value of the support edge. The edge values are updated in the graphs, and the redundant edges eliminated. Overconstraints are identified as positive cycles in the graphs, and a database of the layout is annotated and graphically displayed. The graphical display responds to user inputs to manipulate the display of the relations between constraints. The use of the port abstraction graphs also reduces the number of equations that need to be solved to compact the layout.

REFERENCES:
patent: 5079717 (1992-01-01), Miwa
patent: 5097422 (1992-03-01), Corbin, II et al.
patent: 5381343 (1995-01-01), Bamji et al.
Bushnell et al., "Automated Design Tool Execution in the Ulysses Design Environment," IEEE Trans. on CAD, vol. 8, No. 3, Mar. 1989, pp. 279-287.
Ishima et al., "An Algorithm to Detect Positive Cycles in a Constraint Graph for Layout Compaction," 1990 IEEE Int'l Symp. on Ckts & Sys., pp. 2853-2856.
Lo et al., "An O(n.sup.1.5 logn)1-d Compaction Algorithm," 1990 27th ACM/IEEE Design Automation Conference, Paper 22.3, pp. 382-387.
Martineau et al., "Automatic Jog Insertion for 2D Mask Compaction,: A Global Optimization Perspective," 1992 European Design Automation Conference, pp. 508-512.
Marple, "A Hierarchy Preserving Hierarchical Compactor," 1990 27th ACM/IEEE Design Automation Conference, pp. 375-381.
Schiele, "Compaction w/incremental Over-Constraint Resolution," 1988 ACM/IEEE Design Automation Conference, pp. 390-395.
De Lange et al., "A Hierarchical Constraint Graph Generation and Compaction System for Symbolic Layout," ICCD '89, pp. 532-535.
Ahmad, "Simple Enumeration of Minimal Cutsets of Acyclic Directed Graphs," IEEE Trans. on Reliability, vol. 37, No. 5, Dec. 1988, pp. 484-487.
Chen et al., "VLSI Layout Compaction W/Conditional Constraints," 1991 IEEE Int'l Symposium on Circuits and Systems, pp. 2132-2135.
Kim et al., "A New Hierarchical Layout Compactor Using Simplified Graph Models", 1992 29th ACM/IEEE Design Automation Conference, pp. 323-326.
Boyer, "Symbolic Layout Compaction Review," 1988 25th ACM/IEEE Design Automation Conference, pp. 383-389.
Perez-Segovia et al., "Cactus: A Symbolic CMOS Two-Dimensional Compactor," 1990 European Design Automation Conference, pp. 201-205.
Bamji et al., "Hierarchical Pitchmatching Compaction Using Minimum Design," 1992 ACM/IEEE Design Automation Conference, pp. 311-317.
Dutt et al., "On Minimal Closure Constraint Generation for Symbolic Cell Assembly," 28th ACM/IEEE Design Automation Conference 1991, pp. 736-739.
Lee et al., "Himalayas: A Hierarchical Compaction System w/a Minimized Constraint Set," IEEE, Aug. 1992, pp. 150-157.

Affiliated with

Also associated with

Rating

Identifying overconstraints using port abstraction graphs does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Identifying overconstraints using port abstraction graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Identifying overconstraints using port abstraction graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-790736