# Pthreads，第 3 部分：并行问题（奖金） > 原文：<https://github.com/angrave/SystemProgramming/wiki/Pthreads%2C-Part-3%3A-Parallel-Problems-%28Bonus%29> ## 概观 下一节讨论 pthreads 碰撞时会发生什么，但如果我们让每个线程完全不同，没有重叠怎么办？ 我们发现最大加速并行问题？ ## 令人尴尬的并行问题 在过去几年中，对并行算法的研究已经爆发。一个令人尴尬的并行问题是任何需要很少努力转向并行的问题。他们中的很多人都有一些同步概念，但并非总是如此。你已经知道一个可并行化的算法，Merge Sort！ ```c void merge_sort(int *arr, size_t len){ if(len > 1){ //Mergesort the left half //Mergesort the right half //Merge the two halves } ``` 通过对线程的新理解，您需要做的就是为左半部分创建一个线程，为右半部分创建一个线程。鉴于您的 CPU 有多个真实核心，您将看到符合 [Amdahl 定律](https://en.wikipedia.org/wiki/Amdahl's_law)的加速。时间复杂度分析也很有趣。并行算法运行在 O（log ^ 3（n））运行时间（因为我们假设我们有很多核心的花式分析。 但在实践中，我们通常会做两处更改。一，一旦数组变得足够小，我们就会抛弃并行 mergesort 算法并执行快速排序或其他算法，这些算法可以在小数组上快速运行（某些东西可以缓存一致性）。我们知道的另一件事是 CPU 没有无限核心。为了解决这个问题，我们通常会保留一个工作人员池。 ## 工人池 我们知道 CPU 的内核数量有限。很多时候，我们启动了许多线程，并在空闲时为他们提供任务。 ## 另一个问题，平行地图 假设我们想要将一个函数应用于整个数组，一次一个元素。 ```c int *map(int (*func)(int), int *arr, size_t len){ int *ret = malloc(len*sizeof(*arr)); for(size_t i = 0; i < len; ++i) ret[i] = func(arr[i]); return ret; } ``` 由于没有任何元素依赖于任何其他元素，您将如何进行并行化？您认为在线程之间拆分工作的最佳方法是什么？ ## 调度 分离工作有几种方法。 * 静态调度：将问题分解为固定大小的块（预定义），并让每个线程都在每个块上运行。当每个子问题花费大致相同的时间时，这很有效，因为没有额外的开销。您需要做的就是编写一个循环并将 map 函数赋予每个子数组。 * 动态调度：当一个新问题变得可用时，有一个线程为它服务。当您不知道调度需要多长时间时，这非常有用 * 引导式调度：这是上述各种利益和权衡的混合。您可以从静态计划开始，并根据需要缓慢移动到动态 * 运行时调度：你完全不知道问题需要多长时间。不要自己决定，让程序决定做什么！ [来源](https://software.intel.com/en-us/articles/openmp-loop-scheduling)，但无需记忆。 ## 几个缺点 由于缓存一致性和调度额外线程之类的东西，你不会马上看到加速。 ## 其他问题 来自[维基百科](https://en.wikipedia.org/wiki/Embarrassingly_parallel) * 一次将 Web 服务器上的静态文件提供给多个用户。 * Mandelbrot 集，Perlin 噪声和类似图像，其中每个点都是独立计算的。 * 渲染计算机图形。在计算机动画中，每个帧可以独立渲染（参见并行渲染）。 * 密码学中的暴力搜索。[8]值得注意的现实世界的例子包括 distributed.net 和加密货币中使用的工作证明系统。 * BLAST 在生物信息学中搜索多个查询（但不是针对单个大型查询）[9] * 大规模面部识别系统，其将数千个任意获取的面部（例如，经由闭路电视的安全或监视视频）与类似大量的先前存储的面部（例如，盗贼画廊或类似的观察列表）进行比较。[10] * 计算机模拟比较许多独立场景，例如气候模型。 * 进化计算元启发式算法，如遗传算法。 * 数值天气预报的集合计算。 * 粒子物理中的事件模拟与重建。 * 行进方块算法 * 筛分步骤的二次筛和数字筛。 * 随机森林机器学习技术的树木生长步骤。 * 离散傅里叶变换，其中每个谐波是独立计算的。