| DC 欄位 |
值 |
語言 |
| DC.contributor | 資訊工程學系 | zh_TW |
| DC.creator | 王伯倫 | zh_TW |
| DC.creator | Po-Lun Wang | en_US |
| dc.date.accessioned | 2023-12-11T07:39:07Z | |
| dc.date.available | 2023-12-11T07:39:07Z | |
| dc.date.issued | 2023 | |
| dc.identifier.uri | http://ir.lib.ncu.edu.tw:88/thesis/view_etd.asp?URN=110522007 | |
| dc.contributor.department | 資訊工程學系 | zh_TW |
| DC.description | 國立中央大學 | zh_TW |
| DC.description | National Central University | en_US |
| dc.description.abstract | 由於社群網路應用以及和圖形資料庫系統的普及，大規模圖形 (Large-scale Graph) 已經變成了應用在資料挖掘及深度學習中的主流資料結構。然而，現代計算機系統中有限的隨機存取記憶體 (Dynamic Random-access Memory) 空間，是對整個大規模圖形進行同時處理的挑戰。因此，考慮到可用的計算機資源，將大規模圖形分成多個子圖進行並行處理是有其必要性的。不過，現今的圖分割 (Graph Partitioning) 方法，無法在圖分割的過程中，完善的處理讀取和儲存對於儲存裝置所造成的負擔。
為了在圖分割的過程中找到最佳分割邊，以確保在子圖平衡的同時也能保留大規模圖形的原始特性，我們必須常常對儲存裝置進行加載或是存儲，又因為 NAND 快閃記憶體的基本讀寫單元為一個頁面，使得這樣的問題變得更為嚴重。本文介紹了 GraLoc，一種圖分割解決方法，旨在考慮資料擺放時的圖形局部性，使其更適合應用於 NAND 快閃記憶體。為了減少圖分割過程中所造成的讀取放大 (Read Amplification)，目標是最大化在單一頁面中的圖形局部性，我們的實驗結果展現出圖分割過程中在儲存效能的顯著進步。 | zh_TW |
| dc.description.abstract | 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. | en_US |
| DC.subject | 圖形數據 | zh_TW |
| DC.subject | NAND 快閃記憶體 | zh_TW |
| DC.subject | 局部性 | zh_TW |
| DC.subject | 邊分割 | zh_TW |
| DC.subject | Graph data | en_US |
| DC.subject | NAND flash memory | en_US |
| DC.subject | Locality | en_US |
| DC.subject | Edge partitioning | en_US |
| DC.title | GraLoc: Preserving Graph Locality to Minimize Read and Write Amplification on NAND Flash Memory | en_US |
| dc.language.iso | en_US | en_US |
| DC.type | 博碩士論文 | zh_TW |
| DC.type | thesis | en_US |
| DC.publisher | National Central University | en_US |