成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	蔡孟宗 Tsai, Meng-Tsung
論文名稱：	基於 LLVM 之通用圖形處理器控制流程分歧處理與消除技術 LLVM-Based Control-Flow Divergence Handling and Elimination for General-Purpose GPUs
指導教授：	陳中和 Chen, Chung-Ho
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 電機工程學系 Department of Electrical Engineering
論文出版年：	2026
畢業學年度：	114
語文別：	中文
論文頁數：	85
中文關鍵詞：	SIMT 、控制流程分歧、重新合流、STARLIGHT 、分支消除、RISC-V
外文關鍵詞：	SIMT, Control-Flow Divergence, Reconvergence, STARLIGHT, Branch Elimination, RISC-V
相關次數：	點閱：22 下載：0
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

通用圖形處理器（General Purpose Graphics Processing Unit, GPGPU）常以單指令多執行緒（Single Instruction, Multiple Threads, SIMT）模型提升平行吞吐量。然而，當同一個 warp 內的執行緒對條件分支做出不同判斷時，便會產生控制流程分歧，使硬體序列化執行不同路徑。分歧後的成本不僅來自路徑拆分，也取決於執行緒群組能否在共享程式區段之前及時重新合流；若合流過晚，共享區段可能在部分啟用遮罩下被重複執行，進而增加動態指令數與執行週期。

本研究針對基於優先權的 SIMT 分歧處理機制，提出 STARLIGHT，一種具拓樸感知能力的合流策略。STARLIGHT 不依賴直接後支配點、結構化語法或程式計數器順序，而是由控制流程圖推導合流候選點。其方法以忽略回邊後的反向後序建立近似拓樸順序，將多前驅匯合位置視為潛在合流點，並在其附近插入成對的優先權降低與提高操作，使先抵達者暫時讓出排程機會，讓其他路徑有機會於共享區段前合流。為支援實作，本研究亦設計優先權清理與量化程序，以降低冗餘指令成本，並將優先權層級壓縮至硬體可支援的範圍。

除了改善分歧發生後的合流行為，本研究也探討分歧發生前的分支消除，利用 RISC-V Zicond 與 Zfinx/Zdinx 將部分浮點條件選擇降低為無分支指令序列，將控制相依轉換為資料相依，從源頭減少控制流程分歧。其中相關 LLVM RISC-V 後端修改已合併至上游，顯示其工程可行性。

本研究以 Formosa 模擬平台中的 cycle-accurate pipelined SIMT 實作 simtix 進行評估。實驗結果顯示，在 Rodinia 應用程式 kernel 與非結構化合流微型測試程式的整體比較中，STARLIGHT 的正規化執行週期幾何平均為 91.17%，優於 IPDOM 的 96.78%、ICS-First 的 100.75% 與 MinPC 的 102.26%。在浮點條件選擇 kernels 上，FSEL 與STARLIGHT 結合後的正規化執行週期幾何平均為 96.20%，略優於單獨啟用 FSEL 的 96.34%。整體而言，編譯器應同時處理分歧前與分歧後成本：以無分支 lowering 降低可轉換的分歧來源，並以 STARLIGHT 促成剩餘分支較早合流。

General-purpose graphics processing units use the SIMT execution model to obtain high throughput, but warp-level control-flow divergence can serialize different paths and repeatedly execute shared regions under partial active masks. This thesis studies how a compiler can reduce this cost on a priority-based SIMT architecture. It pro-poses STARLIGHT, a topology-aware reconvergence strategy that derives reconver-gence candidates directly from the control-flow graph rather than from immediate post-dominators, structured syntax, or program-counter order. STARLIGHT uses reverse post-order after ignoring back edges, treats multi-predecessor merge points as poten-tial reconvergence sites, and inserts paired priority adjustments so early-arriving thread groups wait while other paths catch up. Cleanup and quantization passes make the in-serted priority operations practical under limited hardware priority levels. This thesis also studies a complementary branch-elimination direction using RISC-V Zicond with Zfinx/Zdinx to lower selected floating-point conditional selects into branchless instruc-tion sequences. Experiments on the Formosa simtix cycle-accurate SIMT platform show that STARLIGHT achieves a normalized geometric mean execution cycle count of 91.17% across Rodinia kernels and unstructured reconvergence microbenchmarks, out-performing IPDOM, ICS-First, and MinPC. On floating-point conditional-select kernels, FSEL with STARLIGHT reaches 96.20%, slightly better than FSEL alone. The results support a combined compiler strategy: remove divergence when possible, and guide re-convergence when branches remain.

摘要 i
英文延伸摘要 ii
誌謝 x
目錄 xii
表格 xv
圖片 xvi
Chapter 1. 緒論 1
1. 研究背景 1
2. 研究動機 2
3. 研究問題 3
4. 研究方法與主要貢獻 3
Chapter 2. 背景知識 5
1. SIMT 執行模型與控制流程分歧 5
2. SIMT 堆疊與基於優先權的控制機制 6
2.1. SIMT 堆疊機制 7
2.2. 基於優先權的控制機制 8
2.3. 兩種機制之比較 10
2.4. 本研究採用基於優先權機制之原因 11
2.5. 理想的重新合流目標 11
2.6. 本章小結 12
Chapter 3. 處理分歧排程之現有方法與限制 13
1. 概述 13
2. 理想的重新合流目標 13
3. IPDOM（Immediate Post-Dominator）方法 14
3.1. 基本概念 14
3.2. 優點 15
3.3. 限制 16
4. ICS-First（Inner Conditional Statements First）方法 18
4.1. 基本概念 18
4.2. 優點 19
4.3. 限制 19
5. MinPC（Minimum PC First）方法 21
5.1. 基本概念 21
5.2. 優點 22
5.3. 限制 23
6. 小結與現有合流方法缺口 24
Chapter 4. STARLIGHT: 具拓樸感知能力之優先權合流方法 26
1. 設計目標與基本想法 26
2. 具拓樸意義的排序觀點 26
3. 合流候選點之辨識 27
4. 優先權配置方式 28
5. 優先權分歧問題 29
6. STARLIGHT 完整演算法 29
7. 討論 31
8. 本章小結 32
Chapter 5. 編譯器實作與輔助最佳化 33
1. 章節概述 33
2. STARLIGHT 之指令插入流程 33
2.1. STARLIGHT 實作摘要 34
3. 優先權清理程序 35
3.1. 設計動機 35
3.2. 同類型操作之合併 37
3.3. 相反操作之抵銷 37
3.4. 為何不能任意消除「先降後升」 38
4. 優先權量化程序 39
4.1. 設計動機 39
4.2. 基本作法 40
4.3. 量化帶來的取捨 40
4.4. 編譯流程整體觀點 40
5. 本章小結 41
Chapter 6. 以 Zicond 與 Zfinx/Zdinx 進行分支消除 42
1. 章節概述 42
2. 以條件分支轉換消除控制流程分歧 42
3. RISC-V Zicond 擴充 43
3.1. Conditional-zero 指令 43
3.2. 以 Zicond 實現無分支選擇 44
4. Zicond 在傳統浮點架構中的限制 45
5. Zfinx/Zdinx 與 GPGPU 架構之關係 45
5.1. Zfinx/Zdinx 的暫存器模型 45
5.2. Zfinx/Zdinx 對無分支浮點選擇的意義 46
6. 結合 Zicond 與 Zfinx/Zdinx 的浮點分支消除 46
7. 與 STARLIGHT 的互補關係 47
8. 本章小結 47
Chapter 7. 實驗設計與結果分析 48
1. 章節概述 48
2. 實驗平台 48
2.1. 整體流程 48
2.2. Formosa 模擬平台與 simtix 實作 49
2.3. 控制變因 49
3. 硬體與軟體設定 50
4. Benchmark 分組 50
5. 比較方法 51
6. 整體合流結果 52
7. Rodinia 應用程式 Kernels 分析 54
8. 非結構化微型測試程式分析 54
9. 分支消除實驗結果 55
10. 案例分析 56
10.1. IPDOM 錯失的合流機會：lz_tokenizer 56
10.2. ICS-First 過早插入優先權指令影響後續最佳化：voxel_dda 56
10.3. MinPC 的假設並不總是成立 57
10.4. blackscholes：FSEL 前後之控制流程差異 57
11. 整體討論 58
12. 本章小結 58
Chapter 8. 結論與未來展望 63
1. 結論 63
2. 未來工作 64
3. 總結 65
References 66
                                    

[1] Shuai Che, Michael Boyer, Jiayuan Meng, David Tarjan, Jeremy W. Sheaffer, Sang-Ha Lee, and Kevin Skadron. Rodinia: A Benchmark Suite for Heterogeneous Computing. In Proceedings of the IEEE International Symposium on Workload Characterization (IISWC), pages 44–54, 2009.

[2] Kuan-Chung Chen and Chung-Ho Chen. Enabling simt execution model on homogeneous multi-core system. ACM Trans. Archit. Code Optim., 15(1), March 2018.

[3] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, 3 edition, 2009.

[4] Wilson Wai Lun Fung, Ivan Sham, George Yuan, and Tor M. Aamodt. Dynamic warp formation and scheduling for efficient gpu control flow. In Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 407–420, Chicago, IL, USA, 2007. IEEE Computer Society.

[5] LLVM Project. [RISCV][ISelLowering] Use Zicond for FP selects on Zfinx/Zdinx (PR #169299). https://github.com/llvm/llvm-project/pull/169299, 2025.

[6] Steven S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, San Francisco, CA, 1997.

[7] Michael J. Quinn, Philip J. Hatcher, and Karen C. Jourdenais. Compiling c* programs for a hypercube multicomputer. SIGPLAN Not., 23(9):57–65, January 1988.

[8] radareorg contributors. radare2: Reverse Engineering Framework. https://rada.re/n/, 2026.

[9] Robert Endre Tarjan. Edge-disjoint spanning trees and depth-first search. Acta Informatica, 6(2):171–185, 1976.

校外：立即公開

簡易檢索 / 詳目顯示

相關論文