批量同步圖形處理單元編程的製作方法

2023-04-26 00:04:21 1

專利名稱：批量同步圖形處理單元編程的製作方法
批量同步圖形處理單元編程背景當代商品圖形硬體用中等成本提供了強大的原料處理能力。然而，對GPU進行編 程用於通用計算是相對困難的。這部分地是因為現有的通用GPU程式語言基於流處理模 型，因為GPU是流處理器；這些語言包括Brook、Sh和NVIDIA公司的CUDA。流處理是以數據為中心的模型，其中數據被組織成元素的同類流。將調用個體函 數的內核並行地應用於輸入流的所有元素來產生輸出流。通過在多個流上啟動多個內核來 實現複雜計算。這種流/內核抽象顯式地暴露出底層數據依賴性。然而，雖然提供高性能，但出於多個原因，流處理模型使得通用GPU編程很困難。 其一，程序可讀性和維護是一個大問題，因為根據數據依賴性而非功能來將程序分區到各 內核中。將新的功能添加到現有程序通常涉及重寫代碼的許多不相關的部分。其二，由於 中間或臨時流的廣泛使用，複雜應用中的數據流幾乎不與低層程序邏輯有關。顯式數據流 管理因此是乏味的且易於出錯的。編程困難的另一原因在於並行原語的抽象是困難的，這妨礙了代碼重用。更具體 地，許多並行原語，諸如scan和sort，需要多個內核啟動。當內核調用這種原語時，需要將 原語的一部分與調用器進行捆綁來減小中間流尺寸和內核啟動成本。結果是完整性被破壞 的原語，這使得原語的抽象變得困難。因為以上的問題，使用如今的GPU程式語言來編寫即使中等複雜的通用程序也是 極度困難的。對GPU可編程性的任何改進因此是高度需要的。概述提供本概述以便以簡化形式介紹將在以下的詳細描述中進一步描述的一些代表 性概念。本概述不旨在標識出所要求保護的主題的關鍵特徵或必要特徵，也不旨在以限制 所要求保護的主題的範圍的任何方式來使用。簡言之，此處描述的主題的各方面涉及提供和便於對用於圖形處理單元(GPU)上 的通用計算的程式語言的使用的技術。對批量同步GPU編程(BSGP)程序，諸如系統的一部 分進行編程來包括壁壘(barrier)來描述GPU上的並行處理。在一個方面，BSGP編譯器檢測對應於超級步(superst印)的壁壘，基於壁壘將 BSGP程序轉換成內核，並對其進行組合。在編譯期間，編譯器對齊語句中的壁壘，並將相應 的超級步捆綁在一起以便代碼重用。提供par構造來允許程式設計師例如通過指定獨立語句塊 來控制捆綁的各方面。在一個方面，提供了線程操縱仿真來用操作fork(分叉)和kill (銷毀)來透明 地模擬線程創建和銷毀。還提供了用於線程之間的高效通信的遠程變量訪問內部函數和集 體原語操作。結合附圖閱讀以下詳細描述，本發明的其他優點會變得顯而易見。附圖簡述作為示例而非限制，在附圖中示出了本發明，附圖中相同的附圖標記指示相同或 相似的元素，附圖中


圖1是表示編譯器自動地將BSGP程序轉換成流內核並為GPU執行生成管理代碼 的計算(編程/編譯和/或運行時環境)中的示例組件的框圖。圖2A是示出線程之間的壁壘操作的構造的表示。圖2B是示出線程之間的集體操作的構造的表示。圖3A是流編程模型中的原始碼重用的表示。圖;3B是批量同步編程模型中的原始碼重用的表示。圖4是示出編譯BSGP程序所採用的示例步驟的流程圖。圖5A-5C是用於便於臨時流優化的最小流的圖形構建的表示。圖6示出了表示壁壘對齊和合併的par構造的表示。詳細描述此處描述的技術的各方面一般涉及用於GPU上的通用計算的新的GPU程式語言， 此處被稱為BSGP (批量同步GPU編程)。BSGP基於批量同步並行(BSP)模型，該模型是從 低層程序結構中抽象以支持超級步(superst印)的並行編程模型。BSGP程序因此包括超級 步的順序集，其中每一超級步由多個線程完全並行地執行。如此處所使用的，在每一超級步 的結尾處執行壁壘同步來確保按照相對於彼此的順序次序來執行各步驟。如將理解的，BSGP容易閱讀、編寫和維護。例如，BSGP程序看上去與順序C++代碼 相似，只需要某些附加的額外信息來描述GPU上的並行處理。這是因為不像流處理中的內 核，超級步不是具有顯式指定的輸入和輸出參數的個體函數，而是類似於傳統順序編程中 的語句，並且是在語義上推斷的而非在語法上實施的。BSGP的另一優勢在於其數據依賴性是隱式地定義的，因為局部變量是可見的並且 可以跨超級步共享。將程式設計師從流編程中的乏味的時間數據流管理中解脫出來。此外，有 了 BSGP，諸如reduce (縮減)、SCan (掃描)和sort (排序)的並行原語可以作為整體在單 個語句中被調用，使得原語的抽象變得簡單並因此便於代碼重用。如將進一步理解的，BSGP通過透明地仿真一組線程操縱特徵來提供線程操縱仿 真，具體地，通過包括fork和kill的操作來仿真線程拆分和析構。還提供了包括reduce、 scan和sort的高效原語操作庫。還描述了高效地將BSP映射到GPU的語言構造，包括要求 塊和並行塊，來幫助克服關於BSP和GPU的若干不兼容問題。雖然此處描述的某些示例涉及各種代碼清單，但可以理解這些是非限制性的示 例。類似地，雖然在類似CUDA的環境中描述編譯器，但這只是一個合適的環境。如此，本發 明不限於此處所描述的任何特定實施例、方面、概念、結構、功能或示例。相反，此處所描述 的實施例、方面、概念、結構、功能或示例中的任一個都是非限制性的，並且本發明一般能夠 以在計算和GPU編程方面提供好處和優點的各種方式來使用。轉向附圖，描述了 BSGP，S卩，容易閱讀、編寫和維護的用於GPU上的通用計算的一 種程式語言。有了 BSGP，程式設計師只需要向程序102提供少量的額外信息，在此處被稱為壁 壘，來描述GPU 104上的並行處理。BSGP編譯器108自動地將兩個壁壘之間的語句推斷為 超級步並將其轉換成GPU內核Ioe1-Ioen，如圖ι所示。每一超級步因此由多個線程並行地 執行，其中壁壘同步對超級步進行定界來確保正確的並行執行。圖1還示出編譯器所產生 的數據流管理代碼110。對於編譯，BSGP編程模型不直接匹配GPU的流處理體系結構，因此編譯器108需要將BSGP程序轉換為高效的流程序。為了構建編譯器108，需要考慮壁壘同步，因為雖然可以 使用粗粒度化的並行體系結構的硬體同步來直接實現壁壘，但這在流環境中是不可能的。 在GPU的流環境中，常常創建比可以同時在物理處理單元上執行的線程更多的數量級。線 程被動態地分布到可用的處理單元以執行。在完成之後回收類似用於保存線程上下文的寄 存器之類的資源。物理處理單元的同步不影響非執行的線程，並因此不等價於線程的(邏 輯)壁壘。等待所有線程完成可用作有效壁壘，但這使得線程上下文被析構。為了解決這 個問題，編譯器108自動地添加上下文保存代碼來使得壁壘符合BSGP語義，如以下所描述 的。另一個與編譯器相關的問題是生成高效的流代碼。因為局部變量是可見的並且跨 BSGP程序中的超級步共享，所以編譯器108分析超級步之間的數據依賴性並自動地分配臨 時流來在超級步的結尾處保存局部變量值，將這些臨時流傳遞給後續超級步。為了減少臨 時流的總數以便高效使用GPU上可用的(有限)視頻存儲器，此處描述了一種圖優化方案。 作為超級步的順序組織的結果，可以用多項式時間來獲得最優解決方案。轉向BSGP對流處理的考慮，BSGP和流處理之間的一個差別在於BSGP和流處理是 不同形式的SPMD(單程序多數據)處理，其中多個線程並行地執行同一個程序。線程的總 數被稱為線程大小。每一線程被賦予一個等級，例如從0到size-Ι (大小-1)的唯一整數， 這個數字將該線程與其他線程區分開來。壁壘是用SPMD編程的一種同步的形式。當到達壁壘時，阻塞執行直到所有線程到 達同一個壁壘，如圖2A中的壁壘222概括地表示的那樣，圖中的壁壘使得線程0和線程2 等待直到線程1完成其工作負荷。在流處理中，等待內核啟動到終止只是壁壘的一種形式 (注意，內核啟動傳統地在GPU編程中被稱為pass)。雖然具有CUDA能力的硬體支持局部 同步，但一般不能在一個內核中實現所有線程的壁壘。另一方面是集體操作，包括必須由所有線程同時執行的操作。在SPMD編程中，集 體操作在語法上與普通順序操作相似，除了集體操作在語義上在所有線程上操作。一個線 程的輸入可能影響其他線程的輸出。例如，考慮圖2B，其中集體前置和可以被定義為scan (X)，收集線程(線程0、線程 1和線程幻中的χ的值來形成向量。在壁壘同步之後，如圖2B中的虛線所表示的，使用該 向量來計算前置和。隨後將前置和結果重新分發給每一線程的X，代碼執行繼續。典型的集 體操作在內部需要壁壘並因此在流編程中相對稀少。作為原始碼示例，考慮求解以下問題給定三角形網格的連接，為每一頂點計算一 環(one-ring)鄰接三角形的列表。網格含有m個頂點和η個三角形。連接被賦予範圍從 0到m-1的3η個整數的數組，其中每三個連續的整數表示三角形的三個頂點索引。用於求解該問題的示例BSGP原始碼基於排序算法。更具體地，以上問題通過排序 來求解，其中每一三角形被一式三份並與其三個頂點相關聯。將相關聯的頂點索引用作排 序鍵來對一式三份的三角形進行排序。在排序之後，共享同一個頂點的三角形被分組在一 起來創建所有頂點的鄰接三角形的串接列表。隨後將每一排序鍵與其前任進行比較來計算 指向每一頂點列表的開始位置的指針。清單1尋找鄰接三角形(BSGP版本)
權利要求
1.一種在計算環境中的方法，包括檢測批量同步程序中的壁壘(102)，每一壁壘定界超級步；以及將所述超級步編譯(108)成供圖形處理單元(104)執行的流代碼內核(Ioe1-Ioen)。
2.如權利要求1所述的方法，其特徵在於，編譯所述超級步包括在每一壁壘處添加保 存線程上下文的代碼。
3.如權利要求1所述的方法，其特徵在於，所述編譯還包括使用分配的臨時流組合所 述內核中的至少一些。
4.如權利要求3所述的方法，其特徵在於，使用分配的臨時流包括採用圖優化方案。
5.如權利要求1所述的方法，其特徵在於，還包括提供將線程的總數用作參數來執行 GPU代碼塊的spaWn語句。
6.如權利要求1所述的方法，其特徵在於，還包括提供用於將控制處理器代碼插入包 含超級步的require構造，所述require構造用於在啟動所述包含超級步之前執行所述控 制處理器代碼。
7.如權利要求1所述的方法，其特徵在於，還包括提供在所述批量同步程序中使用來 指定獨立的語句塊的par構造。
8.如權利要求1所述的方法，其特徵在於，還包括提供在所述批量同步程序中使用的 一組原語，包括提供數據並行原語、等級調整原語、或線程操縱原語，或數據並行原語、等級 調整原語或線程操縱原語的任意組合。
9.如權利要求8所述的方法，其特徵在於，提供所述一組原語包括提供reduce原語， scan 原語，compact 原語，split 原語或 sort 原語，或 reduce、scan、compact、split 或 sort 原語的任意組合。
10.如權利要求8所述的方法，其特徵在於，提供一組原語包括提供用於拆分線程的原 語、用於對線程排序的原語，或用於拆分線程的原語和用於對線程排序的原語兩者。
11.如權利要求8所述的方法，其特徵在於，提供一組原語包括提供用於銷毀線程的原 語、用於分叉線程的原語，或用於銷毀線程的原語和用於分叉線程的原語兩者。
12.如權利要求1所述的方法，其特徵在於，編譯所述超級步包括內聯對包含壁壘的 函數的調用，執行優化來降低數據依賴性，將CPU代碼和GPU代碼分開並生成內核和內核啟 動代碼，將對CPU變量的引用轉換為內核參數，尋找在定義超級步外部使用的值並生成保 存和加載這些值的代碼，以及生成臨時流分配。
13.—種在計算環境中的系統，包括編譯器(108)，所述編譯器(108)基於壁壘同步來 將包括語句、構造和原語的原始碼處理成流內核(Ioe1-Ioen)，並且將所述內核組合成能被 配置成供圖形處理單元(104)執行的代碼。
14.如權利要求13所述的系統，其特徵在於，所述語句中的一個包括用於在所述源代 碼中定界超級步的barrier語句，並且所述構造中的一個包括用於在所述原始碼中將控制 處理器代碼插入包含超級步中的require構造，所述編譯器編譯所述原始碼以便在啟動對 應於所述包含超級步的指令之前執行對應於所述控制處理器代碼的指令。
15.如權利要求13所述的系統，其特徵在於，所述原語包括reduce原語，scan原語， compact原語，split原語或sort原語，用於拆分線程的原語，用於對線程排序的原語，用於 銷毀線程的原語或用於分叉線程的原語，或reduce原語、scan原語、compact原語、split原語或sort原語、用於拆分線程的原語、用於對線程排序的原語、用於銷毀線程的原語或 用於分叉線程的原語的任意組合。
全文摘要
描述了計算環境中的一種技術，該技術包括用於圖形處理單元(GPU)上的通用計算的程式語言以及相關聯的編譯器。對批量同步GPU編程(BSGP)程序進行編程以包括壁壘來描述GPU上的並行處理。BSGP編譯器檢測響應於超級步(superstep)的壁壘(barrier)，將BSGP程序轉換成基於壁壘的內核，並將其進行組合。在編譯期間，編譯器對齊語句中的壁壘並將相應的超級步捆綁在一起。提供par構造來允許程式設計師例如通過指定塊獨立語句來控制捆綁的各方面。提供了線程操縱仿真來透明地用操作fork(叉分)和kill(銷毀)仿真線程創建和銷毀。還提供了用於線程之間的高效通信的遠程變量訪問內部函數以及集體原語操作。
文檔編號G06F9/38GK102132249SQ200980134286
公開日2011年7月20日 申請日期2009年6月26日 優先權日2008年6月26日
發明者B·郭, H·齊明, K·周 申請人:微軟公司