李 濤,楊 婷,易學(xué)淵,蒲 林,錢博文,黃光新,黃虎才,韓俊剛

(1.西安郵電大學(xué)電子工程學(xué)院,陜西 西安 710061;2.西安郵電大學(xué)計算機學(xué)院,陜西 西安 710061)

螢火蟲2：一種多態(tài)并行機的硬件體系結(jié)構(gòu)*

李 濤1,楊 婷1,易學(xué)淵1,蒲 林1,錢博文1,黃光新2,黃虎才2,韓俊剛2

(1.西安郵電大學(xué)電子工程學(xué)院,陜西 西安 710061;2.西安郵電大學(xué)計算機學(xué)院,陜西 西安 710061)

提出了一種新型的多態(tài)高效并行陣列機結(jié)構(gòu)——螢火蟲2號陣列機。該結(jié)構(gòu)的處理單元可以在SIMD和MIMD兩種模式下運行，兼有異步執(zhí)行機制，還可以實現(xiàn)分布式指令級并行處理。采用了硬件的多線程管理器和高效通信機制，這些機制使得此種陣列機能夠?qū)崿F(xiàn)效率很高的線程級并行運算、數(shù)據(jù)級并行運算和分布式指令級并行運算。尤其值得指出的是，此種陣列機的流處理性能堪與專用集成電路匹敵。該結(jié)構(gòu)還能有效實現(xiàn)靜態(tài)與動態(tài)數(shù)據(jù)流計算，可以高效實現(xiàn)圖形、圖像和數(shù)字信號處理任務(wù)。

陣列機；多態(tài)處理器；計算機圖形；圖像處理；信號處理；數(shù)據(jù)級并行；線程級并行；指令級并行

1 引言

當(dāng)代數(shù)字計算器件主要有CPU(Central Processing Unit)、GPU(Graphic Processing Unit)和FPGA(Field Programmable Gate Array)。CPU的可編程性最佳，GPU的編程稍微困難一些，F(xiàn)PGA則只是可重構(gòu)。另一方面，F(xiàn)PGA的性能要勝于那些可編程器件，GPU的并行處理能力一般要優(yōu)于CPU。專用集成電路ASIC(Application Specific Integrated Circuit)不可編程，但是其速度和功耗性能遠(yuǎn)勝于通用可編程處理器。然而，可編程處理器的靈活性卻是s專用集成電路無法比擬的。FPGA類的可重構(gòu)器件(Reconfigurable Device)[1]，尤其是動態(tài)可重構(gòu)器件[2]，具有一定的靈活性，性能也可能接近ASIC。

在靈活性與性能方面，一端是高度靈活與成熟的可編程處理器，另一端是高性能但不可變的ASIC?？芍貥?gòu)器件介于二者之間。本文提出的螢火蟲2的體系結(jié)構(gòu)，是一種可編程陣列處理器。其目的是要在性能上與ASIC接近，同時兼有可編程器件的靈活性。

在并行計算方面最為人熟知的是Flynn[3]分類法。該方法是按照指令流(Instruction Stream)和數(shù)據(jù)流(Data Stream)的個數(shù)進行分類的。實際中兩種最常見的并行結(jié)構(gòu)是單指令多數(shù)據(jù)結(jié)構(gòu)SIMD(Single Instruction Multiple Data)和多指令多數(shù)據(jù)結(jié)構(gòu)MIMD(Multiple Instruction Stream Multiple Data Stream)。根據(jù)單位運算的復(fù)雜度又可分為粗粒度運算和細(xì)粒度運算。細(xì)粒度運算通常指基本算術(shù)邏輯操作，而粗粒度則指較復(fù)雜的函數(shù)或線程。

現(xiàn)代并行處理中常常提到的并行計算方式[4]包括數(shù)據(jù)級并行DLP(Data Level Parallelism)計算、線程級并行TLP(Thread Level Parallelism)計算和指令級并行ILP(Instruction Level Parallelism)計算。

(1)數(shù)據(jù)級并行DLP計算[5]以SIMD為基礎(chǔ)。GPU使用的是一種擴展的SIMD方式，稱為SIMT。DLP通常使用算法層的并行。

(2)線程級并行TLP計算[6]對應(yīng)于MIMD，通常為粗粒度運算。TLP并行處理需要進程通信機制，不適合細(xì)粒度的并行處理。

(3)指令級并行ILP計算主要是指主流CPU使用的超標(biāo)量和VLIW(Very Long Instruction Word)類的機器和計算方法[7]。計算粒度細(xì)，利用操作間的不相關(guān)性，而不是算法的并行度，采用類似經(jīng)典的數(shù)據(jù)流計算(Dataflow Computation)[8,9]。

此外，還有人把FPGA和ASIC類[10]的計算方法稱為操作并行計算OLP(Operation Level Parallelism)。

現(xiàn)代結(jié)構(gòu)中也有將上述數(shù)種并行處理方法混合的各種例子。GPU[11,12]就是把SIMD和MIMD混合使用的典型例子?，F(xiàn)代GPU的基本計算方法是SIMD的數(shù)據(jù)級并行運算。但是，多個MIMD任務(wù)可以被分配到不同的SM(Streaming Multiprocessor)塊中，在SM上面實現(xiàn)較粗粒度的MIMD運算。EDGE(Explicit Data Graph Execution)[13]機器也是如此，但該機器將指令固定分配到處理單元上，讓數(shù)據(jù)可以流動，以實現(xiàn)宏觀數(shù)據(jù)流計算。這是一種粗粒度的數(shù)據(jù)流計算，是控制流(Control Flow)計算與數(shù)據(jù)流計算(Data Flow)的結(jié)合[14]。

總之，實現(xiàn)上述各種并行計算模式的混合并非新鮮事物，但是在陣列機上分區(qū)并發(fā)實現(xiàn)多種模式而且能夠一步轉(zhuǎn)換模式，卻十分困難。尤其是要在性能上接近ASIC，則是一個真正的挑戰(zhàn)。螢火蟲2陣列機就是面對這個挑戰(zhàn)的一個嘗試。

隨著集成度的提高，芯片上可以利用的資源越來越豐富。實現(xiàn)高度并行處理不再是個難題，但隨之而來的卻是新的挑戰(zhàn)。當(dāng)很多處理功能集成到一個芯片上時，功耗是巨大的，現(xiàn)有的GPU芯片達到了200瓦以上功耗，散熱變得很困難。AMD公司的GPU芯片不得不使用水冷散熱。功耗問題是并行處理芯片面臨的新挑戰(zhàn)[15]?，F(xiàn)代超標(biāo)量處理器結(jié)構(gòu)復(fù)雜，很難解決功耗問題。最新研究[16]表明，超標(biāo)量式的復(fù)雜控制和當(dāng)前多層次存儲結(jié)構(gòu)產(chǎn)生的大量數(shù)據(jù)流動是功耗的主要來源。輕核(Thin Core)處理器[17]和大量的片上存儲是解決功耗問題的有效手段。本文中的陣列處理器就是采用了簡單的處理器結(jié)構(gòu)和大量的片上存儲來降低功耗。

螢火蟲2號陣列機采用一系列設(shè)計方法來實現(xiàn)高效低功耗的并行處理，在許多方面體現(xiàn)了返樸歸真的思想。本文詳述這種陣列機的處理單元結(jié)構(gòu)、線程管理機制、線程通信機制和總體結(jié)構(gòu)。

2 多態(tài)陣列機整體結(jié)構(gòu)

多態(tài)陣列機系統(tǒng)由多個處理器簇(Cluster)組成，每個簇是由處理單元PE(Processing Element)組成的一個二維陣列(2D Array)，是一種較常見的陣列結(jié)構(gòu)。這種簇結(jié)構(gòu)可以平面展開，也可以分層次(Hierarchical)構(gòu)成。

(1)一個基本簇(Basic Cluster)是16個處理單元組成的4×4陣列，如圖1所示。處理單元由近鄰互聯(lián)組成二維陣列。

(2)每一行有行控制器CR(Row Controller)，用來實現(xiàn)行的SIMD運算。每一列也有列控制器CW(Column Controller)，用來管理簇存儲器。

(3)整個簇中有一個簇控制器(Cluster Controller)，用來協(xié)調(diào)整個簇的處理單元。簇中的共享存儲分布在列控制器中。

當(dāng)前的設(shè)計可以支持高達1 024個處理單元。每個行控制器和列控制器帶有自己的程序存儲?？梢园岩恍谢蛘咭涣刑幚韱卧貥?gòu)成SIMD模式，進行數(shù)據(jù)級并行計算；也可以把一個整簇重構(gòu)成SIMD模式，用簇控制器來協(xié)調(diào)整個簇實現(xiàn)SIMD并行計算。程序和數(shù)據(jù)的加載由簇控制器協(xié)調(diào)，行與列控制器輔助執(zhí)行。這些控制器還可以用來控制SIMD運算。

Figure 1 Structure of basic cluster圖1 基本簇的結(jié)構(gòu)

圖2給出了一個完整的螢火蟲2系統(tǒng)，包含一個前端處理器(FEP)、四個F簇(F Cluster0～3)、四個S簇(S Cluster0～3)、各種專用加速器(Accel)、片上緩存器、外部存儲器以及片上互聯(lián)(Interconnect)。F簇處理單元包含浮點運算器和定點運算器，S簇只包含定點運算器。

Figure 2 Architecture of Firefly 2圖2 系統(tǒng)整體結(jié)構(gòu)

當(dāng)執(zhí)行圖形、圖像或者信號處理應(yīng)用程序時，前端處理器是系統(tǒng)與外部處理器或者CPU主處理器的接口。專用加速器通常包括基本函數(shù)運算器(指數(shù)、對數(shù)、三角函數(shù)、平方根等)、圖形處理器加速器(背面消隱器、圖元裝配器、光柵化處理器)等。

當(dāng)F簇和S簇之間的運算負(fù)載不平衡時，可以將部分S簇中的運算轉(zhuǎn)移到F簇中處理。值得一提的是，F(xiàn)簇處理單元采用了一種多格式定點計算器，用來進行圖形和圖像處理中特定的定點運算，如光柵化和背面消隱等。

2.1 線程級并行(MIMD)運行方式

這是螢火蟲2的基本運行方式，也是其最常見的運行方式。只要任務(wù)分割恰當(dāng)，此種方式編程較容易，程序查錯也容易。

在此種方式下，一個程序被分割成數(shù)個基本任務(wù)，每個任務(wù)被分配到一個處理單元上運行。如果任務(wù)之間需要傳遞計算結(jié)果的數(shù)據(jù)，可以通過鄰接互聯(lián)數(shù)據(jù)線；距離較遠(yuǎn)的處理單元之間可以通過路由器傳遞數(shù)據(jù)。指令的阻塞模式特別適合近鄰之間的數(shù)據(jù)通信，因為該模式包含了數(shù)據(jù)傳輸必需的同步操作。

2.2 數(shù)據(jù)級并行(SIMD)運行方式

SIMD運行方式特別適合數(shù)據(jù)級并行處理。因為圖形和圖像處理的運算中很常見四維向量，因此可以用一行處理單元來做SIMD的四維并行運算。如果需要做四維以上16維以下的運算，那就可以使用2～4行處理單元(8～16個處理器)來進行SIMD并行運算。

當(dāng)一行中進行SIMD運算時，該行的控制器CR將指令廣播到這一行中的處理單元，每個單元使用自己的數(shù)據(jù)來執(zhí)行同樣的指令。

如果需要使用多行處理單元進行SIMD運算，簇控制器將指令廣播到相關(guān)的行處理器，再由行處理器廣播到相關(guān)處理單元。

2.3 分布式指令級并行方式

分布式指令級并行計算的基礎(chǔ)是數(shù)據(jù)流計算。其執(zhí)行方法類似超標(biāo)量機器中的亂序執(zhí)行方式。螢火蟲2的分布式指令級并行計算采用計算結(jié)果直接鏈接的方法，無須使用寄存器重命名。這與數(shù)據(jù)驅(qū)動數(shù)據(jù)流的形式是一致的。

使用鄰接互聯(lián)寄存器或者共享存儲，相關(guān)指令直接鏈接起來。指令可以分配到許多處理單元中，因此實現(xiàn)了分布式指令級并行計算。

2.4 流處理運行方式

螢火蟲2的流處理方式類似于典型的FPGA或者ASIC流水線，也即所謂的操作并行處理方式[4]，但是每個單元處理的顆粒粗細(xì)程度可按照性能需求進行調(diào)整和配置。

對于此種運算方式，每個單元相當(dāng)于流水線的一級。在每個處理單元上分配一些簡單操作，重復(fù)執(zhí)行這些操作。一個處理單元的結(jié)果通過近鄰互聯(lián)傳遞到其它處理單元去，構(gòu)成邏輯上的流水線。

為了降低開銷，我們設(shè)有專用的循環(huán)設(shè)置指令。這些指令在流處理開始階段設(shè)置好背景循環(huán)計數(shù)器和循環(huán)界限計數(shù)器，在數(shù)據(jù)處理開始后就是零開銷了，大大優(yōu)化了處理速度。

3 處理單元結(jié)構(gòu)

處理單元的頻率通常在680 MHz以下，以降低功耗。每個處理單元可以執(zhí)行SIMD和MIMD兩種操作模式。每個處理單元由一個ALU、一個控制器、一個路由器、四個鄰接共享存儲、數(shù)據(jù)存儲和指令存儲組成，整體如圖3所示。該處理單元的一個特點是沒有寄存器文件，ALU直接從存儲器中讀取指令和數(shù)據(jù);另一個特點是直接尋址的鄰接共享存儲器及其兩種存取模式。

當(dāng)前片上SRAM(Static Random Access Memory)頻率可達4.8 GHz[18]，可以與最快的CPU速度匹配。一般較快的片上SRAM的頻率也能超過600 MHz。我們的設(shè)計很容易找到相匹配的片上SRAM，因此寄存器文件就不是必需的了。這就可以提高效率、降低功耗。

Figure 3 Structure of processing element圖3 處理單元結(jié)構(gòu)

下面是處理單元及其各個部件操作的詳細(xì)敘述:

(1)算術(shù)邏輯運算器ALU平均每個時鐘可以發(fā)出兩條指令。指令集將在后面詳細(xì)敘述。

在SIMD 模式中，ALU執(zhí)行來自于外部(行、簇)控制器的指令序列，數(shù)據(jù)來自于本地存儲或者鄰接存儲。ICTL是本地控制。屏蔽(MASK)指令用來讀寫本地屏蔽寄存器，進而控制SIMD操作。當(dāng)本地的屏蔽寄存器被置位時，這個處理單元進入閑置狀態(tài)，不執(zhí)行SIMD指令。屏蔽寄存器也可以被外部控制器讀寫。

在MIMD模式中，ALU執(zhí)行的指令序列來自于本地的指令存儲器(I-MEM)，數(shù)據(jù)來自于本地存儲D-MEM和鄰接存儲。

(2)路由器RU負(fù)責(zé)將數(shù)據(jù)傳送到遠(yuǎn)程處理單元。由于熒火蟲2采用近鄰互聯(lián)方式，數(shù)據(jù)傳輸有時需要多跳才能達到。路由器允許數(shù)據(jù)多播，可以實現(xiàn)數(shù)據(jù)流的多目標(biāo)扇出。

遠(yuǎn)程通信需要使用MOVT和MOVF指令。硬件加速器用來加快遠(yuǎn)程數(shù)據(jù)通信的速度。

MOVT和MOVF指令也按照阻塞和非阻塞兩種模式執(zhí)行。

遠(yuǎn)程函數(shù)調(diào)用和返回通過特殊指令和路由器實現(xiàn)。參數(shù)和返回值可以使用MOVT和MOVF指令來傳送。遠(yuǎn)程數(shù)據(jù)包最多可以攜帶8個字(32位)的數(shù)據(jù)。

(3)鄰接共享存儲M分為四個部分：Me(東)、Mw(西)、Ms(南)和Mn(北), 每部分用于一個方向的通信。這四個部分在邏輯上都是處理單元數(shù)據(jù)存儲的一部分，采用直接尋址。大部分指令都可以使用鄰接共享存儲。這部分存儲也可以被鄰居處理單元存取。共享存儲器的存取有兩種模式：

①阻塞模式(線程間同步):每個共享存儲地址都有一位數(shù)據(jù)有效位。當(dāng)讀取數(shù)據(jù)時，如果數(shù)據(jù)無效，則當(dāng)前線程進入等待狀態(tài)；如果數(shù)據(jù)有效，則讀取數(shù)據(jù)，并將其置于無效。當(dāng)寫入數(shù)據(jù)時，若數(shù)據(jù)無效則直接寫入，數(shù)據(jù)有效則等待。

②非阻塞模式(線程間異步):不管數(shù)據(jù)是否有效，直接讀取數(shù)據(jù)。寫入數(shù)據(jù)時也不管目標(biāo)地址數(shù)據(jù)是否有效。

(4)數(shù)據(jù)存儲器D-MEM為每個線程分配一個區(qū)域，最多八個區(qū)域。每個線程的數(shù)據(jù)存儲最大為4 K(32位)字。數(shù)據(jù)存儲采用分塊結(jié)構(gòu)，分為八塊。這可以有效降低數(shù)據(jù)存取的沖突。

(5)指令存儲(I-MEM)為每個線程分配一個區(qū)域，最多八個區(qū)域。每個區(qū)域最多為4 K條指令。指令存儲采用單塊結(jié)構(gòu)。

ALU中的指令讀取單元含有一個程序計數(shù)器PC和一個線程地址寄存器Creg。每個線程都分配一塊數(shù)據(jù)存儲，其基地址可以放在Creg中。上下文轉(zhuǎn)換只需要改變Creg的值，可以一步到位。上下文轉(zhuǎn)換時將當(dāng)前Creg值推入堆棧，然后載入新的Creg值。

處理單元還含有一個線程信息表，用來記錄每個線程的當(dāng)前狀態(tài)?？刂破饔眠@個線程表來實現(xiàn)一步到位的上下文轉(zhuǎn)換。

上面敘述了處理單元的操作。下面將講述處理單元的指令集結(jié)構(gòu)、流水線結(jié)構(gòu)以及控制結(jié)構(gòu)。

3.1 指令集結(jié)構(gòu)

處理單元的多數(shù)指令采用直接存儲尋址。指令執(zhí)行有兩種操作方式，大部分指令按照阻塞和非阻塞兩種方式執(zhí)行。部分指令還有直接數(shù)操作。每條指令通常有三個地址，其格式如圖4所示。

Figure 4 Format of the instruction
圖4 指令格式

螢火蟲2是為圖形、圖像和信號處理等應(yīng)用而設(shè)計的，用來作為專用計算加速器，目前還不考慮通用計算應(yīng)用。因此，其指令的操作數(shù)尋址方式是有一定局限性的。這主要表現(xiàn)在尋址范圍的大小。

指令有6位操作碼，2位標(biāo)志位，12位的目標(biāo)地址可以在4 KB范圍內(nèi)尋址，12位的A操作數(shù)地址，16位的B操作數(shù)地址(也可以是立即數(shù))。對于細(xì)粒度和中等粒度的并行處理，這樣的地址范圍足夠了。對于很粗粒度的應(yīng)用，程序可以分布到多個處理單元上。指令涵括下列類型：

(1)定點算術(shù)與邏輯指令類：如加、減、乘、除、移位、與、或、異或等指令。

(2)定點比較與轉(zhuǎn)移指令類：這類指令按照比較的結(jié)果決定是否轉(zhuǎn)移控制流。在SIMD模式下，轉(zhuǎn)移是用屏蔽棧來實現(xiàn)的。

(3)浮點算術(shù)指令類：如加、減、乘、除等指令。這些指令的操作數(shù)都是浮點數(shù)。

(4)浮點比較與轉(zhuǎn)移指令類：這類指令按照比較的結(jié)果決定是否轉(zhuǎn)移控制流。在SIMD模式下，轉(zhuǎn)移是用屏蔽棧來實現(xiàn)的。

(5)跳轉(zhuǎn)與函數(shù)調(diào)用類指令：實現(xiàn)無條件跳轉(zhuǎn)、函數(shù)(包括SIMD函數(shù))的調(diào)用和返回、以及遠(yuǎn)程函數(shù)調(diào)用和返回。

(6)上下文轉(zhuǎn)換與SIMD屏蔽類指令：包括改變Creg值、上下文堆棧操作和SIMD屏蔽等指令。

(7)循環(huán)設(shè)置類指令：這類指令是為了高效實現(xiàn)OLP運算而設(shè)置的。循環(huán)設(shè)置好后就進入OLP模式執(zhí)行。

(8)遠(yuǎn)程與近鄰?fù)ㄐ蓬愔噶睿喊∕OVT、MOVF和MOVL。

處理單元的指令集結(jié)構(gòu)包含了不少特殊指令，是為了最有效地實現(xiàn)三種基本并行處理模式而設(shè)計的，這樣有利于高性能實現(xiàn)數(shù)據(jù)流計算方式。

3.2 處理單元流水線結(jié)構(gòu)

本文采用了兩種可編程處理單元，兩種處理單元均采用簡單和低功耗的設(shè)計，因此沒有采用類似于超標(biāo)量機器指令級并行ILP[7]的執(zhí)行機制。數(shù)據(jù)與控制冒險(Data and Control Hazards)采用兩種方法來處理：

(1)利用阻塞執(zhí)行模式來實現(xiàn)數(shù)據(jù)流類型的處理方式，還可以實現(xiàn)分布式指令并行化。

(2)依賴編譯器和良好的程序設(shè)計來處理。編譯和匯編程序幫助解決數(shù)據(jù)相關(guān)性問題。

浮點處理器的流水線如圖5所示。

這是一個比較簡單的多功能、多周期流水線。流水線包括了指令讀取(Instruction Fetch-IFETCH)、指令解碼(DECODER)、執(zhí)行(Execute)和回寫(WriteBack)。其中執(zhí)行含有六條執(zhí)行流水線，每條都有其自己的執(zhí)行周期。包含了整數(shù)算術(shù)邏輯運算器(ALU)、整數(shù)乘法器(MULT)、整數(shù)除法器(DIV)、浮點運算器(FPU)、浮點乘法器(FMUL)和浮點除法器(FDIV)。

為了提高效率，還采用了計算結(jié)果前饋機制(FEEDFWD)。整個流水線由流水線控制器(CONTROL)來協(xié)調(diào)操作。圖5中還標(biāo)出了指令存儲(INSTR MEMORY)和數(shù)據(jù)存儲(DATA MEMORY)。除了執(zhí)行本地指令流，流水線還可以執(zhí)行來自外部控制(Cluster Control)的SIMD指令流。

定點處理單元的結(jié)構(gòu)類似于浮點處理單元，只是其ALU、MULT和DIV流水線采用了多格式定點數(shù)方式，不同于普通的整數(shù)處理器。此外，其中的FPU被另一個ALU替換，F(xiàn)MUL被另一個MULT替換，F(xiàn)DIV被取消了。

3.3 單元整體控制器結(jié)構(gòu)

這個部件集成了處理流水線控制、路由器接口和多線程管理的功能，是一個多功能的高層次控制器。它要監(jiān)測各個線程的執(zhí)行情況、鄰接共享存儲的存取以及路由器的輸入和輸出情況。下面是可能影響到處理單元正常工作的情況：

(1)阻塞模式下的數(shù)據(jù)到達與否。數(shù)據(jù)不足的指令就進入等待狀態(tài)?？刂破餍枰O(jiān)視近鄰處理單元的數(shù)據(jù)到達情況，把到達的新數(shù)據(jù)填補到等待的指令中，及時把補足了數(shù)據(jù)的指令恢復(fù)到ready狀態(tài)。

(2)來自于路由器的輸入和輸出。遠(yuǎn)程處理單元可能會向本地處理單元請求數(shù)據(jù)或者發(fā)送數(shù)據(jù)，也可能請求函數(shù)調(diào)用或者返回數(shù)據(jù)?？刂破餍枰O(jiān)視路由器的狀況，及時通知運算器并修改執(zhí)行狀態(tài)。

Figure 5 Arithmetic and logic pipeline of processing element圖5 處理單元的算術(shù)邏輯流水線

(3)運算器流水線的結(jié)果。本地流水線的結(jié)果也會輸出給正在等待的指令，控制器需要監(jiān)視這些結(jié)果的到達，把到達的新數(shù)據(jù)及時填補到等待的指令中，并把補足了數(shù)據(jù)的指令恢復(fù)到ready狀態(tài)。

如果一個線程被阻塞了，該線程就進入等待狀態(tài)，等到它需要的數(shù)據(jù)到達了，這個線程就被喚醒。每個線程的狀態(tài)都被記錄在線程狀態(tài)表中。通常，一個處理單元可以支持8～16個線程，當(dāng)前版本支持八個并發(fā)線程。線程標(biāo)識號(Thread ID)用來選擇表項。線程狀態(tài)表中一些重要域的意義是：

(1)rank域中的值是調(diào)度優(yōu)先值，0為最高。

(2)PC域中是該線程當(dāng)前要執(zhí)行的指令地址。

(3)state 域中保存了線程的當(dāng)前狀態(tài)，如INIT、WAIT、RUN等等。

(4)avail 域中每一位代表了一個數(shù)據(jù)的存在。只有當(dāng)操作數(shù)都存在而目標(biāo)地址的數(shù)不存在時才能恢復(fù)線程的執(zhí)行。

(5)mask位標(biāo)志一個操作數(shù)是否被該指令使用。

(6)stamp是個時間戳，用來計量一個線程在當(dāng)前量子(Quantum)范圍內(nèi)的運行時間，為線程調(diào)度提供信息。

(7)M-base 是線程數(shù)據(jù)的基地址，M-size 是分配給線程的數(shù)據(jù)存儲大小。

控制器還要負(fù)責(zé)與路由器的協(xié)調(diào)工作，接收外來數(shù)據(jù)或者發(fā)送數(shù)據(jù)給遠(yuǎn)程處理單元。目前可配置的線程調(diào)度算法[19,20]有輪循算法(Round-Robin)和動態(tài)優(yōu)先權(quán)(Dynamic Priority)算法。

4 通信機制

熒火蟲2使用了一系列進程通信的硬件機制，包括近鄰共享存儲、遠(yuǎn)程數(shù)據(jù)傳輸和遠(yuǎn)程函數(shù)調(diào)用。信息傳遞(Message Passing)使用了由處理單元包含的路由器和互聯(lián)組成的全局網(wǎng)絡(luò)。這里介紹幾種信息傳遞機制。

4.1 鄰接共享存儲與直接尋址

螢火蟲2在簇內(nèi)采用了mesh拓?fù)浣Y(jié)構(gòu)來實現(xiàn)信息傳遞網(wǎng)絡(luò)。與先進的編譯技術(shù)與映射方法相結(jié)合，可以得到良好的網(wǎng)絡(luò)性能，使得信息流量保持在網(wǎng)絡(luò)的容量之內(nèi)。

第一種信息傳遞機制就是近鄰共享存儲。每一對鄰接的處理單元之間都有一對聯(lián)線組和共享存儲器，如圖6所示，其容量通常在4～16個字之間。共享存儲的訪存地址映射在數(shù)據(jù)訪存空間之內(nèi)。處理單元可以通過共享存儲把信息傳送給鄰居單元。

Figure 6 Communication of direct read/write neighbor shared memory圖6 直接讀寫近鄰共享存儲通信方式

為了便于實現(xiàn)數(shù)據(jù)流類型的操作并行計算，每個共享存儲地址都有一個數(shù)據(jù)有效位。當(dāng)有數(shù)據(jù)寫入這個地址時，這個數(shù)據(jù)有效位就被置位。當(dāng)這個位置的數(shù)據(jù)被讀取后，數(shù)據(jù)有效位就被復(fù)位。

共享存儲區(qū)域通常在可尋址空間的最上部，可供兩個相連的處理單元直接存取。當(dāng)前的設(shè)計可尋址的空間是4 KB。一個PE至多有四個鄰居，也就有四個共享存儲區(qū)域。四個共享存儲區(qū)域都設(shè)置在數(shù)據(jù)訪存可尋址空間上部。

Figure 7 Graphic interface of emulator圖7 仿真器頂層圖形界面

4.2 路由器和遠(yuǎn)程數(shù)據(jù)傳輸

處理單元內(nèi)的路由器用來傳遞信息。路由器與ALU并行操作，實現(xiàn)高性能的并行處理。數(shù)據(jù)傳遞包括常見的點到點傳遞、多播傳遞和函數(shù)調(diào)用。路由器需要與本地運算器和四個鄰接處理單元協(xié)作來完成信息傳遞功能。路由器需要處理的本地信息傳遞請求包括：

(1)本地數(shù)據(jù)發(fā)送請求，來自于MOVT指令；

(2)本地向遠(yuǎn)程處理單元發(fā)出的數(shù)據(jù)請求，來自于MOVF指令；

(3)本地多播信息請求，來自于MOVT指令。

路由器還需要處理來自外部的信息。外部信息傳遞請求包括：

(1)來自遠(yuǎn)程處理單元的信息傳遞請求，由遠(yuǎn)程處理單元產(chǎn)生；

(2)來自鄰居的多播信息請求，由鄰居的MOVT多播模式產(chǎn)生；

(3)遠(yuǎn)程的數(shù)據(jù)請求，來自遠(yuǎn)程處理單元。

除了處理上述信息傳遞功能外，路由器還需要處理本地和遠(yuǎn)程的函數(shù)調(diào)用和返回請求。這將在下一節(jié)中敘述。

4.3 遠(yuǎn)程函數(shù)調(diào)用

遠(yuǎn)程函數(shù)調(diào)用在本文的體系結(jié)構(gòu)中使用硬件加速來實現(xiàn)，比一般的機器性能要高。遠(yuǎn)程函數(shù)調(diào)用包括命令與數(shù)據(jù)兩部分。在本地運算器上產(chǎn)生的遠(yuǎn)程函數(shù)調(diào)用包括：

(1)本地的遠(yuǎn)程函數(shù)調(diào)用請求，源于遠(yuǎn)程模式的函數(shù)調(diào)用CALL指令，還有SIMD函數(shù)的調(diào)用請求。

(2)本地函數(shù)返回請求，來自于遠(yuǎn)程模式的函數(shù)調(diào)用RET指令。該RET是由其他處理單元送過來的CALL請求間接產(chǎn)生的。

來自于遠(yuǎn)程處理單元的請求包括：

(1)來自于遠(yuǎn)程的函數(shù)調(diào)用請求，由遠(yuǎn)程處理單元上的CALL指令產(chǎn)生；

(2)來自于遠(yuǎn)程的RET請求和數(shù)據(jù)，由遠(yuǎn)程處理單元產(chǎn)生。其數(shù)據(jù)部分是函數(shù)返回的結(jié)果數(shù)據(jù)。

遠(yuǎn)程函數(shù)調(diào)用由ALU和路由器協(xié)調(diào)處理。

5 軟件仿真環(huán)境

為螢火蟲2號多態(tài)陣列機開發(fā)了一套時鐘精確仿真平臺。這是一套模塊化的仿真環(huán)境，各個部件可以很容易地從開發(fā)環(huán)境中插入或者移出，一個新的功能部件可以很容易地替換舊的功能部件。

該平臺包含一個時鐘精確的仿真器和查錯器、一個匯編器和一個表達式語言編譯器、配置器和配置文件以及圖形界面，形成了一個完整的開發(fā)環(huán)境(IDE)。圖7示出了該環(huán)境的頂層界面，包括了幾個程序編輯窗口和一個匯編/編譯窗口。

在系統(tǒng)級層次，每個簇和其中的各種加速器、前端處理器、全局加速器等，都可以用數(shù)據(jù)通道可配置協(xié)議接入到全局互聯(lián)上。包括互聯(lián)在內(nèi)的部件都是可以直接插入使用的部件。數(shù)據(jù)通道的數(shù)據(jù)寬度是可配置的，數(shù)據(jù)傳輸使用簡單的雙軌握手協(xié)議(利用數(shù)據(jù)請求和應(yīng)答信號)。

一個簇中的各種控制器、處理單元、存儲器以及處理單元間的互聯(lián)通道，都是可以直接插入使用的部件。使用雙軌協(xié)議的數(shù)據(jù)互聯(lián)通道也都是直接插入使用的部件。

值得一提的是，全局互聯(lián)和處理單元間的數(shù)據(jù)互聯(lián)通道都是用函數(shù)來實現(xiàn)，如此，我們就可以模擬一個互聯(lián)通道的各種參數(shù)，例如時延和緩存深度等。因此可以得到很詳細(xì)的仿真結(jié)果。

查錯器可以讓我們在不同的層面上觀察系統(tǒng)的執(zhí)行狀態(tài)，可以從一個較高層次上逐層深入到更低的層次中，直到某個具體的處理器單元。圖8給出了一個處理單元的查錯界面。

Figure 8 Graphical interface of processing element圖8 處理單元的圖形界面

該仿真平臺是我們的重要工具之一。我們在仿真平臺上已經(jīng)進行了大量的實驗，得到許多有用的結(jié)果，在仿真平臺上能夠執(zhí)行的程序，下載到FPGA驗證板上也都能夠正確執(zhí)行。

6 性能仿真及結(jié)果

本節(jié)給出了初步的仿真實驗結(jié)果。雖然我們在FPGA上實現(xiàn)了一個雛形樣機，但是它的接口速度很慢，配套軟件也比較原始，使用不太方便，因此性能結(jié)果多半來自時鐘精確仿真器。需要指出的是仿真平臺的結(jié)果與RTL實現(xiàn)非常接近的。當(dāng)使用較少數(shù)目的處理單元時，仿真結(jié)果與FPGA實現(xiàn)的結(jié)果是一致的。

對圖形管線中的重要任務(wù)都進行了性能分析，包括模型視力矩陣乘積、頂點變換、平面剪裁等。ILP運算方式的加速度結(jié)果如圖9所示，橫軸表示計算單元的個數(shù)，縱軸表示加速比。

Figure 9 ILP acceleration of matrix multiply/vertex transform/plane clip圖9 矩陣乘積/頂點變換/平面剪裁的ILP運算加速比

由圖9可見，使用了16個處理單元的加速比都不低于10,該結(jié)果非常好，幾個應(yīng)用的加速比都是線性的。

圖10給出了TLP運算方式的加速比結(jié)果。其結(jié)果也呈線性加速，比ILP的要好。但這并不意味著使用TLP并行運算總是要優(yōu)于ILP并行運算，畢竟，程序中固有的ILP并行程度[7]是十分有限的。

Figure 10 TLP acceleration of graphic parallel computing圖10 圖形并行運算的TLP加速比

除了圖形管線中的運算外，我們還對幾個生物信息的算法做了并行化，并在螢火蟲2上進行了仿真實驗。對模體識別(Motif Finding)和全局匹配兩算法進行TLP并行運算，實驗結(jié)果如圖11所示。

Figure 11 TLP parallel computing results of the biological information algorithm圖11 生物信息算法的TLP并行運算結(jié)果

7 結(jié)束語

螢火蟲2號是一種適合于圖像、圖形和數(shù)字信號處理的高性能陣列機結(jié)構(gòu)，它結(jié)合了SIMD、MIMD、FPGA的優(yōu)點，能夠針對多種不同的應(yīng)用來實現(xiàn)接近ASIC的高性能計算。它能夠有機地、無縫地將數(shù)據(jù)級并行運算、線程級并行運算、指令級并行運算和操作并行運算相結(jié)合。螢火蟲2的處理單元采用了多種硬件加速方法，包括硬件線程管理、背景循環(huán)指令、阻塞與非阻塞的鄰接存儲方法、簡單快速的信息傳遞機制等，可以有效地節(jié)省功耗，同時高效地并行運算。

今后的研究重點是針對機器結(jié)構(gòu)的編程方法、編譯器實現(xiàn)和映射方法，以及各種圖形、圖像和數(shù)字信號處理算法在螢火蟲2上面的實現(xiàn)。

[1] Compton K,Hauk S. Reconfigurable computing:A survey of systems and software[J]. ACM Computing Surveys, 2002,34(2):171-210.

[2] Hideharu A. A survey on dynamically reconfigurable processors[J]. IEICE Transactions on Communications, 2006,E89-B(12):3179-3187.

[3] Flynn M.Some computer organizations and their effectiveness[J]. IEEE Transactions on Computers, 1972,21(9):948.

[4] Shen X B.Evolution of MPP SoC architecture techniques[J]. Science in China-Series F:Information Science, 2008,51(6):756-764.

[5] Hillis D. New computer architectures and their relationship to physics or why CS is no good[J]. International Journal of Theoretical Physics, 1982,21(3/4):255-262.

[6] Quinn M J. Parallel programming in C with MPI and OpenMP[M]. NY:McGraw-Hill, 2004.

[7] Hennessey J, Patterson D. Computer architecture:A quantitative approach[M]. 4th Ed. San Francisco:Morgan Kauffmann, 2006.

[8] Veen A H. Dataflow machine architecture[J]. Computing Surveys, 1986,18(4)365-396.

[9] Dennis J B, Misunas D P. A preliminary architecture for a basic data-flow processor[C]∥Proc of ISCA’75, 1975:125-131.

[10] Kilts S. Advanced FPGA design:Architecture, implementation, and optimization[M]. New Jersey:Wiley-IEEE, 2006.

[11] Harris M. Mapping computational concepts to GPUs[C]∥Proc of ACM SIGGRAPH’05, 2005:1.

[12] Nickolls J, Dally W J. The GPU computing era[J]. IEEE Micro, 2010,30(2):56-69.

[13] Keckler S W, McKinley K S, Dahlin M, et al. Scaling to the end of silicon with EDGE architectures[J]. IEEE Computer, 2004,37(7):44-55.

[14] Silc J, Robic B, Ungerer T. Asynchrony in parallel computing:From dataflow to multithreading[J]. Journal of Parallel and Distributed Computing Practices, 1998,1(1):3-30.

[15] Woo D H, Lee H S. Extending Amdahl’s law for energy-efficient computing in the many-core era[J]. IEEE Computer, 2008,41(12):24-31.

[16] Keckler S W, Dally W J, Khailany B, et al. GPUS and the future of parallel computing[J]. IEEE Computer, 2011,44(9):7-17.

[17] Marowka A, Gan R. Back to thin-core massively parallel processors[J]. IEEE Computer,2011,44(12):49-54.

[18] Dhong S H, Takahashi O, Yoshihara H, et al. A 4.8 GHz fully pipelined embedded SRAM in the streaming processor of a cell processor[C]∥Proc of IEEE International Solid-State Circuits Conference,2005:486-612.

[19] Li T, Baumberger D, Koufaty D A, et al. Efficient operating system scheduling for performance-asymmetric multi-core architectures[C]∥Proc of the 2007 ACM/IEEE Conference on Supercomputing, 2007:1.

[20] Liu C L, Layland J W. Scheduling algorithms for multiprogramming in a hard-real-time environment[J]. Journal of the ACM, 1973,20(1):46-61.

[21] Huang H-C, Li T, Han J-G. Simulator implementation and performance study of a polymorphous array computer[C]∥Proc of ISPA’13, 2013:1.

LITao,born in 1954,PhD,professor,CCF member(E200028228M)，his research interests include computer architecture, ASIP design, and VLSI design.

楊婷(1989-),女,陜西澄城人，碩士生，研究方向為計算機體系結(jié)構(gòu)、計算機圖形學(xué)和集成電路設(shè)計。E-mail:yangting198962@163.com

YANGTing,born in 1989,MS candidate,her research interests include computer architecture，computer graphics，and VLSI design.

易學(xué)淵(1987-),男,湖北黃岡人，碩士生，研究方向為計算機體系結(jié)構(gòu)、計算機圖形學(xué)和集成電路設(shè)計。E-mail:yxy19897891@163.com

YIXue-yuan,born in 1987,MS candidate,his research interests include computer architecture，computer graphics，and VLSI design.

蒲林(1989-),男,重慶人，碩士生，研究方向為計算機體系結(jié)構(gòu)、計算機圖形學(xué)和集成電路設(shè)計。E-mail:pulinup@126.com

PULin,born in 1989,MS candidate,his research interests include computer architecture，computer graphics，and VLSI design.

錢博文(1988-),男,安徽蒙城人，碩士生，研究方向為計算機體系結(jié)構(gòu)、計算機圖形學(xué)和集成電路設(shè)計。E-mail:bymoney@126.com

QIANBo-wen,born in 1988,MS candidate,his research interests include computer architecture，computer graphics，and VLSI design.

黃光新(1986-),男,陜西安康人，碩士生，研究方向為計算機體系結(jié)構(gòu)、計算機圖形學(xué)和集成電路設(shè)計。E-mail:bymoney@126.com

HUANGGuang-xin,born in 1986,MS candidate,his research interests include computer architecture，computer graphics，and VLSI design.

黃虎才(1989-),男,廣西陽朔人，碩士生，研究方向為計算機體系結(jié)構(gòu)、計算機圖形學(xué)和系統(tǒng)軟件。E-mail:chinahhucai@gmail.com

HUANGHu-cai,born in 1989,MS candidate,his research interests include computer architecture，computer graphics，and system software.

韓俊剛(1943-),男,吉林長春人，碩士，教授，研究方向為軟件和硬件的形式化驗證、圖形處理器和新型計算機體系結(jié)構(gòu)。E-mail:hanjungang@xupt.edu.cn

HANJun-gang,born in 1943,MS,professor,his research interests include the formal verification of software and hardware, graphics processor, and the new computer architecture.

Architectureofapolymorphousparallelcomputer

LI Tao1,YANG Ting1,YI Xue-yuan1,PU Lin1,QIAN Bo-wen1,HUANG Guang-xin2,HUANG Hu-cai2,HAN Jun-gang2

(1.School of Electronic Engineering,Xi’an University of Posts and Telecommunications,Xi’an 710061;2.School of Computer Science,Xi’an University of Posts and Telecommunications,Xi’an 710061,China)

A novel and efficient polymorphous array architecture, the Firefly2, is proposed. Its Processing Element (PE) can run in both SIMD and MIMD modes. The PE supports asynchronous inter-thread communication and efficient parallel execution of distributed instructions. A PE contains a multi-thread manager to realize one-step context switching and a router for fast data communication. This architecture is highly efficient in realizing parallel computation at thread level, data level, and instruction level. In particular, the performance of this architecture is comparable with ASIC when used for stream processing. This architecture is capable of implementing high-performance, classical static and dynamic dataflow computation. The architecture is designed for computer graphics, image processing and digital signal processing applications.

array computer;polymorphous processor;computer graphics;image processing;digital signal processing;data level parallelism;thread level parallelism;instruction level parallelism

2013-08-11;

：2013-10-20

國家自然科學(xué)基金重大項目(61136002)；西安郵電大學(xué)陜西省2012重點學(xué)科建設(shè)西郵計算機體系結(jié)構(gòu)項目

1007-130X(2014)02-0191-10

TP303

：A

10.3969/j.issn.1007-130X.2014.02.001

李濤(1954-),男,河北饒陽人，博士，教授，CCF會員(E200028228M)，研究方向為計算機體系結(jié)構(gòu)、專用機器設(shè)計和集成電路設(shè)計。E-mail:litao@xupt.edu.cn

通信地址：710061 陜西省西安市紅專南路西安郵電大學(xué)18樓1611室Address:Room 1611,Building 18,Xi’an University of Posts and Telecommunications,Hongzhuan Rd South, Xi’an 710061,Shaanxi,P.R.China