多处理器片上系统中实时自适用仲裁器的设计与分析*

陈利平，高金华

(湖南工学院计算机与信息科学系，衡阳421002)

1 引言

多处理器片上系统(MPSOC)一般由多个处理器单元、专用功能模块甚至混和信号电路组成，构建一个复杂的集成计算系统，从而满足市场对于系统在计算性能、功耗、实时性与成本等方面的需求。MPSOC不是简单的片上多处理器(chip multiprocessor)，后者强调将更多的处理器放在单片上以提高单位面积晶体管密度，并不考虑平衡应用的需求。MPSOC则通过定制体系结构来满足不同应用在成本和功耗等方面的需求，已广泛地用于通信、消费类电子产品和网络多媒体等诸多领域［1］。

MPSOC的性能主要取决于处理器之间的高效通信和其计算量的平衡分配，而不仅仅是单个处理器的速度。尽管对于MPSOC目前有很多可供选择的通信架构，共享总线架构仍然是小规模MPSOC的常用方案，因为它简单，硬件消耗少而且面积效率高。在基于总线的系统中，仲裁器是决定系统性能的关键部分，它负责分配各个处理器访问共享资源的优先级，有效的竞争解决机制必须合理地分配和控制各个处理器占据的总线带宽，避免低优先级传输的饥饿现象。首先介绍了MPSOC仲裁算法领域目前的研究状况，针对静态［2］、动态［3］、实时［4］的lottery总线仲裁算法进行了分析，并在高性能的基础上进行改进，提出一款算法简单的基于ATM交换架构的实时Lottery bus仲裁机制。它为两级仲裁机制，第一级为实时处理;第二级为基于ATM交换机制的lottery bus仲裁，它基于概率总线分配算法，可以解决lottery总线存在的问题。

2 背景及相关研究

常用的仲裁算法有固定优先级、时分复用、Lottery、RT －Lottery、动态自适用。

2.1 固定优先级仲裁算法

固定优先级仲裁算法大量应用于现代总线中［5］。在该仲裁方法中每个处理器访问共享资源的优先级是固定的，传输任务较重的主设备优先级相对较高，如果几个总线主设备同时申请总线使用权，优先级高的设备将获取控制权。这种仲裁算法的优点在于设计简单，硬件消耗小，容易实现;缺点是它缺乏对总线资源分配的控制，低优先级的主设备等待时间过长，容易造成饥饿现象。

2.2 时分复用仲裁算法

时分复用仲裁算法(Time division multiplexed TDM)［6］是将总线上的使用时间分成时段，再把时段分配给要求使用总线的主设备。有时，某主设备对总线使用的申请可能需要多个时段来完成所有要求的传输;然而，在该结构中，该主设备只能通过使用两级仲裁协议交替地访问总线来完成所要求的传输。第1级仲裁采用时间段轮转的方式来选择相应的主设备，如果一个主设备在它的保留时段中没有申请使用总线，第2级仲裁机制会将该时段分配给其他发出请求而且优先级最高的主设备。这种仲裁算法的优点是容易实现;缺点是导致数据传输错误，高优先级设备的总线等待时间过长。

2.3 静态的Lottery总线仲裁

Lottery［2］总线的核心是采用加权随机算法的“Lottery仲裁器”，总线上每个主设备固定分配一定数量的“彩票(ticket)”，“彩票”越多，该主设备被授权的概率越大，如图1所示。如果仲裁器产生的随机数是某个主设备所持“彩票”，则该设备就获得总线使用权。各主设备Ci获得总线授权的概率如式(1)所示:

其中 t1，t2，…，tn依次为主设备 1，2，…，n 的“彩票”数，r1，r2，…，tn是一系列布尔类型的变量，表示各个设备发出请求的情况。如有请求，ri=1，否则 ri为0。

Lottery Bus机制允许Master设备发出多字请求，同时为了避免其中某一Master设备独占总线，还设定了最大总线占用周期以限制最大传输量。静态的lottery总线仲裁的优点是可以很好地控制网络交换应用的带宽分配和公平的平均反应时延，缺点是没有硬实时考虑、不能独立控制响应时延和带宽分配。

图1 静态Lottery bus仲裁机制示例

2.4 动态的Lottery总线仲裁

动态Lottery总线仲裁器［3］如图2所示，增加了各总线主设备的“彩票”数目ti作为输入，而且每个响应的主设备当前拥有的彩票数目是由彩票产生器产生的。在该机构中，不仅当前的彩票范围是动态变化的，而且可以选任意值;而静态lottery中，彩票是固定的。Lottery仲裁器用来分配和控制每个主设备占用的总线带宽。线性反馈移位寄存器(LFSR)用来产生要求范围之内的随机数，从而保证每个主设备都有一定的概率被授权，防止饥饿现象。采用该仲裁方法使得高优先级设备在不同的请求序列中响应延迟较小，而优先级较低的设备总线延迟偏长，而且在各个主设备传输负载相差较大的情况下，由于实际运行下各处理器的传输负载可能超过或不足于请求的情况，它们实际分配到的总线带宽并不符合预先设定的值，如果伪随机数大于总彩票数时，则所有的主设备都不能获得授权信号。

文献［5］中提到一种基于Lottery总线的满足所有硬实时性要求的仲裁算法 RT－Lottery，而文献［6－7］则提出了其他改进型 Lottery总线仲裁器来减小总线缓存大小或者提高总线带宽控制能力等。它们的算法都较为复杂，增加了设计电路的难度和仲裁器所消耗的硬件资源。文献［8］提出的动态自适应仲裁器算法简单易于设计，提高了系统性能，减少了处理器平均等待时间和最大等待时间，但没有针对实时性进行设计。

图2 动态Lottery bus仲裁机制示例

3 实时动态自适应机制

Lottery总线采用了高效的仲裁机制并能有效控制总线各主设备所占总线带宽，但是预先为每个设备设定准确的“彩票”数是很困难的。因此本文提出了硬实时和自适应的动态调整“彩票”数的方法，以期改进标准Lottery总线的仲裁机制。

3.1 实时自适应仲裁机制

Lottery概念仲裁算法不能处理硬实时请求，因此提出一个两级的仲裁算法——实时自适用ATM交换机制。第一级为硬实时处理器，用来处理硬实时请求;第二级为动态自适用ATM交换机制，用来处理总线的带宽，可根据当前总线传输情况自动调节各个处理器占据的总线带宽。

3.2 模拟模型

在该模型中，假定主设备拥有总线时，其它主设备不能访问总线;直到拥有总线的主设备释放总线，其它主设备才能访问总线;每个处理是非抢占式的。如图3所示的系统架构中，有四个主设备，每个主设备都有交通发生器，每个发生器的动作是由设计者给定的。仲裁器从所有主设备收到请求后，再决定授权给哪一个主设备。

图3 二级硬实时钟裁模型

从每一个主设备发出的交通信号有四种:

(1)Rcycles(实时周期)

这是主设备在时钟周期的实时请求，对于大多数没有实时请求的主设备不必定义。

(2)跳数和概率

它定义由主设备发出的触发数的概率。

(3)间隔周期和概率

它由主设备发出的两个相继请求之间的间隔时间决定，但决定间隔时间的规则是随主设备的不同类型而变化的。

(4)主设备类型

根据交通行为主设备分为三种类型:

·D 型( 依赖类型)

D 型主设备没有实时请求，且下一个请求的发出必须依赖当前请求的完成时间。对于D 型主设备，两个相继请求的间隔时间是从前一次请求的发出时间到后一个请求的完成时间。在时钟周期2中，假定交通发生器产生一个4 跳的触发，而这个请求直到时钟周期5 才被授权，时钟周期9 完成。若间隔时间是10，则下一个请求是在时钟周期19 发出( 后者请求的发出时间是前者请求的完成时间加10 个时钟周期) 。

·D－R型(实时依赖型)

D－R型主设备除了和D型有相同的依赖之外，它还有实时请求。主设备有实时请求，Rcycles为10，因此请求在时钟周期2发出，则它一定在时钟周期12完成(2+Rcycles=12)。如果这个请求不能在时钟周期12之前完成，它就违反了实时规则。

·ND－R型(实时非依赖型)

ND－R型主设备请求的发出时间是不依赖于前一个请求的完成时间，且间隔时间是两个相继请求的时钟周期。如图所示，假设间隔时间是15，第二个请求是在时钟周期17发出，它直接依赖于第一个请求的发出时间(时钟周期2)，而不是完成时间(时钟周期9)。因此，当前的请求一定在下一个请求之前完成，Rcycles的合理值应该小于最小间隔时间，使设计者重置较紧的实时请求。为了确保合理的 Rcycles，定义 Rcycles=Min(tmin－interval，tuser－given)，tmin－interval是最小可能的间隔时间，tuser－given是设计者给定的实时请求。

3.3 实时处理

实时处理根据实时请求为主设备设置实时计数器，当一个主设备发出请求时，响应的实时计数器就设置为主设备的Rcycles，实时计数器每时钟周期递减1，直到该主设备被授权为止。警告期是一个全局常量，用来提醒仲裁者授权给最紧迫的主设备。如果响应的实时计数器在警告期以下，则该主设备将有较高的优先级，当两个或多个实时计数器的主设备获得授权，如图4所示，当M1在时钟周期3发出请求，M1的实时计数器就设为30(Rcycles=30)，所有其它的主设备在此时发出请求，而只有M2的实时计数器在警告期以下，则M2首先被授权。M2的请求是8跳触发，该请求在时钟周期11完成，此时，其它发出请求的主设备的实时计数器递减8，M1和M3的实时计数器同时在警告期以下，而M3的实时计数器较小，因此，M3获得授权。

图4 M1的Rcycles=30，Warning－line=20的实时处理图

由上式可知:在最坏情况下，有最大跳数的D型主设备发出最大跳数请求时可获得授权;在下个时钟周期，有实时请求的其它主设备都发出请求，在D型主设备请求完成后，一定要保证满足这些主设备的请求。

3.4 动态自适用ATM交换仲裁机制

在该仲裁机制中，仲裁器的输入参数为请求、彩票、自适用信号三个。请求和彩票是静态总线分配的输入;自适用信号作为附加输入，常用来提高总线授权的概率。这个自适用信号是从因该主设备传输任务较重而需要比其它主设备多授权而发出的，如图5所示。我们不知道哪个IP用在高级的SOC设计的共享总线上，因此自适应信号给定具体参数。主设备计算存储ATM信元的缓冲位置，如果数据接近极限量时，产生自适用信号提高命中概率，则主设备Ci获得授权的概率如(2)式。

上式显示了每个主设备的共享总线概率。待处理的请求和彩票值常用来获得每一个主设备Ci的共享概率，为了提高主设备的授权概率，ai可从查找表获得，并与要完成请求的主设备请求进行比特法与操作，ai是附加的彩票值，用来解决总裁判值小于伪随机数时，以优先级倒置方式将总线分配给主设备。

ATM交换机制的优点是自适用信号解决了伪随机数大于总彩票值时线性反馈移位寄存器(LFSR)特征消失的问题。

4 仿真平台和结果

为验证实时动态自适用ATM交换仲裁器的性能，本文用VHDL来设计静态Lottery总线仲裁器、动态Lottery总线仲裁器和硬实时动态自适用ATM交换仲裁器(见图5)，并使用VHDK测试平台测试3种仲裁机制的性能参数，测试时，数据的长度未考虑，并假设只有一个时钟周期，模拟结果如表1所示。

图5 ATM交换仲裁器结构示意

表1中对不同仲裁机制的每个主设备的平均时延，平均等待时间，平均带宽，实时性能和带宽性能等做了比较。综合以上的实验结果，采用实时ATM交换仲裁机制性能是最佳的，它不仅考虑了实时要求，而且考虑了带宽要求，并减少了平均时延、平均等待时间，提高了资源的整体运行效率，从而改善了系统性能。

表1 综合性能比较

5 结论

静态lottery总线机制和动态lottery总线机制可以解决优先级算法的问题，而lottery总线机制也有一些缺点。实时ATM交换机制是基于概率总线分配算法，它不仅考虑了实时要求，同时也考虑了带宽要求，还解决了伪随机数大于总彩票值时线性反馈移位寄存器(LFSR)特征消失的问题。这种机制可用VHDL建模，提供的模拟结果表明，硬实时ATM交换机制可以减少49%的总线请求延迟。

［1］Abmed Jerraya，Hannu Tenbunen，Wayne Wolf.Multiprocessor systems－ on － chips［J］.IEEE Computer，2005，38(7):36－40.

［2］K Lahiri，A Raghunathan.The LOTTERY BUS on － chip communication architecture［C］.Trans.On VLSI system，June 2006 IEEE.

［3］Dinesh Padole，P R Bajaj，et al.Dynamic Lottery Bus Arbiter for Shared Bus－System on－chip:A Design Approach with VHDL［C］.First international conference on Emerging Trends in Engineering and Technology 2008 IEEE.

［4］C Chen，G Lee，J Huang，et al.A real－ time and bandwidth guaranteed arbitration algorithm for SOC bus communication［C］.Asia and South Pacific Design Automation Conference，Yokohama，Japan，2006.

［5］K A Kettler，J P Lehoezky，J K Ttrosnider.Modeling bus scheduling policies for real－ time systems［C］.The 16th IEEE Real－ Time Systems Symposium，Oakland，USA，1995.

［6］F Poletti，D Bertozzi，L Benini，A Bogliolo.Performance Analysis of Arbitration Policies for SoC Communication Architectures［J］.Journal of Design Automation for Embedded Systems，2003:618 －621.

［7］潘杰，胡丹，张志敏.LotteryBus的设计与实现［J］.微电子学与计算机，2005，22(7):76 －78.

［8］徐懿，李丽，杜高明，等.一款基于多处理器片上系统的动态自适用仲裁器［J］.计算机研究与发展，2008，45(6):1085－1092.