论文研究-申威众核处理器的并行NSGA-II算法.pdf

所需积分/C币:6 2019-09-08 09:28:47 642KB .PDF

非支配排序遗传算法(NSGA-II)在多目标优化领域有着广泛的应用,但在处理复杂问题时运行时间相当长。并行化是提高算法执行速度的有效途径。众核处理器的出现,为实现高度并行奠定了物质基础。基于国产超算“神威·太湖之光”的申威众核处理器平台设计了并行NSGA-II算法(PNSGA-II),实现了算法基于主核的一级并行和基于主/从核的二级并行。在典型测试函数集上的实验表明,在不影响解的质量前提下,PNSGA-II算法不仅大大加快了执行速度,同时算法的收敛速度也更快。
沈焕学,郑凯,刘垚,等:申威众核处理器的并行NSGA-算法 2018,54(17)37 NSGA-山精英策略:保留父代中的优良个体进入子并行则主核和从核同时使用采用MP+ Athread混合编 代。首先将第代产生的新种群Q与父代种群P合程模型。“神威·太湖之光”计算机系统加速线程库以 并组成R,种样大小为2N;对种群R进行非支配排( Athread库)是针对两级并行编程模型(主从加速编程 序并计算毎个个体的拥挤度,根据个体层级序号的高低模)所设计的程序加速库,其H的是为了用户能够方 跟拥挤度的大小选择个体,直到个体的数量达到N此便、快捷地对核组内的线程进行灵活的控制和调度 时产生了一个新的父代种群P1;在此基础上进行新从而更好地发挥核组内多核并发执行的加速性能 轮的选择、交义和变异形成新的子代种群Q4 PNSGA-I算法的核心内容包括 (1)初始化种群。种群规模设置为10000,.用分 3并行NSGA-∏算法的设计和实现 岛模型对其进行分岛,岛的数量为n,n不超过核组中 3.1级并行模式 的主核数量 (2)编码。每个岛内均采用实数编码。为了休证每 如图1所示,将初始种群按照处理器(主核)的个数个岛上产生的个体不完全+样,并行程序都会调用个 分成若千个子种群,各子种群独立地在每个岛上执行遗 时间种子,确保每次每个进程产生的个体不一样。若个 传操作(一个岛对应一个主核),每隔一定的代数各子种 体变量取值范围在(a,b)内,则在(0,1)内生成一个随机 群间进行数据迁移 数d,那么个体的值为 分岛1 分岛n d×(b 种群1 种群n 若个体变量的取值是没有指定范闹的,此时生成的 编码为 选择交又、变异 选择、交叉、变异 满足条件 <<满足条件 是 cl1=2d-1 数据迁移 数据迁移 (3)遗传操作。每个岛对采用NSG∧∏算法进行遗 传操作,NSGA-II的参数设置为: 图1分岛模型结构图 ①选择。锦标賽选择,选择规模为2,对于个体p 3.2二级并行模式 和q,若p≤q灬k,那么优先选择层级较小的pmk; 二级并行则采用分岛主从模式,由主核从核协作若P= 完成,先将种群分成若干子种群,每个子种群对应一个大的个mk,则比较跟的拥挤度,选择拥挤度较 岛,岛内主从加速并行模型。主核主要完成不能由从核 ②交叉。采用实数交叉,交叉率为0.9,交又算子为 并行部分的计算及通信,在从核进行任务计算时,主核模拟二进制交叉: 等待。图2是最常用的两级并行方式,除此之外,申威 众核并行模式还有主从协同并行、主从异步并行和主从 Ck=(1-3p1k+(1+)p2k (3) 动态并行。 c=(1+3)p1+(1-3)p2 ,k表示第个子个体的第k个分量,Pk为选择的父个 空闲 体,BA(≥0为一个随机数由下面公式产生 程序段A (计算通信IO) p(P)=,(n+1),0≤B≤1 加载到程序段 B从核 B) B>1 B+2 程序段B(计算 7为交叉分布指数。 等待 通信/O) 交叉可以使父代的优良基因遗传到下一代中,首先 执行完毕 从每个岛的种群中选出2个待交叉的个体,根据公式 返回 (3)、(4)对个体的每个分量分别进行交义,得到2个新 程序段C 的子个体。 计算通信O) 空闲 实现交叉伪代码如下 主核 从核 图2主从加速并行示意图 for(i-0;i< TASK NUM/2;i计+){/ TASK NUM为岛内种 样大小,每次选择两个个体进行交叉 33 PNSGA-算法操作 i(md<= pcross){/md:产生的随机数,pros:预设 级并行单纯使用主核,利用MPI进行通信。二级定的交叉率 38 2018,54(17) Computer Engineering and4 pplications计算机工程与应用 for(j=0;j<nvar;i计+)var:分量的个数 ir( nd -pmut r)lmd:产生的随机数,pmur:预 parl,par2<- select(;选择父个体进行交叉,设定的变异率 pa2为待交义的两个父个体 *找到dela的值,即公式(7)的a* /找到beta值,即公式(3)、(4)的B2* deltas- finddelta()/利用公式(8),(9 beta<- ndbeta()利用公式(5)、6 child-- mutation( delta,par)/利用公式(7),par为 child1,chid2<- crossover(beta,parl,nar2)/利待变异个体,chid为变异后的子个体 用公式(3).(4), child1,chld2为新产生的两个子个体 (4)迁移策略。每个进程均向其他n-1个进程发 ③变异。变异率为0.1,多项式变异算子为 送个体,进程m根据进程id和当前进化代数的值确定 Ch=P+(p!plot (7)按收个体:移时按照分层序号进行移,江移的个体 c为子个体,p为父个体,p跟p分别为其上下界,为非支配排序的最外层个体确保迁出的都是岛内最优 k是通过下面的公式计算出的 的个体。最后进行替换,将接收到的优良个体跟本岛内 的层级靠后的个体进行替换。 (2r2) l,r5<0. (8) (5)获得解集。达到最大迭代次数后,将所有岛内 k=1-|2(1 7)+ 0.5 (9)的非支配解进行合并,然后再对其进行次非支配排 7k是(0,1)之间的一个随机数,2是变异分布指数 序,最后得到的非支配解即构成 Pareto最优鮮集。 变异则是父个体根据公式(7)在个体变量取值范国34级并行的实现 内重新生成一个值,得到新的子个体。 主核上运行的线程对分岛后岛内的子种群进行初 实现变异伪代码如下: 始化、选择、交叉和变异,主核间使用M进行通信;与 此同时,运行亍从核上的线程进行目标函数与约束条件 r(i0:i< TASK NUM:i计+){ /TASK NUM为岛内种的计算, Athread库可以对核组内的线程进行灵活的控 群大小 制和调度,从而更好地发挥核组内多从核并发执行的加 for(j=0:j<mvar;j+)/nvar:分量的个数 速性能,如图3 开始 初始化种群并 初始化种群并 进行非劣排序 进行非劣排序 选择、交叉、 选择、交叉 从核并行 从核并行 从核并行 从核并行 计算 计算 计算 计算 主核数据汇总, 主核数据汇总 精英策略 精英策略 <Genin=O GenIn=0?>> 是 迁移操作 训种群间数据迁移 迁移操作 <满烂条件 满是条 输出最优解集 结束 图3二级并行NSGAⅡ流程图 沈焕学,郑凯,刘垚,等:申威众核处理器的并行NSGA-算法 2018,54(17)39 4实验与性能分析 重载 Pareto最外层解集 41测试数 级 PNSGA2 程与应」 一级 PNSGA2 ZDT函数: 中行NSGA2 fi(r)=1 12(x)=g(x)1 0 9 50 100 150 (x)=1+ 图4重载时三类算法在 BinhKorn上的解集 x:∈01,=1,2…n2≤n≤30 Binh korn睡数: 重祓 Pareto最外层解集 二级 PNSGAA2 f1(xy2=473+4y2,0÷r≤5 1.0 一级 PNSGA2 串行NSGA2 9=(x5)2+(y-5,0<y<3 0.6 约束条件: s(,y)=(x-5)+y2≤25 g2(x,y)=(x-8)2+(y+3)2=77 0.20.40.60.8101.2 4.2实验主要参数 f2(x) 本实验采用“神威·太湖之光”超算平合,通过多目 图5重载时三类算法在ZDT1上的解集 标测试问题来比较串行NSGA单纯基于主核的一级速比和从核加速比。从表中可以看出随着主核数的增 并行的 NSGA-(简称一级 PNSGA-IL)、使用主核和从加加速比增加,由于计算量较大,当出现跨节点通信时 核协同工作的二级并行的 PNSGA-Ⅱ(简称二级 PNSGA-计算开销远大于通信开销,对加速比、从核加速比的影 I)三类算法性能,并进行性能分析。实验中发现,当从响较小。表1与表2中4个主核时一级并行加速比都超 核计算量较轻时并行效果不明显。鉴于申威众核处理过了4这是因为听设计的 PNSGA1程序,在并行化后 器的主要加速性能来自从核,为了验证从核对性能的提通过岛间种群的迁移,使算法收敛得更快,提升了进化 升程度,实验将在重载条件下进行,重载时对三类方法速度,故出现了在4个主核时加速比略微超过了4。分 添加了挂起操作(use指令)来模拟同等时间的计算析从核加速比与主核数的关系,发现从核加速比在不超 量,算法执行参数设置为种群规模pe=100,过8个主核时效果较好接近理想值30。随着主核数的 化代gm-200,交义概率设置为P。-0.9,变异概率设增加,从核加速比反而变小,这是因为每个岛内分到的 置为Pn=0.1,二级PNSG∧所用的从核数为64个。 个体数量在减少,岛间的通信开销在增加同时从核的计 43评价指标 算量在减小,导致效率降低。 为了銜量程序并行化的效果,本文除了采用加速 ! Binhkorn重载时加速比与从核加速比 比这种通用的指标外,还考察了 Pareto解集的精度以主核串行运行一级并行 及收敛代数;另外还增加了从核的性能评价指标:从核数 运行时人加速比从核加 S运行时原加速二级并行 加速比。从核加速比5为同等条件下只使用主核的14830-1.010250224274 67.41 0933.89 运行时间T除以主核和从核协同工作的运行时间 1079.404.13413.39102.7524.88 37271196015.82 455.36 34.99127.7613.05 (10 303.65 28.19158.1010.77 每个主核最多可用64个从核,主核计算能力强于 表2ZDT1重载时加速比与从核加速比 从核,理想情况下从核加速比能达到30左右。 主核串行运行一级并行 44实验结果及分析 数 运行时间s加速比一级并行 运行时门、加速比从核加 速比 图4,图5分别是串行NSGA-I、一级 PNSGA-跟4 6943 24.102349 二级 PNSGA-在 Binhkorr和ZDT1上重载的 Pareto解 2152.0 56.792989 1018.1544.01 976024.34 集。结果表明在重载情况下 PNSGA-山算法的 Pareto解 691.68 111.3318.87 集不劣于串行NSGA-1 3994810.22 32.30126.4212.37 表1、表2分别表示在 BinhKor和ZDT1上重载加 23.9912.6029651377210.93 402018,54(l7) Computer Engineering and4 pplications计算机工程与应用 表3基于测试两数的PNGA与NSGA收敛代数比较0] MoussA, Elattar E b. Best compromise alternative to 测试函数平均代数(串行)平均代数(并行) EELD problein using hybrid Multiobjective quantun genetic ZDTI 10.2 algorithm [J]. Applied Mathematics Information Sciences Binh Korn 10.l 9.0 14,8(6):2889-2902 表3表明SGAm(含一级并行和二级并行)找到7mAN4四 最外层 Pareto解集时所需的进化代数(简称收敛代数 Strength Pareto Evolutionary Algorithn(SPEA2)[J]Journal 也比串行NSGAⅡ要少约10%,收敛速度更快 of Engineering Thermophysics, 2015, 24(1):86-100 [8 Srinivas n, Deb K Multiobjective optimization using 5结束语 nondominated sorting in genctic algorithms[J]. Evolutionary 针对串行NSG∧算法在处理数据量较大的问题 Computation, 1994, 2(3): 221-2 时,运行时间过长的回题本文基于申威众核处狸器平yebK, Agrawal S,rapA,a. A fast elitist non 台设计和实现了该算法的并行化版本 PNSGA-(含 dominated sorTing genetic algorithm for multi-objective 级与二级并行)实验结果表明, PNSGA除了极大地 optimization: NSGA-II[C]/International Conference on 缩短运行时间外(实验中最高加速比达158),在重载情 Parallel Problem Solving from Nature. 2000:849-858 况下,算法求解精度上与NSGAⅡ相当,收敛代数要少0 Sheng w, LiU K y,LiuY,etal. Optimal placement 于NSGA-I,能够更快地找到 Pareto最优前沿。其中二 and sizing of distributed generation via an improved 级并行的 PNSGA-II,在重载即从核计算量较大时,从核 nondominated sorting genetic algorithm II[JJ.IEEE Trans 加速比接近理想值30,使从核的计算能力得到允分的 actions on Power Delivery, 2015, 30(2): 569-578 发挥。 [1“神威·太润之光”系统快速使用指南[ EB/OL.(2016-06 本文主要是针对一些函数问题进行测试研究, (2016-07-15).http://www.nsccwx.cn/process.php?word= process&i=54,201(-08-10 PNSGA-I算法特别是二级并行的 PNSGA-Ⅱ性能提升 [12 Zhu W, Duan H High-speed detection of emergent mar 十分明显。但还有很多后继工作有待展开,如主存和局 ket clustering via an unsupervised parallel genetic algo 存的利用率优化题:将算法应用于多目标导航、航空 rithm[ South African Journal of Science016,112) 航天领域的更复杂的实际问题 [13] Liu YY, Wang SA scalable parallel genetic algorithm 参考文献: for the generalized assignment probleinJ] Parallel Com [1 Azadeh A, Shoja B M, Ghanei Set al.A multi-objective puting,2015,46(C):98-119 optimization problem for multi-state series-parallel systems: [14] Liu S, Cheng Y. The design and implementation of MPI A two-stage flow-shop manufacturing systemUJ Reliability mastcr-slavc parallel genctic algorithm[C]/Proceedings Enginccring Systcm Safety, 2015, 136(1): 62-74 of icgip 2013 [21 Martinez S Z, Coello C A CA multi-objective evolutionary [15] Almarakeby A FPGA on FPGA: Implementation of fine algorithm based on decomposition for constrained multi grained parallel genetic algoriThm on field program objective optimization[c//Evolutionary Computation, 2014: mable gate array[ J]. International Journal of Computer 429-436 Applications, 2013, 80(6): 29-32 [3] Li M, Yang S, Liu X Pareto or non-pareto: Bi-criterion [16 Hu H, Shu H.An improved coarse-grained parallel algo cvolution in multiobjcctivc optimization!]. IEEE Transactions rithm for computational acceleration of ordinary Kriging on Evolutionary Computation, 2016, 20(5): 645-665 interpolation[J]. Computers Geosciences, 2015, 78(C) [4] Non-Member w Z, Member s F S Multiobjective process 4452 planning and scheduling using improved vector evaluated [17] Wang Zhurong. A study of hybrid parallel genetic algo genetic algorithm with archive[J]. IEEJ Tr ransactions on rithm model[ C /International Conference on Natural Com Electrical Electronic Engineering. 2012. 7(3): 258-267 putation,2011:1038-1042. S] hang R, Chiong r. solving the energy- efficient job shop8]“神威·太湖之光”计算机编译系统用户手册[EB/OL] scheduling problcm: A multi-objective genctic algorithm 2016-06)(2016-07-15).http:/www.nsccwx.cn/process with enhanced local search for minimizing the total php? word-process&i-54, 2016-08-16 weighted tardiness and total energy consumption]. Jυ urmal[19]王竹荣,巨涛,马凡.多核集群系统下的混合并行還传算 f cleaner Production, 2016. 112(1): 3361-3375 法研究「计算机科学,2011,38(7):194-199

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐