高效可重構(gòu)陣列計(jì)算：體系結(jié)構(gòu),設(shè)計(jì)方法與程序映射技術(shù)研究.pdf

1、隨著應(yīng)用領(lǐng)域的服務(wù)質(zhì)量改進(jìn)和標(biāo)準(zhǔn)的提高，人們不斷對(duì)硬件提出了更高的性能和靈活性需求。以軟件無線電為例，目標(biāo)應(yīng)用既要求硬件處理平臺(tái)能夠提供強(qiáng)大的計(jì)算能力以保證實(shí)時(shí)性，也要求硬件處理平臺(tái)支持一定程度的可重構(gòu)，以適應(yīng)多種協(xié)議共存并快速發(fā)展的現(xiàn)狀。粗粒度可重構(gòu)陣列計(jì)算結(jié)構(gòu)（CGRA）就是能夠同時(shí)滿足這兩種需求的一類硬件，既可以通過大量的處理單元（PE）開發(fā)程序中各種粒度的并行，也能夠通過功能單元字級(jí)的重構(gòu)滿足一定程度靈活性。雖然傳統(tǒng)粗粒度可重構(gòu)

2、陣列結(jié)構(gòu)能夠?qū)π阅芎挽`活性提供較好的支持，但這種支持是以硬件的效率為代價(jià)的，無論是硬件開銷還是功耗，CGRA都與專用集成電路（ASIC）存在不小的差距。從CGRA的設(shè)計(jì)實(shí)現(xiàn)到應(yīng)用，面向特定應(yīng)用的設(shè)計(jì)方法以及程序在CGRA上的并行執(zhí)行對(duì)硬件性能的發(fā)揮有著至關(guān)重要的影響。因此，研究高效的粗粒度可重構(gòu)陣列計(jì)算體系結(jié)構(gòu)、設(shè)計(jì)方法和相關(guān)支撐技術(shù)成為當(dāng)前可重構(gòu)計(jì)算領(lǐng)域的重要課題。
　　本文立足于二維網(wǎng)格連接的粗粒度可重構(gòu)陣列的計(jì)算平臺(tái)，從新型

3、高效的體系結(jié)構(gòu)、面向特定應(yīng)用程序的設(shè)計(jì)方法、程序在粗粒度可重構(gòu)陣列上的指令級(jí)并行和循環(huán)級(jí)并行以及可重構(gòu)硬件加速部件五個(gè)方面展開研究工作，并進(jìn)行了詳細(xì)的評(píng)測(cè)與性能分析。本文的主要研究成果和創(chuàng)新性體現(xiàn)在以下幾個(gè)方面：
　　1）提出一種分簇的粗粒度可重構(gòu)陣列計(jì)算結(jié)構(gòu)，實(shí)現(xiàn)了CGRA在面積效率和功耗效率上的提高。針對(duì)功能單元利用率低的不足和數(shù)據(jù)傳遞的特點(diǎn)，本文提出了一種新型分簇的CGRA結(jié)構(gòu)。在分簇CGRA中，根據(jù)功能單元的特點(diǎn)，將硬件功

4、能單元分為兩種類型：一類是簡單的、操作時(shí)間短的PE；另一類是復(fù)雜的，操作時(shí)間長的PE。若干復(fù)雜的PE和若干個(gè)簡單的PE可以組成一個(gè)可重構(gòu)計(jì)算簇，簇內(nèi)的數(shù)據(jù)傳遞由共享寄存器完成。復(fù)雜PE中還可以包含可定制的特殊功能單元，用戶能夠針對(duì)特定的應(yīng)用程序特征進(jìn)行定制。與傳統(tǒng)的CGRA結(jié)構(gòu)相比，該分簇結(jié)構(gòu)由于資源的共享，復(fù)雜PE的數(shù)量減少，節(jié)省了硬件面積，提高了硬件利用率，在提高計(jì)算效率的同時(shí)保持了靈活性。由于簇內(nèi)資源之間相互連接緊密，可以方便地交

5、換數(shù)據(jù)，若在映射應(yīng)用程序時(shí)充分利用數(shù)據(jù)通信的局部性，可以減少復(fù)雜的路由過程，提供更多的資源用于計(jì)算。實(shí)驗(yàn)結(jié)果表明，這種形式的CGRA結(jié)構(gòu)具有更高的面積效率和功耗效率，基于簇的映射過程更加簡單有效。
　　2）針對(duì)面向特定應(yīng)用領(lǐng)域的功能單元定制，提出采用蟻群算法對(duì)應(yīng)用程序自動(dòng)進(jìn)行分析并生成對(duì)應(yīng)硬件結(jié)構(gòu)的設(shè)計(jì)方法。本文分析了特定應(yīng)用程序的特征提取和功能單元生成兩個(gè)問題的現(xiàn)有方法，指出在傳統(tǒng)設(shè)計(jì)方法中，應(yīng)用程序特征識(shí)別和硬件功能單元生成兩

6、個(gè)過程相互獨(dú)立的不足。本文進(jìn)一步發(fā)現(xiàn)這兩個(gè)問題都等價(jià)于確定程序數(shù)據(jù)流圖DFG中兩個(gè)節(jié)點(diǎn)之間的關(guān)聯(lián)度，二者之間存在相互約束和限制。采用這種新的問題定義，本文提出了一體化的識(shí)別應(yīng)用程序特征和硬件功能單元生成的自動(dòng)化設(shè)計(jì)方法。在所提出的設(shè)計(jì)方法中，程序分析和硬件結(jié)構(gòu)生成兩個(gè)過程在算法中迭代交替進(jìn)行，從而避免陷入局部優(yōu)化的解，保證最終結(jié)果的全局優(yōu)化性。基于蟻群優(yōu)化的算法很好地融合了程序特征識(shí)別與硬件生成這兩個(gè)過程，在全局啟發(fā)因素和局部啟發(fā)因素的

7、共同作用下，自動(dòng)地確定兩個(gè)節(jié)點(diǎn)之間的關(guān)聯(lián)度，優(yōu)化效果明顯。所提出的優(yōu)化策略能夠以較小的硬件代價(jià)實(shí)現(xiàn)較大程度的應(yīng)用程序加速。
　　3）針對(duì)CGRA上的指令級(jí)并行，提出一種基于蟻群算法將無環(huán)數(shù)據(jù)流圖DAG映射到CGRA的方法，在此基礎(chǔ)上提出了在分簇CGRA上進(jìn)行映射的優(yōu)化策略。本文給出了將DAG映射到CGRA上的整數(shù)規(guī)劃問題模型，指出DAG的映射實(shí)際上是將節(jié)點(diǎn)與PE單元一一對(duì)應(yīng)，優(yōu)化的目標(biāo)是所有節(jié)點(diǎn)完成執(zhí)行的時(shí)間。進(jìn)而提出采用蟻群算法

8、，在局部上采用盡早可能執(zhí)行的策略，通過Maze Route過程確定節(jié)點(diǎn)在指定PE上的最早可執(zhí)行時(shí)間，以此作為分配節(jié)點(diǎn)到PE的評(píng)價(jià)指標(biāo)；在整體上通過螞蟻殘留的信息素，依靠蟻群算法的全局優(yōu)化能力進(jìn)行程序映射結(jié)果的全局優(yōu)化。在蟻群映射算法基礎(chǔ)之上，本文還發(fā)現(xiàn)某些具有特殊親緣關(guān)系的節(jié)點(diǎn)對(duì)在很大程度上制約了最終結(jié)果質(zhì)量，提出父子關(guān)系和共子關(guān)系的節(jié)點(diǎn)應(yīng)該盡可能地映射到距離相近的計(jì)算簇上這一原則。通過定義和計(jì)算節(jié)點(diǎn)之間親緣關(guān)系，算法在映射的過程中加入

9、了節(jié)點(diǎn)對(duì)的親緣關(guān)系、所在簇之間距離的考慮，以此作為將節(jié)點(diǎn)分配PE另一重要指標(biāo)。加入這一指標(biāo)增強(qiáng)了搜索的指向性，基于最大—最小蟻群算法所獲得的映射結(jié)果質(zhì)量有所提高。此外，以這個(gè)指標(biāo)作為限制條件，適當(dāng)?shù)靥蕴糠植缓侠淼慕饽苡行У販p少搜索空間的范圍，同時(shí)保證解的質(zhì)量。與其他迭代優(yōu)化的方法相比，該映射算法運(yùn)行時(shí)間短、結(jié)果質(zhì)量高并且質(zhì)量穩(wěn)定，為開發(fā)CGRA上的指令級(jí)并行提供了良好的支持。
　　4）針對(duì)CGRA上的循環(huán)級(jí)并行，提出一種基于遺傳

10、算法并考慮路由共享的模調(diào)度方法，根據(jù)分簇CGRA結(jié)構(gòu)提出一種更快速、有效的模調(diào)度方法。本文提出了一種基于遺傳算法的模調(diào)度方法，該方法中定義了數(shù)據(jù)依賴關(guān)系的優(yōu)先級(jí)，以優(yōu)先級(jí)順序進(jìn)行路由，保證路由時(shí)重要的數(shù)據(jù)依賴先得到滿足。當(dāng)循環(huán)核心中存在生產(chǎn)者相同、消費(fèi)者不同的多個(gè)數(shù)據(jù)依賴關(guān)系時(shí)，路由采用Steiner樹進(jìn)行優(yōu)化，在調(diào)度節(jié)點(diǎn)的同時(shí)尋找最優(yōu)路由資源的共享方案。采用一種快速、近似的方法解決求解Steiner樹的問題，較好地實(shí)現(xiàn)了路由節(jié)點(diǎn)的共享

11、。此外，本文通過分析循環(huán)間數(shù)據(jù)依賴和循環(huán)內(nèi)數(shù)據(jù)依賴的數(shù)量，提出利用分簇CGRA體系結(jié)構(gòu)的局部緊耦合特性，將一個(gè)迭代限定在一個(gè)簇上運(yùn)行，相鄰的迭代在相鄰簇上運(yùn)行的分簇CGRA上模調(diào)度算法。這種基于簇的模調(diào)度策略通過循環(huán)展開和擴(kuò)展循環(huán)體，能夠很好地在CGRA的各個(gè)簇之間開發(fā)循環(huán)級(jí)并行。所采用的貪心調(diào)度算法能快速高效地完成循環(huán)核心在一個(gè)簇上的調(diào)度。這種方式的模調(diào)度無需進(jìn)行復(fù)雜的路由映射過程，很好地解決了路由優(yōu)化過程過于復(fù)雜這一難題，實(shí)驗(yàn)表明，

12、這種基于簇的模調(diào)度方法極大地節(jié)省了映射時(shí)間。相比其他已有的算法，本文所提出的方法在分簇CGRA結(jié)構(gòu)上能夠更好地實(shí)現(xiàn)循環(huán)流水，更大程度地實(shí)現(xiàn)程序加速。
　　5）在可重構(gòu)加速部件方面，針對(duì)不適合在可重構(gòu)結(jié)構(gòu)上實(shí)現(xiàn)的Turbo乘積碼算法，設(shè)計(jì)并實(shí)現(xiàn)靈活可配置的VLSI加速部件結(jié)構(gòu)；分析了FFT和Viterbi算法的共性，設(shè)計(jì)并實(shí)現(xiàn)了可重構(gòu)的算法加速部件。本文對(duì)信道編解碼中常用的Turbo乘積碼的解碼算法的過程和計(jì)算進(jìn)行了優(yōu)化，相對(duì)于原算

13、法，優(yōu)化后的算法在性能上有一定提升，并且更適合高效的硬件實(shí)現(xiàn)。所設(shè)計(jì)的Turbo乘積碼解碼器不僅面積效率高，而且支持多種碼型，能滿足不同通信標(biāo)準(zhǔn)的需要。此外，本文針對(duì)FFT和Viterbi這兩種無線通信中頻繁使用的算法，分析二者的算法過程，發(fā)現(xiàn)他們?cè)谟?jì)算結(jié)構(gòu)和訪存模式上存在相似性，因而兩個(gè)加速部件的ASIC實(shí)現(xiàn)可以共享部分硬件單元。本文設(shè)計(jì)并實(shí)現(xiàn)了可重構(gòu)的Viterbi和FFT加速部件，相對(duì)于兩種分立的加速部件資源開銷之和，可重構(gòu)結(jié)構(gòu)的