Tradeoffs in message passing and shared memory implementations of a standard cell router

Margaret Martonosi, Anoop Gupta

Research output: Contribution to journalConference articlepeer-review

12 Scopus citations


Consideration is given to two implementations of the LocusRoute standard cell routing program. One implementation uses a message-passing approach, where global data distributed among the processes are kept consistent through explicit updates using messages. The other implementation uses a shared-memory approach and relies on underlying coherence mechanisms, such as hardware cache coherence protocols, to keep the data consistent. The performances of these two mappings are discussed in terms of the network traffic, execution time, and solution quality. The authors explore a number of update strategies for the data structures in the message-passing implementation, classifying the methods according to whether they are sender initiated or receiver initiated and whether they are blocking or nonblocking. They show that these explicit methods for interprocessor updates can reduce network traffic to as little as 1% of the traffic required for the shared-memory approach. Also, the authors examine methods for task assignment which take advantage of locality. While these methods can improve solution quality and reduce the need for interprocessor communication in either paradigm, task assignment based strictly on locality can lead to load imbalances between processors. The effect of increasing the number of processors on solution quality, execution time, and network traffic is discussed.

Original languageEnglish (US)
Pages (from-to)88-96
Number of pages9
JournalProceedings of the International Conference on Parallel Processing
StatePublished - Dec 1 1989
Externally publishedYes
EventProceedings of the 1989 International Conference on Parallel Processing - University Park, PA, USA
Duration: Aug 8 1989Aug 12 1989

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture


Dive into the research topics of 'Tradeoffs in message passing and shared memory implementations of a standard cell router'. Together they form a unique fingerprint.

Cite this