令牌觸發多線程操作的方法和裝置的製作方法
2023-12-02 15:12:31
專利名稱：令牌觸發多線程操作的方法和裝置的製作方法
技術領域：
本發明大體涉及數字數據處理器領域，尤其涉及用於多線程處理器的線程操作技術。
背景技術：
多線程處理器是支持同時執行多個不同指令序列或「線程」的處理器。例如在1995年由麻薩諸塞州波士頓的Jones和Bartlett出版社出版的M.J.Flynn的「計算機體系結構流水線和並行處理器設計」，和在1997年由麻薩諸塞州雷丁大學的Addison-Wesley出版的G.A.Blaauw和Frederick P.Brooks的「計算機體系結構觀念和發展」中描述了傳統的線程技術，這兩個文獻都包含在這裡以作參考。
作為舉例，被稱為「筒狀多線程操作(barrel multithreading)」的技術允許每個線程根據指定的固定數字序列發出指令。例如，帶有四個按照筒狀多線程的以線程0、線程1、線程2和線程3來表示的多個線程的處理器可以允許線程以固定的數字順序線程0，線程1，線程2，線程3，線程0等發出指令。
筒狀多線程操作和其它現有的線程操作技術存在的問題是這些技術通常配置成不允許發出線程指令的任意序列，或者如果這樣配置時需要過多的硬體來執行它們。
因此現有技術缺乏靈活性，可能對處理器並發性產生不理想的限制。而且，這些技術可以導致阻塞狀況和由此的線程中止，其不利地影響處理器性能。
因此需要改進的技術來用於多線程處理器。
發明內容
本發明提供了用於多線程處理器的令牌觸發線程操作技術。
根據本發明的一個方面，多線程處理器的多個線程的指令發出序列按照這樣的方法來控制將每個所述線程與至少一個寄存器相關聯，所述至少一個寄存器存儲用來識別將被允許發出一個或多個指令的下一個線程的值，和利用該存儲的值來控制該指令發出序列。
作為舉例，在本發明的一個示例性實施例中，多線程處理器的多個硬體線程單元或「上下文」中的每一個都可以包括相應的下一個線程標識符局部寄存器，該寄存器可以由該硬體線程單元升級，用於所述硬體線程單元中給定的一個的局部寄存器存儲一個值，該值用來識別將被允許在所述給定的硬體線程單元已發出一個或多個指令後發出一個或多個指令的下一個線程。
全局寄存器配置也可以或可選擇地被使用。更特別地，可以將所述線程和至少一個可訪問每個所述線程的全局寄存器相關聯，當由所述線程中給定的一個發出指令後該全局寄存器的內容識別將被允許根據所述指令發出序列發出一個或多個指令的另一個線程。
有利地，本發明的多線程處理器可以配置成允許指令發出序列例如對應線程的任意交替偶一奇序列，或者其它任意序列，同時不引起導致線程中止的阻塞狀況。
圖1是一個實現本發明的示例性處理系統的框圖。
圖2是圖1處理系統的多線程處理器的一個示例性實施例的更詳細框圖。
圖3顯示了適用於根據本發明的技術的圖2的多線程處理器的令牌觸發線程操作的一個例子。
圖4顯示了一種方式，在該方式中示例性指令函數可以在根據本發明的技術的圖2多線程處理器中進行流水線處理。
圖5顯示了一個示例性單發流水線，其中圖2處理器的每個線程在每個周期發出一個指令。
圖6顯示了一個示例性多發流水線，其中圖2處理器的每個線程在每個周期發出兩個指令。
圖7顯示了根據本發明配置的並適用於圖2處理器的一組示例性硬體線程單元。
圖8顯示了在圖2處理器的一個示例性實施例中實現的令牌觸發線程操作技術。
具體實施例方式
本發明在這裡將作為在一個示例性多線程處理器中實現來說明。然而應當理解，本發明並不要求使用該示例性實施例的特定多線程處理器配置，而是更一般地適用於任何多線程處理器應用，在這些應用中通過令牌觸發多線程操作與指令流水線配合的使用可以達到提供改進的性能的需要。
將結合圖1和2來描述實現本發明的令牌觸發線程操作技術的一個示例性處理系統100。
圖1顯示了處理系統100，該系統包括連接到主存儲器104的多線程處理器102。該多線程處理器102包括一個多線程高速緩衝存儲器110和一個多線程數據存儲器112。
圖2顯示了多線程處理器102的一個可能實現方式的更詳細視圖。在該實施例中，多線程處理器102包括多線程高速緩衝存儲器110，數據存儲器112，高速緩存控制器114，指令解碼器116，寄存器堆118，和一組算術邏輯部件(ALU)120。該多線程高速緩衝存儲器110在這裡也被稱為多線程高速緩衝。
應當注意，為了使顯示清楚而簡化了圖1和2中所示的特定配置，也可以包括未明確顯示的附加的或可替換的元件，這對於本領域的熟練技術人員來說是顯而易見的。
多線程高速緩衝110包括多個線程緩衝110-1，110-2，…110-N，其中N通常表示根據多線程處理器102的線程的數量。因此每個線程具有在多線程高速緩衝110中的相關的相應線程高速緩衝。類似地，數據存儲器112包括N個不同的數據存儲器實例，其如圖所示地表示為數據存儲器112-1，112-2，…112-N。
多線程高速緩衝110中的每個線程緩衝可以包括具有一組或多組存儲單元的存儲器陣列。給定的線程高速緩衝可以進一步包括用於存儲相關線程標識符的線程標識符寄存器，這將在下面結合圖7進行詳細描述。
多線程高速緩衝110通過高速緩存控制器114與主存儲器104連接。高速緩存控制器114保證了來自主存儲器104的合適指令被加載到多線程高速緩衝110中。在該示例性實施例中的高速緩存控制器114與邏輯電路或與單獨的線程高速緩衝112-1，112-2，…112-N相關的其它處理元件配合地工作，並且執行至少一部分地址映射技術，例如完全關聯映射、直接映射或組相關映射。適合與本發明結合使用的示例性的組相關映射技術描述於申請日為2002年6月4日、序列號為Nos.10/161774和10/161874的美國專利申請中並且與本申請一起被轉讓，該兩個申請都包含於此以作參考。
通常，多線程高速緩衝110用於存儲將要由多線程處理器102執行的指令，而數據存儲器112存儲指令操作的數據。指令由指令解碼器116從多線程高速緩衝110取得，所述解碼器以傳統的方式在控制指令的執行中與寄存器堆118和ALU 120配合操作。諸如116，118和120這樣的多線程處理器元件的操作在本領域中是公知的，因此在這裡不再進一步描述。
數據存儲器112典型地直接連接到主存儲器104，儘管該連接未在圖中明確示出。
一個或多個存儲器104，110和112中每一個都可以配置成包括多個存儲體或其它指定部分。作為示例，每個存儲體可以看作是由一個或多個存儲模塊或者單個存儲模塊的特定部分組成。
關於多線程處理器的這些和其它存儲器的基於線程的存儲體操作技術在上述的代理人檔案號為1007-5、發明名稱為「多線程處理器中基於線程的存儲器訪問的方法和裝置」的美國專利中進行了描述。
對諸如寄存器堆118這樣的寄存器堆的基於線程的訪問技術在上述的代理人檔案號為1007-7、發明名稱為「多線程處理器中寄存器堆埠簡化的方法和裝置」的美國專利申請中進行了描述。
應當強調的是本發明並不要求圖2所示的特定多線程處理器配置。本發明可以用多種其它多線程處理器配置實現。
圖2所示類型的和適合與本發明結合使用的多線程處理器的更特別的例子描述於序列號為No.60/341289、申請日為2001年12月20日的美國臨時專利申請中，該申請包含於此以作參考。如序列號為No.60/341289的美國臨時專利申請所述的多線程處理器的示例性實施例能夠執行基於RISC的控制代碼、數位訊號處理器(DSP)代碼、Java代碼和網絡處理代碼。該處理器包括單指令多數據(SIMD)矢量單元、簡化單元和長指令字(LIW)複合指令執行。
根據本發明的一個方面，提高了諸如圖2的處理器102這樣的多線程處理器的性能。更具體而言，如下面將要更詳細描述的，處理器102根據本發明的技術配置以利用令牌觸發線程操作技術，該技術結合指令流水線操作，以增強處理器並發性和減小線程中止的可能性。
圖3示出了用於實現處理器102的令牌觸發線程操作的一個例子，在該處理器中線程的數量N是八。通常，所有的線程都同時操作，並且每個都訪問線程高速緩衝110和數據存儲器112的相應實例。如圖3所示，這八個線程用線程0，線程1，線程2，…線程7表示，並且顯示成以環的形式串行連接。在該多線程處理器中，給定的線程通常可以看作為硬體和軟體。與給定的線程相關的特定處理器硬體因此在這裡被更特別地稱為硬體線程單元或簡單地稱為「上下文」。
根據圖3所示的令牌觸發線程操作，允許所有的硬體線程單元或上下文同時執行指令，但是僅有一個上下文可以在處理器的一個特定時鐘周期中發出一個指令。也就是說，所有的上下文同時執行但是只有一個上下文在一個特定的時鐘周期是有效的。因此，如果總共有C個上下文，那麼需要C個時鐘周期來從所有的上下文發出一個指令。在每個時鐘周期，一個上下文發出一個指令，令牌指示下一個線程發出一個指令。
在圖3的例子中，令牌以順序的或循環的方式設置，從而上下文將順序地發出指令。然而，令牌指示下一個上下文發出指令可設置成使用其它模式，例如交替偶-奇模式。而且，如上所述，其它類型的線程操作也可以與本發明結合使用。下面將結合圖7和8更詳細地描述本發明的多個示例性線程操作技術。
圖4顯示了一種方式，在該方式中示例性指令函數可以在根據本發明的多線程處理器102中進行流水線處理。在本發明的示例性實施例中，該類型的流水線優選地與前面所述的令牌觸發線程操作結合使用，但是應當理解流水線和線程操作的多種其它組合也可以用於實現本發明。
圖4的流水線設置成與圖3的示例性N＝8個令牌觸發線程結合使用。圖4中示例性指令函數包括加載/存儲(Ld/St)，ALU，整數乘法(I_Mul)和矢量乘法(V_Mul)，並且被顯示成分別具有九，六，七和八個流水線階段。
圖4中所示的每個示例性指令流水線包括至少一個指令解碼階段，一個寄存器堆(RF)讀入階段，一個轉移(Xfer)階段和一個寫回(WB)階段。RF讀入階段包括從諸如寄存器堆118這樣的寄存器堆讀入，轉移階段典型地包括將指令結果轉移到指定的保持寄存器，WB階段包括將指令結果寫回到存儲器或寄存器堆。
Ld/St流水線進一步包括地址生成(Agen)階段，內部(Int)或外部(Ext)確定階段，和三個附加存儲器執行階段，其表示為Mem0，Mem1，Mem2。Ld/St流水線因此總共包括四個存儲器執行階段，也就是，Mem0，Mem1，Mem2和WB。內部或外部確定階段確定相關的存儲器訪問是內部的還是外部的存儲器，並且可以被看作為流水線中附加的解碼階段。應當注意可能要求附加的存儲器執行階段以用於某些外部存儲器訪問。例如，如果外部存儲器訪問的WB階段在相應線程有效的期間未完成，那麼該線程可以被中止，從而WB階段將在下一次該線程有效的時候完成。
ALU流水線進一步包括由Exec1和Exec2表示的兩個執行階段。
整數I_Mul流水線進一步包括由Exec1，Exec2和Exec3表示的三個執行階段。
矢量V_Mul流水線進一步包括兩個乘法階段MPY1和MPY2，和兩個加法階段Add1和Add2。
多線程處理器102優選地配置成一旦來自特定上下文的指令進入其相應流水線，它運行到完成。
使用適當配置的流水線和足夠數量的線程，即使在每個周期每個上下文只發出一個單指令，所有的硬體上下文都可以並發地執行。如前面所指出的，所述特定數量的線程和流水線階段僅僅是作為示例，並不意味著反映優選的實現方式。在這裡所提供的教導下本領域的技術人員將能夠容易地確定對於特定應用的合適數量的線程和流水線階段。
現在將參考圖5和6描述圖4的流水線的操作的多個例子。圖5和6每一個的圖示都顯示了由特定處理器線程發出的指令序列，並且為每個指令指示相應線程利用了寄存器堆118的偶數(e)部分還是奇數(o)部分。上述的代理人檔案號為1007-7、發明名稱為「多線程處理器中寄存器堆埠簡化的方法和裝置」的美國專利申請說明了寄存器堆118怎樣可以被分為偶數和奇數部分的一個例子，使用線程標識符可選擇這些部分中特定的一個。
在圖5和6的例子中，為了描述的簡化和清楚而假設線程的數量N等於4，及每個線程根據圖3令牌觸發線程操作的循環執行方式發出指令。更具體而言，在這些例子中每個線程發出交替的加載和矢量乘法指令，這是在許多信號處理應用中的一個典型的指令序列。該加載和矢量乘法指令基本上如圖4所示的指令函數流水線所述的方式設置。
現在參考圖5，其顯示了單發流水線的一個例子，其中每個線程在每個周期發出一個指令。從圖5中可以看出由發出的指令訪問的寄存器堆部分在線程和線程之間以偶(e)和奇(o)交替。這保證了相鄰寄存器寫回操作，例如那些與線程4的第一加載指令和線程1的矢量乘法指令相關的操作，被引導到寄存器堆的不同部分。更具體而言，線程4的第一加載指令被引導到寄存器堆1的偶數部分，而線程1的矢量乘法指令被引導到寄存器堆的奇數部分。該圖中所示的其它指令以類似的方式被設置。
線程標識符用於選擇給定的線程將訪問寄存器堆的偶數還是奇數部分。例如，在圖5和6的N＝4的情況下，線程標識符的最低有效位(LSB)能夠用於在寄存器堆的偶數和奇數部分之間進行選擇。
圖6顯示了一個示例性多發流水線，其中每個處理器線程在每個周期發出兩個指令。在這裡，單線程在每個周期發出加載和矢量乘法指令。由於在每個周期發出多個指令，因此圖5的例子需要兩個附加的寄存器堆讀入埠。然而，在該圖中可以看出，所有的並發寫入仍然是寄存器的偶數或奇數部分，其由線程標識符的LSB確定，所以所需的寄存器堆寫入埠數量和由此的處理器能量消耗被減少。
應當強調的是與圖5和6結合的所示線程的特定數量僅僅是示例性的，本發明並不限於使用任何特定的線程數量。
圖7顯示了硬體線程單元702-i，i＝1，2，…N的組700，其可以在根據本發明的圖2多線程處理器中執行。如前面所述，這種硬體線程單元在這裡也可以稱為上下文，通常存在與處理器支持的每個線程相關的一個這種單元或上下文。每個硬體線程單元702包括一個線程標識符(TID)寄存器704和一個下一個線程標識符(NTID)寄存器706。另外，每個硬體線程單元702可以包括一個相應的線程高速緩衝110和數據高速緩衝112，以及或可選擇的高速緩存控制器114或其它處理器電路的相關部分。
根據本發明，每個硬體線程單元702可以在一個給定的處理器周期發出一個或更多的指令。在一個給定硬體線程單元中的TID寄存器704存儲相應線程的線程標識符。在該給定的硬體線程單元中的NTID寄存器706存儲下一個硬體線程單元的線程標識符，該下一個硬體線程單元將在該給定的硬體線程單元已發出其指令(一個或多個)之後發出一個指令。該NTID寄存器706因此可以被看作存儲關於本發明的令牌觸發線程操作技術的令牌。該令牌可以被所述給定的硬體線程單元設置成任何其它硬體線程單元的線程標識符，由此在令牌觸發多線程處理中提供很大的靈活性。
儘管在圖7中作為可由相應硬體線程單元獨立編程的局部寄存器示出，NTID寄存器也可以或可選擇地作為可訪問所有硬體線程單元的全局寄存器而實現。在該情況下，每個硬體線程單元不需要串連地增加全局NTID寄存器。例如，在硬體線程單元外部執行的狀態機或其它類似的電路可以用於對全局NTID寄存器編程以提供任何期望的令牌序列。
圖8顯示了對應交替偶一奇模式的示例性令牌序列。在特定的N＝8的令牌觸發線程操作例子中的該令牌序列是線程0(T0)，線程3(T3)，線程2(T2)，線程1(T1)，線程6(T6)，線程5(T5)，線程4(T4)，線程7(T7)，線程0(T0)，等等。
該例子表明如圖7所示的NTID寄存器的使用允許每個上下文在一個偶—奇模式中將令牌授予任何其它上下文而不在執行流水線中導致任何衝突，由此不導致線程中止。該線程操作技術與指令流水線操作的組合明顯地減小了阻塞狀況的數量並允許偶—奇線程序列的任意執行。
如前面所述，線程標識符寄存器704存儲多位線程標識符，多線程處理器102使用該多位線程標識符來識別特定的線程。這種線程標識符可以用傳統方式產生，這對於本領域的技術人員是顯而易見的。
這裡所用的術語「線程標識符」意味著包括適合識別多線程處理器中特定線程或一組多線程的任何信息。作為示例而非限定，n位線程標識符可以用於唯一地識別該多線程處理器支持的N＝2n線程中的一個。適合用於本發明的各種不同的線程標識符設置對於本領域的熟練技術人員來說是顯而易見的。
如上所述，本發明的令牌觸發線程操作技術與傳統的技術相比具有明顯的進步。例如，該技術能夠大幅減小線程中止的可能性。而且，這些改進不會影響處理器的並發性或處理器性能的其它方面。
本發明的上述實施例意味著僅僅是示例性的，附加權利要求範圍內多種可選擇實施例對於本領域的熟練技術人員來說是顯而易見的。例如，多線程處理器配置，線程的數量，線程標識符設置和該示例性實施例的其它參數可以進行變化以適應給定應用的特殊需要。
權利要求
1.控制多線程處理器的多個線程的指令發出序列的方法，該方法包括以下步驟將每個所述線程與至少一個寄存器相關聯，所述至少一個寄存器存儲用來識別將被允許發出一個或多個指令的下一個線程的值；和利用該存儲的值來控制該指令發出序列。
2.根據權利要求1所述的方法，其中所述關聯步驟進一步包括將所述多線程處理器的多個硬體線程單元的每一個與可由該硬體線程單元升級的相應的局部寄存器相關聯的步驟，用於所述硬體線程單元中給定之一的局部寄存器存儲一個值，該值用來識別將被允許在所述給定的硬體線程單元已發出一個或多個指令後發出一個或多個指令的下一個線程。
3.根據權利要求1的方法，其中所述關聯步驟進一步包括將多個寄存器與多個硬體線程單元相關聯的步驟，所述多個寄存器包括用於每個所述硬體線程單元的一個線程標識符寄存器，該線程標識符寄存器存儲相應硬體線程單元的線程標識符，和下一個線程標識符寄存器，該下一個線程標識符寄存器存儲指定硬體線程單元中將被允許發出一個或多個指令的下一個硬體線程單元的下一個線程標識符。
4.根據權利要求1的方法，其中所述關聯步驟進一步包括將每個所述線程和至少一個可訪問每個所述線程的全局寄存器相關聯的步驟，當由所述線程中給定之一發出指令後，該全局寄存器的內容識別將被允許根據所述指令發出序列發出一個或多個指令的另一個線程。
5.根據權利要求1的方法，其中所述關聯和利用步驟設置成允許所述指令發出序列對應任意的交替偶—奇線程序列，同時不引起導致線程中止的堵塞狀況。
6.根據權利要求1的方法，其中所述至少一個寄存器包括一個n位寄存器，該寄存器適合存儲2n線程中給定之一的唯一標識符。
7.根據權利要求1的方法，其中所述至少一個寄存器與一個線程高速緩衝相關聯，該線程高速緩衝對應所述多線程處理器的一個特定線程。
8.根據權利要求1的方法，其中存儲在所述至少一個寄存器中的所述值包括關於令牌觸發線程操作的令牌。
9.根據權利要求8的方法，其中所述令牌觸發線程操作利用該令牌來在當前的處理器周期中識別所述多個線程中將被允許在下一個時鐘周期發出一個指令的特定的一個線程。
10.根據權利要求8的方法，其中所述令牌觸發線程操作將不同的令牌分配到所述多線程處理器的多個線程中的每一個。
11.根據權利要求1的方法，其中所述多線程處理器配置成用於流水線指令處理。
12.根據權利要求11的方法，其中所述多線程處理器利用指令流水線，在該指令流水線中每個線程在每個處理器時鐘周期中發出單指令。
13.根據權利要求11的方法，其中所述多線程處理器利用指令流水線，在該指令流水線中每個線程在每個處理器時鐘周期中發出多個指令。
14.根據權利要求13的方法，其中多個所述線程中的每一個在相應多個處理器時鐘周期中的每一個發出加載和指令乘法指令，同時不中止所述多個線程。
15.一種多線程處理器，其包括多個硬體線程單元並且配置成用於控制該多線程處理器的多個線程的指令發出序列，其中在該處理器中，每個所述線程與至少一個寄存器相關聯，所述至少一個寄存器存儲用來識別將被允許發出一個或多個指令的下一個線程的值，該存儲的值用於控制該處理器的所述指令發出序列。
16.一種製造的產品，其包括機器可讀的存儲介質，該存儲介質具有嵌入其中的程序代碼以用於控制一個多線程處理器的多個線程的指令發出序列，其中當由該處理器執行時該程序代碼執行下述步驟將每個所述線程與至少一個寄存器相關聯，所述至少一個寄存器存儲用來識別將被允許發出一個或多個指令的下一個線程的值；和利用該存儲的值來控制該指令發出序列。
全文摘要
本發明公開了一種多線程處理器中的令牌觸發多線程操作技術。多線程處理器的多個線程的指令發出序列按照這樣的方法來控制將每個所述線程與至少一個寄存器相關聯，所述至少一個寄存器存儲用來識別將被允許發出一個或多個指令的下一個線程的值，和利用該存儲的值來控制該指令發出序列。例如，多線程處理器的多個硬體線程單元中的每一個可以包括可由該硬體線程單元升級的相應的局部寄存器，用於所述硬體線程單元中給定之一的該局部寄存器存儲一個值，該值用來識別將被允許在所述給定的硬體線程單元已發出一個或多個指令後發出一個或多個指令的下一個線程。全局寄存器配置也可以或可選擇地被使用。該處理器可以配置成允許所述指令發出序列對應任意的交替偶—奇線程序列，同時不引起導致線程中止的堵塞狀況。
文檔編號G07FGK1711563SQ200380102976
公開日2005年12月21日 申請日期2003年10月9日 優先權日2002年10月11日
發明者E·赫凱內克, M·穆杜吉爾, J·C·格洛斯納 申請人:沙橋技術有限公司