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

我有一个示例程序在fortran中执行矩阵操作，该操作具有列主要系统来存储矩阵。在两个数组操作中，这是否会在运行时造成显着差异？如果是这样，有人可以解释为什么会发生这种情况，究竟是什么导致了如此大的运行时差异？为什么这些fortran 95循环方法的执行时间不同？

我在GNU Fortran 4.8.4上使用了Ubuntu 14.04。

代码：

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标记或优化代码。这个问题optimization of a seven do cycle有一个答案，说列主要顺序更好。为什么这样？

来源

2015-08-08 343_458

我的问题不同于这个问题的地址。在我的问题中更新了'编辑'部分。 –

这是一个明智的问题，但是知道你有什么基本的理解或者你想要的深度是有帮助的。当然，您可以深入讨论缓存和访问模式，但同样，“数组元素顺序”可能足以满足您的需求。我无法分辨你想要什么或需要什么。目前你的第一个问题是“这个订单重要吗？”这表明需要非常高水平的答案，但后来你说你明白了。 – francescalus

我有兴趣了解背后的详细原因，正如你所说的那样，与缓存相关。事实上，我只是在我的问题中更新了这一点。 –

首先，你的测试是强烈的偏见：要看到偏差，颠倒你正在测试的两个块的顺序，事情会开始改变。对于这样的测试，你必须：

写两个不同的程序，每个案例一个;
多次运行每个程序并取平均时间;

您也可以选择取决于你所感兴趣的一个循环，以取代两个步骤。

现在，回到你的关心，我首先要提及的是，问题太宽泛，francescalus提及。简短地讲述故事;计算机内存被组织成一个层次结构：

RAM;缓存（可以有很多层次，为了简单起见，我们考虑一个层次）;
寄存器

在任何水平都有其优点和缺点：

该RAM可以是大的（千兆字节），但非常缓慢（约几十纳米秒，50至70）。
缓存不是很大（几千到几兆字节），比RAM快（几纳秒0.5到2.5）
寄存器不大（只有几十字节），非常快。

参见例如this link以获得更多信息。我忽略了另一个级别的内存以及网络的磁盘。

数据通常只从一个内存级别传输到下一级别：从RAM到Cache，从缓存到RAM，从Cache到Register，从寄存器到缓存。 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等等。当你的缓存只能保存一列或更少的时候，你会得到一个因子来关闭内存访问时间和cahe之间的因子。请记住，超过10个。

内存的主题是计算机科学中许多课程的主题。我只想给你提供我能够迅速给予的东西。

来源

2015-08-09 04:11:58 innoSPG

要处理数据，CPU需要将其从RAM读取到其缓存中。它需要大量的时间来读取单个字节，因为它可以读取相当多的连续字节。

如果你的内循环超过非连续维度，那么CPU必须独立地读写每个单独的值并写入RAM。如果你的内部循环超过了连续的维度，它可以一次读取很多值，然后在它的缓存中对它们进行操作。

来源

2015-08-09 03:10:28 chw21

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

回答

相关问题