基于局部可重構(gòu)計(jì)算的在線硬件任務(wù)調(diào)度算法研究.pdf

1、可重構(gòu)計(jì)算技術(shù)兼?zhèn)銩SIC的高性能和通用CPU的靈活性的雙重優(yōu)點(diǎn),能夠滿足各領(lǐng)域?qū)Ω咝阅苡?jì)算的迫切要求,已成為業(yè)界的研究熱點(diǎn)。目前,可重構(gòu)邏輯器件已經(jīng)具備局部可重構(gòu)的能力,能夠滿足現(xiàn)代計(jì)算系統(tǒng)高性能和多任務(wù)動態(tài)執(zhí)行的需求,同時(shí)對可重構(gòu)操作系統(tǒng)提出了新的要求。
　　 硬件任務(wù)調(diào)度是可重構(gòu)操作系統(tǒng)的核心技術(shù)。高效的硬件任務(wù)調(diào)度和放置是發(fā)揮局部可重構(gòu)計(jì)算技術(shù)優(yōu)勢最為關(guān)鍵的因素之一。為提高任務(wù)調(diào)度的性能,本文針對局部動態(tài)可重構(gòu)計(jì)算系統(tǒng)中

2、的在線硬件任務(wù)調(diào)度問題展開研究,通過對該領(lǐng)域現(xiàn)有的算法和成果進(jìn)行分析總結(jié),針對其中的一些缺陷與不足提出了自己改進(jìn)方案。論文的具體研究工作如下:
　　 首先,為改善現(xiàn)有資源管理算法隨著可重構(gòu)器件上任務(wù)數(shù)的增多而開銷驟增的缺點(diǎn),本文在已有相關(guān)矩陣模型基礎(chǔ)上,設(shè)計(jì)了一個(gè)基于區(qū)域劃分(Segmentation Algorithm,SA)的資源管理算法。SA屏蔽掉掃描區(qū)域中己被占用的區(qū)域,將大的掃描區(qū)域劃分成多個(gè)子區(qū)域進(jìn)行掃描,從而降低資

3、源管理的時(shí)間開銷。
　　 其次,通過對現(xiàn)有經(jīng)典算法的任務(wù)放置策略進(jìn)行分析,本文發(fā)現(xiàn)他們采用的代價(jià)函數(shù)皆與放置區(qū)域周邊己被占用的可重構(gòu)資源數(shù)量相關(guān)。本文對其加以綜合和簡化,證明了基于最大鄰接邊數(shù)(Max-Adjacent Sides,MAS)的放置策略能有效地降低可重構(gòu)資源的碎裂程度,從而提升任務(wù)的調(diào)度成功率和資源利用率。
　　 再次,由于基于可重構(gòu)邏輯器件的任務(wù)上下文切換開銷巨大,業(yè)界針對可重構(gòu)計(jì)算系統(tǒng)中搶占式內(nèi)核的相關(guān)

4、研究未能引起足夠重視,忽略了可重構(gòu)計(jì)算系統(tǒng)中預(yù)留任務(wù)的特殊屬性。本文利用系統(tǒng)中預(yù)留任務(wù)的特殊屬性,提出了一種亞可搶占任務(wù)調(diào)度算法(Secondary Preemptable Scheduling Algorithm,SPSA)。當(dāng)存在任務(wù)不能被成功調(diào)度時(shí),SPSA剝奪系統(tǒng)己分配給預(yù)留任務(wù)的可重構(gòu)資源,設(shè)計(jì)算法對這些任務(wù)進(jìn)行統(tǒng)一離線調(diào)度,以進(jìn)一步提高任務(wù)調(diào)度成功率和資源利用率。
　　 最后,為了驗(yàn)證本文算法思想的有效性,本文基于現(xiàn)