輸入緩衝分布式調度的交叉開關交換電路的製作方法

2023-05-23 06:19:56

專利名稱：輸入緩衝分布式調度的交叉開關交換電路的製作方法
技術領域：
本實用新型涉及數據交換——一種輸入緩衝分布式交叉開關結構的數據交換電路，這種電路可用作交換機、路由器和集線器的核心電路部件，也可用作超級計算機中處理器互連的路由結構。
技術背景流行的商業交換機和路由器經常採用輸出緩衝輸出調度的總線結構或交叉開關結構，保證輸入數據能安全可靠傳輸到輸出緩衝區，在緩衝區不溢出的情況下不發生丟包現象。由於這種結構的輸出埠的緩衝器至少需要相當於所有輸入埠速率總和的緩衝速度，當輸入埠較多時這種結構的成本非常高。為了降低成本同時又能保證可靠性，二十世紀九十年代以後提出了一系列基於輸入輸出同速度的調度算法，如PIM(並行迭代匹配)、iSLIP(Iterative Round Robin Matching with Slip)、iLQF(iterative Longest Queue First)、iOCF(iterative Oldest CellFirst)、iLPF(iterative Longest Port First)、TSA(Two Step Arbiter)、Shakeup、DRRM(Dual Round-robin Matching)、Parallel Polling、MNCM(maximum node containing matching)等調度算法，這些算法的時間複雜度在O(NlogN)及以上，調度延時大，而且這些算法硬體實現較複雜，成本較高。虛電路交換在建立鏈路後數據傳輸非常快，但建立鏈路和撤銷鏈路的時間都很長，鏈路利用率低。

發明內容
本實用新型的目的是解決快速調度、時鐘轉換、幀的流水傳輸和交換設備級聯擴展等問題，同時使硬體成本保持非常低的水平，而提供一種輸入緩衝分布式調度的交叉開關交換電路。


圖1是四輸入埠四輸出埠的輸入緩衝分布式調度的交叉開關結構交換電路。
本實用新型，是對虛電路交換電路和輸入緩衝交換電路的改進。該電路實現數據交換功能，利用部分單元(RAM塊)實現雙時鐘同步FIFO(先進先出)緩衝器，對輸入數據進行緩衝；用多路選擇器實現交叉開關交換。每個輸入埠的數據進入雙時鐘同步FIFO進行緩衝，同時完成時鐘轉換；解碼器根據幀頭進行埠解碼，向輸出埠發送輸出埠使用請求；輸出埠調度部件(仲裁器)根據輸入埠來的請求進行仲裁，確定哪個輸入埠得到響應，選通多路開關的對應開關，並向輸入埠回傳響應信息；得到響應的輸入埠向數據總線發送數據，數據經過連通的交叉開關到達相應的輸出埠，完成一次數據傳輸。在整個傳輸過程中，由控制器進行流量控制。
4輸入埠4輸出埠的交換電路如附圖1所示。在圖1中，左邊的輸入數據和信號來自於輸入埠，右邊的輸出數據和信號發送到輸出埠，圖中的數字分別代表與各個埠相關的組件。
圖1中，具有四組電路結構，每組具有先進先出緩衝器(FIFO)1、解碼器2、控制器3以及多路開關4、仲裁器5和響應及流控電路6。其中，先進先出緩衝器1輸出分別連接於解碼器2和多路開關4，解碼器2輸出分別連接於控制器3和仲裁器5，仲裁器5連接於多路開關4和響應及流控電路6，響應及流控電路6輸出連接於控制器3，控制器3輸出連接於先進先出緩衝器1。
用這種電路交換數據解決了以下難題降低設備成本、快速調度、時鐘切換、幀的流水傳輸和交換設備級聯擴展。一個有N個輸入埠的交換社備有N個不同的輸入時鐘，而一個調度部件只能依據一個時鐘進行操作，因此必須進行時鐘切換。本實用新型採用雙時鐘同步先進先出存儲器作緩衝器，緩衝器的寫時鐘為輸入埠時鐘，讀時鐘為板上全局時鐘，這樣就解決了時鐘隔離與切換。採用先進先出存儲器實現了輸入緩衝功能，並利用存儲器的使用情況對輸入埠進行水線流量控制(當存儲器使用情況超過某個上限預定值時要求輸入埠停止發送，當低於某個下限設定值時可以繼續發送，在上下限之間的區間內能否發送與進入此區間前的狀態一致)。這種流量控制機制比設備間採用異步應答方式的交換機提高了鏈路的利用率和加快傳輸速度。由於輸入數據從寫入FIFO到從FIFO讀埠看到數據寫入只需要三個時鐘周期(即當FIFO中沒有數據時從寫入新數據到立即讀出只需要四個時鐘周期)，這樣在傳輸時比虛電路僅增加極小的延時，但獲得了便利的控制，實現了虛切入(CutThrough)傳輸方式，實現了幀的流水傳輸，同時使交換機級聯擴展非常容易。為了減小調度時間，本實用新型採用分布式仲裁部件進行調度。為了進一步加快調度速度，本實用新型在一個時鐘周期內完成帶初始化值的輪詢(Round Robin)調度(見附表2)，大大縮短了交換延時，極大提高了幀交換效率。由於每個輸入埠只有一個隊列作緩衝，輸出沒有緩衝，雖然共有N個調度器，但每個調度器佔用的邏輯很少，因此硬體成本非常低。
附表二帶初始化值的輪詢(Round Robin)調度算法的Verilog語言描述input[N-1:0] request_i；//N個輸入埠對第i個輸出埠的使用請求，輸入信號output[N-1:0] acknowledge_i；dp///第i個輸出埠對N個輸入埠請求的響應，輸出信號reg[N-1:0] state；//當前狀態，用寄存器存儲always @(posedge clock) //在全局時鐘的上升沿case(state)沒有埠進行傳輸beginif(request_i[i+1]＝＝1) //第i+1個輸入埠有請求beginstate＝第i+1個輸入埠與第i個輸出埠進行傳輸；acknowledge_i＝1＜＜(i+1)；//給第i+1個輸入埠響應endelse if(request_i[i+2]＝＝1) //第i+2個輸入埠有請求 beginstate＝第i+2個輸入埠與第i個輸出埠進行傳輸；acknowledge_i＝1＜＜(i+2)；enddp///各埠的優先級別按i+1、i+2、i+3、……、N-1、0、//1、2、……、i-1、i依次降低else if(request_i[i-1]＝＝1) //第i-1個輸入埠有請求 beginstate＝第i-1個輸入埠與第i個輸出埠進行傳輸；acknowledge_i＝1＜＜(i-1)；endelse if(request_i[i]＝＝1) //第i個輸入埠有請求beginstate＝第i個輸入埠與第i個輸出埠進行傳輸；acknowledge_i＝1＜＜i；end end第0個輸入埠與第i個輸出埠進行傳輸beginif(request_i[0]＝＝0)//埠0撤銷請求begin if(request_i[1]＝＝1) begindp/　　state＝第1個輸入埠與第i個輸出埠進行傳輸；　　acknowledge_i＝1＜＜1；　　 end　　 else if(request_i[2]＝＝1)　　 begin　　state＝第2個輸入埠與第i個輸出埠進行傳輸；　　acknowledge_i＝1＜＜2；　　 end　　 else if(request_i[N-1]＝＝1)　　 begin　　state＝第N-1個輸入埠與第i個輸出埠進行傳輸；　　acknowledge_i＝1＜＜(N-1)；　　 end　　 else　　 begin　　 state＝沒有埠進行傳輸；　　 acknowledge_i＝0；　　 enddp/endend第N-1個輸入埠與第i個輸出埠進行傳輸beginif(request_i[N-1]＝＝0)//埠N-1撤銷請求begin if(request_i[0]＝＝1) begin state＝第0個輸入埠與第i個輸出埠進行傳輸； acknowledge_i＝1； end else if(request_i[1]＝＝1) begin state＝第1個輸入埠與第i個輸出埠進行傳輸； acknowledge_i＝1＜＜1； end else if(request_i[N-2]＝＝1)dp/ beginstate＝第N-2個輸入埠與第i個輸出埠進行傳輸；acknowledge_i＝1＜＜(N-2)； end else begin state＝沒有埠進行傳輸；acknowledge_i＝0； end end endendcase………………………………
具體實施方式
用FPGA晶片Altera APEX20K200E實現4輸入埠4輸出埠交叉開關交換機，交換機板上全局時鐘為33Mhz(時鐘周期為30納秒)時，完成一次調度的時間為7.8納秒，在沒有阻塞的情況下幀從進入交換晶片到出來交換晶片的時間為210納秒(7個時鐘周期)，遠小於商業交換機的延時。
…本實用新型涉及一種輸入緩衝分布式調度的交叉開關結構交換電路，是一種交叉開關結構的電路交換單位，這種電路可用作交換機、路由器和集線器的核心電路部件，也可用作超級計算機中處理器互連的路由設備。該電路實現數據交換功能，利用部分單元實現雙時鐘同步先進先出存儲器，對輸入數據進行緩衝，實現水線流量控制；用多路選擇器實現交叉開關交換。每個輸入埠根據幀頭進行埠解碼，向輸出埠發送鏈路使用請求，輸出埠調度部件根據輸入埠來的請求進行仲裁(在一個時鐘周期內實現帶初始化值的輪循調度)，得到響應的輸入埠與相應的輸出埠建立鏈路，完成數據的傳輸。
權利要求1.一種輸入緩衝分布式調度的交叉開關結構交換電路，其特徵是採用雙時鐘先進先出存儲器作為輸入緩衝器，採用水線流量控制，採用分布式調度並在一個時鐘周期內完成一次帶初始化值的輪循交換調度。
2.根據權利要求1所述的輸入緩衝分布式調度的交叉開關結構交換電路，調度算法的硬體實現，即在一個時鐘周期內完成帶初始化值的輪循調度的硬體實現。
3.根據權利要求1所述的輸入緩衝分布式調度的交叉開關結構交換電路，由先進先出緩衝器(FIFO)1、解碼器2、控制器3以及多路開關4、仲裁器5和響應及流控電路6組成，其特徵在於，先進先出緩衝器1輸出分別連接於解碼器2和多路開關4，解碼器2輸出分別連接於控制器3和仲裁器5，仲裁器5連接於多路開關4和響應及流控電路6，響應及流控電路6輸出連接於控制器3，控制器3輸出連接於先進先出緩衝器1。
專利摘要本實用新型涉及一種輸入緩衝分布式調度的交叉開關結構交換電路，由先進先出緩衝器(FIFO)1、解碼器2、控制器3以及多路開關4、仲裁器5和響應及流控電路6組成。是一種交叉開關結構的電路交換單位，這種電路可用作交換機、路由器和集線器的核心電路部件，也可用作超級計算機中處理器互連的路由設備。該電路實現數據交換功能，利用部分單元實現雙時鐘同步先進先出存儲器，對輸入數據進行緩衝，實現水線流量控制；用多路選擇器實現交叉開關交換。每個輸入埠根據幀頭進行埠解碼，向輸出埠發送鏈路使用請求，輸出埠調度部件根據輸入埠來的請求進行仲裁，得到響應的輸入埠與相應的輸出埠建立鏈路，完成數據的傳輸。
文檔編號H04L12/24GK2650400SQ200320100659
公開日2004年10月20日 申請日期2003年11月19日 優先權日2003年11月19日
發明者胡明昌, 史崗, 唐志敏 申請人:中國科學院計算技術研究所