本文關鍵詞： FPGA計算加速 最大空閑矩形 任務調度 硬件任務情境 硬件資源情境　出處：《上海大學》2012年博士論文　論文類型：學位論文

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

【參考文獻】

相關期刊論文 前10條

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

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

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

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

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

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

7 張宏烈;張國印;叢萬鎖;胡海燕;;一種應用圖論方法管理可重構資源的策略[J];計算機科學;2010年12期

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

9 許新達;徐成;劉彥;李仁發(fā);;基于可重構系統(tǒng)的亞可搶占任務調度算法[J];計算機工程;2011年06期

10 劉沙;周學功;王穎;王伶俐;;可重構系統(tǒng)在線任務預約重調度算法[J];計算機工程;2011年08期

相關博士學位論文 前1條

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

相關碩士學位論文 前1條

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

，

本文編號：1536322