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

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

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

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

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

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

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