面向粗粒度可重構體系結構的應用映射關鍵技術研究.pdf

1、粗粒度可重構結構（CGRA）為多媒體處理程序等數(shù)據(jù)密集型應用提供了靈活且高效的加速方式。CGRA應用映射決定了應用程序在其體系結構上的實現(xiàn)方式，其針對給定的CGRA應用功能和體系結構，在滿足系統(tǒng)約束的前提下，將應用程序映射到CGRA體系結構上，對CGRA處理性能和效率有重要影響。目前應用映射技術已成為CGRA研究領域的熱點與難點。本文研究CGRA應用映射關鍵技術。先分析了已有應用映射方法及其存在的不足。在此基礎上重點研究了面向CGRA應

2、用映射的程序特征分析方法、基于循環(huán)仿射劃分的并行任務生成方法、應用處理任務到CGRA體系結構的高效分配與任務調(diào)度方法等。完成的主要工作和取得的創(chuàng)新性成果如下：
　?、盘岢鲆环N基于仿真與解析方法相結合的應用特征分析方法。根據(jù)CGRA應用映射對應用特征信息的需求，基于模擬器、程序中間表示和多面體模型等工具構建了應用特征分析框架，通過動態(tài)仿真、中間表示解析和基于多面體建模分析等多種方法，分析得到了各種程序特征，包括：應用結構特征、控制流

3、/數(shù)據(jù)流特征、計算/操作數(shù)特征、存儲需求特征、數(shù)據(jù)依賴關系、執(zhí)行時間等。特別針對應用中核心關鍵循環(huán)，通過基于執(zhí)行時間和工作量估算相結合的方法，產(chǎn)生不同的核心循環(huán)識別因子，從而實現(xiàn)核心循環(huán)的識別與提取。實驗表明：該方法可以為CGRA應用映射提供較為全面的程序特征信息，為后續(xù)的并行任務生成、任務分配與調(diào)度等過程提供了有力的特征信息支持。
　?、铺岢鲆环N基于存儲需求分析的關鍵循環(huán)任務映射方法MALP。該方法首先定義RCP_CGRA體系結

4、構模型，利用已提取的循環(huán)特征信息構建循環(huán)的PIA-CDTG模型來闡述關鍵循環(huán)到CGRA的映射問題。通過引入結合數(shù)組分簇的多面體數(shù)據(jù)域劃分方法進行循環(huán)存儲分析，隨后根據(jù)分析結果，結合體系結構資源約束實現(xiàn)了循環(huán)的有效映射。實驗結果表明，通過利用多面體模型進行循環(huán)數(shù)據(jù)依賴分析和存儲需求分析，此方法能夠有效降低循環(huán)映射時的資源占用率，提高數(shù)據(jù)吞吐量，進一步提升CGRA上循環(huán)映射的性能。與已有的方法相比，MALP方法進一步提升了CGRA上循環(huán)映射

5、的性能。
　?、翘岢鲆环N新穎的面向CGRA循環(huán)流水映射的數(shù)據(jù)并行優(yōu)化方法。為了在CGRA上最大程度開發(fā)應用并行性，降低循環(huán)訪存開銷，提高硬件資源利用率，該方法通過定義一種新的可重構計算模型TMGC2以實現(xiàn)對循環(huán)的多條數(shù)據(jù)流水線并行加速。為避免并行化執(zhí)行帶來的額外存儲體沖突問題影響 CGRA執(zhí)行性能，為后續(xù)循環(huán)映射創(chuàng)造了良好數(shù)據(jù)條件，引入存儲體消除對數(shù)據(jù)進行重組，并結合數(shù)據(jù)重用圖實現(xiàn)數(shù)據(jù)并行優(yōu)化。實驗表明，采用此方法對已有CGRA循

6、環(huán)流水映射方法進行優(yōu)化，可以提高37.2％的數(shù)據(jù)吞吐量及41.3%的資源利用率。
　?、忍岢隽艘环N基于多面體模型的程序多級仿射劃分的并行任務生成方法該方法引入程序特征（如：數(shù)據(jù)依賴關系、各數(shù)據(jù)的使用頻率等）和體系結構信息（如：計算資源、存儲層次、重構開銷等），分步設置循環(huán)多級仿射劃分的參數(shù)?；陉P注元采用程序多級仿射劃分對核心循環(huán)進行并行性和局部性轉換，得到可并行執(zhí)行的各個循環(huán)子塊，作為各并行子任務提供給后續(xù)任務分配與調(diào)度過程。實

7、驗表明，通過在任務生成時引入了循環(huán)特征和體系結構信息，通過CGRA約束函數(shù)指導仿射劃分，使得生成的并行任務更適于在CGRA目標體系結構上運行，減少了后續(xù)任務分配和調(diào)度的限制。
　?、商岢隽艘环N基于圖著色模型的高效蟻群進化任務分配與調(diào)度方法。針對任務的分配與調(diào)度問題，提出了一種應用任務到CGRA的高效分配與調(diào)度方法。通過用圖節(jié)點多著色模型描述CGRA任務分配與調(diào)度問題,使用高效的進化蟻群算法進行任務調(diào)度，通過引入遺傳算法控制參數(shù)，從