可重構系統中實時任務容錯調度算法
2009-01-01 00:00:00殷進勇顧國昌吳艷霞
計算機應用研究 2009年5期
(哈爾濱工程大學 計算機科學與技術學院 哈爾濱 150001)
摘 要：現在FPGA已被廣泛的應用，但三模冗余(TMR)結構不能充分利用FPGA資源，基于主/從版本技術，提出一種實時任務容錯調度算法。算法通過后向調度從版本，使得從版本在其截止期限內盡可能地推遲執行，從而同一任務的主從版本在執行時間上沒有重疊或較少重疊，當任務主版本成功執行時釋放任務從版本所占用的資源。仿真實驗表明，與TMR相比，此方法能更有效地利用FPGA資源，提高硬件任務的接受率。
關鍵詞：可重構計算； 實時調度； 容錯調度； 放置策略
中圖分類號：TP316文獻標志碼：A
文章編號：1001-3695(2009)05-1729-04
Faulttolerant scheduling algorithm of realtime tasks for reconfigurable system
YIN Jinyong GU Guochang WU Yanxia
(College of Computer Science Technology Harbin Engineering University Harbin 150001 China)
Abstract:FPGA has been used widely now but the architecture of TMR(triple module redundancy) can not make full use of FPGA. This paper proposeda faulttolerant scheduling algorithm of hardware realtime tasks based on primary/slave copy. By scheduled backwards the salve copy executed as late as possible before its deadline. So that the primary copy had no overlap or as small overlap as possible with the slave copy on the executing time. When the primary copy executed successfully released the slave copy. The result of experiment demonstrates that the method can use the FPGA more efficiently than TMR and the accept ratio of hardware tasks increases.
Key words：reconfigurable computing; realtime scheduling; faulttolerant scheduling; placement scheme
0 引言
近年來，FPGA被廣泛地使用，針對FPGA的容錯處理有了專門的研究，主要分為基于硬件和基于軟件兩類。第一類仍然沿著硬件冗余思路，在FPGA芯片內設置備用資源實現容錯，如果某處資源損壞，就用備用資源進行置換[1]。另一些研究則通過設計特殊硬件結構以簡化資源置換過程。文獻[2]提出一種基于配置數據移動的方案，通過對SRAM進行特殊設計，配置數據能在行間、列間以及I/O模塊之間移動。出現故障時，失效資源的配置數據將根據特定規則被轉移到鄰近空閑資源上，使系統恢復正常。第二類基于軟硬件協同容錯方法，首先對FPGA芯片進行檢測，并將損壞情況存入數據庫，隨后進行邏輯映射時，從數據庫讀取檢測結果，保證損壞部分不被使用，最后重新布局布線，使FPGA恢復正常運行[3]。但這些方案在檢測FPGA芯片時要求系統停止工作，降低了系統性能和靈活性。因此研究人員又提出一種在線檢測和動態重構方案，能在系統正常工作時實現容錯處理[4，5]。以上這些方案主要是針對非實時系統提出的離線或在線故障檢測，不能保證任務實時性。
當前的可重構器件不僅提供了大量的可編程邏輯單元，還具備了部分可重構的能力，也就是在一部分邏輯單元正在運行的同時可以對另一部分邏輯單元進行配置，而對正在運行的部分沒有影響。為充分利用可重構硬件資源、提高開發效率，需要操作系統對硬件任務和可重構資源進行有效的管理[6]。
本文通過任務調度的方法實現故障容錯，使實時任務在其截止期限內完成。實時任務包括主/從兩個版本，主版本采用雙模冗余進行在線故障檢測，當任務主版本所使用的可重構單元出現故障時，則啟動對應的任務從版本，否則撤銷任務從版本的執行。在進行任務調度時，盡量使任務的主/從版本在執行時間上沒有重疊，這樣有利于提高可重構器件的利用率和硬件任務的接受率。本文相繼給出了系統的模型、算法的詳細設計，最后由仿真實驗驗證了算法的有效性。
1 系統模型
系統由一個主處理器和一個可重構器件組成，如圖1所示。
可重構器件包含一定數量的可重構單元(RCU)，形成一個二維矩陣。主處理器中運行的操作系統負責管理可重構資源。操作系統包括到達任務隊列、已調度任務隊列、待加載任務隊列等數據結構以及調度器、放置器、加載器等模塊。已調度任務和待加載任務可用一個有向無環圖(DAG)來表示任務之間的優先約束關系。
G=(V，E)
其中：V＝{Ti｜Ti為硬件任務，i＝1，2，…，n，n為任務數目}；E＝{eij｜eij為任務Ti到Tj的邊，Ti稱為Tj的前驅任務，Tj稱為Ti的后繼任務}。
pred(Ti)={Tj｜eji∈E}，表示任務Ti的所有前驅任務。succ(Ti)={Tj｜eij∈E}，表示任務Ti的所有后繼任務。如果Ti沒有前驅任務，則Ti為開始任務；如果Ti沒有后繼任務，則Ti為結束任務。
到達系統的實時任務存放在到達任務隊列中等待調度。調度器調用放置器找到合適的任務放置位置，并確定任務的啟動時間，不能在截止期前完成的任務則被拒絕，被接收的任務進入已調度任務隊列。待加載任務為G中的開始任務，當待加載的任務Ti加載完畢時，succ(Ti)將進入待加載任務隊列。如圖2所示，T1、T5為待加載任務，其余為已調度任務。當T1加載完畢時，T2、T3成為待加載任務。
當有新任務到達系統時，調度器根據某種調度策略重新調度已調度任務，但待加載的任務不再參與調度。通過這種方式，調度算法的時間復雜性雖然有一定的增加，但并不影響可重構器件的運行，保證了硬件任務的實時性。待加載的任務由加載器在其啟動時間將其加載到可重構器件中運行。
在目前的技術條件下，硬件任務的上下文切換還難以實現，因此模型中采用非搶占調度，任務在加載后不間斷地運行到結束。由于可重構器件出現故障的概率很小，任務的從版本盡量晚調度，以便能夠接收更多的任務主版本，提高任務的接收率。
硬件任務在可重構器件上的映射方式具有一維與二維、動態與靜態劃分等多種模型。本文采用動態二維模型，即任意大小的矩形硬件任務可以放置在器件上的任意位置。其原因是該模型最為靈活，能夠充分利用可重構器件。
可重構器件RC(W，H)由N=W×H 個可重構單元構成，形成一個W列H行的二維矩形陣列，器件中的每個RCU都是相同的。每個單元具有一個坐標位置〈x，y〉(1≤x≤W，1≤y≤H)分別代表RCU所在的列和行。子區域S(w，h)(1≤w≤W，1≤h≤H)表示器件中的一個w列h行的矩形區域。子區域在器件中的位置由其左下角和右上角RCU 的坐標表示：〈x1，y1，x2，y2〉。其中x2=x1+w-1，y2= y1+h-1。子區域左下角位置〈x1，y1〉稱為子區域的基點。
任務是一個兩元組T=(Tp，Tb)，Tp、Tb分別表示任務的主版本和從版本。Tp、Tb可用一個六元組 (w，h，a，e，D，d)來表示。其中w是寬度，h是高度，a是到達時間，e是執行時間，D 是相對截止期限，d是絕對截止期限，簡記為t(w，h)。
任務在運行時需要占用一個子區域S(w，h)，調度器為任務確定啟動時間s和放置位置。對已調度的任務記為t(x1，y1，x2，y2，s，f)。其中〈x1，y1，x2，y2〉確定了放置區域，f=s+e是任務的結束時間。對任務的有效調度必須保證在器件上同時運行的各個任務所占用的子區域不能重疊。
2 算法設計
在主/從版本備份技術中，從版本的運行方式可分為被動運行方式和主動運行方式。被動運行是指在實時任務的主版本不能正確執行時，才啟動從版本運行；而主動運行方式同時運行主版本和從版本，在主版本不能執行時，從版本仍然繼續執行，保證正確的輸出結果，但在系統無故障情況下浪費了計算資源。本文綜合運用兩種運行方式，算法盡量早地調度任務主版本，盡量晚地調度任務從版本。如果主從版本在運行時間上存在重疊，則從版本為主動從版本；否則為被動從版本。
可重構系統的實時任務調度與一般的任務調度有一定的區別，它不僅要考慮實時任務的運行時間問題，還要考慮任務的放置位置問題。
2.1 相關概念
定義1 任務的有效調度。對于一個被調度任務t(w，h，a，e，D，d)，如果對它的一個調度t(x1，y1，x2，y2，s，f )滿足以下四個條件，則稱其為t的有效調度。
a)放置位置有效
1≤x1≤W∧1≤y1≤H∧1≤x2≤W∧1≤y2≤H∧x2=
x1+w-1∧y2=y1+h-1
b)啟動時間合理
s≥a
c)滿足截止期
s+e≤d
d)時空不重疊
對于已調度任務t(x′1，y′1，x′2，y′2，s′ f′)
x1＞x′2∨x′1＞x2∨y1＞y′2∨y′1∨＞y2∨s＞f ′∨s′1＞f
定義2 運行任務和預約任務。假定當前時間為ct，一個調度后的任務t(x1，y1，x2，y2，s，f )如果已開始運行，即s≤ct＜f，則稱為運行任務；若t尚未開始運行，即ct＜s，則稱t為預約任務。
定義3 有效區域。對于任務t(w，h)，稱At=(1，1，W-w+1，H-h+1)為任務t的有效區域，即任務t必須以At內的點為放置基點才有可能是一個有效調度。
定義4 覆蓋區域。對于已調度任務B(x1，y1，x2，y2，s，f)和任務t(w，h)，稱CBt =(xc，yc，x2，y2)為任務t對B的覆蓋域。其中xc=max(1，x1-w+1)，yc=max(1，y1-h+1)。如果任務t的基點落在CBt內，則稱任務t覆蓋任務B，記為t＞B。
定義5 RCU的最早有效時間。可重構單元u∈At 對任務t的最早有效時間為EAt(u)=min{s｜任務t以單元u為基點，s為啟動時間的調度滿足有效調度的條件a)b)d)}。
定義6 RCU的最遲有效時間。可重構單元u∈At 對任務t的最遲有效時間為LAt(u)=max{s｜ 任務t以單元u為基點，s為啟動時間的調度滿足有效調度的條件a)c)d)}。
2.2 算法設計
調度算法維護著三個隊列，即EL、SL和LL，分別保存當前的運行任務、已調度任務和待加載任務。二維數組ELA[Wa ，Ha]用來保存EA矩陣或LA矩陣，EA矩陣和LA矩陣分別表示每個可重構單元的最早有效時間和最遲有效時間。本節設計了四個算法，分別用于確定任務的放置位置和啟動時間。ComputeEA和computeLA算法計算可重構單元的最早有效時間和最遲有效時間，確定任務主版本和從版本的放置位置。Schedule和FTSchedule算法完成任務的調度和容錯調度。
文獻[7]中的RCU最早有效時間的算法沒有考慮任務的調度策略，按照任務的先來先服務(FCFS)方式計算可重構單元的最早有效時間。本文算法可以采用不同的任務調度策略，如最早截止期限優先(EDF)等。算法描述如下：
computeEA(t(w，h，a，e，D，d))
{
for all 〈x，y〉∈At do
ELA [x，y] ←a
for all E(x1，x2，y1，y2，s，f)∈EL do
for all 〈x，y〉∈CEt∩At do
if ELA[x，y]＜f then ELA[x，y]←f
for all L(x1，x2，y1，y2，s，f)∈LL do
for all 〈x，y〉∈CLt∩At do
if ELA[x，y]＜f then ELA[x，y]←f
for all S(x1 x2 y1 y2 s f)∈SL do
for all〈x，y〉∈CSt∩At do
if ELA[x，y]＜f and ELA[x，y]+e＞s
then ELA[x，y] ←f
}
算法首先為數組賦予初始值a，這是每個可重構單元的最早有效時間；隨后依次處理EL、LL和SL任務隊列；算法結束時，每個可重構單元的最早有效時間被記錄到ELA中。
為了提高任務的接收率，應使任務從版本在其截止期內盡可能地推遲執行，現給出RCU的最遲有效時間算法。其中EL和LL按照任務結束時間的降序排列，SL按照任務啟動時間的降序排列。算法描述如下：
computeLA(t(w，h，a，e，D，d))
{
for all 〈x，y〉∈At do
ELA[x，y] ←de
for all S(x1 x2 y1 y2 s f)∈SL do
for all 〈x，y〉∈CSt∩At do
if ELA [x，y]＜f and ELA[x，y]＞se
then ELA [x，y] ←se
for all L(x1 x2 y1 y2 s f)∈LL do
for all 〈x，y〉∈CLt∩At do
if ELA [x，y]＜fthen ELA[x，y] ←-1
for all E(x1 x2 y1 y2 s f)∈EL do
for all 〈x，y〉∈CEt∩At do
if ELA [x，y]＜f then ELA[x，y] ←-1
}
算法首先進行初始化操作，為ELA數組的每個單元賦予初始值de，這是每個可重構單元的最遲有效時間。采用后向調度技術使得任務從版本的釋放時間達到最遲。算法依次處理已調度任務隊列、待加載任務隊列和運行任務隊列，如果任務t的調度與現有的任務相沖突，則任務t的最遲允許開始時間提前，從而在算法結束時，ELA數組中保存了每個可重構單元的最遲有效時間。
調度算法分為schedule算法和FTSchedule算法兩部分。Schedule算法是對任務的主版本或從版本的調度；FTSchedule是對實時任務的容錯調度。算法分別描述如下：
schedule(τ)
{
BSL=SL∪{τ}；
SL=；
sort(BSL)；
t=BSL.getHead();
while(t!=1)
{
if(t是任務主版本)
{
computeEA(t)；
{s CL} ←findCandidate(t)；
if (s>de)
{
return 1；
}
〈xy〉←findBase(CL)；
addSL(txys)；
}
if(t是任務從版本)
{
computeLA(t)；
{s CL} ←findCandidate(t)；
if (s＜a)
{
return 1；
}
〈x y〉←findBase(CL)；
addSL(t x y s)；
}
t=BSL.getNext( );
} // end while
return true；
}
Schedule算法中，τ為任務的主版本或從版本，返回1表示任務不可調度，返回true表示調度成功。BSL為一個臨時隊列，用于保存SL和任務τ。Sort()按照某種調度策略(如EDF等)對任務排序；如果t為主版本則findCandidate(t)找出ELA矩陣的最小數值，否則findCandidate(t)找出ELA矩陣的最大數值作為任務t的預啟動時間s，ELA中所有數值等于s的單元作為候選單元放在列表CL中；findBase()按照一定的放置策略確定放置任務的基點；addSL()將任務t加入到已調度任務集合SL中。
FTSchedule(T(Tp，Tb))
{
if(schedule(Tp)==1)
{
return 1;
}
if(schedule(Tb)==1)
{
return 1;
}
return true;
}
FTSchedule為容錯調度算法。算法首先調度任務的主版本，再調度任務的從版本。如果返回true表示調度成功；否則調度失敗。
3 算法仿真
可重構器件按照Xilinx Virtex5LX330 的規模定義，具有240×108個RCU。生成的模擬任務按面積分為三類 分別記為C30、C40和C50。其中Cn的寬度和高度在區間[5，n ]內均勻分布，以C50為例，80%以上的任務面積在50~1 250，這與現有的可重構IP核的面積基本符合。任務的運行時間在[5，50]個時間單元內均勻分布；任務的相對截止期限在[200，300]內均勻分布。
器件負載率對于調度成功率影響很大，本文通過控制任務到達系統的頻率來控制器件的負載率，任務到達系統的時間為參數為λ的泊松流。在生成任務時，首先生成一組任務的寬度、高度、運行時間和松弛時間，最后以參數為λ確定任務到達系統的時間。
任務的主版本采用雙模冗余法進行故障檢測，其結構如圖3所示，從版本沒有冗余模塊。假設可重構器件的故障到達間隔有一個最小值，使得任務主版本因故障失效時，任務從版本能夠順利執行。
每個任務組包含1 000個任務，對于每個不同的面積類和不同的負載率生成100 組任務，將各組任務模擬數據的平均值作為評估結果，并與三模冗余(TMR)進行比較，結果如圖4所示。其中FTS(fault tolerant schedule)為本文算法。
從圖4可以看出 與TMR相比，FTS明顯地提高了任務的接受率。主要因為，如果采用TMR方式，硬件實時任務它所需的可重構器件面積為原來的三倍。采用FTS方式，任務的主版本所需的可重構器件面積為原來的兩倍；從版本沒有變化，并且任務主版本順利執行時，從版本被釋放。因此，節省了可重構器件資源，提高了硬件任務的接受率。
4 結束語
目前采用調度技術對可重構器件進行容錯的研究還較少，本文研究了可重構器件中的實時任務在線容錯調度問題，提出了實時任務容錯調度算法。硬件實時任務包括主版本和從版本兩種。算法首先調度任務的主版本，如果主版本運行失敗，則調度任務的從版本；否則釋放從版本所占的可重構器件資源。在調度任務從版本時，采用后向調度技術，即從任務的絕對截止期限向前調度，使得任務從版本的釋放時間達到最遲，以便接收更多的任務主版本。實驗結果表明，與TMR方法相比，此方法有效地利用可重構器件資源，提高了硬件任務的接受率。
本文模型還比較簡單，今后的研究將針對實際的FPGA 器件和可重構應用系統改進問題模型，如硬件任務與軟件任務聯合調度、考慮任務配置時間以及考慮任務間的通信開銷等。
參考文獻：
［1］CHAPMAN G H DUFOET B. Using laser defect avoidance to build largearea FPGAs[J]. IEEE Design Test of Computers1998，15(4): 75-81.
[2]DOUMAR A KANEKO S ITO H. Defect and fault tolerance FPGAs by shifting the configuration data[C]//Proc of the 14th International Symposium on Defect and FaultTolerance in VLSI Systems. Washington DC:IEEE Computer Society，1999: 377-385.
[3]HANCHEK F DUTT S. Methodologies for tolerating cell and interconnect faults in FPGAs[J]. IEEE Trans on Computers 1998，47(9):15-33.
[4]ABRAMOVICI M STROUD C WIJESURIYA S，et al. Using roving STARs for online testing and diagnosis of FPGAs in faulttolerant applications[C]//Proc of IEEE International Test Conference. 1999: 973-982.
[5]EMMERT J STROUND C SKAGGS B et al. Dynamic fault tolerance in FPGAs via partial reconfiguration[C]//Proc of IEEE Symposium on FieldProgrammable Custom Computing Machines. Washington DC:IEEE Computer Society 2000: 165-174.
[6]周博，王石記，邱衛東，等. SHUM2UCOS : 基于統一多任務模型可重構系統的實時操作系統[J]. 計算機學報 2006，29(2):208-218.
[7]周學功，梁樑，黃勛章，等. 可重構系統中的實時任務在線調度與放置算法[J]. 計算機學報 2007，30(11):1901-1909.
