請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/67282
標題: | 快速生成無尺度隨機網路之非揮發性記憶體感知演算法 A Fast Non-Volatile Memory aware Algorithm for Generating Random Scale-Free Networks |
作者: | Cheng-Chin Tu 杜承錦 |
指導教授: | 郭大維(Tei-Wei Kuo) |
關鍵字: | 隨機網路,非揮發性記憶體,網路生成演算法, Non-Volatile Memory,Scale-Free Network,BA model, |
出版年 : | 2017 |
學位: | 碩士 |
摘要: | 本論文提出實現Barab’asi-Albert網路模型的方法以優先連接機制生成大型無尺度(scale-free)網路。據我們所知,BA模型即有的實現方式並非最和諧的管理生成無尺度網路的資料因而效率不佳。為了解決此問題,我們提出包含前綴和遞減堆積與索引陣列的資料結構適合地管理連接數不同的各個節點。提出的方法有利於使用非揮發性記憶體為主要記憶體的計算機系統,減少寫入延遲是提升非揮發性記憶體效能的關鍵,而此方法不僅可以節省讀出作業亦可減少非常多量的寫入次數。本篇在實驗階段比較提出的方法和既有的實作方式生成102至108大小的網路圖,實驗結果顯示提出的方法可減少約50%的寫入次數,再來如果使用相變記憶體這一種非揮發性記憶體為系統的主要記憶體,提出的方法在相較之下可加快至1.92倍。 In this paper, we propose a method to realize the Barab´asi-Albert (BA) model for generating large scale-free networks with preferential attachment. To our knowledge, the existing implementations of the BA model are still not very efficient because they fail to manage the temporary data of scale-free networks properly by ignoring the inherent property. To address this problem, we propose to leverage data structures containing a prefix sum max heap and index arrays, which can competently manage nodes with different amount of connections. The proposed method is also friendly to the computing system with non-volatile memory as main memory. Reducing long-latency write operations is the key to improve the efficiency of NVM memory, while the proposed method can ultimately save not only read operations but also significant amount of writes. We compare our proposed method with the baseline methods by generating networks of size from 102 nodes to 108 nodes. Experiment results show that the proposed method can save up to 50% of write counts. Furthermore, when the phase change memory, a kind of non-volatile memory, is used as main memory, the proposed method can be 1:92 faster. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/67282 |
DOI: | 10.6342/NTU201702670 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-106-1.pdf 目前未授權公開取用 | 1.95 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。