我正在用我自己的 L-BFGS(用 c++ 实现)解决数值优化问题。该问题有优化参数。
为了找到目标函数梯度,我通过使用 FFTW3 库以双精度进行离散傅里叶变换,我所有的其他计算/变量也是双精度的。
现在,问题在于,在初始条件和所有参数相同的情况下,算法有时会以次迭代收敛,有时会以次迭代收敛。
- 这种非确定性行为是否是由累积浮点错误(或 FFTW 错误)引起的?
- 或者这是否意味着我的代码有一个错误,我可能在某个地方访问未分配的内存(或其他导致非确定性行为的错误)?
我正在用我自己的 L-BFGS(用 c++ 实现)解决数值优化问题。该问题有优化参数。
为了找到目标函数梯度,我通过使用 FFTW3 库以双精度进行离散傅里叶变换,我所有的其他计算/变量也是双精度的。
现在,问题在于,在初始条件和所有参数相同的情况下,算法有时会以次迭代收敛,有时会以次迭代收敛。
在不同的运行中计算中的不可重现行为可能涉及多种机制,有时是混合的。当对大量数据(例如逆 3D 断层扫描)进行迭代计算时,它们可能特别敏感。
x=a+b
不同于x=b+a
(非交换性),x=a+b+c+d
)时不会给出相同的结果。x=(a+b)+(c+d)
x=(a+c)+(b+d)
不确定性方面可能主要来自第四种类型,因为从一个运行到另一个运行,可以执行不同的集合或不同的分组。
[编辑] 专门针对 FFTW3,文档说:
问题 3.8。FFTW 在运行之间给出不同的结果
如果您使用 FFTW_MEASURE 或 FFTW_PATIENT 模式,则 FFTW 采用的算法不是确定性的:它取决于运行时性能测量。这将导致每次运行的结果略有不同。但是,差异应该很小,大约在浮点精度上,因此对大多数应用程序应该没有实际影响。但是,如果您使用已保存的计划(智慧)或 FFTW_ESTIMATE 模式,则该算法是确定性的,并且运行之间的结果应该相同。
例如,在Not So Fast - The Hacker Factor Blog中对此进行了讨论
一些快捷方式非常快但不确定
这可以在您的情况下进行检查。
一些快速来源:
ScaLAPACK 和 LAPACK 之间的一个重要区别是并行计算环境(可能由处理器的异构集合组成)引入了 LAPACK 运行的串行环境中未发现的可能错误的新来源。这些错误确实会影响任何使用浮点运算的并行算法。
可重复性,即从同一程序的多次运行中获得按位相同的浮点结果,是许多用户在许多代码中进行调试或正确性检查时所依赖的属性1。然而,并行计算资源的动态调度和浮点非关联性的结合,使得即使对于简单的归约操作(例如并行计算数字向量的总和),实现可重复性也是一个挑战
FFTW 包含一些适应性,可以在您的硬件上选择最快的算法。我不是 FFTW 内部的专家,但这个库似乎不太可能导致您观察到的巨大差异,特别是因为它被广泛使用。因此我建议:
尝试使用尽可能多的运行时错误检查进行编译。例如,使用gfortran
标志-fcheck=all
在调试时会非常有帮助。不幸的是g++
,似乎没有提供这样的检查,尽管-Wall -Wextra
有时会有所帮助。如果可用,请尝试不同的编译器。
使用类似的工具运行您的程序valgrind
,可能会减少问题大小,以找出未分配、未初始化或未释放的内存。
您没有提及您的代码是否并行运行,如果是这种情况,那么并行负载平衡可能是非确定性行为的来源。