基于最小空闲时间优先的片上总线仲裁算法

摘 要： 提出一种基于抢占阈值的最小空闲时间优先服务的总线仲裁算法。主设备总线服务请求的空闲时间越短，获得总线服务就越快，引入抢占阈值降低了总线服务频繁切换造成的颠簸现象。实验结果表明，该算法的MDP比常见的算法平均减少了43.8%,满足了各主设备总线服务请求的强实时要求。
关键词： 片上总线；仲裁算法；最小空闲时间优先；抢占阈值；截止期错失率

对于包含多主设备的片上系统，采用共享总线的结构具有实现简单和硬件开销较少的优势，已成为设计的主要手段。在共享总线结构中，多个总线主设备竞争使用总线控制权，不可避免地会产生竞争和冲突，为有效解决冲突，设计了总线仲裁器来决定总线上哪个主设备获得总线的使用权。但是，各总线主设备会有不同的实时性和带宽的要求，所以，总线仲裁器必须采取合理的策略和高性能的调度算法来满足各主设备的要求。目前，常用的总线仲裁算法有：固定/动态优先权算法FP/DP(Fix/Dynamic Priority)、时分复用算法TDMA(Time Division Multiple Access)、时间片轮转算法RR(Round Robin)和彩票算法(Lottery)。文献[1]-[3]已经证明了这些传统算法不能很好地满足各主设备实时性和带宽要求。目前，不少学者对传统算法进行了改进，如文献[4]把Lottery算法改进成三级总线仲裁机制；文献[5]通过自适应的动态调整“彩票”数来改进Lottery算法；文献[6]则提出了一种基于传输时间精确预测的仲裁算法。但是，这些改进算法也都没有考虑主设备请求总线服务的缓急程度。因此，本文提出一种基于抢占阈值的最小空闲时间优先PT-LSF(Preemption Threshold-Least Slack First)服务的片上总线仲裁算法。该算法在收集主设备请求(服务时间和截止时间等)特性参数和总线传输状态信息的基础上，通过PT-LSF算法的调度结果，实时动态地改变主设备优先权，以满足主设备强实时性要求。
1 基于最小空闲时间优先的总线仲裁算法原理及实现
1.1 算法原理
记空闲时间Si定义为从当前时刻t直到其截止期di的时间与其剩余服务时间ci(t)之间的差，则最小空闲时间优先调度算法的策略是：按照主设备的空闲时间动态地分配优先级p，可由式(1)确定：
p_i=p_max-S_i (1)
空闲时间越短，主设备的优先级就越高，因此选择具有最小空闲时间的主设备获得总线的使用权。假设某个主设备Ti发出请求总线服务请求时，总线正被具有更高优先级的其他主设备Tj所占用，从而阻止了Ti使用总线。随着时间的推移，Ti的空闲时间严格单调递减直至小于正占用总线的主设备Tj的空闲时间时，按照调度策略，总线必须切换到服务Ti。
1.1.1 总线颠簸现象
由于等待主设备的空闲时间随时间严格递减，当有多个任务等待主设备时，其空闲时间不断变化，所以会出现多个主设备相互交叉抢占总线服务的现象。每次抢占都发生一次总线切换，造成总线服务颠簸现象。由于总线服务切换的时间不可忽略，而且会加大仲裁器的设计难度，浪费资源，因此必须有效地避免颠簸现象。颠簸现象的产生主要是因为等待服务主设备Ti的空闲时间Si一旦小于服务主设备Tj的空闲时间Sj，就马上进行总线服务切换，所以选择合适的切换时机可以有效地解决颠簸现象。本文引入抢占阈值来扩展最小空闲时间优先服务的总线仲裁算法。
1.1.2 抢占阈值的确定
记pi为主设备Ti的优先级，hi为主设备Ti的切换阈值。根据之前的分析，主设备的优先值越大，其优先级就越高，所以主设备的切换阈值必须大于其优先值，即hi>pi。因为pi的值是动态变化的，所以hi值不能事先确定，需要随时间进行动态修改。考虑到总线仲裁过程实时性要求很高，hi值的确定不宜过于复杂，所以本文采用线性法来设计。对于任意Ti，hi的值由式(2)确定：

1.2 算法流程
算法流程如下：
(1)算法初始化；
(2)检测是否有主设备请求总线服务，有则初始化主设备(假设为Ti)的参数(优先级pi=pmax；切换阈值hi=hmax；空闲时间Si)，并加入等待服务主设备队列T′中；
(3)对T′中的每个主设备计算Si；
(4)判断总线是否正在服务，是则转(5)，否则转(7)；
(5)对T′中的所有Ti，计算Si-Sj，结果小于0则加入就绪服务主设备队列T″中，转(6)；
(6)判断T″是否为空，是则转(9)，否则对T″中的每个主设备计算pi=pi-hj，如果max(pi)>0设置Ti的优先级最高，减小pj，转(7)；
(7)对优先级最高的Ti进行服务，转(8)；
(8)修改各主设备参数，按照式(1)修改pi，式(2)修改hi；判断T′中的主设备是否服务完，是则转(9)，否则转(2)；
(9)算法结束。
1.3 算法实现
基于阈值的最小空闲时间优先服务的片上总线仲裁算法由4个基本模块组成：算法控制模块、优先级调节器、带宽调节器和总线传输控制器。另外，算法所需的主设备访问总线特性参数（服务时间、截止时间等）和总线服务参数信息由信号提取模块完成，信号的控制和实际数据的传输由信号授权模块完成，其总体结构如图1所示。

（1）优先级调节器
该模块的主要作用是实现对主设备优先级的动态调节,以满足主设备的实时性要求。该模块从信号提取模块中获得各个主设备实时性相关的参数(主设备请求总线服务时间、最大截止时间、请求访问从设备的地址及从设备传输响应时间等)，然后进行简单的处理后，传入算法控制模块，经过算法控制模块的运算，最终得到各个主设备调整后的优先级。优先级调节器根据该结果通过信号授权模块动态调整各个主设备的优先级。
（2）带宽调节器
该模块的主要作用是监视总线上主设备实际传输带宽和由算法控制的应该配置带宽之间的变化，实时反馈信息给算法控制模块来保证带宽精确分配。该模块从信号提取模块中获得各个主设备带宽要求相关的参数(主设备每次数据传输的长度、主设备带宽需求以及总线带宽利用情况等)，然后进行简单的处理，传入算法控制模块，经过算法控制模块的运算，最终得到各个主设备调整后的带宽要求，带宽调节器根据该结果通过信号授权模块动态调整各个主设备的带宽配置。
（3）总线传输控制器
该模块的主要作用是监视总线带宽的状态，准确预测出各设备请求的响应时间，并将该结果传入算法控制模块，经过算法控制模块的运算，得到新的总线带宽分配方案。总线传输控制器通过信号授权模块来协调各个主设备使用总线。
（4）算法控制模块
算法控制模块的硬件逻辑包括：时间片定时器、判据寄存器组、比较逻辑和算法控制状态机。其中，判据寄存器组的初始值通过离线计算获得，在总线服务过程时，通过主设备特性参数提取模块获得实时参数值，作为新的判据寄存器数据提供给算法控制状态机。比较逻辑负责对算法运行产生的新结果与判据寄存器组进行比较，并对判据寄存器组内的数据进行更新。
算法控制状态机采用Mealy有限状态机来实现总线仲裁算法流程，完成对各主设备的优先级、带宽分配等属性的动态调节。另外对各主设备请求使用总线服务进行仲裁，实现各主设备协调使用总线所提供的服务。
2 实验及结果分析
为验证基于阈值的最小空闲时间优先服务总线仲裁器的性能，本文对基于动态优先级的仲裁器、基于时间轮转的仲裁器和本文提出的仲裁器进行了实验，并进行了比较。
2.1 实验平台
实验硬件平台为Core 2 Duo CPU(主频为2 GHz)，内存4 GB，操作系统是Windows XP，仿真软件使用ModelSim6.4。在实验平台上，共实现了6个主设备、1个从设备和1个总线仲裁器。6个主设备的类型和相关参数如表1所示(在表1中，R表示有实时性要求，NR表示没有实时性要求；B表示有带宽要求，NB表示没有带宽要求)。

2.2 实验结果
首先，定义两种性能指标：
(1)服务请求截止期错失率MDP（Missed Deadline Percentage）=“所有截止期错失的总线服务请求/所有主设备总线服务请求之和”。
(2)服务切换次数SSN(Service Switch Num)=“从未完成的总线服务请求到抢占的总线服务请求切换次数”+“从完成总线服务请求到另一总线服务请求的切换次数”。
在此基础上，对表1中所示的6个主设备分别采用4种总线仲裁算法进行仿真实验，得到如下结果。
(1)对于不同总线负载ρ
取公式（2）中的α=5，图2和图3分别表示对于不同总线负载ρ(0.5≤ρ≤2.0)情况下，4种总线仲裁算法的MDP比较。其中图2是在每个主设备请求100个总线服务下的MDP，图3是每个主设备请求200个总线服务下的MDP。从图2和图3中可以看出，最小空闲时间优先总线仲裁器得到的MDP要明显小于其他两种总线仲裁器。当ρ≤1时，最小空闲时间总线仲裁器可以保证每个主设备都满足其总线服务截止期要求；当ρ>1时，会出现主设备部分总线服务请求不能满足其服务截止期要求的情况，但其MDP要明显小于其他两种总线仲裁器。

(2)对于不同比例系数α
取ρ=1.3，图4和图5分别给出了在不同比例系数α时的MDP和SSN变化情况。
从图4中可以看出，对于MDP的影响，并不是抢占次数越多（比例系数α越小）调度效果就越好，而是当α=12时，MDP最小；而当α=1时，MDP达到最大。从图5中可以看出，SSN的值随着ρ的变大而逐渐变小，但是，当α的值大到一定量时，SSN的值变化不明显；当α接近1时，SSN变化显著。究其原因，从公式（2）中可以看出：当α=1时，hi=pi，即主设备的抢占阈值等于其优先级，则抢占阈值就没有起到作用，即变成了完全抢占模式，该情况下，主设备频繁地抢占总线服务，造成过多的总线服务切换，浪费了总线带宽资源，从而影响总线服务的性能；当α=16时主设备的抢占阈值为最高优先级，造成永远不能被其他主设备抢占的情况，成为非抢占模式。以上两种情况都会造成总线服务质量的下降，所以，比例系数α的选择应当保证MDP最小的情况下，相应的SSN值不能太大，结合图4和图5可以看出，α=12为最优比例系数。

2.3 试验结果分析
在PT-LSF算法中，总线仲裁器在收集主设备请求特性参数和总线传输状态信息基础上，结合主设备请求总线服务的缓急程度来实时地改变主设备优先权，以满足主设备强实时性要求。通过与常用的动态优先级算法、时间片轮转算法和Lottery算法的实验分析比较可以看出，本文提出的PT-LSF算法在服务请求截止期错失率（MDP）上有显著优势。当总线负载在0.5～1.0范围内时，PT-LSF算法的MDP值为0；当总线负载在1.0～2.0范围内时，PT-LSF算法的MDP值比时间片轮转算法平均减少了50.8%，比动态优先级算法平均减少了43.6%，比Lottery算法平均减少了36.3%。综合对比，PT-LSF算法的MDP比其他算法平均减少了43.8%，能很好地满足各主设备在各种情况下的强实时要求。另外，在PT-LSF算法中，使总线服务达到最优时，并不是抢占次数越多（比例系数α越大）越好，而是取一个中间合适值。在本文中，系统最大优先级为16，最小优先级为1，最优比例系数α为12，该结果为抢占阈值比例系数?琢的确定提供了实验依据。
本文提出了基于最小空闲时间优先的总线仲裁算法，并给出了算法的实现流程和组成结构。将其与动态优先级算法、时间片轮转算法和Lottery算法进行比较。实验结果显示：该总线仲裁算法在MDP方面比其他两种算法平均减少了43.8%，能更好地保证主设备的强实时要求。该总线仲裁算法对于共享总线的片上系统设计具有重要的参考价值。
参考文献
[1] POLETTI F，BERTOZZI D，BENINI L，et al.Performance analysis of arbitration policies for SoC communication architectures[J].Journal of Design Automation for Embedded Systems，2003(8)：189-210.
[2] LISNER J C.Efficiency of dynamic arbitration in TDMA protocols[C].EDCC2005，Berlin，2005：91-102.
[3] ZHANG Y.Architecture and performance comparison of a statistic-based Lottery arbiter for shared bus on chip[C]. //Proceedings of Asia South Pacific Design Automation Conference，Yokohama，2004：1313-1316
[4] Bu-Ching Lin，Geeng-Wei Lee，Juinn-Dar Huang，et al.A Precise bandwidth control arbitration algorithm for hard real-time SoC buses.IEEE，2007：165-170.
[5] 徐懿，李丽，杜高明，等.一款基于多处理器片上系统的动态自适应仲裁器[J].计算机研究与发展，2008，45(6)：1085-1092.
[6] 孟海波，张志敏.基于传输时间精确预测的片上总线仲裁算法[J].计算机辅助设计与图形学学报，2008，20(7)：830-837.