An Empirical Study of Message-Passing Overhead

Conventional wisdom holds that message-passing is orders of magnitude more expensive than shared memory for communication between parallel processes. Differences in the speed of underlying hardware mechanisms fail to account for a substantial portion of the performance gap. The remainder is generally attributed to the "inevitable cost" of higher-level semantics, but a deeper understanding of the factors that contribute to messge-passing overhead has not been forthcoming. In this paper we provide a detailed performance analysis of one message-passing system: the implementation for the BBN Butterfly Parallel Processor of the LYNX distributed programming language. The case study includes a description of the implementation, an explanation of optimizations employed to improve its performance, and a detailed breakdown of remaining costs. The data provide a direct measure of the expense of individual features in LYNX. They also provide insight into the likely costs of other message-passing systems, both present and future. Lessons gained from our experience should be of use to other researchers in performing similar studies