Using Space-filling Curves for Computation Reordering
Using Space-filling Curves for Computation Reordering
复制标题
使用空间填充曲线进行计算重新排序
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
J. Mellor
中科院分区：
文献类型：
--
作者：
G. Jin;J. Mellor
空间填充曲线已被广泛用于数学中，并将多维问题转化为一维形式。对于科学应用，沿太空填充曲线的订购数据或计算对于在平行系统分配或重组以利用内存层次结构时利用区域是有用的。在本文中，我们提出了一种有效的方法，用于枚举点或绘制沿空间填充曲线的点。我们引入了一个新的表规范，位置规范，用于映射到沿空间填充曲线的点。我们讨论如何将该框架用于重新排序计算。在三个现代微处理器平台上进行的实验表明，我们的算法沿曲线列出点的速度快72倍，并且比以前面向字节的，不具有曲线的曲线绘制到曲线上的绘制速度更快11倍。执行。
Space-filling curves have been widely used in mathematics and to transform multi-dimensional problems into one-dimensional forms. For scientific applications, ordering data or computation along spacefilling curves can be useful for exploiting locality when partitioning onto parallel systems or when restructuring to exploit memory hierarchy. In this paper, we present an efficient approach for enumerating points or mapping to points along space-filling curves. We introduce a new table specification, position specification, for mapping to points along space-filling curves. We discuss how this framework can be used for reordering computation. Experiments on three modern microprocessor based platforms show that our algorithm is up to a factor of 72 faster for enumerating points along a curve and up to a factor of 11 faster for mapping to points on the curve than a previous byte-oriented, non-recursive implementation.