LogGP: Incorporating Long Messages into the LogP Model for Parallel Computation
LogGP: Incorporating Long Messages into the LogP Model for Parallel Computation
复制标题
DOI：
10.1006/jpdc.1997.1346
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Albert D. Alexandrov;M. Ionescu;K. Schauser;C. Scheiman
中科院分区：
文献类型：
--
作者：
Albert D. Alexandrov;M. Ionescu;K. Schauser;C. Scheiman
我们提出了一种新的并行计算模型的LogGP模型，并使用它来分析一些算法，最值得注意的是，单节点分散（一对所有个性化广播）。LogGP模型是用于并行计算的LogP模型的扩展，其通过使用四个参数来抽象固定大小的短消息的通信：通信延迟（L）、开销（o）、带宽（g）和处理器数量（P）。实验数据表明，LogP模型可以准确预测只有短消息发送时的通信性能（如CM-5）。然而，许多现有的并行机具有对长消息的特殊支持，并且对于长消息实现比对于短消息高得多的带宽（例如，IBM SP-2，Paragon，Meiko CS-2，Ncube/ 2）。我们扩展了基本的LogP模型与长消息的线性模型。这种组合，我们称之为LogGP并行计算模型，有一个额外的参数，G，它捕获长消息获得的带宽。在Meiko CS-2上收集的实验数据表明，LogP模型的这种简单扩展可以相当准确地预测短消息和长消息的通信性能。本文讨论了新模型下的算法设计和分析。我们还将更详细地研究LogGP下的单节点分散问题。我们推导出这个问题的解决方案，这是定性不同的那些下得到的更简单的LogP模型，反映了捕捉长消息的模型中的重要性。© 1997学术出版社
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 for long 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. © 1997 Academic Press