LogGP: Incorporating Long Messages into the LogP Model for Parallel Computation
Authors: Alexandrov, A.; Ionescu, M.F.; Schauser, K.E.; Scheiman, C.
Source: Journal of Parallel and Distributed Computing, Volume 44, Number 1, July 1997 , pp. 71-79(9)
Publisher: Academic Press
Abstract:We present a new model of parallel computation-the LogGP model-and use it to analyze a number of algorithms, most notably, the single node scatter (one-to-all personalized broadcast). The LogGP model is an extension of the LogP model for parallel computation which abstracts the communication of fixed-sized short messages through the use of four parameters: the communication latency (L), overhead (o), bandwidth (g), and the number of processors (P). As evidenced by experimental data, the LogP model can accurately predict communication performance when only short messages are sent (as on the CM-5). However, many existing parallel machines have special support for long messages and achieve a much higher bandwidth for long messages than for short messages (e.g., IBM SP-2, Paragon, Meiko CS-2, Ncube/2). We extend the basic LogP model with a linear model for long messages. This combination, which we call the LogGP model of parallel computation, has one additional parameter, G, which captures the bandwidth obtained forlong messages. Experimental data collected on the Meiko CS-2 shows that this simple extension of the LogP model can quite accurately predict communication performance for both short and long messages. This paper discusses algorithm design and analysis under the new model. We also examine, in more detail, the single node scatter problem under LogGP. We derive solutions for this problem which are qualitatively different from those obtained under the simpler LogP model, reflecting the importance of capturing long messages in a model.
Document Type: Research Article
Affiliations: Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, 93106
Publication date: July 1997