为什么这些Fortran 95循环方法的执行时间不同？

Question

我有一个用Fortran编写的矩阵操作示例程序，它使用列主系统来存储矩阵。这是否会导致两个数组操作的运行时间差异如此之大？如果是这样，有人可以解释一下为什么会发生这种情况，以及到底是什么导致了如此大的运行时间差异吗？

我正在使用Ubuntu 14.04和GNU Fortran 4.8.4。

代码：

program main
implicit none

integer :: i,j
real :: start, finish
real,dimension(256,256) :: arr1

!ROW format - put 0 to main diagonal
call cpu_time(start)
do i=1,255,1
    do j=1,255,1
        arr1(i,j)=0
    end do
end do
call cpu_time(finish)

write(*,100) 'Execution time arr(i,j) in seconds= ', (finish-start)
100 format (A,f12.9)

!COLUMN format - put 1 to main diagonal
call cpu_time(start)
do j=1,255,1
    do i=1,255,1
        arr1(i,j)=1
    end do
end do
call cpu_time(finish)

write(*,100) 'Execution time arr(j,i) in seconds = ', (finish-start)

end program 

编译:

gfortran main.f95 -o main 

输出：

Execution time arr(i,j) in seconds=  0.000736000
Execution time arr(j,i) in seconds =  0.000164000

第一种方法执行时间是第二种方法的4.5倍左右。

编辑：我更感兴趣的是知道为什么执行时间会有这么大的差异（在进行行主序时编译器、处理器或内存级别是否发生了异常等）。而不是简单地添加-o3标志或优化代码。这个问题优化七重循环有一个回答说列主序排序更好。为什么呢？

- 343_458

---

我的问题与这个问题不同。 我的问题中更新了“编辑”部分。 - 343_458

这是一个明智的问题，但了解您的基本理解或想要的答案深度将会很有帮助。当然，您可以进行关于缓存和访问模式的深入讨论，但同样，“数组元素顺序”可能已经足够满足您的需求。我无法确定您想要/需要哪种类型的回答。目前，您的第一个问题是“顺序是否重要？”，这表明需要一个非常高层次的答案，但后来您又说您已经理解它的重要性。 - francescalus

我对这背后的详细原因很感兴趣，就像你所说的与缓存有关。事实上，我刚刚在我的问题中更新了这个。 - 343_458

Answer 1

首先，你的测试存在强烈的偏见： 为了发现这种偏见，可以交换你正在测试的两个块的顺序，情况会开始改变。对于这样的测试，你需要：

1. 编写两个不同的程序，一个用于每种情况；
2. 运行每个程序多次并取平均时间；

您也可以选择根据您感兴趣的内容将步骤二替换为循环。

现在回到您的问题，我首先要提到的是，正如francescalus所提到的那样，这个问题过于宽泛。简单点说，计算机内存被组织成一个层次结构：

1. RAM；
2. 高速缓存（可以有许多级别，为简单起见，我们只考虑一级）；
3. 寄存器

任何层都有其优点和缺点：

1. RAM可以很大（千兆字节），但非常慢（约十纳秒，50至70）。
2. 高速缓存不是很大（几千字节到几兆字节），比RAM快（几纳秒0.5〜2.5）
3. 寄存器不大（仅十多个字节），但速度非常快。

有关更多信息，请参见此链接。我忽略了磁盘，这是另一种内存级别以及网络。

通常数据只从一级内存过渡到下一级内存：意味着从RAM到Cache，从Cache到RAM，从Cache到寄存器，从寄存器到Cache。 CPU仅在最快的寄存器上操作。因此，对于每个操作，数据都从RAM带到寄存器，并且在计算之后，它们被带回到RAM。噢不，不要这么快。让我们保持简单，假设CPU在字节上操作（如果您深入探究，会学习连续字节组成的词汇概念和页面概念，即连续单词组成的组）。

当您访问尚未在缓存中的字节时，会发生缓存错误，该字节首先从RAM到缓存，然后转到寄存器进行操作。当系统将该字节从RAM取出并放入缓存时，它一起获取了一组连续字节。因此，如果下一个操作是邻居，则无需去RAM。

现在，在您的程序中发生了什么，是Fortran按列存储数组，这意味着在内存中元素按此顺序存储：

a(1,1) a(2,1) a(3,1) ... a(M,1) a(1,2) a(2,2) a(3,2) ... a(M,2) ...

所以这个循环。

do j=1,255,1
    do i=1,255,1
        arr1(i,j)=1
    end do
end do

按照存储在内存中的顺序访问元素。RAM和缓存之间的传输次数减少到最小。

对于另一个循环

do i=1,255,1
    do j=1,255,1
        arr1(i,j)=1
    end do
end do

您只是没有按正确的顺序访问元素。例如，如果您的缓存只能容纳矩阵的一列以下，那么对于内部循环的任何迭代，系统都必须重新填充缓存。而且这不是很简单，为了重新填充缓存，系统将首先将在缓存中的数据复制回RAM（如果它们已被修改），这在这里是适用的情况。要查看此内容，请将矩阵增加到RAM可以处理的最大大小，您将看到不遵循存储逻辑意味着什么，间隙将增加。您可以逐步进行，1000x1000，然后是10000x10000等等。当您的缓存只能容纳一列或更少时，您将获得接近RAM和缓存访问时间之间因子的结果。请记住，超过10。

内存主题是计算机科学中许多课程的主题。我只想快速给您提供我所能给出的内容。

- innoSPG

Answer 2

为了处理数据，CPU需要将其从RAM读取到缓存中。读取单个字节与读取一些连续字节的时间几乎相同。

如果您的内部循环在非连续维度上，则CPU必须独立地从RAM读取和写入每个值。如果您的内部循环在连续维度上，则可以一次读取许多值，然后在其缓存中对它们进行操作。

- chw21