[發明專利]一種通過死代碼移除來加快GPU運行速度的方法

有效

• 申請號: 201310020549.2
• 申請日: 2013-01-21
• 公開（公告）號: CN103049304A
• 公開（公告）日: 2013-04-17
• 發明（設計）人: 遲利華;劉杰;胡慶豐;晏益慧;龔春葉;甘新標;徐涵;蔣杰;楊博
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F9/45
• 分類號: G06F9/45
• 代理公司: 國防科技大學專利服務中心 43202
• 代理人: 郭敏

技術領域

本發明涉及加快大規模GPU核心程序運行速度的方法，尤指通過移除死代碼來加快GPU運行速度的方法。

背景技術

GPU（Graphics?Processing?Unit，圖形處理單元）過去通常用于圖形圖像應用領域，現在也廣泛應用于加速各種通用的并行算法和應用。這些算法和應用在GPU上的核心程序通常都比較簡單，一般只有上百行代碼。但是對于一些具有實際應用價值的大規模應用程序，如非確定性粒子輸運程序MCNP（Monte?Carlo?N-particle，N粒子蒙特卡羅方法），其GPU實現的核心代碼通常上萬行，同時在具體程序執行時存在大量死代碼。與CPU相比，GPU的指令緩存較少，從而對生成的匯編代碼的大小很敏感。并且GPU一般采用_inline_指令對子函數進行內聯，編譯時需要對整個核心程序進行全局優化。死代碼的存在既增大了生成的匯編代碼體積，又降低了全局優化的效果，嚴重影響了GPU運行速度。目前加快GPU運行速度的方法主要有以下幾種：

（1）將只讀數據布局于GPU常量存儲空間來提高訪存速度。

（2）將頻繁訪問的數據布局于GPU片上共享存儲器來提高訪存速度。

（3）通過接合式訪問GPU全局內存來提高訪存速度。

（4）調整GPU核心程序線程塊大小來提高寄存器資源利用率和程序執行效率。

上述四類方法都存在局限性。GPU常量存儲器容量有限且只能存放只讀數據；GPU片上共享存儲器容量有限且存在體沖突（bank?conflicts）；GPU全局內存存在訪存延遲高的問題；調整大型GPU核心程序線程塊大小通常只能逐一嘗試來確定最優的線塊大小，效率低。

死代碼就是程序執行過程中可能執行但實際運行時并沒有執行的代碼段。死代碼的存在將增大匯編代碼體積，嚴重影響程序優化和調度，降低程序運行效率。對于一些具有實際應用價值的大規模應用程序而言，其GPU核心程序匯編代碼體積已經相當可觀，同時GPU指令緩存空間卻相當有限，GPU核心程序中死代碼的存在將增加GPU指令緩存的壓力，浪費GPU寶貴的指令緩存空間，嚴重影響GPU核心代碼的調度和優化，延長GPU核心代碼的運行時間。因此死代碼的刪除對于提高大規模GPU程序執行效率和加快程序運行速度至關重要。

BODIK提出了編譯優化過程中識別無用賦值語句的方法；SWEENEY提出了面向對象的不可達子程序的檢測方法；XI提出了無用函數參數的檢測方法；張廣梅從程序的控制結構出發實現了無效程序分支的檢測。上述死代碼檢測技術均以編譯為基礎，側重于死代碼檢測技術基本原理的推導和證明，理論證明詳實可信，但是實際應用復雜，可操作性差，不利于推廣應用。

對于具有實際應用價值的大規模GPU核心程序，移除死代碼可以顯著增加程序的執行效率，因此，如果能夠檢測和刪除死代碼，必定能夠加快GPU運行速度，但是目前還沒有公開文獻研究相關技術方案。

發明內容

本發明要解決的技術問題在于：針對大型GPU核心程序存在執行效率不高的問題，在保證程序正確性的前提下，提出一種通過死代碼移除來加速GPU運行速度的方法，提高大規模GPU核心程序的執行和編譯效率。

為了解決上述技術問題，本發明的具體技術方案為：

第一步、構建函數狀態檢測表。為大規模GPU核心程序中的所有函數構建狀態檢測表，狀態檢測表的表項數為GPU核心程序中函數的個數。狀態檢測表共包含六個字段，分別為：函數編號ID、函數名稱Name、調用標記Callee、靜態分析標記Static、動態執行標記Dynamic和刪除標記Del。函數編號ID為函數的全局唯一標記，函數名稱Name表示函數的名字；調用標記Callee表示函數是否被程序調用，調用標記Callee為true表示函數被程序調用過，Callee為false表示函數沒有被程序調用過；靜態分析標記Static表示對函數模塊進行靜態分析后判斷其是否會執行，Static為true表示函數在程序執行時可能會運行，Static為false表示函數在程序執行時不會運行；動態執行標記Dynamic表示程序運行時函數是否被執行，Dynamic為true表明函數在程序運行時運行過，Dynamic為false表明函數在程序運行時沒有運行過；刪除標記Del表示函數代碼段能否被刪除，Del為true表明函數代碼段是死代碼應該刪除，若Del為false表明函數代碼段不是死代碼不應刪除。