可重構(gòu)眾核流處理器上的編譯與程序優(yōu)化技術(shù).pdf

1、半導(dǎo)體工藝的持續(xù)進(jìn)步和流編程模型的提出是推動(dòng)眾核流處理器體系結(jié)構(gòu)向前發(fā)展的兩個(gè)重要因素。為了充分利用摩爾定律發(fā)展帶來的豐富廉價(jià)的晶體管資源，片上多處理器已經(jīng)成為工業(yè)界所接受的新一代處理器體系結(jié)構(gòu)的解決方案之一。另一方面，流編程模型的提出為解決應(yīng)用程序并行性表示和開發(fā)提供了有利的工具，業(yè)已成為程序并行化的一般方法。但是流應(yīng)用程序本身的運(yùn)行時(shí)特性對(duì)處理器資源的靈活可配置提出了新的要求。一方面，不同程序?qū)τ谟?jì)算，存儲(chǔ)和控制的硬件資源需求是千差

2、萬別的;另一方面，有的程序?qū)τ谟布Y源的需求還表現(xiàn)出階段性特征，不同階段所需的硬件資源也不盡相同。為了解決這一問題，近年來可重構(gòu)眾核處理器體系結(jié)構(gòu)受到廣泛關(guān)注，期望以同構(gòu)的輕量級(jí)物理核來構(gòu)建不同粒度的邏輯處理器，自適應(yīng)地調(diào)整硬件資源，最大化串行程序的性能。我們基于以上認(rèn)識(shí)，提出了可重構(gòu)的眾核流處理器體系結(jié)構(gòu)TPA-S，旨在為流應(yīng)用程序提供片上資源靈活可重構(gòu)的硬件襯底。
　　 本文圍繞這一體系結(jié)構(gòu)，研究了以CUDA為代表的流編程模

3、型在TPA-S上的編譯和程序優(yōu)化技術(shù)，分別從可重構(gòu)流處理器的執(zhí)行模型，指令集擴(kuò)展，編譯系統(tǒng)設(shè)計(jì)，以及程序優(yōu)化技術(shù)等方面展開研究。主要的研究?jī)?nèi)容包括:
　　 (1)研究流編程模型與可重構(gòu)流體系結(jié)構(gòu)的執(zhí)行模型，探索流應(yīng)用程序在可重構(gòu)流處理器TPA-S上的映射方案。流編程模型的實(shí)質(zhì)在于控制和計(jì)算的分離:流程序中的計(jì)算密集部分以核心函數(shù)的形式被抽取出來，使用多個(gè)計(jì)算線程來開發(fā)數(shù)據(jù)級(jí)并行性;而控制線程專注于計(jì)算之外的控制流程序，為核心函數(shù)

4、組織數(shù)據(jù)以及開發(fā)生產(chǎn)者-消費(fèi)者局部性。我們?cè)O(shè)計(jì)了主從式和分階段式兩種程序映射方案，分別以異步和同步的方式將計(jì)算線程和控制線程映射到TPA-S的多個(gè)邏輯處理器上。另外，我們還提出了單一線程和組合線程這兩種核心函數(shù)的組織方式，在單線程性能和系統(tǒng)吞吐率之間尋求最佳平衡點(diǎn)。
　　 (2)研究流編程模型對(duì)TPA-S指令集體系結(jié)構(gòu)產(chǎn)生的設(shè)計(jì)需求，提出擴(kuò)展的類數(shù)據(jù)流EDGE指令集DISC-S。TPA-S流處理器基于顯式數(shù)據(jù)流圖執(zhí)行(EDGE)

5、指令集，將程序的每個(gè)線程組織為原子執(zhí)行和提交的超塊序列，在超塊內(nèi)部按照類數(shù)據(jù)流方式執(zhí)行。EDGE指令集中特殊的目標(biāo)域編碼方式是TPA-S處理器實(shí)現(xiàn)物理核可重構(gòu)的基礎(chǔ)之一。然而流編程模型為TPA-S微結(jié)構(gòu)帶來了一些不包括在EDGE指令集中的新特性，例如:多個(gè)計(jì)算線程需要依靠只讀的特殊寄存器來快速地獲取線程索引信息;計(jì)算線程需要訪問軟件管理的片上共享存儲(chǔ)器數(shù)據(jù);另外，多個(gè)線程之間需要實(shí)現(xiàn)高效的柵欄同步機(jī)制。DISC-S擴(kuò)展指令集針對(duì)以上新特

6、性，增加了對(duì)特殊寄存器讀寫，軟件管理的片上共享存儲(chǔ)層次以及線程間同步的指令支持，為實(shí)現(xiàn)流編程模型的映射帶來了方便。
　　 (3)設(shè)計(jì)并實(shí)現(xiàn)面向CUDA編程語(yǔ)言的TPA-S編譯器系統(tǒng)。本文基于NVCC編譯框架將編譯器系統(tǒng)分為核心級(jí)與流級(jí)兩條編譯鏈。我們參考scale編譯器設(shè)計(jì)了核心級(jí)編譯器Ptx2EDGE，將PTX匯編語(yǔ)言形式的計(jì)算線程源代碼程序編譯成DISC-S擴(kuò)展指令集的二進(jìn)制目標(biāo)代碼。在流級(jí)，我們實(shí)現(xiàn)了CUDAC語(yǔ)法擴(kuò)展和A

7、PI函數(shù)接口以及運(yùn)行時(shí)庫(kù)的移植，并復(fù)用scale串行編譯器產(chǎn)生控制線程代碼。編譯器系統(tǒng)設(shè)計(jì)的主要工作由一系列編譯模塊與工具軟件的代碼實(shí)現(xiàn)組成，包括PTX和CUDA語(yǔ)法的前端識(shí)別，中間表示形式轉(zhuǎn)換，超塊生成和優(yōu)化，資源分配與指令調(diào)度，匯編器與鏈接器等。另外，為了實(shí)現(xiàn)CUDA控制線程中設(shè)備管理，線程管理，執(zhí)行控制和存儲(chǔ)器管理等功能模塊，我們移植了CUDA運(yùn)行時(shí)庫(kù)并實(shí)現(xiàn)了軟件運(yùn)行時(shí)系統(tǒng)Mpsim。編譯系統(tǒng)的正確性和執(zhí)行效率通過實(shí)驗(yàn)在一組基準(zhǔn)測(cè)

8、試程序上進(jìn)行了驗(yàn)證與評(píng)測(cè)。
　　 (4)研究了不規(guī)則程序在流處理器上的程序優(yōu)化方法。本文主要分析了眾核流處理器上不規(guī)則程序的性能瓶頸問題，并對(duì)GPU平臺(tái)上的圖廣度優(yōu)先搜索算法進(jìn)行了實(shí)例研究，希望找到不規(guī)則程序在流處理器上進(jìn)行性能調(diào)優(yōu)的一般性方法。我們針對(duì)不規(guī)則程序中復(fù)雜多變的無組織數(shù)據(jù)并行性提出了基于并行性反饋的FlexBFS高效實(shí)現(xiàn)方法，并針對(duì)不規(guī)則訪存帶來的動(dòng)態(tài)隊(duì)列訪存效率問題以及不規(guī)則輸入引起的負(fù)載平衡問題，分別提出了相應(yīng)

9、的程序優(yōu)化技術(shù)。這些實(shí)現(xiàn)方法和優(yōu)化技術(shù)都能夠被應(yīng)用到其它的不規(guī)則程序當(dāng)中。
　　 本文獲得了以下重要認(rèn)識(shí):(1)流編程模型能夠驅(qū)動(dòng)指令集體系結(jié)構(gòu)的設(shè)計(jì)，ISA需要反映編程模型帶來的新特性;(2)流程序的多線程映射需要軟件運(yùn)行時(shí)庫(kù)的協(xié)同工作，在將來的操作系統(tǒng)中可以增加對(duì)流編程模型的支持;(3)編譯系統(tǒng)設(shè)計(jì)環(huán)節(jié)需要使用合適的編程模式和軟件工程方法來增強(qiáng)程序的模塊化與可讀性，例如訪問者模式;(4)不規(guī)則程序的并行性開發(fā)需要準(zhǔn)確的并行性