一种多端口数据调度算法

摘要:文章讨论了多端口数据传输情况下的一种高效的调度算法。该算法通过矩阵运算和时间片管理,在规定操作时钟周期内完成多端口数据传输调度,为各端口合理分配传输带宽,实现各端口数据的高效均衡传输。

关键词:多端口数据传输;调度算法;时间片;分配模块

中图分类号:TN915文献标识码:A

文章编号:1009-2374 (2010)24-0067-03

0引言

多端口数据调度是数据传输中经常遇到的情况,这种情况是指多端口数据在同一个物理接口或者同一个通道里传输时,需要完成的n选1的调度操作。这种多端口调度算法需要保证可预测的服务质量(Quality of Service,简称QoS),例如带宽、延时和延时抖动。多端口数据调度完成n选1的调度算法,并将所调度的数据发送给后级模块数据接收端。

1目前的调度算法分析

1.1目前的调度算法

目前常用的调度算法,主要是:

1.1.1轮转调度算法(Round-Robin,简称RR)RR算法将各个端口的数据按同一优先级进行轮转调度,各个端口得到均等的调度机会。

1.1.2固定优先级算法(Strict Priority,简称SP)SP算法存在于优先级队列(Priority Queuing,简称PQ)中。将分组分为4类,分别是:高优先级队列(top)、中优先级队列(middle)、正常优先级队列(normal)和低优先级队列(bottom),优先级依次降低。在调度操作时,高优先级的队列优先调度,低优先级的队列非优先调度。

1.1.3根据各个端口内缓存FIFO的数据水线的加权调度算法端口调度的结果是:水线高的端口优先得到调度,而水线低的端口则不能得到调度。目前的端口调度算法基本是通过比较器来实现,也就是通过比较运算出各个端口之间数据水线的高低,从而得到调度结果。

1.2目前的调度算法中存在几种不合理的情况

在实际应用中,如果调度操作不合理,将会造成各路数据传输的不合理:

1.2.1 串行调度操作的不合理调度操作与数据读写操作串行。这种情况下,每次数据读写操作之前都进行一次调度操作,那么无疑将占用数据带宽。如果调度周期过多(例如短报文操作),那么必将使带宽利用率大大降低。

1.2.2无权重调度算法的不合理无权重调度算法,例如RR调度算法,操作的不合理是显而易见的,当各个端口的数据流量不均衡时,它并没有给流量高的端口分配足够的带宽。

1.2.3有权重调度算法的不合理有权重调度算法,例如SP调度算法和数据水线的加权调度算法,不合理在于:各路的数据流量不均衡将会导致各个端口内的数据水线不同。如果单纯的通过以数据水线高低来进行调度,那么数据流量较小的端口,由于其数据水线较低,将长时间不能进行数据传输。这在多路数据传输中明显是不合理的。

2改进的调度算法

为了克服目前调度算法的不足,本文的改进算法采用矩阵运算快速产生调度结果,并采用时间片管理方式,为流量小的端口提供传输带宽保证。

2.1算法描述一些说明

2.1.1关于档位的说明

说明1:档位的判断

在本设计中,需要确定各个端口属于哪个档位。根据水线信号arb_wmark[n],确认该端口所在的档位。本设计将端口分为四个档位,分别对应arb_wmark[n][3:0]中的各位。本设计采用独热码形式设置arb_wmark[n][3:0],用于端口表征所处的档位。

说明2:档位的高低和最高档位

档位的高低顺序是:第3档位最高,第0档位最低。如果当前端口中有端口属于第3档位,则第3档位就被称为当前最高档位;如果当前端口中没有端口属于第3档位,而有端口属于第2档位,则第2档位就被称为当前最高档位。依此类推。

2.1.2关于时间片的说明本算法根据参考文献[4],应用其中的时间片调度的算法来满足低档位端口的数据传输需要,需要说明如下:

说明1:时间片计数器的初始值设置

本发明为每个档位设置一个时间片计数器,也就是4个时间片计数器,为这4个时间片计数器提供初始值。

例如,初始值序列为0,10,40,100。初始值0分配给最高档位的时间片计数器;10分配给第二高档位的计数器;依此类推。也就是说,如果第3档位为最高档位,那么其计数器的初始值就为0;如果第2档位为最高档位,那么其计数器的初始值就为0。

说明2:时间片计数器的计数

当一次端口调度操作结束时,如果某个端口被调度,那么这个端口所在档位的时间片计数器将被设置为初始值;如果某个端口没有被调度,同时,这个档位的时间片计数器不等于0,那么这个档位的时间片计数器将被减1。

2.1.3端口调度操作的原则说明

原则1:除了最高档位外,如果其他档位的时间片计数器都不为0,那么端口调度的结果一定是属于最高档位的端口。

原则2:除了最高档位外,如果存在其他一个档位的时间片计数器为0,那么端口调度的结果一定是属于这个档位的端口。

原则3:除了最高档位外,如果存在其他两个或者两个以上的档位的时间片计数器为0,那么端口调度的结果一定是属于其中较高档位的端口。例如,第3档位为最高档位,而第2档位和第3档位的时间片计数器都为0,那么调度的结果一定是属于第2档位的端口。

原则4:同档位的端口轮转调度。例如非最高档位的第2档位有两个端口:第n端口和第m端口,如果上次调度中,该档位的时间片计数器为0,那么调度的结果为第n端口。数次调度操作过后,该档位的时间片计数器又变为0,那么本次调度操作的结果为第m端口。

总之,当其他档位的时间片计数器都不为0,最高档位端口的优先级最高,它们被轮转调度;当其他档位的时间片计数器为0,这些档位的端口的优先级变为最高,按照档位高低分解进行响应。这样做的目的就是为了保证较低档位的端口也能得到定时的响应。

2.2端口调度模块

2.2.1 端口调度结构框图

端口调度模块可以分为两个部分:等待时间片分配模块和调度算法实现模块。

其中等待时间片分配模块在arb_grant信号驱动下,启动一次新的时间片计算:根据向量Cwmark(详见端口调度的算法描述部分)和arb_port[7:0]信号,进行各个档位的等待时间片计数。通过时间片计数器得到arb_pri[3:0]信号。arb_pri[3:0]表征四个档位中那个档位的操作请求的优先级最高。

调度算法实现模块在arb_grant信号驱动下,启动一起新的调度运算:将输入的arb_req、arb_wmark[N-1][3:0]、arb_strobe[N-1:0]进行矩阵运算,得到各个档位可能的调度结果。然后根据arb_pri[3:0]信号,挑选出处于最高优先级档位上的调度结果,作为最后的调度结果。

2.2.2端口调度矩阵运算输入的水线向量arb_wmark[N-1][3:0]记做wmark[N-1][3:0],并整理为式(1):

那么式(1)中的Iwmark0～Iwmark3向量就表示四个水线档位上,各有那些端口。

例如:就表示第0档位上有第1、3和4端口。

将Ing_strobe[N-1:0]和Ing_req[N-1:0]记做strobe

[N-1:0]和req[N-1:0],并做如下处理:

那么CwmarkM[N-1:0]表示在第M档位上,有那些端口可能被调度。

例如:就表示第3档位上有第1、3和4端口可能会被调度。

第M档位上可能被调度的多个端口中,最终哪个将被调度呢?根据调度原则,还需要满足以下两个条件:

(1) 该档位的优先级是否为最高,也就是arb_pri[M]是否为高电平;

(2) 该档位的某个端口应该是下一个轮转到的端口。

首先,需要确认目前第M档位是否为最高优先级的档位。例如,第2档位由于等待时间片用完,其优先级被提为最高,也就是arb_pri[2]为高电平,则提取Cwmrak2[N-1:0],记做Swmark[N-1:0]。

其次,如果上次的调度结果为wport[N-1:0],做如下处理:

从式(3)可见RwportM[N-1:0]向量是端口号向量wport[N-1:0]左移M位得到的。

最后,做如下矩阵乘法处理:

(4)

将Swmark[N-1:0]与Rwport的各个子向量进行矩阵乘,得到Gwport[N-1:0]。从0到N-1依次扫描Gwport[N-1:0]的各值,找到第一个非零的值,记下其序号M,则RwportM就是调度结果,其中非零项所对应的端口就是被调度端口。

2.3等待时间片分配模块的算法描述

设定arb_priM变量,用来表征第M档位上的时间片是否用完。如果arb_priM为高电平,表示时间片用完,该档位上的端口请求的优先级变为最高。arb_priM变量的算法如下:

每个档位都有一个计数器,初始值可设定;

如果本次调度结果所指示的端口不属于该档位,且该档位计数器的计数值不为零,则该档位计数器的计数值减1;

如果档位计数器的计数值减1操作后变为零,则表示该档位的时间片已经使用完,则arb_priM变量赋值为1;

如果arb_priM变量值为1,表示该档位上的端口请求的优先级变为最高。调度算法优先调度该档位上的端口。

如果该档位上的端口被调度,则将arb_priM变量值赋值为0,且将该档位计数器的计数值赋值为初始值。

在得到arb_priM结果后,按照如下约定的规则计算各个档位的优先级arb_pri[3:0]:

(1)一般情况下,第3档位为最高优先级,如果该档位存在可能响应的端口(Cwmark3[N-1:0]不等0),则其等待时间片计数器设置为0(arb_pri3为高电平),表示其不需要等待。

(2)如果两个档位的等待时间片都用完,那么就按照其原先的优先级进行响应。例如第2档位和第1档位的等待时间片都用完(arb_pri2和arb_pri1为高电平),那么优先响应第2档位的端口。

因此,arb_pri[3:0]的计算公式如式(5)

3结论

本文所描述的调度算法,在Xilinx公司的Virtex 5LXT FPGA芯片和Altera公司的Stratix II GX FPGA芯片上都得到实现。目前已经应用在某路由交换设备的16端口数据处理线卡中。该调度算法的存在如下优点:

3.1调度速度快

本算法采用矩阵运算的方法,在多个状态信号输入的情况下,只要经过4个时钟周期的运算,就可以得到调度结果。而且随着端口数目的增加,运算周期并没有相应增加。也就是说端口越多,该算法的优势越明显。

3.2调度算法可以保证各个端口的数据均衡

本调度算法采用优先级轮转和时间片抢占的调度方式。高水线的端口优先响应;相同水线的端口轮转响应;低水线的端口通过时间片抢占,也能保证一定的数据传输带宽。

参考文献

[1] Nong G,Hamdi M. On the provision of quality-of-service guarantees for input queued switches [J].IEEE Communications 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,2004

[4] da SILVA P P,PATON N W. A UML-based design environment for interactive applications[C].// Proceedings of the 2nd International Workshop on User Interfaces to Data Intensive Systems: UIDIS’01.Washington,DC:IEEE Computer Society,2001.