日(rì)前，四川省計算機研究院（以下簡稱“研究院”）1篇論文《Graph Algorithms with Partition Transparency》被國(guó)際頂級期刊IEEE TKDE正式收錄。此次發表的論文開創性地提出了分(fēn)區透明度的概念，解決了圖算法不能在不同的分(fēn)區下正常工(gōng)作(zuò)的難點問(wèn)題，并能夠進一步提升圖分(fēn)區算法的計(jì)算速度，彰顯了研究院在圖計(jì)算領域全面領先的科(kē)研實力。

目前，爲了處理(lǐ)現實生(shēng)活中的大(dà)型圖，我們常常需要對分(fēn)區圖進行并行計(jì)算。于是，人(rén)們提出了各種圖分(fēn)區算法，包括邊切割、點切割，以及混合分(fēn)區。然而，針對特定圖分(fēn)區方法開發的圖算法不能在其他(tā)圖分(fēn)區下正常工(gōng)作(zuò)，導緻如(rú)需切換到其他(tā)圖分(fēn)區方法，可(kě)能不得(de)不重寫算法。

爲了解決這一問(wèn)題，研究院科(kē)研團隊及其合作(zuò)者開創性地提出了分(fēn)區透明度的概念，這樣圖算法就(jiù)能夠在不同的分(fēn)區下正常工(gōng)作(zuò)而無需更改，同時還(hái)能進一步提升混合分(fēn)區算法的計(jì)算速度。實驗證明：

（1）以圖爲中心模型和以點爲中心模型的透明算法在邊切割、點切割和混合分(fēn)區下都(dōu)能正确工(gōng)作(zuò)，不需要任何修改。

（2）在混合分(fēn)區下的透明算法，比在邊切割和點切割下的算法平均快(kuài)2.3-21.2倍；同樣的，比在邊切割和點切割下的定制算法平均快(kuài)2.8和1.6倍。

（3）即使所有算法都(dōu)在點切割或邊切割的情況下運行，透明算法與爲單個分(fēn)區量身(shēn)定制的算法之間的性能差距也很小，不超過5.8%。

（4）在混合分(fēn)區下，透明算法具有較好的擴展性，還(hái)能較快(kuài)地處理(lǐ)大(dà)型圖。當處理(lǐ)器數量n從(cóng)32變爲160時，平均快(kuài)2.5倍。透明的WCC（weakly connected component）和PR（PageRank）算法在使用90個處理(lǐ)器對具有500M頂點和6B邊的圖進行計(jì)算時，平均花費66.5秒。

論文鏈接：

https://ieeexplore.ieee.org/document/9495146

數讀(dú)研究院科(kē)研成果：

截至2021年(nián)8月23日(rì)，研究院共發表/錄用高水平論文54篇，其中CCF A類44篇；申請(qǐng)專利/PCT共26項，授權發明專利3項。科(kē)研成果比肩全球任何一支大(dà)數據學術(shù)團隊。