multithreading - 通过线程实现动态编程算法来加速

Question

假设我有这个非常常见的 DP 问题(动态规划)-

给定成本矩阵成本 [][] 和成本 [][] 中的位置 (m, n)，编写一个函数返回从 (0) 到达 (m, n) 的最小成本路径成本, 0).矩阵的每个单元格代表遍历该单元格的成本。到达 (m, n) 路径的总成本是该路径上所有成本的总和(包括源和目的地)。您只能从给定单元格向下、向右和对角向下遍历单元格，即从给定单元格 (i, j)、单元格 (i+1, j)、(i, j+1) 和 (i+1, j+1)可以遍历。您可以假设所有成本都是正整数。

PS:回答这个 - 8

现在，在解决了这个问题之后……下面的问题在我脑海中闪过。

假设我有 1000*1000 矩阵。 O(n^2) 需要一些时间(在英特尔 i5 上肯定 <1 秒)。 但我可以进一步减少它吗？比如说使用这个算法启动 6-8 个线程，然后将它们同步回来，最后得到答案？得到答案会很快，甚至在逻辑上是可能的，还是我应该放弃这个想法

Answer 1

一般来说，在这么小的问题上(如你所说的<1sec)，由于协议(protocol)开销(线程启动和同步)，并行计算的效率低于顺序计算。另一个问题可能是，您增加了缓存未命中率，因为您从输入中选择要“随机”(非线性)操作的数据。然而，当涉及到更大的问题时，比如条目数增加 10 倍的矩阵，这确实值得一想(或两想)。

这是一个可能的解决方案。给定一个 16x16 矩阵，我们将其切成 4 个相等的正方形。对于这些方 block 中的每一个，一个线程负责。每个小方 block 中的数字表示经过多少个时间单位可以计算出该方 block 中的结果。

因此，总时间为 33 个单位(无论单位是什么)。与64个单元的顺序解决方案相比，它只是一半。您可以说服自己任何 2^k x 2^k 矩阵的运行时间是 2^(2k - 1) + 1。

然而，这只是我想到的第一个想法。我希望外面的世界有一个(多)更快的并行解决方案。

此外，出于我在回答开头提到的原因，出于所有实际目的，您不会使用我的解决方案实现 2 的加速。