所以我之前发布了一个类似的问题，但我没有发布足够的代码来获得所需的帮助。即使我现在回去添加那个代码，我也不认为它会被注意到，因为这个问题已经过时了，而且已经"得到了回答"。所以我的问题是：
我正在尝试生成一段曼德布洛特分形。我可以很好地生成它，但当我添加更多的核心时，无论问题大小有多大，额外的线程都不会产生任何加速。我对多线程完全陌生，可能只是缺少了一些小东西。总之，以下是生成分形的函数：
void mandelbrot_all(std::vector<std::vector<int>>& pixels, int X, int Y, int numThreads) {
using namespace std;
vector<thread> threads (numThreads);
int rowsPerThread = Y/numThreads;
mutex m;
for(int i=0; i<numThreads; i++) {
threads[i] = thread ([&](){
vector<int> row;
for(int j=(i-1)*rowsPerThread; j<i*rowsPerThread; j++) {
row = mandelbrot_row(j, X, Y);
{
lock_guard<mutex> lock(m);
pixels[j] = row;
}
}
});
}
for(int i=0; i<numThreads; i++) {
threads[i].join();
}
}
std::vector<int> mandelbrot_row(int rowNum, int topX, int topY) {
std::vector<int> row (topX);
for(int i=0; i<topX; i++) {
row[i] = mandelbrotOne(i, rowNum, topX, topY);
}
return row;
}
int mandelbrotOne(int currX, int currY, int X, int Y) { //code adapted from http://en.wikipedia.org/wiki/Mandelbrot_set
double x0 = convert(X, currX, true);
double y0 = convert(Y, currY, false);
double x = 0.0;
double y = 0.0;
double xtemp;
int iteration = 0;
int max_iteration = 255;
while ( x*x + y*y < 2*2 && iteration < max_iteration) {
xtemp = x*x - y*y + x0;
y = 2*x*y + y0;
x = xtemp;
++iteration;
}
return iteration;
}
mandelbrot_all被传递一个向量来保存像素、向量的最大X和Y以及要使用的线程数，该向量在程序运行时从命令行获取。它试图在多个线程之间按行分割工作。不幸的是，即使这是它正在做的，它似乎也没有让它变得更快。如果你需要更多的细节，请随时询问，我会尽我所能提供。
提前感谢您的帮助。
编辑：提前预留矢量编辑2：在四核笔记本电脑上运行此代码，问题大小为9600x7200。一个线程(超过5次运行)平均需要36590000次循环，四个线程平均需要55142000次循环。
您的代码可能看起来是进行并行处理的，但实际上并不是。基本上，您要花费时间四处复制数据，并排队等待内存分配器访问。
此外，您正在使用未受保护的i循环标记，就好像它什么都没有一样，这将向您的工作线程提供随机垃圾，而不是图像的漂亮切片。
和往常一样，C++在厚厚的语法糖外壳下向你隐瞒了这些可悲的事实。
但你的代码最大的缺陷是算法本身，如果你进一步阅读，你可能会看到这一点。
由于这个例子对我来说似乎是一个平行处理的教科书案例，而且我从未见过对它的"教育性"分析，所以我会尝试一个。
功能分析
您希望使用所有CPU核心来压缩Mandelbrot集的像素。这是可并行计算的完美案例，因为每个像素计算都可以独立完成。
所以基本上，如果你的机器上有N个内核，每个内核应该有一个线程来完成1/N的处理。
不幸的是，划分输入数据，使每个处理器最终完成所需处理的1/N，并不像看上去那么明显。
给定的像素可能需要0到255次迭代才能进行计算。"黑色"像素的成本是"白色"像素的255倍。
因此，如果你简单地将图片划分为N个相等的子表面，那么除了一个会在"黑色"区域爬行的处理器外，所有处理器都有可能轻松通过"白色"区域。因此，最慢的区域计算时间将占主导地位，并行化将几乎一无所获。
在实际情况下，这不会那么引人注目，但仍然是计算能力的巨大损失。
负载平衡
为了更好地平衡负载，更有效的方法是将图片分割成更小的比特，并让每个工作线程在完成前一个比特后立即选择并计算下一个可用比特。这样，处理"白色"块的工人最终会完成工作，并开始挑选"黑色"块来帮助不幸的兄弟姐妹。
理想情况下，块应该通过降低复杂性来排序，以避免将大块的线性成本添加到总计算时间中。
不幸的是，由于Mandlebrot集的混沌性质，没有实际的方法来预测给定区域的计算时间。
如果我们决定这些块将是图片的水平切片，那么按自然y顺序对它们进行排序显然是次优的。如果该特定区域是一种"从白到黑"的梯度，那么最昂贵的行将全部聚集在块列表的末尾，您最终将计算出最昂贵的位，这是负载平衡的最坏情况。
一个可能的解决方案是以蝴蝶图案打乱块，这样最后集中"黑色"区域的可能性就很小
另一种方法就是随机打乱输入模式。
以下是我的概念验证实现的两个输出：
作业按相反的顺序执行(作业39是第一个，作业0是最后一个)。每行解码如下：
ta-b:处理器b上的线程n°a
b：开始时间
1) 蝶式订购的40个工作岗位
job 0: t 1-1 b 162 e 174 d 12 // the 4 tasks finish within 5 ms from each other
job 1: t 0-0 b 156 e 176 d 20 //
job 2: t 2-2 b 155 e 173 d 18 //
job 3: t 3-3 b 154 e 174 d 20 //
job 4: t 1-1 b 141 e 162 d 21
job 5: t 2-2 b 137 e 155 d 18
job 6: t 0-0 b 136 e 156 d 20
job 7: t 3-3 b 133 e 154 d 21
job 8: t 1-1 b 117 e 141 d 24
job 9: t 0-0 b 116 e 136 d 20
job 10: t 2-2 b 115 e 137 d 22
job 11: t 3-3 b 113 e 133 d 20
job 12: t 0-0 b 99 e 116 d 17
job 13: t 1-1 b 99 e 117 d 18
job 14: t 2-2 b 96 e 115 d 19
job 15: t 3-3 b 95 e 113 d 18
job 16: t 0-0 b 83 e 99 d 16
job 17: t 3-3 b 80 e 95 d 15
job 18: t 2-2 b 77 e 96 d 19
job 19: t 1-1 b 72 e 99 d 27
job 20: t 3-3 b 69 e 80 d 11
job 21: t 0-0 b 68 e 83 d 15
job 22: t 2-2 b 63 e 77 d 14
job 23: t 1-1 b 56 e 72 d 16
job 24: t 3-3 b 54 e 69 d 15
job 25: t 0-0 b 53 e 68 d 15
job 26: t 2-2 b 48 e 63 d 15
job 27: t 0-0 b 41 e 53 d 12
job 28: t 3-3 b 40 e 54 d 14
job 29: t 1-1 b 36 e 56 d 20
job 30: t 3-3 b 29 e 40 d 11
job 31: t 2-2 b 29 e 48 d 19
job 32: t 0-0 b 23 e 41 d 18
job 33: t 1-1 b 18 e 36 d 18
job 34: t 2-2 b 16 e 29 d 13
job 35: t 3-3 b 15 e 29 d 14
job 36: t 2-2 b 0 e 16 d 16
job 37: t 3-3 b 0 e 15 d 15
job 38: t 1-1 b 0 e 18 d 18
job 39: t 0-0 b 0 e 23 d 23
当一个线程处理了几个小作业后，将超过另一个需要更多时间处理自己的块的线程时，您可以看到负载平衡在工作。
2) 具有线性排序的40个作业
job 0: t 2-2 b 157 e 180 d 23 // last thread lags 17 ms behind first
job 1: t 1-1 b 154 e 175 d 21
job 2: t 3-3 b 150 e 171 d 21
job 3: t 0-0 b 143 e 163 d 20 // 1st thread ends
job 4: t 2-2 b 137 e 157 d 20
job 5: t 1-1 b 135 e 154 d 19
job 6: t 3-3 b 130 e 150 d 20
job 7: t 0-0 b 123 e 143 d 20
job 8: t 2-2 b 115 e 137 d 22
job 9: t 1-1 b 112 e 135 d 23
job 10: t 3-3 b 112 e 130 d 18
job 11: t 0-0 b 105 e 123 d 18
job 12: t 3-3 b 95 e 112 d 17
job 13: t 2-2 b 95 e 115 d 20
job 14: t 1-1 b 94 e 112 d 18
job 15: t 0-0 b 90 e 105 d 15
job 16: t 3-3 b 78 e 95 d 17
job 17: t 2-2 b 77 e 95 d 18
job 18: t 1-1 b 74 e 94 d 20
job 19: t 0-0 b 69 e 90 d 21
job 20: t 3-3 b 60 e 78 d 18
job 21: t 2-2 b 59 e 77 d 18
job 22: t 1-1 b 57 e 74 d 17
job 23: t 0-0 b 55 e 69 d 14
job 24: t 3-3 b 45 e 60 d 15
job 25: t 2-2 b 45 e 59 d 14
job 26: t 1-1 b 43 e 57 d 14
job 27: t 0-0 b 43 e 55 d 12
job 28: t 2-2 b 30 e 45 d 15
job 29: t 3-3 b 30 e 45 d 15
job 30: t 0-0 b 27 e 43 d 16
job 31: t 1-1 b 24 e 43 d 19
job 32: t 2-2 b 13 e 30 d 17
job 33: t 3-3 b 12 e 30 d 18
job 34: t 0-0 b 11 e 27 d 16
job 35: t 1-1 b 11 e 24 d 13
job 36: t 2-2 b 0 e 13 d 13
job 37: t 3-3 b 0 e 12 d 12
job 38: t 1-1 b 0 e 11 d 11
job 39: t 0-0 b 0 e 11 d 11
在这里，代价高昂的块往往会在队列的末尾聚集在一起，因此会造成明显的性能损失。
3) 每个核心只有一个作业的运行，有一到4个核心激活
reported cores: 4
Master: start jobs 4 workers 1
job 0: t 0-0 b 410 e 590 d 180 // purely linear execution
job 1: t 0-0 b 255 e 409 d 154
job 2: t 0-0 b 127 e 255 d 128
job 3: t 0-0 b 0 e 127 d 127
Master: start jobs 4 workers 2 // gain factor : 1.6 out of theoretical 2
job 0: t 1-1 b 151 e 362 d 211
job 1: t 0-0 b 147 e 323 d 176
job 2: t 0-0 b 0 e 147 d 147
job 3: t 1-1 b 0 e 151 d 151
Master: start jobs 4 workers 3 // gain factor : 1.82 out of theoretical 3
job 0: t 0-0 b 142 e 324 d 182 // 4th packet is hurting the performance badly
job 1: t 2-2 b 0 e 158 d 158
job 2: t 1-1 b 0 e 160 d 160
job 3: t 0-0 b 0 e 142 d 142
Master: start jobs 4 workers 4 // gain factor : 3 out of theoretical 4
job 0: t 3-3 b 0 e 199 d 199 // finish at 199ms vs. 176 for butterfly 40, 13% loss
job 1: t 1-1 b 0 e 182 d 182 // 17 ms wasted
job 2: t 0-0 b 0 e 146 d 146 // 44 ms wasted
job 3: t 2-2 b 0 e 150 d 150 // 49 ms wasted
在这里，我们得到了3倍的改进，而更好的负载平衡可以产生3.5倍的改进。
这是一个非常温和的测试案例(你可以看到计算时间只会变化大约2倍，而理论上它们可能会变化255倍！)。
无论如何，如果你不实现某种负载平衡，你可能编写的所有闪亮的多处理器代码仍然会产生糟糕的性能。
实施
为了让线程不受阻碍地工作，它们必须免受外部世界的干扰。
一个这样的干扰是内存分配。每次分配哪怕一个字节的内存，都会排队等待对全局内存分配器的独占访问(并浪费一点CPU来进行分配)。
此外，为每个图片计算创建工作者任务是另一种时间和资源浪费。计算可以用于在交互式应用程序中显示Mandlebrot集，因此更好地让工作人员预先创建并同步以计算连续的图像。
最后，还有数据副本。如果每次计算完几个点后都与主程序同步，那么您将再次花费大部分时间排队以独占访问结果区域。此外，大量数据的无用副本将对性能造成更大的损害。
显而易见的解决方案是完全放弃副本，转而使用原始数据。
设计
你必须为你的工作线程提供他们不受阻碍地工作所需的一切。为此，您需要：
- 确定系统上可用内核的数量
- 预先分配所需的所有内存
- 为每个员工提供对图像块列表的访问权限
- 每个核心只启动一个线程，让它们自由运行以完成工作
作业队列
不需要花哨的不等待或任何小发明，我们也不需要特别注意缓存优化
在这里，计算像素所需的时间减少了线程间同步成本和缓存效率问题。
基本上，队列可以在图像生成开始时作为一个整体进行计算。工人只需要从中读取作业：这个队列上永远不会有并发的读/写访问，因此实现作业队列的或多或少的标准代码位对于手头的作业来说将是次优的，而且过于复杂。
我们需要两个同步点：
- 让工人等待新一批工作
- 让主机等待图片完成
工作人员将等待队列长度更改为正值。然后，它们将全部唤醒并开始原子性地递减队列长度。队列长度的当前值将为他们提供对相关作业数据的独占访问(基本上是Mandlebrot集合中要计算的区域，以及存储计算的迭代值的相关位图区域)。
同样的机制也被用来解雇工人。这些可怜的工人不会找到新的一批工作，而是醒来后发现了解雇的命令。
等待图片完成的主机将被将完成处理最后一个作业的工作者唤醒。这将基于要处理的作业数的原子计数器。
这就是我实现它的方式：
class synchro {
friend class mandelbrot_calculator;
mutex lock; // queue lock
condition_variable work; // blocks workers waiting for jobs/termination
condition_variable done; // blocks master waiting for completion
int pending; // number of jobs in the queue
atomic_int active; // number of unprocessed jobs
bool kill; // poison pill for workers termination
void synchro (void)
{
pending = 0; // no job in queue
kill = false; // workers shall live (for now :) )
}
int worker_start(void)
{
unique_lock<mutex> waiter(lock);
while (!pending && !kill) work.wait(waiter);
return kill
? -1 // worker should die
: --pending; // index of the job to process
}
void worker_done(void)
{
if (!--active) // atomic decrement (exclusive with other workers)
done.notify_one(); // last job processed: wakeup master
}
void master_start(int jobs)
{
unique_lock<mutex> waiter(lock);
pending = active = jobs;
work.notify_all(); // wakeup all workers to start jobs
}
void master_done(void)
{
unique_lock<mutex> waiter(lock);
while (active) done.wait(waiter); // wait for workers to finish
}
void master_kill(void)
{
kill = true;
work.notify_all(); // wakeup all workers (to die)
}
};
综合起来：
class mandelbrot_calculator {
int num_cores;
int num_jobs;
vector<thread> workers; // worker threads
vector<job> jobs; // job queue
synchro sync; // synchronization helper
mandelbrot_calculator (int num_cores, int num_jobs)
: num_cores(num_cores)
, num_jobs (num_jobs )
{
// worker thread
auto worker = [&]()
{
for (;;)
{
int job = sync.worker_start(); // fetch next job
if (job == -1) return; // poison pill
process (jobs[job]); // we have exclusive access to this job
sync.worker_done(); // signal end of picture to the master
}
};
jobs.resize(num_jobs, job()); // computation windows
workers.resize(num_cores);
for (int i = 0; i != num_cores; i++)
workers[i] = thread(worker, i, i%num_cores);
}
~mandelbrot_calculator()
{
// kill the workers
sync.master_kill();
for (thread& worker : workers) worker.join();
}
void compute(const viewport & vp)
{
// prepare worker data
function<void(int, int)> butterfly_jobs;
butterfly_jobs = [&](int min, int max)
// computes job windows in butterfly order
{
if (min > max) return;
jobs[min].setup(vp, max, num_jobs);
if (min == max) return;
jobs[max].setup(vp, min, num_jobs);
int mid = (min + max) / 2;
butterfly_jobs(min + 1, mid );
butterfly_jobs(mid + 1, max - 1);
};
butterfly_jobs(0, num_jobs - 1);
// launch workers
sync.master_start(num_jobs);
// wait for completion
sync.master_done();
}
};
测试概念
这段代码在我的2核/4 CPU Intel I3@3.1 GHz上运行得很好，使用Microsoft Dev Studio 2013编译。
我在1280x1024像素的窗口上使用了一个平均90次迭代/像素的集合。
只有一名工人的计算时间约为1.700s，而有4名工人的则降至0.480s大可能的增益是因子4。我得到一个因子3.5。还不错。
我认为这种差异部分是由于处理器架构(I3只有两个"真正的"内核)。
篡改调度程序
我的程序强制线程在每个内核上运行(使用MSDNSetThreadAffinityMask)
如果调度器可以自由分配任务，则增益因子将从3,5降至3,2。
这很重要，但Win7调度程序在单独使用时仍然做得很好。
同步开销
在"白色"窗口(r<2区域之外)上运行该算法可以很好地了解系统调用开销。
与代表性区域的480毫秒相比，计算这个"白色"区域大约需要7毫秒。
大约1.5%，包括作业队列的同步和计算。这是在1024个作业的队列上进行同步。
我认为完全可以忽略。这可能会让周围所有排队等候的狂热分子深思。
优化迭代
迭代的方式是优化的关键因素
经过几次尝试，我决定采用这种方法：
static inline unsigned char mandelbrot_pixel(double x0, double y0)
{
register double x = x0;
register double y = y0;
register double x2 = x * x;
register double y2 = y * y;
unsigned iteration = 0;
const int max_iteration = 255;
while (x2 + y2 < 4.0)
{
if (++iteration == max_iteration) break;
y = 2 * x * y + y0;
x = x2 - y2 + x0;
x2 = x * x;
y2 = y * y;
}
return (unsigned char)iteration;
}
净增益：与OP的方法相比增加了20%
(register指令没有什么区别，它们只是用来装饰的)
每次计算后终止任务
让工人活着的好处大约是计算时间的5%。
蝴蝶效应
在我的测试案例中，"蝴蝶"订单做得非常好，在极端情况下产生了30%以上的收益，由于"去集群"最庞大的请求，通常会产生10-15%的收益。
代码中的问题是所有线程捕获和访问相同的i变量。这就造成了一种比赛条件，结果极不正确。
您需要将其作为参数传递给线程lambda，并更正范围(i-1将使索引超出范围)。