Hier archical pitchmaking compaction method and system for integ

Details Hier archical pitchmaking compaction method and system for integ Hier archical pitchmaking compaction method and system for integ

1992-05-26

1995-01-10

Teska, Kevin J.

Boots, shoes, and leggings

364489, 364491, G06F 1560

Patent

active

053813430

ABSTRACT:
A hierarchical pitchmatching compactor is provided that maintains hierarchical structure, design rule correctness, and circuit integrity of a symbolic layout while globally compacting the layout without excessive computational or data handling requirements, even for layouts of substantial size. The compactor achieves this result by taking advantage of the regularity of the layout, to reduce the number of constraints in the linear programming problem to a minimum level. This minimal problem, called the minimum design, can be drastically smaller than the original minimization problem for layouts of practical interest. This technique is implemented by means of a computer program that operates on the original symbolic layout of an integrated circuit to produce an automatically compacted layout as the data output.

REFERENCES:
patent: 5079717 (1992-01-01), Miwa
patent: 5281558 (1994-01-01), Bamji et al.
David G. Boyer, "Symbolic Layout Compaction Review", ACM IEEE 25th Design Automation Conference, 1988; paper 26.1, pp. 383-389.
David Marple, "A Hierarchy Preserving Hierarchical Compactor", ACM IEEE 27th Design Automation Conference, 1990; paper 22.2, pp. 375-381.
David Marple, "Globally Optimum Compaction of Layout Hierarchies", 1990 preprint of document AB supra.
Cyrus S. Bamji, Charles E. Hauck, and Jonathan Allen, "A Design By Example Regular Structure Generator", ACM IEEE 22nd Design Automation Conference, 1985; paper 2.3, pp. 16-21.
John Hopcroft and Robert Tarjan, "Efficient Planarity Testing", Journal of the ACM, vol. 21, No. 4, Oct. 1974, pp. 549-568.
Jurgen Doenhardt and Thomas Lengauer, "Algorithmic Aspects of One-Dimensional Layout Compaction", IEEE Transactions on Computer-Aided Design, vol. CAD-6, No. 5, Sep. 1987, pp. 863-878.
Chi-Yuan Lo and Ravi Varadarajan, "An O(n.sup.1.5 logn) 1-d Compaction Algorithm", ACM IEEE 27th Design Automation Conference, 1990, pp. 382-386.
Debaprosad Dutt and Chi-Yuan Lo, "On Minimal Closure Constraint Generation for Symbolic Cell Assembly", ACM IEEE 28th Design Automation Conference, 1991, paper 41.5, pp. 736-739.
Yuh-Zen Liao and C. K. Wong, "An Algorithm to Compact A VLSI Symbolic Layout With Mixed Constraints", IEEE Transactions on Computer-Aided Design, vol. CAD-2, No. 2, Apr., 1983, pp. 62-69.
Mark Reichelt and Wayne Wolf, "An Improved Cell Model for Hierarchical Constraint-Graph Compaction", IEEE Int'l. Conf. on Computer-Aided Design, 1986; pp. 482-485.
Christos H. Papadimitriou and Kenneth Steiglitz, "Combinatorial Optimization: Algorithms and Complexity"; Prentice-Hall, Englewood Cliffs 1982, pp. 1-3, 26-66, 88-103, 342-343.
"Physical Design Automation of VLSI Systems", Ed. by B. T. Preas and Michael J. Lorenzetti, Benjamin/Cummings, Menlo Park 1988; Ch. 6, pp. 211-267, 274-281.

Affiliated with

Also associated with

Rating

Hier archical pitchmaking compaction method and system for integ does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hier archical pitchmaking compaction method and system for integ, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hier archical pitchmaking compaction method and system for integ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-855528