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

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.