[發(fā)明專利]用于線程排序的方法、裝置和系統(tǒng)

有效

• 申請?zhí)枺?/td>: 200910160558.5
• 申請日: 2009-07-30
• 公開（公告）號: CN101639789B
• 公開（公告）日: 2019-02-15
• 發(fā)明（設計）人: M·K·杜耶;R·L·法瑞爾;H·蔣;T·A·皮亞扎
• 申請（專利權）人: 英特爾公司
• 主分類號: G06F9/46
• 分類號: G06F9/46;G06T1/20
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 錢慰民;謝喜堂

本發(fā)明描述可用于在多線程環(huán)境中確保線程的有序計算和/或回退的技術。線程可包含綁定的工作實例，每個工作實例相對于系統(tǒng)中其它線程中所封裝的工作實例具有獨特排序限制。當應用于3D圖形時，視頻和圖形處理域允許不受限制的線程處理，直到到達其關鍵部分。可在執(zhí)行關鍵部分等之前請求排序。

技術領域

本文所公開的主題涉及管理操作的順序，尤其涉及線程處理的排序。

相關領域

在很多計算機應用中，存在由例程和其上應用例程的數(shù)據(jù)集提供的固有并行度。并行度可包括由具有最小排序要求的例程處理數(shù)據(jù)集的分立元素，達到例程可同時應用于數(shù)據(jù)集的很多元素的程度，假設存在足夠的計算資源來這樣做。在這種情形中，數(shù)據(jù)和指令被綁定為“線程”，并發(fā)送至計算陣列以供處理。由于并行度，線程的很多實例可在任何時間點存在于計算陣列中，且某些線程可相對于系統(tǒng)中的其它類似線程提前或延遲其處理，這取決于很多系統(tǒng)級因素。因此，線程的完成可以不按線程發(fā)出的順序。在需要排序的情形中，可能需要用于確保滿足排序要求的技術，且期望該技術對總體性能具有最小的負面影響。

例如，并行度尤其存在于圖形處理中，從而使其高度線程化。在某些圖形處理系統(tǒng)中，對于給定XY坐標屏幕位置的一系列像素有排序要求以便于以它們在本申請中所呈現(xiàn)的順序回退。回退的像素系列是其中已經(jīng)完成計算且像素可用于顯示的像素系列。例如，回退的像素可被存儲在幀緩沖器中。在三維像素處理算法中，由于同時處理的像素的量及其與系統(tǒng)資源的交互，像素處理可無序地完成，這可導致相同XY坐標的像素無序回退。

在某些情形中，XY像素位置的流在任意相同XY系列之間具有有效時間，使得在請求涉及相同XY的計算之前任何涉及對該XY寫入的計算不再運行。無論通過系統(tǒng)的典型或自然排序如何，都需要一種保證正確排序的機制。

無論背景如何，線程化系統(tǒng)可使用實現(xiàn)正確計算和/或輸出排序的技術。在關于線程化計算的一般情形中，一個已知的排序系統(tǒng)通過阻擋對計算單元的線程發(fā)布(或“分派”)直到滿足所有的排序請求來實現(xiàn)排序處理和/或輸出。在這種情形中，記錄板用于跟蹤系統(tǒng)中線程和用于檢測線程之間的相關性的邏輯的狀態(tài)。在其中僅要求輸出排序的情形下，另一個已知系統(tǒng)使用臨時存儲線程輸出的緩沖器，且最終直到滿足關于相關聯(lián)線程的所有排序規(guī)則才回退輸出。

發(fā)明內容

根據(jù)本申請的一個方面，提出了一種用于線程排序的方法，包括：存儲線程標識符的陣列，其中所述線程標識符標識在工作單元的處理中所涉及的線程；響應于線程回退的指示，清除回退線程的標識符；響應于嘗試執(zhí)行線程的關鍵區(qū)指令，確定是否所有其它與所述線程相關聯(lián)的前導工作單元被請求相關性清除；以及響應于每個其它前導工作單元的相關性清除，完成允許執(zhí)行所述關鍵區(qū)指令。

根據(jù)本申請的另一個方面，提出了一種用于線程排序的裝置，包括：記錄板，用于存儲用于處理工作單元的線程的至少一個標識符；線程生成器，用于標識各個未決線程，所述未決線程將處理就與第一線程相關聯(lián)的工作有排序要求的工作單元；線程相關性寄存器，用于存儲與所述第一線程的每個工作單元相關聯(lián)的未決線程標識符；執(zhí)行單元，響應于線程回退的指示，清除回退線程的標識符，并執(zhí)行所述第一線程，其中所述執(zhí)行單元執(zhí)行第一線程直到到達關鍵區(qū)指令，其中所述執(zhí)行單元響應于用于所述第一線程的線程相關性寄存器指示所有相關性已經(jīng)被清除而選擇性地執(zhí)行所述關鍵區(qū)指令；以及監(jiān)視已完成線程的線程回退處理器。