论文标题
空间计算机：节能平行计算的模型
The spatial computer: A model for energy-efficient parallel computation
论文作者
论文摘要
我们提出了一种适用于空间体系结构的新的平行计算模型，用于通信的能量在很大程度上取决于通信处理器的距离。在我们的模型中，处理器在概念上的二维网格上有位置，其距离决定了他们的沟通成本。特别是，我们介绍了空间计算的能源成本，该计算衡量了所有消息的总距离，并研究了通信深度，该沟通的深度衡量了一条消息链的最多啤酒花。我们显示了许多基础问题的匹配能量下限和上限，包括排序，中值选择和矩阵乘法。我们的模型不取决于输入形状和大小以外的任何参数，从而简化了算法分析。我们还展示了如何模拟模型中的婴儿车算法以及如何为更复杂的模型获得结果，该模型引入了处理器的本地记忆的大小作为参数。
We present a new parallel model of computation suitable for spatial architectures, for which the energy used for communication heavily depends on the distance of the communicating processors. In our model, processors have locations on a conceptual two-dimensional grid, and their distance therein determines their communication cost. In particular, we introduce the energy cost of a spatial computation, which measures the total distance traveled by all messages, and study the depth of communication, which measures the largest number of hops of a chain of messages. We show matching energy lower- and upper bounds for many foundational problems, including sorting, median selection, and matrix multiplication. Our model does not depend on any parameters other than the input shape and size, simplifying algorithm analysis. We also show how to simulate PRAM algorithms in our model and how to obtain results for a more complex model that introduces the size of the local memories of the processors as a parameter.
