[發明專利]基于圖的遍歷的同步數據流系統節點參數快速處理方法

有效

• 申請號: 201310034095.4
• 申請日: 2013-01-29
• 公開（公告）號: CN103136334A
• 公開（公告）日: 2013-06-05
• 發明（設計）人: 龍翔;楊經緯;高小鵬;萬寒;姜博
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京永創新實專利事務所 11121
• 代理人: 周長琪

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執行，否則，結束本方法；

步驟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)。

3.根據權利要求1所述的同步數據流系統節點參數快速處理方法，其特征在于，所述的步驟12中判斷節點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’所在環的運行參數不滿足一致性要求。