面向SIMD的自動并行化關鍵技術研究.pdf

1、SIMD擴展部件以其實現成本低、部件功耗少、計算效率高等特點，逐漸成為高性能計算機的必備計算加速部件，其應用領域也從最初的多媒體處理，擴展到科學計算、信號處理、密碼分析等領域。由于向量指令與底層硬件關系密切，編程人員很難寫出正確高效的SIMD代碼，因此用編譯器實現程序的自動向量化成為必然選擇。目前 Open64、Gcc、ICC和LLVM等主流編譯器都實現了自動向量化功能。SIMD擴展部件具有特殊的硬件結構和并行計算方式，為了適應復雜的應

2、用并獲得更好的加速效果，SIMD在指令功能和并行寬度方面一直在不斷地發(fā)展和改進。然而，面向SIMD的自動向量化方法在識別能力和優(yōu)化效果方面仍然存在一些不足。為了加強向量并行識別能力，進一步發(fā)掘和優(yōu)化程序中的向量并行性，本文在向量并行發(fā)掘方法及其優(yōu)化技術方面進行了系統(tǒng)深入研究。
　　本研究主要內容包括：⑴提出了一種基于循環(huán)分段的嵌套循環(huán)向量化方法 simdcodegen。該方法首先分析了依賴環(huán)形成的原因，并討論了循環(huán)分段對于消除依賴

3、環(huán)的作用。然后在codegen的基礎上，將循環(huán)分段逐層地應用于多層循環(huán)，實現了嵌套循環(huán)的向量化。雖然循環(huán)分段總是合法的，但進行分段后會帶來執(zhí)行代價的增加，本文設計了循環(huán)分段的有利性測試方法，來避免無效分段的實施。⑵提出了一種分段約束的SLP發(fā)掘路徑優(yōu)化算法。循環(huán)展開后每次迭代對應的展開單元稱為一個段。本文采用分段的冗余刪除方法，來保證冗余刪除后段的同構性；采用了“相鄰-段間”的SLP發(fā)掘方法，來約束發(fā)掘路徑的范圍。由于“分段冗余刪除”較

4、“全局冗余刪除”保留了部分冗余的訪存操作，打包后生成的向量代碼往往存在訪存重疊的情形，存在進一步優(yōu)化空間。本文針對此情況引入了SIMD訪存優(yōu)化調整方法，以數據重組指令來替代重疊的向量訪存指令，有效提高了程序執(zhí)行效率。⑶提出了一種循環(huán)級與基本塊級結合的向量化方法。該方法分析了上述兩種方法適用范圍，同時對程序中可能存在的向量并行特征進行分類，根據不同類別的并行特征確定了向量化任務分配方案，最后設計了混合的向量化框架來實現這種任務分配方案。為

5、了明確目標循環(huán)并行性特征，本文給出了循環(huán)迭代間和迭代內的向量并行性檢測方法。⑷提出了一種非滿載使用SIMD指令的方法。研究了向量寄存器的非滿載使用方式，設計了對應的非滿載向量操作，實現了NEI_LOOP的向量化，然后將非滿載的向量化方法用于一般循環(huán)的向量化。由于非滿載的向量操作需要額外的代價，向量化并不總是有益的，因此文章同時提供了收益分析算法，僅對收益大于零的程序實施向量化。該方法不僅可以實現NEI_LOOP向量化，同時還可以解決向量

6、化過程中的大部分非規(guī)則訪存問題，如跨幅訪存，一般的非連續(xù)訪存等等，基本思想就是向量寄存器的非規(guī)則使用。⑸提出了一種面向部分向量化的循環(huán)分布及聚合方法。為了解決循環(huán)開銷過大的問題，需要在保證循環(huán)向量并行性的基礎上盡可能進行循環(huán)合并，因此提出一種面向最大聚合的拓撲排序方法，使得無環(huán)結點盡可能相鄰，有環(huán)結點也盡可能相鄰，最終可聚合得到盡可能少的循環(huán)。為了解決數據重用問題，設計了一種基于數據重用的凝聚圖節(jié)點聚合優(yōu)化方法，從寄存器重用和cache