为什么这些 Fortran 95 循环方法的执行时间不同？
Why the execution time is different for these fortran 95 loop methodologies?
我有一个用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 标志或优化代码。这个问题 optimization of a seven do cycle 有一个答案说列主要排序更好。为什么这样？
要处理数据，CPU 需要将数据从 RAM 读入缓存。读取单个字节所需的时间与读取大量连续字节所需的时间几乎相同。
如果您的内部循环在非连续维度上，CPU 必须独立地从 RAM 读取和写入每个单值。如果你的内循环在连续维度上，它可以一次读取很多值，然后在它的缓存中对它们进行操作。
首先，你的测试有很大的偏差：
要查看偏差，请颠倒您正在测试的两个块的顺序，事情将开始发生变化。对于这样的测试，您必须：
- 编写两个不同的程序，每种情况一个；
- 运行每个程序多次，取平均时间；
您也可以根据自己的兴趣，选择用循环代替第二步。
现在，回到您的问题上，我首先要提一下，这个问题太宽泛了，就像 francescalus 提到的那样。简而言之；计算机内存组织成层次结构：
- 内存；
- 缓存（可以有很多层，为了简单我们考虑一层）；
- 注册
任何级别都有其优点和缺点：
- RAM 可以很大（千兆字节），但速度很慢（大约几十纳秒，50 到 70）。
- 缓存不是很大（几千到几兆字节），比 RAM 快（几纳秒 0.5 到 2.5）
- 寄存器不大（只有几十个字节），速度很快
有关详细信息，请参见示例 this link。我忽略了另一层内存和网络的磁盘。
数据通常只从一级内存传输到下一级：即从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个。
内存是许多计算机科学课程的主题。我只想给你我能很快给的东西。
我有一个用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 标志或优化代码。这个问题 optimization of a seven do cycle 有一个答案说列主要排序更好。为什么这样？
要处理数据，CPU 需要将数据从 RAM 读入缓存。读取单个字节所需的时间与读取大量连续字节所需的时间几乎相同。
如果您的内部循环在非连续维度上，CPU 必须独立地从 RAM 读取和写入每个单值。如果你的内循环在连续维度上，它可以一次读取很多值，然后在它的缓存中对它们进行操作。
首先，你的测试有很大的偏差： 要查看偏差，请颠倒您正在测试的两个块的顺序，事情将开始发生变化。对于这样的测试，您必须：
- 编写两个不同的程序，每种情况一个；
- 运行每个程序多次，取平均时间；
您也可以根据自己的兴趣，选择用循环代替第二步。
现在，回到您的问题上，我首先要提一下，这个问题太宽泛了，就像 francescalus 提到的那样。简而言之；计算机内存组织成层次结构：
- 内存；
- 缓存（可以有很多层，为了简单我们考虑一层）；
- 注册
任何级别都有其优点和缺点：
- RAM 可以很大（千兆字节），但速度很慢（大约几十纳秒，50 到 70）。
- 缓存不是很大（几千到几兆字节），比 RAM 快（几纳秒 0.5 到 2.5）
- 寄存器不大（只有几十个字节），速度很快
有关详细信息，请参见示例 this link。我忽略了另一层内存和网络的磁盘。
数据通常只从一级内存传输到下一级：即从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个。
内存是许多计算机科学课程的主题。我只想给你我能很快给的东西。