摘要： 现代计算机一直沿用传统的线性数据布局模式,该模式允许对使用行主序模式存储的二维矩阵进行高效的行优先数据访问,但是增加了高效执行列优先数据访问的复杂性,造成列优先访问的空间局部性较差。改善列优先数据访存效率的常见解决方案是对原始矩阵进行预先转置操作,将列优先访问的复杂性集中在一次矩阵转置运算中,然而矩阵转置不仅会引入额外的数据传输操作,而且会消耗额外的存储空间用于存储转置后的矩阵。为了在不引入额外开销的情况下使行优先与列优先数据访问具有同样高效的访存效率,提出一种新颖的交错映射(IM)数据布局,同时在不改变便笺式存储器(SPM)内部结构的基础上,在SPM的输入和输出(I/O)接口处添加循环移位单元和译码单元2个新组件,实现交错映射数据布局并定制访存指令,使程序员可通过定制的访存指令充分利用该数据布局。实验结果表明,应用交错映射数据布局的SPM在仅额外增加了1.73%面积开销的情况下获得了1.4倍的加速。

关键词: 矩阵转置, 单指令多数据, 便笺式存储器, 数据布局, 静态随机存储器

Abstract: Modern computers adhere to the classical linear data layout mode, which enables efficient row-major access to Two-Dimensional (2D) matrices stored in the row-major order. However, this complicates the efficient execution of column-major data access, thus resulting in unsatisfactory spatial locality. The efficiency of column-major data access is typically improved by pre-transposing the original matrix and concentrating the complexity of column-major access into a single matrix transposition operation. Nevertheless, matrix transposition introduces additional data transfer operations and requires additional memory to store the transposed matrix. To achieve equally efficient access to row-major and column-major data without introducing additional overhead, a novel Interleaved Mapping (IM) data layout is proposed. Without altering the internal structure of the Scratch Pad Memory (SPM), this layout is implemented by adding two new components—a Cyclic Shift Unit and a Decoder Unit—at the Input and Output (I/O) interfaces of the SPM. Additionally, customized memory access instructions are developed, thus enabling programmers to leverage the data layout fully via these instructions. Experimental results show that the SPM utilizing the IM data layout increases the speedup by 1.4 times while incurring 1.73% additional area overhead.

Key words: matrix transposition, Single Instruction Multiple Data(SIMD), Scratch Pad Memory(SPM), data layout, Static Random Access Memory(SRAM)

中图分类号: 

• TP302.7