Report ID
1995-09
Report Authors
Albert Alexandrov, Mihai F. Ionescu, Klaus E. Schauser, andChris Scheiman
Report Date
Abstract
We present a new model of parallel computation---the LogGP model---and use itto 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 computationwhich abstracts the communication of fixed-sized short messages through the useof four parameters: the communication latency (L), overhead (o), bandwidth(g), and the number of processors (P). As evidenced by experimental data, theLogP model can accurately predict communication performance when only shortmessages are sent (as on the CM-5). However, many existing parallel machineshave special support for long messages and achieve a much higher bandwidth forlong messages compared to 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. Thiscombination, which we call the LogGP model of parallel computation, has oneadditional parameter, G, which captures the bandwidth obtained for longmessages. Experimental data collected on the Meiko CS-2 shows that this simpleextension of the LogP model can quite accurately predict communicationperformance for both short and long messages. This paper discusses algorithmdesign and analysis under the new model, examining the all-to-all remap, FFT,and radix sort.We also examine, in more detail, the single node scatter problem. We derivesolutions for this problem and prove their optimality under the LogGP model.These solutions are qualitatively different from those obtained under thesimpler LogP model, reflecting the importance of capturing long messages in amodel.
Document
1995-09.ps345.59 KB