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

【摘要】：高性能計(jì)算是一個(gè)國(guó)家的綜合國(guó)力的體現(xiàn)，是支撐國(guó)家實(shí)力持續(xù)發(fā)展的關(guān)鍵技術(shù)之一。近年來(lái)，高性能計(jì)算機(jī)體系結(jié)構(gòu)技術(shù)研究發(fā)生了改變，異構(gòu)體系結(jié)構(gòu)已成為未來(lái)高性能計(jì)算機(jī)發(fā)展的主要趨勢(shì)�；贔PGA的可重構(gòu)計(jì)算作為一種新的體系結(jié)構(gòu)，讓系統(tǒng)擁有了硬件的高性能，又具備了軟件的靈活性。通過(guò)采用主/協(xié)處理器技術(shù)，將計(jì)算的任務(wù)交由計(jì)算加速部件以硬件任務(wù)完成，而任務(wù)管理等，則交由通用處理器來(lái)完成，達(dá)到一個(gè)優(yōu)化的計(jì)算效果。 本文主要對(duì)基于FPGA計(jì)算加速的異構(gòu)高性能計(jì)算架構(gòu)上的任務(wù)與資源管理算法與計(jì)算模型方面的研究。在研究與分析當(dāng)前高性能計(jì)算體系結(jié)構(gòu)的發(fā)展趨勢(shì)的基礎(chǔ)上，以異構(gòu)高性能計(jì)算平臺(tái)為研究目標(biāo)，結(jié)合FPGA計(jì)算加速，通過(guò)對(duì)多體問(wèn)題（N-body）求解的FMM算法在FPGA計(jì)算加速的加速效果，通過(guò)分析FPGA加速上的計(jì)算性能效果，提出了多級(jí)加速優(yōu)化方案與對(duì)應(yīng)的計(jì)算架構(gòu)。 資源管理是任務(wù)調(diào)度研究的基礎(chǔ)，通過(guò)研究查找空閑矩形空間的算法來(lái)遍歷這些最大的空閑空間矩形MFR全集，本文分別以基于狀態(tài)矩陣模型與運(yùn)行任務(wù)邊線模型來(lái)研究MFR全集查找與管理算法。為有效查找與管理MFR全集，在基于資源狀態(tài)矩陣模型中提出了基于雙向倒形塔的MFR全集掃描求解算法，并在此基礎(chǔ)了又給出掃描優(yōu)化算法與M值標(biāo)示優(yōu)化算法。在基于運(yùn)行任務(wù)邊線模型上，提出了基于上右邊線交點(diǎn)CPTR的全集MFR查找算法，并給出了在線調(diào)度時(shí)的基于FPGA局部影響空間上的MFR全集更新算法。 高性能計(jì)算平臺(tái)多是屬于商業(yè)應(yīng)用計(jì)算平臺(tái)，要為眾多的高性能計(jì)算用戶提供計(jì)算服務(wù)，針對(duì)高性能計(jì)算平臺(tái)的多級(jí)任務(wù)調(diào)度模型，提出了基于本地資源FPGA上的時(shí)間與空間情境CBTA的多情境狀態(tài)的硬件任務(wù)放置與調(diào)度算法體系，并根據(jù)設(shè)置的不同的任務(wù)情境與資源情境狀態(tài)，提出了多種不同的適應(yīng)于任務(wù)與資源情境狀態(tài)下的任務(wù)調(diào)度與放置算法。采用讓每個(gè)計(jì)算資源節(jié)點(diǎn)根據(jù)自己的資源情境狀態(tài)變化，而主動(dòng)去選擇對(duì)應(yīng)自己情境的任務(wù)的自適應(yīng)任務(wù)調(diào)度策略，并給出了CBTA調(diào)度算法的并行優(yōu)化策略。最后通過(guò)實(shí)驗(yàn)來(lái)說(shuō)明了算法在對(duì)用戶響應(yīng)時(shí)間、負(fù)載均衡以及任務(wù)拒絕率上的優(yōu)勢(shì)。
[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é)位級(jí)別】：博士
【學(xué)位授予年份】：2012
【分類號(hào)】：TP38;TN791

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：1536322