高效的访问矩阵列

高效的访问问题：我需要访问一个大矩阵（大于2000x2000）列明智，我的算法需要1行通过和1列通过。行传递对于内存效率（高速缓存未命中）是正确的，但是如何减少列通过中的高速缓存未命中？我需要效率。高效的访问矩阵列

我的嘛我是这样的：声明ñ局部变量（根据内存读取大小），

int a1, a2, a3, a4; for (int j = 0 ; j < DIM_Y ; j+=4) for (int i = 0 ; i < DIM_X ; i++) a1 = matrix[i][j]; ... ; a4 = matrix[i][j+4]; // make the column processing on the 4 variables.

这是一个在C或C++，和数组或int或字符。

欢迎提出任何建议和意见。

谢谢。

来源

2013-02-02 user1479498

你在用什么语言？请相应地标记问题。 – ja72

矩阵类型是什么？很容易假设它是一个二维int数组，但也可能是一个int数组指针等。 – jimhark

存储2D矩阵的有效方式，是使用C样式阵列是这样的：

| a11 a12 a13 | 
| a21 a22 a23 | -> memory: [a11,a12,a13,a21,a22,a23,a31,a32,a33] 
| a31 a32 a33 | 

Element(i,j) = memory[N_COL*i+j]

其中i是从0开始行号索引，和j列号索引也从0开始，和N_COL的列数。

希望编译器/ jit将所有的值按顺序放在内存中以便快速访问。通常你试图欺骗编译器的次数越多（就像手动循环展开一样），你越是在性能上受到伤害。编写干净的代码并让编译器完成它的工作。

来源

2013-02-02 21:58:11 ja72

如果N_COL在编译时不知道，那么这是一个好方法，否则C支持二维数组直接使用（在原始问题中明显使用）。它们效率不低（尽管在编译时你必须知道除了最后一个维度外的所有维度）。 – jimhark

嗨Ja72，谢谢，但我的输入矩阵，它来自另一个应用程序，并转换为一个数组第一将不会记忆效率高，第二不会让它更快，元素在N_COL距离将有相同的缓存缺失坏处。 – user1479498

两种基本技术适用：

1）循环阻断

代替

for (j=0;j<2000;j++) 
    for (i=0;i<2000;i++) 
    process_element(i,j);

使用

for (j=0;j<2000;j+=8) 
    for (i=0;i<2000;i+=8) 
    process_block_of_8x8(i,j);

2）非动力2行步幅（例如8192字节+ 64） - 必要时填充

在这种情况下，row [i] .. row [i + 7]不会为同一高速缓存行作战

数据应该位于手动计算的填充区的连续内存区域中。

来源

2013-02-04 10:41:17

这不会给出相同数量的缓存未命中，除非矩阵以块方式存储。 – user877329

高效的访问矩阵列

回答

相关问题