Identifying overconstraints using port abstraction graphs

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

1994-01-21

1996-10-22

Teska, Kevin J.

Boots, shoes, and leggings

364488, 364489, 364490, G06F 1750

Patent

active

055683967

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 Transactions on Computer-Aided Design, 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 Symposium on Circuits and Systems, 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 Log Insertion for 2D Mask Compaction: A Global Optimization Perspective," 1992 European Design Automation Conference, pp. 508-512.
Perez-Segovia et al., "CACTUS: A Symbolic CMOS Two-Dimensional Compactor," 1990 European Design Automation Conference, pp. 201-205.
Bamji, C., et al., "Hierarchical Pitchmatching Compaction Using Minimum Design", Cadence Design Systems, 1992 ACM/IEEE Design Automation Conference, pp. 311-317.
Dutt, D., et al., "On Minimal Closure Constraint Generation for Symbolic Cell Assembly", 28th ACM/IEEE Design Automation Conference, Paper 41.5, 1991, pp. 736-739.
Lee, J., et al., "HIMALAYAS-A Hierarchical Compaction System with a Minimized Constraint Set", IEEE, Aug. 1992, pp. 150-157.
Marple, D., "A Hierarchy Preserving Hierarchical Compactor", 27th ACM/IEEE Design Automation Conference, Paper 22.2, 1990, pp. 375-381.
Schiele, W., "Compaction with Incremental Over-Constraint Resolution", 25th ACM/IEEE Design Automation Conference, Paper 26.2, 1988, pp. 390-395.

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-2364396