常见cpu密集型任务示例

Question

为了测试并行化工具，我正在寻找任务或算法的示例，这些任务或算法如下：

1. cpu密集
2. 可并行性
3. 投入和输出相对较少
4. 通常用于日常编程中(不只是科学家和算法开发人员)

我已经找到了很多例子，但没有一个满足4。最明显的例子是素因式分解。旅行推销员问题是另一个问题。

为了满足数字3，我认为算法不应该具有线性或接近线性复杂性，例如排序。

Answer 1

有两种类型的耗时任务：

1. 遍历大量的数据..。这违反了第3点(除非您动态创建数据)
2. 对小数据进行耗时的计算.这违反了第四点。

我可以建议的是创建基本类型的大向量，并对它的每个元素执行简单的操作(插入随机值/按随机值修改)或排序。

这将是cpu密集型，很容易分裂成多个线程，您可以动态生成数据(输入小，但内存占用仍然很大)，这是非算法性的。

Answer 2

几个图像处理滤波器是耗时和高度并行性。

例如，中位或双侧或非局部指的是大直径的过滤器.这对于图像去噪是非常有用的。

典型的图像大小是几MB。一个好的和有用的应用程序是允许实时反馈的可调参数，这需要运行时间下的第二个。

具有指数行为的困难问题并不是理想的目标，因为它们的运行时间在很大的范围内变化，而且您将被限制在一个小的N的范围内，这使得研究变得有些人为。

线性代数将为N_2存储提供一系列具有N~3行为的算法。Tey在物理模拟代码中被大量使用。