[發明專利]適用于開放式數控系統周期性依賴任務的低功耗調度方法

有效

• 申請號: 201911354473.0
• 申請日: 2019-12-25
• 公開（公告）號: CN113031522B
• 公開（公告）日: 2022-05-31
• 發明（設計）人: 郭銳鋒;彭阿珍;胡毅;吳昊天;王楚婷
• 申請（專利權）人: 沈陽高精數控智能技術股份有限公司
• 主分類號: G05B19/408
• 分類號: G05B19/408
• 代理公司: 沈陽科苑專利商標代理有限公司 21002
• 代理人: 許宗富

本發明公開一種適用于開放式數控系統周期性依賴任務的低功耗調度方法，其步驟如下：步驟1：初始化遺傳算法參數；步驟2：采用有向無環圖對周期性依賴任務進行建模；步驟3：建立調度任務的目標函數，設定約束條件，得到最優化模型；步驟4：用改進的遺傳算法求解最優化模型，得到任務調度序列及處理器需要配置的供電電壓。本發明考慮了任務的周期性依賴關系，設計了能夠保持任務拓撲結構的初始種群生成算法和交叉操作，與其他算法相比，不僅具有更快的搜索速度而且最優解對應的調度方案具有更低的能耗。本發明對遺傳算法產生的最優個體進行變鄰域搜索，以提高算法的局部搜索能力，該算法在保證系統可調度性的前提下，可有效降低系統能耗。

技術領域

本發明涉及多核平臺實時系統領域任務的實時調度，具體的說是適用于開放式數控系統周期性依賴任務的低功耗調度方法。

背景技術

開放式數控系統作為一種典型的實時系統，其關鍵功能均由實時任務實現。數控系統不僅要求在截止期限內完成任務，而且要保證任務的正確執行。隨著數控系統中各種功能需求的增加，多核處理器的應用越來越廣泛。與單處理器相比，任務在多核平臺上的調度需要考慮處理器間遷移、通信等行為，因此系統能耗也相應的越來越高。高能耗產生的高熱量會影響處理器的使用壽命，還會造成資源浪費，進而影響環境。這對調度算法提出了新的要求：在保證任務在其截止期限前完成的前提下，盡可能的降低系統能耗。

由于多核平臺上的調度問題是NP-hard的，目前許多學者采用智能啟發式算法來解決多核平臺上的低能耗調度問題，其本質是將任務調度問題形式化的描述為具有一些優先約束的最優化問題，通過啟發式搜索算法找到問題的近似最優解。

Kim H等人在其發表的論文“Communication-aware task scheduling andvoltage selection for total energy minimization in a multiprocessor systemusing Ant Colony Optimization”提出一種基于蟻群算法的低能耗調度算法，算法采用具有總能耗的全局啟發信息和具有處理器間通信量的局部啟發信息對解空間進行隨機決策搜索，并通過標準化總能耗來更新信息素軌跡。該方法由于未考慮任務之間的依賴關系，所以并不適用于多核平臺數控系統。

發明內容

針對現有多核平臺上低功耗調度算法的不足，本發明提出一種適用于開放式數控系統中周期性依賴任務的節能調度方法，該方法首先用有向無環圖對周期性依賴任務進行建模，接著對調度問題進行形式化的描述，將其抽象為具有一些約束條件的最優化問題，并設計了能夠保持任務拓撲結構的初始生成方法以及交叉操作，并采用變鄰域搜索算法拓展搜索范圍，找到局部最優解，實現多核處理器系統上任務的快速分配及低功耗目標。

適用于開放式數控系統周期性依賴任務的低功耗調度方法，包括以下步驟：

步驟1：初始化遺傳算法參數；

步驟2：采用有向無環圖對周期性依賴任務進行建模；

步驟3：建立調度任務的目標函數，設定約束條件，得到最優化模型；

步驟4：用改進的遺傳算法求解最優化模型，得到任務調度序列及處理器需要配置的供電電壓。

所述遺傳算法參數，包括：總迭代次數為Max_gen、種群規模為P_size、交叉概率為P_C、變異概率為P_M、迭代次數為R。

所述最優化模型包括：當系統滿足約束條件時，找到最優的任務調度序列及處理器電壓，使得系統總能耗E最小；

最小化：

約束條件：