相依指令線程調度的製作方法

2023-10-05 15:06:04

專利名稱：相依指令線程調度的製作方法
技術領域：
本發明大體來說涉及圖形處理器且更具體來說涉及對具有相依指令的線程的線 程調度。
背景技術：
經常使用專用處理器來執行與一種類型的應用程式相關的具體功能，以有效且快 速地執行與所述應用程式相關的操作。舉例來說，圖形處理器執行各種圖形操作來處 理圖像數據並再現圖像且有效地操縱並顯示計算機圖形。由於其高度並行的結構，對 於各種各樣的複雜算法，圖形處理器比典型的通用處理器更有效。圖形處理器以以下 方式來實施若千圖形圖元操作使通過主機中央處理單元(CPU)執行所述操作比直 接向屏幕呈現所述圖形快得多。
為有效地利用專用處理器(例如，圖形處理器)中的資源，經常將任務組織為線 程，其中可同時或偽同時執行所述線程的執行。由於資源在給定時間通常僅可尋址單 個指令，因此使用線程調度器來控制對各種線程的指令的執行的計時且有效地向所述 線程分配資源。然而，某些指令需要從具有不可預測的延遲的數據源檢索數據。舉例 來說，由於數據大小或位置，從處理器系統內的某些存儲器檢索數據可具有不可預測 的延遲。具有不可預測的延遲的數據源的另一實例是在圖形處理器中返回紋理數據的 紋理引擎。由於紋理指令的可變複雜性，不能夠預測返回紋理數據所需要的時間。線 程的指令可以或可不需要從具有不可預測的延遲的數據源檢索數據。在線程的執行期 間，相依指令可需要由先前指令獲取的數據來執行所述相依指令。當從不可預測延遲 數據源獲取所述所需數據時，可能無法及時返回所述所需數據來執行所述相依指令。
用於在常規系統中管理線程的一種技術包括在執行特定線程的每--寸旨令之前檢 査數據可用性。然而，所述方法需要利用資源的複雜檢測方案。用於常規系統中的另 --技術包括暫停指令，直到完成加載指令，此導致低效率。
因此，需要 一種用於有效地管理具有相依指令的線程的執行的線程調度器。

發明內容
一種線程調度器包括用於提交線程的指令供所述線程調度器調度的線程上下文 單元，其中每一上下文寄存器包括用於維持指示與特定上下文寄存器相關聯的若干數
據請求與若干數據返回之間的差的計數器值的加載參考計數器。所述上下文單元的線程上下文控制器經配置以避免在所述計數器值為非零時提交線程的指令且所述指令 包括指示所述指令需要由先前指令返回的數據的數據相依性指示符。


圖1是根據本發明的實例性實施例的線程管理系統的框圖。
圖2是根據所述實例性實施例的線程控制的狀態機圖。
圖3是根據所述實例性實施例的管理具有相依指令的線程的方法的流程圖。
具體實施例方式
本文所用措詞"實例性"意指"充當實例、示例或例證"。本文說明為"實例性" 的任何實施例未必解釋為優選或優於其它實施例。
圖1是根據本發明的實例性實施例的線程管理系統100的框圖。除參照圖1所論 述的那些以外，線程管理系統100可包括其它過程、實體、引擎及/或功能。可使用
硬體、軟體及/或固件的任一組合來實施圖1中所圖解說明的塊。此外，可以任何數 量的裝置、電路或元件來實施圖1中所說明的塊的功能及操作。可將所述功能塊中的 兩者或更多者集成在串-個裝置中，且可在若干裝置上實施說明為在任一單個裝置中執
行的功能。線程管理系統100的適合實施方案的實例包括將系統100實施為多線程處 理器IOI的部分。然而，可將所論述的技術應用到用於調度並處理多個線程的各種處
理器或計算機系統中的任一者。
在所述實例性實施例中，在多線程處理器101中實施線程調度器102、算術邏輯 單元(ALU) 106、加載控制器108、指令高速緩存器(未顯示)、寄存器堆庫(未 顯示)、常數隨機存取存儲器(RAM)(未顯示)、其它功能。多線程處理器101 是經配置以有效地處理特定類型的數據串流的可編程處理器。適合的多線程處理器 101的實例包括多線程處理器，所述多線程處理器包括用於有效地處理多媒體數據串 流(例如，視頻、音頻等)的常數數據。所述常數RAM通過改善寄存器庫檢索效率 來支持所述ALU。指令高速緩存器存儲線程的指令以向線程調度器102提供指令。 在線程調度器102的控制下，加載控制器108用來自存儲器128的指令加載指令高速 緩存器且用來自存儲器128及/或紋理引擎130的數據加載所述常數RAM及所述寄存 器堆庫。所述指令指示針對每一線程將要執行的具體操作。適合操作的實例包括算術 操作、初等函數及存儲器存取操作。
所述常數RAM存儲由ALU 106使用的常數值。所述寄存器堆庫可存儲臨時結 果以及線程的來自ALU 106的最終結果。輸出接口 (未顯示)從寄存器堆庫接收已 執行線程的最終結果且將所述結果提供到對應的應用程式。
線程管理系統100從(舉例來說)應用程式接收線程，例如圖形線程。大體來說， 線程調度器102接收線程串流且執行各種功能來調度並管理線程的執行。舉例來說，
6線程調度器102可調度線程的處理、確定特定線程所需要的資源是否可用，且經由加
載控制器108將線程數據移動到寄存器堆庫。線程調度器102與加載控制器108介接 以使所接收線程的資源同步。線程調度器102還可監視從特定應用程式接收線程的次 序且致使這些線程以與接收時的相同次序或序列被輸出。
線程調度器102選擇活動線程以用於執行，檢查所選擇線程之間的讀取/寫入端 口衝突，如果不存在衝突，那麼將來自線程的適當指令指派到ALU 106中且將另一 線程的另一指令發送到加載控制器108。在線程調度器102的請求下，加載控制器108 還可經配置以從不可預測延遲數據源104 (例如，紋理引擎130或外部存儲器128) 獲得與線程相關聯的數據。舉例來說，存儲器128可包括全局數據高速緩存器及/或 外部存儲器裝置。除發出對丟失指令的提取請求以外，加載控制器108將線程數據加 載到寄存器堆庫(未顯示)中且將相關聯指令加載到指令高速緩存器(未顯示)中。 線程調度器102還移除已由ALU 106處理的線程。
ALU 106可以是單個四元組ALU或可包括四個標量ALU。在所述實例性實施例 中，ALU106對多達四個像素的屬性的一個分量執行像素並行處理。在某些情況下， ALU 106對單個像素的屬性的多達四個分量執行分量並行處理。ALU 106從寄存器堆 庫提取數據且從常數RAM接收常數。理想地，ALU106在每一時鐘循環處理數據， 使得其不空閒，從而提高處理效率。ALU106在到寄存器堆庫的接口上包括多個讀取 及寫入埠，使得其能夠在新線程數據在每一時鐘循環被提取/讀取時提供線程結果。
所述線程調度器包括用於通過線程仲裁/資源管理器(在本文中稱作資源管理器) 132來管理並提交用於執行的線程的多個線程上下文單元110、 112、 114。每一線程 被指派到線程槽且在相關聯的線程上下文單元110、 112、 114上被管理。每一線程上 下文單元IIO、 112、 114內的線程上下文寄存器134、 136、 138存儲所述線程的每一 指令的指令類型及其它信息。每一線程上下文單元110、 112、 114內的線程上下文控 制器140、 142、 144控制向資源管理器132對指令的提交。線程上下文單元從資源管 理器132請求資源。當資源可用時，所述資源管理器批准所述請求。線程調度器102 內的流控制器(未顯示)及資源管理器132允許每一線程存取ALU106、加載控制器 108及指令高速緩存器(未顯示)以允許每一線程上下文單元110、 112、 114加載數 據且使指令由適當的資源執行以執行所述線程。
為執行指令，線程上下文單元首先請求將所述指令加載到指令高速緩存器中。所 述指令至少部分地被解碼且線程上下文單元110內的上下文控制140基於相依性指示 符的存在及線程上下文單元110的加載參考計數器(LRC) 116的值來確定是否應執 行所述指令。當線程上下文單元提交指令時，指令類型向資源管理器132指示執行所 述指令所需要的資源。舉例來說，所請求的資源可以是ALU106、存儲器128或紋理 引擎130。當所述資源被批准時，將所述指令轉發到可用資源以用於執行。因此，資 源管理器(線程仲裁管理器)132管理所請求資源的分配以向請求線程上下文單元批 準所請求的資源。線程內的指令可具有可預測的延遲或不可預測的延遲。具有可預測的延遲的指令 在本文中稱作可預測延遲指令且包括在已知數量的時鐘循環內執行的指令。可預測延 遲指令的實例包括ALU操作及不需要多線程處理器核心外部的資源的其它操作。在 所述實例性實施例中，內部多線程處理器101操作經設計而具有標準的延遲。不具有 可預測延遲的指令在本文中稱作不可預測延遲指令。不可預測延遲指令的實例包括需 要多線程處理器101外部的外部資源的操作。舉例來說，存取外部存儲器的與紋理相 關的指令及數據檢索指令具有不可預測的延遲。
因此，特定指令可需要從具有不可預測的延遲的數據源檢索數據。在所述實例性 實施例中，不可預測數據源104可以是紋理引擎130或存儲器128。所述線程內與紋 理相關的指令需要紋理引擎130處理由所述指令提供的信息並返回紋理數據。與存儲 器相關的指令需要檢索存儲在存儲器128內的所存儲數據。當所述存儲器為晶片外 時，檢索所請求數據所需要的時間可不可預測。當特定數據檢索事件具有不可預測的 延遲時，可引發其它情形。
所述線程上下文單元包括用於管理線程的執行的適當資源。除線程上下文寄存器 134、 126、 138以外，線程上下文單元IIO、 112、 114還包括實施在用於管理線程的 執行的邏輯中的上下文控制器140、 142、 144。如下文參照圖2所論述，可用狀態機 來建模上下文控制器，其中所述上下文控制器在有限組狀態之間轉換。在所述實例性 實施例屮，每-'線程上下文寄存器110、 112、 114包括加載參考計數器(LRC) 116、 120、 124且每-'上下文控制器140、 142、 144包括相依性指示符檢測器(DID) 118、 122、 126。當從執行線程的相關聯線程上下文單元發出對數據的請求時，將每一LRC 遞增一。當從所述源返回所請求的數據時，將每一LRC遞減一。因此，所述加載參 考計數器(LRC)經配置以針對所述特定線程維持指示若干數據請求與若干數據返回 之間的差的計數器值。相依性指示符檢測器118、 122、 126經配置以檢測指令中的相 依指示符。所述相依性指示符可以是任何類型的數據、旗標、位或指示所述指令是否 需要來自所述線程中的先前指令的數據的其它指示符。當原始碼經編譯以創建線程代 碼時，添加相依性指示符。在所述實例性實施例中，向所述線程的每一數據相依指令 添加單個位相依性指示符。因此，線程的需要來自先前指令的數據的每一指令包括相 依性指示符。
在線程的執行期間，根據對應線程的數據請求及返回來遞增及遞減每一 LRC。 當相依性指示符檢測器(DID) 112、 122、 126識別指令相依於來自先前指令的數據 時，評價所述LRC以確定其是否為零。如果所述LRC為非零，那麼線程上下文單元 避免提交所述指令且將所述線程上下文單元置於等待狀態。當所述LRC等於零時， 執行所述指令。
圖2是根據所述實例性實施例的線程控制的狀態機圖。所述狀態機圖是由狀態、 轉換及動作組成的行為的模型。由於其反映從系統開始到目前的輸入改變，因此狀態 存儲關於過去的信息。轉換由圖2中的箭頭指示且所述轉換指示狀態改變。必須遇到特定條件來使轉換發生。圖2是線程上下文單元的狀態及轉換的表示圖。因此，每一 線程上下文單元在線程調度器的操作期間可處於不同的狀態。
在所述實例性實施例中，所述線程上下文單元可處於包括以下狀態的七個狀態中
的一者空閒狀態202、 ALU狀態204、加載狀態206、流狀態208、 DEP狀態210、 等待狀態212及發射狀態214。所有線程均以空閒狀態202開始及結束。線程上下文 單元在空閒狀態202中等待新線程。當從空閒狀態轉換到等待狀態204 (其中線程上 下文單元等待資源變得可用)時，指令類型被呈現到資源管理器132。當加載控制器 可用時，從指令高速緩存器加載所述指令且所述指令被執行。所述指令可包括ALU 操作、加載操作或紋理操作。依據特定指令及當前狀態，線程上下文單元轉換為適當 狀態。在流狀態208中，線程上下文單元執行流控制任務且更新程序計數器。在加載 狀態206中，線程上下文單元執行加載任務，例如初始加載、加載紋理數據、加載來 自存儲器的數據及其它加載及存儲執行。在等待狀態204中，線程上下文單元等待資 源。算術邏輯單兀(ALU) 106在ALU狀態204中被存取以執行算術或邏輯指令。 當在指令中檢測到相依性指示符且LRC為非零時，線程上下文單元進入DEP狀態 210。當LRC返回到零時，線程上下文單元轉換為先前的退出狀態。在發射狀態214 期間，所述指令的所返回結果被移動出上下文寄存器。
圖3是根據所述實例性實施例的管理具有相依指令的線程的方法的流程圖。雖然 所述方法可應用於其它結構，但在所述實例性實施例中，所述方法由線程上下文單元 執行。以下步驟提供執行參照圖2論述的與相依指令相關的技術的實例。因此，可用 在圖3中省略(為了清晰及簡明起見)的其它塊或流程表來建模線程上下文單元的其 它操作。在所述實例性實施例中，所述方法由執行上下文控制器140、 142、 144的操 作的邏輯電路執行。
如下文所論述，所述上下文控制器邏輯的動作由經編譯的線程代碼規定。因此， 在所述編譯程序期間，編譯器識別較高級代碼中所指示的相依性且將所述相依性指示 符插入所述指令的由所述上下文控制器辨別的適當位置內。
在步驟302處，針對新線程初始化程序計數器(PC)及加載參考計數器值 (LRC—VAL)。全局寄存器針對所述線程設定經初始化的值。當應用程式需要線程 在並非歩驟O (第一步驟)的步驟處開始時，INIT_PC可以是非零且可將所述PC設 定為非零值。當不需要預加載數據時，INIT—LRC—VAL為零。然而，如果所述線程 需要預加載數據(例如，紋理數據)，那麼(舉例來說)可將INIT—LRC_VAL設定 為非零值。線程上下文單元處於空閒狀態202且等待新線程。當指派新線程時，所述 方法在步驟304處繼續。
在步驟304處，確定當前指令是否是相依指令。如果在所述指令中檢測到相依性 指示符，那麼將所述指令識別為相依指令且所述方法在步驟306處繼續。否則，所述 方法進行到步驟312。
在步驟306處，確定LRC值(LRC—VAL)是否等於零。如果所述LRC等於零那麼所述方法在步驟312處繼續。如果所述LRC.值為非零，那麼所述方法進行到步 驟308。
在步驟308處，確定是否已檢索到所請求的數據。在所述實例性實施例中，加載 控制器指示所述數據已被返回到適當的寄存器堆。如果已返回數據，那麼所述方法在 步驟310處繼續，在步驟310中將LRC遞減1。否則，所述方法返回到步驟308。在 步驟310之後，方法返回到步驟306。
在步驟312處，發出對用以執行所述指令的適當資源的請求。當所述資源可用且 由資源管理器(線程仲裁管理器)132批准時，所述指令由所述適當資源執行。
在步驟314處，確定所述指令是否已請求數據。如果已請求數據，那麼在所述方 法進行到步驟318之前，所述方法在步驟316處繼續，在步驟316中將LRC值遞增1。 如果未請求數據，那麼所述方法進行到步驟318。
在歩驟318處，將程序計數器遞增1。在步驟320處，針對所述線程確定下一 PC指令是否存在。如果存在更多指令，那麼所述方法返回到步驟304。否則，所述方 法返回到步驟302以等待下一線程。
所屬技術領域中的技術人員應了解，可使用各種不同技法及技術中的任一者來表 示信息及信號。舉例來說，以上說明通篇可能提及的數據、指令、命令、信息、信號、 位、符號及碼片可由電壓、電流、電磁波、磁場或磁粒子、光場或光粒子或其任一組
合來表不。
所屬技術領域中的技術人員應進一步了解，結合本文所揭示實施例說明的各種說 明性邏輯塊、模塊、電路、及算法步驟可實施為電子硬體、計算機軟體或兩者的組合。 為清楚地圖解說明硬體與軟體的此種可互換性，上文己就其功能性總體說明了各種說 明性組件、塊、模塊、電路及步驟。此種功能性實施為硬體還是軟體取決於特定應用 及施加到整個系統上的設計約束條件。所屬技術領域中的技術人員可針對每一特定應 用以不同的方法來實施所說明的功能性，但此類實施決策不應被視為導致背離本發明 的範圍。
可用以下裝置來實施或執行結合本文所揭示實施例說明的各種說明性邏輯塊、模 塊及電路通用處理器、數位訊號處理器(DSP)、專用集成電路(ASIC)、現場可 編程門陣列(FPGA)或其它可編程邏輯裝置、離散門或電晶體邏輯、離散硬體組件 或其設計用於執行本文所說明功能的任一組合。通用處理器可以是微處理器，但另一
選擇為，處理器可以是任何常規處理器、控制器、微控制器或狀態機。處理器也可實 施為計算裝置的組合，例如，DSP與微處理器的組合、多個微處理器的組合、 一個或 一個以上微處理器與DSP核心的聯合或任何其它此類配置。
結合本文所揭示實施例所說明方法的步驟可直接體現在硬體中、由處理器執行的 軟體模塊中或兩者的組合中。軟體模塊可駐存在RAM存儲器、快閃記憶體、ROM 存儲器、EPROM存儲器、EEPROM存儲器、寄存器、硬磁碟、可抽換磁碟、CD-ROM 或所屬技術領域中已知的任何其它形式的存儲媒體中。實例性存儲媒體耦合到所述處理器，使得所述處理器可從所述存儲媒體讀取信息及向所述存儲媒體寫入信息。另一
選擇為，存儲媒體可集成到處理器中。處理器及存儲媒體可駐存在ASIC中，ASIC 可駐存在用戶終端中。另一選擇為，處理器及存儲媒體可作為離散組件駐存在用戶終端中。
提供對所揭示實施例的以上說明旨在使所屬技術領域中的技術人員能夠製作或 使用本發明。所屬技術領域中的技術人員將易於明了這些實施例的各種修改，且本文 所定義的一般原理也可在不背離本發明的精神或範圍的情況下應用於其它實施例。因 此，並非打算將本發明限定為本文所示實施例，而是要賦予其與本文所揭示原理及新 穎特徵相一致的最寬廣範圍。
權利要求
1、一種線程上下文單元，其經配置以轉發線程的指令以供執行，所述線程上下文單元包含加載參考計數器，其經配置以維持指示若干數據請求與若干數據返回之間的差的計數器值；及上下文控制器，其經配置以避免在所述計數器值為非零時提交線程的指令且所述指令包括指示所述指令需要由先前指令返回的數據的數據相依性指示符。
2、 如權利要求1所述的線程上下文單元，其中所述若干數據請求是對來自不可 預測延遲數據源的數據的若干數據請求且所述若干數據返回是來自所述不可預測延 遲數據源的若干數據返回。
3、 如權利要求2所述的線程上下文單元，其中所述不可預測延遲數據源是存儲器。
4、 如權利要求2所述的線程上下文單元，其中所述不可預測延遲數據源是紋理 引擎。
5、 如權利要求2所述的線程上下文單元，其中所述上下文控制器被實施在邏輯 中且包含經配置以檢測所述數據相依性指示符的相依性指示符檢測器。
6、 如權利要求1所述的線程上下文單元，其中所述上下文控制器進一步經配置 以在所述計數器值為零時執行所述指令。
7、 如權利要求2所述的線程上下文單元，其中所述上下文控制器進一步經配置 以在識別所述對來自所述不可預測延遲數據源的數據的請求時遞增所述計數器且經 配置以響應於識別來自所述不可預測延遲的數據的所述返回時遞減所述計數器。
8、 一種線程調度器，其經配置以向用於管理線程的執行的多個線程上下文寄存 器分配所請求的資源，所述線程調度器包含多個加載參考計數器，每一加載參考計數器經配置以維持指示與線程上下文單元 相關聯的若干數據請求與若干數據返回之間的差的計數器值，所述線程調度器經配置 以避免在與線程相關聯的計數器值為非零時轉發所述線程的數據相依指令以供執行 且所述數據相依指令包括指示所述指令需要由所述線程的先前指令返回的數據的數據相依性指示符。
9、 如權利要求8所述的線程調度器，其中所述若干數據請求是對來自不可預測 延遲數據源的數據的若干數據請求且所述若干數據返回是來自所述不可預測延遲數 據源的若干數據返回。
10、 如權利要求9所述的線程調度器，其中不可預測延遲數據源是存儲器。
11、 如權利要求9所述的線程調度器，其中不可預測延遲數據源是紋理引擎。
12、 如權利要求9所述的線程調度器，其中所述線程調度器進一步包含多個相依 性指示符檢測器，每一相依性指示符檢測器經配置以檢測所述數據相依性指示符。
13、 如權利要求8所述的線程調度器，其中所述線程調度器進一步經配置以在所 述計數器值為零時執行所述指令。
14、 如權利要求9所述的線程調度器，其中所述線程調度器進一步經配置以在識 別所述對來自所述不可預測延遲數據源的數據的請求時遞增所述計數器且經配置以 響應於識別來自所述不可預測延遲的數據的所述返回時遞減所述計數器。
15、 一種用於處理圖形線程的圖形處理器，所述圖形處理器包含 算術邏輯單元，其經配置以根據由線程上下文單元管理的圖形線程的指令來執行算術功能；加載控制器，其經配置以根據所述指令從不可預測延遲時間源中檢索數據； 線程調度器，其經配置以向線程上下文單元分配所請求的資源且包含多個加載參考計數器，每一加載參考計數器經配置以維持指示由線程上下文 爭元呈現的對來自不可預測延遲數據源的數據的若干數據請求與由所述加載控制 器執行的來自所述不可預測延遲數據源且與所述線程上下文單元相關聯的若干數 據返回之間的差的計數器值，所述線程調度器經配置以避免在與圖形線程相關聯 的計數器值為非零時轉發所述圖形線程的數據相依指令以供執行且所述數據相依 指令包括指示所述指令需要由所述線程的先前指令返回的數據的數據相依性指示
16、 如權利要求15所述的圖形處理器，其中不可預測延遲數據源是存儲器。
17、 如權利要求15所述的圖形處理器，其中不可預測延遲數據源是紋理引擎。
18、 如權利要求15所述的圖形處理器，其中所述線程調度器進一步包含多個相 依性指示符檢測器，每一相依性指示符檢測器經配置以檢測所述數據相依性指示符。
19、 如權利要求15所述的圖形處理器，其中所述線程調度器進一步經配置以在所述計數器值為零時執行所述指令。
20、 如權利要求15所述的圖形處理器，其中所述線程調度器進一步經配置以在 識別所述對來自所述不可預測延遲數據源的數據的請求時遞增所述計數器且經配置 以響應於識別來自所述不可預測延遲的數據的所述返回時遞減所述計數器。
全文摘要
一種線程調度器包括用於管理線程的執行的上下文單元，其中每一上下文單元包括加載參考計數器，所述加載參考計數器用於維持指示與特定上下文單元相關聯的若干數據請求與若干數據返回之間的差的計數器值。線程上下文單元的上下文控制器經配置以避免在所述計數器值為非零時轉發線程的指令且所述指令包括指示所述指令需要由先前指令返回的數據的數據相依性指示符。
文檔編號G06F9/38GK101506774SQ200780031658
公開日2009年8月12日 申請日期2007年8月27日 優先權日2006年8月29日
發明者春 於, 戈爾夫·焦, 雲 杜 申請人:高通股份有限公司