在通用计算领域如大数据处理科学计算、天文图像的数字图像处理等其数据处理量呈爆发式增长。由于单机处理能力发展的限制，海量数据的处理必然从单机发展到多机、到超级计算机系统^[1]，通过提高单个处理器能力和增加系统并行性是解决问题的2个基本因素。但常规并行计算系统成本十分昂贵，如美国橡树岭国家实验室的“Titan”升级项目耗资9 000万美元，耗电量为700万瓦；中国的“天河一号”、“天河二号”也耗资数亿。因其成本问题，使得不少用户转向了以嵌入式系统为代表中低端硬件构成的机群平台^{[2, 3]}。一般系统以Intel、IBM这两家为代表的多核处理器为基础构建^[4]，而特定领域则以FPGA和DSP为核心。而在四代到五代计算机体系的发展中，嵌入式多核、多处理器系统在空间图像处理、空间计算等需要高性能、高可靠性、低功耗处理器^{[5, 6, 7]}领域日益受到关注，特别在车船、军事应用领域受到重视^[8]。

现有多处理器结构大多以AMP(异构系统)结构为主，AMP将2种或2种以上的处理器组合起来，分别处理用于一般任务处理和专用任务处理，当前AMP设计大多以FPGA与DSP、FPGA与ARM组合为主^[9]，但AMP设计复杂、编辑难度大、通用性低，因此基于Cortex-M3架构的SMP多处理器系统配以混合调度机制改进了该缺陷。

Cortex-M3架构具有很强的实时性同时兼顾应用能力；完成了双核方案，使用“一主多从”方式构建多处理器系统利用M3架构下STM32F1xx芯片的特殊的FSMC(flexible static memory controller)^[10]控制器，并对一般主-从结构优化系统简图如图 1所示：

图 1 基于主-从结构的多处理器系统简图

图选项

其中,主机和从机共享一组存储器，通过AHB/FSMC总线进行数据交互，主机与从机间使用TXEV和RXEV硬件连接实现,这可减少同步通信量提高系统并行处理能力。

CM3使用三级流水线，分别完成取指、解码和执行，如图 2所示配合共享存储器的缓冲机制，提高系统并行性和处理能力。

图 2 Cortex-M3三级流水线

图选项

在设计上主要参考消息机制^[11]，但具体实现是使用信号量机制加快任务切换，消息则通过一种特殊的共享存储区进行交互(tasks and data exchange area，TDAE)，如所图 3所示：

图 3 交互简图

图选项

这种设计通过独立的硬件中断进行信号量的快速响应，比直接消息传递、识别和处理要快很多，且占用总线带宽少，图 4是系统的详细设计框图。

图 4 系统详细结构框图

图选项

系统主要由主机、TDAE和从机构成。其中Host通过其BANK1的4个子sBANK1~4分别连接到TDAE区中的4个RAM，Client使用其BANK1的sBANK1分别连接到各自专属的RAM。Host通过片选总线Main-SW选择访问RAM；Host与Client在访问共享RAM之前还需要检查该RAM的SW控制信号，只有当SW处于合适的状态时，Host和Client才能获得对应RAM的访问权。

在任务管理上采用集中式工作池方式管理，主机负责任务的分配，使用DMA进行大数据传输；从机在响应主机控制信号后独立进行任务处理——从机相互独立且可相互替代。可以根据具体应用要求将Host和Client通过总线连接，而非现有的通过TDAE间接连接，以实现更复杂的通讯机制。

可以将图 4中各Client通过sBANK1独立访问的RAM相互交叉链接，这样就构成了MIMD结构，所有Client共享、访问这些RAM空间并构成“片上网络多处理器系统”^[12]。

在集中式工作池中，Host维护工作池，通过TDAE向空闲Client分派任务并使用中断控制通知任务开始；当Client完成任务后，它会向主机发送完成中断——与一般调度算法不同的是，Client不会主动请求任务，是否分派下一个任务完全是由Host来处理，这样可以良好的进行能耗控制，而且Host可以确切的知道“任务何时完成”，这一点对于嵌入式系统的实时性是非常重要的。

工作池技术可以灵活支持不同尺寸和要求的任务，但一般优先分派较大、较复杂的任务(Complex tasks first，CTF复杂任务优先调度)，在复杂任务完成期间其他Client可以并行的完成更多较为简单任务。

定义处理器集合P=｛P₀,P₁,…,P_i｝,i∈^{[0, 4]},其中P₀表示Host,由于单个系统至少一个Host,最多4个Client,因此i∈^{[0, 4]};P_i∈P,P_i=｛m_i,s_i,Lⁱ｝:其中m_i为处理器存储空间;s_i是系统处理能力S_i=(C_i^s ,T_i^s )其中C_i^s为服务时间,T_i^s为周期);Lⁱ为分配给该处理器的任务列表,Lⁱ=｛L₁ⁱ ,L₂ⁱ ,…,L_kⁱ ｝,L_kⁱ∈Lⁱ表示将任务L_kⁱ分派给该处理器。

定义信号量数组sw=｛sw₁,sw₂,…,sw_i｝,i∈^{[0, 4]},其中sw₀表示Hos的状态,每次操作前都应该对sw进行检测,提高系统可靠性和容错能力^[13];

系统主要采用集中式工作池的调度策略,Host作为工作池的管理者,定义主任务池taskpool_main < T>=｛T₁,T₂,…,T_k｝,T为标准任务结构包括:

周期任务τ=｛τ₁,τ₂,…,τ_n｝,τ_i∈τ,τ_i=(C_i,D_i,T_i),其中C_i为执行时间,D_i为相对截止时间和T_i为周期;

非周期任务J=｛J₁,J₂,…,J_n｝,J_i∈J,J_i=(A_i,C_i,D_i,S_i),其中A_i为到达时间,C_i为处理时间,D_i为相对截止时间^[14],S_i为任务空间规模对应需求处理器m。

根据集中式任务池的基本调度策略和信号量控制机制,任务调度主要分为任务派发、任务处理和结果处理3个部分,其流程如图 5所示:

图 5 系统任务调度处理流程图

图选项

以下为主机和从机任务处理伪代码:

文献[14]给出了基本的调度可行性证明,使用其提出的DM、DS-EDF算法能够成功验证系统的调度可行性。在以DM(Deadline Monotonic)算法调度时,只要满足公式(1)及其推广形式就可以满足周期任务的实时调度:

点击浏览公式

对于非周期任务通过满足公式(2)可以使用DS-EDF算法:

点击浏览公式

如果任意时刻t满足公式(3)非周期任务就是可以调度的:

点击浏览公式

在集中式控制池框架下,可以根据系统特性采用多种任务分派策略与任务缓冲机制。

图 6是系统关于集中式工作池的2种基本分派示意图,图 6a)中将TDAE看作是Client的任务存储空间,Host直接从Job Pool中取出合适的任务分派到其中就可以了;图 6b)中在TDAE中可以设立子任务队列,这样Host就可以一次或分多次向Client分派多个任务,实现任务本地化,从而减少Host的干预频度,提高运行效率;如果任务规模较小,则可将任务存储到处理器自带的cache(如STM32F1XE系列带64 kB)中,以双任务缓冲的方式提高存储空间的异步性、减少带宽占用并提升系统性能,如图 6c)所示。

图 6 集中式工作池(Centralizaed work pool)

图选项

系统在进行动态调度时可以按以下模型调度:

对于单个处理机P_m,如果由主机分配了一组非周期任务j=｛j₁,j₂,…,j_L｝,j∈J,对于下一个在时刻t(或下一个由主机分派)到达的任务j_L+1而言,以c_i(t)(i=1,2,…,L,L+1)代表任务j_i在时刻t剩余执行时间,则该处理器中所有的任务j可调度的充要条件为:

点击浏览公式

不失一般性,可以将工作池中的任务按照紧迫程度排序,然后再采用类似于“银行家算法”尝试将任务分派给某个Client,如果状态是安全的则分派该任务,否则尝试将其分派给下一个Client:

点击浏览公式

公式(5a)中,如果当前处理器队列为空,新任务满足公式(3),且没有超出资源限制,则使用图 6a)所示的单任务方式分派;公式(5b)中,如果该处理器在新增任务加入后仍然是可调度的,则使用图 6b)所示的任务队列方式调度,同时如果S_i < Cache_i及所需资源少于Cache拥有的,则允许使用图 6c)双缓冲调度。

可将多个系统组成群集,原有Host将成为群集的一个分布式节点的管理单元,形成分布式工作池,可将主工作池任务分布到Host所管理的子任务池中,以实现分布式动态负载平衡的方式处理任务;在上层可以配合Hadoop这样的分布式系统进行性能调整以进一步增强系统的处理能力。

在混合调度策略下,可以配STM32的3种低功耗模式²与实际任务环境需求进行动态节能控制,以最大限度的在运算性能和功耗之间取得平衡,如图 5所示,在每个调度阶段完成后,主机或从机就可以进入到节能模式。

系统可以在3种基本能耗模式下工作,如图 7所示。图 7b)属于节能优先的工作方式,分别对Host如能处理所有任务则就地分配模式,所有Client则可以待机或停机模式以降低功耗;如果处理不了,则将剩余任务尽量集中分配给其中一个Client,其他Client依然处于待机或停机模式以节省能源;只有当任务超出P_i的处理能力后才会将剩余任务分派给P_i+1。

图 7 基于负载的动态节能调度示意图

图选项

在以性能优先的调度策略时,如图 7c)所示,将任务吞吐量做为第一要素,将任务按照一定的调度策略分摊给每个Client处理,采用贪心法^[18]将任务“平均”分派到各个处理器,采用公式(6)

点击浏览公式

选择当前负载率最低σ_j的处理器j分派任务即可满足简单的负载平衡。

如果将实时性作第一要素,则可以采用RMS、EDF、LLF等一般实时调度算法,也可以使用针对多处理器系统的近视算法、动态调度算法、节约算法^[22]等。除此以外在任务环境允许的前提下,系统还可以采用改变处理器频率使得处理器在运算能力和功耗之间取得平衡,配合前面2类工作模式可以进一步增加系统的功耗控制能力。

选用任务量较大的中值滤波算法进行调度算法性能测试,采用定时器中断方式设定为1 ms，其中规模为64、160、256、400和640的方形灰度图像进行测试,结果如表 1和图 8所示。

图 8 系统在不同处理器数量及任务规模下的效率测试图

图选项

当处理器数量增加时，系统的效率降低，这是因为处理器增加后需要进行多次任务请求与分派，需要消耗更多的时间在进程同步上；当任务规模增加时，处理效率整体呈现下降趋势，其中4个处理器的下降趋势较大。

如图 9所示，使用cache构成双缓冲可以提高系统效率，但应当注意随着规模的增加特别是在规模接近或超过cache大小的时候，效率的提升是不明显的；是否适用单任务分派和基于队列的多任务分派之间的效率差异并不明显，或者说几乎是相同的。

图 9 启用cache后的效率对比图

图选项

系统在混合调度模型下可以支持3种类型的能耗，测试中使用4个从机、单任务分派机制，任务规模为400*400，测试结果如图 10所示：

(其中休眠功耗大约为1.3 mA，这里为了便于观察，将其值增放大了10倍)图 10 系统能耗测试

图选项

Host启动之后功耗维持在34~38 mA，从机处于休眠状态(功耗约1.3 mA)，当任务到达主机缓冲池(约28 ms)后Host开始向空闲Client分派任务，这也需要约28 ms进行任务传输，因此经过约56 ms后第一个从机被唤醒，然后进入执行状态；整个任务处理需要约550 ms，完成任务后通知Host分派下一个任务，然后进入休眠状态直到下个任务到达后再次被唤醒。

在单任务分派模式下，2个任务之间需要约28 ms数据传输时间，如果利用cache构成双缓冲，则可消除该延迟以提升系统运行效率，这一点通过图 9也能得到反映。

根据以上分析，如Host可以处理完所有任务，则所有Client都可以处于休眠状态，系统总功耗维持在40 mA水平；当启用能耗优先时，系统会根据任务数量将其逐步分派到各个Client上，此时功耗水平大约为“Host(36ma)+运行Client数量*36mA+休眠Client数量*1.3mA”；而在性能优先模式下Host和Client都在全速运转，总功耗约为180mA。可见不同任务调度模型对于能耗控制的重要性。

此外，由于系统统计时间的不准确导致在任务规模较小时，统计得到的实际效率超过理论效率，在问题规模较大时则不明显。

基于嵌入式系统实现了一种主从式多处理器系统，基于硬件中断的信号量控制方式可以较大程度的提高系统的响应速度和并行性，在集中式任务池管理方式下采用混合调度策略与算法在能耗和性能之间取得动态平衡，通过使用多种算法进行验证，系统的设计是合理的。

由于选用的F10X系列并非针对高密度计算而设计的芯片，其运算能力较低，并不适合支持如图像处理这样的任务，后期可以考虑使用带DSP的F40X芯片或选用具有较强处理能力的Cortex-A8解决方案。