基于图的遍历的同步数据流系统节点参数快速处理方法

摘要

本发明公开了一种基于图的遍历的同步数据流(SDF)系统节点参数快速处理方法，该方法为实时系统构建SDF图，图中每条边的两端标注所连接节点在该边上的通信参数，建立一个堆栈存储SDF图遍历过程需要暂存的节点，然后选定SDF中任意一个节点并初始化其运行参数，然后开始扫描，在对每一个节点进行扫描的过程中可以判断图中是否存在环，如果存在则进行运行参数一致性判断，否则基于节点通信参数确定该节点的运行参数，并对图中已扫描过的节点的运行参数进行全局归一化调整。本发明方法处理步骤少，计算量小，效率高，计算结果准确，具备处理不同属性参数的通用化特点，提高了计算机处理实时SDF系统节点运行参数的速度和效率。

权利要求

1.一种基于图的遍历的同步数据流系统节点参数快速处理方法，其特征在于，包括如下步骤：步骤1：为实时系统构建同步数据流(SDF)图，SDF图中每个节点表示单个计算任务，节点间边的两端标注所连接节点在该边上的通信参数，所述的通信参数为通信频率或者通信周期；

步骤2：初始化设置，设定SDF图中的所有节点的运行参数的值为0，所有的边为未扫描状态；

步骤3：初始化堆栈Stack为空；

步骤4：选定SDF中任一节点，标记为v，设定节点v的运行参数res(v)=1；

步骤5：判断节点v是否还有未扫描的邻边，若有，取其中一个未扫描的邻边e，进入步骤6执行，否则，执行步骤13；

步骤6：将未扫描的邻边e标记为已扫描；

步骤7：将与邻边e相连的另一个节点标记为v’；

步骤8：判断节点v’的运行参数res(v’)是否为0，若是，执行步骤9，否则，图中存在环，执行步骤12；

步骤9：将节点v’压入堆栈Stack；

步骤10：确定节点v在邻边e上的通信参数val(v,e)和节点v’在邻边e上的通信参数val(v’,e)的最大公约数gcd，然后更新节点v和节点v’在邻边e上的通信参数：val(v,e)=val(v,e)/gcd；val(v’,e)=val(v’,e)/gcd；

步骤11：确定节点v在邻边e上的通信参数val(v,e)与节点v的运行参数res(v)的最小公倍数lcm，然后更新SDF图中已经取得运行参数值的每个节点vo的运行参数：res(vo)=res(vo)*lcm/res(v)，最后确定节点v’的运行参数res(v’)=val(v’,e)*lcm/val(v,e)；转步骤5执行；

步骤12：判断节点v和节点v’所在环的运行参数是否满足一致性要求，若是，转步骤5执行，否则，结束本方法；

判断节点v和节点v’所在环的运行参数是否满足一致性要求，具体是：设节点v’在环中通过边es连接节点vs，通过边ed连接节点vd，根据节点vs的运行参数和节点v’、vs在边es上的通信参数得到节点v’的运行参数res’(v’)，根据节点vd的运行参数和节点v’、vd在边ed上的通信参数得到节点v’的运行参数res(v’)，判断res’(v’)与res(v’)是否相等，若相等，则节点v和节点v’所在环的运行参数满足一致性要求，若不相等，则节点v和节点v’所在环的运行参数不满足一致性要求；

步骤13：判断堆栈Stack中是否还有节点，若有，执行步骤14，否则结束本方法；

步骤14：从堆栈Stack中弹出栈顶节点，并设该节点为v，然后转步骤5执行。

2.根据权利要求1所述的同步数据流系统节点参数快速处理方法，其特征在于，所述的步骤1中边上的通信参数的初始设置方法为：设邻边e的两顶点分别为src(e)和snk(e)，src(e)为源节点，每运行一次往邻边e上发送prd(e)个元数据，snk(e)为目的节点，每运行一次从邻边e上读取cns(e)个元数据；当通信参数为通信周期时，设置节点src(e)在邻边e上的通信周期val(src(e),e)=prd(e)，节点snk(e)在邻边e上的通信周期val(snk(e),e)=cns(e)；当通信参数为通信频率时，设置节点src(e)在邻边e上的通信频率val(src(e),e)=cns(e)，节点snk(e)在邻边e上的通信频率val(snk(e),e)=prd(e)。

说明书

基于图的遍历的同步数据流系统节点参数快速处理方法

技术领域

[0001] 本发明涉及实时系统调度中同步数据流系统模型的构建，具体涉及一种同步数据流(Synchronous Data Flow，简写为SDF)系统模型中节点参数的快速处理方法。

背景技术

[0002] SDF系统模型由Berkeley的Edward Ashford Lee博士于1987年提出，其主要面向DSP应用而对各计算单元(节点)及其通信行为进行建模和分析。在SDF模型中，程序或者系统被划分为多个模块，模块之间具有数据通信关系，每个模块在需求的数据经由数据通路到达之后便开始执行。程序由数据流图方式描述，该数据流图为有向图，图中的节点表示模块，而节点之间的有向边则表示模块之间的数据通路，每条有向边的头部标注所连接节点运行一次从该通路提取的数据量，而有向边的尾部标注所连接节点运行一次往该通路上发送的数据量。与传统数据流系统不同的是，SDF所描述的节点之间的数据通信行为模式是固定的，即节点每运行一次所消耗或者产生的数据量固定，系统的运行行为在编译时就可以确定，因此可以有效避免运行时开销，并提高系统资源利用效率。除了DSP之外，SDF模型还被大量用于其他具有实时性要求的通用系统(CPU)建模分析，分析的目标主要在于确定节点的运行频率及运行周期等重要参数，该过程成为实时系统调度分析最为关键和耗时的环节之一，虽然目前已经被集成到计算机辅助开发环境，但是仍有诸多值得改进之处。

[0003] 目前，大多数基于SDF模型的实时系统的数学分析往往根据计算节点的互联结构及通信参数(数据生产率、数据消耗率)建立相应的拓扑矩阵，然后求解该拓扑矩阵的零空间向量，从而得出每个节点的运行次数(频率)需求，并以此为基础，经过一系列处理过程后确定各节点的运行周期，为系统的实时调度提供参数依据。SDF模型分析过程中常用的零空间向量等效求解方法包括解方程法和图的遍历法方式，解方程法由于需要消耗大量的处理器时间，人们更倾向于采用图的遍历法。无论采用何种方法，对于实时任务运行周期的处理，往往是通过先确定任务的运行频率，然后依据所有任务的频率对各个任务的周期展开全局关联推导，该种方法过于迂回且浪费计算资源，需要加以改进。另外，在现有的图遍历法中，系统节点运行参数的处理过程与可调度性分析过程是分开进行的，对于不满足可调度性要求的系统，由于无法在处理过程中发现其参数的非一致性并提前终止计算，从而对计算资源造成不必要的浪费。对于功能复杂的系统(如航电系统、汽车电子)，由于系统模块众多，节点数据量较为庞大，解方程法具有结果不准确、耗时严重、可扩展性差等劣势，而已有图遍历法也显示出存储需求量大的短处。

发明内容

[0004] 本发明针对传统SDF系统模型图中节点参数处理方法存在资源浪费、结果不准确、耗时严重、存储需求量大等问题，提供了一种基于图的遍历的同步数据流系统节点参数快速处理方法，以提高计算机在处理相应问题时的性能和效率。

[0005] 本发明提供的基于图的遍历的同步数据流系统节点参数快速处理方法，包括如下步骤：

[0006] 步骤1：为实时系统构建SDF图，SDF图中每个节点表示单个计算任务，节点间边的两端标注所连接节点在该边上的通信参数，所述的通信参数为通信频率或者通信周期。所述的通信频率表示两个相连节点在单位时间内各自需要完成的通信次数；所述的通信周期表示每个节点完成一次通信需要的单位时间数。

[0007] 步骤2：初始化设置，设定SDF图中的所有节点的运行参数的值为0，所有的边为未扫描状态。

[0008] 步骤3：初始化堆栈Stack为空，堆栈Stack用于存储在SDF图遍历过程中需要暂存的节点。

[0009] 步骤4：选定SDF中任一节点，标记为v，设定节点v的运行参数res(v)=1。

[0010] 步骤5：判断节点v是否还有未扫描的邻边，若有，取其中一个未扫描的邻边e，进入步骤6执行，否则，执行步骤13。

[0011] 步骤6：将未扫描的邻边e标记为已扫描。

[0012] 步骤7：将与边e相连的另一个节点标记为v’。

[0013] 步骤8：判断节点v’的运行参数res(v’)是否为0，若是，执行步骤9，否则，图中存在环，执行步骤12。

[0014] 步骤9：将节点v’压入堆栈Stack。

[0015] 步骤10：更新节点v和节点v’的通信参数：确定节点v在边e上的通信参数val(v,e)和节点v’在边e上的通信参数val(v’,e)的最大公约数gcd；然后更新节点v和节点v’在边e上的通信参数：val(v,e)=val(v,e)/gcd；val(v’,e)=val(v’,e)/gcd。

[0016] 步骤11：根据通信参数比值关系，将v与v’之间在边e上的通信参数与已经求得的节点运行参数进行全局归一化调整并得到运行参数。具体方法是：确定节点v在边e上的通信参数val(v,e)与节点v的运行参数res(v)的最小公倍数lcm；更新SDF图G中已经取得运行参数值的每个节点vo的运行参数：res(vo)=res(vo)*lcm/res(v)；确定节点v’的运行参数res(v’)=val(v’,e)*lcm/val(v,e)。转至步骤5执行。

[0017] 步骤12：判断节点v和节点v’所在环的运行参数是否满足一致性要求，若是，转步骤5执行，否则，结束本方法。

[0018] 步骤13：判断堆栈Stack中是否还有节点，若有，执行步骤14，否则结束本方法。

[0019] 步骤14：从堆栈Stack中弹出栈顶节点，并设该节点为v，然后转步骤5执行。

[0020] 本发明方法的优点和积极效果在于：

[0021] （1）本发明方法所构建的SDF图中，在边上输入节点通信参数，具有节点通信参数类型多样化的优势，通过本发明方法不仅可以处理节点运行频率，还可以处理节点运行周期以及其他属性参数，具有通用化的益处。

[0022] （2）本发明方法在遍历SDF图并处理各节点运行参数的过程中可以同时检测环的存在并验证环上节点参数的一致性，在具体处理过程中，若发现SDF中存在不满足参数一致性要求的环则可以及时停止处理过程，避免后续不必要的参数计算，提高系统效率。

[0023] （3）传统SDF模型在处理节点运行周期的过程中，一般基于节点通信速率先确定系统中每个节点运行频率，然后再以此为依据，利用实时任务的运行周期与频率的关系，通过最小公倍数法依次得到每个节点的运行周期。而在本发明方法中，节点的通信周期被直接做为普适参数输入处理过程，最终得出的结果即为节点运行周期，避免了不必要的额外计算过程，加快计算进程，提高了计算机处理速度和效率。

[0024] （4）本发明方法的中间结果全部为整数，避免了解方程过程中小数结果造成的数据精度丢失。在基于SDF图遍历的处理过程中，节点参数的计算结果往往采用分数形式保存，以确保精度不丢失，需要占用分子和分母两个整数存储空间。而本发明在具体对各节点参数进行处理过程中，由于及时进行全局归一化调整，避免了分数的出现，每个节点只需要一个整数值保存中间结果，根据每一步最新计算需求对已得到的节点运行参数进行迭代更新，以时间换取空间，在保证了计算结果严格准确的情况下将其对存储空间的需求降为传统方法的一半，对于节点规模较大、存储空间紧张等情况下的实时系统建模分析具有一定的现实意义。

附图说明

[0025] 图1为本发明SDF节点参数处理系统运行流程图；

[0026] 图2为本发明的SDF节点参数快速处理方法的步骤流程图；

[0027] 图3为本发明实施例所构建的SDF的示例图；

[0028] 图4为本发明实施例进行运行周期参数一致性判断的示例图；

[0029] 图5为本发明实施例进行运行频率参数一致性判断的示例图；

[0030] 图6为采用本发明实施例中采用本发明方法遍历SDF图处理节点运行参数示例图；其中，图6-1为由节点v1起始并扫描节点v2的示意图，图6-2为扫描节点v3的示意图，图6-3为检测节点v1、v2、v3运行参数一致性的示意图，图6-4为扫描节点v6的示意图，图6-5为扫描节点v4的示意图，图6-6为扫描节点v5示意图。

具体实施方式

[0031] 在下述具体实施示例中，结合附图对本发明进行进一步的详细说明。通过足够详细的描述这些实施示例，使得本领域技术人员能够理解和实践本发明。在不脱离本发明的主旨和范围的情况下，可以对实施做出逻辑的、实现的和其他的改变。因此，以下详细说明不应该被理解为限制意义，本发明的范围仅仅由权利要求来限定。

[0032] 如图1所示，为依据本发明方法构建的SDF节点参数处理系统运行流程图，构建SDF节点参数处理系统包括如下模块：SDF节点拓扑结构及参数输入、节点运行参数求解、SDF图中环的检测、节点参数一致性检测以及SDF节点运行参数输出。其中，SDF图中环的检测以及节点参数一致性检测依据SDF节点拓扑结构而定，不是必需的。采用本发明方法，事先依据应用特性构建改进型的SDF图以描述应用系统中的每个节点及其通信行为，根据要处理的内容，输入各边上相应的节点通信参数。如处理目标为节点运行频率时，则输入节点的通信频率，如处理目标为运行周期，则输入节点的通信周期，如要同时处理二种参数，由于二者之间的相关性，只需输入其中一种通信参数，待求得相应运行参数之后即可推导另一种运行参数。

[0033] 如图2所示，为本发明的基于图的遍历的同步数据流系统节点参数快速处理方法的步骤。

[0034] 步骤1：为实时系统构建SDF图，SDF图中每个节点表示单个计算任务，SDF图中节点间边的两端标注所连接节点在该边上的通信参数，通信参数为通信频率或者通信周期。

[0035] 本发明对实时系统各计算节点及节点间通信展开建模，每个节点为周期性实时任务，有固定的运行周期或频率约束，具备通信关系的节点间以无向边或有向边相连。边的两端标注所连接节点在该边上的通信频率，或者通信周期，分别表示两个相连节点在单位时间内各自需要完成的通信次数以及每个节点完成一次通信需要的单位时间数，这不同于传统SDF图中仅能在有向边上标注一种量纲数据：通信速率(运行一次生产/消耗的数据)。本发明方法中SDF图各边上的参数的主要特性是面向通信而非计算，且具有局部化的特点，无法直接反映各节点的全局运行属性，因此需要通过图的遍历及相应计算将通信属性转换为运行属性，且进行全局归一化调整。SDF图用符号G表示，SDF图中涉及的符号及其含义如表1所示：

[0036] 表1SDF图所用符号及其含义

[0037]符号 含义 符号 含义
V G中节点集合 E G中边的集合
v 节点 e 边
res(v) v的运行参数(周期、频率等) src(e) e的源节点
val(v,e) 节点v在边e上的通信参数(周期、频率等) snk(e) e的目的节点
gcd(a,b) 整数a、b的最大公约数 lcm(a,b) 整数a、b的最小公倍数

[0038] 以处理节点运行周期为例，在边e两端需要设置通信周期。SDF图中的边e上相邻两顶点分别为src(e)、snk(e)，节点的数据生产率和消耗率分别为prd(e)和cns(e)，意思是：src(e)为源节点，每运行一次往信道e上发送prd(e)个元数据，snk(e)为目的节点，每运行一次从信道e上读取cns(e)个元数据。为了将e上的数据平均存储量维持在一个常量，保证通信缓冲区不出现溢出或者不足现象，边e的两顶点在边e上的通信（运行）周期比值val(src(e),e)/val(snk(e),e)等于prd(e)/cns(e)。这样一来，可以设节点src(e)与边e完成一次通信过程需要val(src(e),e)个时间单位，同时产生prd(e)个单位数据，而节点snk(e)与边e完成一次通信过程需要val(snk(e),e)个时间单位，同时消耗cns(e)个单位数据(后续描述中，如无特殊需要，对周期以及数据的描述不再特别交代相应的数值单位)，故而两个节点的通信速率(单位时间内传递的数据量)相等，即：prd(e)/val(src(e),e)=cns(e)/val(snk(e),e)，从而保证边e上通信缓冲区平均存储量的恒定性。因此SDF图中e上相应的局部通信周期参数可初始化设置如下：

[0039] val(src(e),e)=prd(e),val(snk(e),e)=cns(e)。

[0040] 当边e上的通信参数标注为通信频率时，初始设置方法为：设置节点src(e)在边e上的通信频率val(src(e),e)=cns(e)，节点snk(e)在边e上的通信频率val(snk(e),e)=prd(e)。无论本发明方法是为了处理节点运行周期还是运行频率，在完成相应通信参数的初始化之后，其后续过程是一致的。

[0041] 本发明方法的目的是：根据所构造的SDF图G以及输入的相关通信参数val(v,e)，确定SDF图G中各节点的运行参数res(v)。在完成SDF图构建以及边上通信参数输入之后，任选SDF图中的一个节点为出发点，基于深度优先与广度优先混合的策略对SDF图中各节点进行遍历搜索，计算相应运行参数。

[0042] 步骤2：初始化设置，设定SDF图中的所有节点的运行参数的值为0，即设置所有节点的运行参数向量res(V)=[0,0,0,…,0]。设定SDF图中的所有的边为未扫描状态。

[0043] 步骤3：初始化堆栈Stack为空。堆栈Stack用于存储在SDF图遍历过程中需要暂存的节点。在遍历过程中扫描完与当前节点相连的某个节点之后，将其压入堆栈，然后继续扫描与当前节点相连的其他节点并压入堆栈，待扫描完所有与当前节点相连的节点之后，弹出栈顶节点，并以其为出发点继续按照以上策略扫描其他节点。如此往复，直至堆栈中没有节点(或图中所有节点扫描完毕)，则停止。

[0044] 步骤4：选定SDF中任意一节点v，设定该节点的运行参数res(v)=1。

[0045] 步骤5：判断节点v是否还有未扫描的邻边，若有，取其中一个未扫描的邻边e，执行步骤6，否则，执行步骤13。

[0046] 步骤6：将未扫描的邻边e标记为已扫描。

[0047] 步骤7：将与边e相连的另一个节点标记为v’。

[0048] 步骤8：判断节点v’的运行参数res(v’)是否为0，若是，执行步骤9，否则，图中存在环，执行步骤12。

[0049] 步骤9：将节点v’压入堆栈Stack。

[0050] 步骤10：更新节点v和节点v’的通信参数。具体方法是：

[0051] 步骤10-1：获取节点v和节点v’在边e上的通信参数val(v,e)和val(v’,e)，然后确定两个通信参数的最大公约数gcd：gcd=gcd(val(v,e),val(v’,e))；

[0052] 步骤10-2：更新节点v在边e上的通信参数val(v,e)=val(v,e)/gcd；

[0053] 步骤10-3：更新节点v’在边e上的通信参数val(v’,e)=val(v’,e)/gcd。

[0054] 步骤11：将v与v’之间的局部通信参数与已经求得的节点运行参数全局归一化调整并得到运行参数。具体方法是：

[0055] 步骤11-1：确定节点v在边e上的通信参数val(v,e)与节点v的运行参数res(v)的最小公倍数lcm：lcm=lcm(val(v,e),res(v))；

[0056] 步骤11-2：更新SDF图G中已经取得运行参数值的每个节点vo的运行参数：res(vo)=res(vo)*lcm/res(v)；已经取得运行参数值的节点是指当前G中所有运行参数值不为0的节点；

[0057] 步骤11-3：确定节点v’的运行参数res(v’)=val(v’,e)*lcm/val(v,e)。转至步骤5执行。

[0058] 步骤12：判断节点v和节点v’所在环的运行参数是否满足一致性要求，若是，转步骤5执行，否则，结束本发明方法。

[0059] 由于SDF图中环上节点参数的一致性是满足实时应用系统可调度性要求的必要条件，因此在实时应用系统开发环境中，除了要计算节点运行参数之外，还需要测试位于环上的节点运行参数的一致性。判断节点v和节点v’所在环的运行参数是否满足一致性要求，具体是：设节点v’在环中通过边es连接节点vs，通过边ed连接节点vd，根据节点vs的运行参数和节点v’、vs在边es上的通信参数得到节点v’的运行参数res’(v’)，根据节点vd的运行参数和节点v’、vd在边ed上的通信参数得到节点v’的运行参数res(v’)，判断res’(v’)与res(v’)是否相等，若相等，则节点v和节点v’所在环的运行参数满足一致性要求，若不相等，则节点v和节点v’所在环的运行参数不满足一致性要求。

[0060] 如图4所示，为本发明方法中在边两端输入的为通信周期情况下的一致性判断示例图。图4是一个包括3个节点v1～v3的环，T1～T6为通信周期，在SDF图节点运行参数处理过程中，基于遍历搜索算法可以检测到该环的存在，假设节点v1的运行周期为t，通过边①上的通信参数的比值关系可知节点v2的运行周期为t*T2/T1，基于边③上的通信参数可得到节点v3的运行周期为t*T2/T1*T4/T3。基于节点v1的周期t和边②上的通信参数还可求得节点v3的运行周期为t*T5/T6，为了保持参数一致性，t*T2/T1*T4/T3=t*T5/T6必须成立，即：T1*T3*T5＝T2*T4*T6，对于图4中的示例，代入通信周期的值，就是判断1*3*4＝2*3*2是否成立，显然该示例中的环满足一致性要求。

[0061] 对本发明方法中在边两端输入的为通信频率情况下的一致性判断，与图4中的判断条件在原理上是一致的。如图5所示的示例，对于节点v1～v3形成的环，F1～F6为通信频率。设节点v1的运行频率为f，通过边①上的通信参数的比值关系可知节点v2的运行频率为f*F2/F1，基于边③上的通信参数可得到节点v3的运行频率为f*F2/F1*F4/F3，基于节点v1的运行频率f和边②上的通信参数求得节点v3的运行频率为f*F5/F6，为了保持参数一致性，f*F2/F1*F4/F3=f*F5/F6必须成立，即：F1*F3*F5＝F2*F4*F6，代入通信频率的值，就是判断2*3*2＝1*3*4是否成立，显然该示例中的环满足一致性要求。

[0062] 现有方法将参数计算及其一致性检测分开进行，先行计算SDF图中各节点参数，然后再统一测试各环上节点参数的一致性，一旦发现不满足一致性要求的环，则整个系统是不可调度的，之前的参数计算结果也没有任何意义，浪费了大量的处理器时间。基于效率的考虑，本发明方法在遍历并计算各节点运行参数的过程中可以同时检测环的存在并适时检测节点运行参数的一致性，在具体处理过程中，若发现SDF中存在不满足参数一致性条件的环，则可以及时停止计算，避免后续不必要的参数计算过程，提高了系统效率。

[0063] 步骤13：判断堆栈Stack中是否还有节点，若有，执行步骤14，否则结束本发明方法。

[0064] 步骤14：从堆栈Stack中弹出栈顶节点，并设该节点为v，然后转步骤5执行。

[0065] SDF分析的主要依据在于节点间的数据流通信，传统方法以SDF图及节点通信速率为输入，仅能实现节点运行频率的直接处理，本发明具有节点通信参数类型多样化的优势，同样的流程方法不仅可以处理节点运行频率，还可以处理节点运行周期以及其他属性参数，具有通用化的益处。

[0066] 以图3所示的为某实时系统构建的SDF图为例，该SDF图中共有6个实时任务节点v1～v6，节点间的互联关系以有向边表示，边的两端标注的数值(如1、2、3)为节点通信参数(本发明实施例中标注的为通信周期)，边的中间标注的为边序号(如①、②、③)。以处理各节点运行周期为例，如图6-1所示，随机选择节点v1为出发点对SDF图进行遍历，节点v1的运行周期res(v1)被设置为1。根据遍历规则，通过边①与节点v1连接的节点v2会被先扫描并被压栈，边①设为已扫描状态。val(v1,①)=1、val(v2,①)=2，节点v1和节点v2的通信周期比为val(v1,①)/val(v2,①)=1/2，由于节点的一次完整的通信行为伴随着一次完整运行过程而发生，通信周期即运行周期，所以有res(v1)/res(v2)=val(v1,①)/val(v2,①)。求解gcd(val(v1,①),val(v2,①))=gcd(1,2)=1，依次将节点v1、v2的在边①上的局部通信参数做如下更新：

[0067] val’(v1,①)=val(v1,①)/gcd(val(v1,①),val(v2,①))=1/1=1;

[0068] val’(v2,①)=val(v2,①)/gcd(val(v1,①),val(v2,①))=2/1=2。

[0069] 显然，这里res(v1)/res(v2)=val’(v1,①)/val’(v2,①)依然成立，节点v1和v2的运行周期可以初步预期为val’(v1,①)和val’(v2,①)，由于前面已经做了约简处理，因此可以保证两节点的预期周期值互质。但是这仅仅是一个预期的局部值，其最终结果还需要与已经求得的其他节点(包括节点v1自身)的运行参数进行全局归一化处理并更新，具体过程如下：

[0070] 求解节点v1的通信周期(亦即预期运行周期)val’(v1,①)与已经求得的运行周期res(v1)的最小公倍数lcm(val’(v1,①),res(v1))=lcm(1,1)=1，在此之后，对于已经得到的所有节点的运行周期按相同比例扩增如下：

[0071] res’(v1)=res(v1)*lcm(val’(v1,①),res(v1))/res(v1)=1*1=1；

[0072] …

[0073] res’(vn)=res(vn)*lcm(val’(v1,①),res(v1))/res(v1)；

[0074] 对于本发明实施例，当前仅得到v1的运行周期，所以仅更新v1的运行周期即可。

[0075] 根据通信参数比值关系，节点v2的运行周期计算如下：

[0076] res(v2)=val(v2,①)*lcm(val’(v1,①),res(v1))/val’(v1,①)=2*1/1=2。

[0077] 经过全局归一化的结果与局部预期值val’(1,①)，val’(2,①)一致。

[0078] 由于在处理过程中融入了最小公数和最大公约数的处理，因此可以保证求得的运行参数不会出现分数形式，且各参数之间互质。在具体实施过
程中，若lcm(val’(v1,①),res(v1))=res(v1)，则已经得到的节点的运行 周期无需全局归一化并更新，而节点v2的运行周期res(v2)=val(v2,①)*res(v1)/val’(v1,①)=res(v1)*val(v2,①)/val’(v1,①)=2。后续各节点的运行周期处理过程与此类似，如无特殊情况则不再具体描述，直接给出计算公式与结果。

[0079] 对于节点v1和v2来说，虽然运行周期已经确定，但是它们还各自与其他节点(如v3、v4、v5)具有通信关系，其最终运行周期还要分别满足与这些节点之间的比值约束关系。如图6-2，此时以节点v1为出发点，继续扫描其它邻接边，基于本发明的遍历策略，接下来系统会扫描到边②，设其状态为已扫描，通过边②找到节点v3并将其压栈，节点v3与节点v1的通信周期比值为val(v3,②)/val(v1,②)=4/2=2/1=2，节点v3的运行周期为：res(v3)=res(v1)*val(v3,②)/val(v1,②)=1*2=2。

[0080] 此时，节点v1已经没有未扫描的邻接边，接下来弹出堆栈的栈顶节点v3，并开始扫描通过边③与节点v3相连的节点v2，边③的状态设为已扫描。如图6-3，由于节点v2此前已经被扫描过，即res’(v2)≠0，因此节点v2不被压栈，但是通过节点v3可以得出节点v2的运行周期res(v2)=res(v3)*val(v2,③)/val(v3,③)=2*3/3=2。节点v2先前已经被扫描过说明图中存在环，将当前得到的res(v2)与先前计算得到的res’(v2)值相比较发现二者相等，因此环中节点参数满足一致性要求。如图4所示的判断方法进行一致性判断：

[0081] 根据节点v3和边③确定的节点v2的运行周期：

[0082] res(v2)=res(v3)*val(v2, ③ )/val(v3, ③ )=res(v1)*val(v3, ② )/val(v1,②)*val(v2,③)/val(v3,③)；

[0083] 根据节点v1和边①确定的节点v2的运行周期：

[0084] res’(v2)=res(v1)*val(v2,①)/val(v1,①)

[0085] 若res(v2)=res’(v2)，则有：

[0086] res(v1)*va l(v3, ② )/val( v1, ② )*val(v2, ③ ) /val(v3,③)=res(v1)*val(v2,①)/val(v1,①)

[0087] 化简并整理后得到：

[0088] val(v1,①)*val(v2,③)*val(v3,②)=val(v2,①)*val(v3,③)*val(v1,②)，此即：

[0089] T1*T3*T5=T2*T4*T6。

[0090] 可见res(v2)=res’(v2)与T1*T3*T5=T2*T4*T6等价。倘若发现上诉一致性约束不成立，即res(v2)≠res’(v2)，则此SDF描述的系统不满足可调度性必要条件，计算过程停止。

[0091] 完成节点v2的处理之后，根据遍历规则，接下来扫描通过边⑥与节点v3相连的节点v6，如图6-4，此时将边⑥设为已扫描，节点v6压栈，val(v6,⑥)=4，val(v3,⑥)=3，二者互质，约简后的结果不变，即：val’(v6,⑥)=4，val’(v3,⑥)=3，但是lcm(val’(v3,⑥),res(v3))=lcm(3,2)=6，与res(v3)的值不相等，节点运行参数需要进行全局归一化调整，因此节点v1、v2、v3的运行周期调整如下：

[0092] res(v1)=res(v1)*lcm(val’(v3,⑥),res(v3))/res(v3)=1*6/2=3;

[0093] res(v2)=res(v2)*lcm(val’(v3,⑥),res(v3))/res(v3)=2*6/2=6;

[0094] res(v3)=res(v3)*lcm(val’(v3,⑥),res(v3))/res(v3)=2*6/2=6;

[0095] 节点v6的运行周期计算结果如下：

[0096] res(v6)=val’(v6,⑥)*lcm(val’(v3,⑥),res(v3))/val(v3,⑥)=4*6/3=8。

[0097] 完成上述扫描之后，节点v3已经没有未扫描邻接边，弹出堆栈的栈顶节点v6，由于v6没有未扫描邻接边，接着弹出节点v2，对于节点v2来说，由于边①、③已经被扫描，接下来会扫描边④并找到节点v4，依照惯例，边④设为已扫描，节点v4压栈，如图6-5，在此之后可得到res(v4)=res(v2)*val(v4,④)/val(v2,④)=6*2/3=4。依次类推，接下来节点边⑤设为已扫描，节点v5压栈，其周期为res(v5)=res(v2)*val(v5,⑤)/val(v2,⑤)=6*3/2=9，如图6-6。

[0098] 至此，SDF图中各节点的运行周期处理完毕，但是还会继续运行，此时由于节点v2的所有邻接边已经被扫描完毕，弹出栈顶节点v5，但节点v5没有未扫描邻接边，继续弹栈得到节点v4，依然没有未扫描邻接边，此时栈已空，结束本方法。

[0099] 被处理系统满足实时系统可调度性，所有节点的运行周期如下：

[0100] [res(v1),res(v2),res(v3),res(v4),res(v5),res(v6)]=[3,6,6,4,9,8][0101] 各个节点参数为整数且相对互质，即最大公约数为1。对于运行频率，其处理过程也是如此。