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

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

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

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

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

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

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

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

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

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