雙向環路互連上單分組到達的流量控制方法和設備的製作方法
2023-11-11 15:47:42
專利名稱：雙向環路互連上單分組到達的流量控制方法和設備的製作方法
技術領域：
本發明的實施方案總體上涉及網絡中的流量控制，尤其是雙向環路互連中的分組流量控制。
背景技術：
計算機網絡中的流量控制機制管理著從源節點到目的地節點的分組傳送。典型的流量控制機制包括布線和邏輯以控制並發到達目的地節點的多個分組。但這種機制有若干缺點。
首先，如果目的地節點能夠同時處理的分組少於能夠在一個時鐘周期內到達的分組，可能需要額外的硬體來緩衝到達的分組，直到目的地節點能夠處理它們為止。另外，目的地節點可能能夠同時處理的分組和在一個周期內能夠到達的分組一樣多，仍然需要顯著的附加硬體。這個附加硬體給空間嚴重受限的半導體晶片帶來了特定的問題。
第二，在目的地節點可能需要仲裁邏輯來確定接收分組的次序。除了增加了邏輯的複雜性之外，分組等待時間可能由於仲裁的原因而導致顯著增加。不能在分組到達的時鐘周期內接收它，相反，分組必須等待。結果是系統的整體性能降低。
在環路拓撲中，並發的多分組到達是特別要關注的問題。如果一個分組必須在環路上等待直到目的地節點接收該分組，那麼等待的分組之後的分組在環路上的前進都會被阻塞。結果是目的地節點上發生了不必要的擁塞。這種情況顯著地增加了分組等待時間並降低了環路的峰值吞吐量。
因此，在本領域中需要克服由並發的多分組到達導致的缺點，在環路拓撲中尤其如此。
發明內容
為了克服上述的缺陷，在本發明的一個方面，提供了一種方法，包括在半導體晶片上，根據源節點和目的地節點之間的距離在一個時鐘周期內以第一方向在第一環路結構上從源節點向目的地節點發送分組或以與第一方向相反的第二方向在第二環路結構上從源節點向目的地節點發送分組。
在本發明的另一個方面，提供了一種方法，包括在偶數編號的時鐘周期內在半導體晶片的第一環路結構上接收來自源節點的分組；並在奇數編號的時鐘周期內在半導體晶片的第二環路結構上接收來自源節點的分組。
在本法發明的又一個方面，提供了一種方法，包括選擇在半導體晶片上的順時針環路結構和逆時針環路結構中的一個環路結構以把分組從源節點傳輸到目的地節點；計算在所選擇的環路結構上源節點和目的地節點之間的距離；確定計算出的距離是偶數還是奇數個時鐘周期；根據確定出的距離在第一時鐘周期把分組從源節點發送到目的地節點；根據所選擇的環路結構在第二時鐘周期內在目的地節點接收分組。
在本發明的又一個方面，提供了一種半導體晶片，包括第一環路結構，以第一方向發送分組；第二環路結構，以與第一方向相反的第二方向發送分組；和與第一和第二環路相耦合的多個節點，第一和第二環路結構根據到目的地節點的距離在一個時鐘周期內把分組發送到目的地節點。
本發明還提供了一種系統，包括一個多處理器晶片，包括多個節點，和與節點耦合的多個環路結構，用於根據源節點和目的地節點之間的距離在時鐘周期內從源節點向目的地節點傳輸分組，該多個環路結構中的第一個環路結構以第一方向傳輸分組，而該多個環路結構中的第二個環路結構以和第一方向相反的第二方向傳輸分組；和與該多處理器晶片耦合的總線。
本發明還提供了一種機器可讀介質，其上存儲了實施一種方法的多個可執行指令，該方法包括選擇在順時針環路結構和逆時針環路結構中的一個上從源節點傳輸分組到目的地節點；計算在所選擇的環路結構上從源節點到目的地節點之間的距離；確定計算出的距離是偶數還是奇數個時鐘周期；根據確定出的距離在第一時鐘周期內從源節點向目的地節點發送分組；根據所選擇的環路結構在第二時鐘周期內在目的地節點上接收分組。
本發明還提供了另一種機器可讀介質，其上存儲了實施一種方法的多個可執行指令，該方法包括在半導體晶片上，根據源節點和目的地節點之間的距離在一個時鐘周期內以第一方向在第一環路結構上從源節點向目的地節點發送分組或以與第一方向相反的第二方向在第二環路結構上從源節點向目的地節點發送分組。
圖1是依照本發明的一種實施方案的半導體晶片，包括耦合到單個雙向環路互連的多個節點。
圖2是依照本發明的一種實施方案的半導體晶片，包括耦合到多個單向和/或雙向環路互連的多個節點。
圖3是依照本發明的一種實施方案的方法的流程圖。
圖4是依照本發明的一種實施方案的與雙向環路互連耦合的分組隊列結構。
圖5是實現本發明的實施方案的計算機系統的框圖。
具體實施例方式
本發明的實施方案可以提供一種在一個時鐘周期內在雙向環路上的目的地節點上的單分組到達的方法。在一種實施方案中，該方法可以包括根據源節點和目的地節點的(按照時鐘周期測量的)距離在預定的和/或動態確定的時鐘周期內在半導體晶片的雙向環路互連上把分組從源節點發送到目的地節點。在這種實施方案中，該方法還可以包括如果兩個節點之間的距離是偶數，就在偶數時鐘周期內在環路互連上以順時針方向發送分組，並在奇數時鐘周期內以逆時針方向發送分組。該方法還可以包括如果兩個節點之間的距離是奇數，就在奇數時鐘周期內以順時針方向發送分組，並在偶數時針周期內以逆時針方向發送分組。
本發明的實施方案還可以提供一種半導體晶片，包括一個雙向環路互連和與該雙向環路互連耦合的節點，其中該雙向環路互連可以在源和目的地節點之間傳輸分組。每個節點還可包括若干隊列，以在根據分組將經過的距離是偶數或奇數以及分組將經過的方向是順時針或逆時針而在傳輸之前保存選擇的分組。
本發明的實施方案可以有利地確保在目的地節點上一個時鐘周期內的單分組到達，由此克服了多分組到達機制的問題。尤其，這些實施方案可以避免典型流量控制機制的附加硬體以及仲裁邏輯的複雜度。此外，這些實施方案可以確保雙向環路互連上的分組到達而不會顯著增加雙向環路互連上的分組等待時間也不會顯著降低雙向環路互連上的峰值吞吐量。因此，可以簡化目的地節點上的峰值流量控制。這些實施方案對用於晶片多處理的片上雙向環路互連尤其有用。
圖1是依照本發明的一種實施方案的半導體晶片，包括耦合到雙向環路互連的多個節點。節點110(1)到110(n)可以在多個不同的訪問點或訪問站與雙向環路互連120相連。分組可以按照順時針方向或逆時針方向在互連120上的節點110(1)到110(n)之間穿行。
節點110(1)到110(n)可以包括處理器、高速緩衝存儲器體、存儲器接口、全局一致性引擎接口、輸入/輸出接口和在半導體晶片上發現的任意其它這種分組處理部件。
在圖1中，在本發明的一種實施方案裡，通過邏輯地將單個大容量共享高速緩衝存儲器劃分為若干子集可以將節點110(1)到110(n)實現為高速緩衝存儲器體節點。每個高速緩衝存儲器體節點可以包括單個高速緩衝存儲器中的一部分地址空間，並且可以獨立地服務於對單個高速緩衝存儲器中該部分地址空間的塊請求(讀、寫、使無效等等)。在互連120上，每個高速緩衝存儲器體節點可以有它自己的訪問點或訪問站。
在圖1中，互連120可以包括多個單向線(未示出)，其中第一組單向線可以按照順時針方向傳輸分組，第二組可以按照逆時針方向傳輸分組。每組單向布線可以有一個具體的目的(例如，發送地址命令)或者具有通用目的(例如，支持多種分組類型(地址請求、數據、高速緩衝存儲器一致性協議消息等))。可選地，可以指定每一組單向線傳輸單一分組類型。
可選地，在圖1中，互連120可以包括多個能夠在兩個方向上傳輸分組的雙向線。在這種備選實施方案中，該半導體晶片可以包括開關邏輯，用於將所述線切換到希望的方向以在特定的事務期間傳輸分組。
互連120可以按照各種不同的速率傳輸分組。例如，互連120可以按照每時鐘周期一個或多個節點的速率或每兩個或更多時鐘周期一個節點的速率傳輸分組。很多因素可以決定傳輸速率，包括通信量、時鐘速率、節點間的距離等等。通常，一個節點必須等到已經在互連120上並位於該節點的任意分組通過該節點後才能將分組放到互連120上。
圖2是依照本發明的一種實施方案的半導體晶片，包括耦合到多個環路互連的多個節點。節點210(1)到210(n)可以在多個不同的訪問點或訪問站與環路互連220(1)到220(m)相連。每個節點可以選擇環路互連220(1)到220(m)中的任何一個以便在其上把分組傳輸到另一節點。
在一種實施方案中，圖2中的所有互連都可以是單向的，其中一些互連只以順時針方向傳輸分組而其它互連只以逆時針方向傳輸分組。
在一種備選實施方案中，圖2中的一些互連可以是單向的，而其它的，則是雙向的。在這種備選實施方案中，單向互連中的一些可以只在順時針方向上傳輸分組而其它只在逆時針方向上傳輸分組。雙向互連可以在兩個方向上傳輸分組，與圖1中的雙向互連的操作一致。
圖3是依照本發明的一種實施方案的方法的流程圖。在圖3中，該方法可以確保在雙向環路互連上的目的地節點上在一個給定的時鐘周期內的單分組到達。在一種實施方案中，節點在雙向環路互連上可以以順時針或逆時針方向發送和接收分組。該雙向環路互連可以包括以順時針方向傳輸分組的第一組線(它可以包括第一環路結構)和以逆時針方向傳輸分組的第二組線(它可以包括第二環路結構)。該雙向環路互連可以看作是一系列時隙(slot)，每個時隙在每個時鐘周期內把分組從一個訪問點或訪問站攜帶到下一個訪問點或訪問站。
在圖3中，源節點(如圖2的節點210(1))可以選擇(310)順時針或逆時針環路結構，以在其上把分組從與環路結構相耦合的源節點傳輸到目的地節點。在一個實施例中，所述選擇可以基於在兩個環路結構上達到目的地節點將要經過的時隙的數目。例如，如果在順時針環路結構上經過的時隙的數量小於在逆時針環路結構上經過的時隙的數量，源節點可以選擇順時針環路結構。
可選地，所述選擇可以基於在兩個環路結構上到達目的地節點要經過的節點數，這裡可以選擇分組在其上經過節點較少的環路結構。在另一備選實施方案中，所述選擇可以基於經過兩個環路結構的時鐘周期數，這裡所選擇的環路結構可能佔用較少的時鐘周期來傳輸分組。可選地，所述選擇可以基於環路結構上的通信量，這裡所選擇的環路結構可以具有較少通信量。可以用任意其它這種標準來確定該選擇。
在圖3中，源節點可以計算(315)到所選擇的環路結構上的目的地節點的距離。該距離可被計算為到達目的地節點的時鐘周期數。在一種備選實施方案中，距離可以被計算數到達目的地節點的所經歷的節點數。可以用任意其它這種標準來確定源和目的地節點之間的距離。
在圖3中，源節點可以確定(320)計算出的距離是偶數或奇數個時鐘周期遠。如果計算出的距離是偶數個時鐘周期，源節點可以確定(325)所選擇的環路結構是順時針還是逆時針環路結構。如果所選擇的環路結構是順時針的的環路結構，那麼源節點可以在一個偶數編號的時鐘周期內把分組發送(330)到目的地節點以便確保該分組在一個偶數編號的時鐘周期內到達該目的地節點。如果所選擇的環路結構是逆時針的的環路結構，那麼源節點可以在一個奇數編號的時鐘周期內把分組發送(335)到目的地節點以確保該分組在一個奇數編號的時鐘周期內到達目的地節點。
在圖3中，如果源節點確定(320)計算出的距離是奇數個時鐘周期遠，那麼源節點可以確定(340)所選擇的環路是順時針還是逆時針環路結構。如果所選擇的環路結構是順時針的環路結構，那麼源節點就可以在一個奇數編號的時鐘周期內把分組發送(345)到目的地節點以確保該分組在一個偶數編碼的時鐘周期內到達該目的地節點。如果所選擇的環路結構是逆時針的的環路結構，那麼源節點可以在一個偶數編號的時鐘周期內把分組發送(350)到目的地節點以確保該分組在一個奇數編碼的時鐘周期內到達目的地節點。
表1示出了圖3所描述的發送分組的方法中所用的邏輯。該表條目給出了不同場景下源節點的發送時鐘周期。對一個給定的傳輸方向(順時針或逆時針方向)和從源節點到目的地節點的偶數或奇數距離而言，該表條目表明了該源節點可以在偶數編號還是奇數編號的時鐘周期內發送分組。
表1.分組發送規則在圖3中，目的地節點可以確定(355)分組正在到達順時針和逆時針環路結構中的哪一個。例如，目的地節點可以輪詢順時針和逆時針環路結構以確定分組在哪個環路上到達。在本發明的這個實施方案中，分組可以在順時針環路結構上到達並在偶數編號的時鐘周期內由目的地節點接收(360)。分組可以在逆時針環路結構上到達並在奇數編號的時鐘周期內由目的地節點接收(365)。可以設想分組可以到達的其它實施方案。
由本發明的實施方案實現的根本規則是目的地節點可以只在偶數編號的時鐘周期內從順時針環路結構接收分組並只在奇數編號的時鐘周期內從逆時針環路結構接收分組。這可以確保在任意時鐘周期內只有單個分組到達目的地節點。源節點的發送規則可以公式化以滿足該根本規則。
假定，依照本發明的一種實施方案，例如，源節點n(i)計算它與目的地節點n(j)之間的距離，此處，距離是d(i，j)。如果目的地節點n(j)在順時針環路結構上距離源節點n(i)是偶數個時鐘周期遠，節點n(i)可以在偶數編號的時鐘周期C上發送分組到n(j)，因為到達的時鐘周期C+d(i，j)是偶數，即偶數加上偶數等於偶數。因而，可以滿足根本規則。
同樣，依照本發明的一種實施方案，例如，如果目的地節點n(j)在順時針環路結構上距源節點n(i)奇數個時鐘周期遠，節點n(i)可以在偶數編碼的時鐘周期C上向節點n(j)發送分組，因為到達的時鐘周期C+d(i，j)是奇數，即偶數加上奇數等於奇數。因而，可以再次滿足根本規則。
在一種備選實施方案中，雙向環路互連可以包括兩個單向環路互連以在相反的方向上傳輸分組。在這種實施方案中，其中一個以順時針方向傳輸分組的單向環路互連可以包括第一環路結構，並且以逆時針方向傳輸分組的另一單向環路互連可以包括第二環路結構。
在其它備選實施方案中，雙向環路互連可以包括一個單向環路互連和一個雙向環路互連或兩個雙向環路互連。與前面描述的實施方案類似，其中一個互連可以包括第一環路結構，另一個互連可以包括第二環路結構。
將會理解，雙向環路互連並不限於一個或兩個環路結構，而是可以包括任意數量的環路結構以在多個方向上傳輸分組，所述多個方向不限於順時針和逆時針方向。
半導體晶片的實施方案可以實現依照本發明的實施方案的方法。在一種實施方案中，半導體晶片可以包括一個雙向環路互連和與該雙向環路互連相耦合的節點，其中該雙向環路互連可以根據到目的地節點的距離在預定的和/或動態確定的時鐘周期內把分組發送到目的地節點。每個節點可以包括一個減法器、可編程有限狀態機、或處理器來計算在順時針或逆時針方向上到目的地節點的距離。
在該實施方案中，每個節點可以包括多個隊列以選擇性地存儲要發送到目的地節點的分組，這裡每個隊列可以根據將要發送分組的方向和時鐘周期而存儲分組。在一種實施方案中，每個節點可以對環路互連上的順時針和逆時針方向各維護兩個要發送的分組的隊列，總共四個隊列。第一個隊列可以存儲要在偶數編號的時鐘周期內以順時針方向發送的分組。第二個隊列可以存儲要在奇數編號的時鐘周期內以順時針方向發送的分組。同樣，第三個隊列可以存儲要在偶數編號的時鐘周期內在逆時針方向上發送的分組。第四個隊列可以存儲要在奇數編號的時鐘周期內在逆時針方向上發送的分組。
圖4是依照本發明的一種實施方案的分組隊列結構。在圖4中，示出了兩個在雙向環路互連上以順時針方向傳輸分組的隊列。同樣的配置(未示出)可以用於逆時針方向上的分組傳輸。
在圖4中，第一個隊列410(1)可以保存要在偶數編號的時鐘周期內在順時針方向上發送的分組(目的地是偶數距離遠的分組)。第二個隊列410(2)可以保存要在奇數編號的時鐘周期內以順時針方向發送的分組(目的地是奇數距離遠的分組)。
在圖4中，隊列多路復用器420可以在時鐘信號線425上接收時鐘信號以觸發對隊列410(1)和410(2)之一的選擇。如果時鐘信號表明當前時鐘周期是偶數，隊列多路復用器420可以從第一隊列410(1)選擇一個分組。如果時鐘信號表明當前時鐘周期是奇數，隊列多路復用器420可以從第二隊列410(2)選擇一個分組。
如果分組在當前時鐘周期內沒有到達互連120上的節點，節點多路復用器430可以將分組從所選擇的隊列注入到互連120上。如果一個分組在當前時鐘周期內到達節點，節點多路復用器430可以允許到達的分組前進。如果這個節點是目的地節點，開關邏輯435可以將到達的分組引導到該節點-例如節點處理器440或任意節點部件中。如果這個節點不是目的地節點，開關邏輯435可以引導到達的分組在互連120上繼續前進。節點多路復用器430可以等待直到下一個合適的偶數或奇數時鐘周期才在到達的分組通過之後將來自隊列的分組注入。開關邏輯435可以引導從隊列注入的分組經過互連120。
將會理解，可以使用開關邏輯或能夠把分組引導到節點或在互連上的任意這種硬體和/或軟體。
當環路互連上的通信量均勻時，一半目的地節點可以是偶數距離遠而一半可以是奇數距離遠。如果一個未佔用的時隙在一個偶數編號的時鐘周期內到達一個節點，該時隙可以用來自偶數隊列的分組填充，並且如果該未佔用的時隙在一個奇數周期內到達一個節點，該時隙可用來自奇數隊列的分組填充。因而，不管一個空時隙何時到達，該節點總能夠注入一個等待分組(如果它有的話)以維持環路互連的完全利用、高峰值吞吐量和低分組等待時間。
本發明的實施方案可以通過通信總線與包括其它半導體晶片的系統耦合。當分組到達或離開半導體晶片時該總線可以依照本發明的實施方案傳輸分組。在一種實施方案中，該總線可以傳輸從半導體晶片拒絕的分組，條件是該被拒絕的分組在一定時間周期-例如在經過了半導體晶片的環路互連上的節點多次或已經過了多個時鐘周期，後沒有被接收。
圖5是一種計算機系統的框圖，該計算機系統包括一種體系結構狀態，包括依照本發明的一種實施方案使用的一個或多個多處理器和存儲器。在圖5中，計算機系統500可以包括與處理器總線520耦合的一個或多個多處理器510(1)到510(n)，處理器總線520可以與系統邏輯530耦合。一個或多個多處理器510(1)到510(n)中的每一個可以是N-位處理器並且可以包括一個解碼器(未示出)和一個或多個N-位寄存器(未示出)。依照本發明的一種實施方案，一個或多個多處理器510(1)到510(n)中的每一個可以包括一個雙向環路互連(未示出)以耦合到N-位處理器、解碼器、和一個或多個N-位寄存器。
系統邏輯530可以通過總線550與系統存儲器540耦合，並通過外部總線560與非-易失性存儲器570及一個或多個外圍設備580(1)-580(m)耦合。外部總線560可以表示例如一個或多個外圍部件互連(PCI)總線、PCI專業組(SIG)PCI局部總線規範(2.2修訂本，1998年12月18日發布)；工業標準結構(ISA)總線；擴展ISA(EISA)總線，BCPR Service Inc；EISA規範，1992 3.12修訂版，1992年發布；通用串行總線(USB)，USB規範1.1版，1998年9月23日發布；以及類似的外部總線。非易失性存儲器570可以是靜態存儲器器件，諸如只讀存儲器(ROM)或者是閃速存儲器。外部設備580(1)-580(m)可以包括例如鍵盤；滑鼠或其它指點設備；大容量存儲設備，如硬碟驅動器、光碟(CD)驅動器、光碟和數字視頻光碟(DVD)驅動器；顯示器等等。
本發明的實施方案可以用根據本發明的教義編程的任意類型的計算-例如通用微處理器來實現。本發明的實施方案因而還包括一種計算機可讀介質，它可以包括用來對處理器編程以執行依照本發明的實施方案的方法的指令。這個介質可以包括但不限於任意類型的盤如軟盤、光碟和CD-ROM。
可以理解用來實現本發明的實施方案的軟體的結構可以採用任意期望的形式，例如單個或多個程序。可以進一步理解本發明的一種實施方案的方法可以由軟體、硬體或其組合來實現。
上面是對本發明的優選實施方案的詳細論述。對申請人授權的本發明的完整的範圍由下文的權利要求定義。意謂著權利要求的範圍可以覆蓋除了上述那些實施方案和它們的等效方案之外的其它實施方案。
權利要求
1.一種方法，包括在半導體晶片上，根據源節點和目的地節點之間的距離在一個時鐘周期內以第一方向在第一環路結構上從源節點向目的地節點發送分組或以與第一方向相反的第二方向在第二環路結構上從源節點向目的地節點發送分組。
2.權利要求1的方法，其中第一和第二環路結構包括一個雙向環路結構。
3.權利要求1的方法，其中第一方向是順時針方向，而第二方向是逆時針方向。
4.權利要求1的方法，還包括選擇以第一和第二方向中的哪一個方向發送分組；計算在所選擇的方向上源節點和目的地節點之間的距離；以及確定計算出的距離是奇數還是偶數個時鐘周期，其中所述選擇包括選擇要經過的節點較少的方向。
5.權利要求4的方法，其中所述發送包括如果計算出的距離是偶數並且所選擇的方向是順時針，就在偶數編號的時鐘周期內發送分組；和如果計算出的距離是偶數並且所選擇的方向是逆時針，就在奇數編號的時鐘周期內發送分組。
6.權利要求4的方法，其中所述發送包括如果計算出的距離是奇數並且所選擇的方向是順時針，就在奇數編號的時鐘周期內發送分組；和如果計算出的距離是奇數並且所選擇的方向是逆時針，就在偶數編號的時鐘周期內發送分組。
7.權利要求1的方法，其中所述發送包括在偶數編號的時鐘周期內以第一方向發送來自第一隊列的分組；在奇數編號的時鐘周期內以第一方向發送來自第二隊列的分組；在偶數編號的時鐘周期內以第二方向發送來自第三隊列的分組；以及在奇數編號的時鐘周期內以第二方向發送來自第四隊列的分組；
8.權利要求7的方法，其中第一隊列保存要發送到在第一環路結構上偶數距離遠的目的地節點的分組；其中第二隊列保存要發送到在第一環路結構上奇數距離遠的目的地節點的分組；其中第三隊列保存要發送到在第二環路結構上偶數距離遠的目的地節點的分組；以及其中第四隊列保存要發送到在第二環路結構上奇數距離遠的目的地節點的分組；
9.權利要求1的方法，其中時鐘周期是偶數編號或奇數編號的時鐘周期。
10.一種方法，包括在偶數編號的時鐘周期內在半導體晶片的第一環路結構上接收來自源節點的分組；以及在奇數編號的時鐘周期內在半導體晶片的第二環路結構上接收來自源節點的分組。
11.權利要求10的方法，其中第一環路結構以第一方向傳輸分組，而第二環路結構以第二方向傳輸分組。
12.權利要求11的方法，其中第一方向是順時針方向，而第二方向是逆時針方向。
13.權利要求11的方法，其中第一方向是逆時針方向，而第二方向是順時針方向。
14.權利要求10的方法，其中環路結構是雙向的。
15.權利要求10的方法，還包括在偶數編號的時鐘周期內輪詢第一環路結構；以及在奇數編號的時鐘周期內輪詢第二環路結構。
16.一種方法，包括選擇在半導體晶片上的順時針環路結構和逆時針環路結構中的一個環路結構以把分組從源節點傳輸到目的地節點；計算在所選擇的環路結構上源節點和目的地節點之間的距離；確定計算出的距離是偶數還是奇數個時鐘周期；根據確定出的距離在第一時鐘周期把分組從源節點發送到目的地節點；以及根據所選擇的環路結構在第二時鐘周期內在目的地節點接收分組。
17.權利要求16的方法，其中第一時鐘周期包括偶數編號的時鐘周期和奇數編號的時鐘周期，第二時鐘周期包括偶數編號的時鐘周期和奇數編號的時鐘周期。
18.權利要求16的方法，其中所述發送包括如果計算出的距離是偶數並且所選擇的環路結構是順時針環路結構，就在偶數編號的時鐘周期內發送分組；如果計算出的距離是偶數並且所選擇的環路結構是逆時針環路結構，就在奇數編號的時鐘周期內發送分組；如果計算出的距離是奇數並且所選擇的環路結構是順時針環路結構，就在奇數編號的時鐘周期內發送分組；以及如果計算出的距離是奇數並且所選擇的環路結構是逆時針環路結構，就在偶數編號的時鐘周期內發送分組。
19.權利要求16的方法，其中所述接收包括如果所選擇的環路結構是順時針環路結構，就在偶數編號的時鐘周期接收分組；和如果所選擇的環路結構是逆時針環路結構，就在奇數編號的時鐘周期接收分組。
20.一種半導體晶片，包括第一環路結構，以第一方向發送分組；第二環路結構，以與第一方向相反的第二方向發送分組；和與第一和第二環路相耦合的多個節點，第一和第二環路結構根據到目的地節點的距離在一個時鐘周期內把分組發送到目的地節點。
21.權利要求20的半導體晶片，其中第一方向是順時針方向，而第二方向是逆時針方向。
22.權利要求20的半導體晶片，其中每個節點包括一個減法器，以計算到目的地節點的距離。
23.權利要求20的半導體晶片，其中每個節點包括一個可編程有限狀態機，被編程以計算到目的地節點的距離。
24.權利要求20的半導體晶片，其中每個節點包括一個處理器，用於選擇在第一和第二環路結構中的哪一個上傳輸分組，計算在所選擇的環路結構上到目的地節點的距離，以及確定該距離是偶數還是奇數個時鐘周期；以及多個隊列，以在根據確定出的距離和所選擇的環路結構在發送之前有選擇地保存分組。
25.權利要求24的半導體晶片，其中多個隊列中的第一個隊列保存在確定出的距離是偶數的情況下要在第一環路結構上發送的分組；其中多個隊列中的第二個隊列保存在確定出的距離是奇數的情況下要在第一環路結構上發送的分組；其中多個隊列中的第三個隊列保存在確定出的距離是偶數的情況下要在第二環路結構上發送的分組；其中多個隊列中的第四個隊列保存在確定出的距離是奇數的情況下要在第二環路結構上發送的分組。
26.權利要求25的半導體晶片，每個節點還包括第一多路復用器，以選擇第一和第二隊列中的一個而響應偶數編號或奇數編號的時鐘周期在第一環路結構上發送分組；第二多路復用器，以選擇第三和第四隊列中的一個而響應偶數編號或奇數編號的時鐘周期在第二環路結構上發送分組。
27.權利要求26的半導體晶片，每個節點還包括第三多路復用器，以從第一多路復用器或已經在第一環路結構上的其它分組中選擇分組以發送到目的地節點。
28.權利要求26的半導體晶片，每個節點還包括第四多路復用器，以從第二多路復用器或已經在第二環路結構上的其它分組中選擇分組以發送到目的地節點。
29.權利要求24的半導體晶片，其中所述處理器還用來確定在偶數編號的時鐘周期還是在奇數編號的時鐘周期內在所選擇的環路結構上發送分組。
30.權利要求24的半導體晶片，其中所述處理器還用來確定在偶數編號的時鐘周期還是在奇數編號的時鐘周期內接收分組；根據確定出的時鐘周期確定在第一和第二環路結構中的哪一個上接收分組；以及在確定出的時鐘周期內輪詢所確定出的環路結構以得到分組。
31.一種系統，包括一個多處理器晶片，包括多個節點，和與節點耦合的多個環路結構，用於根據源節點和目的地節點之間的距離在時鐘周期內從源節點向目的地節點傳輸分組，該多個環路結構中的第一個環路結構以第一方向傳輸分組，而該多個環路結構中的第二個環路結構以和第一方向相反的第二方向傳輸分組；以及與該多處理器晶片耦合的總線。
32.權利要求31的系統，其中第一方向是順時針方向，而第二方向是逆時針方向。
33.權利要求31的系統，其中第一方向是逆時針方向，而第二方向是順時針方向。
34.權利要求34的系統，其中所述節點中的至少一個節點是總線接口，用於在偶數編號的時鐘周期內在該多個環路結構中的第一個環路結構上接收分組，並且在奇數編號的時鐘周期內在該多個環路結構中的第二個環路結構上接收分組，並在此後的一個時鐘周期內向該總線傳輸分組。
35.權利要求34的系統，其中每個節點每時鐘周期只接收一個分組。
36.一種機器可讀介質，其上存儲了實施一種方法的多個可執行指令，該方法包括選擇在順時針環路結構和逆時針環路結構中的一個上從源節點傳輸分組到目的地節點；計算在所選擇的環路結構上從源節點到目的地節點之間的距離；確定計算出的距離是偶數還是奇數個時鐘周期；根據確定出的距離在第一時鐘周期內從源節點向目的地節點發送分組；以及根據所選擇的環路結構在第二時鐘周期內在目的地節點上接收分組。
37.權利要求36的機器可讀介質，其中第一時鐘周期包括偶數編號的時鐘周期和奇數編號的時鐘周期，第二時鐘周期包括偶數編號的時鐘周期和奇數編號的時鐘周期。
38.權利要求36的機器可讀介質，其中所述發送包括如果計算出的距離是偶數並且所選擇的環路結構是順時針環路結構，就在偶數編號的時鐘周期內發送分組；如果計算出的距離是偶數並且所選擇的環路結構是逆時針環路結構，就在奇數編號的時鐘周期內發送分組；如果計算出的距離是奇數並且所選擇的環路結構是順時針環路結構，就在奇數編號的時鐘周期內發送分組；以及如果計算出的距離是奇數並且所選擇的環路結構是逆時針環路結構，就在偶數編號的時鐘周期內發送分組。
39.權利要求36的機器可讀介質，其中所述接收包括如果所選擇的環路結構是順時針環路結構，在偶數編號的時鐘周期內接收分組；如果所選擇的環路結構是逆時針環路結構，在奇數編號的時鐘周期內接收分組。
40.一種機器可讀介質，其上存儲了實施一種方法的多個可執行指令，該方法包括在半導體晶片上，根據源節點和目的地節點之間的距離在一個時鐘周期內以第一方向在第一環路結構上從源節點向目的地節點發送分組或以與第一方向相反的第二方向在第二環路結構上從源節點向目的地節點發送分組。
41.權利要求40的機器可讀介質，還包括選擇以第一和第二方向中的哪一個發送分組；計算在所選擇的方向上源節點和目的地節點之間的距離；確定計算出的距離是偶數還是奇數個時鐘周期，其中所述選擇包括選擇要經過的節點較少的方向。
42.權利要求41的機器可讀介質，其中所述發送包括如果計算出的距離是偶數並且所選擇的方向是順時針，就在偶數編號的時鐘周期內發送分組；並且如果計算出的距離是偶數並且所選擇的方向是逆時針，就在奇數編號的時鐘周期內發送分組。
43.權利要求41的機器可讀介質，其中所述發送包括如果計算出的距離是奇數並且所選擇的方向是順時針，就在奇數編號的時鐘周期內發送分組；並且如果計算出的距離是奇數並且所選擇的方向是逆時針，就在偶數編號的時鐘周期內發送分組。
全文摘要
本發明的實施方案總體上涉及網絡中的數據流量控制，尤其是雙向環路互連中的分組流量控制。一種方法的一個實施方案包括根據在半導體晶片上的源節點和目的地節點之間的距離在一個時鐘周期內在這兩個節點之間在雙向環路互連上以第一方向或與第一方向相反的第二方向發送分組。一種設備的一個實施方案包括半導體晶片，它包括一個雙向環路互連和與該雙向環路互連耦合的多個節點，其中該雙向環路互連可以根據源節點和目的地節點之間的距離在一個時鐘周期內以順時針或逆時針方向傳輸分組。實施方案確保了在任意時鐘周期內單個分組能夠到達目的地節點。示例應用包括晶片多處理。
文檔編號H04L12/427GK1703025SQ20051007393
公開日2005年11月30日 申請日期2005年5月27日 優先權日2004年5月28日
發明者M·馬蒂納 申請人:英特爾公司