Fortran广度优先搜索运行缓慢

Question

背景：我编写了一个Fortran子程序，它从未加权的有向网络的邻接矩阵计算最短路径长度矩阵。该子程序使用广度优先搜索算法。最短路径长度矩阵的对角线元素是最短环路长度。

我也在MATLAB中实现了这个算法。我迁移到Fortran是为了减少运行时间(请注意，我是Fortran的新手)。然而，此子程序在MATLAB中的运行速度略快于在Fortran实现中的运行时间(对于相同的~1000节点网络，在MATLAB中约44秒，在Fortran中约46秒)。这对我来说没有意义，因为我的理解是Fortran对于基于循环的操作应该更快。我的其他一些子程序在Fortran中的速度要快1-2个数量级。

我在OSX 10.10.2上编译，安装了最新的gfortran二进制文件，没有优化标志。(打开优化标志实际上似乎会进一步降低代码速度。)

问题：有人能看到我的fortan代码中可能导致其运行效率低下的缺陷吗？(对于Fortran新手来说，任何其他通用提示都将不胜感激)。或者，有没有更快的算法来完成这项任务？

代码：

subroutine spl(a,splmat)
implicit none
! Input: Adjacency matrix a
logical, intent(in) :: a(:,:)
! Output: Shortest path length matrix
integer, dimension (:,:), allocatable :: splmat
integer, dimension (:), allocatable :: stk
! Variables: nnodes (size of network); s (source node); r (read ptr);
! w (write pointer) ; d (distance from s to node n), n (the node
! pointed to by the value of the stack at r); j (loop variable);
integer :: nnodes,s,r,w,d,n,j
nnodes = size(a,1)
allocate(splmat(nnodes,nnodes))
splmat = 0
allocate (stk(nnodes))
! Outer loop over each node
do s = 1,nnodes
stk = 0
stk(1) = s
r = 1
w = 2
! Inner loop
do while (r/=w)
n = stk(r)
r = r+1
d = splmat(s,n)
do j=1,nnodes
if (a(n,j).and.(splmat(s,j)==0)) then
splmat(s,j) = d+1
stk(w) = j
w = w+1
end if
end do
end do
end do
end subroutine spl

Answer 1

我不知道您使用的算法，但我立即注意到一个非常简单的问题是，为了在Fortran中获得最佳性能，您的索引顺序错误。

我的意思是，这通常是不好的：

do i = 1, m
do j = 1, n
! Do something with a(i,j)
end do
end do

而这要好得多：

do j = 1, n
do i = 1, m
! Do something with a(i,j)
end do
end do

对于小问题，通常没有太大区别(除非在某些情况下，您严重依赖SIMD矢量化来提高性能)。然而，对于更大的问题，缓存使用的效率可能会有很大的差异。