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

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/93537

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/93537

Title:	GraLoc: Preserving Graph Locality to Minimize Read and Write Amplification on NAND Flash Memory
Authors:	王伯倫;Wang, Po-Lun
Contributors:	資訊工程學系
Keywords:	圖形數據;NAND 快閃記憶體;局部性;邊分割;Graph data;NAND flash memory;Locality;Edge partitioning
Date:	2023-12-11
Issue Date:	2024-03-05 17:43:35 (UTC+8)
Publisher:	國立中央大學
Abstract:	由於社群網路應用以及和圖形資料庫系統的普及，大規模圖形 (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.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	67	View/Open

社群 sharing

Loading...