Poi*_*ain 0 c++ multithreading mandelbrot
所以我之前发布了一个类似的问题,但我没有发布足够的代码来获得我需要的帮助.即使我现在回去并添加了该代码,我也不认为它会被注意到,因为这个问题很老并且"已经回答"了.所以这是我的问题:
我正在尝试生成一个mandelbrot分形的一部分.我可以很好地生成它,但是当我添加更多内核时,无论问题大小有多大,额外的线程都不会产生加速.我对多线程是全新的,它可能只是我想念的小东西.无论如何,这里是生成分形的函数:
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个周期.
kur*_*eko 10
您的代码似乎可以进行并行处理,但实际上并非如此.基本上,您花时间复制数据并排队等待内存分配器访问.
此外,您正在使用未受保护的i循环指示,就好像它没有任何东西,它将为您的工作线程提供随机垃圾而不是图像的漂亮切片.
像往常一样,C++在一层厚厚的句法糖下隐藏着这些可悲的事实.
但是你的代码最大的缺陷就是算法本身,正如你可能会看到的那样,如果你进一步阅读的话.
由于这个例子似乎是一个对我并行处理的教科书案例,我从未看过它的"教育"分析,我会尝试一个.
您希望使用所有CPU内核来处理Mandelbrot集的像素.这是可并行计算的完美情况,因为每个像素计算可以独立完成.
所以基本上你在你的机器上有N个核心,你应该每个核心只有一个线程进行1/N的处理.
不幸的是,将输入数据分开以使每个处理器最终完成所需处理的1/N并不像看起来那么明显.
给定像素可以进行0到255次迭代来计算."黑色"像素比"白色" 像素高出255倍.
因此,如果您只是将图片划分为N个相等的子表面,那么您的所有处理器都可能会轻松穿过"白色"区域,除了将会爬过"黑色"区域的区域.结果,最慢的区域计算时间将占主导地位,并行化几乎不会获得任何结果.
在实际情况下,这不会那么戏剧化,但仍然是计算能力的巨大损失.
为了更好地平衡负载,将图像分成更小的位更有效,并且让每个工作线程在完成前一个可用位后立即选择并计算下一个可用位.这样,处理"白色"块的工人最终将完成其工作并开始挑选"黑色"块以帮助其不那么幸运的兄弟姐妹.
理想情况下,应该通过降低复杂度对块进行排序,以避免将大块的线性成本添加到总计算时间.
不幸的是,由于Mandlebrot集的混乱性质,没有实际的方法来预测给定区域的计算时间.
如果我们确定块将是图片的水平切片,则按自然y顺序对它们进行排序显然不是最理想的.如果该特定区域是一种"白色到黑色"的渐变,那么最昂贵的线条将全部聚集在块列表的末尾,并且最终将计算最昂贵的位,这是负载平衡的最坏情况.
一种可能的解决方案是以蝴蝶图案对块进行混洗,使得最终集中"黑色"区域的可能性很小.
另一种方法就是随机改变输入模式.
以下是我的概念验证实现的两个输出:
作业以相反的顺序执行(作业39是第一个,作业0是最后一个).每行解码如下:
t ab:处理器上的线程n°a
b:开始时间(自图像计算开始)
e:结束时间
d:持续时间(所有时间,以毫秒为单位)
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)每个核心只有一个作业的运行,激活一到四个核心
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只有两个"真实"核心).
我的程序强制线程在每个核心上运行(使用MSDN SetThreadAffinityMask).
如果调度程序可以自由分配任务,则增益因子从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%.
| 归档时间： |
|
| 查看次数： |
2724 次 |
| 最近记录： |