高效可重構陣列計算：體系結構,設計方法與程序映射技術研究.pdf

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

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

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

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

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

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

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

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

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

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

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

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

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