快速生成無尺度隨機網路之非揮發性記憶體感知演算法

A Fast Non-Volatile Memory aware Algorithm for Generating Random Scale-Free Networks

杜承錦(Cheng-Chin Tu)

指導教授 ： 郭大維

共同指導教授 ： 葉彌妍(Mi-Yen Yeh)

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201702670

摘要

本論文提出實現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.

並列關鍵字

Non-Volatile Memory ； Scale-Free Network ； BA model