Strong I/O Lower Bounds for Binomial and FFT Computation Graphs
Strong I/O Lower Bounds for Binomial and FFT Computation Graphs
复制标题
二项式和 FFT 计算图的强 I/O 下界
DOI：
10.1007/978-3-642-22685-4_12
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
M. Zubair
中科院分区：
文献类型：
--
作者：
D. Ranjan;J. Savage;M. Zubair
大多数现代计算设备上的处理器具有多个级别的内存层次结构。为了在这些处理器上获得良好的性能，有必要设计算法，以最大程度地降低I/O流量，以使层次结构中的记忆较慢。在本文中，我们提出了一种新技术，即边界流技术，用于在两级内存层次结构中的问题的记忆流量复杂性得出下限。边界流技术依赖于识别与最少数量边界顶点相等的计算相对应的亚计算结构，这又与计算图的顶点等级参数有关。我们证明，该技术在内存层次结构架构上为众所周知的计算结构中的内存流量提供了更强的下限：二项式计算图和FFT计算图。
Processors on most of the modern computing devices have several levels of memory hierarchy. To obtain good performance on these processors it is necessary to design algorithms that minimize I/O traffic to slower memories in the hierarchy. In this paper, we propose a new technique, the boundary flow technique, for deriving lower bounds on the memory traffic complexity of problems in a two-level memory hierarchy architectures. The boundary flow technique relies on identifying sub-computation structure corresponding to equal computations with a minimum number of boundary vertices, which in turn is related to the vertex isoperimetric parameter of a computation graph. We demonstrate that this technique results in stronger lower bounds for memory traffic on memory hierarchy architectures for well-known computation structures: the binomial computation graphs and FFT computation graphs.