[發明專利]一種TTFC網絡的任務調度模型及消息調度表生成方法

有效

• 申請號: 201911012741.0
• 申請日: 2019-10-23
• 公開（公告）號: CN111030835B
• 公開（公告）日: 2022-08-09
• 發明（設計）人: 沈卓煒;汪德鳳;楊康;朱國家
• 申請（專利權）人: 東南大學
• 主分類號: H04L41/0896
• 分類號: H04L41/0896;H04L41/14;H04L41/12;H04L67/1097;H04L67/60
• 代理公司: 南京眾聯專利代理有限公司 32206
• 代理人: 薛雨妍

1.一種TTFC網絡的任務調度系統，其特征在于，綜合考慮運行在端系統上的計算任務和通過網絡進行數據交換的通信任務，支持TT任務和RC任務的描述及約束條件的表達，同時支持單播和多播應用，系統包括如下模塊：

模塊S11：描述TTFC網絡結構的網絡拓撲模型；

模塊S12：描述TTFC網絡中的TT任務、RC任務及其數據幀的任務模型、鏈路樹模型和數據幀模型；

所述模塊S12包括以下模型：

S121：任務模型；S122：鏈路樹模型、S123：數據幀模型；

S121、任務模型包括：TT任務和RC任務，

所述TT任務：

T_i＝{{T_i,1,T_i,2…T_i,n},T_i.Tr,T_i.p,T_i.D,T_i.rt,T_i.F_i}

其中，{T_i,1,T_i,2…T_i,n}表示T_i的子任務序列，子任務個數為n；T_i.Tr表示任務T_i所涉及的所有物理鏈路構成一棵鏈路樹；T_i.p表示任務T_i的周期；T_i.D表示任務T_i的截止期；T_i.rt表示任務T_i的響應時間，即任務T_i的最后一個子任務完成時間與周期開始時間之間的時長；T_i.F_i表示任務T_i產生的數據幀集合；其中任務T_i中的單個子任務T_i,j可表示為如下元組：

其中，表示任務T_i,j的偏移量；任意T_i,j.link＝[v_m,ν_n]∈E，當m≠n時，T_i,j.link＝[v_m,ν_n]表示通信子任務T_i,j的傳輸鏈路，當m＝n時，T_i,j.link＝[v_m,ν_m]表示計算子任務T_i,j在節點v_m上執行；任務T_i中，消息發送者端系統上的計算任務稱為消息的生產者子任務，消息接受者端系統上的計算任務稱為消息的消費者子任務；在多播任務的情況，將一個任務T_i中所有的消費者子任務集合記為Tc_i；

T_i,j.c表示任務T_i,j的執行時間，當T_i,j.link＝[v_m,ν_m]時，T_i,j.c為WCET(Worst-caseExecution Time)，即最壞情況執行時間，運行于端系統v_a上的一個計算任務的執行時間記作：wcet(v_a)；當T_i,j.link＝[v_m,ν_n]時:其中F_i,s.L為當前任務數據幀長度，[v_m,ν_n].bw表示鏈路[v_m,ν_n]上的網絡帶寬，[v_m,ν_n].d表示鏈路延遲；T_i,j.p：表示任務T_i,j的周期，滿足關系：T_i,j.p＝T_i.p；

所述RC任務：

區別于強實時任務，系統中所有的RC(rate-constrained，速率受限)任務集合記為R，其中R_i∈R，是第i個任務；同TT消息相比，R_i可描述為：

R_i＝{{R_i,1,R_i,2…R_i,n},R_i.Tr,R_i.bw,R_i.BAG,R_i.F_i}

其中，{R_i,1,R_i,2…R_i,n}表示RC任務R_i的子任務；R_i.Tr表示任務R_i所涉及的所有物理鏈路構成一棵鏈路樹；R_i.bw表示任務R_i的帶寬；R_i.BAG表示任務R_i的最小幀間隙，即任務R_i發送兩個連續幀的起始二進制位之間的最小間隔；R_i.F_i：表示任務R_i產生的數據幀集合；

其中任務R_i中的單個任務R_i,j可表示為如下元組：

其中，表示任務R_i,j的偏移量；任意R_i,j.link＝[v_m,ν_n]∈E，當m≠n時，R_i,j.link＝[v_m,ν_n]表示通信子任務R_i,j的傳輸鏈路，當m＝n時，R_i,j.link＝[v_m,ν_m]表示計算子任務T_i,j在節點v_m上執行；R_i,j.c表示任務R_i,j的執行時間，當R_i,j.link＝[v_m,ν_m]時，R_i,j.c為WCET(Worst-case Execution Time)，即最壞情況執行時間，其執行時間長度同TT任務；當R_i,j.link＝[v_m,ν_n]時:其中F_i,s.L為當前RC任務數據幀長度，[v_m,ν_n].bw表示鏈路[v_m,ν_n]上的網絡帶寬，[v_m,ν_n].d表示鏈路延遲；

S122、鏈路樹模型：

對一個應用程序任務來說，其產生的數據幀會在網絡鏈路上進行傳播；一個任務中所有通信子任務的link構成一棵鏈路樹；任務T_i對應的鏈路樹記為Ttr_i，樹中的頂點集合記為Ttr_i.V，邊的集合記為Ttr_i.E；同理，任務R_i對應的鏈路樹記為Rtr_i；任務系統中所有的鏈路樹構成的集合記為LT；

S123、數據幀模型：

定義任務Γ_i∈Γ產生的有序幀集合記為Fi，f_i,s表示任務Γ_i產生的第s個幀；f_i,s在鏈路[v_m,ν_n]上的傳輸記為可用如下元組表示：

其中，表示任務Γ_i產生的第s個幀在鏈路[v_m,ν_n]上的傳輸偏移量，即數據幀在鏈路上的發送時間；表示任務Γ_i產生的第s個幀在鏈路[v_m,ν_n]上的傳輸周期；表示任務Γ_i產生的第s個幀在鏈路[v_m,ν_n]上傳輸時的數據幀長度；網絡中所有任務的幀集合記為F，Fi在鏈路[v_m,ν_n]上的傳輸記為其中傳輸的最后一個幀記為

模塊S13：描述TTFC網絡中任務調度要求的一組任務調度模型約束條件。