核心内容摘要
超级创新【物流中心选址】基于企鹅优化算法在物流中心选址的应用附Matlab代码
Mandelbrot集合的多线程并行计算加速最近研究并行计算找了CS149的网课看看顺便做做作业QAQ代码下载Mandelbrot集合的多线程并行计算加速代码文件目录Mandelbrot集合的多线程并行计算加速
Mandelbrot 集合介绍
1 Mandelbrot 图像的产生过程计算视角1️⃣ 选定计算区域复平面上的矩形2️⃣ 建立像素网格离散化3️⃣ 像素 → 复数点的映射4️⃣ 对每个点做 Mandelbrot 迭代5️⃣ 发散判定阈值判断6️⃣ 最大迭代次数限制防止无限循环7️⃣ 迭代次数 → 像素值
Mandelbrot图并行计算
2.
连续块划分block / chunk特点代码
2.
交错划分cyclic / interleaved示意图代码
2.
性能对比
Mandelbrot 集合介绍对复数z x yiz n 1 z n 2 c , z 0 0 z_{n1} z_n^2 c,\quad z_0 0zn1zn2c,z00如果在不断迭代后|z|超过某个阈值通常是 2就认为这个点不属于 Mandelbrot 集。
好这里我按**“图是怎么一步一步算出来的”来讲用流程化 偏实现视角**的描述正好对应你代码里在做的事而不是纯数学定义。
1 Mandelbrot 图像的产生过程计算视角1️⃣ 选定计算区域复平面上的矩形首先在复平面中选一个有限的矩形区域作为“观察窗口”x ∈ [x0, x1] y ∈ [y0, y1]这个矩形决定了你最终看到的是 Mandelbrot 集的哪一块缩放、平移本质上就是在改这个矩形。
2️⃣ 建立像素网格离散化接着指定输出图像大小width × height这一步的含义是把连续的复平面矩形离散成一个规则网格每个网格点对应一个像素。
由此得到步长dx (x1 - x
/ width dy (y1 - y
/ height3️⃣ 像素 → 复数点的映射对图像中的每一个像素(i, j)x x0 i * dx y y0 j * dy c x yi也就是说每个像素都代表复平面中的一个复数 c。
4️⃣ 对每个点做 Mandelbrot 迭代对当前复数点c执行如下迭代z0 0 zn1 zn² c这是一个局部、互不依赖的计算过程因此非常适合并行。
5️⃣ 发散判定阈值判断在迭代过程中每一步都会检查|zn| threshold ?通常threshold 2一旦超过阈值就认为该点已经发散记录此时的迭代次数n6️⃣ 最大迭代次数限制防止无限循环为了避免无限计算引入最大迭代次数例如maxIterations 255规则是如果在255 次迭代内发散→ 返回实际发散的迭代次数如果迭代 255 次仍未发散→ 停止迭代认为该点“属于 Mandelbrot 集内部或边界附近”7️⃣ 迭代次数 → 像素值最终output[j * width i] iteration_count这个值通常被用于直接作为灰度值或作为调色函数的输入生成彩色分形图
Mandelbrot图并行计算
2.
连续块划分block / chunk每个线程拿一整块连续的行行号: 0 1 2 3 4 5 6 7 8 9 10 11 ─────────────────────────────── 线程0: █ █ █ █ 线程1: █ █ █ █ 线程2: █ █ █ █等价于thread 0 → 行0,1,2,3thread 1 → 行4,5,6,7thread 2 → 行8,9,10,11特点✅ cache 友好✅ 实现简单❌ 如果不同区域算得“慢/快”不均会负载不平衡代码voidworkerThreadStartBlock(WorkerArgs*constargs){inttidargs-threadId;intTargs-numThreads;intH(int)args-height;introwsPerThreadH/T;intremainderH%T;intstartRowtid*rowsPerThread(tidremainder?tid:remainder);intnumRowsrowsPerThread(tidremainder?1:
;if(numRows
return;mandelbrotSerial(args-x0,args-y0,args-x1,args-y1,(int)args-width,(int)args-height,startRow,numRows,args-maxIterations,args-output);}
2.
交错划分cyclic / interleaved行号按线程号取模规则行 j 交给线程 (j % T)示意图行号: 0 1 2 3 4 5 6 7 8 9 10 11 ─────────────────────────────── 线程0: █ █ █ █ 线程1: █ █ █ █ 线程2: █ █ █ █等价于thread 0 → 行0, 3, 6, 9thread 1 → 行1, 4, 7, 10thread 2 → 行2, 5, 8, 11这就是你看到的那句话线程 t 算 t, tT, t2T… 行代码voidworkerThreadStartCyclic(WorkerArgs*constargs){inttidargs-threadId;intTargs-numThreads;intH(int)args-height;// Interleaved partitioning: Thread tid is responsible for row tid, tidT, tid2T, ...for(intjtid;jH;jT){mandelbrotSerial(args-x0,args-y0,args-x1,args-y1,(int)args-width,(int)args-height,j,// startRow1,// numRowsargs-maxIterations,args-output);}}
2.
性能对比运行代码结果如下[mandelbrot serial]:[
6
776]ms Wrote imagefilemandelbrot-serial.ppm[mandelbrot thread block]:[
9
090]ms Wrote imagefilemandelbrot-thread.ppm[mandelbrot thread cyclic]:[
4
905]ms(
52x speedup: serial vs thread block,16threads)(
1
88x speedup: serial vs thread cyclic,16threads)实际上交错划分性能更好简单来说Mandelbrot 图像中不同位置的点发散速度不同导致不同图像行的计算量不均匀。
在block连续块划分中复杂区域的多行可能集中分配给某一个线程使该线程成为瓶颈其他线程空闲等待从而降低整体性能。
而cyclic交错划分将不同行均匀分配给各个线程把计算量较大的区域打散到多个线程中显著改善负载均衡因此整体执行时间更短、加速比更高。