在環型緩衝區中確定順序優先級的製作方法
2023-07-15 02:57:11 1
專利名稱：在環型緩衝區中確定順序優先級的製作方法
技術領域：
本發明涉及含有項目序列的環型緩衝區，更具體地說，涉及在所述環型緩衝區中滿足給定判據的項目之間順序優先級的確定。
當實現先進先出(FIFO)的緩衝區時，採用環型緩衝區，其中儲存項目序列。新項目從項目序列頭部加入，老項目從序列的尾部取出。通過加入新項目和取出老項目，所述環型緩衝區中的有效窗口就開始移動，它像蠕蟲一樣繞著環型緩衝區爬行，時而收縮，時而伸展。
無論何時，只要所述項目序列伸展到緩衝區最後一個項目位置以外，就出現環繞，這意味著所述序列最新的項目裝入所述緩衝區的第一個項目的位置。
當所述項目被安排入項目序列時，在這些項目之間存在一種次序。因為，例如，需要選擇滿足某個條件的最老的或最新的項目，所以就會出現這種次序變得重要的情況。例如，不同的項目可能都滿足給定的條件，這時就需要在它們的順序優先級上進行比較。
這個問題的一種解決辦法是總在項目序列的尾部和項目序列頭部之間留出一段空隙，並使滿足所述判據的指令阻塞較新的指令。
這種解決辦法的一個缺點是浪費緩衝區空間，因為緩衝器的項目得不到充分利用。
本發明的一個目的是提供一種在從所述序列的第一個項目排列到所述序列的最後一個項目存在真實的項目位置的連續序列的環繞式存儲器中，確定滿足給定的條件的項目的順序優先級的方法，並提供能避免現有解決辦法的缺點的相應的環繞式緩衝區。
本發明的目的用根據本發明的環繞式緩衝區和根據本發明的在環繞式緩衝區中確定項目順序優先級的方法解決。
根據本發明的環繞式緩衝區包括n個真實的項目位置，用來保存項目；第一組項目位置，它包括從所述序列的第一個項目到所述序列的最後一個項目的真實項目位置的連續序列；第二組項目位置，它包括所有不包括在所述第一組項目位置內的所有項目位置；所述第一組項目的預定項目的子集。
首先，向環繞式緩衝區未被佔用的部分至少提供額外的虛擬項目位置。
第二步，通過禁止從所述預定的項目子集的每一個所述預定項目開始包括所述虛擬項目位置的至少(n-1)個相鄰項目位置，來確定預定項目子集的在順序上最新的項目或在順序上最老的項目。
根據本發明的在環繞式緩衝區中確定項目順序優先級的方法，所述環繞式緩衝區包括n個真實的項目位置，用來保存項目；第一組項目位置，它包括從所述序列的第一個項目到所述序列的最後一個項目的真實項目位置的連續序列；第二組項目位置，它包括所有不包括在所述第一組項目位置內的所述真實項目位置；第一組項目位置的預定項目的子集；所述方法包括以下步驟在第二組項目位置中提供至少n個虛擬的項目位置；通過抑制從所述預定項目子集的每一個預定項目開始包括虛擬項目位置的至少(n-1)個相鄰的項目位置，從所述預定項目的子集中確定順序上最新的項目或者順序上最老的項目。
通過加入虛擬項目位置，可以加寬項目序列頭部和項目序列尾部之間的間隙，而不留下一大部分未佔用的環型緩衝區。使用一種實現起來成本低的容易的阻塞機制來阻塞被選中的不具有順序優先級的項目。」倖存者」便是具有順序優先級的項目。
所述預定項目的子集可以包含滿足任何給定判據的項目。這樣，所述選擇具有順序優先級的項目的方法，就可以應用於任何選擇判據。
圖1表示環型環繞式緩衝區的兩種不同狀態，這樣每一種狀態都可以用各自的入指針和出指針的位置來表徵。
圖2A表示將用作實施例的環型緩衝區的非環繞狀態。
圖2B表示為了使位串尺寸加大一倍可以如何展開初始有效位串。
圖3給出完成展開後有效位串的圖形表示。
圖4描述擴展初始位串用的可能的電路。
圖5A表示用作第二實施例的環型緩衝區的環繞狀態。
圖5B表示如何通過展開邏輯使初始位串尺寸加大一倍。
圖6給出處於展開狀態的有效位串的圖形表示。
圖7表示如何實現用來選擇具有順序優先級的項目的優先級濾波器。
圖8表示為了阻塞所有優先級比自己低的匹配線，每一條匹配線如何激勵對應的禁止線。
圖9描繪為了提供幾個具有順序優先級的匹配項目而將幾個優先級網絡級聯的方法。
圖1表示環型緩衝區的兩個狀態，」空」態和」滿」態。環型緩衝區(100)包括一組項目位置(101)，它可以含有項目(102)或不含有項目(101)。當具有順序次序的項目寫入所述環型緩衝區時，當裝配所述項目時，必需注意這個次序。一般設置兩個指針，進指針(103)和出指針(104)，它們使環形緩衝區作為先進先出(FIFO)緩衝區而運行成為可能。進指針指向環型緩衝區中與緩衝區最近被佔用的項目相鄰接的第一個空閒的項目位置(107)。這樣，進指針定義了已儲存的項目序列的頭部。無論何時，只要新的項目準備寫入緩衝區，它就被放在進指針所指的項目位置上。然後使進指針加一，以便再次指向下一個可用的項目位置。這樣，進指針便確定了已經存入環型緩衝區的項目序列的頭部。
反之，項目序列的尾部由出指針確定，後者指向第一個被佔用的項目位置，這是所述項目位置序列中最老的項目位置。無論何時，只要選擇先進先出(FIFO)項目，並使之離開先進先出(FIFO)，就選擇出指針(106)所確定的項目，因為就順序而言，它是最老的項目。接著，出指針加一，於是一個新的未被佔用的項目位置又變成可以使用了。
在環型緩衝區空的情況下，進指針(103)和出指針(104)都指向同一個項目位置。在環型緩衝區滿的情況下，這意味著有多少可以填入的項目位置就已經寫入了多少個項目，仍舊存在一個由進指針(105)指著的未被佔用的項目位置(107)。出指針(106)指向與所述空項目位置(107)鄰接的項目位置。這樣，只要看看進指針和出指針各自的位置，就可以區分空態和滿態。
通過向項目序列頭部加入新的項目，以及從項目序列尾部取出老項目，項目序列就開始移動。可以把它想像成一條可以向前爬行的蠕蟲，它時而伸展，時而收縮。
下面將用圖2A給出的例子表示如何可以把多個虛擬項目位置加入環型環繞式緩衝區真實項目位置。已佔用項目序列從項目位置0伸向項目位置52。因此，在這種情況下，構成有效窗口的所述項目序列在環型緩衝區中是不環繞的，已佔用的項目序列不同時佔用項目位置63和0。有效窗口的範圍由出指針(201)的位置確定，後者指出，項目位置O保有所述項目序列最不新的項目(202)，它通常是最老的項目。項目位置52保有最近加入的項目(204)，它由出指針(203)指出，後者指向與之鄰近的作為第一個未被佔用的項目位置的可用項目位置53(205)。
根據環型緩衝區64個項目位置中給定的一個是否被佔用，在由與環型緩衝區64個項目對應的64個位組成的」有效位串」(206)中設置」有效位」。這樣，在所述」有效位串」(206)中1的序列代表在所述環型緩衝區中從出指針(201)到進指針(203)之前的項目位置範圍的項目序列。對於環型緩衝區每一個未被佔用的項目位置，在有效窗口位串(206)對應的位置設置「0」。在我們這個實施例中，0從位串位置53伸展到位串位置63。
圖2B給出的電路的任務是向有效窗口位串206的64位加上與虛擬項目位置對應的64個位。所述環型緩衝器只包括64個真實的項目位置。因此，在環型緩衝區中並不存在與所述64個虛擬項目位置對應的項目位置。展開有效窗口串的任務是通過包括所述有效窗口串中每位一個展開電路(208，209)的展開邏輯(207)來完成的。因此，就需要平行地存在64個所述的展開電路(208，209)。
有效窗口串的每一位，例如位i(210)設置為它對應的展開電路(208)的輸入。每一個展開電路存在兩個輸出。展開電路i的第一個輸出(212)寫到包括128個項目的擴充的位串214的第i位。所述展開電路的第二個輸出(213)寫到擴充的位串214的第i+64位，後者同時代表真實項目位置的和額外的虛擬項目位置的狀態。在展開電路208的輸入i(210)等於1的情況下，1出現在輸出212或213中的一個上。所述展開電路的另一個環繞輸入211確定擴充的位串214的位i還是位i+64將含有」1」。在無環繞發生的情況下輸入211失效。這是在圖2A所描繪的實施例的情況，因此，輸出i將被設置成」1」(212)，而輸出i+64將被設置成」0」(213)。
輸入k(215)與環型緩衝區未被佔用的項目位置對應，因而等於」0」。在這種情況下，對應的展開電路209的兩個輸出都等於」0」。」0」既寫入擴充的位串214的位置k(216)，又寫入位置k+64(217)。
因為在這個實施例中，並沒有環繞，所以有效窗口串206中所含的所有」1」都向前送到擴充的位串214的下半部。
所得有效位串214的結構示於圖3中的圖形表示。由於初始有效窗口串的所有」1」都向前送到擴展窗口串(無環繞！)的同一位置。擴展窗口串214的位0-52(300)都填成」1」。擴充的位串214的剩餘部分含有零。位53-63中所含的零與初始有效窗口串206的位位置52-63的零對應。擴充的位串214的位64-127也填成零，因為所有展開電路的所有輸出i+64都已經把零寫到擴充的位串的上半部分。這之所以發生，因為在本實施例中還沒有出現任何環繞。
在圖4中給出了所述展開電路(208，209)中的一個的可能的實現(400)。有效窗口串的位i作為所述展開電路的輸入(401)向前送。環繞輸入(402)確定所述輸入位向前送給哪一個輸出(405，407)。首先，確定是否存在環繞。在項目位置0和項目位置63都保有有效項目的情況下，環繞存在。在有環繞存在的情況下，在第二步確定所考慮的位的項目號i是否小於出指針所指向的項目號。
在兩個條件都滿足的情況下，環繞輸入402被設置成」高」，與輸出407對應的場效應管(FET)406被激活，而通過反相器403接收所述環繞信號402的FET 404被置成失效。這意味著在環繞的情況下，出現」0」(405)，後者寫到擴充的位串214的位i。輸入401向前送到輸出407，後者寫到所述擴充的位串的位i+64。
在無環繞的情況下，環繞輸入402是」低」，FET 406失效，而FET404被激活。這意味著輸入401向前送到輸出405，後者寫到所述擴充的位串214的第一半，而零出現在輸出407。
看看環繞存在的緩衝區狀態，這種電路的含義就變得更清楚了。在圖5A中描繪出這樣一種狀態。在那裡，正如標出有效窗口串尾部的出指針501所指出的，可以發現有效項目序列最老的項目(502)是在項目位置63。當跟蹤從所述尾部開始的已佔用的項目序列時，發生從項目位置63到項目位置0的環繞。因為項目位置63和項目位置0都含有有效項目，所以滿足圖4中的第一個環繞信號402的條件。有效項目序列向上伸展到項目位置61(504)。項目位置61的項目確定了有效順序的頭部。這是由指向下一個可用的項目位置(505)的進指針503指出的。所述項目位置是唯一未被佔用的項目位置。
在圖5B中解釋有效窗口串506向包括128個項目的擴充的位串514的平移。初始有效窗口串包括從位0到位61的」1」的序列，在位62上的」0」和位63上的」1」。顯然，當環繞發生時，有效順序被分成兩部分從項目位置0到進指針的前一個項目位置的前部和從出指針所規定的項目位置直至項目位置63的後部。
圖4條件框給出的第二個條件要求，所考慮的項目位置小於出指針所指的項目號。對於從0到61的有效序列的前部，這個條件是滿足的。但是，對於屬於有效項目序列的後部的所有項目，這個條件都是不滿足的。在我們的例子中，後部只包括一個項目位置，項目位置63，它並不小於出指針所指的項目位置。這樣，在環繞的情況下，對於屬於所述已佔用的項目序列的前部的所有項目，環繞信號是有效的，而對於所有屬於所述有效序列的後部的項目位置，所述環繞信號是無效的。
位i(510)屬於有效窗口串506的前部。因此，環繞信號511有效。所以，與位i對應的展開電路508把輸入510的」1」向前送到i+64的輸出513，於是，把」1」寫入擴充的位串514的位置i+64。相應地，」0」出現在所述展開電路508的輸出512上，因而」0」寫入所述擴充的位串的位置i。相應地，有效窗口串位置61上所含的」1」向前送到輸出520，並寫到擴充的位串514的位置125。因此位置125含有」1」(521)。相應地，」0」寫入位串514的位置61。這樣，位串506的位置62含有0，而所述的0也寫入擴充的位串514的位置62和位置126。
對於項目位置63所含的」1」，情況就不同了。在這裡，圖4條件框中的第二個條件是不滿足的，因為項目位置63不小於出指針501所指的位置。因此，有效窗口串506的位置63所含的」1」向前送到輸出515，並寫入擴充的位串514的位置63(516)。與初始位串的項目位置63對應的第二個輸出(517)無效，因為不滿足所述條件。所以，一個」0」寫入所述擴充的位串的位置126。項目位置126和127總含有零(522)。
在圖6中給出擴充的位串所得的結構。初始有效窗口串的後部只在位置63包含項目(601)。所述初始有效窗口串的前部包括從項目位置0(602)直至項目位置61(603)的項目。但是，所述有效窗口串(604)的所述前部所含的」1」並不同樣地複製到擴充的位串，因為圖4條件框的兩個條件都滿足。相反，項目位置0(602)所含的」1」映射(605)到項目位置64的」1」(606)。相應地，項目位置61所含的」1」(603)寫到(607)擴充的位串514的項目位置125(608)。這樣，初始有效窗口串的整段604複製到擴充的位串上半部分的段609。有效窗口串604前面的項目，包含在擴充的位串的下半部分，用零填充。這樣，在已佔用的項目序列的後部保持不變(601)的同時，所述有效項目序列的整個前部完成轉移到擴充的位串的上半部。
通過這樣做，在項目位置63和項目位置0之間加入64個虛擬項目，就重新裝配了已經撕成兩部分的有效項目序列，以便形成從項目位置63到項目位置125的連續序列。在最新的項目(608)和最老的項目(601)之間的間隙，為了形成所述擴充的位串已經加入64個虛擬項目，全都含有零。所述間隙開始時只在項目位置62包括未被佔用的位置(505)，而現在所述間隙含有65個未被佔用的位置，但是，所述未被佔用的位置中有64個是虛擬項目位置，它們並不對應於任何真實的緩衝區項目。這樣，所述間隙就虛擬地增加了。
在圖7中，說明所述擴充的位串如何向前送到順序優先網絡。選用與圖2A描繪的相同的緩衝區狀態作為例子。環型緩衝區含有從項目位置0到項目位置52的項目位置序列，沒有環繞。這由含有64個項目的有效窗口串206中相應的1和0的序列代表。所述64個項目向前送到擴展邏輯(207)，後者使用有效窗口串206的各位和環繞信息(211)作為輸入，並產生128個位寬的擴充的位串作為輸出。所述擴充的位串是按照圖2B所給出的方法產生的，因此，所得的擴充的位串214與圖3給出的結構相同。這個擴充的位串向前送到發送選擇單元700。在這裡，對所述擴充的位串的每一個有效位位置都應用判據。只有也滿足所述判據的擴充的位串的有效位才向前送到順序優先級網絡。
現用一個例子更加清楚地說明可以如何確定所述判據。在無順序的處理系統中，指令在它們被分送到它們各自的執行單元之前，首先被送到指令窗口緩衝區。在所述指令窗口緩衝區中，每一條指令被分配給一個項目，後者保存所述指令本身，源和目的操作數識別符以及若干狀態位。每一個項目保留在指令窗口緩衝區中直至它所有源操作數都已經計算出來並已可用為止。一旦它的所有的源操作數都已可用，就可以把指令發送到執行單元中的一個。所述指令窗口緩衝區通常都做成環型緩衝區。這意味著來自指令串的新指令寫到窗口緩衝區中的指令隊列的第一個空閒項目上。所述第一個空閒項目就是進指針所指向的項目。可以環繞的隊列的尾部由出指針指示。這樣所述出指針便指向保持隊列最老指令的項目。
在每一個周期中，都需要從指令窗口緩衝區選擇」準備好發送」的指令。
按照處理能力和可用執行單元的數目，可以向執行單元發送數目有限的指令。發送指令的前提是指令所有的源操作數都可用。這通常由」源有效」位指出。在所述指令的源操作數的所有源有效位都置1的情況下，所述指令就」準備好發送」了。在這種情況下，上述判據就是所有源操作數都可用。
但是，確定了在所述有效指令隊列中哪些指令滿足發送判據之後，仍可能還有許多」準備好發送」的候選指令，不能在一個周期中把它們都發送出去。所以，在這些候選指令中，還需要按照它們的優先級進行選擇。」準備好發送」的候選指令中最老的指令要首先發送。因此，優先邏輯需要利用所有可用的源確定所述指令中具有最高的優先級的指令。
現在讓我們回到圖7，看一下發送選擇邏輯(700)。展開邏輯(207)已發送一種有效位串，其中每一個有效指令項目都保持」1」。對這種擴充的位串應用是否全部指令源操作數都可用(701)的判據。由於項目i和項目i+64都對應於同一個物理項目，所以」所有源操作數均可用」信號(702)同時加到所述擴充的位串的位置i和i+64。這是通過把」所有源操作數均可用」信號(702)向前送到每個所述擴充的位串位位置的「與」門(703，704)來實現的。通過把指令窗口緩衝區隊列的每個有效指令項目含有」1」的擴充的位串饋送到一排128個「與」門(705)，只有那些滿足」所有源操作數均可用」(701)判據的有效位才被保留下來。這些是發送的可能的候選者，在它們之中，需要確定優先級。所述「與」門(703，704，…)的128個輸出被稱為」匹配線」(706)。所有128條匹配線都向前送到優先級濾波器。
優先級濾波器的任務是確定所有有效匹配線(706)中最老的一條。
對於每一條匹配線ML(0)到ML(127)，都存在對應的禁止線。在圖7給出的優先級濾波器電路背後的想法是，每一條有效的匹配線通過激活它們的禁止線應該能夠阻塞63條隨後的代表較新項目的匹配線。
作為一個實施例，讓我們考慮匹配線ML(2)(707)。當所述匹配線有效時，「與」門711的兩個輸入中的一個為高。禁止線708與ML(2)對應。所述禁止線708初始為」高」，除非前面63條匹配線中的一條將它拉」低」，否則它仍舊為」高」。在所述禁止線708不被它前面的匹配線拉」低」的情況下，「與」門711的兩個輸入都有效，因此該「與」門的輸出M(2)有效。
因為ML(2)(707)有效，所以所有的FET 709都被激活，後者將與ML(3)，ML(4)，…ML(65)對應的禁止線拉」低」。因為禁止線710被拉」低」，所以M(3)至M(65)都無效。
M(0)至M(127)代表優先級濾波器的最後所得的輸出。準確地說這些信號線中，只有一個將是有效的，而這條信號線指出哪一個緩衝區項目既滿足判據又具有順序優先級。在我們的情況下，所述優先級濾波器輸出將指出所有源操作數均可用的最老的緩衝區項目。
為了使這些輸出信號與緩衝區項目發生關係，需要去除由展開邏輯207加入的虛擬項目。這是通過把輸出M(i)和輸出M(i+64)相「或」(717)而實現的。「或」門(717)的輸出718將確定緩衝區項目i是不是所有源操作數均可用的最老的緩衝區項目。
圖8表示一條有效匹配線如何能夠阻塞隨後的63條匹配線。有效項目序列從出指針所指的最老的項目(800)排列到進指針之前的最新項目。因為沒有環繞，所以展開邏輯(207)剛好加上從項目64排列到項目127的64個虛擬項目。讓我們假定，4條匹配線ML(5)(803)，ML(20)(804)，ML(39)(805)和ML(46)(806)滿足給定的判據。在這些候選項目中，需要由優先級邏輯確定最老的一個。每一條有效匹配線都通過激活所述63條隨後的匹配線來阻塞隨後的63條匹配線。這樣，匹配線(5)(803)阻塞所有匹配線，從6至68(806)。被禁止的匹配線的範圍總是用半園表示。匹配線804阻塞匹配線的範圍808，匹配線805阻塞範圍809，而匹配線806阻塞範圍810。唯一不被其他匹配線阻塞的匹配線是ML(5)。ML(5)事實上是最老的匹配線。因此，ML(5)將是有效的，它將與ML(68)進行「或」操作，後者不是有效的，而所得結果將指出項目5是滿足所述判據的最老的項目。
圖8還指出，為什麼需要把虛擬項目加到有效窗口串上。否則，隊列尾部和頭部之間的間隙就不足夠大，而老的匹配線就可能被較新的匹配線阻塞。在給出的解決方案中避免了這個問題。
當需要確定最新的項目時，圖7的電路也可以應用。在這種情況下，匹配線阻塞需要發生在相反的方向。有效的匹配線會需要阻塞前面63個項目。
在圖9中給出了表示幾個優先級濾波器的級聯電路。為了不僅確定滿足條件的最老的或最新的項目，而且確定若干個滿足條件的最老的或最新的項目，需要這樣的級聯電路。看看將是有效匹配線的ML(2)(901)，所述原理就清楚了。假如這條匹配線不被其他任何一條匹配線阻塞，則它對應的禁止線(900)將為」高」。在這種情況下，ML(2)是最老的匹配線，為了指示這一點，「與」門902的輸出有效。因為ML(2)已經被優先級濾波器1選擇為最老的有效匹配線，所以它不需要向前送到優先級濾波器2。禁止線900向前送到「與」門903的反相輸入。所以，只要禁止線處於」高」電平，匹配線904就無效。
若(2)已經被任何其他較老的匹配線阻塞，情況就不一樣了。在這種情況下，它對應的禁止線900將被置成」低」，「與」門902的輸出無效。這意味著ML(2)不是滿足所述判據的最老的項目。但是，仍舊可能是滿足所述判據的第二最老的項目。禁止線900連接到「與」門903的反相輸入，而有效匹配線901本身連接到非反相輸入。所以，構成所述匹配線中與優先級濾波器2相關的一條匹配線的輸出904是有效的，而ML(2)將被在下一個連接步驟考慮。
通過在所述優先級濾波器級聯電路上加入其他優先級濾波器，就可以同時選擇若干個具有順序優先級的項目。在一個周期中從指令緩衝區向若干個執行單元發送幾條指令，是這樣的級聯循環電路有用的一個例子。但是，本發明絕不限於指令窗口緩衝區。
權利要求
1.一種環繞式緩衝區，它包括n個真實的項目位置，用來保存項目，第一組項目位置，它包括從所述序列的第一個項目到所述序列的最後一個項目的真實項目位置的連續序列，第二組項目位置，它包括所有不包括在所述第一組項目位置內的所述項目位置，所述第一組項目位置的預定項目的子集，其特徵在於用來在所述第二組項目位置中提供至少n個額外虛擬項目位置的裝置，用來確定所述預定項目的子集中順序上最新的項目或者順序上最老的項目的裝置，從而，所述裝置從所述預定項目的子集的每一個所述預定項目開始，至少禁止包括所述虛擬項目位置的(n-1)個相鄰的項目位置。
2.按照權利要求1的環繞式緩衝區，其特徵在於所述第一組項目位置的所述預定項目的子集包含所述第一組項目位置中滿足預定判據的所有所述項目。
3.按照前面的權利要求中任何一個的環繞式緩衝區，其特徵在於用來在所述第二組項目位置中提供至少n個額外的虛擬項目位置的所述裝置把至少n個虛擬項目位置加到所述環繞式緩衝區的後面，假如所述第一組項目位置的環繞存在，則把所述第一組項目位置分成兩部分，前部和後部，所述提供至少n個虛擬項目位置的裝置把所述兩部分中的一部分複製到所述環繞式緩衝區的所述虛擬項目位置上。
4.按照前面的權利要求中任何一個的環繞式緩衝區，其特徵在於所述用來確定所述預定項目的子集中順序上最新的項目或者順序上最老的項目的裝置包括用來把所述真實的項目位置與虛擬項目位置複合的裝置。
5.按照前面的權利要求中任何一個的環繞式緩衝區，其特徵在於所述環繞式緩衝區是指令窗口緩衝區，從而所述第一組項目位置中的每一個項目保持指令。
6.按照權利要求5的環繞式緩衝區，其特徵在於所述第一組項目位置的所述預定項目的子集包含所述第一組項目位置的所述項目中這樣一些項目保持在所述項目中的指令的所有源操作數均是可用的。
7.按照前面的權利要求中任何一個的環繞式緩衝區，其特徵在於所述用來確定所述預定項目的子集中順序上最新的項目或者順序上最老的項目的裝置還包括每一個項目位置一條匹配線，從而包括所述虛擬項目位置，以及從而，假如每一條匹配線對應的項目位置保持屬於所述第一組項目位置的所述預定項目的子集的項目，則所述匹配線有效。
8.按照權利要求7的環繞式緩衝區，其特徵在於所述用來確定所述預定項目的子集中順序上最新的項目或者順序上最老的項目的裝置還包括每一條匹配線一條禁止線，從而，所述禁止線禁止與至少(n-1)個相鄰的項目位置對應的所述匹配線。
9.一種用來在環繞式緩衝區中確定項目順序優先級的方法，所述環繞式緩衝區包括n個真實的項目位置，用來保存項目，第一組項目位置，它包括從所述序列的第一個項目到所述序列的最後一個項目的真實項目位置的連續序列，第二組項目位置，它包括所有不包括在所述第一組項目位置內的所述真實項目位置，所述第一組項目位置的預定項目的子集，其特徵在於所述方法包括以下步驟在所述第二組項目位置中提供至少n個虛擬的項目位置，通過禁止從所述預定項目子集的每一個所述預定項目開始的包括所述虛擬項目位置的至少(n-1)個相鄰的項目位置，確定所述預定項目的子集的順序上最新的項目或者順序上最老的項目。
10.按照權利要求9的方法，其特徵在於所述第一組項目位置的所述預定項目的子集包含所述第一組項目位置中滿足預定判據的所有所述項目。
11.按照權利要求9或10的方法，其特徵在於所述環繞式緩衝區是指令窗口緩衝區，所述第一組項目位置中的每一個項目都保持指令。
12.按照權利要求11的方法，其特徵在於所述第一組項目位置的所述預定項目的子集包含所述第一組項目位置的所述項目中的這樣一些項目保持在所述項目中的指令的所有源操作數均是可用的。
13.按照權利要求9-12中任何一個的方法，其特徵在於用來在所述第二組項目位置中提供至少n個額外的虛擬項目位置的所述步驟包括以下步驟把至少n個虛擬項目位置附加到所述環繞式緩衝區上，假如所述第一組項目位置存在環繞，則把所述第一組項目位置分成兩部分，前部和後部，把所述兩部分中的一部分複製到所述緩衝區的所述虛擬項目位置。
14.按照權利要求9-13中任何一個的方法，其特徵在於用來確定所述預定項目的子集中順序上最新的項目或者順序上最老的項目的所述步驟包括把所述真實的項目位置與所述虛擬項目位置複合的步驟。
全文摘要
本發明涉及含有項目序列的環型緩衝區,在既滿足給定條件又含於所述序列中的項目之間確定順序優先級。在所述環型序列中所述項目序列可以環繞。按照本發明,首先,把數量上至少等於緩衝區中真實項目位置的虛擬項目位置加到所述緩衝區未被佔用部分上。第二步,每一個滿足給定條件的項目阻塞若干個相鄰的項目,包括所述虛擬項目。只剩下一個仍舊不被阻塞的並滿足給定條件的項目。這個項目就是具有順序優先權的項目。
文檔編號G06F5/06GK1193141SQ9810442
公開日1998年9月16日 申請日期1998年2月9日 優先權日1997年3月10日
發明者W·梭爾, D·文德爾, F-C·韋尼克 申請人:國際商業機器公司