可调度性保证的TTP总线能量有效优化方法

赵天鹤，熊华钢，程子敬，李 峭

(1.北京航空航天大学,a.大型飞机高级人才班; b.电子信息工程学院，北京 100191；2.北京卫星信息工程研究所国家重点实验室，北京 100080)

0 引言

时间触发协议(Time-Triggered Protocol,TTP)是分布式容错实时系统电子模块互连的实时通信协议[1]。TTP主要用于各种航空航天应用，例如波音787发电系统和环境控制、空中客车A380的机舱压力系统以及Aermacchi M-346 的全权数字发动机控制(FADEC)系统等。

节能环保的“绿色航电”理念已经开始渗入到航空电子系统设计的各个层面[2]，在实时应用条件下，有关通信的能量有效性研究关注于能量有效调度问题；文献[3]基于具有并行度的调度提出静态电源管理方法，配合两个动态电源管理方法(贪婪法和空隙填补法)来节省尽可能多的能量；文献[4]权衡了能量有效和可靠性，提出一种约束逻辑编程算法对比了不同动态错误下能量有效和可靠性的相互制约；文献[5]提出了一种启发式能量意识随机任务调度算法(ESTS)，比过去的多种能量有效的调度方法节省更多的能量。

上述研究提出了信号电平和信号频率影响数字电路系统能耗公式，并加以改进，但较少关注将能量有效目标直接用于指导航空电子综合化系统的调度问题。具体到TTP总线网络，既有的可调度性分析方法[6]包括静态单一消息(SM)、静态多消息(MM)、动态消息(DM)和动态分片(DP)消息分配模型。考虑文献[3-5]提出的能量有效策略，给出适合码元速率调整的静态分片(SP)分配模型，提出一种以能量有效为优化目标的消息调度表生成方法。该方法可用于计算降频节能的调度裕量，通过组合优化得到每个节点包含的调度裕量的最优分配方案，对周期消息调度表进行降频节能优化。

随着航空电子综合化设计向微小型化智能系统发展，时间触发互连协议将应用于芯片之间(off-chip)甚至是芯片内部(on-chip)[7-8]，在这些应用场景中将应用主频更高的网络协议处理单元，能量消耗对于码元速率的变化更加敏感，本文方法有望对未来微小型智能航电系统的综合设计提供参考。

1 模型

1.1 TTP节点调度模型

TTP网络采用总线式结构将各个嵌入式节点联接为分布式系统。TTP节点由主机、通信网络接口(CNI)和TTP控制器组成，其中，在一个集群中，发送节点从CNI接口获得带有状态信息的消息数据后，立即组帧并发送给其他需要接收的节点。每个节点的发送时间被保存在事先设定好的消息描述列表(Message Descriptor List,MEDL)中[1]。MEDL是TTP/C控制器的调度矩阵，用来描述节点数据收发消息等相关属性，存储在控制器RAM中，如图1所示。

图1 TTP总线构架图Fig.1 TTP bus structure

在高安全性领域，一般采用双冗余通道互连，通过相互冗余的通信通道连接的TTP节点形成一个集群，采用时分多路访问(TDMA)方法组织总线通信。一个集群包含多个TDMA round，各个TDMA周期的时隙划分是固定的。给定的节点可以按静态配置占据各个周期中的某个时隙，或占据集群中某个周期的固定时隙(虚拟时隙)；占据时隙的节点具有在总线上发送消息的能力，其他节点可以侦听接收到总线上的消息。

当没有数据需要发送时，传统的TTP网络的物理层处于MARK状态，对应于没有被消息占据的时隙，发送方发送填充字符，以保持码元同步；在更高的协议层次，这些填充对应于SAE AS6003标准规定的在没有数据帧(N帧)传输时填充发送初始化帧(I帧)[9]，尽管此时并不需要初始化操作。

对于实用的航电互连设计，为了保证全生命周期的可扩展性，总线利用率往往留有可观的余量。可以利用时间资源余量降低传输真正数据负载的能量消耗，且保证其不超出其应占据的时隙区间，这就契合了绿色航电的设计理念，而实现的难点在于找到一种复杂度可以接受的能量有效消息组织的方法。

由上说明，由于TTP总线是静态调度的，余量的利用不会影响可扩展性，当新型号的总线利用率提高时，重新设计调度表就可以释放已占用的余量。

1.2 SP静态分片模型

承载数据的N帧最长为240字节，包含不到4字节的协议开销(4 bit头部+CRC校验24 bit)。消息包含一个或多个应用数据单元，嵌入帧中；显然，当消息长度较长时，需要多条帧共同完成消息的发送，而数据单元的组织也为消息的分片提供了可能。TTP网络完全通过预设的调度表控制帧的发送时刻，并在接收端识别帧的类型。

文献[6]介绍了消息调度的4种组织方法，其中有静态调度方法，即静态单一消息(SM)、静态多消息(MM)两种消息分配模型；另外，还有动态调度方法，即动态消息(DM)和动态分片(DP)两种消息分配模型。经过对比，认为在精确的时钟同步基准下，如果将MM模型进一步扩展，事先将MM分片，同样通过静态的调度表控制各个分片的发送时刻，不仅可以利用分片调度的灵活性进一步提高可调度性，而且不必像DP调度那样付出动态决策的开销。

因此，提出静态分片模型(SP)，由于TTP帧的协议开销比例小，在调度表设计时可暂不考虑；实际工程中可以为每个时隙保留一定比例的开销余量，将仅含纯数据的消息封装为实际的帧，所以在本文中只考虑仅含纯数据的消息。SP模型的设计思路是消息在被发送到传输线之前，即被分成多个小分片，分别对分片进行调度组织。因为节点的时隙长度在每个round中都是一样的，并且时隙长度应当大于最长的消息长度，所以采用静态分片模型可以大大提高总线的利用率，并且更方便后面降频节能的实现。

1.3 能量有效消息调度

在保证通信性能的前提下动态调整数字电路的电平和频率，可以达到节能的目的[10]；考虑到总线传输抗干扰的特殊性，本文方法仅采用降频节能。

当有调度裕量存在时，传统的总线传输会用无意义的码元填充空闲时隙，这样在无效数据传输时仍然耗能。考虑到实时通信主要关注消息传输的截止期限，只要给定的消息能够在截止期限之前发送到总线上，即使拉长消息发送时间也可保证系统的性能，反之，提早完成传输没有收益而且会增加缓存的负担[10]。所以，只要能够保证正好按时完成总线上各个消息的传输，就有望适当、合理地动态降低码元发送频率。

动态降低码元发送频率增加了发送、接收器芯片实现的复杂度，为了在能量有效和实现复杂度之间获得权衡，本文方法规定(如图2所示)：1)当存在空闲时段，仅以偶数倍降低码元频率；2)只有在节点切换的边沿，频率才可以进行改变。

TTP总线上的各个节点加载静态的消息调度表，在精确时钟定时下对于降频节能方案具有一致的操作。

图2 降频调度图示Fig.2 Illustration of down-frequency scheduling

2 能量有效TTP消息调度方法

2.1 设计方案

本文设计的方案流程如图3所示。首先要设定节点数、各个节点的消息数以及消息周期和消息长度。在SP模型下，计算可用于降频节能的调度裕量数。在先不考虑调度裕量时，生成周期性消息调度表，然后通过组合优化得到调度裕量分配给各个节点的最佳分配方案，生成优化后的能量有效消息调度表。

值得说明的是，设SP模型下可允许的最小分片时间长度Tmin由设计给定；不失一般性，令Tmin=1，并以其为单位，对round、消息周期、截止期限等参数的时间长度进行归一化。

图3 总体方案流程图Fig.3 Flow chart of the overall scheme

2.2 调度裕量的计算方法

降低码元的发送频率，相当于拉长消息的长度，使之最接近它们的截止期限，就可以在保障调度性能的前提下降低功耗。设N个节点分时共享TTP总线的每个round，记为节点i(i=1，2，…，N)。设节点i的相对截止期限为Di，round的时间长度记为D*，集群中含有round的数目为R。设计要求D*≤min(Di)。

由节点i发送的消息由二元组〈Pi,m,Ci,m〉表示，其中，参数Pi,m和Ci,m分别表示节点i的第m种消息的周期和长度。

对于∀m，令Di≤Pi,m，对Pi,m进行规整

(1)

对于R的设定应当保证所有节点的所有消息都可以执行完，定义

(2)

在消息静态分片模型中，设消息是可以被分片的。以相同长度的分片大小同时对消息和时隙进行静态分片分配。分片长度T定义为

(3)

式中,n=⎣lbD*」，使得T∈[1,2)，使之尽可能接近Tmin。实际的分片长度T作为分配和利用调度裕量的单位，进而对消息长度规整为

(4)

如果不通过降频利用调度裕量，节点i在每个

round中发送消息必需的分片数目为

(5)

可以得到round中可用来进行降频节能操作的调度裕量数目为

(6)

2.3 周期性消息调度表生成

(7)

将集群周期内的round标记为r=1,2,…,R，时隙内的分片位置标记为g=1,2,…,Gi，则在节点i的时隙中任意分片的位置可用矩阵Sr×g表示。

节点消息分片调度安排算法如下。

andGi

Output:Sr×g,

(r=1,2,…,R;g=1,2,…,Gi)

fori=1 toNdo

fork=1 toKdo

num=0;

num=num+1;

end

else

break;

end

end

end

end

returnSr×g

算法中，通过find()函数进行检查，找到一组可行的位置，容纳周期性重复的分片，并使其第一个位置在可行条件下最靠近调度表的起始点。

节点消息分片调度安排如图4所示。其中，roundx(x=1,2,…,R)代表第x个round。相同颜色形状的方框是同一个消息的周期性调度安排。

图4 节点消息分片调度安排示意图Fig.4 Illustration of node message SP scheduling

2.4 能耗的计算

在SP模型下，由式(6)求得的调度裕量分片通过组合优化分配给各个节点，设各节点获得裕量分片个数分别为L1,…,Li,…,LN。当Li=0,1,…,L时，节点i耗能为Ei,Li。节点i在第x个round中消息分片数为li,x。

降低时序同步逻辑数字电路的电平和主频，都可以降低其动态功耗。由于降低总线电压在实现上有一定困难，所以本文采用降频节能的方法。设节点i分配得到Li个分片在第x个round中降频后的频率为fi,Li,x，参照文献[3]的式(4)，本文所讨论的li,x和Li相当于原文献中的平行度为1时每个调度元素的长度和分配给此调度元素的静态裕量，未降频的总线码速率即是公式中的频率fmax，可得

(8)

对li,x和Li以T为时间单位，并忽略常量fmax和转换电容Cef，设ei,Li为简化的Ei,Li，简化的算式为

(9)

虽然式(9)失去了物理量纲的意义，但并不影响组合优化问题的求解。下文中将ei,Li的单位统称为“能量单位”，进而可以得出所有节点的总耗能量为

(10)

2.5 调度裕量组合优化分配算法

(11)

得到最优的调度裕量分片的分配方案。常规可以采用混合整数线性规划(MILP)求解最优分配，但考虑到TTP的调度表是离线生成的，可以采用复杂度较高但易于理解的方法，先枚举计算各个节点的ei，Li,然后采用树结构递归[11]的方法求解式(11)。这里的算法伪代码如下所示。

Global variable：LandNand {L1，L2，…，LN} and Minenergy

treesearch (energysum,Li,i)

end

end

else

ifLi<=L-Lusethen

Compare and Update Minenergy andLi;

end

else

Li++;

treesearch(energysum,Li,i);

end

end

return{L1,L2,…,LN}。

3 案例研究

为了展示以能量有效为优化目标的消息调度表生成方法，这里选取某个节点数N为4的案例作为典型算例；随后再给出扩展节点数后能量有效TTP总线调度表优化结果。

3.1 典型算例

设节点消息数上限为10条，在实验中随机生成4个节点的消息数以及每条消息的周期值，取D*=minDi=minPi,m，根据式(1)将消息周期以D*为单位进行规整，如表1所示。

表1 规整后的消息周期(单位D*)Table 1 Regularized message cycle (the unit is D*)

根据式(4)将消息长度以调度分片T为单位进行规整，如表2所示,然后计算出所有消息长度所需要的分片数量以及剩余的调度分片裕量。本案例中round数R为36，一个round的分片数为32，4个节点所需要的分片数量分别为2，5，3，3。剩余的调度裕量L有19条。

表2 规整后的消息长度(单位T)Table 2 Regularized message length (the unit is T)

根据2.3节中节点周期性消息分片调度安排算法将节点的所有消息分片分配到各个节点时隙中。如图5所示的节点消息分片调度表，相同的颜色代表同一个消息类，白色表示没有消息，灰色用来分隔不同节点，每个分片中消息的高度代表频率，优化前还未降频节能，满格表示最高频率。

图5 节点消息分片调度表Fig.5 SP scheduling of node message

通过枚举法和树结构递归法求得不同调度裕量分配方案的耗能情况,如图6所示。

图6 不同调度裕量分配方案的耗能分布图Fig.6 Energy consumption distribution map of different scheduling slack allocation schemes

由图6可以看出,当分配给4个节点的调度裕量{L1,L2,L3,L4}={2,7,5,5}时，可以通过降频节能方法节省最多的能量。选择此分配方案并进行降频，得到能量有效优化节点消息调度表，如图7所示。

图7 能量有效优化节点消息调度表Fig.7 Energy-efficient optimal node message scheduling

通过式(10)、式(11)可以求得采用以能量有效为优化目标的消息调度表生成方法前后的能耗分别为232.0能量单位和38.4能量单位。

3.2 扩展案例

将典型算例中的节点个数由4节点扩展到8节点，其余不变。实验中得到调度裕量有5条，节点消息分片调度表和能量有效优化节点消息调度表如图8所示。

同样可以求得采用以能量有效为优化目标的消息调度表生成方法前后的能耗分别为367.9能量单位和181.1能量单位。

图8 8节点案例结果图Fig.8 The case result of 8 nodes

4 结论

本文结合“绿色航电”的理念提出一种以能量有效为优化目标的消息调度表生成方法，提出了静态分片分配方法，将调度裕量组合优化以耗能最小的分配方案分配给各个节点，从而达到合理降频节能的效果，并通过了仿真案例验证。针对本文的应用对象TTP总线，该方法可以保证消息的可调度性。

微小型智能片上系统的片间甚至片内的互连有望采用类似的时间触发总线的实时通信方式[7]，降频等数字电路节能方法对于集成电路效果更加明显[8]，本文方法有望对未来微小型智能航电系统的综合设计提供参考。

参考文献

[1] 陈长胜,刘智武,李晓庆,等.时间触发总线时钟同步技术研究[J].电光与控制,2017，24(6):74-78.

[2] TIANRAN Z,XIONG H.Design of energy-efficient hierarchical scheduling for integrated modular avionics systems[J].Chinese Journal of Aeronautics,2012,25(1):109-114.

[3]MISHRA R,RASTOGI N,ZHU D,et al.Energy aware scheduling for distributed real-time systems[C]//International Symposium on Parallel and Distributed Processing,IEEE Computer Society,2003.doi:10.1109/IPDPS.2003.1213099.

[4]POP P,POULSEN K,HARBO R,et al.Scheduling and voltage scaling for energy/reliability trade-offs in fault-to-lerant time-triggered embedded systems[C]//IEEE/ACM International Conference on Hardware/Software Codesign and System Synthesis,IEEE,2007:233-238.

[5]LI K,TANG X,LI K.Energy-efficient stochastic task scheduling on heterogeneous computing systems[J].IEEE Transactions on Parallel & Distributed Systems,2014,25(11):2867-2876.

[6] POP P,ELES P,PENG Z.Bus access optimization for

distributed embedded systems based on schedulability analysis[C]//Design,Automation and Test in Europe Conference and Exhibition,IEEE,2000:567-575.

[7] OLIVER R S,CRACIUNAS S S.Hierarchical scheduling over off-and on-chip deterministic networks[J].ACM SIGBED Review,2016,13(4):14-19.

[8] SCHOEBERL M.A time-triggered network-on-chip[C]//International Conference on Field Programmable Logic and Applications,IEEE,2007:377-382.

[9] SAE Aerospace.SAE AS6003 TTP communication protocol [S].[S.l.]:SAE International,2009.

[10] ZHAI B,BLAAUW D,SYLVESTER D,et al.The limit of dynamic voltage scaling and insomniac dynamic voltage scaling[J].IEEE Transactions on Very Large Scale Integration Systems,2005,13(11):1239-1252.

[11] 唐青松.深度优先算法在创建树形结构中的应用研究[J].计算机技术与发展,2014(9):226-229.