[發(fā)明專利]基于多核處理器和FPGA的軟硬件混合實(shí)時(shí)任務(wù)調(diào)度方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310460364.3
• 申請(qǐng)日: 2013-09-26
• 公開（公告）號(hào): CN103488531A
• 公開（公告）日: 2014-01-01
• 發(fā)明（設(shè)計(jì)）人: 殷進(jìn)勇;袁麗;曾瑋妮;宋漢廣;吳亮;徐振朋
• 申請(qǐng)（專利權(quán)）人: 中國(guó)船舶重工集團(tuán)公司第七一六研究所
• 主分類號(hào): G06F9/46
• 分類號(hào): G06F9/46;G06F9/50
• 代理公司: 南京理工大學(xué)專利中心 32203
• 代理人: 馬魯晉

技術(shù)領(lǐng)域

本發(fā)明涉及一種實(shí)時(shí)任務(wù)調(diào)度方法，特別是一種基于多核處理器和FPGA的周期性軟/硬件混合實(shí)時(shí)周期任務(wù)調(diào)度方法。

技術(shù)背景

由于FPGA具有可多次重新配置邏輯單元的功能和互連的特性，使系統(tǒng)兼具靈活性、高性能、高可靠、低能耗、低成本、易于升級(jí)等多種優(yōu)良特性，因此基于通用處理器和FPGA的可重構(gòu)計(jì)算填補(bǔ)了軟硬件之間的鴻溝，它不僅保持了硬件的高性能，同時(shí)還具有接近于軟件的靈活性。如何在基于多核處理器和FPGA的異構(gòu)平臺(tái)上調(diào)度軟/硬件混合實(shí)時(shí)任務(wù)已成為一個(gè)研究熱點(diǎn)，也是一個(gè)噬待解決的問題。

文獻(xiàn)《Online?scheduling?and?placement?of?real-time?tasks?to?partially?reconfigurable?devices》提出了一種硬件實(shí)時(shí)任務(wù)的調(diào)度和放置方法，但是它是針對(duì)硬件任務(wù)單一任務(wù)類型提出的，文獻(xiàn)《采用預(yù)配置策略的可重構(gòu)混合任務(wù)調(diào)度算法》提出了軟/硬件混合任務(wù)調(diào)度算法，算法采用預(yù)配置策略，降低了配置時(shí)間對(duì)任務(wù)執(zhí)行的影響，但沒有考慮任務(wù)的實(shí)時(shí)性。

殷進(jìn)勇在其博士論文《可重構(gòu)系統(tǒng)中實(shí)時(shí)任務(wù)調(diào)度算法研究》和《一種面向部分可重構(gòu)FPGA的混合實(shí)時(shí)任務(wù)調(diào)度算法》中對(duì)軟/硬件混合實(shí)時(shí)的調(diào)度進(jìn)行了探討，文中用一個(gè)有向無(wú)環(huán)圖表示軟件任務(wù)和硬件任務(wù)之間的約束關(guān)系，軟件任務(wù)和硬件任務(wù)均為強(qiáng)實(shí)時(shí)任務(wù)，沒有考慮硬件任務(wù)的配置時(shí)間對(duì)實(shí)時(shí)任務(wù)的影響，僅在理論上給出了軟/硬件混合實(shí)時(shí)任務(wù)可調(diào)度性判定方法和任務(wù)調(diào)度算法。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種基于多核處理器和FPGA的軟硬件混合實(shí)時(shí)任務(wù)調(diào)度方法。

實(shí)現(xiàn)本發(fā)明目的的技術(shù)方案為：一種基于多核處理器和FPGA的軟硬件混合實(shí)時(shí)任務(wù)調(diào)度方法，包括以下步驟：

步驟1、根據(jù)處理器核心數(shù)m，把實(shí)時(shí)任務(wù)集T={T₁，T₂，…，T_n}分成m組，使得每組的任務(wù)負(fù)載趨于平衡，其中和P_i分別表示任務(wù)T_i的軟件任務(wù)執(zhí)行時(shí)間，硬件任務(wù)執(zhí)行時(shí)間和相對(duì)截止期限；把實(shí)時(shí)任務(wù)集T={T₁，T₂，…，T_n}分成m組，m為處理器核心數(shù)，具體包括以下步驟：

步驟1-1、把任務(wù)集T={T₁，T₂，…，T_n}的實(shí)時(shí)任務(wù)按照硬件任務(wù)的最大寬度從大到小的順序排列；

步驟1-2、用G₁，G₂，…，G_m表示m個(gè)任務(wù)分組，初始值G₁=G₂=…=G_m=φ，用U₁，U₂，…，Um表示任務(wù)分組G₁，G₂，…，G_m已分配的任務(wù)負(fù)載，初始值U₁=U₂=…=U_m=0；

步驟1-3、從任務(wù)集T中取出硬件任務(wù)寬度最大的實(shí)時(shí)任務(wù)T_i分配給負(fù)載U_i最小的任務(wù)分組G_i，修改變量T=T-{T_i}，G_i=G_i+{T_i}，其中和和P_i分別表示實(shí)時(shí)任務(wù)T_j的硬件部分執(zhí)行時(shí)間、軟件部分執(zhí)行時(shí)間和周期；

步驟1-4、判斷實(shí)時(shí)任務(wù)是否分配完畢，如果實(shí)時(shí)任務(wù)集分配沒有分配完畢，即T≠φ，則轉(zhuǎn)返回步驟1-3，否則任務(wù)分組結(jié)束。

步驟2、判定步驟1中劃分的每組實(shí)時(shí)任務(wù)的可調(diào)度性，如果每組實(shí)時(shí)任務(wù)均可調(diào)度，則任務(wù)集T可調(diào)度，否則不可調(diào)度；

判定每組實(shí)時(shí)任務(wù)的可調(diào)度性，具體方法為：將每組實(shí)時(shí)任務(wù)按照截止期限從小到大的順序排列，如果每組都滿足以下不等式，則實(shí)時(shí)任務(wù)集T可調(diào)度：

其中l(wèi)表示分組中的實(shí)時(shí)任務(wù)個(gè)數(shù)，表示相對(duì)截止期限大于等于任務(wù)T_k的實(shí)時(shí)任務(wù)的硬件任務(wù)最長(zhǎng)執(zhí)行時(shí)間，和分別表示實(shí)時(shí)任務(wù)T_j的硬件部分執(zhí)行時(shí)間和軟件部分執(zhí)行時(shí)間，t表示時(shí)間。

步驟3、根據(jù)實(shí)時(shí)任務(wù)相對(duì)截止期限以及執(zhí)行時(shí)所在的處理器核心是否是分配的處理器核心，動(dòng)態(tài)地設(shè)置任務(wù)的優(yōu)先級(jí)；