臺灣博碩士論文加值系統

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

口試委員會審定書i
Acknowledgments ii
致謝iii
中文摘要iv
Abstract v
1 Introduction 1
2 Preliminaries 4
2.1 Barab´asi-Albert model . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Main Memory: from RAM to Non-volatile Memory . . . . . . . . . . . . 4
2.3 Implementation and Related Work . . . . . . . . . . . . . . . . . . . . . 6
3 Methodoloy 10
3.1 Prefix Sum Max Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Prefix Sum Max Heap & Index Array . . . . . . . . . . . . . . . . . . . 11
4 Experiment 14
4.1 Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Efficiency and Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3 Endurance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5 Conclusion 20
Bibliography 21

[1] igraph - the network analysis package. http://igraph.org/, 2015. R. Albert and A.-L. Barab´asi. Statistical mechanics of complex networks. Reviewsof Modern Physics, 74:47–97, Jan. 2002.[3] A.-L. Barab´asi and R. Albert. Emergence of scaling in random networks. Science,286(5439):509–512, 1999.[4] G. E. Blelloch. Prefix sums and their applications. 1990.[5] S. Chen, P. B. Gibbons, and S. Nath. Rethinking database algorithms for phasechange memory. January 2011.[6] J. Han, J. Pei, and M. Kamber. Data mining: concepts and techniques. Elsevier,2011.[7] L. Jiang, B. Zhao, J. Yang, and Y. Zhang. A low power and reliable charge pump designfor phase change memories. In 2014 ACM/IEEE 41st International Symposiumon Computer Architecture (ISCA), pages 397–408, June 2014.[8] L. Jiang, B. Zhao, Y. Zhang, J. Yang, and B. R. Childers. Improving write operationsin mlc phase change memory. In IEEE International Symposium on High-Performance Comp Architecture, pages 1–10, Feb 2012.[9] H. A. Khouzani, C. Yang, and J. Hu. Improving performance and lifetime of drampcmhybrid main memory through a proactive page allocation strategy. In The 20thAsia and South Pacific Design Automation Conference, pages 508–513, Jan 2015.[10] D. Lazer, A. S. Pentland, L. Adamic, S. Aral, A. L. Barabasi, D. Brewer, N. Christakis,N. Contractor, J. Fowler, M. Gutmann, et al. Life in the network: the comingage of computational social science. Science (New York, NY), 323(5915):721, 2009.[11] B. C. Lee, E. Ipek, O. Mutlu, and D. Burger. Architecting phase change memoryas a scalable dram alternative. SIGARCH Comput. Archit. News, 37(3):2–13, June2009.21[12] C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J.Reddi, and K. Hazelwood. Pin: Building customized program analysis tools withdynamic instrumentation. In Proceedings of the 2005 ACM SIGPLAN Conferenceon Programming Language Design and Implementation, PLDI ’05, pages 190–200,New York, NY, USA, 2005. ACM.[13] T. Nito, Y. Nagasaka, and H. Uchigaito. Large-scale bsp graph processing in distributednon-volatile memory. In Proceedings of the GRADES’15, GRADES’15,pages 1:1–1:6, New York, NY, USA, 2015. ACM.[14] C. Pan, M. Xie, J. Hu, Y. Chen, and C. Yang. 3m-pcm: Exploiting multiple writemodes mlc phase change main memory in embedded systems. In Proceedings of the2014 International Conference on Hardware/Software Codesign and System Synthesis,CODES ’14, pages 33:1–33:10, New York, NY, USA, 2014. ACM.[15] M. Qiu, Z. Ming, J. Li, K. Gai, and Z. Zong. Phase-change memory optimization forgreen cloud with genetic algorithm. IEEE Transactions on Computers, 64(12):3528–3540, Dec 2015.[16] M. K. Qureshi, V. Srinivasan, and J. A. Rivers. Scalable high performance mainmemory system using phase-change memory technology. SIGARCH Comput. Archit.News, 37(3):24–33, June 2009.[17] M. Technology. Technical note calculating memory system power forddr3. https://www.micron.com/support/tools-and-utilities/power-calc, 2017.[18] J. Yue and Y. Zhu. Making write less blocking for read accesses in phase changememory. In 2012 IEEE 20th International Symposium on Modeling, Analysisand Simulation of Computer and Telecommunication Systems, pages 269–277, Aug2012.[19] C. Zang, P. Cui, and C. Faloutsos. Beyond sigmoids: The nettide model for socialnetwork growth, and its applications. In Proceedings of the 22Nd ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining, KDD ’16,pages 2015–2024, New York, NY, USA, 2016. ACM.[20] P. Zhou, B. Zhao, J. Yang, and Y. Zhang. A durable and energy efficient mainmemory using phase change memory technology. SIGARCH Comput. Archit. News,37(3):14–23, June 2009.