Modeling communication in parallel algorithms: a fruitful interaction between theory and systems?
Modeling communication in parallel algorithms: a fruitful interaction between theory and systems?
复制标题
并行算法中的通信建模：理论与系统之间富有成效的交互？
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
Anoop Gupta
中科院分区：
文献类型：
--
作者：
J. Singh;E. Rothberg;Anoop Gupta
近年来，人们提出了几种并行体系结构的理论模型，以取代PRAM作为提供给算法设计者的模型。新模型的一个主要焦点是包括处理器间通信的成本，这在现代并行体系结构中越来越重要。我们认为对架构或系统中的通信成本进行建模只是问题的一部分。另一部分（通常要困难得多）是对算法本身的通信属性进行建模，它为体系结构模型提供必要的输入，以确定总体复杂性。在此背景下，我们在本文中提出了三个主要观点：(i)不考虑其与复制的关系来描述传播是不完整的。我们提出了一种用算法的工作集层次来描述通信-复制关系的方法。（ii）固有通信和通信-复制关系都很难在许多实际应用中至关重要的不规则动态计算中建模。我们举一些例子来说明这种困难。（iii）我们相信，在这项工作中，可以从计算机系统社区获得实质性的杠杆作用，它可以提供从抽象到详细的模拟和分析工具的层次结构，以满足算法设计者的需求。我们提出了一套初步的模拟工具，并讨论了未来可能对这套工具进行的改进。
Recently, several theoretical models of parallel architectures have been proposed to replace the PRAM as the model that is presented to an algorithm designer. A primary focus of the new models is to include the cost of interprocessor communication, which is increasingly important in modern parallel architectures. We argue that modeling the communication costs in the architecture or system is only one part of the problem. The other, and usually much more difficult, part is modeling the communication properties of the algorithm itself, which provides necessary inputs into the architectural model to determine overall complexity. In this context, we make three main points in this paper: (i) It is incomplete to describe communication without regard to its relationship with replication. We propose a description of the communication-replication relationship in terms of the working set hierarchy of an algorithm. (ii) Both inherent communication and the communication-replication relationship can be very difficult to model in irregular, dynamic computations that are crucial in many real-world applications. We present some examples that demonstrate this difficulty. (iii) We believe that substantial leverage can be obtained in this effort from the computer systems community, which can provide a hierarchy of simulation and profiling tools—from abstract to detailed—tailored to the needs of the algorithm designers. We propose an initial set of simulation tools, and we discuss possible future refinements to this set.