面向粗粒度可重構(gòu)體系結(jié)構(gòu)的應(yīng)用映射關(guān)鍵技術(shù)研究.pdf

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

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

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

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

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

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

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