Mur*_*fer 2 c pthreads quicksort
我将使用Pthreads为列表分为左右两半(小于和大于枢轴)后为每个分区创建新的胎面.我递归执行此操作,直到达到允许的最大线程数.
当我使用printfs来跟踪程序中发生的事情时,我清楚地看到每个线程并行执行其委托工作.但是,使用单个过程始终是最快的.一旦我尝试使用更多线程,完成几乎双倍所需的时间,并随着线程数量不断增加.
我可以在运行它的服务器上使用多达16个处理器.
算法如下:通过将元素与枢轴进行比较,将数组拆分为左右.为右侧和左侧启动一个新线程,并等待线程重新加入.如果有更多可用线程,则可以递归创建更多线程.每个线程都等待其子进程加入.
一切都对我有意义,排序工作得非常好,但更多的线程让它变得极为缓慢.
我尝试为每个分区设置最小数量的元素,以便启动一个线程(例如50000).
我尝试了一种方法,当一个线程完成时,它允许启动另一个线程,这导致数百个线程开始和完成.我认为开销太大了.所以我摆脱了它,如果一个线程完成执行,没有创建新的线程.我获得了更多的加速,但仍然比单个进程慢很多.
我使用的代码如下.
有没有人知道我可能做错了什么？
启动一个线程有相当大的开销.你可能最好创建一个具有固定数量线程的线程池,以及一个线程安全队列来为线程排队作业.线程等待队列中的项目,处理该项目,然后等待另一个项目.如果你想真正做到这一点,这应该是一个优先级队列,其顺序基于分区的大小(所以你总是先排序最小的分区,以防止队列大小过多).
这至少可以减少启动线程的开销 - 但这仍然不能保证您获得比单线程版本更好的性能.特别是,快速排序涉及CPU本身的足够少的工作,它可能几乎完全受带宽到内存的约束.一次处理多个分区可能会影响缓存局部性,以至于在任何情况下都会丢失速度.