用於對互連訪問進行仲裁的系統和方法

2023-06-10 23:51:21 1

用於對互連訪問進行仲裁的系統和方法
【專利摘要】本發明的多個方面涉及對在多個埠之間的互連訪問進行仲裁。例如，輸入埠接收對所標識的目的埠的訪問的請求並在一個或多個FIFO內對這些請求進行緩衝。與一個或多個對應的FIFO相關聯的挑選器開始包括用於每個輸出埠的位置的空仲裁包並且比如基於優先化方案對該包內的一個或多個位置進行填充。以環形將每個包傳遞至另一個挑選器，該挑選器執行不與該包內的之前填充的位置相衝突的填充。每個挑選器都有機會將請求放置在這些包中的每個包內。將仲裁結果分發至與對應的輸出埠相關聯的重排序緩衝區並且將其用於對互連進行調度。因此，每個仲裁周期為互連產生有待在後續數據傳送步驟中使用的控制信息集。
【專利說明】用於對互連訪問進行仲裁的系統和方法

【技術領域】
:
[0001]以下涉及用於對數據互連的使用進行仲裁，並在一個具體方面，涉及在分布式計算中對內存的訪問進行仲裁。

【背景技術】
:
[0002]數據交換機可以具有多個輸入埠和多個輸出埠。交換機用於在輸入埠接收輸入和確定有待將每個輸入發送到其上的對應輸出埠。在一些情況下，每個輸入埠可以接收可能需要被發送出輸出埠中的任一埠的輸入。可以在輸入埠處異步地接收輸入，從而使得可能存在多個可能需要被切換至同一輸出埠的多個輸入；系統局限性阻止所有這些輸入被同時發送到同一輸出埠，而引起衝突。進行這些衝突輸入之間的仲裁以便確定衝突數據傳送將被服務的相對排序。


【發明內容】

[0003]在一個方面中，一種用於對互連訪問進行仲裁的方法包括隨時間在η個輸入埠中的任何輸入埠處接收一個或多個數據傳送請求，每個請求指定來自m個輸出埠中的對應的輸出埠，將通過該輸出埠為該請求進行服務。可以緩衝這些請求中的每個請求。該方法將對應的空仲裁包分配給已分配給每個輸入埠的對應的挑選器。每個仲裁包具有用於這m個輸入埠中的每個輸出埠的位置。在每個挑選器處，選擇至少一個緩衝請求並將其放在用於每個選定的請求被發到其上的輸出埠的位置中的那個挑選器處的仲裁包內。在挑選器之間傳遞仲裁包，直到每個挑選器已經接收到每個仲裁包，並且同時每個挑選器具有每個仲裁包，挑選器試圖將至少一個請求放在該仲裁包內的任何剩餘位置中。已完成的仲裁包用於使用互連來對這些請求的履行進行調度。
[0004]另一方面涉及一種用於對η個輸入埠 m個輸出埠互連訪問的仲裁器，該仲裁器具有可操作用於存儲在這些η個輸入埠中的任何埠處接收的數據元素的緩衝器。該仲裁器還具有多個挑選器。每個挑選器被耦聯成從另一個挑選器接收仲裁包。該仲裁包包括用於這m個輸出埠中的每個埠的位置。每個挑選器試圖對所接收的仲裁包內的至少一個空位置進行填充，其中，這些挑選器中的任何挑選器可以對所接收的仲裁包內的任何空位置進行填充，並且將該仲裁包傳遞至另一個挑選器。該多個挑選器並行地完成η個仲裁包。在一種方法中，這m個輸出埠中的每個埠具有對應的重排序緩衝區，該重排序緩衝區可操作用於接收該輸出埠的η個仲裁包內的條目並強制實施源自同一輸入埠的條目的先進先出順序。
[0005]另一個方面涉及一種帶有具有一組埠的互連和控制器的計算系統，並且該控制器可操作用於將該互連配置成使得能夠在這些埠的指定組合之間發生數據事務。該控制器可操作用於接收互連配置數據集合序列和根據這些互連配置數據集合配置用於數據傳送周期序列的互連。當將使用連配置數據集合時，每個互連配置數據集合具有對在數據傳送周期期間被耦聯用於數據傳送的埠的組合的指示。該仲裁器具有多個輸入埠，在這些輸入埠處接收在該互連上進行數據事務的請求。該仲裁器還具有多個挑選器。每個挑選器耦聯到對應的輸入埠上，並且與前一個挑選器和後一個挑選器進行通信。每個挑選器用於在仲裁周期期間獲得仲裁包。每個仲裁包包括預先確定數量的有待用互連配置數據填入的槽。每個挑選器用用於在輸入埠處接收到的一個或多個請求的互連配置數據填入仲裁包內的一個或多個槽。該填入涉及對已經用互連配置數據填充的任何槽進行標識並且對需要與所填入的槽所指定的互連埠的組合相衝突的互連埠組合的任何請求不予考慮。每個挑選器將仲裁包傳送至後面的挑選器，直到每個挑選器已經接收到這些仲裁包中的每個仲裁包至少一次。因此，每個挑選器從前一個挑選器接收仲裁包，並用所接收到的仲裁包重複進行該填入。

【專利附圖】

【附圖說明】
[0006]圖1描繪了一種示例系統環境，其中，仲裁器可以操作用於對互連元件進行調度；
[0007]圖2描繪了示例仲裁器的各個方面；
[0008]圖3描繪了示例輸入埠的各個方面；
[0009]圖4描繪了用於互連元件的使用的仲裁的示例；
[0010]圖5描繪了圖4的示例中的仲裁的每輸出隊列排序；
[0011]圖6描繪了輸出隊列的重排序條目，以便通過輸入埠保持數據傳送請求的相同的相對順序；
[0012]圖7描繪了將氣泡從輸出隊列中的首要位置中清除；
[0013]圖8描繪了示例仲裁過程的流程圖；
[0014]圖9描繪了另一種示例仲裁過程；
[0015]圖10和圖11描繪了與輸入埠的另一種示例實現方式相關的各個方面；
[0016]圖12描繪了可以與根據圖10和圖11的輸入埠一起使用的示例仲裁過程；以及
[0017]圖13和圖14描繪了從圖10和圖11中描繪的輸入埠緩衝區內可用的互連請求之間選擇用於布置的互連請求的示例方法。

【具體實施方式】
[0018]圖1描繪了一個示例系統2，其中仲裁器5對選擇性地使不同的輸入埠 3與不同的輸出埠 4耦聯的互連6的訪問進行仲裁。在該示例中，在每個傳送周期中，互連元件6可以將任何單個輸入埠連接到任何單個輸出埠上。因此，如果兩個輸入埠需要同一個輸出埠，則會發生衝突，需要仲裁。
[0019]各種組件可以耦聯到輸入埠 3和輸出埠 4上，並且在示例系統2中，計算單元7和8、數據管理器9以及連結10耦聯到輸入埠 3上，並且內存Ila-1ld耦聯到輸出埠4上。數據管理器9展示了數據管理器可以設置多個內存從而使得計算單元可以使用數據管理器9安排在內存Ila-1ld中的數據執行計算的情形。連結10可以用來連接到另一個仲裁器/互連元件組上以便產生更大的互連。本公開內容的一些用法可以只具有耦聯到輸入3上的計算單元。在一些情形下，可以通過執行程序的計算單元或通過電路實現數據管理器9。通過一條或多條線路或一個或多個互連點實現所示的每個輸入和輸出埠。並且，輸入埠 3和輸出埠 4可以被實現為分離的控制和數據路徑，其中，控制主要被路由到仲裁器5，而數據路徑被路由到互連元件6。控制路徑本身傳送表示對一組指定埠的互連元件6的使用或預訂的請求的數據，而數據路徑用來傳輸跨該互連移動的數據。在一些示例中，單條組合數據路徑可以包含控制和數據元素兩者。
[0020]互連元件6可以包括用來接收指定信息以便設置不同內存請求的內存控制器。該內存控制器所需的信息由程序或由生成將互連元件6用於數據傳送的請求的電路所提供。不同的內存控制器可以使用不同的信息和支持不同的能力。因此，到達輸入埠的信息不同之處將在於這些不同的實現方式。
[0021]某些埠標記為輸入和其他埠標記為輸出是對數據流量通過互連6的方向的限制的一種不必要的指示。例如，可以根據數據傳送請求將數據從內存Ila-1ld傳輸到輸入埠 3中的任何埠，並且反之亦然。所以，仲裁是確定在每次數據傳送機會時哪些數據埠被耦聯用於數據傳送。以下提供了仲裁器5的操作的進一步的描述和示例。
[0022]圖2描繪了針對輸入埠 3的每個輸入埠而具有多條輸入線路的仲裁器5(具體標識了 14ab、15ab和16ab)。每條輸入線路14ab_16ab耦聯到對應的FIFO緩衝區20ab_22ab上。對應的挑選器30-32與用於這些輸入埠其中之一的輸入線路耦聯。例如，挑選器30耦聯到輸入線路14ab的FIF020ab上。數據路徑35耦聯到挑選器30-32上、與挑選器30-32互連，從而使得挑選器30-32被互連。例如，在一種方法中，挑選器30-32連接成環形，其中挑選器32連接到前一個挑選器和挑選器30上。
[0023]每個挑選器可操作用於從一個挑選器接收一個仲裁包並且向後續挑選器發送一個仲裁包。在一個示例中，挑選器30-32操作用於同步地將多個仲裁包從一個挑選器傳遞到另一個挑選器。每個挑選器可以包含存儲用於一個仲裁步驟的仲裁包的寄存器，其中數據路徑35連接不同挑選器的寄存器。當對寄存器進行計時時，每個挑選器的寄存器內的仲裁包被發送至下一個挑選器。
[0024]數據路徑35還可以包括選擇性地將仲裁包的部分傳送到每個部分所屬於的輸出緩衝區的互連。具體地，仲裁包可以包括與該仲裁包內展示的每個請求指定的傳送有關的數據，如用於讀取/寫入內存的特定源和/或目的地址。因此，在一個示例中，輸出緩衝區接收內存地址或指針，其指示數據將要被讀取或者數據將要被存儲的位置。
[0025]在另一個示例中，仲裁包包括用於每個輸出埠的單個比特。每個挑選器對其在每個仲裁包內預訂的每個輸出埠的比特進行設置(圖4的示例中有兩個)。當將每個請求放在包內時，該請求的細節被傳送至針對該請求涉及的輸出隊列而被填充的FIFO。因此，在本方法中，數據傳送的細節並沒有在仲裁包內進行展示，而是直接被傳送到輸出隊列的合適 FIFO。
[0026]數據路徑35還操作用於向輸出緩衝區50ab_53ab提供仲裁包的內容。在一種方法中，每個輸出埠 45-48與兩個輸出緩衝區相關聯。如以下將進一步解釋的，讀出一個輸出緩衝區，同時填充另一個輸出緩衝區。輸入和輸出埠的數量、每輸入埠的線路的數量以及為輸入埠服務的挑選器的數量在根據本公開內容的實現方式中可以變化。
[0027]圖2描繪了仲裁器5還可以包括如在數據路徑35中所示的側載入器37和溢出緩衝區38。在一些實現方式中，如圖4的仲裁示例將舉例說明的，挑選器30-32可能不能夠始終填充所有的仲裁包，從而不時引起空條目(氣泡)。在一種方法中，側載入器37可以檢測到仲裁包何時完成但仍然具有空位置，並且然後試圖用來自緩衝區38的條目填充該空位置。緩衝區38可以存儲較低優先級的數據流量請求，或在每個FIF020ab-22ab包括有限數量位置的情形下，緩衝區38可以從FIF020ab-22ab中任何FIFO中接收溢出。側載入器37的操作類似於挑選器，試圖對仲裁包內可以填充的位置進行標識，但不作為同級(as a peer)來參與仲裁周期。
[0028]圖2描繪了每個輸入埠包括兩條被單個挑選器服務的線路，其中挑選器可以在仲裁步驟中從每條線路中選擇一個條目。本示例展示了使有待在給定步驟中執行的工作量與在實現方式中所用的電路和內存量到達平衡的設計選擇。
[0029]圖3描繪了與一個輸入埠的一種安排19有關的進一步的細節，其中，多條輸入線路接收數據並將這種接收到的數據存儲在對應的輸入FIFO內，該輸入FIFO由挑選器服務。具體地，輸入線路14a-14b將數據分別存儲在FIF020a-20b中，挑選器30為這些FIFO服務。圖3還描繪了每個FIF020a-20b存儲表示需要使用互連元件6的事務的數據。需要相同組合的埠(或重疊埠)的事務需要仲裁。
[0030]圖4描繪了仲裁器5的所描繪的組件如何起作用的示例。圖4還用於展示圖8中所描繪的方法的特定示例。圖4的示例示出了一個示例,其中每個具有2條輸入線路的4個輸入埠針對八個輸出埠的任何埠的訪問進行仲裁(在圖4中，每個輸出埠被稱為存儲體，縮寫為「B」，如BO為存儲體O)。如以上介紹的，對應的挑選器為每個輸入埠的輸入線路服務。4個輸入埠之間的一個仲裁周期在4個步驟(T0-T4)中進行；每個步驟可以是處理時間的合適分配以便在該步驟中執行所需要的任務，並且不暗示與時間的絕對增量有關的任何具體要求。在本公開內容中，仲裁周期是指產生一組可以用於在多個後續數據傳送步驟中對互連進行控制的仲裁包。在圖4的具體示例中，當向每個挑選器提供四個仲裁包中的每個仲裁包用於有機會將條目放在該仲裁包內時，仲裁周期完成。每次將仲裁包從一個挑選器傳送至另一個挑選器可以被稱為一個『仲裁步驟』。
[0031]為了開始進行仲裁，在TO (圖8的202)，在每個挑選器處啟動對應的空仲裁包。在一個示例實現方式中，允許每個挑選器放置來自其相關聯的FIFO的多達2個請求，並且在一個具體示例中，放置來自每個FIFO的一個請求。在一種方法中，在輸入埠的FIFO之間，分配給一個FIFO第一優先級。可以在這些FIFO之間轉動此優先級，從而使得在後續仲裁周期中，優先級FIFO將變化。在一個示例中，從優先級的FIFO開始，每個挑選器始終試圖將該第一條目放置在每個可以被放置的FIFO內。因此，對於TO處的空仲裁包而言，保證每個挑選器能夠放置來自當前優先級隊列的其最高優先級條目，並且將也能夠放置來自其他FIFO中的條目(如果有可用的話)。在圖8中，這些布置決定操作共同被標識為204。圖4描繪了仲裁包為81-84。為了方便展示,每個仲裁包81-84被分割成8個位置,每個位置對應一個輸出存儲體，其中『N』表示仲裁包內的具體位置是空的，而『F』表示這種位置是滿的。圖4沒有暗示按具體順序陳列仲裁包的要求(例如，每個輸出存儲體在仲裁包具有一個預先確定的相對位置，因為可以包括存儲體標識符用來對已經填充的輸出存儲體進行標識)。在205，每個挑選器對在204標識的一個或多個請求進行放置。這種布置中所涉及的機構在不同的實現方式中可以變化，並且在此披露了兩個示例。
[0032]在圖4中，示出了每個輸入隊列的FIFO具有多個發往特定輸出存儲體的請求。(例如，埠 O的FIF00具有請求B4、B6、B4、B4、B0和B7。)圖4描繪了每個挑選器在當前挑選器的操作之後的狀態下在仲裁包正上方的每個時間增量中填充了哪些請求(在圖8中，204選擇和205放置)。例如，考慮TO處的仲裁包81，仲裁包81在到達時是空的。填充了 B4和B3 (其是埠 O的每個FIFO中的第一條目)。因此，示出了仲裁包81填充了第四和第五位置。類似地，針對BO和BI填充仲裁包82，從而使得在用於埠 I的挑選器的操作之後填充位置O和I。每個挑選器在提供到其的仲裁包上執行其操作，其在TO處全是空的。只要每個輸入埠的每個FIFO具有一個條目，則每個挑選器將會將條目放置在空仲裁包中的兩個位置內。然後，在圖8的206，將每個挑選器處的仲裁包傳遞到一個後續挑選器，從而使得仲裁包81現在例如在埠 I的挑選器處。埠 3處的仲裁包包送至埠 I。在圖8中，在208，可以檢查給定的仲裁包是否已經訪問了每個挑選器。在此，由於情況是沒有訪問，所以所描繪的方法返回至204。
[0033]在圖4中，埠 O的挑選器現在具有仲裁包84，其中(通過之前步驟中的埠 3的挑選器)填充了位置B7和B6。在FIFO的優先級在每次時間增量時進行切換的情況下，現在埠 O的第二 FIFO具有放置的優先級，並且該FIFO中的第一條目為BI，可以對該條目進行放置。當FIF00尋求放置時，發現填充了 B6。現在，在一個實現方式中，進行往回對FIF00的搜索以對FIF00內的可以被放置的第一條目進行標識，該條目為該第二條目B4。每個挑選器在Tl (圖8中的204和205)期間放置來自其FIFO中的兩個條目並再次傳遞(圖8中的206)仲裁包81-84。在T2中，這些第一 FIFO (FIF00)具有優先級，並且如所描繪的，每個挑選器放置一個或多個條目。
[0034]在圖8中，表示該挑選的數據布置可以包括兩個操作(圖8中的205處)。一個操作是在與被選中的輸出埠相關聯的仲裁包內設置比特，並且另一個操作是將事務信息(在一個示例中)發送至針對被選中的輸出埠而填充的FIFO。本方法展示了一種其中每個仲裁包包括用於每個輸出埠的比特的實現方式。當挑選器在給定的仲裁步驟中挑選了該輸出埠時，對該比特進行設置。然而，仲裁包不包含與事務的細節相關的信息。而是該信息被單獨地傳輸至與該輸出埠相關聯的緩衝區。在一個示例中，該信息包括內存地址，從該內存地址讀取或寫入信息，該地址發往或源自該輸出埠。在本實現方式中，沒有在仲裁包中傳遞事務的細節，並且因此減少了所需的互連量和容裝仲裁包的寄存器的大小。並且，減少了每個挑選器所需的電路或邏輯，因為可以用位屏蔽遮蔽仲裁包以對便以最小的複雜程度對任何未填充的輸出埠進行標識。
[0035]埠 I處的仲裁包84示出了可以從FIF00放置B0，但不存在來自FIF01的可以被放置的非衝突條目。在一個FIFO不能放置條目的情況下，本情況對更簡單的硬體實現方式的局限性進行標識，在該實現方式中沒有從同一 FIFO放置兩個條目。更加複雜的實現方式可以允許挑選器從這些FIFO中的一個或多個中選擇條目的滿分配。另一個實現方式可以確定在另一個FIFO先行的情況下(即，在這些FIFO其中之一中僅存在I個非衝突條目，該條目與優先級FIFO中的第一優先級條目衝突)這些FIFO其中之一是否不能放置條目，並且相應地對布置進行調整。在上述情況下，例如，在T2允許FIF01將BO放置在仲裁包84內的情況下，則FIF00可以放置B2。在此，示出了一種更簡單的HW實現方式，從而使得埠 I的FIF01在T2中沒有將兩個條目放置在仲裁包84內。如圖4中所描述的，根據這些示例繼續填充仲裁包81-84。
[0036]在圖4的86處描繪了最後的仲裁包。所有這些仲裁包在同一仲裁步驟中結束。因此，在本示例中，仲裁需要一個用於每個輸入埠的步驟(在該每個輸入埠中給予一個將條目放置在每個仲裁包內的步驟)並且所有挑選器並行地操作。根據輸出的數量確定每個仲裁包的大小。因此，圖4的示例示出了一個4輸入(其中，每個輸入具有2個FIFO或線路)8輸出仲裁。
[0037]如果仲裁包包括關於所放置的傳送的信息，則可以在210傳遞這些仲裁包以便在每存儲體多個輸出FIFO (—個這種FIFO，其中針對每個存儲體保持多個FIFO)之間進行劃分。
[0038]圖5不出了按照根據輸出存儲體(存儲體0-7)的順序對齊的每個仲裁包。在圖5中，符號的形式為「L#-#_T#」。本符號對後面跟著哪個FIFO (或者O或者I)、後面跟著該條目放置在該仲裁包內時的時間的輸入埠進行標識。例如，在仲裁包81中，存儲體O條目在T2來自線路2FIF00。本符號沒有暗示這種數據包括在該FIFO本身內，而是用來對仲裁器如何在圖4的示例中放置請求進行追蹤。
[0039]此排序示出了根據以上披露的仲裁的一種邊緣效應是可以相對於輸入FIFO中的順序對來自同一輸入、發往同一輸出埠的條目進行重排序。例如，考慮存儲體O，將來自仲裁包83的條目放在T3處，但將來自仲裁包84、位於仲裁包83後面的條目放置在T2處。因此，在一種方法中，可以執行每個輸出埠重排序(圖8中的212)。此重排序可以在沒有來自鄰近輸出埠的信息的情況繼續進行並且只需要考慮每個輸出埠 FIFO的內部狀態。圖6示出了響應於對來自同一 FIFO的無序條目進行標識而在存儲體O和存儲體I中重排序的條目92。輸出FIFO中的重排序還可以在選擇時間基礎上嚴格地進行，而不是每輸入埠重排序。在這種方法中，僅根據挑選時間對輸出FIFO中的條目進行重排序。圖6還示出了空條目是存儲體I內的第一條目。圖7描繪了空條目可以冒泡排序93到FIFO的後面；還可以簡單地清除空條目。取決於FIFO的實現方式，考慮到這種清除，可以或不可以將剩餘的條目進行重新定位。
[0040]圖9描繪了另一種過程，仲裁器5可以通過該過程進行對互連元件6的訪問的仲裁。在280，挑選器對所接收到的仲裁包內的空位置進行標識(不包括佔滿的位置)。在一個示例中，這意味著每個仲裁包針對每個輸出支持一個條目，儘管可以構造實現方式來有區別地執行。例如，不同的輸出可以在不同速度下運行，並且因此給定的仲裁包針對一個輸出可以具有比另一個輸出更多的位置。輸出的容量可以是動態的，並且如果希望的話，用於這種情況的仲裁包還可以實施動態調整。
[0041]在282，可以對來自一個第一優先級FIFO的可以被放置的第一條目進行標識(如果有的話)。在286，確定是否可以放置來自一個第二優先級FIFO的條目。如果可以，則在288放置來自該第一和第二優先級FIFO的條目。否則，在290確定第二優先級FIFO的可以被放置的僅一個條目與所標識的第一優先級FIFO條目之間是否存在衝突。如果存在這種衝突，則在294，對可以與來自該第二優先級FIFO的條目一起放置的來自該第一優先級FIFO的另一個條目進行標識。在296，放置這些條目。在298，作出是否訪問了每個挑選器的確定。如果沒有訪問，則將仲裁包傳遞至下一個挑選器。否則，如以上解釋的，在302，可以執行每個輸出FIFO的條目的重排序。圖9的示例示出了一種方法，其中可以進行更多涉及到的埠內衝突解決。然而，本方法還會由於嚴格老化引起條目無序地離開輸入埠，這對一些應用而言是不令人希望的。並且，實施這種過程的硬體可能更加複雜。
[0042]挑選器行為的另一個變化可以是:用於接收給定仲裁包的最後的挑選器可以試圖填充該仲裁包內的任何剩餘的位置。本方法還可能引起更大的硬體複雜程度，因為硬體將需要能夠在最後的時間段中比之前的時間段放置更多的條目。可以使最後的時間段更長，如允許多達3次挑選，或可以提供更多的挑選器硬體。如果需要增加仲裁時間或更多的硬體，則降低給定仲裁包中增加的空條目的概率，從而將減少返回至允許最後的挑選器進行任意數量的布置。側載入器37向這種情況提供了替代性方法的示例。
[0043]圖10和圖11描繪了根據本公開內容的用於輸入埠的另一種實現方式。圖2描繪了每個輸入埠的每條線路包括存儲用於所有輸出埠的有序請求集合的對應FIFO。圖10描繪了每個輸入埠反而具有可以基於每個輸出埠緩衝被隔離的請求列表的內存源375。具體地，每條輸入線路14a和14b仍然接收可以對任何輸出埠進行標識(在通常情況下)的請求集合；並且條目351-356通過對不同輸出埠進行命名來舉例說明這種情況。然而，並非需要挑選器30往回搜索FIFO來對可以被放置的條目進行標識，而是可以對條目進行預分類。圖11描繪了內存375中的內存位置存儲了請求351-354，所有這些請求對輸出埠 45進行標識，而其他請求對不同的輸出埠進行命名並因此被存儲在內存375的不同區段內。如希望，可以提供機構用於在內存375中強制實施條目布置的具體順序，其中來自不同輸入線路的多個條目(例如，條目354和351)對同一輸出埠進行標識。關於圖12描述了圖10和圖11的實現方式的操作示例。
[0044]圖12描繪了根據本公開內容的仲裁的示例過程，其中每個輸入埠根據輸出埠對條目進行預分類，以供該輸入埠的對應挑選器使用。在402，在輸入線路處接收對輸出埠進行識別的請求。在404，將該請求存儲到與該輸出埠相關聯的箱中。在這種分類過程中，任何輸入線路可以繼續接收進一步的請求。在406，可以為該請求分類到其中的箱設置指示請求在等待仲裁的標記。此活動可以是受制約(condit1ned)的，或者可以僅在請求第一次分類到具體的箱中時或者在該箱變空之後、已經對該箱中的請求進行仲裁之後作出可觀測的變化。
[0045]在408,每個挑選器接收仲裁包,從這些箱中將一個或多個請求放置在該仲裁包內。在410，每個挑選器對其仲裁包內的開放位置進行標識。在412，決定兩個以上請求是否可以用於放置，並且如果可以，則在416，進行從可用的請求之間選擇兩個請求的過程。在418，可以放置那些選定的請求。否則，在414，可以放置兩個或更少的請求。以上示例基於允許每個挑選器選擇多達兩個有待放置的請求(如果可能的話)。實現方式可以對每個挑選器允許更多或更少的請求並且將相應地調整這種數量。
[0046]當可用的請求比位置更多(或請求超過允許的布置極限)時，各種過程或其他技術可以用來選擇有待放置的請求。圖13和圖14提供了兩個這種過程的示例。在圖13中，在420，可以訪問與每個箱中的請求相關聯的老化計數器，並且在422，可以選擇兩個最老的條目用於布置。可以在緩衝不以一種用按年齡分類方式保持條目的方式來實施的情況下提供老化計數器。在424，可以對與剩餘條目相關聯的老化計數器進行更新。本方法提供了每請求老化，這對一些實現方式而言會引起過度的開銷。圖14描繪了其中每箱多個計數器的示例。在426，對與每個箱相關聯的老化計數器進行訪問，並且選擇兩個具有最老計數器的箱。選擇之後，在430，所選定的箱上的計數器被清零(reset)並且剩餘箱上的計數器增加。在本方法中，存在一個在多個箱之間保持選擇公平的機構。由於每個箱可以存儲多個條目，所以將需要更少的計數器。每箱老化的其他實現方式可以包括循環(round robin)選擇技術，其中僅具有有待仲裁的請求的箱參與該循環。可以實施對循環選擇的修改以處理某些輸入埠比其他輸入埠更活躍等的情況。
[0047]仲裁器和它們對其進行調度的互連可以用於多種情況下。例如，它們可以用來加載帶有數據元素的分布式內存，其中仲裁器所使用的控制信息對數據從來源(例如，處理器，見圖1)到合適內存的傳輸進行調度。例如，一種應用是在分布式計算的背景下，如分布式圖形處理。分布式圖形處理可以包括光線追蹤。例如，可以對光線進行處理(例如，可以針對與3-D場景的圖元(primitive)的相交對光線進行追蹤，從而進行渲染)。仲裁器可以接收光線的有待分布在分布式內存之間的定義數據，其中，在光線相交測試期間可以根據需要反覆訪問這些內存。其他應用包括從分布式內存中讀取數據。因此，可以讀取、寫入對互連訪問的請求，或其任意組合。因此，互連的埠可以用作輸入端或輸出端。
[0048]本公開內容涉及仲裁，其中在仲裁周期中將保證多個輸入埠中的每個輸入埠具有至少一次預訂任何輸出埠的機會。這種保證的一種方法是在仲裁周期期間在每個仲裁參與者(例如，圖2的挑選器)處啟動空仲裁包至少一次。此外，本公開內容描述了在進行了更高優先級挑選之後每個仲裁參與者如何可以被給予遞減的到剩餘可用的任何輸出埠的優先級順序挑選機會集合。在圖2和圖4的示例中，這相當於使仲裁包轉動穿過每個挑選器，從而使得每個挑選器獲得每個仲裁包。然而，不同的仲裁包在進行了不同數量的挑選之後到達具體的挑選器。這些方法與波前仲裁形成對照，因為波前仲裁指定輸入埠和輸出埠的具體組合將在具體的數據傳送周期上是活躍的。例如，在每個數據傳送周期中在同一點處將輸入端I連接到輸出端2上。
[0049]本文的示例通常描述了響應於請求而分配的多對埠。然而，在一些應用中，請求可以定義更複雜的埠組合，如將一個數據元素寫入到許多位置，將一個數據元素集寫入到多個指定的輸出端，以及將多個數據元素從多個指定的位置讀到單個讀取埠。
[0050]典型的實現方式可以使用固定的功能硬體，該硬體可以在需要良好定義的重複互連任務集合的情況下允許最大速度和效率。其他實現方式可以使用可配置硬體或固定功能與可配置硬體的組合。
[0051]在一些實現方式中，互連元件6可以是交叉開關，其中可以進行任何事物到任何事物的連接(例如，在傳送周期中，任何兩個埠可以配成對)。可以通過專用硬體實現交叉開關。然而，在一些實現方式中，可以使互連元件6的性質抽象化，從而使得可以通過總線實現該互連元件，即使仲裁器5將互連元件6作為交叉開關對待。例如，η X η埠的交叉開關在一個步驟中可以支持最多η個數據傳送。在一個仲裁步驟中可以支持η個數據傳送的總線可以實現物理互連，並且可以向仲裁器5提供展示總線的基於埠的視圖的抽象層。
[0052]一些實現方式可以使用可編程元件來實現所披露的仲裁的各方面，即使這種實現方式對於一些應用而言是不切實際的。如果在固件和/或軟體中實施，則功能可以被展示為計算機可讀介質上的一個或多個指令或代碼，在一個實例中該介質是非瞬態的。示例包括用數據結構編碼的計算機可讀介質和用電腦程式編碼的計算機可讀介質。機器可讀介質包括非瞬態機器可讀介質。其他種類的介質包括傳輸介質。非瞬態介質可以是任何可以被機器訪問的有形介質。舉例來講，但不具有限制性，這種計算機可讀介質可以包括RAM、ROM、EEPROM、CD-ROM或其他光碟存儲器、磁碟存儲器、或其他磁存儲裝置、或任何可以用來以指令或數據結構的形式存儲所希望的程序代碼和可以被機器訪問的其他介質。
[0053]提供各方面和特徵的描述用來使本領域的技術人員能夠製作和使用這些系統、裝置以及執行所披露的方法。各種修改將對本領域的技術人員是明顯的，在不背離本公開內容的精神和範圍的情況下可以將本文件內描述的原理應用到其他方面。因此，本說明書並不旨在限制權利要求書。相反，將使權利要書求賦予與在此披露的原理和新穎性特徵一致的範圍。
[0054]附圖包括結構的相對安排和過程組件的排序，僅作為幫助理解本說明書。這些相對安排和編號不是對權利要求書中的元素和步驟的排序或安排的任何特定限制的隱含披露。在不背離本公開內容的範圍的情況下可以順序地互換過程限制，權利要求書並且裝置加功能語句旨在涵蓋被描述為執行所述功能的不僅包括結構等效物而且還包括等效結構的結構。
[0055]儘管使用了各種示例和其他信息來解釋所附權利要求書的範圍內的多個方面，但不應基於這種示例中的具體特徵或安排而暗示對權利要求書的限制，因為普通技術人員將能夠使用這些示例導出很多種實現方式。進一步地，並且儘管以結構特徵和/或方法步驟的示例專用的語言描述了某個主題，但應理解到，所附權利要求書中限定的主題不一定局限於這些描述的特徵或動作。例如，這種功能性可以有所不同的分布，或者在與除了在此標識的組件以外的組件、附加的組件或更少的組件執行。相反，公開了所述特徵和步驟作為所附權利要求書的範圍內的系統和方法的組件的示例。
【權利要求】
1.一種對互連訪問進行仲裁的方法，包括: 隨時間接收一個或多個數據傳送請求，每個請求對互連中的來自η個輸入埠中的一個輸入埠和來自m個輸出埠中的一個輸出埠進行指示，將通過該互聯為該請求進行服務； 對這些請求中的每個請求進行緩衝； 將對應的空仲裁包分配給已分配給這些輸入埠中的每個輸入埠的對應的挑選器，每個仲裁包具有用於這m個輸出埠中的每個輸出埠的位置； 在這些挑選器中的每個挑選器處，選擇至少一個緩衝請求並將每個選定的請求放置在用於該選定的請求所指示的輸出埠的位置中的那個挑選器處的仲裁包內； 在這些挑選器之間傳遞這些仲裁包，直到每個挑選器已經接收到每個仲裁包，並且同時每個挑選器具有每個仲裁包，試圖將至少一個請求放置在該仲裁包內的任何剩餘位置中；以及 根據這些仲裁包內的請求的布置，使用該互連來對這些請求的履行進行調度。
2.根據權利要求1所述的對互連訪問進行仲裁的方法，其中，放置每個選定的請求包括在與該請求所指示的輸出埠相關聯的仲裁包內設置屏蔽位和將來自該選定的請求的輸入埠信息提供至與該輸出埠相關聯的緩衝區。
3.根據權利要求1和2中任一項所述的對互連訪問進行仲裁的方法，其中，這些輸入埠中的每個輸入埠包括兩條或更多條線路，並且其中，該緩衝包括對來到一個單獨的FIFO緩衝區內的線路中的每條線路的請求進行緩衝。
4.根據權利要求1至3中任一項所述的對互連訪問進行仲裁的方法，其中，用於每個請求的輸入埠通過仲裁器的哪個輸入埠接收到該請求來指示。
5.根據權利要求1所述的對互連訪問進行仲裁的方法，其中，該傳遞包括激活電路以將每個仲裁包從一個挑選器中的寄存器傳送到後續挑選器中的寄存器。
6.根據權利要求1所述的對互連訪問進行仲裁的方法，其中，該緩衝包括針對該輸入埠的對應挑選器的訪問根據該請求中所標識的輸出埠存儲這些請求中的每個請求並且設置對該輸出埠的請求的可用性進行指示的標記。
7.根據權利要求1所述的對互連訪問進行仲裁的方法，其中，該互連包括η個輸入m個輸出的交叉開關，並且該方法進一步包括根據這些仲裁包內的請求的布置在後續多個數據傳送周期中選擇性地將該交叉開關的η個輸入中的每個輸入連接到該交叉開關的m個輸出其中之一上。
8.根據權利要求1至7中任一項所述的對互連訪問進行仲裁的方法，其中，這些輸出埠每個與內存地址相關聯，並且每個請求包括內存地址，可以根據與這些輸出埠中的每個輸出埠相關聯的內存地址從該內存地址推斷出輸出埠。
9.根據權利要求8所述的對互連訪問進行仲裁的方法，其中，這些內存地址跨這些輸出埠是成帶的。
10.根據權利要求1所述的對互連訪問進行仲裁的方法，其中，放置每個請求包括設置與正在放置的位置相對應的屏蔽位和將數據傳送信息發送至與該請求的被指示出的輸出埠相關聯的重排序緩衝區。
11.根據權利要求1所述的對互連訪問進行仲裁的方法，其中，該緩衝包括至少對每個請求進行緩衝，直到該輸入埠的挑選器已經對其進行了服務，其中該請求通過該輸入埠而到達。
12.根據權利要求1至11中任一項所述的對互連訪問進行仲裁的方法，其中，每個輸出埠在每個仲裁包內具有對應的預先確定的相對位置，並且將請求放置在該仲裁包內包括用關於該請求的數據填充該位置。
13.—種用於η個輸入埠 m個輸出埠的互連訪問的仲裁器,包括: 緩衝區，可操作用於存儲在這些η個輸入埠中的任何輸入埠處接收到的多個請求， 多個挑選器，這些挑選器中的每個挑選器被耦聯成從另一個挑選器接收仲裁包，該仲裁包包括用於這m個輸出埠中的每個輸出埠的位置，以試圖將請求放置在所接收到的仲裁包內的至少一個空位置中，其中，這些挑選器中的任何挑選器能夠對所接收到的仲裁包內的任何空位置進行填充，並且將該仲裁包傳遞至另一個挑選器，其中，所述多個挑選器並行地完成η個仲裁包；以及 用於這m個輸出埠中的每個輸出埠的對應的重排序緩衝區，該對應的重排序緩衝區可操作用於接收該輸出埠的事務信息並強制實施對源自同一輸入埠的條目的先進先出順序。
14.根據權利要求13所述的仲裁器，其中，所述多個挑選器包括用於這η個輸入埠中的每個輸入埠的挑 選器。
15.根據權利要求13所述的仲裁器，其中，每個仲裁包包括用於這m個輸出埠中的每個輸出埠的單個比特，當對用於該輸出埠的位置進行填充時，該挑選器對該比特進行設置，並且其中，每個挑選器可操作用於向這m個輸出埠中的每個輸出埠的對應重排序緩衝區提供這些仲裁包中已填充的條目。
16.根據權利要求13所述的仲裁器，其中，用於這m個輸出埠中的每個輸出埠的重排序緩衝區包括多個重排序緩衝區，其中，該多個重排序緩衝區中的至少一個重排序緩衝區可操作用於從這些挑選器接收條目，同時來自這些緩衝區的另一個緩衝區的條目被用來對該互連進行控制。
17.根據權利要求13所述的仲裁器，其中，這m個輸出埠中的每個輸出埠包括多個重排序緩衝區，其中，這些重排序緩衝區其中之一能夠用於對互連進行控制，同時另一個重排序緩衝區正被該仲裁器用後續請求的傳送信息進行填充。
18.根據權利要求13所述的仲裁器，其中，這η個輸入埠中的每個輸入埠包括多條輸入線路，並且單個挑選器被耦聯成對從這些輸入線路中的每條線路接收到的仲裁包內的空位置進行填充。
19.一種包括根據權利要求12至18中任一項所述的仲裁器的計算系統，進一步包括具有一組埠的互連和控制器，該控制器可操作用於將該互連配置成使得能夠在這些埠的指定組合之間發生數據事務，該控制器可操作用於接收互連配置數據集合序列並且根據這些互連配置數據集合將該互連配置成用於數據傳送序列，每個互連配置數據集合包括當將要使用該互連配置數據集合時對在數據傳送周期期間有待耦聯的埠的組合的指示。
【文檔編號】H04L12/937GK104052686SQ201410088316
【公開日】2014年9月17日 申請日期:2014年3月11日 優先權日:2013年3月12日
【發明者】J·M·理查茲, S·J·克勞塞特, J·R·雷德格瑞芙 申請人:想像技術有限公司