GraLoc: Preserving Graph Locality to Minimize Read and Write Amplification on NAND Flash Memory

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 博碩士論文 > Item 987654321/93537

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/93537

题名:	GraLoc: Preserving Graph Locality to Minimize Read and Write Amplification on NAND Flash Memory
作者:	王伯倫;Wang, Po-Lun
贡献者:	資訊工程學系
关键词:	圖形數據;NAND 快閃記憶體;局部性;邊分割;Graph data;NAND flash memory;Locality;Edge partitioning
日期:	2023-12-11
上传时间:	2024-03-05 17:43:35 (UTC+8)
出版者:	國立中央大學
摘要:	由於社群網路應用以及和圖形資料庫系統的普及，大規模圖形 (Large-scale Graph) 已經變成了應用在資料挖掘及深度學習中的主流資料結構。然而，現代計算機系統中有限的隨機存取記憶體 (Dynamic Random-access Memory) 空間，是對整個大規模圖形進行同時處理的挑戰。因此，考慮到可用的計算機資源，將大規模圖形分成多個子圖進行並行處理是有其必要性的。不過，現今的圖分割 (Graph Partitioning) 方法，無法在圖分割的過程中，完善的處理讀取和儲存對於儲存裝置所造成的負擔。為了在圖分割的過程中找到最佳分割邊，以確保在子圖平衡的同時也能保留大規模圖形的原始特性，我們必須常常對儲存裝置進行加載或是存儲，又因為 NAND 快閃記憶體的基本讀寫單元為一個頁面，使得這樣的問題變得更為嚴重。本文介紹了 GraLoc，一種圖分割解決方法，旨在考慮資料擺放時的圖形局部性，使其更適合應用於 NAND 快閃記憶體。為了減少圖分割過程中所造成的讀取放大 (Read Amplification)，目標是最大化在單一頁面中的圖形局部性，我們的實驗結果展現出圖分割過程中在儲存效能的顯著進步。 ;Due to the prevalence of social network applications and graph database systems, large-scale graphs have become a mainstream data structure for data mining and machine learning. However, the challenge arises from the limited size of dynamic random-access memory (DRAM), preventing the simultaneous processing of entire large-scale graphs in modern computer systems. Consequently, the need arises to partition the overall large-scale graph into multiple sub-graphs for parallel processing and to align with available computing resources. Unfortunately, existing graph partitioning solutions do not adequately address the load/store overhead on the storage device during the partitioning process. As the graph partitioning process involves finding the optimal splitting edge to ensure sub-graph balance and preserve the original properties of the large-scale graph, there is frequent loading from and storing to the storage device. This issue is further exacerbated on NAND flash memory due to its basic read/write unit (i.e., a page size). This paper introduces GraLoc, a graph partitioning solution designed to be NAND flash memory-friendly by considering graph locality during data placement. The proposed solution aims to maximize graph locality within a single page, effectively minimizing read amplification during the graph partitioning process. Our experiments demonstrate a significant improvement in storage performance during graph partitioning.
显示于类别:	[資訊工程研究所] 博碩士論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	67	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....