并行合并使用线程排序/比Seq更多/更慢。 合并排序。 救命
http://pastebin.com/YMS4ehRj
这是我对并行合并排序的实现。 基本上我所做的是，对于每一次拆分，前半部分由一个线程处理，而后半部分是顺序的（即）说我们有一个包含9个元素的数组，[0..4]由线程1处理，[0 ..1]处理线程2，[5..6]由线程3处理（查看源代码以便澄清）。
其他一切都保持不变，比如合并。 但问题是，这比合并排序慢得多，甚至比正常的冒泡排序慢！ 我的意思是一个25000 int的数组。 我不确定瓶颈在哪里：它是互斥锁吗？ 是合并吗？
关于如何加快速度的任何想法？
您正在创建大量线程，每个线程只执行很少的工作。 要对25000个int进行排序，您需要创建大约12500个生成其他线程并合并其结果的线程，以及大约12500个每个只排序两个 int的线程。
创建所有这些线程的开销远远大于从并行处理中获得的收益。
为避免这种情况，请确保每个线程都有合理的工作量。 例如，如果一个线程发现它只需要排序<10000个数字，它可以简单地用正常的合并排序对它们进行排序，而不是产生新的线程。
鉴于您的系统上有一个有限数量的内核，为什么要创建比内核更多的线程？
此外，还不清楚为什么你需要一个互斥锁。 据我所知，从快速扫描中可以看出，程序不需要在本地函数之外共享线程[lthreadcnt]。 只需使用一个局部变量，你就应该是金色的。
你的并行性太精细了，有太多的线程只做小工作。 您可以定义阈值，以便按顺序对大小小于阈值的数组进行排序。 注意产生线程的数量，一个很好的迹象是线程数通常不比核心数大很多。
因为你的大部分计算都在merge函数中，另一个建议是使用Divide-and-Conquer Merge而不是简单合并。 优点是双重的：运行时间更短，并且很容易产生线程以运行并行合并。 您可以在此处了解如何实现并行合并： http ： //drdobbs.com/high-performance-computing/229204454 。 他们还有一篇关于并行合并排序的文章可能对您有所帮助： http ： //drdobbs.com/high-performance-computing/229400239