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

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

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

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

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

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

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

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

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

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

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

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

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

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