基于動態數據流的粗粒度可重構陣列設計

吳昊

（上海交通大學，上海200240）

0 引言

隨著信息化社會的不斷發展，涌現了大批以大量數據處理為主導的算法，例如機器學習和神經網絡，這些算法對處理器的性能有非常高的需求，并要求且處理器能夠提高較高程度的靈活型以適應不斷變換的算法需求。通用處理器難以支持如此龐大的算力，專用處理器雖然能夠實現很高的加速比但是針對特定的算法而設計，不具備靈活支持多種算法的能力，因此粗粒度可重構陣列[1]成為了當下研究的熱點。

粗粒度可重構陣列由陣列控制器、大量的處理單元（Process Element，PE）及互聯資源構成，處理單元的功能及處理單元之間的互聯結構均可以根據算法的需求重構，在利用空間計算提升執行效率的同時還能夠獲得較高的靈活性。但是陣列中如此多的處理單元往往很難被充分的利用，受到長延遲操作、數據依賴關系等諸多因素的制約，因此提高處理單元的利用率是粗粒度可重構陣列研究中的重要問題，也是提升整體性能的關鍵。

現有粗粒度可重構陣大多基于配置流驅動[2]，雖然能夠通過指令級并行的方式提升對處理單元的利用率，但是其控制代價也非常高的昂，在陣列運行中頻繁的切換配置帶來了很高的功耗，并且需要更多的片上存儲保存指令，增加了陣列的面積。因此，本文基于動態數據流[3]的執行方式設計粗粒度可重構陣列，通過解決陣列中的長延遲操作以提升陣列中處理單元的利用率，從而提高陣列的流水頻率，最終達到提升陣列整體性能的目的。

1 設計思路

動態數據流能夠有效地隱藏長延遲操作帶來的性能損失，其核心思想是讓陣列在進行長延遲操作時優先處理后續的數據。例如當陣列運行中出現對片外存儲器的訪問時，可以繼續從緩存中提取后續將要訪問的數據并優先執行后續的操作。除此之外，一些虛擬流水化操作也可以用動態數據流的方式加速，例如虛擬流水化的除法器，實際上是通過多個除法單元并行工作的方式模擬流水化執行，因為除法操作的延遲與數據相關，所以當長延遲操作發生時，陣列可以優先處理后續的短延遲操作。

動態數據流的實現需要陣列中所有的數據都攜帶標記信息，理想情況下同一次循環迭代中的數據應該具有相同的標記，不同循環迭代的數據應該具有不同的標記。PE需要對操作數的標記進行匹配，如果所有操作數的標記相同則激活ALU執行運算，否則等待操作數的匹配。匹配過程如圖1所示，第2批的數據由于先準備好所以先開始計算，不需要等待第1批的數據完成，有效地利用了處理器的閑置時間。

圖1 動態數據流執行圖

為了在可重構陣列上實現動態數據流，需要對以下問題進行設計。

（1）交叉匹配問題

由于標記的實現需要額外的布線資源和硬件邏輯，所以標記的數目是受到限制的，一般會通過循環的方式重復利用之前使用過的標記。在這種標記的使用策略下可能會發生交叉匹配的問題，即由于陣列中不同循環迭代間的數據具有了相同的標記，這些不同批次的數據就有可能交叉匹配從而導致陣列計算出錯。為了解決這一問題，本設計采用的方案是對PE的輸入buffer增加一些限制邏輯，不允許PE的輸入buffer中同時存在多個有相同標記的數據。

（2）死鎖問題

死鎖問題發生在標記的數目大于輸入buffer的規模時。如圖2所示，由于輸入1的buffer和輸入2的buffer中均是不同的標記，所以該PE無法完成數據的匹配并激活運算，同時由于兩個輸入buffer都已經被填滿，所以能夠匹配的輸入無法進入輸入buffer，PE一直卡死在這一狀態就發生了死鎖。為了解決這一問題，需要對標記的數目進行更為嚴格的限制，當標記的數目等于輸入buffer的規模時就可以避免死鎖。

圖2 死鎖示意圖

（3）PE間通信機制

在可重構陣列領域有兩種基本的通信機制，一種是ACK機制，在這種機制下發送端先發送數據，再根據接收端的反饋信號選擇是否清除。另一種是Credit機制[4]，此機制下接收端先提供Credit信號，發送端接收后再發送數據并且直接清除。兩種通信機制如圖3所示，Credit機制的正確運行基于接收端一定能夠接收發送端所發出的每一個數據，但是由于要解決上述交叉匹配問題所以無法滿足Credit機制的運行條件，PE必須檢測輸入數據的標記是否和輸入buffer中的有效數據重復，如果發生重復則不能接收該數據。因此，本文采用ACK機制作為陣列內部的通信協議，如果PE檢測完成后確認可以接收該數據則向其上級節點反饋ACK信號。

圖3 兩種通信機制

2 陣列結構設計

2.1 陣列整體結構

陣列的整體結構如圖4所示，由陣列控制器、PE陣列和數據存儲模塊三部分構成。其中陣列控制器負責向PE陣列導入配置，啟動陣列的執行并收集陣列的結束信息。PE陣列執行計算任務，陣列內部采取行互聯和列互聯的結構。數據存儲模塊中包含片上高速緩存和片外存儲兩部分，片上緩存的訪問代價較低但是容量較小，片外存儲容量大但是訪存代價很高。陣列的執行過程如下：在任務開始執行前由陣列控制器導入配置并固化互聯結構，導入完成后激活陣列執行，當陣列結束后向陣列控制器反饋結束信號，標志任務的結束。由于陣列基于數據流驅動，所以在陣列運行過程中PE的結構及互聯均不發生改變，只依靠操作數的匹配激活PE進行運算。這種可重構陣列控制的代價非常低，并且具有更低的功耗。

圖4 粗粒度可重構陣列整體結構圖

2.2 PE結構設計

PE的內部結構如圖5所示，輸入輸出均是兩個數據線加一個控制線，數據線傳遞操作數而控制線傳遞布爾信號。PE內部可以劃分成三個流水級，輸入buf?fer對外部輸入進行緩沖，ALU執行算術運算，輸出buffer保存ALU的計算結果。其中輸入buffer的層數和tag的數目相對應以解決死鎖問題，并且有專門的匹配電路依據標記對輸入buffer中的操作數進行匹配。所有的標記在輸入buffer中都有相對應的唯一位置，從而有效的防止了攜帶相同標記的數據進入buffer。配置寄存器負責接收配置信息并根據配置信息對PE內部的數據通路以及ALU執行的功能進行配置，本地寄存器儲存常量數據或者迭代數據。

圖5 PE結構圖

3 實驗結果與分析

為了驗證動態數據流對性能的影響，本文設計了C++仿真器對粗粒度可重構陣列進行功能驗證和性能仿真。仿真器中包含了陣列模型和存儲模型，能夠模擬片上緩存的行為以及片外存儲的延時。在進行仿真前需要設置一些硬件參數，本次實驗采用的參數如表1所示。仿真器的應用過程如下：首先將應用轉換成數據流圖的表達形式，根據數據流圖為陣列中的PE編寫配置文件，然后將配置文件作為仿真器的輸入并開始執行仿真。仿真的過程中逐周期的訪問所有PE，并且按照硬件的時序順序訪問PE內部的每一級流水級。當仿真結束后能夠得到陣列的執行周期數。

本文采用廣度優先搜索算法進行仿真測試[5]，該算法較為隨機的訪存特征能夠體現動態數據流的優勢。輸入的圖中包含8192個節點以及491520條邊，總的數據規模為516097，并且以稀疏化的存儲方式組織數據。仿真的結果如圖6所示，依據標記數目設置了多組測試以評估動態數據流的性能，仿真結果以標記數目為2時的性能作為基準進行歸一化。從圖中可以看出，隨著標記數目的增加性能有顯著的提升，并且隨著標記數目增加性能提升的幅度也在不斷降低，最終在標記數目等于64時達到了3.12的加速比。發生這一現象的原因是動態數據流對陣列實現加速的同時也對訪存模塊造成了更大的壓力，因此訪存模塊成為了制約性能提升的瓶頸。

表1 硬件參數表

圖6標記數目對性能的影響

4 結語

本文基于動態數據流技術對粗粒度可重構陣列進行設計，首先根據動態數據流的實現原理對PE的功能和PE間的通信方式進行設計，其次對可重構陣列整體結構和PE內部的微架構進行詳細的設計。最后，本文設計了C++仿真器對上述架構進行建模，針對廣度優先搜索算法進行仿真測試和性能評估，證明了動態數據流的執行機制能夠有效的實現性能的提升，并且隨著標記數目的增多性能也逐漸提升，直到達到訪存的瓶頸。