多核系统负载平衡模型设计

引言

在嵌入式多处理机系统中，经常出现这种情况：某些处理机负载过重而另外一些负载很轻，甚至空闲。这种情况无疑降低了整体系统的工作效率。为了提高处理机的利用率和系统并行计算的效率，应该把负载过重的处理机上的一部分负载转移到空闲或轻负载处理机上，这就出现了负载分配问题的研究。

简单的说，负载平衡就是要尽量均匀地分配任务，并尽量减少结点之间的通信。解决负载平衡问题，通常有静态和动态两种调度策略：

①静态负载平衡是根据系统的先验知识做出决策，运行时负载不能重新分配。

②动态负载平衡是根据计算机过程中数据项的变化情况，交换系统的状态信息来决定系统负载的分配。它具有超过静态算法的执行潜力，能够适应系统负载变化情况，比静态算法更灵活、有效。但是由于必须收集、存储并分析状态信息，因此动态算法会产生比静态算法更多的系统开销，不过这种开销和付出常是有所回报的。

本文描述了一种有效的嵌入式多处理机系统的负载平衡模型，通过动态判断当前系统的负载情况，自动选择负载平衡算法，从而使整个系统以尽可能小的附加代价来达到全局的负载平衡。最后，在卡内基·梅隆大学的负载平衡测试框架上，搭建仿真环境进行模拟测试。结果显示，该模型能较好地平衡各结点的负载。

1 负载分配问题的数学描述

负载(1oad)是对一个处理机上运行的所有任务占用资源的衡量，负载指标(1oad index)是对负载进行量化的评价标准，不同的负载指标定义会得出当前时刻处理机不同的负载程度。关于这个问题，许多学者提出了他们的看法。

参考文献的研究表明，一般效果较好的是，将单项指标中的资源队列长度作为负载指标。参考文献[4]建议使用资源利用率而不是资源队列长度作为负载指标。近年来，随着CPU速度的快速增长。CPU和内存通信之间的瓶颈较为突出，内存空间的不足可能导致频繁的页面交换，这使得访问延迟大大增加。根据参考文献的研究，定义这样一个负载指标：

定义1 假设系统由N个处理单元构成，记为P0，P1，…，Pn-1。处理单元之间用通信线路连接，每个处理单元的负载记为WORK(i)，0≤i≤n-1。

其中，ε和ω为经验调整系数，O<ε≤10，K1<ω<+∞，ω为足够大的数；μ、L和M分别是处理机i的CPU利用率、运行队列长度和处理机i中所有任务请求的内存之和；Mem(i)为处理机i的可用内存。
整个系统的总负载为：

系统的平均负载wavg可以简单认为是：

Wavg=TotalWork／n

定义负载上界为W1=Wavg+ζ，负载下界为W2=Wavg-ζ。其中，参数ζ视具体系统之不同而定。

有了以上的基础，可以再进一步对各个结点的负载进行划分：某个处理单元的负载WORK(i)<W1，则为轻载结点；W1<WORK(i)<W2的为适载结点；WORK(i)>W2的为重载结点；WORK(i)=0的是空载结点，如图1所示。

2 嵌入式多处理机系统的动态负载平衡算法

一般来说，系统中每个结点上的任务是动态产生的，负载大小也是动态变化的。在完成任务的过程中，要周期性地检查任务完成的情况，并与其他结点交互这些情况。在此基础上，按照一定原则确定是否对任务进行迁移，以及迁移的源、目的结点和迁移量。

在动态负载平衡策略中，比较有代表性的算法是轻载结点请求算法和重载结点请求算法。在嵌入式多处理机系统中，一般情况下，根据系统当前的负载情况选用其中之一，可以有效地平衡负载；但是，当系统负载发生变化后，可能会由于原先选用的算法不合适而导致附加开销陡增，并且无法有效地平衡负载。因此，考虑到嵌入式系统本身的特点(例如资源有限等)，轻载结点请求算法和重载结点请求算法不加改进而直接用于嵌入式多处理机系统是不合适的。综合这两种算法的优缺点，就有了双向请求算法。

2．1 轻载结点请求算法

轻负载结点会尝试向重载结点请求任务，每个结点都定义了相关域，相关域的定义是把所有与之相邻的结点作为相关域成员。结点只与其相关域中的结点进行交互和任务传递。如果请求到任务，则中止请求，否则就继续询问下一个相邻结点。

启动时，所有结点几乎都是轻载结点。经过一段时间以后，结点开始检查自身是否仍是轻载结点，如果仍是，就试图在相关域中找出重载结点，并请求该结点上的任务。具体来说，设该轻载结点的负载为WORK(p)，相关域中有k个结点WORK(a+1)、WORK(a+2)……WORK(a+k)，则该部分的平均负载Wavg′为：

为达到任务的均匀分布，应求得相关域中重载结点应该传递给该结点的负载量(设为Mk)，但是必须对每个结点引入阈值H(j)，以避免任务从负载更轻的轻载结点迁移过来。若WORK(j)>为达到任务的均匀分布，应求得相关域中重载结点应该传递给该结点的负载量(设为Mk)，但是必须对每个结