Integrated circuit cell placement parallelization with minimal n

Details Integrated circuit cell placement parallelization with minimal n Integrated circuit cell placement parallelization with minimal n

1997-02-11

1999-02-23

Teska, Kevin J.

Boots, shoes, and leggings

364489, 364490, 395675, G06F 1750

Patent

active

058751181

ABSTRACT:
A method for maximizing effectiveness of parallel processing, using multiple processors, to achieve an optimal cell placement layout on an integrated circuit (IC) chip is disclosed. The method requires the cells of the IC to be assigned to one of the multiple processors in a manner to balance the work load among the multiple processors. Then, the affinity of the cells to each of the multiple processors is determined. The affinity of the cells, including the conflict reduction factors and work load balancing factors, is used to reassign the cells to the processors. The cell affinity calculation and the processor reassignment are repeated until no cells are reassigned or for a fixed number of times. The assignment of the cells to the multiple processors and subsequent reassignments of the cells based on affinity of the cells to the processors reduces or eliminates the problems associated with prior parallel cell placement techniques.

REFERENCES:
patent: 5144563 (1992-09-01), Date et al.
patent: 5491641 (1996-02-01), Scepanovic et al.
patent: 5495419 (1996-02-01), Rostoker et al.
patent: 5557533 (1996-09-01), Koford et al.
patent: 5568322 (1996-10-01), Azami et al.
patent: 5568636 (1996-10-01), Koford
patent: 5578840 (1996-11-01), Scepanovic et al.
patent: 5615128 (1997-03-01), Scepanovic et al.
patent: 5636125 (1997-06-01), Rostoker et al.
patent: 5638293 (1997-06-01), Scepanovic et al.
patent: 5661663 (1997-08-01), Scepanovic et al.
patent: 5682322 (1997-10-01), Boyle et al.
patent: 5694602 (1997-12-01), Smith
patent: 5699265 (1997-12-01), Scepanovic et al.
patent: 5712793 (1998-01-01), Scepanovic et al.
patent: 5742510 (1998-04-01), Rostoker et al.
patent: 5745363 (1998-04-01), Rostoker et al.
Woo et al. ("Load balancing on a hypercube", IEEE Comput. Soc. Press, Proceedings of the Fifth International Symposium on Parallel Processing, 30 Apr. 1991, pp. 525-530).
Chandy et al. ("A parallel circuit-partitioned algorithm for timing driven cell placement", IEEE, Proceedings of International Conference on Computer Design: VLSI in Computers and Processors, 1 Jan. 1997, pp. 621-627).
Sanchis ("Multiple-way network partitioning", IEEE Transactions on Computers, vol. 38, No. 1, pp. 62-81, Jan. 1989).
Rose et al. ("Parallel standard cell placement algorithms with quality equivalent to simulated annealing", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 7, No. 3, pp. 387-396, Mar. 1988).
Banerjee et al. ("Parallel Simulated Annealing Algorithms for Cell Placement on Hypercube Multiprocesors", IEEE Transactions on Parallel and Distributed Systems, vol. 1, NO. 1, Jan. 1990).
Qian et al. ("Load balancing on generalized hypercube and mesh multiprocessors with LAL", IEEE Comput. Soc. Press, 11th International Conference on Distributed Computing Systems, 20 May 1991, pp. 402-409).
Adachi et al. ("A parallel implementation of nonlinear steady state analysis based on time-domain Newton-Raphson algorithm", IEEE, 1989 IEEE International Symposium on Circuits and Systems, 8 May 1989, pp. 889-892).

Affiliated with

Also associated with

Rating

Integrated circuit cell placement parallelization with minimal n does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Integrated circuit cell placement parallelization with minimal n, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Integrated circuit cell placement parallelization with minimal n will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-312597