請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/98225完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 郭斯彥 | zh_TW |
| dc.contributor.advisor | Sy-Yen Kuo | en |
| dc.contributor.author | 吳建賢 | zh_TW |
| dc.contributor.author | Chien-Hsien Wu | en |
| dc.date.accessioned | 2025-07-30T16:24:21Z | - |
| dc.date.available | 2025-07-31 | - |
| dc.date.copyright | 2025-07-30 | - |
| dc.date.issued | 2025 | - |
| dc.date.submitted | 2025-07-28 | - |
| dc.identifier.citation | [1] Assefaw Hadish Gebremedhin, Fredrik Manne, and Alex Pothen. What color is yourjacobian? graph coloring for computing derivatives. SIAM Rev., 47:629–705, 2005.
[2] Maxim Naumov, Patrice Castonguay, and Jonathan Cohen. Parallel graph coloring with applications to the incomplete-lu factorization on the gpu. Nvidia White Paper, 2015. [3] Umit Catalyurek, John Feo, Assefaw Gebremedhin, Mahantesh Halappanavar, and Alex Pothen. Graph coloring algorithms for muti-core and massively multithreaded architectures, 2012. [4] S. M. Ferdous, Reece Neff, Bo Peng, Salman Shuvo, Marco Minutoli, Sayak Mukherjee, Karol Kowalski, Michela Becchi, and Mahantesh Halappanavar. Picasso: Memory-Efficient Graph Coloring Using Palettes With Applications in Quantum Computing. 1 2024. [5] M Luby. A simple parallel algorithm for the maximal independent set problem. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC ’85, page 1–10, New York, NY, USA, 1985. Association for Computing Machinery. [6] Mark T. Jones and Paul E. Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, 14(3):654–669, 1993. [7] Ghadeer Alabandi, Evan Powers, and Martin Burtscher. Increasing the parallelism of graph coloring via shortcutting. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’20, page 262–275, New York, NY, USA, 2020. Association for Computing Machinery. [8] William Hasenplaugh, Tim Kaler, Tao B. Schardl, and Charles E. Leiserson. Ordering heuristics for parallel graph coloring. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’14, page 166–177, New York, NY, USA, 2014. Association for Computing Machinery. [9] Dominic J. A. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. Comput. J., 10:85–86, 1967. [10] James R. A. Allwright, Rajesh R. Bordawekar, Paul D. Coddington, Kivanç Dinçer, and Christine Martin. A comparison of parallel graph coloring algorithms. 1995. [11] David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. J. ACM, 30(3):417–427, jul 1983. [12] George Karypis and Vipin Kumar. METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices, September 1998. [13] Ian Bogle, Erik G. Boman, Karen Devine, Sivasankaran Rajamanickam, and George M. Slota. Distributed memory graph coloring algorithms for multiple gpus. In 2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3), pages 54–62, 2020. [14] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014. [15] Tim Davis and Yifan Hu. Suitesparse matrix collection. https://sparse.tamu.edu/. Accessed: 2021-05-06. [16] Michael Trick. COLOR graph coloring instances. https://mat.tepper.cmu. edu/COLOR/instances/, 2018. Carnegie Mellon University, accessed on 2025-03-31. [17] DIMACS, Center for Discrete Mathematics and Theoretical Computer Science. Dimacs challenge graph instances. http://www.dis.uniroma1.it/challenge9/download.shtml. Accessed: 2021-05-06. [18] Galois Project, ISS - The University of Texas at Austin. Galois graph benchmark suite. https://iss.oden.utexas.edu/?p=projects/galois. Accessed: 2021-05-06. [19] Xuhao Chen and Li. Csrcolor. https://github.com/chenxuhao/csrcolor, 2021. Last accessed on May 6, 2021. [20] Xuhao Chen, Pingfan Li, and Canqun Yang. Efficient and high-quality sparse graph coloring on the GPU. CoRR, abs/1606.06025, 2016. [21] Mehmet Deveci, Erik G Boman, Karen D. Devine, and Sivasankaran ajamanickam. Parallel graph coloring for manycore architectures. In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 892–901, 2016. [22] Kokkos-Kernels Developers. Kokkos-kernels. https://github.com/kokkos/kokkos-kernels, 2021. Last accessed on May 6, 2021. [23] Maciej Besta, Armon Carigiet, Kacper Janda, Zur Vonarburg-Shmaria, Lukas Gianinazzi, and Torsten Hoefler. High-performance parallel graph coloring with strong guarantees on work, depth, and quality. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’20. IEEE Press, 2020. [24] Chao-Tung Yang, Chih-Lin Huang, and Cheng-Fang Lin. Hybrid cuda, openmp, and mpi parallel programming on multicore gpu clusters. Computer Physics Communications, 182(1):266–269, 2011. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/98225 | - |
| dc.description.abstract | 圖著色（Graph Coloring）是一種基礎的演算法，目的是將顏色分配給圖形的節點，且相鄰節點不能擁有相同的顏色。在平行圖著色演算法中，主要評估兩個參數：顏色的品質與執行速度。我們提出的優化包含兩個部分：
首先，我們重新設計 JP-SL 的優先級分配流程，以減少全域頂點掃描的次數並在執行過程中更有效地利用平行化。其次，我們將大規模圖劃分為多個子圖，並將其分配至多個 GPU 上同時運行，以進一步提升整體執行效率。 | zh_TW |
| dc.description.abstract | Graph coloring is a fundamental problem involving the assignment of colors to the vertices of a graph, ensuring that no two adjacent vertices possess the same color. In parallel graph coloring, two primary parameters are evaluated: color quality and execution speed. Our optimization methodology has two parts.
We first improve priority allocation by re-engineering JP-SL to minimize global vertex scans and optimize parallelism during execution. Secondly, we enhance the overall runtime by splitting the extensive graph into subgraphs and allocating them across many GPUs for concurrent execution. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2025-07-30T16:24:21Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2025-07-30T16:24:21Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Verification Letter from the Oral Examination Committee i
Acknowledgements iii 摘要 v Abstract vii Contents ix List of Figures xi List of Tables xiii Chapter 1 INTRODUCTION 1 1.0.1 Priority Allocation Optimization . . . . . . . . . . . . . . . . . . . 4 1.0.1.1 Resilient Smallest Degree Last (R-SL) Architecture . . 4 1.0.1.2 Worklist-Based Optimization . . . . . . . . . . . . . . 5 1.0.1.3 Fuzzy Parameter to Reduce Iteration Count . . . . . . . 5 1.0.2 Distributed Graph Coloring Framework . . . . . . . . . . . . . . . 5 Chapter 2 BACKGROUND 7 2.1 Priority Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 JP-LF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.2 JP-SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Color Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Chapter 3 METHODOLOGIES 13 3.1 Priority Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1.1 Resilient SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1.2 Worklist-Based Parallelization . . . . . . . . . . . . . . . . . . . . 14 3.1.3 Fuzzy Parameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Distributed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Chapter 4 EXPERIMENTAL 19 4.1 Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Comparison with Other Algorithms . . . . . . . . . . . . . . . . . . 19 4.2.1 Single-GPU Performance Comparison . . . . . . . . . . . . . . . . 20 4.2.2 GPU vs CPU: Algorithm Comparison . . . . . . . . . . . . . . . . 22 4.3 Impact of Worklist-Based Parallelization . . . . . . . . . . . . . . . 23 4.4 Effect of the Fuzzy Parameter . . . . . . . . . . . . . . . . . . . . . 24 4.5 Ordering Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.6 Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Chapter 5 CONCLUSION 29 References 31 | - |
| dc.language.iso | en | - |
| dc.subject | 平行應用 | zh_TW |
| dc.subject | 平行運算 | zh_TW |
| dc.subject | 演算法設計與分析 | zh_TW |
| dc.subject | 圖著色 | zh_TW |
| dc.subject | 圖演算法 | zh_TW |
| dc.subject | algorithm design and analysis | en |
| dc.subject | parallel applications | en |
| dc.subject | parallel computing | en |
| dc.subject | graph algorithms | en |
| dc.subject | graph coloring | en |
| dc.title | 高品質分散式圖著色演算法 | zh_TW |
| dc.title | Distributed High-Quality Graph Coloring Algorithm on GPUs | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 113-2 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 張耀文;陳俊良 ;雷欽隆;顏嗣鈞 | zh_TW |
| dc.contributor.oralexamcommittee | Yao-Wen Chang;Jiann-Liang Chen;Chin-Laung Lei;Hsu-chun Yen | en |
| dc.subject.keyword | 圖著色,圖演算法,平行運算,平行應用,演算法設計與分析, | zh_TW |
| dc.subject.keyword | graph coloring,graph algorithms,parallel computing,parallel applications,algorithm design and analysis, | en |
| dc.relation.page | 34 | - |
| dc.identifier.doi | 10.6342/NTU202502064 | - |
| dc.rights.note | 同意授權(全球公開) | - |
| dc.date.accepted | 2025-07-30 | - |
| dc.contributor.author-college | 重點科技研究學院 | - |
| dc.contributor.author-dept | 積體電路設計與自動化學位學程 | - |
| dc.date.embargo-lift | 2025-07-31 | - |
| 顯示於系所單位： | 積體電路設計與自動化學位學程 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-113-2.pdf | 2.06 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。