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

摘要

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

主权项

一种基于图的遍历的同步数据流系统节点参数快速处理方法，其特征在于，包括如下步骤：步骤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’在环中通过边e_s连接节点v_s，通过边e_d连接节点v_d，根据节点v_s的运行参数和节点v’、v_s在边e_s上的通信参数得到节点v’的运行参数res’(v’)，根据节点v_d的运行参数和节点v’、v_d在边e_d上的通信参数得到节点v’的运行参数res(v’)，判断res’(v’)与res(v’)是否相等，若相等，则节点v和节点v’所在环的运行参数满足一致性要求，若不相等，则节点v和节点v’所在环的运行参数不满足一致性要求；步骤13：判断堆栈Stack中是否还有节点，若有，执行步骤14，否则结束本方法；步骤14：从堆栈Stack中弹出栈顶节点，并设该节点为v，然后转步骤5执行。