多路总线仲裁算法优化研究

赵琳

（西安航空学院计算机学院，陕西西安710077）

在共享总线系统中由于多个设备要争用总线来和其他设备进行互访以及资源共享，从而引出总线仲裁的概念。总线仲裁就是实现将总线控制权从一个设备向另一个设备转移和指定的过程。

目前，在高复杂度、高集成度的系统芯片Soc设计中，微处理器、微控制器等主模块与存储器、外围设备等从模块进行通信时，由于多个主模块同时申请总线请求传输，而引起的有限总线资源竞争已经成为影响系统性能的重要因素[1]。

因此，多路设备同时发出总线请求时就会冲突，为使总线资源有效利用，对竞争设备进行仲裁并根据结果对设备赋权的策略称为仲裁算法，仲裁算法对于系统性能的影响起着重要的作用[2]。目的带宽比与实际赋权比的吻合程度是衡量仲裁算法的重要因素，越吻合，算法越具广泛适用性。近几年的研究多以此项指标进行仲裁器的性能评估[3]。

仲裁赋权决策多由不依赖于硬件的仲裁算法确定，本文利用Visual Stidio设计了仿真平台，充分利用软件的优点对仲裁算法进行检验[6]。

1 常用仲裁算法介绍

1.1 经典仲裁算法

固定优先级仲裁算法[7-9]就是各个设备优先级保持不变。仲裁时总是先响应优先级较高的设备。它的优点在于电路简单，硬件开销少；缺点在于容易导致高优先级设备长时间占用总线，而低优先级设备长时间争用不到总线，容易出现“撑死”或者“饿死”的情况，适用范围有限。

循环优先级仲裁算法[10-12]指设备的优先级循环变化，最高优先级在每个设备之间进行轮转。该算法中，每个总线设备都能上升为最高优先级设备，可以保证每个设备都能占用到总线。缺点在于各设备优先级过于公平，忽视设备本身优先级高低的差异。

彩票仲裁算法[14-15]是指将所有设备按照自身带宽比需求的不同赋值一个彩票抽取范围，仲裁器随机抽取彩票所在范围的设备赋予总线使用权限。彩票仲裁算法理想情况下能够很好的实现目的带宽比。缺点在于仲裁受到概率的影响，且对电路的开销较大。

1.2 静态和动态算法

常用的仲裁算法分为静态算法和动态算法。在算法中主模块的优先级是确定的称为静态算法。在仲裁过程中主模块自身优先级可变称为动态算法。固定优先级仲裁算法、循环优先级仲裁算法、彩票仲裁算法都是静态优先级算法。

2 本文仲裁算法

为了弥补固定优先级仲裁算法和循环优先级仲裁算法中的不足，兼顾主模块本身的优先级和公平性的要素。文献[16-18]设计应用了两层仲裁系统，第一层使用固定优先级算法进行快速仲裁响应，第二层以轮询仲裁算法保证公平性原则。为了保证目的带宽比与实际带宽比吻合这一性能指标，文献[3-6]中都根据彩票仲裁算法的思想为主设备本身的特点预先赋值彩票数，从而达到满足目的带宽比的性能要求。

在众多的双层仲裁器算法中，仲裁器需要逐一对主设备进行判断和询问，这样会产生判断顺序的问题并使得主模块的优先级更加复杂[6]。另外在双层算法中要对两种仲裁算法分别设计仲裁模块，增加了总线的延迟和损耗，两层算法在切换时也会增加额外的总线周期影响总线利用率[5]。

为了弥补双层仲裁算法的不足，本文在借鉴固定优先级仲裁算法和彩票仲裁算法的基础上，提出了一种改进的有序仲裁算法。其原理如图1所示。

图1 本文算法流程

本文仲裁算法中的工作方法为：在第一次共享总线上有设备进行总线请求时，若只有一个设备则直接将总线使用权赋予该设备。若为多个设备请求总线使用权，则根据每个主设备的固定优先级进行总线仲裁。其余未被赋权的主设备按照固定优先级进行排队。当本次总线使用结束后，总线仲裁设备将直接从排队中按照先入先出的顺序进行多设备的总线赋权。为了保障目的带宽比与实际带宽比相吻合这一指标，给每个设备按照目的带宽比赋予彩票值。每个设备被进行了总线赋权之后，该设备的彩票值减1。在每次循环第一次仲裁之外的其他仲裁，仲裁器都是从排队中获得需要被赋权的设备。但是在每次赋权之前首先进行彩票值的判断，若彩票值为0则屏蔽掉改设备的总线申请并将该设备从排队中删除。若排队设备为空，则说明或者为轮空状态或者所有设备的彩票值都已经为0了。此时，按照目的带宽比给所有设备重新赋值。并按照固定优先级的仲裁算法开始新一轮的总线仲裁和排队过程。

综合改进后的顺序仲裁算法，从主设备本身所具有的不同优先级来看待设备之间的关系，赋予各设备不同的固定的优先级。根据目的带宽比赋予各设备不同的彩票值。根据每个设备提出请求的顺序不同而进行申请排序。在每个循环周期开始根据固定优先级仲裁，其余仲裁按照FIFO的原则进行赋权操作，每进行完一次总线赋权操作便将相应主设备上的彩票值减1。在按照FIFO的原则进行赋权之前判断一下各设备的彩票值是否全部为0，以此为依据来决定是否开始下一轮重新赋权循环仲裁。本文算法中根据彩票值规定每个设备在一个仲裁循环周期中能否访问总线的门限值，保证目的带宽比。通过排队保证一个循环周期内的仲裁顺序。各设备固定优先级用于每个周期最初的赋权操作。本算法在保证目的带宽比的情况下，通过排队兼顾了仲裁算法的公平性，弥补了固定优先级算法的“饿死”或者“撑死”的现象。

3 算法仿真

3.1 仿真平台

仲裁算法大多不依赖于硬件设备，文献[6]中介绍了一种在Visual Studio编译环境下进行算法仿真的方法。本文借鉴了该方法并在此软件基础上增设了排队功能，验证本文仲裁算法的结果。

3.2 仿真方法

在仿真中通过含有3个域的变量来模拟设备，一个是整型域用来表示设备编号，一个是布尔型域表示设备的请求，另一个还是整型域用于表示该设备的彩票值。彩票值根据每个设备的目的带宽比确定。这样每个设备构成了一个具有3个域的设备向量。用队列实现冲突状态下多个设备的排序。仲裁算法用函数设计，设备向量作为仲裁函数的输入，在仲裁函数内部，根据队列的判空来确定是进行快速赋权还是从队获取仲裁设备赋权。经仲裁后形成仲裁向量与设备向量进行逻辑加如表达式（1）所示，最后将赋权设备输出。

表达式（1）中X表示设备向量，W表示仲裁向量，Z表示仲裁结果。

在函数中设置了累加器和每个主设备被赋权次数的计算器，用于计算每个主设备的实际带宽比。比较实际带宽比与目的带宽比的吻合程度测试算法的性能。

3.3 参数设置

本文使用四主设备争用总线模型作为测试对象。4个主设备的固定优先级如表1所示。4个主设备的彩票值（目的带宽比）如表2所示。4个设备发出总线请求的比例如表3所示。验证在4个设备同时具有总线请求的冲突状况下进行。

表1 4个主设备的固定优先级

表2 4个主设备目的带宽比（彩票值）

表3 4个主设备发出请求的比例

本文在验证时对固定优先级仲裁算法和彩票仲裁算法进行了比对，用于分析目的带宽比与实际带宽比的吻合程度结果如图2、图3所示。

图2 目的带宽比（4:3:2:1）下算法验证

图3 目的带宽比（3:2:2:1）下算法验证

3.4 结果分析

固定优先级仲裁算法、彩票优先级仲裁算法、本文优先级仲裁算法，在四设备高冲突律的情况下。固定优先级在不同的目的带宽比和不同的主设备请求比例的情况下都出现了“撑死”和“饿死”的情况。而彩票仲裁法和本文仲裁法在预设了每个主设备彩票值的情况下目的带宽比在两种不同的主设备请求比例的状态下都能够很好的被满足。但彩票仲裁法受到概率的影响，且忽视了设备请求顺序这一实际情况，使得仲裁公平性受到影响。本文仲裁法在高冲突率的状态下较好的满足了目的带宽比，由于采用了排队的思想，考虑了各个主设备提出仲裁的顺序，体现了仲裁算法的公平性原则，高冲突率下的总线利用率为100%，避免了轮空现象。

本文仲裁算法很好的借鉴了了固定优先级和彩票优先级算法的优点，在优先级比较高的设备中使用总线的概率明显要高于固定优先级仲裁算法、仲裁公平性方面优于彩票优先级。由于每个主设备根据目的带宽比设置了预设彩票就给算法应用增加了更多的灵活性，可在优先级一定的情况下动态修改彩票权值即根据应用环境设置在一次循环中一个设备访问总线的门限值。更能满足实际中关于总线仲裁的各种应用[19-21]。

4 结 论

本文以双层仲裁算法为基础，借鉴彩票仲裁算法以及排队思想，弥补了双层仲裁算法的不足。在高冲突律的状态下提高了总线的利用率，并通过在赋权的同时对未被响应的设备进行排队，提高仲裁算法的公平性。从仿真结果看，本文的仲裁算法很好的满足了目的带宽比与实际带宽比相吻合这一重要指标，有广泛的适用范围。

参考文献：

[1]Bachanna P，Jalad V，Shetkar S.Design and Analysis of High Speed Low Power Reusable on Chip Bus Based on Wishbone[C]//Proceedings of the 2014 5th International Conference on Signal and ImageProcessing.Piscataway:IEEE，2014:197-200.

[2]YANG Yan-fei，ZHU Zhang-ming，ZHOU Duan，etal.Delay-independent asynchronous dynamic priority arbiter for the network on chips[J].Journal of Xidian University，2012.39（1）:42-48.

[3]吴睿振，杨银堂，张丽，等.一种基于权重与轮询的双层仲裁算法[J].电子与信息学报，2013，12（12）:3024-3029.

[4]杨哲，张萍，马佩军，等.基于动态混合优先级算法的仲裁器设计[J].电子器件，2011，6（3）:307-311.

[5]吴睿振，杨银堂，张丽，等.自调整附加权动态仲裁算法[J].计算机辅助设计与图形学学报，2014，9（9）：1494-1500.

[6]刘露，周小锋，朱樟明，等.一种采用双层仲裁机制的新型总线仲裁器[J].西安电子科技大学学报：自然科学版，2017，2（1）：12-18.

[7]Abdel-Hafeez S and Harb S.A VLSI highperformance priority encoder using standard CMOS library[J].IEEE Transactionson Circuitsand Systems II:Express Bricfs，2006，53（8）:597-601.

[8]Dimitrakopoulos G，Chrysos N，Galanopoulos K.Fastarbiters for on-chip network switches[C]//IEEE InternationalConference on Computer Design，Lake Tahoe，2008:664-670.

[9]Ciresan D C，Meier U，Gameardella L M，et al.Convolutional neural network committees for handwritten character classification[C]//Proceedings of the International Conference on Document Analysis and Recognition.Priscataway:IEEE Computer Society，2011:1135-1139.

[10]Ugurdag H F，Baskirt O.An in-depth look at prior art in fast round-robin arbiter circuits[R].Ozyegin University，2011.

[11]Ugurdag H F，Temizkan F，Baskirt O.Fast twopick n2n round-robin arbiter circuit[J].Electronics Letters，2012，48（13）:759-760.

[12]Medion G，Lee M S，Tang C K.A computational framework for segmentation and grouping[M].New York:Elsevier，2000.

[13]杨冬勤，黄航，张小燕，等.多路有序优先级和有序环形仲裁器设计[J].计算机工程，2011，12（24）：236-238.

[14]Singh A K，Shrivastava A，Tomar G S.Design and implementation of high performance AHB reconfigurable arbiter for on-chip bus architecture[C]//Proceedings of International Conference on Communication Systems and Network Technologies.Los Alamitos:IEEE Computer Society Press，2011:455-459.

[15]Khanam R，Sharma H，Gaur S.Design a Low latency arbiter for on chip communication architecture[C]//International Conference on Computing，Communication&Automation.Piscataway:IEEE，2015:1421-1426.

[16]龚丁禧，曹长荣.基于卷积神经网络的植物叶片分类[J].计算机与现代化，2014（4）:12-15.

[17]程江华，高贵，库锡树，等.高分辨率SAR图像道路交叉口检测与识别新方法[J].雷达学报，2012，1（1）：100-108．

[18]苗则朗.基于多特征的高分辨率遥感影像道路提取算法研究[D].徐州:中国矿业大学，2014.

[19]姜宁，陈建春，王沛，等.基于FPGA的PCIe接口实现[J].电子科技，2014（10）：188-191.

[20]徐震，邵波，王云鹏.无线传感器网络分布式数据采集功率控制研究[J].电力信息与通信技术，2017（2）:115-120.

[21]侯亚玲，李敏.智能优化算法在波导缝隙阵天线设计中的应用[J].自动化与仪器仪表，2017（8）:50-52.