基于集合理论的求解Ramsey数算法

)JournalofJilinUniversitScienceEditiony(

吉林大学学报(理学版)

Vol.57 No.3

Ma 2019y

研究简报

:/doi10.13413.cnki.dxblxb.2018092jj

基于集合理论的求解Ramsey数算法

()陕西科技大学文理学院,西安710021

白 云 霄

摘要:针对传统单核DNA计算机算法求解Ramsey数时运算效率较低,求解过程耗时高,所理论的MaReduce模型中Phoenix++系统为基础,设计单核CPU下的圈集对完全图的pRamsey数求解算法并对其实施优化,优化时进行数据预处理、高效任务分割和键值对规划Ramseamsey数,并对其数值进行验证,实现Ry数的求解.实验结果表明,程序处理图像数量随着顶点数的增加而不断增大,该方法求解Ramsey数的正确性较高,最大加速比和执行效率较好,运算性能较强.

关键词:集合理论;计算机算法;RamseaReduc模型;单核CPUy数求解;Mp()中图分类号:TP301.6 文献标志码:A 文章编号:1671-201903-07-06等过程,获取根据Phoenix++系统基于集合理论的并行算法,采用DNA计算机算法求解得结果误差较大的问题,提出一种基于集合理论的求解Ramsey数算法.该算法以基于集合

SolvinamseumberAlorithmBasedonSetTheorgRyNgy

(’SchoolortsandSciences,ShaanxiUniversitcience&TechnoloXian710021,China)fAyofSgy,

BAIYunxiao

:,AbstractAiminttheproblemoflowefficienchihtimeconsuminndlareerrorinsolvingayggagg-RamseumberbhetraditionalsinlecoreDNAcomuteralorithm,theauthorproosedaynytgpgp-oftheMaReducemodelbasedonsettheor.TheauthordesinedandotimizedtheRamseumberpygpyn

,ealorithmforthecomletegrahunderthesinlecoreCPU.Dataprerocessinfficienttaskgppgpg-basedonsettheornPhoenix++sstemwasobtained.TheRamseumberwassolvedbNAyiyynyDRamseumberalorithmbasedonsettheor.ThealorithmwasbasedonthePhoenix++sstemyngygy

sementationandkevaluepairplanninereperformeddurintimization.Theparallelalorithmgygwgopg-

exerimentalresultsshowthatthenumberofimaeprocessedbheproramincreaseswiththepgytg

,increaseofthevertices.TheproosedmethodhashihaccuracnsolvinheRamseumberpgyigtyn,bettermaximumaccelerationratioandexecutionefficiencandstronomutationalerformance.ygcpp

:;;M;Kewordssettheorcomuteralorithm;RamseumbersolutionaReducmodelsinlecoreCPUypgynpgy-

comuteralorithmanditsnumericalvaluewasverifiedtosolvetheRamseumber.Thepgyn

目前,提高计算水平的两种有效方法分别为基于集群的分布式编程和基于集合理论的多线程并发

]1

编程,这两种方法顺应了处理器超线程和多核化的发展轨迹[.为处理密集型数据,可同时处理海量

数据的并行编程模型应运而生,且逐渐出现了许多改进模型,执行过程中效率较高的是基于集合理论共享存储的体系.在求解Ramsey数的过程中,重点任务是通过指数级增加与着色情形观测图的顶点

收稿日期:2018-03-03.

—),男,汉族,硕士,副教授,从事应用数学和计算机算法应用的研究,:作者简介:白云霄(1974E-mailbaiunxiao@sust.edu.cn.y)基金项目:陕西省教育厅专项科研计划项目(批准号:14JK1081.

8 吉林大学学报(理学版) 第57卷

]2个数增长[.传统基于单核DNA计算机算法在求解Ramsey数过程中,无法高效率求解高速提升的

运算量,求解过程耗时较高,计算结果也存在较大偏差.基于此,本文采用基于集合理论的计算机算1 基于集合理论的计算机算法1.1 基于集合理论的MaReduce系统 为适合使用多个处理器应采取并行编程,对于一个用户,p

3]像消息传递模型这类传统并行编辑方法会浪费较长的时间及大量的精力[.用户亲自建造线程,利用

法对Ramsey数进行求解,以提高求解效率和准确性.

线程锁机制同步线程或利用消息传递模式,手工对数据进行控制,能更准确地控制程序的并发性.为大学计算机系统实验室开发了基于集合理论共享内存的Phoenix和Phoenix++版本的MaReduce系p

4]

,这些系统是基于集合理论的计算机算法,其在求解R统,解决了上述弊端[amsey数中具有加速比

了不重复编写代码,应转移程序在各系统间的位置.为最大程度简化繁琐的并行程序,美国Stanford及执行效率较高的优势.

1.2 Phoenix++系统及其执行流程 Phoenix系统验证了MaReduce模型适用于共享存储计算机,p

但Stanford大学计算机系统实验室为避免其局限性重新编写了Phoenix系统.更新后的Phoenix++系统更便于用户研发特制的程序,使程序模型更具有灵活性.Phoenix++系统比Phoenix系统提高了扩展性与功能性,同时,使用者编写MaReduce代码时更简便和严谨.p

图1为基于集合理论的Phoenix++系统执行流程.系统给每个内核衍生的Worke线程数量是可用的内核数目,这是由于MaReduce模型经常处理数据密集型工作.调度器初始化运行时,使用者会pReduce或Maork线程分配而来.所有的Reduce或Map工作都被每个内核所产生的wp工作线程的创

5]

,管理任务过程中通信的缓冲区也由调度器控制.立与运行都由调度器控制[

为功能指针与数值域进行赋值.在初始化后,该计算需要使用的内核数目由调度器决定.一定数目的

图1 Phoenix++系统的执行流程

Fi.1 ExecutionprocessofPhoenix++sstemgy

启动Malit函数割分出部分大小相等的数据块,再由p阶段前,原始输入数据先被调度器用Sp

Maalit函数反馈指针,该指针指向的数据块需要通过Map任务解决.各Mp任务通过调用Spp任务进

6]

,>行操作[键值对.所有具.Maorker线程,进而在产生过程中输出有相等k键值对被分区函数Pekevalueartition集合到一个单元内.此外,需要按照key值的,协助最后的成果排序,M列所有在缓冲区内的束时,调度器才会对Reduce进行初始化.按照keaartition.但当y值分配在Mp任务中的分区函数P

[]出现同一个kealue值与其相关联.此时,为了使负载具有均衡性7,在划分中输y值时,会有大量的v

出键值对的过程中,使用者应自己编写适用于针对具体应用的Partition函数.

求解算法设计 数据集合的划分是设计基于集合理论并行的1.3 基于集合理论的R(C≤k,Km)

,>键值对,按照kReduce任务施行时只能处理具有相同kekevalueeeduce任务y值的所有[8]

的输出结果.在结尾阶段,由一个单缓冲区综合所有的Reduce任务并根据key值排列.融合时存在Loorker线程量用p描述.g个过程,真实过程中W

Worker线程是由Maeduce任务动态分配的.当任务与任务之间全部时,Map任务与Rp任

,>务正在处理<键值对.施行Rkevalueeduce任务的各Worker间负载具有不均衡性,这是由于y

第3期 白云霄:基于集合理论的求解Ramsey数算法 9

下面以1个Reduce和q个Map任务为例对本文方法求解过程进行说明:首先将集合

*

中的图分成若干个子集,假设分成q个子集,再用q个MSC≤k,Km)ap处理器对上述子集进行n-1(

Ramsey数求解算法时要考虑的重要因素.因此本文首先对该集合中的图形实施划分,然后用并行算

[9]

法,通过多Map方法对划分后的数据块进行处理.(一一对应处理,其中第i个M1≤i≤ahile循环中各环节的操作后,经历了添边、p任务通过执行wq)

*

删边等操作生成新的子集合SC≤k,Km).将这q个新图的子集合利用Reduce过程进行合并,可得:n,i(

****

()SC≤k,Km)C≤k,Km)∪SC≤k,Km)∪…∪SC≤k,Km).1=Sn(n,1(n,2(n,q(

**

为w 设SC≤k,Km)hile循环的初始值,通过多次迭代逐步构建形成集合SC≤k,Km).在2(i(

Phoenix++系统中,Maeduce过程通过Worker节点实现,因此需在并行计算中多次对Workerp和R

节点进行调用,从而实现多次迭代的目的.本文方法求解流程如图2所示.

图2 本文方法求解流程

Fi.2 Solutionflowchartofproosedmethodgp

由图2可见,本文方法对R(进行并行求解时的实现过程如下:C≤k,Km)

**

);步骤1SC≤k,Km)=Ø;SC≤k,Km)={K2}n=3;n(n-1(*)w)步骤2hile(SC≤k,Km)≠Ø)and(n≤tdon-1(*){:};步骤3SF∪{vF∈SC≤k,Km)1={n}n-1(

)步骤4SSS0=1;1=Ø;)w步骤6orkdeing)M:步骤7aaskipT)步骤10endfor

);步骤5′PartitionSokstbsetsS1≤i≤0t0,i(q))步骤8′foreachG∈Sdo0,i,)步骤11ReduceTask:)w步骤13orkend)}步骤14n++;.

*);步骤9ConstructSC≤k,Km)n,i(

***);步骤12SC≤k,Km)=SC≤k,Km)∪…∪SC≤k,Km)n(n,1(n,q(

时,1.4 DNA计算机算法求解Rasmeasmem,n)y数 基于集合理论的计算机算法求解Ry中的R(

可将R定义为完全图中存在R(个顶点,无论采用何种方法对染色体进行染色,amsem,n)m,n)y数R(均可搜索到红色的m阶完全子图,或是蓝色的n阶完全子图.这需要在数学公式中计算出R(的m,n)上下界,参照RamseNAy的理论和定义,删除符合条件的部分链,通过检测确认最终的试管空间中D是否被完全删除,对求得的值是否满足Ramsey数进行确认.用上述方法对上界和下界之间的每个数

进行验证,获取R(中的具体数值.对R(数的Dm,n)m,n)NA进行求解时,采用的计算机算法框架为:对R(数生成基于下界的解空间;将空间中一部分具备完全子图特征的Dm,n)NA链删除;删除解空间

650 吉林大学学报(理学版) 第57卷

中一些属于完全空图的D数的结果并对结果进行检测.NA链;获取R(m,n)

法生成解空间,将满足完全子图和完全空图的DNA链删除,形成最终试管.然后对最终试管进行检测,确认其是否包含D与p间的等式关系.运用D数NA链,判断R(m,n)NA计算机算法对R(m,n)进行求解是一种基于生成解空间的DNA算法、删除完全子图和完全空图的DNA计算机算法以及检2 实验分析

测子算法的综合性算法.

假设R(的下界为p,用生成解空间的Dm,n)NA计算机算法,通过q个顶点中完全图的边用穷举

,4.00GHzIntelm5-3430CPU,4GB内存,600GB硬盘;软件环境为:Ubuntu13.12(w87_75)Phoenix++,GCC4.7.4,CodeBlocks12.12.实验通过并行运算过程中的加速比Sq和执行效率Ep处理器所用时间;Tp为使用p个处理器所用的时间.p为处理器个数;2.1 正确性评估 实验通过局部测试验证本文方法求解Ramsey的正确性.若判断当n为最大值时的上、下界计算用时较短;当n=9时计算用时最长,计算R(本文方法和传统R(C≤n,Kn+2)C≤n,Kn+1),可见当n=9时本文方法运算效率高于单核D226.18,925.36sNA方法.当n≤9时,检验本文方法是否正确可以通过测算R(与R(得出.表1和表2分别列出了当n=9时本文方C≤n,Kn+1)C≤n,Kn+2)法与传统单核DNA方法的计算结果.当p=4时,当前迭代步骤的顶点数为n,当前迭代步骤中取得的中间图数为g本文方法在当前迭代步骤形成的图数量为HMRC,单核DNA方法在当前迭代步骤形n,表明多核算法MRC正确.

成的图数量为HSRC.由表1和表2可见,单核DAN方法和本文方法在相同计算条件下运行结果相同,

Table1 ResultsofR(C≤9,K1calculatedbtwomethods0)y

顶点数n3456781011121314151617181920219

ng下面用本文方法对完全图的Ramse数求解圈集时的性能进行检测.实验硬件环境为:4核8线程

/检测本文方法求解R其中:amseT1Tp和Ep=SP/T1为本文方法y时的性能,两个指标设置为Sp,q=本文方法是否正确,应先计算当n取小数值时本文方法的正确性.当n<9时,与R(C≤n,Kn+1);计算R(单核D本文方法和单核DNA方法分别用时16.37,68.85sC≤n,Kn+2)NA方法分别用时

表1 两种方法对R(的计算结果C≤9,K10)

123102210522010122107348245504338240125210510466

迭代1次()12

()23()34()55

HMRC

迭代2次迭代1次

HSRC

迭代2次

()105()227()468()210()3012()114()415()811()19

()1049()50110()12013()46114()21

()198111

()207412()300513()316214()201815()120417()5518

()67816

()18217()319()920()1210

()3616()124015()201616()50318()18619

第3期 白云霄:基于集合理论的求解Ramsey数算法

Table2 ResultsofR(C≤9,K1calculatedbtwomethods1)y

表2 两种方法对R(的计算结果C≤9,K11)

651

顶点数n3456781011121314151617181920219

ng123102210521210872582104731570421020202141215817615551527466

迭代1次()12

()23()34()65

HMRC

迭代2次迭代1次

HSRC

迭代2次

()105()227()468()19()3012()114()515()3616()2117()519()3620()221()423()210()911

()1049

()22

()51010()105611()166715()520316()114618()438619()27721()43322()12013()47714

()865814

()1016315()1051217()1092818()658120()119121

()153018

()245012()505813

评估本文方法的性能.设4≤n≤12.2 性能评估 下面基于R(C≤n,Kn+2)0,因为硬件环境为4核

时8线程CPU,所以对核数为8时也进行测评.不同处理器数目p情形下本文方法求解R(C≤n,Kn+2)的加速比S和执行效率E分别列于表3和表4,其中:T1表示使用单处理器计算所花费的时间;Tp表

示使用p个处理器所花费的时间.

Table3 AccelerationratioSandexecutionefficiencithp=2,3yEw

0.180.291.3047.404.44/T2s

1.571.621.631.661.741.1.82

表3 p=2,3时的加速比S和执行效率E顶点数n45678109

0.310.512.177.93

/T1s

S2

/%E2

83.9885.4986.7887.4791.4594.5195.49

0.120.190.752.88

/T3s

2.352.372.2.582.612.792.76

S3

/%E3

81.81.5687.2288.56.52.2294.56

12833.3

919.32

88.58

7109.49

473.97

顶点数n45678109

0.320.412.198.13

/T1s

Table4 AccelerationratioSandexecutionefficiencithp=4,8yEw

0.090.050.6224.372.31/T4s

3.183.143.153.213.413.513.68

表4 p=4,8时的加速比S和执行效率E4746.14

318.91

31.87

S4

/%E4

79.6880.1480.4882.8687.98.4691.47

0.390.480.672.35

/T8s

0.780.872.813.163.213.483.62

S8

/%E810.8835.4739.7740.4933.7745.529.85

由表3和表4可见,当p=2,3,4,8时,随着顶点数n的增加,执行效率处于上升趋势.本文方法

进行并行运算耗费的时间明显低于程序运行时间;如果n取值较小,则表示程序处理的图数量较少,

12833.32

919.31

88.59

3653.44

243.33

3631.19

245.18

25.87

652 吉林大学学报(理学版) 第57卷

与并行相关的时间开销所占比例较大;如果n取值较大,则表示程序处理的图数量较多,程序运行时间远高于并行相关的时间开销.图3为本文算法操作的图数统计结果.由图3可见,顶点数越大,程序处理的图数量越多.

综合分析可知,当p=2时,随着n值的不断增加,本文方法的执行效率呈上升趋势,其值从

图3 本文方法操作的图数

83.98%提升至95.49%;当p=3时,随着n值的增加,本文方法的执行效率值从81.%提升到

94.56%;当p=4时,本文方法的执行效率值从Fi.3 Numberofgrahsoeratedbroosedmethodgppypp79.68%提升到91.47%,4核情形下本文方法的执行效率略小于2核和3核,但该情形下本文方法的加速比提升至3.68,说明此情形下本文方法的性能较佳;当p=8时,随着n值的增加,本文方法加速比提升至3.62,但本文方法的执行效率降低,导致该现象的原因是本文方法运行的硬件环境是4核得最佳的Ramsey数求解结果.

8线程,如果程序完全占用CPU,则无法响应其他线程申请,形成阻塞问题,降低本文方法的运算性能.所以应综合分析程序加速比和执行效率,本文方法求解Ramsey时应采用4核进行运算,才能获DNA计算机算法存在的运算复杂度高及准确性差的问题,提高了Ramsey数求解加速比和执行效率,效果较好.

参

考

文

献

[]社会科学1] 张春勤,陆维特.改进RamseJ.浙江理工大学学报(y模型的城市公共交通分时段定价方法研究[

综上所述,本文采用一种基于集合理论的计算机算法对Ramsey数进行求解,解决了传统单核

[]:2] 施建中,李荣,杨勇.一种新的区间二型模糊集合降阶算法[J.计算机应用研究,2017,34(2)378-381.

,():)AlicationResearchofComuters2017,342378-381.ppp

(,,YANSHIJianzhonLIRonGYon.NewIntervalTe2FuzzetsTeReductionAlorithm[J].gggypySypg

():)2017,31-496.

]),TransortBasedonImrovedRamseodel[J.JournalofZheianciTechUniversitSocialSciencesppyMjgSy(-

,():,版)2017,31-496.(ZHANGChuninLUWeite.ResearchontheTimeBasedPricinfUrbanPublicqgo-

[3] MACIÁ-PÉREZF,BERNA-MARTINEZJV,OLIVAAF,etal.AlorithmfortheDetectionofOutliersBasedg[]:均值算法[4] 孙志鹏,钱雪忠,吴秦,等.基于加权距离计算的自适应粗糙K-J.计算机应用研究,2016,33(7)

,,WUQ,1987-1990.(SUNZhienQIANXuezhoninetal.SelfadativeRouhK-MeansAlorithmBasedonpggpgg-],():)WeihtedDistance[J.AlicationResearchofComuters2016,3371987-1990.gppp],ontheTheorfRouhSets[J.DecisionSuortSstems2015,75:63-75.yogppy

[]5] 韩英杰,朱维军,焦林枫,等.线性时序逻辑公式XNA计算方法[J.小型微型计算机系统,p模型检测的D

(:,,,2017,383)553-558.(HANYinieZHUWeiunJIAOLinfenetal.DNAComutinethodsofLTLgjjgpgM],():)ModelCheckinnXJ.JournalofChineseComuterSstems2017,383553-558.gop[py

[]:,6] 谭莉,应石.多目标优化机制下DNA编码序列模型[J.计算机工程与应用,2016,52(15)34-37.(TANLi

,():)andAlications2016,521534-37.pp

]YINGShi.MultiObectiveOtimizationMechanismforDNACodineuenceModel[J.ComuterEnineerinjpgSqpgg

[7] MORAESER,POONJK,BALAKRISHNANK,etal.TowardsComonentBasedValidationofGATE:p-[],():8] 周治平,赵晓晓,邵楠楠.结合模糊集合与D-S证据理论的WSN信任评估模型[J.系统仿真学报,2018304

,,1229-1236.(ZHOUZhiinZHAOXiaoxiaoSHAONannan.TrustEvaluationModelBasedonFuzzetandD-SpgyS],,():)EvidenceTheorinWirelessSensorNetwork[J.JournalofSstemSimulation20183041229-1236.yy],():AsectsoftheCoincidenceProcessor[J.PhsicaMedica2015,31143-48.py

[]():9] 朱维军,周清雷,张钦宪.基于DNA计算的线性时序逻辑模型检测方法[J.计算机学报,2016,3912

,,2578-2597.(ZHUWeiunZHOUQinleiZHANGQinxian.ALTLModelCheckinroachBasedonDNAjggApp],():)ComutinJ.ChineseJournalofComuters2016,39122578-2597.pg[p

(责任编辑:韩 啸)