請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/19524
標題: | 巨量社群資料之融合GPU與CPU之高效率影響力最大化演算法 An Efficient GPU-CPU Monte Carlo Simulation Algorithm for Influence Maximization in Large Scale Graphs |
作者: | Chien-Chih Tseng 曾建智 |
指導教授: | 郭大維(Tei-Wei Kuo) |
關鍵字: | 影響力最大化,異質運算,蒙地卡羅模擬,巨量社群網路, influence maximization,heterogeneous computing,Monte-Carlo simulation,large-scale social networks, |
出版年 : | 2016 |
學位: | 碩士 |
摘要: | 影響力最大化演算法是一個在社群網路中尋找一組高影響力的個體,使得在特定的訊息傳播模型下能夠讓總體影響力達到最大化的NP難度的問題,雖然基於蒙地卡羅模擬的演算法能夠有理論上的保證來產生近似於最佳解的結果,時間上的高複雜度使得此種方法難以應用到巨量社群網路。因此一些基於經驗法則的演算法為了解決蒙地卡羅模擬演算法的高耗時問題,犧牲了答案的精確度理論保證來大幅提升時間效率。另一方面,隨著GPU開始被大量使用於加速一般應用程式,一些研究也顯示了GPU在應用於圖論演算法的加速潛力,此外隨著近年來異質運算平台像是OpenCL以及HSA的發展,CPU與GPU之間的共同運算也變得較以往容易許多。因此我們提出了一個在GPU-CPU異質多核心平台上的高效率影響力最大化演算法,基於蒙地卡羅模擬的方法且利用GPU的平行運算處理能力來加速影響力值模擬計算,此外也提出了一些技巧來進一步加速我們的演算法。實驗結果顯示和現有獨立使用CPU以及GPU運算的蒙地卡羅模擬演算法相比,我們的演算法能夠有數百倍的加速卻仍然能保持相同的答案精確度。 Influence maximization is an NP-hard problem to find a small set of highly influential individuals in a social network to maximize the influence spread under a specific information propagation model. While the Monte-Carlo-simulation-based algorithms produce near-optimal solutions with a theoretical guarantee, these algorithms run extremely slow for large-scale networks. Therefore, many heuristic algorithms have been proposed without theoretical guarantee, compromising the quality of solution with time efficiency. On the other hand, graphics processing unit (GPU) has recently been widely used as a popular general-purpose computing device and shown promising potential in accelerating the computation of some graph algorithms. In addition, the development of heterogeneous computing frameworks such as OpenCL and HSA makes the collaboration of CPU and GPU much more easily than before. As a result, we propose an efficient GPU-CPU algorithm for influence maximization problem on heterogeneous platform, which is based on the Monte-Carlo-simulation-based approach, where we leverage the parallel processing capability of GPU for large number of independent influence spread calculations. Moreover, several techniques are presented in this paper to accelerate the algorithm. The experimental results show the speedup over the state-of-the-art Monte-Carlo-simulation-based algorithms for CPU and GPU respectively with up to two orders of magnitude while maintaining the quality of solution. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/19524 |
DOI: | 10.6342/NTU201600155 |
全文授權: | 未授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-1.pdf 目前未授權公開取用 | 2.61 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。