陈海燕，刘 胜，吴健虢

(国防科技大学 计算机学院， 湖南 长沙 410073)

为充分开发微处理器的数据并行性、以较低的硬件代价和功耗实现密集型数据处理，获得较高的峰值运算性能，单指令多数据流(Single Instruction Multiple Data,SIMD)技术成为微处理器体系结构发展的一个重要扩展。对于地址连续或等距跨步等规则应用的数据访存模式，一般的SIMD结构处理器往往都能提供充足的访存带宽，得到较理想的峰值运算性能；但在处理不规则应用时，其访存带宽性能急剧下降，主要原因是不规则应用的访存模式复杂、无规律，数据的空间局部性差，目前的SIMD架构微处理器不能很好支持。如何高效支持不规则应用访存以提高通用性能成为SIMD微处理器设计中面临的一个重要问题。

科学计算和工程应用中存在大量的不规则数据访存，例如稀疏矩阵计算、图像边缘检测和语音识别等[1-2]。有学者总结出十余类基本的并行计算模式，其中一半以上都是不规则的[3]，即这些并行计算模式中存在大量的不规则数据访存，数据访存模式随机无规律，时间和空间局部性差等[4]。随着SIMD技术的不断发展，片上集成的按SIMD方式操作的运算单元越来越多，需要越来越宽的SIMD访存带宽支持，而不规则访存潜在的访问冲突降低了处理器的实际数据带宽，增加了访存延时，降低了数据访存效率[5-6]。支持单指令多线程(Single Instruction Multiple Threads, SIMT)的向量访存仅支持SIMD结构中每个运算单元访问各自对应的数据地址空间，不能共享整个数据存储器，限制了其应用范围。……