史媛芳，李潤(rùn)豐

（1.安徽國(guó)防科技職業(yè)學(xué)院 機(jī)電工程系 安徽 六安 237011；2.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230009）

基于縱向優(yōu)先多播路由算法的片上網(wǎng)絡(luò)路由器設(shè)計(jì)

史媛芳1，李潤(rùn)豐2

（1.安徽國(guó)防科技職業(yè)學(xué)院 機(jī)電工程系 安徽 六安 237011；2.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230009）

設(shè)計(jì)了一種支持多播通信技術(shù)的簡(jiǎn)單片上路由器，采用“縱向優(yōu)先”的多播路由算法和蟲孔交換技術(shù)，實(shí)現(xiàn)同時(shí)向指定區(qū)域內(nèi)多個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)的功能。通過仿真驗(yàn)證了算法有效可用，在節(jié)約網(wǎng)絡(luò)資源、提高系統(tǒng)工作效率方面，具有實(shí)用性。

片上網(wǎng)絡(luò)；多播通信；多播路由器；縱向優(yōu)先

20世紀(jì)90年代末期，傳統(tǒng)的片上系統(tǒng)（SoC）的總線架構(gòu)已不能應(yīng)對(duì)隨著半導(dǎo)體技術(shù)發(fā)展而出現(xiàn)的一些問題，比如可擴(kuò)展性、時(shí)間同步和并行通信等，為了彌補(bǔ)這些不足，研究機(jī)構(gòu)正式提出了片上網(wǎng)絡(luò)（NoC）的概念。當(dāng)前，國(guó)內(nèi)外對(duì)片上網(wǎng)絡(luò)技術(shù)的研究范圍主要集中在體系結(jié)構(gòu)、操作系統(tǒng)、設(shè)計(jì)方法、設(shè)計(jì)工具及應(yīng)用服務(wù)等領(lǐng)域［1］。隨著集成電路技術(shù)的不斷發(fā)展，芯片越來越多地由第三方提供的IP核集成，形成具有眾核的大規(guī)模集成電路；而對(duì)芯片中眾多的IP核進(jìn)行快速有效的測(cè)試，會(huì)遇到許多問題，如測(cè)試時(shí)間過長(zhǎng)與測(cè)試功耗過大的問題。研究表明，合理使用并行測(cè)試的方法則能有效地解決這些問題［2］。將網(wǎng)絡(luò)通信技術(shù)運(yùn)用在NoC芯片測(cè)試中是目前芯片測(cè)試的主要手段。NoC的數(shù)據(jù)傳送方式主要是單播通信和多播通信，多播通信技術(shù)的出現(xiàn)是多核并行處理的需求［3］。在數(shù)據(jù)傳輸與芯片測(cè)試中，片上路由器實(shí)現(xiàn)了網(wǎng)絡(luò)互連、網(wǎng)絡(luò)處理和網(wǎng)絡(luò)管理的功能，它是NoC設(shè)計(jì)中最重要的部分，也是實(shí)現(xiàn)高性能NoC的關(guān)鍵［4］。

1 多播路由器設(shè)計(jì)

片上網(wǎng)絡(luò)路由器的設(shè)計(jì)過程主要涉及輸入存儲(chǔ)、路由算法、虛擬通道仲裁、交叉開關(guān)和鏈路控制技術(shù)等幾方面的問題。

1.1 總體結(jié)構(gòu)設(shè)計(jì)

本文所設(shè)計(jì)的路由器是一個(gè)可以實(shí)現(xiàn)多播通信的簡(jiǎn)單的片上路由器，它運(yùn)用基于“縱向優(yōu)先”思想的X-Y路由策略，采用蟲孔交換技術(shù)，通過建立虛電路的方式進(jìn)行數(shù)據(jù)的傳送，傳送方向是一個(gè)指定大小的矩形區(qū)域。路由器由輸入控制及路由仲裁器、交叉選擇開關(guān)、輸出緩沖及控制器三大部分組成。其中：輸入控制及路由仲裁器用來接收數(shù)據(jù)，解析目的地址，同時(shí)選擇傳輸方向；交叉選擇開關(guān)根據(jù)路由仲裁器發(fā)來的方向傳送數(shù)據(jù)包；輸出緩沖及控制器則負(fù)責(zé)發(fā)送數(shù)據(jù)。

本方案涉及“東、西、南、北、本地”五個(gè)方向的數(shù)據(jù)輸入和數(shù)據(jù)輸出。圖1為路由器的總體結(jié)構(gòu)框架及主要引腳圖。由圖1可以看出，5×5的交叉選擇開關(guān)將從5個(gè)方向輸入的數(shù)據(jù)傳送到不同的方向，實(shí)現(xiàn)路由最基本的存儲(chǔ)和轉(zhuǎn)發(fā)功能。圖中的L、E、W、S、N分別表示本地、東、西、南、北。

圖1 路由器的總體結(jié)構(gòu)

由于方案采用的路由是基于蟲孔交換技術(shù)的，因此，在輸出端口設(shè)置了一個(gè)輸出緩存（buffer），這個(gè)緩存的大小設(shè)為數(shù)據(jù)流控制單位的大小，即一個(gè)微片的大小。當(dāng)某個(gè)路由阻塞時(shí)，未發(fā)出的微片就存儲(chǔ)在這個(gè)緩存中，同時(shí)阻止上一個(gè)路由向本路由發(fā)送數(shù)據(jù)。

1.2 多播路由器的關(guān)鍵技術(shù)

設(shè)計(jì)路由器還要包括數(shù)據(jù)包格式、路由協(xié)議和轉(zhuǎn)發(fā)策略各個(gè)方面。其中，路由策略包括確定性路由和自適應(yīng)路由兩大類。前者使用較多的是維序路由，主要包括X-Y路由和E-code路由兩大類；后者中最常用的是自適應(yīng)X-Y路由。由于片上網(wǎng)絡(luò)面積和功耗等條件的制約，要求路由算法不能過于復(fù)雜，因此，簡(jiǎn)單無死鎖的X-Y路由最為常用，即先在X方向、再在Y方向上傳送數(shù)據(jù)，只要源節(jié)點(diǎn)和目的節(jié)點(diǎn)固定，數(shù)據(jù)包的傳輸路徑也就固定了［5］。

蟲孔交換技術(shù)是將發(fā)送的消息，也就是數(shù)據(jù)包，分割為若干個(gè)微片，分別緩存在路由器中。每個(gè)數(shù)據(jù)包的頭微片包含控制路由信息，剩余的微片以流動(dòng)的方式在向前“蠕動(dòng)”，如果遇到阻塞，流動(dòng)中的微片則存儲(chǔ)在阻塞發(fā)生時(shí)所在的節(jié)點(diǎn)里面［5-6］。此時(shí)，每個(gè)路由器只需緩存當(dāng)前微片，以及阻塞發(fā)生時(shí)暫時(shí)存儲(chǔ)進(jìn)來的幾個(gè)微片就可以了，而不需要緩存整個(gè)數(shù)據(jù)包。這樣，路由器所需緩存空間就可大大縮?。?］。

1.3 縱向優(yōu)先多播路由算法策略

當(dāng)數(shù)據(jù)微片到達(dá)目標(biāo)頂點(diǎn)時(shí)，目標(biāo)頂點(diǎn)會(huì)將數(shù)據(jù)微片復(fù)制并向矩形區(qū)域內(nèi)的X和Y方向同時(shí)發(fā)送。從X方向接收到微片的路由節(jié)點(diǎn)重復(fù)上一個(gè)頂點(diǎn)的發(fā)送方向，而從Y方向接收到微片的路由節(jié)點(diǎn)只需向Y方向發(fā)送即可，直到發(fā)送到矩形區(qū)域的邊界為止。這樣便能用最短的時(shí)間將數(shù)據(jù)微片傳送到矩形區(qū)域的每個(gè)節(jié)點(diǎn)，而不會(huì)造成數(shù)據(jù)的重傳和回傳。

圖2為縱向優(yōu)先多播路由算法實(shí)例圖。圖2是一個(gè)7×4 Mesh網(wǎng)絡(luò)NoC，數(shù)據(jù)包由A節(jié)點(diǎn)進(jìn)入，需要傳送到虛線框中的每個(gè)節(jié)點(diǎn)。通過比較A節(jié)點(diǎn)與該矩形四個(gè)頂點(diǎn)（即B、D2、D1和H）的路徑距離，系統(tǒng)確定A點(diǎn)離B點(diǎn)最近，因此將微片傳送到B節(jié)點(diǎn)。B節(jié)點(diǎn)將微片向右方和下方傳送，即向C2和C1傳送。當(dāng)微片到達(dá)C2時(shí)，C2判斷微片是由X方向傳送來的，因此C2將數(shù)據(jù)微片復(fù)制后，繼續(xù)向下方和右方傳送；而微片到達(dá)C1時(shí)，因?yàn)槲⑵怯蒠方向傳送而來，所以C1只將微片向下方發(fā)送。這樣便做到了在最短的時(shí)間內(nèi)讓矩形區(qū)域內(nèi)的所有節(jié)點(diǎn)都能接收到數(shù)據(jù)。

圖2 “縱向優(yōu)先的多播路由算法”實(shí)例圖

1.4 多播路由器各部件設(shè)計(jì)

1.4.1 數(shù)據(jù)包格式設(shè)計(jì)

本文設(shè)計(jì)的多播路由器具有將同一個(gè)數(shù)據(jù)包發(fā)送到指定大小矩形區(qū)域內(nèi)的IP核的功能。如IP核需要這些數(shù)據(jù)則接收，不需要?jiǎng)t自動(dòng)拋棄。因此數(shù)據(jù)包格式必須滿足矩形區(qū)域范圍地址均可到達(dá)的條件。

微片分為頭微片、中間微片和尾微片三種，通過前兩位標(biāo)志位區(qū)分，即“01”表示這個(gè)微片是頭微片，“10”表示中間微片，“11”表示尾微片。其中頭微片用來傳送目的地址信息，它讓路由器可識(shí)別到微片所要送達(dá)的目的地。路由識(shí)別后由交叉開關(guān)負(fù)責(zé)把微片送到正確的輸出端口。緊接著標(biāo)志位的八位為目的矩形對(duì)角線上一個(gè)頂點(diǎn)的地址，后八位為該對(duì)角線上另一頂點(diǎn)的地址，這樣可以確定唯一一個(gè)矩形區(qū)域；如果后八位全是“1”，則表示本數(shù)據(jù)包只有一個(gè)目的地址。中間微片和尾微片的任務(wù)是傳送具體數(shù)據(jù)，它們的前兩位也為標(biāo)志位，后16位是數(shù)據(jù)位。尾微片還可用來表示數(shù)據(jù)已經(jīng)傳送完畢。

1.4.2 輸入控制及路由仲裁器設(shè)計(jì)

輸入控制器是數(shù)據(jù)進(jìn)入路由器經(jīng)過的第一道關(guān)卡，而路由仲裁器則是用來解析數(shù)據(jù)頭微片，找出目的地址和傳送方向的關(guān)鍵部件。圖3為輸入控制及路由仲裁器的引腳示意圖。

由圖3可見，此部分主要有11條信號(hào)線，其中：“clk”是時(shí)鐘信號(hào)；“rst”是復(fù)位信號(hào)；“ads”是發(fā)送數(shù)據(jù)前注入的當(dāng)前路由器的地址信息，共8位，它用當(dāng)前路由在網(wǎng)絡(luò)中的X和Y坐標(biāo)來表示地址，“ads”的前四位表示X方向坐標(biāo)，后四位表示Y方向坐標(biāo)，注入“ads”信號(hào)后，當(dāng)前的路由地址不會(huì)再改變；“DataX_in”是上一個(gè)路由發(fā)來的數(shù)據(jù)信息；“ReqX_in”是上一個(gè)路由發(fā)來的請(qǐng)求發(fā)送數(shù)據(jù)信號(hào)；“AckX_out”是當(dāng)前路由器給上一個(gè)路由器發(fā)送的應(yīng)答信號(hào)，表示數(shù)據(jù)已經(jīng)收到；“DataX_sel”是輸入控制器向交叉選擇開關(guān)發(fā)送的數(shù)據(jù)信息；“ReqX_sel”是輸入控制器向交叉選擇開關(guān)發(fā)送的請(qǐng)求信號(hào)；“AckX_sel”則是交叉開關(guān)回復(fù)的應(yīng)答信號(hào)；“Select”是路由仲裁器發(fā)給交叉開關(guān)的方向選擇信號(hào)，此信號(hào)共5位，分別表示“本地、東、西、南、北”五個(gè)方向，當(dāng)需要向某一個(gè)或幾個(gè)方向傳送數(shù)據(jù)時(shí)，該方向所對(duì)應(yīng)的表示位置為“1”，否則為“0”，例如需要同時(shí)向“本地、南、北”三個(gè)方向傳送數(shù)據(jù)，則置Select為“10011”；“Keep_sel”是地址保持信號(hào)，從頭微片到達(dá)至尾微片到達(dá)始終置為“1”，起到保持虛電路的功能。

針對(duì)輸入控制器部分，可用循環(huán)的狀態(tài)轉(zhuǎn)換圖來實(shí)現(xiàn)。路由選擇算法則使用前文提到的“縱向優(yōu)先多播路由算法”。

圖3 輸入控制器和路由仲裁器信號(hào)及引腳示意圖

1.4.3 交叉選擇開關(guān)設(shè)計(jì)

交叉選擇開關(guān)是整個(gè)多播路由中最為重要的模塊之一，它負(fù)責(zé)將輸入控制及路由仲裁器輸送來的數(shù)據(jù)根據(jù)其路由信息轉(zhuǎn)發(fā)到一個(gè)或多個(gè)不同的端口，即實(shí)現(xiàn)多播通信功能。本文交叉開關(guān)的設(shè)計(jì)部分解決了實(shí)現(xiàn)在內(nèi)部向多端口傳輸數(shù)據(jù)的問題。

開關(guān)設(shè)計(jì)輸入和輸出端口各五個(gè)，本文只選取其中一個(gè)輸入端口與一個(gè)輸出端口進(jìn)行分析。圖4所示為交叉選擇開關(guān)的部分引腳與信號(hào)線。

圖4中，“DataL_sel”是本地（Local）輸入控制及路由仲裁器發(fā)來的數(shù)據(jù)信號(hào)；“ReqL_sel”為請(qǐng)求信號(hào)；“SelectL”為路由選擇信號(hào)，模塊根據(jù)這個(gè)信號(hào)來進(jìn)行輸出端口的選擇；“KeepL_sel”為虛電路保持信號(hào)，如果此信號(hào)為“1”，則不檢測(cè)新的路由選擇信號(hào)；“AckL_sel”為應(yīng)答信號(hào)；“Data_que”為交叉開關(guān)發(fā)送給輸出緩沖器的數(shù)據(jù)信息；“ReqL_que”為請(qǐng)求信號(hào)；“AckL_que”為應(yīng)答信號(hào)。

圖4 交叉選擇開關(guān)的部分引腳與信號(hào)線

1.4.4 輸出緩沖及控制器設(shè)計(jì)

輸出緩沖及控制器是用于控制數(shù)據(jù)輸出和緩存的重要模塊。此模塊結(jié)構(gòu)和輸入控制模塊結(jié)構(gòu)類似，不同的是“DataX_que”表示交叉開關(guān)發(fā)送來的數(shù)據(jù)信息，“ReqX_que”表示交叉開關(guān)發(fā)送來的請(qǐng)求信號(hào)，“AckX_que”表示應(yīng)答信號(hào)，“DataX_out”表示輸出控制器向下一個(gè)路由發(fā)送的數(shù)據(jù)信息，“ReqX_out”表示向下一個(gè)路由發(fā)送的請(qǐng)求信號(hào)，“AckX_in”表示下一個(gè)路由發(fā)來的應(yīng)答信號(hào)。

2 實(shí)驗(yàn)仿真

2.1 單個(gè)路由仿真

本文運(yùn)用Modelsim仿真軟件和Synplify綜合工具，來驗(yàn)證所設(shè)計(jì)的路由器的邏輯功能。將5個(gè)輸入控制與路由仲裁器、1個(gè)交叉選擇開關(guān)、5個(gè)輸出緩沖及控制器組合起來便構(gòu)成了一個(gè)簡(jiǎn)單的、支持多播功能的路由器。對(duì)其進(jìn)行數(shù)據(jù)輸入，并觀察它是否從正確的端口輸出。由于路由涉及的引腳多，本文僅選取幾個(gè)重要的引腳信號(hào)波形圖，圖5所示即為單個(gè)路由的部分仿真波形圖。

從圖5中可以看出，該路由地址為“00000000”，當(dāng)本地方向發(fā)來請(qǐng)求信號(hào)時(shí)，經(jīng)過解析頭微片看到，目的矩形頂點(diǎn)地址是“00010001”和“00000000”，可知該數(shù)據(jù)包的目的地址是位于對(duì)角線頂點(diǎn)“00010001”和“00000000”的矩形區(qū)域，也就是“00000000”“00010000”“00000001”“00010001”四個(gè)節(jié)點(diǎn)。經(jīng)判斷后得出傳送方向?yàn)闁|和南。在圖5中可以看到，東和南的輸出端口正確輸出了數(shù)據(jù)。

圖5 單個(gè)多播路由器仿真波形圖

2.2 多個(gè)路由仿真

本文用4個(gè)路由與4個(gè)簡(jiǎn)單的IP核組成一個(gè)2×2的NoC網(wǎng)絡(luò)。路由的地址用坐標(biāo)表示，分別用（0，0）、（0，1）、（1，0）、（1，1）代表。IP核是為了驗(yàn)證路由的正確性而設(shè)置的一個(gè)簡(jiǎn)單的裝置，只具備接收數(shù)據(jù)并在內(nèi)部緩存中存儲(chǔ)數(shù)據(jù)的功能。

對(duì)這個(gè)簡(jiǎn)單的支持多播技術(shù)的NoC網(wǎng)絡(luò)進(jìn)行編程測(cè)試。路由1輸入數(shù)據(jù)，目的路由節(jié)點(diǎn)是路由2和路由4組成的矩形區(qū)域。本文分別截取仿真過程中數(shù)據(jù)流經(jīng)的路由1、路由2、路由4、IP2和IP4的波形圖來說明數(shù)據(jù)在NoC網(wǎng)絡(luò)的傳輸過程。同樣，這里也只列出幾種主要的信號(hào)波形。

（1）路由1。圖6所示是路由1的波形圖。由圖6可見，路由1的地址是“00000000”，數(shù)據(jù)從北邊端口進(jìn)來，目的地址是“00010001”和“00010000”兩個(gè)節(jié)點(diǎn)為對(duì)角線的矩形區(qū)域，也就是路由2和路由4。由于該矩形區(qū)域是設(shè)置在路由1的右側(cè)，因此路由仲裁得出傳輸方向?yàn)椤?1000”，即向東傳送給路由2。從圖6中可以看出，東端口輸出正確的數(shù)據(jù)信息。

圖6 路由1波形圖（多播）

（2）路由2。圖7所示是路由2的波形圖，它的地址是“00010000”。由圖7可見，它接收到路由1傳來的信息后，經(jīng)過分析地址信息，得出該數(shù)據(jù)包需要向兩個(gè)方向發(fā)送，分別是南邊和本地。由圖7可見，南邊的輸出端口和本地的輸出端口先后發(fā)送出數(shù)據(jù)。數(shù)據(jù)將發(fā)送至路由器4和IP2。

圖7 路由2波形圖（多播）

（3）IP2。圖8所示是IP2的波形圖，可以看到節(jié)點(diǎn)2的IP核成功接收到了路由2發(fā)來的數(shù)據(jù)。

圖8 IP2波形圖（多播）

（4）路由4。圖9所示的是路由4的波形圖。從圖9中可以看到，路由4接收到路由2發(fā)來的數(shù)據(jù)信息后，解析得出該數(shù)據(jù)的目的地就是本地，因此路由選擇信號(hào)為“10000”。數(shù)據(jù)發(fā)送至本地輸出端口，即IP4。

圖9 路由4波形圖（多播）

（5）IP4。圖10所示是IP4的波形圖，可以看到節(jié)點(diǎn)4的IP核成功接收到了路由4發(fā)來的數(shù)據(jù)。

圖10 IP4波形圖（多播）

至此，含有兩個(gè)目的地址的信息都成功傳送到了目的節(jié)點(diǎn)，證明本文設(shè)計(jì)的路由器簡(jiǎn)單、有效。

3 結(jié)束語

在片上網(wǎng)絡(luò)互連結(jié)構(gòu)中，片上路由器用于支持報(bào)文的轉(zhuǎn)發(fā)、實(shí)現(xiàn)數(shù)據(jù)流的路由和存儲(chǔ)轉(zhuǎn)發(fā)數(shù)據(jù)包功能，是實(shí)現(xiàn)高性能片上網(wǎng)絡(luò)的關(guān)鍵。本文設(shè)計(jì)了一個(gè)簡(jiǎn)單的、支持多播通信的NoC路由。主要包括對(duì)數(shù)據(jù)包格式、路由仲裁器和交叉選擇開關(guān)等模塊的設(shè)計(jì)。該路由器能同時(shí)識(shí)別一個(gè)矩形區(qū)域內(nèi)的多個(gè)目的地址，并能正確地向多個(gè)不同的目的地發(fā)送數(shù)據(jù)，實(shí)現(xiàn)了多播路由器的雛形。經(jīng)過軟件仿真，證實(shí)它可以在復(fù)雜的環(huán)境中向規(guī)定矩形區(qū)域內(nèi)的目的地正確地發(fā)送數(shù)據(jù)信息，從而實(shí)現(xiàn)將信息向一片節(jié)點(diǎn)廣播。

［1］ 岳峰，李潤(rùn)豐，陳田，等.基于隨機(jī)路由的高性能片上路由器設(shè)計(jì)與仿真［J］.電子測(cè)量與儀器學(xué)報(bào)，2013（7）：669-675.

［2］ 方芳，韓銀和，李曉維.熱量敏感的眾核芯片多播并行測(cè)試方法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2010（5）：845- 851.

［3］ 方芳，董建波，韓銀和，等.支持多播路徑傳輸?shù)钠暇W(wǎng)絡(luò)并行測(cè)試方法［J］.電子測(cè)量與儀器學(xué)報(bào)，2010（10）：911-917.

［4］ 于鵬.片上網(wǎng)絡(luò)中路由器技術(shù)的研究［D］.西安：西安電子科技大學(xué)，2011.

［5］ 董少周.NoC路由算法及仿真模型的設(shè)計(jì)與研究［D］.合肥：合肥工業(yè)大學(xué)，2009.

［6］ 朱兵.基于片上網(wǎng)絡(luò)的通信路由方法研究［D］.合肥：合肥工業(yè)大學(xué)，2009.

【責(zé)任編輯 梅欣麗】

A New Design of Networks-on-chip Router with Longitudinal-priority-algorithm-based Multicast Routing

SHI Yuanfang1，LI Runfeng2
（1. Department of Electrical Engineering, Anhui National Defence Vocational College, Lu’an 237011, China； 2. School of Computer and Information, Hefei University of Technology, Hefei 230009, China）

In this paper, we designed a simple on-chip router to support multicast communication technology. By adopting the longitudinal-priority multicast routing algorithm and using the wormhole switching technology, sending data to multiple nodes within a designated region at the same time is achieved. Through simulated test, effective availability, this design has certain applicability in the aspects of saving network resources and raising the working efficiency of the system.

networks-on-chip； multicast communication； multicast router； longitudinal-priority

TP302

A

2095-7726（2015）03-0028-05

2015-01-01

2011年安徽省高等學(xué)校省級(jí)教學(xué)質(zhì)量與教學(xué)改革工程項(xiàng)目

史媛芳（1984-），女，安徽壽縣人，碩士，研究方向：計(jì)算機(jī)應(yīng)用技術(shù)和人工智能。