如何以可重现的方式比较两种算法的运行时间

计算科学 正则 表现 再现性
2021-12-15 17:54:26

我正在用两种不同的算法解决一个相对简单的问题：一种使用蛮力，另一种是优化的。由于各种原因，我实际上无法在此处显示代码，但我认为这并不重要。

以下是我目前比较这两种算法的方式（我使用 Fortran）：

CALL CPU_TIME(t1)
DO pp = 1,10000
    **Algorithm_1**
END DO
CALL CPU_TIME(t2)

CALL CPU_TIME(t3)
DO pp = 1,10000
    **Algorithm_2**
END DO
CALL CPU_TIME(t4)

PRINT*, "Algorithm 1 time = ", (t2-t1)/(pp-1)
PRINT*, "Algorithm 2 time = ", (t4-t3)/(pp-1)

这让我对加速因素有一个粗略的了解。但我的问题是它只给出了一个粗略的想法。

对于一种情况，平均加速因子约为 460。有时我得到 534，有时是 380。这是通过连续多次运行相同的可执行文件获得的。这是最极端的情况；我通常得到 5 % 的范围，这仍然困扰着我。±

有没有一种比较两种算法的稳健方法？还是预期的结果存在差异？

1个回答

要进行更可靠的比较（在 linux 上），您可以：

1) 在 Intel CPU 上，turbo 会超频您的 CPU。这是由 CPU 的温度控制的，因此它在一次运行中的表现可能会有所不同。在 Linux 上，您可以按如下方式阻止 CPU 的频率。例如，对于 2.4GHz：

  echo 1 > /sys/module/processor/parameters/ignore_ppc

  for x in /sys/devices/system/cpu/cpu[0-3]/cpufreq/;do 
    echo 2400000 > $x/scaling_max_freq
  done

2) 只要​​有空闲内存，linux 就会缓存你最后的 I/O。如果您的程序需要分配大量内存，第一次分配将花费一些时间，因为它会清空 I/O 缓存以提供一些空闲内存。为了使您的分配时间更可预测，清空您的 I/O 缓存

echo 3 > /proc/sys/vm/drop_caches

3) 您的进程可以从一个 CPU 核心迁移到另一个。在每次迁移时，您都会丢失 L1 和 L2 缓存，因此您会遇到更多的缓存未命中。此外，迁移需要一些时间。要消除此开销，请将您的进程绑定到 CPU 内核：

export OMP_PROC_BIND=true
taskset -c 0-3 ./a.out

4）在测量CPU时间之前，先做一点热身

5）也许算法1在算法2之前运行得更快，反之亦然。为避免这种偏差，您可以交错算法 1 和 2 的测量。

  ! DO ALL POSSIBLE INITIALIZATION HERE

  NREP=10000
  NLOOP=100

  time1 = 0.d0
  time2 = 0.d0

  DO k=1,NLOOP

    ! WARM UP
    DO pp = 1,NREP/10
        **Algorithm_1**
    END DO

    !MEASURE 1
    CALL CPU_TIME(t1)
    DO pp = 1,NREP
        **Algorithm_1**
    END DO
    CALL CPU_TIME(t2)

    time1 = time1 + t2-t1


    ! WARM UP
    DO pp = 1,NREP/10
        **Algorithm_2**
    END DO   

    ! MEASURE 2
    CALL CPU_TIME(t3)
    DO pp = 1,NREP
        **Algorithm_2**
    END DO
    CALL CPU_TIME(t4)

    time2 = time2 + t4-t3

  ENDDO

  PRINT*, "Algorithm 1 time = ", time1/(dble(NREP)*dble(NLOOP))
  PRINT*, "Algorithm 2 time = ", time2/(dble(NREP)*dble(NLOOP))

6）确保您是机器上的唯一用户

7) 如果您使用的是台式计算机（firefox 等），请关闭所有其他后台应用程序

8) 关闭网络

9) 对于多线程应用程序，确保您的线程绑定到不同的物理 CPU 内核（签入/proc/cpuinfo）

其它你可能感兴趣的问题
上一篇四阶龙格-库塔是的'= yy′=y 下一篇有限元方法的数学基础书籍