任务分解

Question

所以我想了解任务分解是如何工作的以及为什么它似乎不会增加我的计算速度。所以我制作了一个简单排序数组的并行系统。使用4个线程，我的速度有了不错的提升，但是当我执行任务分解时，似乎没有加快我的计算速度，我不明白为什么。

所以对于我的系统，我已经为每个线程创建了一个任务队列。然后每个线程开始逐个计算每个任务，直到堆栈为空。此时，不是让线程等待所有其他线程完成，而是使用一个空堆栈的线程进行搜索，以查找具有任务并从中窃取的堆栈 - 有效地最大化每个线程可以执行的工作量。

但问题是，虽然我加快了速度，但它非常小，我似乎无法弄清楚为什么。是否可能是线程正在等待的时间太短以至于几乎不影响计算时间？或者，访问其他线程堆栈所需的时间否定了大部分加速其他堆栈上的任务的窃取速度？

这里是我的结果，你可以看到正在发生的事情：

parallel_for (1 Thread) parallel_for (4 Threads) parallel_for (4 Threads) + Task Decomposition 
1   seg fault     seg fault     seg fault 
10  21.993      seg fault     seg fault 
100  21.7294      5.42989      seg fault 
1000  21.5556      5.2258      5.38024 
10000  21.5513      5.43617      5.3735 
100000 21.6238      5.4557      5.41096 
1000000 21.5447      5.9712      5.9325 
10000000 21.5898      10.8605      10.753 

可以忽略赛格故障（它只是由于对堆栈没有足够的空间），并在旁边的值都只是每一个线程都将数组分开进行计算 - 它不应该是任务分解为什么提供最小化加速的原因。

Answer 1

不，不，否，不，不！

简单地增加线程不会加速任何东西，除非：

1）的任务是完全独立的（也许是这样，也许他们都没有）

2）每个任务可以被分配给它的OWN CPU（或核心）

3）与任务正在执行的实际工作相比，管理线程的成本很小。

建议：

如果您在使用“GCC”，尝试运行“gprof的”，以确定究竟在何处瓶颈可能是您的实现。另外，还要确保你的线程库（如并行线程）的工作站上采取所有的CPU /核心优势：

• GPROF Tutorial – How to use Linux GNU GCC Profiling Tool

• PThreads Overview

PS：这在很大程度上取决于上：

a）您的操作系统（Linux？Mac？Windows？）

b）你的编译器（GCC？ MSVC？）

c）您的线程库