NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Parallel simulated annealing algorithms for cell placement on hypercube multiprocessorsTwo parallel algorithms for standard cell placement using simulated annealing are developed to run on distributed-memory message-passing hypercube multiprocessors. The cells can be mapped in a two-dimensional area of a chip onto processors in an n-dimensional hypercube in two ways, such that both small and large cell exchange and displacement moves can be applied. The computation of the cost function in parallel among all the processors in the hypercube is described, along with a distributed data structure that needs to be stored in the hypercube to support the parallel cost evaluation. A novel tree broadcasting strategy is used extensively for updating cell locations in the parallel environment. A dynamic parallel annealing schedule estimates the errors due to interacting parallel moves and adapts the rate of synchronization automatically. Two novel approaches in controlling error in parallel algorithms are described: heuristic cell coloring and adaptive sequence control.
Document ID
19900047409
Document Type
Reprint (Version printed in journal)
External Source(s)
Authors
Banerjee, Prithviraj (Illinois, University Urbana, United States)
Jones, Mark Howard (AT&T Bell Laboratories Naperville, IL, United States)
Sargent, Jeff S. (Incredible Technologies Arlington Heights, IL, United States)
Date Acquired
August 14, 2013
Publication Date
January 1, 1990
Publication Information
Publication: IEEE Transactions on Parallel and Distributed Systems
Volume: 1
ISSN: 1045-9219
Subject Category
COMPUTER PROGRAMMING AND SOFTWARE
Funding Number(s)
CONTRACT_GRANT: NAG1-613
CONTRACT_GRANT: NSF MIP-86-57563
Distribution Limits
Public
Copyright
Other