基于多核的極圖構(gòu)造并行算法研究的開題報(bào)告一、選題背景及意義：在計(jì)算科學(xué)領(lǐng)域，極圖（PolarGraph）是一種新近提出的圖論模型。極圖建立在極坐標(biāo)系統(tǒng)上，將節(jié)點(diǎn)按照極角與半徑分布，可以用于解決實(shí)際中多種問題包括通信網(wǎng)絡(luò)，社交關(guān)系、生物多樣性等等。極圖的性質(zhì)與歐幾里得圖不同，現(xiàn)有的常規(guī)算法不能直接應(yīng)用于極圖中。因此，如何在極圖的基礎(chǔ)上進(jìn)行算法的構(gòu)造和研究，成為當(dāng)前計(jì)算科學(xué)領(lǐng)域的熱點(diǎn)問題。在本課題中，我們將著重針對多核極圖并行算法這一方向展開研究。計(jì)算機(jī)硬件技術(shù)的飛速發(fā)展，多核處理器在市場中的普及與推廣，已經(jīng)成為當(dāng)前高性能計(jì)算的趨勢。多核的出現(xiàn)為并行計(jì)算提供了強(qiáng)有力的支持，對于解決大規(guī)模圖應(yīng)用問題具有較大的優(yōu)勢。而針對極圖這種特殊的圖論模型，其并行處理的方法和技巧還沒有得到充分的探究和發(fā)揮。因此，本次研究的開展對于多核處理器對極圖處理的應(yīng)用有著重要的意義和實(shí)際意義。二、研究內(nèi)容：（1）研究極圖的表示方法、特性及其算法設(shè)計(jì)過程；（2）研究多核處理器上極圖的并行計(jì)算體系結(jié)構(gòu)與并行化算法設(shè)計(jì)；（3）基于多核的極圖構(gòu)造并行算法研究；（4）設(shè)計(jì)并實(shí)現(xiàn)針對極圖多核并行處理的算法，并進(jìn)行性能測試與評估。三、預(yù)期研究成果：（1）了解極圖的基礎(chǔ)知識與相關(guān)的算法設(shè)計(jì)過程；（2）掌握多核并行處理器的體系結(jié)構(gòu)和并行化算法設(shè)計(jì)的方法與技巧；（3）研究極圖在多核處理器上的并行處理方法，設(shè)計(jì)有效的算法實(shí)現(xiàn)方案；（4）實(shí)現(xiàn)針對極圖多核并行處理的算法，并對算法性能進(jìn)行性能測試與評估，驗(yàn)證算法的正確性和有效性。四、擬定工作計(jì)劃：（1）文獻(xiàn)綜述：查閱極圖的相關(guān)文獻(xiàn)及多核并行處理器的研究進(jìn)展，了解研究背景和進(jìn)展；（2）算法設(shè)計(jì)：研究多核處理器上極圖并行計(jì)算的算法，設(shè)計(jì)并實(shí)現(xiàn)具有高性能的算法；（3）系統(tǒng)實(shí)現(xiàn)及性能測試：實(shí)現(xiàn)以上算法，并基于多核處理器進(jìn)行性能測試評估；（4）論文撰寫：根據(jù)研究成果完成論文撰寫。五、研究難點(diǎn)：（1）極圖的特殊性質(zhì)給多核并行處理帶來了新的挑戰(zhàn)；（2）如何利用多核處理器提升算法的并行計(jì)算效率；（3）如何設(shè)計(jì)一種高效的極圖算法。六、研究方法：（1）文獻(xiàn)調(diào)研和綜述；（2）算法設(shè)計(jì)和系統(tǒng)實(shí)現(xiàn)；（3）性能測試和評價(jià)。七、參考文獻(xiàn)：[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]吳志勇,朱旭起,韓旭,等.概率極圖及其在多智能體系統(tǒng)中的作用[J].清華大學(xué)學(xué)報(bào)(自科版),2016,56(12):1143-1