计算科学 - 估计运行串行/并行代码的时间 - 吾爱随笔录

假设我正在运行一个迭代方法，我粗略估计了它需要多少次迭代，如何最好地估计它将连续运行的时间？

例如，如果我有共轭梯度（对于 Ax=b），如果我知道矩阵维度，我如何估计它将运行多长时间？

具体来说，我想问：

可以通过忽略缓存和编译器优化来进行粗略的计算，但有没有办法解释它们？当然，对其中的每一个都进行解释是不可能的，但至少是重要的。我对我的另一个问题上发布的分析很感兴趣，并希望能够找出其他算法的估计值，但有更严格的界限。
您如何找出优化运营的成本？例如，MatVecs 是 $O(N^2)$ . 在计算 BLASDGEMV时，您假设什么前导常数？

3. 既然我知道它在串行模式下运行的时间，我如何估计并行模式下的时间？我研究了阿姆达尔定律，但我不确定如何将它用于迭代方法。 已回答

PS：在线PDF（或任何参考资料）以了解更多信息会很棒！

更新：为了解决以 DGEMV 为瓶颈的 10000x10000 CG 问题，我执行了以下操作：我将大小从 2k x 2k 到 19k x 19k 的矩阵绘制为时间（对于随机 matvec）与大小^2 的关系图。我将时间乘以 2.13E9（对于 GHz），得出总操作与大小^2 的关系图。然后我逼近这条线的斜率，这给了我 Operations = (slope) * N^2。在我的例子中，常数是 45.45454545 并且图表是笔直的。对于 10k x 10k CG 问题，每次迭代需要 1 个 matvec（无预处理器）和 550 次这样的迭代。总共有 550 个 matvecs $\approx$ 550*45.45*N^2 次操作 $\approx$ 550*45.45*1e8 / 2.13e9 秒 $\approx$ 1000 秒。

事实证明（我已要求 SO 的版主删除该问题）：

我没有考虑每秒（和每个时钟）的指令。因此，我的实际运行时间是 120 秒（对于 10k x 10k CG），而我的计算是 1000 秒！我如何计入 IPS/IPC？
45 对于 MatVecs 来说是一个太大的领先常数。理想情况下，它应该在 2 左右。我在这个计算中哪里出错了？

如何改进我的理论预测？