Methods for partitioning circuits in order to allocate elements

Details Methods for partitioning circuits in order to allocate elements Methods for partitioning circuits in order to allocate elements

1995-07-31

1997-08-19

Teska, Kevin J.

Boots, shoes, and leggings

364488, 364489, 364490, 364491, G06F 1750

Patent

active

056597177

ABSTRACT:
Improved circuit partitioning methods are provided which combine the advantage of multiple starting positions of the random initial placement approach with the advantage of optimal starting positions of the greedy initial placement approach, by starting with greedy initial placement and modifying partitioning constraints on subsequent passes so that each pass begins in a new position, In addition, the partitioning goals of interconnection minimization and resource utilization efficiency may be prioritized according to a design goal by manipulating the manner in which partitioning constraints are changed during each partitioning pass. Furthermore a user may adjust the weight of the benefits for eliminating existing interconnections and the weight of the penalties for adding new interconnections in accordance with a design goal.

REFERENCES:
patent: 4495559 (1985-01-01), Gelatt, Jr. et al.
patent: 4577276 (1986-03-01), Dunlop et al.
patent: 4593363 (1986-06-01), Burstein et al.
patent: 4609986 (1986-09-01), Hartmann et al.
patent: 4617479 (1986-10-01), Hartmann et al.
patent: 4677318 (1987-06-01), Veenstra
patent: 4713792 (1987-12-01), Hartmann et al.
patent: 4774421 (1988-09-01), Hartmann et al.
patent: 4871930 (1989-10-01), Wong et al.
patent: 4899067 (1990-02-01), So et al.
patent: 4908772 (1990-03-01), Chi
patent: 4912342 (1990-03-01), Wong et al.
patent: 4918614 (1990-04-01), Modarres et al.
patent: 5113352 (1992-05-01), Finnerty
patent: 5121006 (1992-06-01), Pedersen
patent: 5187784 (1993-02-01), Rowson
patent: 5218551 (1993-06-01), Agrawal et al.
patent: 5220214 (1993-06-01), Pedersen
patent: 5224056 (1993-06-01), Chene et al.
patent: 5237514 (1993-08-01), Curtin
patent: 5251147 (1993-10-01), Finnerty
patent: 5260610 (1993-11-01), Pedersen et al.
patent: 5260611 (1993-11-01), Cliff et al.
patent: 5308798 (1994-05-01), Brasen et al.
patent: 5341308 (1994-08-01), Mendel
patent: 5349536 (1994-09-01), Ashtaputre et al.
patent: 5350954 (1994-09-01), Patel
patent: 5359537 (1994-10-01), Saucier et al.
patent: 5359538 (1994-10-01), Hui et al.
patent: 5371422 (1994-12-01), Patel et al.
patent: 5495419 (1996-02-01), Rostoker et al.
patent: 5506788 (1996-04-01), Cheng et al.
patent: 5513124 (1996-04-01), Trimberger et al.
patent: 5521837 (1996-05-01), Frankle et al.
patent: 5557533 (1996-09-01), Koford et al.
patent: 5568636 (1996-10-01), Koford
"A New Simultaneous Circuit Partitioning and Chip Placement Approach Based on Simulated Annealing", by A. Chatterjee et al., 27th ACM/IEEE Design Automation Conference, 1990, pp. 36-39.
"The Optimal Circuit Decompositions Using Network Flow Formulations", by C. Cheng, Circuits and Systems, 1990 IEEE International Symposium, pp. 2650-2653.
"A Unified Approach to Partitioning and Placement", by R. Tsay et al., IEEE Transactions on Circuits and Systems, vol. 38, No. 5, May 1991, pp. 521-533.
"On the Graph Bisection Problem", by Y. Saab et al., IEEE Transactions on Circuits and Systems--Part 1: Fundamental Theory and Applications, vol. 39, No. 9, Sep. 1992, pp. 760-762.
"ML-Germinal: A New Heuristic Standard Cell Placement Algorithm", by A. Dahmani et al., IEEE European Design Automation Conference, 1993, pp. 184-188.
"A Generic Floorplanning Methodology", by M. Mortazavi et al., IEEE Autotestcon, Sep. 1994, pp. 749-763.
"Min-Cut Placement with Global Objective Functions for Large Scale Sea-of-Gates Arrays", by K. Takahashi et al., IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, No. 4, Apr. 1995, pp. 434-446.
"On the Integration of Partitioning and Global Routing for Rectilinear Placement Problems", by C. Yeh et al., IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, No. 1, Jan. 1996, pp. 83-91.
Breuer, Melvin A., "A Class of Min-Cut Placement Algorithms", Dept. Of Elec. Engng. & Comp. Sci., University of Southern California, pp. 284-290.
Fiduccia, C.M., et al., "A Linear-Time Heuristic for Improving Network Partitions", 19th Design Automation Conference, 1982, pp. 241-247.
Kernighan, B.W., et al., "An Efficient Heuristic Procedure for Partitioning Graphs", Bell Sys. Tech. Jour., pp. 291-307 (1970).
Krishnamurthy, Balakrishnan, "An Improved Min-Cut Algorithm For Partitioning VLSI Networks", IEEE Trans. On Comp, vol. C-33, No. 5, May 1984, pp. 438-446.
Schweikert, D.G., et al., "A Proper Model for the Partitioning of Electrical Circuits", Proceedings of the 9th Design Automation Workshop, 1979, pp. 57-62.

Affiliated with

Also associated with

Rating

Methods for partitioning circuits in order to allocate elements does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods for partitioning circuits in order to allocate elements , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods for partitioning circuits in order to allocate elements will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1112237