本文選題：流編程模型 + 可重構(gòu)眾核流處理器�。� 參考：《中國科學(xué)技術(shù)大學(xué)》2013年博士論文

【摘要】：半導(dǎo)體工藝的持續(xù)進步和流編程模型的提出是推動眾核流處理器體系結(jié)構(gòu)向前發(fā)展的兩個重要因素。為了充分利用摩爾定律發(fā)展帶來的豐富廉價的晶體管資源,片上多處理器已經(jīng)成為工業(yè)界所接受的新一代處理器體系結(jié)構(gòu)的解決方案之一。另一方面,流編程模型的提出為解決應(yīng)用程序并行性表示和開發(fā)提供了有利的工具,業(yè)已成為程序并行化的一般方法。但是流應(yīng)用程序本身的運行時特性對處理器資源的靈活可配置提出了新的要求。一方面,不同程序?qū)τ谟嬎?存儲和控制的硬件資源需求是千差萬別的；另一方面,有的程序?qū)τ谟布Y源的需求還表現(xiàn)出階段性特征,不同階段所需的硬件資源也不盡相同。為了解決這一問題,近年來可重構(gòu)眾核處理器體系結(jié)構(gòu)受到廣泛關(guān)注,期望以同構(gòu)的輕量級物理核來構(gòu)建不同粒度的邏輯處理器,自適應(yīng)地調(diào)整硬件資源,最大化串行程序的性能。我們基于以上認(rèn)識,提出了可重構(gòu)的眾核流處理器體系結(jié)構(gòu)TPA-S,旨在為流應(yīng)用程序提供片上資源靈活可重構(gòu)的硬件襯底。 本文圍繞這一體系結(jié)構(gòu),研究了以CUDA為代表的流編程模型在TPA-S上的編譯和程序優(yōu)化技術(shù),分別從可重構(gòu)流處理器的執(zhí)行模型,指令集擴展,編譯系統(tǒng)設(shè)計,以及程序優(yōu)化技術(shù)等方面展開研究。主要的研究內(nèi)容包括： (1)研究流編程模型與可重構(gòu)流體系結(jié)構(gòu)的執(zhí)行模型,探索流應(yīng)用程序在可重構(gòu)流處理器TPA-S上的映射方案。流編程模型的實質(zhì)在于控制和計算的分離：流程序中的計算密集部分以核心函數(shù)的形式被抽取出來,使用多個計算線程來開發(fā)數(shù)據(jù)級并行性；而控制線程專注于計算之外的控制流程序,為核心函數(shù)組織數(shù)據(jù)以及開發(fā)生產(chǎn)者-消費者局部性。我們設(shè)計了主從式和分階段式兩種程序映射方案,分別以異步和同步的方式將計算線程和控制線程映射到TPA-S的多個邏輯處理器上。另外,我們還提出了單一線程和組合線程這兩種核心函數(shù)的組織方式,在單線程性能和系統(tǒng)吞吐率之間尋求最佳平衡點。 (2)研究流編程模型對TPA-S指令集體系結(jié)構(gòu)產(chǎn)生的設(shè)計需求,提出擴展的類數(shù)據(jù)流EDGE指令集DISC-S。TPA-S流處理器基于顯式數(shù)據(jù)流圖執(zhí)行(EDGE)指令集,將程序的每個線程組織為原子執(zhí)行和提交的超塊序列,在超塊內(nèi)部按照類數(shù)據(jù)流方式執(zhí)行。EDGE指令集中特殊的目標(biāo)域編碼方式是TPA-S處理器實現(xiàn)物理核可重構(gòu)的基礎(chǔ)之一。然而流編程模型為TPA-S微結(jié)構(gòu)帶來了一些不包括在EDGE指令集中的新特性,例如：多個計算線程需要依靠只讀的特殊寄存器來快速地獲取線程索引信息；計算線程需要訪問軟件管理的片上共享存儲器數(shù)據(jù)；另外,多個線程之間需要實現(xiàn)高效的柵欄同步機制。DISC-S擴展指令集針對以上新特性,增加了對特殊寄存器讀寫,軟件管理的片上共享存儲層次以及線程間同步的指令支持,為實現(xiàn)流編程模型的映射帶來了方便。 (3)設(shè)計并實現(xiàn)面向CUDA編程語言的TPA-S編譯器系統(tǒng)。本文基于NVCC編譯框架將編譯器系統(tǒng)分為核心級與流級兩條編譯鏈。我們參考scale編譯器設(shè)計了核心級編譯器Ptx2EDGE,將PTX匯編語言形式的計算線程源代碼程序編譯成DISC-S擴展指令集的二進制目標(biāo)代碼。在流級,我們實現(xiàn)了CUDA C語法擴展和API函數(shù)接口以及運行時庫的移植,并復(fù)用scale串行編譯器產(chǎn)生控制線程代碼。編譯器系統(tǒng)設(shè)計的主要工作由一系列編譯模塊與工具軟件的代碼實現(xiàn)組成,包括PTX和CUDA語法的前端識別,中間表示形式轉(zhuǎn)換,超塊生成和優(yōu)化,資源分配與指令調(diào)度,匯編器與鏈接器等。另外,為了實現(xiàn)CUDA控制線程中設(shè)備管理,線程管理,執(zhí)行控制和存儲器管理等功能模塊,我們移植了CUDA運行時庫并實現(xiàn)了軟件運行時系統(tǒng)Mpsim。編譯系統(tǒng)的正確性和執(zhí)行效率通過實驗在一組基準(zhǔn)測試程序上進行了驗證與評測。 (4)研究了不規(guī)則程序在流處理器上的程序優(yōu)化方法。本文主要分析了眾核流處理器上不規(guī)則程序的性能瓶頸問題,并對GPU平臺上的圖廣度優(yōu)先搜索算法進行了實例研究,希望找到不規(guī)則程序在流處理器上進行性能調(diào)優(yōu)的一般性方法。我們針對不規(guī)則程序中復(fù)雜多變的無組織數(shù)據(jù)并行性提出了基于并行性反饋的FlexBFS高效實現(xiàn)方法,并針對不規(guī)則訪存帶來的動態(tài)隊列訪存效率問題以及不規(guī)則輸入引起的負載平衡問題,分別提出了相應(yīng)的程序優(yōu)化技術(shù)。這些實現(xiàn)方法和優(yōu)化技術(shù)都能夠被應(yīng)用到其它的不規(guī)則程序當(dāng)中。 本文獲得了以下重要認(rèn)識：(1)流編程模型能夠驅(qū)動指令集體系結(jié)構(gòu)的設(shè)計,ISA需要反映編程模型帶來的新特性；(2)流程序的多線程映射需要軟件運行時庫的協(xié)同工作,在將來的操作系統(tǒng)中可以增加對流編程模型的支持；(3)編譯系統(tǒng)設(shè)計環(huán)節(jié)需要使用合適的編程模式和軟件工程方法來增強程序的模塊化與可讀性,例如訪問者模式；(4)不規(guī)則程序的并行性開發(fā)需要準(zhǔn)確的并行性度量,使用在線剖析技術(shù)能夠指導(dǎo)計算資源的合理劃分。
[Abstract]:The continuous progress of the semiconductor process and the presentation of the flow programming model are two important factors to promote the development of the architecture of the core stream processor. In order to make full use of the rich and cheap transistor resources developed by Moore's law, the multiprocessor on chip has become a solution to the new generation of processor architecture received by the industry. One of the cases. On the other hand, the presentation of the flow programming model provides a favorable tool for solving the application parallelism representation and development. It has become a general method of program parallelization. However, the runtime characteristics of the flow application itself put forward new requirements for the flexible configuration of the processor resources. On the one hand, different programs are for computing, The requirements for storage and control of hardware resources are different. On the other hand, some programs also show phase characteristics for the requirements of hardware resources, and the hardware resources are not the same in different stages. In order to solve this problem, the reconfigurable architecture of the multiprocessor system has been widely concerned in recent years and is expected to be isomorphic with light weight. Level physical kernel constructs different granularity logic processors, adaptively adjusts hardware resources and maximizes the performance of serial programs. Based on the above knowledge, we propose a reconfigurable architecture of the public kernel flow processor architecture (TPA-S), which aims to provide flexible and reconfigurable hardware substrates for streaming applications.
This paper focuses on this architecture, and studies the compiler and program optimization techniques of the flow programming model represented by CUDA on the TPA-S. It studies the execution model of the reconfigurable flow processor, the instruction set extension, the design of the compiler system, and the optimization of the program. The main research contents include:
(1) to study the execution model of flow programming model and reconfigurable flow architecture, explore the mapping scheme of flow application on reconfigurable flow processor TPA-S. The essence of the flow programming model lies in the separation of control and calculation: the computing intensive part in the flow program is extracted by the form of the core function, and is developed using multiple computing threads. Data level parallelism; while the control thread concentrating on the control flow program outside the calculation, organizing the data for the core function and developing the producer consumer locality, we designed two program mapping schemes, the master-slave and the phased, mapping the computing threads and the control threads to the multiple logic of TPA-S in asynchronous and synchronous ways. In addition, we also propose the organization of the two core functions, single thread and combined thread, to find the best balance between single thread performance and system throughput.
(2) the design requirements of the flow programming model to the TPA-S instruction collective system structure are studied. The extended class data stream EDGE instruction set DISC-S.TPA-S stream processor is based on the explicit data stream graph execution (EDGE) instruction set, and each thread of the program is organized into the super block sequence of the atom execution and submission, and in the super block the class data stream is held in the way of the class data flow. The special target domain encoding method in the line.EDGE instruction set is one of the bases for the physical reconfiguration of the TPA-S processor. However, the flow programming model brings some new features that are not included in the EDGE instruction set for TPA-S microstructures, for example, multiple computing threads need to rely on the read-only special register to quickly obtain the thread indexed letters. The computing thread needs to access the shared memory data of the software managed by the software; in addition, multiple threads need to implement the efficient barrier synchronization mechanism.DISC-S extended instruction set for the above new features, increase the read-write to special registers, the shared storage layer on the software management, and the synchronization instruction support between threads. The mapping of current programming models is convenient.
(3) design and implement the TPA-S compiler system oriented to CUDA programming language. Based on the NVCC compiler framework, the compiler system is divided into two compiler chains at the core level and the stream level. We have designed the core compiler Ptx2EDGE with reference to the scale compiler, which compiles the computation line Cheng Yuan code program of the PTX assembly language into the DISC-S extended instruction set. At the stream level, we implemented the CUDA C syntax extension, the API function interface and the migration of the runtime library, and reused the scale serial compiler to produce the control thread code. The main work of the compiler system design consists of a series of compiler modules and the code implementation of the tool software, including the front-end recognition of the PTX and CUDA syntax. In addition, in order to realize the function modules such as device management, thread management, execution control and memory management in CUDA control threads, we transplant the CUDA runtime library and implement the positive Mpsim. compiler system of the software runtime system, in order to implement the function modules of the device management, thread management, execution control and memory management in the thread of the control. Accuracy and efficiency are tested and evaluated on a set of benchmark programs through experiments.
(4) the program optimization method of irregular program on stream processor is studied. This paper mainly analyzes the performance bottleneck of irregular programs on the public kernel stream processor, and studies the algorithm of map breadth first search on the GPU platform, hoping to find a general method for the performance tuning of irregular programs on the stream processor. We propose a FlexBFS efficient implementation method based on parallel feedback for the complex and changeable data parallelism in irregular programs. The corresponding program optimization techniques are proposed for the problem of dynamic queuing efficiency and the problem of load balancing caused by irregular input. Both the law and optimization techniques can be applied to other irregular programs.
This article obtains the following important understanding: (1) the flow programming model can drive the design of the instruction collective structure, and ISA needs to reflect the new characteristics of the programming model. (2) the multi thread mapping of the flow program needs the cooperative work of the software runtime library, and can increase the support of the convective programming model in the future operating system; (3) compile the system. Design links need to use appropriate programming patterns and software engineering methods to enhance the modularization and readability of programs, such as visitor patterns; (4) the parallel development of irregular programs requires accurate parallelism measurement, and the use of online analysis techniques can guide the rational division of computing resources.
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2013
【分類號】：TP314

【相似文獻】

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

1 沈緒榜;嵌入式MPP處理器的發(fā)展[J];電子產(chǎn)品世界;2005年21期

2 于永斌;徐潔;吳曉華;王華;丁旭陽;;多核時代的“計算機系統(tǒng)結(jié)構(gòu)”課程[J];計算機教育;2011年06期

3 羅沛霖;羅晉;凱睿;Steve Novack;Victor Berman;;混合式可重構(gòu)數(shù)字多核并行處理器平臺[J];前沿科學(xué);2008年04期

4 俞善賢;袖珍機程序優(yōu)化一例[J];氣象;1985年05期

5 劉永革,張愛平,趙國濤;基于快照和動態(tài)集的程序優(yōu)化研究[J];計算機工程與應(yīng)用;2004年14期

6 ;通過FLIX指令結(jié)構(gòu)提高可配置處理器計算性能[J];電子設(shè)計技術(shù);2006年02期

7 袁永富;熊福林;;基于最短走刀路線的數(shù)控加工程序優(yōu)化設(shè)計[J];機床與液壓;2010年12期

8 徐志強;;復(fù)雜關(guān)系巧化解——巧用表達式一例[J];信息與電腦(理論版);2010年10期

9 林芳;VFP應(yīng)用程序的優(yōu)化探討[J];河池師專學(xué)報;2001年04期

10 張欣;;Protel電路設(shè)計中的程序優(yōu)化[J];技術(shù)與市場;2007年04期

相關(guān)會議論文 前10條

1 彭林;張小強;劉德峰;謝倫國;田祖?zhèn)?;一種挖掘多核處理器存儲級并行的算法[A];第15屆全國信息存儲技術(shù)學(xué)術(shù)會議論文集[C];2008年

2 陳虎;歐彥麟;陳海波;;面向多核處理器平臺的并行Hash JOIN算法設(shè)計與實現(xiàn)[A];NDBC2010第27屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集(B輯)[C];2010年

3 陳虎;羅偉良;干蕓蕓;;Multi_MINT:一個基于MINT的多核處理器模擬器[A];第十五屆計算機工程與工藝年會暨第一屆微處理器技術(shù)論壇論文集（B輯）[C];2011年

4 何軍;王飆;;通用多核處理器發(fā)展現(xiàn)狀和趨勢研究[A];第十五屆計算機工程與工藝年會暨第一屆微處理器技術(shù)論壇論文集（A輯）[C];2011年

5 周巍;孫冰;戰(zhàn)立明;呂建華;王國仁;于戈;;基于DOM模型的XML查詢處理器的設(shè)計與實現(xiàn)[A];第十八屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2001年

6 張永;李如國;萬昌文;談毅;;干油填充泵空限位改造及主泵控制程序優(yōu)化[A];第七屆(2009)中國鋼鐵年會論文集（下）[C];2009年

7 郭寶森;毛峽;;基于Starcore SC140的DSP優(yōu)化方法研究[A];全國第十屆信號與信息處理、第四屆DSP應(yīng)用技術(shù)聯(lián)合學(xué)術(shù)會議論文集[C];2006年

8 張成;丁緒星;秦巍;;基于TMS320C6000系列DSP的軟件開發(fā)及優(yōu)化[A];2007'中國儀器儀表與測控技術(shù)交流大會論文集（二）[C];2007年

9 鄧振強;聶延生;曹善文;;船舶電站微機控制系統(tǒng)的程序優(yōu)化與快速并車方法[A];中國航海學(xué)會優(yōu)秀論文文摘及學(xué)術(shù)會議論文目次匯編（1990—1991）[C];1992年

10 鄧華陽;王志軍;趙紅怡;;AVS及其在DM642平臺上的編碼器優(yōu)化方案研究[A];2007通信理論與技術(shù)新發(fā)展——第十二屆全國青年通信學(xué)術(shù)會議論文集（上冊）[C];2007年

相關(guān)重要報紙文章 前10條

1 本報記者 溫慶生　特約記者 王握文;“算盤王國”新傳奇[N];光明日報;2010年

2 學(xué)健 編譯;Linux：一種趨勢[N];計算機世界;2001年

3 心元;PC“心臟”的搏擊[N];計算機世界;2004年

4 本報記者 湯銘;“天河一號” 躍居世界榜首[N];計算機世界;2010年

5 ;Microsoft Embeded OS縮小的桌面系統(tǒng)[N];中國計算機報;2001年

6 ;BMC PATROL for SLM[N];網(wǎng)絡(luò)世界;2001年

7 鄒小民;七程序優(yōu)化保領(lǐng)先[N];中國電力報;2008年

8 本報記者 薛仁　王握文 特約通訊員 司宏偉;超越之路[N];解放軍報;2010年

9 本報記者 蒲荔子邋實習(xí)生 周豫;國學(xué)放大人性光明一面[N];南方日報;2008年

10 單群一;愛普生瞄準(zhǔn)稅務(wù)打印市場[N];中國稅務(wù)報;2006年

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

1 劉谷;可重構(gòu)眾核流處理器上的編譯與程序優(yōu)化技術(shù)[D];中國科學(xué)技術(shù)大學(xué);2013年

2 徐光;分片式流處理器體系結(jié)構(gòu)[D];中國科學(xué)技術(shù)大學(xué);2010年

3 許牧;可重構(gòu)眾核流處理器體系結(jié)構(gòu)關(guān)鍵技術(shù)研究[D];中國科學(xué)技術(shù)大學(xué);2012年

4 劉德峰;面向存儲級并行的多核處理器關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2011年

5 李靜梅;多核處理器的設(shè)計技術(shù)研究[D];哈爾濱工程大學(xué);2010年

6 朱海濤;面向高密度計算的多核處理器結(jié)構(gòu)研究[D];中國科學(xué)技術(shù)大學(xué);2011年

7 陳虎;面向應(yīng)用的指令集處理器關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2011年

8 黃立波;片上集群體系結(jié)構(gòu)關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2010年

9 任永青;邏輯核動態(tài)可重構(gòu)的眾核處理器體系結(jié)構(gòu)[D];中國科學(xué)技術(shù)大學(xué);2010年

10 張惠臻;可重構(gòu)指令集處理器設(shè)計中的軟件重定向關(guān)鍵技術(shù)研究[D];中國科學(xué)技術(shù)大學(xué);2010年

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

1 趙麗麗;基于TTA內(nèi)核的流處理器設(shè)計的研究[D];上海交通大學(xué);2010年

2 董珍;異構(gòu)多核處理器的任務(wù)調(diào)度分配問題及算法研究[D];哈爾濱工程大學(xué);2010年

3 尤凱迪;高性能低功耗多核處理器研究[D];復(fù)旦大學(xué);2011年

4 鐘松延;可配置可擴展處理器編譯器設(shè)計[D];天津大學(xué);2012年

5 董正楊;亂序處理器指令吞吐量平穩(wěn)化的動態(tài)調(diào)節(jié)方法研究[D];華中科技大學(xué);2012年

6 葉新棟;一種Java處理器的體系結(jié)構(gòu)設(shè)計與研究[D];復(fù)旦大學(xué);2011年

7 馬媛;基于多核處理器平臺的分流模塊的設(shè)計與實現(xiàn)[D];北京交通大學(xué);2012年

8 朱辰;基于多核處理器的分組數(shù)據(jù)通信網(wǎng)關(guān)系統(tǒng)設(shè)計與實現(xiàn)[D];西安電子科技大學(xué);2008年

9 胡綿江;面向密碼應(yīng)用的定制處理器關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2011年

10 王光;基于FPGA的可穿戴處理器的設(shè)計與實現(xiàn)[D];西北大學(xué);2010年

，

本文編號：2108023