面向SIMD的自動并行化關(guān)鍵技術(shù)研究.pdf

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

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

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

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

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

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