多维数据的Z-Ordering存储映射算法及其缓存调度优化

多维数据以线性形式在存储系统中进行访问操作,二维及以上维度空间中的相邻节点被不同的映射算法映射到一维空间的不相邻位置。高维空间中进行相邻节点访问时,其一维存储映射位置有着不同的访问距离和访问延迟。提出了基于空间填充曲线Z-Ordering的存储映射方法及其访问距离的度量指标,并和常规优先算法进行了对比,发现能更好地将高维相邻的数据节点簇集到一维存储位置,加强了局部性。调整缓存空间中用于预取的空间大小,可以利用增强的局部性,提高了缓存命中率。实验结果表明,改善了多维数据的访问速度,优化了系统性能。

A Z-ordering storage mapping algorithm and cache optimization for multidimensional data

Multidimensional data are processed and accessed in the linear form. Adjacent nodes in 2 dimension or higher space are mapped to non adjacent addresses in 1 dimensional storage hardware. These variant address distances lead to variant access latencies. We propose a storage mapping algorithm based on Z Ordering function, and several indicators of this algorithm are presented and calculated, which are compared with the ordinary row major ordering mapping method. The proposed algorithm manifests a stronger locality to aggregate the adjacent nodes in a small linear scope. An increscent prefetching space in a fixed cache space maximizes this strength, therefore, the cache hit rate is increased and its system performance is improved.