基于0-1规划的并行计算图划分模型.pdfVIP

小型微型计算机系统 2011年8月第8期 JournalofChinese VoL32No．82011 ComputerSystems 基于0-1规划的并行计算图划分模型 马永刚，谭国真，王启冬 (大连理工大学计算机科学与技术学院，辽宁大连11(50：24) E-mail：mayonggan92006@hotmail．com；gztan@dlut．cdu．cn 摘要：图划分广泛地应用在许多科学与工程领域。但它应用于并行计算任务分配时，使用无向图表示数据依赖关系，这限帝3 了它的应用(例如，无向图不能表示矩形和非对称依赖关系的应用)．为了克服图划分的这个缺点，我们对数据间的依赖关系进 行区分(即同一条边区分通信的发送方与接收方)，然后基于0一l规划模型化这个问题，并通过互联网上求解优化问题常用的 NEOS服务器进行求解，在一些数据集上的实验表明，O—l规划方法优于求解图划分流行的多层划分方法． 关键词：0．1规划；图划分；并行计算；任务分配 中图分类号：TP393 文献标识码：A 文章编号：1000．1220(2011)08—1613-04 Modelfor PartitioningParallel Basedon0-1 Graph Computing Programming MA Cmo-zhen．WANG Yong-gang-TAN Qi-dong and Technology。DalianUniversity Dalian (SchoolofComputerScience ofTechnologyI116024-Ch／na) is in 8aenceand fields．However。whenis in Abstract：Graphpartitioningwidelyappfiedmany engineering graphpartitioningapplied task in UseSundirectedtO data limitsits the assignmentparallelprocessorsystems-it graphexpress dependencies．whichapplications can not and ordertoovercomethe of representrectanglenon-symmetric (e．g．-undirectedgraph applications)．In shc眦cominggraph thedata isto thesenderandreceiverofthecommunicationwhich partitioning．wedistinguishdependencies-thatsay。wedistinguish is an in model．Thenwemodelthe basedon0·1 model representedby edgegraphpartitioning problem be isa carl solvedNEOS common solverthatisavailableOVertheIntemet．Some results by seFver，which optimization