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

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

作　　者：侯昉[1] 陆寄远[1] 黄承慧[1] 

机构地区：[1]广东金融学院计算机科学与技术系,广东广州510521

出　　处：《计算机工程与科学》2016年第5期877-884,共8页Computer Engineering & Science

基　　金：广东省自然科学基金(2014A030313662)

摘　　要：多维数据以线性形式在存储系统中进行访问操作,二维及以上维度空间中的相邻节点被不同的映射算法映射到一维空间的不相邻位置。高维空间中进行相邻节点访问时,其一维存储映射位置有着不同的访问距离和访问延迟。提出了基于空间填充曲线Z-Ordering的存储映射方法及其访问距离的度量指标,并和常规优先算法进行了对比,发现能更好地将高维相邻的数据节点簇集到一维存储位置,加强了局部性。调整缓存空间中用于预取的空间大小,可以利用增强的局部性,提高了缓存命中率。实验结果表明,改善了多维数据的访问速度,优化了系统性能。Multidimensional data are processed and accessed in the linear form. Adjacent nodes m 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 pre- fetching space in a fixed cache space maximizes this strength, therefore, the cache hit rate is increased and its system performance is improved.

关 键 词：多维数据 存储映射 缓存 预取 命中率 

分 类 号：TP331[自动化与计算机技术—计算机系统结构]