動態優先級外部事務處理系統的製作方法
2023-10-08 13:40:04
專利名稱：動態優先級外部事務處理系統的製作方法
背景技術：
人們知道，許多現代計算系統採用多代理者體系結構(multi-agentarchitecture)。
圖1示出一種典型的系統。其中多個代理者110-160按照預定的總線協議在外部總線170上進行通信。「代理者」可以包括通用處理器110-140、存儲器控制器150、接口晶片集160、輸入輸出裝置和/或其它對數據請求進行處理的集成電路(未示出)。總線170可允許同時進行幾個外部總線事務處理。
代理者(例如110)通常包括事務處理管理系統，該管理系統接收來自所述代理者的其它部件的請求一般並處理外部總線事務處理以實現所述請求。圖2所示的總線排序單元200(「BSU」)，是這樣一種事務處理管理系統的示例。BSU200可以包括仲裁器210、內部高速緩存220、內部事務處理隊列230、外部事務處理隊列240、外部總線控制器250和預取隊列260。BSU200響應由例如代理者核心(圖2中未示出)發出的數據請求而管理外部總線170上的事務處理。
仲裁器210不僅可以接收來自所述核心的數據請求，而且還可以接收來自諸如預取隊列260的各種其它源的數據請求。仲裁器210可以在仲裁器210同時收到的可能的幾個數據請求中進行選擇，並將其中的一個輸出到BSU200的其餘部分。
內部高速緩存220可以將數據存儲在幾個高速緩存項目中。它可能具有對數據請求作出反應以確定高速緩存220是否存儲請求數據的有效拷貝的邏輯。這裡用到的「數據」可以指可以由代理者使用的變量數據和指令數據。內部高速緩存220可以響應數據請求而供給請求數據。
內部事務處理隊列230也可以接收並存儲仲裁器210發出的數據請求。對於讀取請求，內部事務處理隊列230與內部高速緩存220配合以確定請求數據是否「命中」內部高速緩存220(可由內部高速緩存220供給)。如果不，如果數據請求「錯過」內部高速緩存220，則內部事務處理隊列230將數據請求轉發到外部事務處理隊列240。
外部事務處理隊列240可以解釋數據請求並生成外部總線事務處理來完成它們。外部事務處理隊列240可以包括幾個隊列寄存器。它在代理者的事務處理在外部總線170上進行時對它們進行管理。例如，當數據可用於響應事務處理時，外部事務處理隊列240檢索該數據並將其轉發到代理者中的請求者(例如核心)。
預取隊列260可以識別由核心(未示出)發出的讀取請求中的預定模式。例如，如果核心發出指向順序增加的存儲單元(地址A、A+1、A+2、A+3、…)的讀取請求，則預取隊列260可以發出預取請求，以便在核心實際請求數據本身之前從順序中的下一個地址(A+4)讀取數據。通過預期數據需要，預取隊列260可以使數據在核心發出數據請求時可在內部高速緩存220中得到。將從內部高速緩存220而不是外部存儲器向核心供給數據—快得多的操作。這裡，這種類型的預取請求被稱為「模式預取(patterned prefetch)」。
BSU200可以實現第二類型的預取，這裡稱為「盲預取(blindprefetch)」。當核心發出將由外部總線事務處理完成的對某個地址(假定地址B)的數據的讀取請求時，盲預取機制可使第二外部總線事務處理檢索第二存儲地址(B+1)的數據。盲預取可以使不能內部完成的來自核心的每個讀取請求產生一對外部總線事務處理。盲預取可以通過兩次檢索同滿足核心讀取請求所需的一樣多的高速緩存線(或高速緩存扇區)來改進處理器性能。再且，如果核心最終需要從其它地址(B+1)預取的數據的數據，則在核心發出數據讀取請求時可以在內部高速緩存220中得到數據。也可以從模式預取請求生成盲預取請求。利用上述示例，可以由對地址A+5的盲預取增加對地址A+4的模式預取請求。
回到圖1，眾所周知，特別是在多處理器計算機系統中，外部總線170會限制系統性能。外部總線170通常操作在遠低於代理者的內部時鐘速度的時鐘速度下。核心通常會在外部總線170能完成單個外部總線事務處理的時間發出幾個數據請求。這樣，單個代理者會消耗外部總線170的大量帶寬。當多個代理者必須共享外部總線170時，每個代理者只分配有總線170上可用帶寬的一部分。在多代理者系統中，在外部總線檢索代理者進程所需的數據時，代理者常常必須空閒地等待。
外部事務處理隊列240(圖2)可以包括對等候發送到外部總線的請求按優先級排序的控制邏輯。通常，核心讀取應該優先於預取讀取，而預取讀取應該優先於寫入。核心讀取請求識別核心立即需要的數據。預取讀取請求識別核心可能在將來某個時間需要的數據。寫入請求識別代理者正返回給系統存儲器的數據。因此，外部事務處理隊列240可以包括根據所述優先級把請求發送到外部總線上的控制邏輯。
預定優先級方案具有其不足。請求通常被存儲在事務處理隊列240中，直到它在總線上被完成。在高擁擠階段期間，當事務處理隊列完全或幾乎滿了的時候，預取和寫入請求會阻止新的核心請求被存儲在隊列240中。這些較低優先級的請求將繼續存儲在隊列中，直到請求的外部總線事務處理完成。這樣，較低優先級的請求會阻止較高優先級的請求被執行。這會限制系統的性能。
因此，技術上在代理者中需要用於外部事務處理隊列的擁擠管理系統。技術上需要這樣一種系統它提供動態優先級系統—在沒有系統擁擠時保持第一優先級方案，但在擁擠事件出現時執行第二優先級。
發明內容
本發明的實施例提供一種用於代理者的多模式事務處理隊列。所述事務處理隊列可以按照預設優先級方案操作。當檢測到擁擠事件時，事務處理隊列可以使用第二優先級方案。
附圖簡述圖1是多代理者計算機系統的方框圖。
圖2是代理者的示例性總線排序單元的方框圖。
圖3是按照本發明一個實施例的代理者的外部事務處理隊列的方框圖。
圖4是按照本發明一個實施例的擁擠管理方法的流程圖。
詳細描述本發明的實施例提供一種事務處理隊列，它提供對擁擠事件的測量響應。事務處理隊列選擇性地使隊列中正在等候的存儲的事務處理無效—它們目前未被發送到外部總線。在一個實施例中，事務處理隊列首先使盲預取請求無效。事務處理隊列還可以使未發送的預取請求無效，其中所述未發送的預取請求與有關發送的預取請求被存儲。最後，在極端擁擠的情況下，如沒有可用於新請求的空間時，事務處理隊列可以使未發送的模式預取請求對無效。
這些實施例有利地提供具有動態優先級方案的事務處理隊列。在沒有擁擠時，事務處理隊列可以按照第一優先級方案操作。例如如上所述，事務處理隊列可以使核心讀取請求優先於預取請求，並使預取請求優先於寫入請求。可是，當擁擠事件出現時，事務處理隊列可以採用第二優先級方案。例如，事務處理隊列可以將核心讀取保持為最高優先級請求，而將寫入請求的優先級重新安排為次最高優先級請求。
圖3是按照本發明的一個實施例的代理者的外部事務處理隊列300的方框圖。外部事務處理隊列300可以包括控制器310和多個隊列寄存器320-1到320-N(共同標記為320)。各個隊列寄存器可以包括幾個欄位，包括地址欄位330、第一狀態欄位340和第二狀態欄位350。
外部事務處理隊列300可適合用於執行盲預取的代理者。狀態欄位340、350每個都可以存儲有關按照盲預取對來執行的外部總線事務處理中相應一個的信息。地址欄位330可以存儲事務處理將被定向到的基地址。通常，在地址欄位330和狀態欄位340、345之間將存在預定關係。例如，如果地址D被存儲在寄存器320-1的地址欄位330中，則狀態欄位340可以保持有關定向到地址D的事務處理的狀態信息，並且狀態欄位350可以保持有關定向到地址D+1的第二事務處理的狀態信息。
狀態欄位340、350可以存儲關於相應的事務處理的管理信息。這樣的信息可以包括請求類型、關於外部總線上相應的事務處理的狀態的信息(即它是否被發送、請求可能在哪一個事務處理階段、事務處理是否完成等)和關於按照事務處理可能收到的數據的目的地的信息。通常，當狀態寄存器340、350兩者都表明其相應的事務處理已經完成時，從寄存器320清除所述事務處理。
按照本發明的一個實施例，狀態欄位340、350每一個都可以包括子欄位，該子欄位識別是否按照核心請求(「C」)或按照預取請求(「P」)生成對應的事務處理。圖3說明了7個請求為核心請求和乘下的為預取請求的示例。在該示例中，存儲在寄存器320-1、320-4、320-5、320-6、320-8、320-11和320-N中的事務處理存儲由核心請求啟動的事務處理。那些寄存器的狀態欄位340或350中的一個識別源於核心請求的事務處理；其它狀態欄位表明盲預取請求。
其它寄存器320-2、320-3、320-7、320-9和320-10識別由盲預取增加的模式預取請求。狀態欄位340、350兩者都表明請求是預取請求。
控制器310把外部事務處理隊列300連接到代理者中的其它元素(例如參見圖2)。控制器310可以使事務處理被輸入到隊列寄存器320中或從其中刪除事務處理，並可以把數據寫入到地址欄位330以及寫入到狀態欄位340、350。控制器310還可以為要發送到外部總線170(圖1)的事務處理安排次序。在一個實施例中，控制器310可以是狀態機。
按照本發明的一個實施例，控制器310可以BSU 200中的擁擠事件期間選擇性地禁止預取請求。在第一實施例中，當事務處理300經歷擁擠時，事務處理隊列可以禁止還未被發送到外部總線上的任何盲預取事務處理。這可以例如通過即使事務處理從未被發送也把盲預取事務處理的狀態欄位標記為完成來實現。在此實施例中，當在外部總線上完成核心讀取請求時，可以從事務處理隊列300中逐出事務處理。
在另一個實施例中，當事務處理隊列經歷擁擠時，事務處理隊列300可以逐出存儲在隊列中還未被發送到外部總線上的任何模式預取請求。事務處理隊列300可以簡單地通過解除對有關隊列寄存器的分配來逐出未開始的預取請求。
在又一個實施例中，當事務處理隊列經歷擁擠，並且事務處理隊列300存儲已經開始的模式預取事務處理時，事務處理隊列300可以禁止預取對中的任何未發送的預取事務處理。考慮圖3的寄存器320-2中示出的模式預取請求。如所示的那樣，狀態欄位350表明第一預取事務處理正在等候但還沒有被發送到外部總線上。相反，狀態欄位340表明第二預取事務處理已經被發送到外部總線上。在該實施例中，事務處理隊列300可以響應於擁擠事件而把第一事務處理標記為完成。在這種情況下，第二預取請求將被允許繼續完成。當它完成時，事務處理隊列300可以解除對寄存器320-2的分配，因為狀態340、350兩者都識別完成的事務處理。
圖4是按照本發明的一個實施例可以由事務處理隊列300(圖3)執行的方法1000的流程圖。在擁擠事件時，事務處理隊列可以確定新請求是否被輸入到事務處理隊列(步驟1010)。在收到新請求時，事務處理隊列可以確定是否有新請求可用的寄存器(步驟1020)。如果是，則它把請求存儲在可用的寄存器中(步驟1030)。可以按照在本領中的傳統方法執行請求的存儲。事務處理隊列300可以確定請求的基地址並在分配的寄存器的各個欄位330-350中輸入適當的信息。
如果在步驟1020中沒有可用的寄存器，則事務處理隊列300可以解除對與一對未發送的模式預取請求有關聯的寄存器的分配(步驟1040)。在執行該步驟中，事務處理隊列300可以解除狀態欄位340、350都表明相應的事務處理還未被發送到外部總線的模式預取請求的分配。如果寄存器320中沒有一個識別一對未開始的預取請求，則新接收的請求可以被安裝(步驟未示出)。該請求被禁止輸入事務處理隊列。
在步驟1030結束時，或者在步驟1010沒有收到請求，事務處理隊列確定它是否正在擁擠模式下操作(步驟1050)。如果不是，事務處理隊列300可以停止方法1000的這種重複。
如果事務處理隊列300正在擁擠模式下操作，則事務處理隊列確定它是否存儲任何等候的盲預取事務處理(步驟1060)。如果是，事務處理隊列300可以禁止盲預取事務處理的其中之一(步驟1070)。步驟1070可以應用於與核心請求有關的盲預取或模式預取請求。如果不是，或者在步驟1070結束時，該方法可以結束。
方法1000有利地提供對擁擠的測量響應。作為第一響應，事務處理隊列使來自事務處理隊列的盲預取請求無效。如所討論的那樣，作為類的預取請求次於核心請求。經驗也表明使盲預取次於模式預取是適當的。模式預取可能比盲預取更有效。對存儲器的核心讀取的建立模式進行響應而發出模式預取。盲預取不依賴任何種類的可測量標記。這樣，模式預取更可能檢索核心最終將請求的數據，並應該有利於盲預取而被保持。
當盲預取被無效時，它增加了寄存器320可用於新接收的請求的速率。如說明的那樣，盲預取與核心讀取請求有關。核心讀取請求是由事務處理隊列處理的最高優先級的請求—它們以最高優先級被發送到外部總線上。
在優先級的第二級，如果擁擠即使在所有預取都被無效後仍然繼續，則事務處理隊列可以使與進行中的預取請求有關的等候的模式預取請求無效(步驟1080)。因為預取請求中的一個已經被發送到外部總線上，因此它可能在預定時間內結束。可是，即使它結束，第二等候的預取請求的狀態(在步驟1080中被無效的那個)會阻止有關寄存器被解除分配。通過把等候的預取請求標記為完成，步驟1080確保在發送的預取請求結束時解除對寄存器的分配。
在優先級的第三級，事務處理隊列有利於新收到的請求而解除對存儲一對等候的預取請求的寄存器的分配。這種情況僅在新接收的請求沒有可用的寄存器時出現。
本發明的原理允許幾個不同的觸發事件以使事務處理隊列300判定它是否在擁擠模式下操作。在第一實施例中，事務處理隊列300可以根據隊列中被分配了的或未被分配的寄存器320的數量來確定它是擁擠的。例如，如果事務處理隊列確定寄存器滿到90％或100％，它可判決它是在擁擠模式下操作。
在第二示例中，事務處理隊列可以根據外部總線的測量的等待時間來確定擁擠事件已經出現。人們知道，代理者通常按照預定的總線協議操作。總線協議可以建立管理規則，以管理新請求何時可被發送到外部總線上以及的多個可能的代理者中的哪一個可能在各請求「時隙」中把新請求發送到總線上，每個時機把一個新請求發送到總線上。在這樣一個實施例中，事務處理隊列300可以測量若干在事務處理隊列300獲得總線所有權之前傳送的請求時隙。如果測量的時隙數超過預定閾值，則事務處理隊列300可以確定擁擠事件已經出現。
按照另一個實施例，事務處理隊列300根據檢測的一種類型的擁擠不同地響應擁擠事件。考慮事務處理隊列可以檢測上述兩種類型的觸發事件的示例1)可用寄存器的數量低於某閾值數(假設事務處理隊列全滿)，以及2)測量的外部總線上的等待時間超過閾值量。按照一個實施例，事務處理隊列300可以在事務處理隊列300全滿時使所有預取請求無效，而在測量的外部總線上的等待時間超過閾值時僅使盲預取請求無效。該實施例會是有利的，因為它具有簡單的實現並區分低嚴重性和高嚴重性的擁擠事件。
前面的討論區分了等候和發送請求。這裡，發送請求是已經在外部總線上開始的請求。通常，外部總線由預定總線協議定義，它指定事務處理完成經歷的增加的階段。前面實施例中描述的擁擠管理方法不幹擾已經發送的事務處理。相反，等候的請求是存儲在BSU中的但還未在外部總線上開始的請求。本發明的擁擠管理方法可以按照前面實施例中描述的那些技術來使等候請求無效。
如上所述，本發明的實施例提供事務處理隊列300，它可以按照動態優先級方案操作。第一優先級方案可被定義用於沒有擁擠時的事務處理隊列。但是在檢測到擁擠時，事務處理隊列可以執行第二優先級方案。在上述實施例中，事務處理隊列可以使預取請求無效。
前面實施例中描述的擁擠管理技術針對於讀取由事務處理管理系統處理的請求。人們知道，BSU可以處理其它類型的請求，如寫入請求，它們不是用來使數據被讀入代理者。前面實施例描述的擁擠管理技術不是用來幹擾事務處理管理系統處理這些其它類型的請求的方法。
在此具體示出並描述了本發明的幾個實施例。可是要知道，在不脫離本發明的精神和預期範圍下的本發明的修改和變化被上述示教所覆蓋並在後附權利要求書的範圍內。
權利要求
1.一種用於代理者的事務處理隊列，它按照動態優先級方案操作，所述事務處理隊列按照預設優先級方案操作並在檢測到擁擠事件時使用第二優先級方案。
2.一種在代理者中的用於外部事務處理的管理方法，它包括對多個讀取請求的數據進行排隊，對於各個排隊的請求，存儲與相應的所述請求有關的盲預取事務處理的數據，當事務處理擁擠事件出現時，禁止選定的被存儲的預取請求。
3.如權利要求1所述的管理方法，其特徵在於所述事務處理擁擠事件在排隊的請求的數量超過預定閾值時出現。
4.如權利要求1所述的管理方法，其特徵在於所述事務處理擁擠事件在存儲所述排隊的請求的隊列變滿時出現。
5.如權利要求1所述的管理方法，其特徵在於所述事務處理擁擠事件在發送事務處理的測量的等待時間超過預定閾值時出現。
6.一種在代理者中的用於外部事務處理的管理方法，它包括對多個外部總線事務處理的數據進行排隊，對於至少一個排隊的事務處理，存儲與所述相應的事務處理有關的盲預取事務處理的數據，當事務處理擁擠事件出現時，禁止所述盲預取事務處理。
7.如權利要求6所述的管理方法，其特徵在於所述事務處理擁擠事件在排隊的請求的數量超過預定閾值時出現。
8.如權利要求6所述的管理方法，其特徵在於所述事務處理擁擠事件在存儲所述排隊的請求的隊列變滿時出現。
9.如權利要求6所述的管理方法，其特徵在於所述事務處理擁擠事件在發送事務處理的測量的等待時間超過預定閾值時出現。
10.一種在代理者中的用於外部事務處理的管理方法，它包括對多個讀取請求、與代理者核心執行的執行有關的某些讀取請求、與預取的數據有關的某些其它讀取請求的數據進行排隊，當事務處理擁擠事件出現時，禁止所述預取請求。
11.如權利要求10所述的管理方法，其特徵在於所述事務處理擁擠事件在排隊的請求的數量超過預定閾值時出現。
12.如權利要求10所述的管理方法，其特徵在於所述事務處理擁擠事件在存儲所述排隊的請求的隊列變滿時出現。
13.如權利要求10所述的管理方法，其特徵在於所述事務處理擁擠事件在發送事務處理的測量的等待時間超過預定閾值時出現。
14.一種在代理者中的用於外部事務處理的多模式管理方法，它包括對多個核心讀取請求的數據進行排隊，對於各個核心讀取請求，存儲與相應的所述核心讀取請求有關的盲預取事務處理的數據，對與核心讀取請求的模式有關的預取請求的數據進行排隊，在第一模式下，當事務處理擁擠事件出現時，禁止所述盲預取事務處理，在第二模式下，當事務處理擁擠事件出現時，禁止所述預取請求。
15.如權利要求14所述的管理方法，其特徵在於所述事務處理擁擠事件在排隊的請求的數量超過預定閾值時出現。
16.如權利要求14所述的管理方法，其特徵在於所述事務處理擁擠事件在存儲所述排隊的請求的隊列變滿時出現。
17.如權利要求14所述的管理方法，其特徵在於所述事務處理擁擠事件在發送事務處理的測量的等待時間超過預定閾值時出現。
18.一種事務處理隊列，它包括控制器，多個隊列寄存器，每一個都具有地址欄位和與一對有關所述地址的事務處理有關的狀態欄位，其中，所述控制器響應擁擠事件而修改寄存器中所述狀態欄位之一，以使相應的所述事務處理無效。
19.如權利要求18所述的事務處理隊列，其特徵在於所述事務處理隊列存儲核心讀取請求、盲預取請求和模式預取請求，以及所述無效的事務處理是盲預取請求。
20.如權利要求19所述的事務處理隊列，其特徵在於當沒有有效盲預取請求時，所述控制器使模式預取請求無效。
21.代理者的一種總線排序單元，它包括仲裁器，內部高速緩存，它被耦合到所述仲裁器，事務處理隊列，它被耦合到所述仲裁器，並存儲要由所述代理者執行的外部事務處理、從核心讀取請求組選擇的事務處理、盲預取請求和模式預取請求的數據，以及外部總線控制器，它被耦合到所述事務處理隊列，其中所述事務處理隊列響應所述總線排序單元中的擁擠事件而使選擇的事務處理無效。
22.如權利要求21所述的總線排序單元，其特徵在於所述選擇的事務處理是盲預取請求。
23.如權利要求21所述的總線排序單元，其特徵在於當所述事務處理隊列中沒有盲預取請求時，所述選擇的事務處理是模式預取請求。
24.一種用於外部事務處理的擁擠管理方法，所述外部事務處理成對地存儲在所述事務處理隊列中，並從核心讀取請求-盲預取請求對和模式預取請求對的集合中獲得，所述方法包括在事務處理隊列接收新請求，確定所述事務處理隊列是否具有空間存儲所述新請求，如果沒有，則從所述事務處理隊列中刪除一對模式預取請求，以及在所述事務處理隊列中存儲所述新請求。
25.如權利要求24所述的擁擠管理方法，其特徵在於還包括使盲預取請求無效。
26.如權利要求23所述的擁擠管理方法，其特徵在於還包括在所述對中的第二模式預取請求已經被發送時使第一模式預取請求無效。
全文摘要
一種多模式事務處理隊列可以按照預設優先級方案操作。當檢測到擁擠事件時，事務處理隊列可以採用第二優先級方案。
文檔編號G06F13/362GK1503947SQ00817791
公開日2004年6月9日 申請日期2000年11月28日 優先權日1999年12月28日
發明者D·L·希爾, D·T·巴錢德, C·B·普魯德維, D·T·馬爾, D L 希爾, 巴錢德, 普魯德維, 馬爾 申請人:英特爾公司