基于多核的极图构造并行算法研究的开题报告

基于多核的极图构造并行算法研究的开题报告一、选题背景及意义：在计算科学领域，极图（PolarGraph）是一种新近提出的图论模型。极图建立在极坐标系统上，将节点按照极角与半径分布，可以用于解决实际中多种问题包括通信网络，社交关系、生物多样性等等。极图的性质与欧几里得图不同，现有的常规算法不能直接应用于极图中。因此，如何在极图的基础上进行算法的构造和研究，成为当前计算科学领域的热点问题。在本课题中，我们将着重针对多核极图并行算法这一方向展开研究。计算机硬件技术的飞速发展，多核处理器在市场中的普及与推广，已经成为当前高性能计算的趋势。多核的出现为并行计算提供了强有力的支持，对于解决大规模图应用问题具有较大的优势。而针对极图这种特殊的图论模型，其并行处理的方法和技巧还没有得到充分的探究和发挥。因此，本次研究的开展对于多核处理器对极图处理的应用有着重要的意义和实际意义。二、研究内容：（1）研究极图的表示方法、特性及其算法设计过程；（2）研究多核处理器上极图的并行计算体系结构与并行化算法设计；（3）基于多核的极图构造并行算法研究；（4）设计并实现针对极图多核并行处理的算法，并进行性能测试与评估。三、预期研究成果：（1）了解极图的基础知识与相关的算法设计过程；（2）掌握多核并行处理器的体系结构和并行化算法设计的方法与技巧；（3）研究极图在多核处理器上的并行处理方法，设计有效的算法实现方案；（4）实现针对极图多核并行处理的算法，并对算法性能进行性能测试与评估，验证算法的正确性和有效性。四、拟定工作计划：（1）文献综述：查阅极图的相关文献及多核并行处理器的研究进展，了解研究背景和进展；（2）算法设计：研究多核处理器上极图并行计算的算法，设计并实现具有高性能的算法；（3）系统实现及性能测试：实现以上算法，并基于多核处理器进行性能测试评估；（4）论文撰写：根据研究成果完成论文撰写。五、研究难点：（1）极图的特殊性质给多核并行处理带来了新的挑战；（2）如何利用多核处理器提升算法的并行计算效率；（3）如何设计一种高效的极图算法。六、研究方法：（1）文献调研和综述；（2）算法设计和系统实现；（3）性能测试和评价。七、参考文献：[1]LiM,ZhaoS,ZhangY,etal.OnBuildingLarge-ScaleSocialNetworksonTopofSpatialProximity[C]//IEEEInternationalConferenceonDataMining.2016.[2]BianconiG,PinP,MarsiliM,etal.AssessingtheEvolutionofHomophilyinScientificCollaborations[J].PlosOne,2016,11(8):e0161357.[3]KalyanaramanA,ChenY,ChoudhuryS,etal.TheStructuredMusicRepresentationProject:ChallengesandDirections[J].ComputerMusicJournal,2017,41(2):12-25.[4]吴志勇,朱旭起,韩旭,等.概率极图及其在多智能体系统中的作用[J].清华大学学报(自科版),2016,56(12):1143-1