一種多端口數(shù)據(jù)調(diào)度算法

1、一種多端口數(shù)據(jù)調(diào)度算法    摘要:文章討論了多端口數(shù)據(jù)傳輸情況下的一種高效的調(diào)度算法。該算法通過矩陣運算和時間片管理,在規(guī)定操作時鐘周期內(nèi)完成多端口數(shù)據(jù)傳輸調(diào)度,為各端口合理分配傳輸帶寬,實現(xiàn)各端口數(shù)據(jù)的高效均衡傳輸。關(guān)鍵詞:本文來自： 駱駝?wù)撐亩喽丝跀?shù)據(jù)傳輸;調(diào)度算法;時間片;分配模塊0引言多端口數(shù)據(jù)調(diào)度是數(shù)據(jù)傳輸中經(jīng)常遇到的情況,這種情況是指多端口數(shù)據(jù)在同一個物理接口或者同一個通道里傳輸時,需要完成的n選1的調(diào)度操作。這種多端口調(diào)度算法需要保證可預(yù)測的服務(wù)質(zhì)量(Quality of Service,簡稱QoS),例如帶寬、延時和延時抖動。多端口數(shù)據(jù)

2、調(diào)度完成n選1的調(diào)度算法,并將所調(diào)度的數(shù)據(jù)發(fā)送給后級模塊數(shù)據(jù)接收端。1目前的調(diào)度算法分析1.1目前的調(diào)度算法目前常用的調(diào)度算法,主要是:1.1.1輪轉(zhuǎn)調(diào)度算法(Round-Robin,簡稱RR)RR算法將各個端口的數(shù)據(jù)按同一優(yōu)先級進行輪轉(zhuǎn)調(diào)度,各個端口得到均等的調(diào)度機會。1.1.2固定優(yōu)先級算法(Strict Priority,簡稱SP)SP算法存在于優(yōu)先級隊列(Priority Queuing,簡稱PQ)中。將分組分為4類,分別是:高優(yōu)先級隊列(top)、中優(yōu)先級隊列(middle)、正常優(yōu)先級隊列(normal)和低優(yōu)先級隊列(bottom),優(yōu)先級依次降低。在調(diào)度操作時,高優(yōu)先級的隊列優(yōu)

3、先調(diào)度,低優(yōu)先級的隊列非優(yōu)先調(diào)度。1.1.3根據(jù)各個端口內(nèi)緩存FIFO的數(shù)據(jù)水線的加權(quán)調(diào)度算法端口調(diào)度的結(jié)果是:水線高的端口優(yōu)先得到調(diào)度,而水線低的端口則不能得到調(diào)度。目前的端口調(diào)度算法基本是通過比較器來實現(xiàn),也就是通過比較運算出各個端口之間數(shù)據(jù)水線的高低,從而得到調(diào)度結(jié)果。1.2目前的調(diào)度算法中存在幾種不合理的情況在實際應(yīng)用中,如果調(diào)度操作不合理,將會造成各路數(shù)據(jù)傳輸?shù)牟缓侠?1.2.1 串行調(diào)度操作的不合理調(diào)度操作與數(shù)據(jù)讀寫操作串行。這種情況下,每次數(shù)據(jù)讀寫操作之前都進行一次調(diào)度操作,那么無疑將占用數(shù)據(jù)帶寬。如果調(diào)度周期過多(例如短報文操作),那么必將使帶寬利用率大大降低。1.2.2無權(quán)重

4、調(diào)度算法的不合理無權(quán)重調(diào)度算法,例如RR調(diào)度算法,操作的不合理是顯而易見的,當各個端口的數(shù)據(jù)流量不均衡時,它并沒有給流量高的端口分配足夠的帶寬。1.2.3有權(quán)重調(diào)度算法的不合理有權(quán)重調(diào)度算法,例如SP調(diào)度算法和數(shù)據(jù)水線的加權(quán)調(diào)度算法,不合理在于:各路的數(shù)據(jù)流量不均衡將會導(dǎo)致各個端口內(nèi)的數(shù)據(jù)水線不同。如果單純的通過以數(shù)據(jù)水線高低來進行調(diào)度,那么數(shù)據(jù)流量較小的端口,由于其數(shù)據(jù)水線較低,將長時間不能進行數(shù)據(jù)傳輸。這在多路數(shù)據(jù)傳輸中明顯是不合理的。2改進的調(diào)度算法為了克服目前調(diào)度算法的不足,本文的改進算法采用矩陣運算快速產(chǎn)生調(diào)度結(jié)果,并采用時間片管理方式,為流量小的端口提供傳輸帶寬保證。2.1算法描述

5、一些說明2.1.1關(guān)于檔位的說明說明1:檔位的判斷在本設(shè)計中,需要確定各個端口屬于哪個檔位。根據(jù)水線信號arb_wmarkn,確認該端口所在的檔位。本設(shè)計將端口分為四個檔位,分別對應(yīng)arb_wmarkn3:0中的各位。本設(shè)計采用獨熱碼形式設(shè)置arb_wmarkn3:0,用于端口表征所處的檔位。說明2:檔位的高低和最高檔位檔位的高低順序是:第3檔位最高,第0檔位最低。如果當前端口中有端口屬于第3檔位,則第3檔位就被稱為當前最高檔位;如果當前端口中沒有端口屬于第3檔位,而有端口屬于第2檔位,則第2檔位就被稱為當前最高檔位。依此類推。2.1.2關(guān)于時間片的說明本算法根據(jù)參考文獻4,應(yīng)用其中的時間片調(diào)

6、度的算法來滿足低檔位端口的數(shù)據(jù)傳輸需要,需要說明如下:說明1:時間片計數(shù)器的初始值設(shè)置本發(fā)明為每個檔位設(shè)置一個時間片計數(shù)器,也就是4個時間片計數(shù)器,為這4個時間片計數(shù)器提供初始值。例如,初始值序列為0,10,40,100。初始值0分配給最高檔位的時間片計數(shù)器;10分配給第二高檔位的計數(shù)器;依此類推。也就是說,如果第3檔位為最高檔位,那么其計數(shù)器的初始值就為0;如果第2檔位為最高檔位,那么其計數(shù)器的初始值就為0。說明2:時間片計數(shù)器的計數(shù)當一次端口調(diào)度操作結(jié)束時,如果某個端口被調(diào)度,那么這個端口所在檔位的時間片計數(shù)器將被設(shè)置為初始值;如果某個端口沒有被調(diào)度,同時,這個檔位的時間片計數(shù)器不等于0,

7、那么這個檔位的時間片計數(shù)器將被減1。2.1.3端口調(diào)度操作的原則說明原則1:除了最高檔位外,如果其他檔位的時間片計數(shù)器都不為0,那么端口調(diào)度的結(jié)果一定是屬于最高檔位的端口。原則2:除了最高檔位外,如果存在其他一個檔位的時間片計數(shù)器為0,那么端口調(diào)度的結(jié)果一定是屬于這個檔位的端口。原則3:除了最高檔位外,如果存在其他兩個或者兩個以上的檔位的時間片計數(shù)器為0,那么端口調(diào)度的結(jié)果一定是屬于其中較高檔位的端口。例如,第3檔位為最高檔位,而第2檔位和第3檔位的時間片計數(shù)器都為0,那么調(diào)度的結(jié)果一定是屬于第2檔位的端口。原則4:同檔位的端口輪轉(zhuǎn)調(diào)度。例如非最高檔位的第2檔位有兩個端口:第n端口和第m端口,

8、如果上次調(diào)度中,該檔位的時間片計數(shù)器為0,那么調(diào)度的結(jié)果為第n端口。數(shù)次調(diào)度操作過后,該檔位的時間片計數(shù)器又變?yōu)?,那么本次調(diào)度操作的結(jié)果為第m端口?？傊?當其他檔位的時間片計數(shù)器都不為0,最高檔位端口的優(yōu)先級最高,它們被輪轉(zhuǎn)調(diào)度;當其他檔位的時間片計數(shù)器為0,這些檔位的端口的優(yōu)先級變?yōu)樽罡?按照檔位高低分解進行響應(yīng)。這樣做的目的就是為了保證較低檔位的端口也能得到定時的響應(yīng)。2.2端口調(diào)度模塊2.2.1 端口調(diào)度結(jié)構(gòu)框圖端口調(diào)度模塊可以分為兩個部分:等待時間片分配模塊和調(diào)度算法實現(xiàn)模塊。其中等待時間片分配模塊在arb_grant信號驅(qū)動下,啟動一次新的時間片計算:根據(jù)向量Cwmark(詳見端口

9、調(diào)度的算法描述部分)和arb_port7:0信號,進行各個檔位的等待時間片計數(shù)。通過時間片計數(shù)器得到arb_pri3:0信號。arb_pri3:0表征四個檔位中那個檔位的操作請求的優(yōu)先級最高。調(diào)度算法實現(xiàn)模塊在arb_grant信號驅(qū)動下,啟動一起新的調(diào)度運算:將輸入的arb_req、arb_wmarkN-13:0、arb_strobeN-1:0進行矩陣運算,得到各個檔位可能的調(diào)度結(jié)果。然后根據(jù)arb_pri3:0信號,挑選出處于最高優(yōu)先級檔位上的調(diào)度結(jié)果,作為最后的調(diào)度結(jié)果。2.2.2端口調(diào)度矩陣運算輸入的水線向量arb_wmarkN-13:0記做wmarkN-13:0,并整理為式(1):&

10、#160;   那么式(1)中的Iwmark0Iwmark3向量就表示四個水線檔位上,各有那些端口。例如:就表示第0檔位上有第1、3和4端口。將Ing_strobeN-1:0和Ing_reqN-1:0記做strobe N-1:0和reqN-1:0,并做如下處理:                         

11、0;   那么CwmarkMN-1:0表示在第M檔位上,有那些端口可能被調(diào)度。例如:就表示第3檔位上有第1、3和4端口可能會被調(diào)度。第M檔位上可能被調(diào)度的多個端口中,最終哪個將被調(diào)度呢?根據(jù)調(diào)度原則,還需要滿足以下兩個條件:(1) 該檔位的優(yōu)先級是否為最高,也就是arb_priM是否為高電平;(2) 該檔位的某個端口應(yīng)該是下一個輪轉(zhuǎn)到的端口。首先,需要確認目前第M檔位是否為最高優(yōu)先級的檔位。例如,第2檔位由于等待時間片用完,其優(yōu)先級被提為最高,也就是arb_pri2為高電平,則提取Cwmrak2N-1:0,記做SwmarkN-1:0。其次,如果上次的調(diào)度結(jié)果為wportN-

12、1:0,做如下處理:從式(3)可見RwportMN-1:0向量是端口號向量wportN-1:0左移M位得到的。最后,做如下矩陣乘法處理:(4)將SwmarkN-1:0與Rwport的各個子向量進行矩陣乘,得到GwportN-1:0。從0到N-1依次掃描GwportN-1:0的各值,找到第一個非零的值,記下其序號M,則RwportM就是調(diào)度結(jié)果,其中非零項所對應(yīng)的端口就是被調(diào)度端口。2.3等待時間片分配模塊的算法描述設(shè)定arb_priM變量,用來表征第M檔位上的時間片是否用完。如果arb_priM為高電平,表示時間片用完,該檔位上的端口請求的優(yōu)先級變?yōu)樽罡?。arb_priM變量的算法如下:每個檔

13、位都有一個計數(shù)器,初始值可設(shè)定;如果本次調(diào)度結(jié)果所指示的端口不屬于該檔位,且該檔位計數(shù)器的計數(shù)值不為零,則該檔位計數(shù)器的計數(shù)值減1;如果檔位計數(shù)器的計數(shù)值減1操作后變?yōu)榱?則表示該檔位的時間片已經(jīng)使用完,則arb_priM變量賦值為1;如果arb_priM變量值為1,表示該檔位上的端口請求的優(yōu)先級變?yōu)樽罡摺Ｕ{(diào)度算法優(yōu)先調(diào)度該檔位上的端口。如果該檔位上的端口被調(diào)度,則將arb_priM變量值賦值為0,且將該檔位計數(shù)器的計數(shù)值賦值為初始值。在得到arb_priM結(jié)果后,按照如下約定的規(guī)則計算各個檔位的優(yōu)先級arb_pri3:0:(1)一般情況下,第3檔位為最高優(yōu)先級,如果該檔位存在可能響應(yīng)的端口(

14、Cwmark3N-1:0不等0),則其等待時間片計數(shù)器設(shè)置為0(arb_pri3為高電平),表示其不需要等待。(2)如果兩個檔位的等待時間片都用完,那么就按照其原先的優(yōu)先級進行響應(yīng)。例如第2檔位和第1檔位的等待時間片都用完(arb_pri2和arb_pri1為高電平),那么優(yōu)先響應(yīng)第2檔位的端口。因此,arb_pri3:0的計算公式如式(5)3結(jié)論本文所描述的調(diào)度算法,在Xilinx公司的Virtex 5LXT FPGA芯片和Altera公司的Stratix II GX FPGA芯片上都得到實現(xiàn)。目前已經(jīng)應(yīng)用在某路由交換設(shè)備的16端口數(shù)據(jù)處理線卡中。該調(diào)度算法的存在如下優(yōu)點:3.1調(diào)度速度快本

15、算法采用矩陣運算的方法,在多個狀態(tài)信號輸入的情況下,只要經(jīng)過4個時鐘周期的運算,就可以得到調(diào)度結(jié)果。而且隨著端口數(shù)目的增加,運算周期并沒有相應(yīng)增加。也就是說端口越多,該算法的優(yōu)勢越明顯。3.2調(diào)度算法可以保證各個端口的數(shù)據(jù)均衡本調(diào)度算法采用優(yōu)先級輪轉(zhuǎn)和時間片搶占的調(diào)度方式。高水線的端口優(yōu)先響應(yīng);相同水線的端口輪轉(zhuǎn)響應(yīng);低水線的端口通過時間片搶占,也能保證一定的數(shù)據(jù)傳輸帶寬。參考文獻1 Nong G,Hamdi M. On the provision of quality-of-service guarantees for input queued switches J.IEEE Communi

16、cations Magazine,2000,38(12).2 Li Y,Panwar S,Chao HJ. On the performance of a dual Round-Robin Switch J.In:Ammar M,ed.Proc.Of the IEEE INFOCOM.Anchorage:IEEE Communications Society,2001.3 Tim Szigeti,Christin a Hatting h. End-to-End QoS Network Design M.Cisco,20044 da SILVA P P,PATON N W. A UML-based design envir