本文關(guān)鍵詞： FPGA計算加速 最大空閑矩形 任務(wù)調(diào)度 硬件任務(wù)情境 硬件資源情境　出處：《上海大學(xué)》2012年博士論文　論文類型：學(xué)位論文

【摘要】：高性能計算是一個國家的綜合國力的體現(xiàn)，是支撐國家實力持續(xù)發(fā)展的關(guān)鍵技術(shù)之一。近年來，高性能計算機(jī)體系結(jié)構(gòu)技術(shù)研究發(fā)生了改變，異構(gòu)體系結(jié)構(gòu)已成為未來高性能計算機(jī)發(fā)展的主要趨勢�；贔PGA的可重構(gòu)計算作為一種新的體系結(jié)構(gòu)，讓系統(tǒng)擁有了硬件的高性能，又具備了軟件的靈活性。通過采用主/協(xié)處理器技術(shù)，將計算的任務(wù)交由計算加速部件以硬件任務(wù)完成，而任務(wù)管理等，則交由通用處理器來完成，達(dá)到一個優(yōu)化的計算效果。 本文主要對基于FPGA計算加速的異構(gòu)高性能計算架構(gòu)上的任務(wù)與資源管理算法與計算模型方面的研究。在研究與分析當(dāng)前高性能計算體系結(jié)構(gòu)的發(fā)展趨勢的基礎(chǔ)上，以異構(gòu)高性能計算平臺為研究目標(biāo)，結(jié)合FPGA計算加速，通過對多體問題（N-body）求解的FMM算法在FPGA計算加速的加速效果，通過分析FPGA加速上的計算性能效果，提出了多級加速優(yōu)化方案與對應(yīng)的計算架構(gòu)。 資源管理是任務(wù)調(diào)度研究的基礎(chǔ)，通過研究查找空閑矩形空間的算法來遍歷這些最大的空閑空間矩形MFR全集，本文分別以基于狀態(tài)矩陣模型與運行任務(wù)邊線模型來研究MFR全集查找與管理算法。為有效查找與管理MFR全集，在基于資源狀態(tài)矩陣模型中提出了基于雙向倒形塔的MFR全集掃描求解算法，并在此基礎(chǔ)了又給出掃描優(yōu)化算法與M值標(biāo)示優(yōu)化算法。在基于運行任務(wù)邊線模型上，提出了基于上右邊線交點CPTR的全集MFR查找算法，并給出了在線調(diào)度時的基于FPGA局部影響空間上的MFR全集更新算法。 高性能計算平臺多是屬于商業(yè)應(yīng)用計算平臺，要為眾多的高性能計算用戶提供計算服務(wù)，針對高性能計算平臺的多級任務(wù)調(diào)度模型，提出了基于本地資源FPGA上的時間與空間情境CBTA的多情境狀態(tài)的硬件任務(wù)放置與調(diào)度算法體系，并根據(jù)設(shè)置的不同的任務(wù)情境與資源情境狀態(tài)，提出了多種不同的適應(yīng)于任務(wù)與資源情境狀態(tài)下的任務(wù)調(diào)度與放置算法。采用讓每個計算資源節(jié)點根據(jù)自己的資源情境狀態(tài)變化，而主動去選擇對應(yīng)自己情境的任務(wù)的自適應(yīng)任務(wù)調(diào)度策略，并給出了CBTA調(diào)度算法的并行優(yōu)化策略。最后通過實驗來說明了算法在對用戶響應(yīng)時間、負(fù)載均衡以及任務(wù)拒絕率上的優(yōu)勢。
[Abstract]:High performance computing is the embodiment of a country's comprehensive national strength and one of the key technologies to support the sustainable development of national strength. In recent years, the research of high-performance computer architecture technology has changed. Heterogeneous architecture has become the main trend of the development of high-performance computers in the future. As a new architecture, reconfigurable computing based on FPGA enables the system to have the high performance of hardware. By using the master / coprocessor technology, the computing task is assigned to the computing acceleration unit to complete the hardware task, and the task management is handed over to the general purpose processor to achieve an optimized computing effect. In this paper, the task and resource management algorithms and computing models of heterogeneous high-performance computing architecture based on FPGA computing acceleration are studied, based on the research and analysis of the development trend of current high-performance computing architecture. Taking heterogeneous high performance computing platform as the research goal, combining with the acceleration of FPGA computation, the acceleration effect of FMM algorithm for solving multibody problem (N-body) in FPGA computation is analyzed, and the computational performance effect on FPGA acceleration is analyzed. A multilevel acceleration optimization scheme and its corresponding computing framework are proposed. Resource management is the foundation of task scheduling. By studying the algorithm of finding free rectangular space, we can traverse these maximal free space rectangular MFR complete sets. In this paper, based on the state matrix model and the running task edge-line model, we study the MFR complete set lookup and management algorithm, in order to find and manage the MFR complete set effectively. Based on the resource state matrix model, the MFR full set scanning algorithm based on the bidirectional inverted tower is proposed, and the scan optimization algorithm and the M value marking optimization algorithm are also given. On the basis of the run-time task boundary line model, the scanning optimization algorithm and the M value marking optimization algorithm are presented. In this paper, a full set MFR lookup algorithm based on the intersection point CPTR of the upper and right line is proposed, and the MFR complete set updating algorithm based on the local influence space of FPGA in the online scheduling is also presented. The high performance computing platform belongs to the commercial application computing platform. It is necessary to provide computing services for many high performance computing users, aiming at the multilevel task scheduling model of the high performance computing platform. This paper proposes a hardware task placement and scheduling algorithm system based on time and space situation CBTA on local resource FPGA, and according to the different task situation and resource situation state, the hardware task placement and scheduling algorithm system based on local resource FPGA is proposed. In this paper, a variety of task scheduling and placement algorithms are proposed, which are suitable for task and resource situation, and each computing resource node is asked to change according to its own resource situation. Meanwhile, the adaptive task scheduling strategy of the task corresponding to their own situation is chosen, and the parallel optimization strategy of the CBTA scheduling algorithm is given. Finally, the response time of the algorithm to the user is illustrated by experiments. The advantages of load balancing and task rejection rates.
【學(xué)位授予單位】：上海大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2012
【分類號】：TP38;TN791

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 Mike Strickland;;FPGA協(xié)處理的進(jìn)展[J];今日電子;2010年04期

2 齊驥;李曦;胡楠;周學(xué)海;龔育昌;王峰;;基于硬件任務(wù)頂點的可重構(gòu)系統(tǒng)資源管理算法[J];電子學(xué)報;2006年11期

3 王握文;陳明;;“天河一號”超級計算機(jī)系統(tǒng)研制[J];國防科技;2009年06期

4 李濤;楊愚魯;;可重構(gòu)資源管理及硬件任務(wù)布局的算法研究[J];計算機(jī)研究與發(fā)展;2008年02期

5 劉彥;李仁發(fā);許新達(dá);徐成;;一種異構(gòu)可重構(gòu)片上系統(tǒng)的實時任務(wù)調(diào)度算法[J];計算機(jī)研究與發(fā)展;2010年06期

6 余國良;伍衛(wèi)國;楊志華;錢德沛;;一種采用邊界表進(jìn)行可重構(gòu)資源管理及硬件任務(wù)調(diào)度的算法[J];計算機(jī)研究與發(fā)展;2011年04期

7 張宏烈;張國印;叢萬鎖;胡海燕;;一種應(yīng)用圖論方法管理可重構(gòu)資源的策略[J];計算機(jī)科學(xué);2010年12期

8 李濤;楊愚魯;;基于最大空閑矩形的可重構(gòu)資源管理方法[J];計算機(jī)工程;2008年03期

9 許新達(dá);徐成;劉彥;李仁發(fā);;基于可重構(gòu)系統(tǒng)的亞可搶占任務(wù)調(diào)度算法[J];計算機(jī)工程;2011年06期

10 劉沙;周學(xué)功;王穎;王伶俐;;可重構(gòu)系統(tǒng)在線任務(wù)預(yù)約重調(diào)度算法[J];計算機(jī)工程;2011年08期

相關(guān)博士學(xué)位論文 前1條

1 劉勇;嵌入式可重構(gòu)計算系統(tǒng)及其任務(wù)調(diào)度機(jī)制的研究[D];中國科學(xué)院研究生院（上海微系統(tǒng)與信息技術(shù)研究所）;2006年

相關(guān)碩士學(xué)位論文 前1條

1 馮德貴;支持硬件任務(wù)可搶占的CPU/FPGA混合架構(gòu)的軟硬件任務(wù)遷移研究[D];浙江大學(xué);2010年

，

本文編號：1536322