输入缓存调度算法的仿真与实现范文

《空间电子技术杂志》2015年第一期

1一种改进的串行调度算法

1．1算法思想由于卫星信道具有时延长、星上芯片资源有限等特点，在星上交换机中要求输入缓存调度算法具有较好的调度时延及丢失率等性能。文章采用串行调度的思想，对原有串行调度算法进行改进，在对端口仲裁时，改进算法优先选择对收到请求数目最少的输出端口进行仲裁，较晚仲裁收到请求数目较多的端口，这样可以增加每个时隙内匹配更多输入/输出端口的可能性，从而改善星上交换机性能。同时每个端口在仲裁时采用了轮询指针的方法，该指针在每次成功匹配后都进行更新，这样能够保证算法的公平性。改进的输入缓存调度算法包括以下几个步骤:首先，各个输入端口同时向它的队列中信元可能到达的输出端口发送调度请求信号。其次，所有收到请求的输出端口采用串行的方式进行仲裁。仲裁所有收到请求的输出端口时，选择收到请求数目较少的输出端口优先进行仲裁，较晚仲裁请求数目较多的输出端口。当每个输出端口进行仲裁时，可从轮询指针目前指示的输入端口开始，选择出一个尚未匹配的输入端口，然后通知各个输入端口其请求是否被准许，同时更新该输出端口的轮询指针。当完成一个输出端口的仲裁后，可以重新开始对下一个输出端口的仲裁，最终轮询完所有的输出端口。由于很难通过建立数学模型的方法来比较各种不同调度算法的性能，因此本文在对改进算法进行性能分析、举例说明的基础上，利用仿真的方法来比较各算法性能，最后通过FPGA设计对其可行性进行验证。

1．2性能分析带宽利用率、调度时延及公平性是衡量Crossbar调度算法性能的几个主要指标。带宽利用率是指平均每次调度匹配成功的输入、输出端口数目与Crossbar开关总端口数目之比。当交换结构总端口数目一定时，如果每次调度匹配成功的输入、输出端口数目越多，那么该算法的带宽利用率也就越高，同时若信元在队列中等候的时间越短，交换结构中信元平均延时也就越短。因此当缓存队列有限时，增加每次匹配的端口数目也可以降低交换结构中信元的丢失率。(1)不同仲裁顺序对Crossbar交换结构带宽利用率的影响由于采用不同的仲裁顺序，交换结构可成功匹配输入、输出端口的数目也不同，这里首先分析并比较不同的仲裁顺序对成功匹配端口数目产生的影响。这里假设有两个输出端口a和b，各端口分别收到m1、m2个输入端口的请求，并且m1＞m2，当首先匹配输出端口b时，输出端口a成功匹配的概率将大于先匹配输出端口a时输出端口b成功匹配的概率。证明:(a)当两个输出端口收到的请求中，所有输入端口都没有重复时，那么按照这两种顺序成功匹配数目相同。(b)当两个输出端口收到的请求中，有m个重复的输入端口(m＜m1，m2)若优先匹配输出端口选择的输入端口不在这m个端口中，仲裁顺序不会影响成功匹配端口的数目，因此这里主要考虑优先匹配输出端口在m个输入端口中选择输入端口的情况。当优先匹配输出端口a时，以的概率在m/m1个端口中选择输入端口;其次匹配输出端口b时，该输出端口可选择输入端口的数目变为m2－1，那么该情况下输出端口成功匹配的概率是。综上所述，优先选择仲裁收到请求数目较少的输出端口可以增加成功匹配端口数目的概率，进而增加了提高Crossbar交换结构带宽利用率的可能性。(2)比较keepfull过程下信元的最大等待时延keepfull到达过程是指在任何时刻，任何VOQ队列都非空，这种情况下原有串行调度算法中缓存区信元在VOQ队头等待被交换的最大延时为N2，而在改进输入缓存调度算法中，缓存区信元在队头等待被交换的最大延时为N。证明:假设缓存区中某个信元在时刻t成为某队列的队头(HeadOfLine)信元:(a)那么根据原算法的思想，在t时刻后的N2次匹配中，必然会有N次匹配先从端口b开始进行仲裁;由于该算法中轮询指针仅在首次匹配后修改，那么在之后N次仲裁中，输出端口b的轮询指针必然会有一次等于a，因此，在t时刻后的N2个时隙内该信元必然会被交换到输出端口b。(b)根据改进算法的思想，当keepfull到达过程时，该算法可以得到完全匹配。这是因为改进算法在每次匹配成功后都需要更新该输出端口处得的轮询指针，这样可保证各个输出端口处的轮询指针必然不同。这种情况下各个输出端口收到输入端口的请求数目都是N，而每次匹配的顺序不会改变，那么在t时刻后的N个时隙内，输出端口的轮询指针必然会有一次等于a，因此，在t时刻后的N个时隙内该信元必然会被交换到输出端口b。证毕。综上所述，本文提出的改进输入串行调度算法优先匹配选择范围较小的输出端口，较晚匹配选择范围较大的输出端口，这样相比收到请求少的输出端口，成功匹配的概率比较大。因此，改进输入串行调度算法在每个信元时隙内可以比原算法获得更多的成果匹配数目，同时降低了调度时延、丢失率等指标，也可以更好地满足卫星交换的需要。另一方面，改进算法每次成功匹配后都会更新输出端口处的轮询指针，这样能够保证算法的公平性。

1．3举例说明下面以4×4的交换单元为例进行对原有算法和改进算法进行说明:图1给出了一个在4端换开关上分别使用输出串行调度算法和改进算法的例子。某时刻各输入端口的请求和调度器的状态分别如图1中(a)和(b)所示。根据原有输出串行调度算法，从输出端口1开始，按照1、2、3、0的顺序依次对每个输出端口进行仲裁。首先对输出端口1进行匹配，根据轮询指针的优先级选择了输入端口1;接着输出端口2进行仲裁，由于该端口只收到输入端口1的一个请求，而该输入端口又已经被匹配，因此在该时隙里输出端口2无法得到匹配;同理对3、0端口分别匹配，最终得到如图1中(c)所示的结果。而该二分图可以达到如图1中(d)所示的最大匹配。在改进的串行调度算法中，收到请求数目最少的输出端口优先仲裁，即按照输出端口2、0、3、1的顺序进行仲裁，对每个输出端口仲裁时仍然按照轮询(Round-Robin)指针的方法，每个端口轮询指针的状态依然如图1中(b)所示。该算法首先为输出端口2选择输入端口，由于只收到输入端口1的请求，所以选择输入端口1，同时该输出端口的轮询指针指向输入端口2;接着为输出端口0、3进行匹配，为保证公平性，每个端口得到匹配后都要更新轮询指针;最后匹配输出端口1时，虽然已有3个输入端口被匹配，但由于该输出端口收到的请求数目最多，因此在这种情况下，该端口获得匹配的可能性仍然比较大。在这个例子中，输出端口1仍然得到了匹配。图1中(e)给出了改进算法调度的结果。从分析的结果可知，在这种情况下，采用原有的输出串行调度算法得到的匹配数目只是最大匹配的一半;而采用改进算法得到的匹配数目和最大匹配相同。这是因为根据收到请求的数目来安排仲裁输出端口的顺序，保证了选择范围较小的输出端口先仲裁，而选择范围较大的输出端口即使较晚仲裁，较之收到请求少的输出端口，得到匹配的概率也会较大。这种算法不一定达到最大匹配，但大大增加了接近最大匹配的概率。

2OPNET仿真及比较

本节利用OPNET软件对改进的输入缓存调度算法及其他典型算法进行仿真并进行性能比较。iS-LIP算法是目前比较常用的一种输入缓存调度算法，该算法通常少于log2N次迭代后收敛［14］，也具有一定的代表性。因此，本节通过OPNET构造一个16×16的Crossbar交换结构仿真模型，在该模型中对4-SLIP算法、原有串行调度算法及改进的串行调度算法进行仿真，并根据仿真结果来分析并比较这三种算法在高负载，突发长度为32情况下的平均调度时延，同时在缓存队列有限的情况下，比较改进输入缓存算法与原串行调度算法的丢失率。在图2中，当信元突发到达时，改进算法的平均调度时延明显小于4-SLIP算法和原输出串行调度算法。这是由于串行迭代调度算法能够避免并行迭代算法中的同步现象，这样可以增加每次调度中成功匹配的数目，同时也就降低了平均时延;因此仿真中的两种串行调度算法时延都小于4-SLIP算法，而本文提出的改进串行调度算法在原串行调度的基础优先仲裁请求数目较少的输出端口，使调度中成功匹配的数目增加，因此改进算法的平均时延低于原串行调度算法;而改进串行调度算法在各输出端口成功匹配后更新轮询指针，也保证了算法的公平性。从图3中可看出，当负载分别为0．65和0．95、突发长度为10时，不同VOQ队列长度下改进串行调度算法带来的信元丢失率小于输出串行调度算法;当负载较低(0．65)时，两种算法的丢失率均小于负载较高(0．95)的情况;另外增加缓存区的大小可明显减少低负载(0．65)下信元的丢失率，但是要减少高负载(0．95)下到达信元的丢失率，缓存区的设置需要很大。

3硬件实现的分析与仿真

3．1调度模块的硬件设计框图图4给出了基于星上交换的输入缓存调度算法调度模块的实现框图，该调度模块主要由时序产生、指针产生、请求处理、仲裁和输出控制等模块组成。时序产生模块根据改进算法的要求产生当前需要轮询的输出端口号，同时由R－R指针产生模块产生该端口处的轮询指针;仲裁模块根据请求及当前轮询指针对该输出端口进行仲裁，并将仲裁结果交给输出控制模块，同时更新轮询指针;当输出控制模块收到所有输出端口的仲裁结果后，将每个输入端口匹配的结果分别送给各输入端口及交换模块，用于下个时隙信元的交换。

3．2工作频率与端口速率的关系本文提出的星上输入缓存调度算法完成每次调度共需要N+1个时钟节拍，调度模块需要在交换一个信元的时间内计算出下个时隙的端口匹配情况，因此调度的总时间应该小于交换一个信元的时间。假设交换机的端口速率为Vbps，调度模块芯片的工作频率为MHz，端口数目为N。由于交换机内部采用64字节的定长交换，每秒钟到达的信元数目为V/(64*8)，那么信元到达的周期为T=(64×8)/V秒，也就是说要在时间T内完成一个信元的交换;另一方面，平均每次调度需要N+1个时钟节拍，那么调度模块完成一次调度的时间为(N+1)/Ms。

3．3FPGA仿真结果星上输入缓存调度算法FPGA仿真的输入条件为每个输入端口的请求，如果该输入端口有信元发送到第j个输出端口，那么该输入端口的第j位设为1;通过仿真应该得到的是每个输入端口的匹配情况，如果该输入端口与第j个输出端口匹配，那么发往该输入端口的结果中第j位为1。每个输出端口处的轮询指针根据每次匹配的结果来更新。本文通过编写输入端口请求消息作为激励源，并对比VHDL仿真的结果和按照算法应得到的匹配结果。如果仿真得到的匹配结果与本文提出的改进算法期望得到的结果相同，说明该算法是可实现的。仿真分为功能仿真和时序仿真，前者验证设计模块的逻辑功能，后者用于验证设计模块的时序关系。由于不同器件的内部时延不一样，不同的布局布线方案也给时延造成不同的影响。因此在设计处理以后，对系统和各模块进行时序仿真，分析其时序关系，估计设计的性能，以及检查和消除竞争冒险等是非常有必要的。实际上这也是与实际器件工作情况基本相同的仿真。因此，为仿真实际器件的工作情况，本节采用时序仿真的方法来验证星上输入缓存调度算法的FP-GA设计。下面以仿真中一个信元时隙里的调度为例验证本算法的可实现性。假设输入条件如矩阵A表示，表示输入端口A(i，j)=1有信元准备发送到输出端口j。图5为本次ModelSim仿真结果的波形图。将仿真结果与计算出的结果相比较，可看出两者一致，说明仿真正确，本文提出的改进的输入缓存调度算法是可实现的。

4结论

针对星上交换的性能要求，本文对原有的串行调度算法进行了改进，并对改进算法进行了性能分析。同时本文构造了OPNET仿真模型，在信元突发到达过程下对改进算法和常见的几种典型调度算法进行了仿真和比较。仿真结果表明，在平均调度时延方面，本文提出的改进串行调度算法性能明显优于iSLIP算法及原有输出串行调度算法;另外，当缓存区大小有限时，改进串行调度算法的丢失率明显小于原串行调度算法。最后，本文对改进串行调度算法节能型了硬件分析和仿真，通过分析和仿真算法可知，该算法是可实现的，且实现起来比并行调度算法更加简单。因此，针对星上交换的时延大且芯片受限等特点，可考虑将该算法用于ATM或IP交换结构中，同时也可以应用于多级交换的基本交换单元里。

作者：张怡周诠黎军李静玲梁薇单位：中国空间技术研究院西安分院空间微波技术部级重点实验室