基于動(dòng)態(tài)數(shù)據(jù)流的粗粒度可重構(gòu)陣列設(shè)計(jì)

吳昊

（上海交通大學(xué)，上海200240）

0 引言

隨著信息化社會(huì)的不斷發(fā)展，涌現(xiàn)了大批以大量數(shù)據(jù)處理為主導(dǎo)的算法，例如機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)，這些算法對(duì)處理器的性能有非常高的需求，并要求且處理器能夠提高較高程度的靈活型以適應(yīng)不斷變換的算法需求。通用處理器難以支持如此龐大的算力，專用處理器雖然能夠?qū)崿F(xiàn)很高的加速比但是針對(duì)特定的算法而設(shè)計(jì)，不具備靈活支持多種算法的能力，因此粗粒度可重構(gòu)陣列[1]成為了當(dāng)下研究的熱點(diǎn)。

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

現(xiàn)有粗粒度可重構(gòu)陣大多基于配置流驅(qū)動(dòng)[2]，雖然能夠通過(guò)指令級(jí)并行的方式提升對(duì)處理單元的利用率，但是其控制代價(jià)也非常高的昂，在陣列運(yùn)行中頻繁的切換配置帶來(lái)了很高的功耗，并且需要更多的片上存儲(chǔ)保存指令，增加了陣列的面積。因此，本文基于動(dòng)態(tài)數(shù)據(jù)流[3]的執(zhí)行方式設(shè)計(jì)粗粒度可重構(gòu)陣列，通過(guò)解決陣列中的長(zhǎng)延遲操作以提升陣列中處理單元的利用率，從而提高陣列的流水頻率，最終達(dá)到提升陣列整體性能的目的。

1 設(shè)計(jì)思路

動(dòng)態(tài)數(shù)據(jù)流能夠有效地隱藏長(zhǎng)延遲操作帶來(lái)的性能損失，其核心思想是讓陣列在進(jìn)行長(zhǎng)延遲操作時(shí)優(yōu)先處理后續(xù)的數(shù)據(jù)。例如當(dāng)陣列運(yùn)行中出現(xiàn)對(duì)片外存儲(chǔ)器的訪問(wèn)時(shí)，可以繼續(xù)從緩存中提取后續(xù)將要訪問(wèn)的數(shù)據(jù)并優(yōu)先執(zhí)行后續(xù)的操作。除此之外，一些虛擬流水化操作也可以用動(dòng)態(tài)數(shù)據(jù)流的方式加速，例如虛擬流水化的除法器，實(shí)際上是通過(guò)多個(gè)除法單元并行工作的方式模擬流水化執(zhí)行，因?yàn)槌ú僮鞯难舆t與數(shù)據(jù)相關(guān)，所以當(dāng)長(zhǎng)延遲操作發(fā)生時(shí)，陣列可以優(yōu)先處理后續(xù)的短延遲操作。

動(dòng)態(tài)數(shù)據(jù)流的實(shí)現(xiàn)需要陣列中所有的數(shù)據(jù)都攜帶標(biāo)記信息，理想情況下同一次循環(huán)迭代中的數(shù)據(jù)應(yīng)該具有相同的標(biāo)記，不同循環(huán)迭代的數(shù)據(jù)應(yīng)該具有不同的標(biāo)記。PE需要對(duì)操作數(shù)的標(biāo)記進(jìn)行匹配，如果所有操作數(shù)的標(biāo)記相同則激活A(yù)LU執(zhí)行運(yùn)算，否則等待操作數(shù)的匹配。匹配過(guò)程如圖1所示，第2批的數(shù)據(jù)由于先準(zhǔn)備好所以先開始計(jì)算，不需要等待第1批的數(shù)據(jù)完成，有效地利用了處理器的閑置時(shí)間。

圖1 動(dòng)態(tài)數(shù)據(jù)流執(zhí)行圖

為了在可重構(gòu)陣列上實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)流，需要對(duì)以下問(wèn)題進(jìn)行設(shè)計(jì)。

（1）交叉匹配問(wèn)題

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

（2）死鎖問(wèn)題

死鎖問(wèn)題發(fā)生在標(biāo)記的數(shù)目大于輸入buffer的規(guī)模時(shí)。如圖2所示，由于輸入1的buffer和輸入2的buffer中均是不同的標(biāo)記，所以該P(yáng)E無(wú)法完成數(shù)據(jù)的匹配并激活運(yùn)算，同時(shí)由于兩個(gè)輸入buffer都已經(jīng)被填滿，所以能夠匹配的輸入無(wú)法進(jìn)入輸入buffer，PE一直卡死在這一狀態(tài)就發(fā)生了死鎖。為了解決這一問(wèn)題，需要對(duì)標(biāo)記的數(shù)目進(jìn)行更為嚴(yán)格的限制，當(dāng)標(biāo)記的數(shù)目等于輸入buffer的規(guī)模時(shí)就可以避免死鎖。

圖2 死鎖示意圖

（3）PE間通信機(jī)制

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

圖3 兩種通信機(jī)制

2 陣列結(jié)構(gòu)設(shè)計(jì)

2.1 陣列整體結(jié)構(gòu)

陣列的整體結(jié)構(gòu)如圖4所示，由陣列控制器、PE陣列和數(shù)據(jù)存儲(chǔ)模塊三部分構(gòu)成。其中陣列控制器負(fù)責(zé)向PE陣列導(dǎo)入配置，啟動(dòng)陣列的執(zhí)行并收集陣列的結(jié)束信息。PE陣列執(zhí)行計(jì)算任務(wù)，陣列內(nèi)部采取行互聯(lián)和列互聯(lián)的結(jié)構(gòu)。數(shù)據(jù)存儲(chǔ)模塊中包含片上高速緩存和片外存儲(chǔ)兩部分，片上緩存的訪問(wèn)代價(jià)較低但是容量較小，片外存儲(chǔ)容量大但是訪存代價(jià)很高。陣列的執(zhí)行過(guò)程如下：在任務(wù)開始執(zhí)行前由陣列控制器導(dǎo)入配置并固化互聯(lián)結(jié)構(gòu)，導(dǎo)入完成后激活陣列執(zhí)行，當(dāng)陣列結(jié)束后向陣列控制器反饋結(jié)束信號(hào)，標(biāo)志任務(wù)的結(jié)束。由于陣列基于數(shù)據(jù)流驅(qū)動(dòng)，所以在陣列運(yùn)行過(guò)程中PE的結(jié)構(gòu)及互聯(lián)均不發(fā)生改變，只依靠操作數(shù)的匹配激活PE進(jìn)行運(yùn)算。這種可重構(gòu)陣列控制的代價(jià)非常低，并且具有更低的功耗。

圖4 粗粒度可重構(gòu)陣列整體結(jié)構(gòu)圖

2.2 PE結(jié)構(gòu)設(shè)計(jì)

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

圖5 PE結(jié)構(gòu)圖

3 實(shí)驗(yàn)結(jié)果與分析

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

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

表1 硬件參數(shù)表

圖6標(biāo)記數(shù)目對(duì)性能的影響

4 結(jié)語(yǔ)

本文基于動(dòng)態(tài)數(shù)據(jù)流技術(shù)對(duì)粗粒度可重構(gòu)陣列進(jìn)行設(shè)計(jì)，首先根據(jù)動(dòng)態(tài)數(shù)據(jù)流的實(shí)現(xiàn)原理對(duì)PE的功能和PE間的通信方式進(jìn)行設(shè)計(jì)，其次對(duì)可重構(gòu)陣列整體結(jié)構(gòu)和PE內(nèi)部的微架構(gòu)進(jìn)行詳細(xì)的設(shè)計(jì)。最后，本文設(shè)計(jì)了C++仿真器對(duì)上述架構(gòu)進(jìn)行建模，針對(duì)廣度優(yōu)先搜索算法進(jìn)行仿真測(cè)試和性能評(píng)估，證明了動(dòng)態(tài)數(shù)據(jù)流的執(zhí)行機(jī)制能夠有效的實(shí)現(xiàn)性能的提升，并且隨著標(biāo)記數(shù)目的增多性能也逐漸提升，直到達(dá)到訪存的瓶頸。