周延鵬，張興明

（國際數(shù)字交換系統(tǒng)工程技術(shù)研究中心 河南 鄭州450002）

交叉節(jié)點緩存crossbar交換結(jié)構(gòu)設(shè)計

周延鵬，張興明

（國際數(shù)字交換系統(tǒng)工程技術(shù)研究中心 河南 鄭州450002）

針對傳統(tǒng)交換結(jié)構(gòu)調(diào)度復(fù)雜且時間開銷大的問題，采用交叉點緩存（Buffered Crossbar）交換結(jié)構(gòu)和改進(jìn)的輪詢調(diào)度算法，在輸出端設(shè)置按一定的緩存順序輸出，并通過verilog代碼實現(xiàn)了8*8的CICQ交換結(jié)構(gòu)。極大地緩解了傳統(tǒng)Crossbar交換結(jié)構(gòu)存在的輸入輸出端口沖突問題，有效避免了隊頭阻塞問題。采用算法復(fù)雜度為O（1）的輪詢調(diào)度算法，硬件實現(xiàn)簡單。可以達(dá)到100%的吞吐效率，實現(xiàn)了最快3個時鐘周期的高速度低延時交換。

crossbar；交換結(jié)構(gòu)；調(diào)度算法；輪詢

Abstract:The traditional exchange structure is complicated and time scheduling overhead problem.Using a modified round-robin scheduling algorithm，at the output buffer is set according to a certain order of output，and by verilog code to achieve the 8*8 CICQ switch fabric.Greatly reducing the conflict of input and output ports of traditional crossbar switch fabric，effectively avoiding HOL blocking problem.Using an algorithm complexity is O（1） of the round-robin scheduling algorithm，hardware implementation simple.It can achieve 100%throughput efficiency，to achieve the fastest speed three clock cycles low latency switching.

Key words:crossbar；switch fabric； scheduiingaigorithm； round-robin

當(dāng)前，大容量、高性能的交換設(shè)備所采用的核心交換技術(shù)通常為交換結(jié)構(gòu)（Switch Fabric）[1-3]和調(diào)度算法（Schedule Algorithm）[1，4]兩個部分。 交換結(jié)構(gòu)負(fù)責(zé)的是報文高速轉(zhuǎn)，它的結(jié)構(gòu)和性能直接決定了交換機(jī)設(shè)備的應(yīng)用性能，因此，交換結(jié)構(gòu)的設(shè)計對網(wǎng)絡(luò)核心交換機(jī)的研制有著十分重要的意義。對于支持高鏈路帶寬和多端口的交換設(shè)備而言，其調(diào)度器的仲裁時間越短越好，這就需要調(diào)度算法所使用的仲裁時間盡量的短，也就是說調(diào)度算法的實現(xiàn)復(fù)雜度要盡可能的低。因此，在交叉開關(guān)交換結(jié)構(gòu)上尋求低復(fù)雜度、高吞吐量的調(diào)度算法具有非常重要的意義。常用的單Crossbar交換結(jié)構(gòu)可以分為輸入排隊[5-6]、輸出排隊[5-6]、聯(lián)合輸入輸出排隊和交叉緩存交換結(jié)構(gòu)[7，14]，目前大容量高速交換通常采用聯(lián)合輸入輸出排隊和交叉緩存（CICQ）[10]交換結(jié)構(gòu)。在做了理論分析的基礎(chǔ)上，設(shè)計實現(xiàn)了CICQ交換結(jié)構(gòu)和輪詢調(diào)度算法，該結(jié)構(gòu)能實現(xiàn)低延時的高速數(shù)據(jù)傳輸[15-17]。

1 CICQ交換結(jié)構(gòu)設(shè)計

CICQ是在CICQ交換結(jié)構(gòu)的基礎(chǔ)上增加了輸出緩存隊列設(shè)計。根據(jù)設(shè)計思路把CICQ交換結(jié)構(gòu)的組成可以分為3個部分：輸入端，交換單元，輸出端3部分組成。

CICQ交換結(jié)構(gòu)工作流程可分為4步，

第一步：包到達(dá)過程，即包進(jìn)入輸入端口后按照包信息緩存到對應(yīng)端口的對應(yīng)VOQ[1-9][11-12]緩存隊列；

第二步：輸入虛擬緩存隊列到交叉點緩存的調(diào)度過程，采用能夠用有效避免端口餓死的輪訓(xùn)調(diào)度算法；

第三步：交叉節(jié)點到輸出緩存的調(diào)度過程，同樣采用輪訓(xùn)調(diào)度算法[11-13]。

第四步：輸出緩存讀出過程，按一定優(yōu)先級進(jìn)行輸出過程；

圖1 CICQ結(jié)構(gòu)框圖

1.1 輸入端口

根據(jù)8*8 CROSSBAR交換結(jié)構(gòu)的需求，從上圖整體設(shè)計可以看出需要8個輸入端口，每個輸輸入端口設(shè)置8個VOQ虛擬緩存隊列分貝對應(yīng)8個不同的輸出端口。采用VOQ虛擬緩存能有效的避免交換結(jié)構(gòu)的對頭阻塞（HOL，Head of Line blocking）[8]問題。VOQ緩存采用深度為16，位寬為32的同步fifo設(shè)計下面對一個輸入端口進(jìn)行詳細(xì)介紹；

數(shù)據(jù)進(jìn)入交換結(jié)構(gòu)在輸入端口虛擬緩存在非滿狀態(tài)下根據(jù)要去往的輸出端口緩存至對應(yīng)的VOQ隊列，如圖2所示，r0_bus_data_i、r0_req_i均有效。r0_dest_port=8’b10000011時，數(shù)據(jù)就緩存在 VOQ0、VOQ1、VOQ7 中。

圖2 輸入端VOQ

1.2 交叉端

交叉端要完成的任務(wù)是從根據(jù)輸入調(diào)度算法從輸入端的虛擬緩存隊列中讀出數(shù)據(jù)并緩存到交叉點；

1）監(jiān)測輸入端VOQ虛擬緩存中是否有數(shù)據(jù)

2）監(jiān)測交叉點緩存（RN_CXB）是否為滿，即交叉點可以接受輸入端數(shù)據(jù)

3）當(dāng)滿足以上兩個條件時，根據(jù)輪訓(xùn)調(diào)度算法，依次從8個輸入端讀入數(shù)據(jù)緩存至交叉點緩存調(diào)度算法的實現(xiàn)將在后文詳細(xì)介紹。

1.3 輸出端

輸出端要完成的任務(wù)是根據(jù)輸出調(diào)度算法從交叉點緩存讀出數(shù)據(jù)至輸出緩存，在輸出緩存采先到先出的原則進(jìn)行讀出。以要從輸出端口一輸出為例，做如下介紹

1） 監(jiān)測 R0_CXB0、R1_CXB0、 到 RN_CXB3、中是否有數(shù)據(jù)；

2）監(jiān)測對應(yīng)輸出端緩存是否為滿，即輸出是否可以接收檢查點的數(shù)據(jù)；

3）當(dāng)滿足以上兩個條件時，根據(jù)輪訓(xùn)調(diào)度算法，依次從8個交叉點讀入數(shù)據(jù)緩存至輸出端緩存；

4）當(dāng)輸出緩存中有數(shù)據(jù)時按先到先出原則讀出數(shù)據(jù)；

2 調(diào)度算法設(shè)計

CICQ交換結(jié)構(gòu)采用的分布式調(diào)度，即輸入端到交叉點的輸入調(diào)度算法和交叉點到輸出端的輸出調(diào)度算法。本文采用的輸入和輸出調(diào)度算法核心都是輪訓(xùn)調(diào)度，實現(xiàn)方式類似。在此只對輸入調(diào)度進(jìn)行詳細(xì)介紹。

2.1 輸入調(diào)度

輸入調(diào)度流程如圖3所示。

圖3 輸入調(diào)度流程

調(diào)度算法流程：

1）監(jiān)測輸入端VOQ虛擬緩存中是否有數(shù)據(jù)，、監(jiān)測交叉點緩存（RN_CXB）是否為滿，即交叉點可以接受輸入端數(shù)據(jù)；

2）產(chǎn)生需要仲裁的端口請求信號備用；

3）第一次仲裁按照端口優(yōu)先級順序，即0到7依次降低的順序，假設(shè)第一次0端口有請求，就從0端口開始，仲裁結(jié)果就是0，并將請求緩存至“上一次請求寄存器”跳至步驟6）；

4）第一次讀出數(shù)據(jù)以后產(chǎn)生仲裁請求備用；

5）根據(jù)仲裁騎牛和當(dāng)前仲裁端口信息以及緩存寄存器信息產(chǎn)生仲裁結(jié)果；

6）根據(jù)仲裁結(jié)果從沖輸入VOQ緩存中讀出數(shù)據(jù)；

7）讀出數(shù)據(jù)緩存至交叉點緩存

8）結(jié)束。

2.2 輸出調(diào)度

輸出調(diào)度和輸入調(diào)度均采用輪詢算法，區(qū)別主有兩點

1）輸出調(diào)度中的進(jìn)入數(shù)據(jù)時緩存在輸出端口相同的交叉點緩存 （假設(shè)輸出端口為0，對應(yīng)的是R0_CBX0、R1_CBX0 到 R7_CBX0）；

2）數(shù)據(jù)輸出的緩存隊列不同于輸入調(diào)度的多個CBX緩存，而是多個CBX緩存至一個輸出緩存。

3 仿真驗證

仿真驗證環(huán)境為linux下的Vivado套件，由于仿真驗證工作繁瑣，所以只列出輸入調(diào)度、輸出調(diào)度、以及整體的仿真信息。

測試激勵說明：

對8個輸入端口全部進(jìn)行多播[7]形式數(shù)據(jù)寫入，這樣可以更全面地測試輸入和輸出調(diào)度以及數(shù)據(jù)輸出是否按照預(yù)期輪詢依次輸出。

3.1 調(diào)度仿真

輸入調(diào)度：

輸入調(diào)度做作用綜合考慮輸入緩存和交叉點緩存以及上一次調(diào)度結(jié)果，產(chǎn)生ib_grant仲裁信號。從圖4可以看出ib_grant能夠正常移位進(jìn)行輪詢調(diào)度。

圖4 輸入調(diào)度仿真

輸出調(diào)度：

輸出調(diào)度做作用綜合考慮交叉點緩存和輸出緩存以及上一次調(diào)度結(jié)果，產(chǎn)生ob_grant仲裁信號。從圖5可以看出ob_grant能夠正常移位進(jìn)行輪詢調(diào)度。

圖5 輸出調(diào)度仿真

3.2 系統(tǒng)仿真

系統(tǒng)及仿真主要體現(xiàn)輸入數(shù)據(jù)能否正常到達(dá)目標(biāo)端口，從圖6可以看出輸出信號能夠依次輸出，需要說明的是第一個輸出信號延遲較長，后邊達(dá)到流水輸出后就能夠達(dá)到最短3個時鐘延遲的告訴輸出。

圖6 系統(tǒng)仿真

3.3 硬件開銷

硬件開銷如圖7所示。

圖7 硬件開銷

4 結(jié) 論

本文主要研究了一種基于CICQ的crossbar交換結(jié)構(gòu)和基于輪訓(xùn)的調(diào)度算法，并通過Verilog編碼實現(xiàn)，在vivado工具下進(jìn)行了仿真和基本功能驗證以及網(wǎng)標(biāo)綜合，均達(dá)到設(shè)計要求。實現(xiàn)了流水輸出，最短輸出時間延遲為3個時鐘周期，該交換結(jié)構(gòu)和角度算法可以應(yīng)當(dāng)前很多交換設(shè)備在硬件電路設(shè)計和功能驗證方面具有一定的理論意義和應(yīng)用價值。

[1]王俊芳，張思東.通用高速分組交換調(diào)度算法[J].電子科技大學(xué)學(xué)報，2010（1）：69-73.

[2]韓永，姚念民，蔡紹濱，等.iSCSI虛擬交換機(jī)包轉(zhuǎn)發(fā)調(diào)度算法 FC-WFQ[J].電子學(xué)報，2013，41 （3）:587-592.

[3]蔣泳波，高速交換結(jié)構(gòu)多播技術(shù)研究[D].西安：西安電子科技大學(xué)，2013.

[4]高雅，邱智亮，張茂森，等.一種支持單組播混合交換的 Clos網(wǎng)絡(luò)及調(diào)度算法 [J].西安電子科技大學(xué)學(xué)報：自然科學(xué)版，2013，40（1）:48-52.

[5]徐寧，余少華，汪學(xué)舜.一種新型的負(fù)載均衡－交叉點緩沖交換結(jié)構(gòu) [J].電子學(xué)報，2012，40（12）:2360-2366.

[6]戴藝，蘇金樹，孫志剛.高性能新型交換結(jié)構(gòu)綜述[J].電子學(xué)報，2010，38（10）:2389-2399.

[7]Divakaran D M，AnhaltF，Altman E.Size-based flow scheduling in a CICQ switch[A].Dallas，USA:IEEE 2010.

[8]Rojas-Cessa， Roberto，Dong， Ziqian.Load-Balanced Combined Input-Crosspoint Buffered Packet Switches[J].IEEE Transactions on Communications 2011，5（5）.

[9]倪杰.用于三級Clos網(wǎng)絡(luò)的一種高效自尋路交換機(jī)制研究[D].成都：電子科技大學(xué)，2013.

[10]鄭若鹢.CICQ交換結(jié)構(gòu)的調(diào)度算法分析[J].電腦與信息技術(shù)，2010（6）：20-22.

[11]Lin D，Jiang Y，and M.Hamdi.Selective Request Round-Robin Scheduling for VOQ Packet Switch Architecture[C]//Proceedings of IEEE International Conference on Communications （ICC），2011:1-5.

[12]任濤，蘭巨龍，扈紅超.并行分組交換研究綜述[J].計算機(jī)工程與設(shè)，2012（1）：47-50.

[13]LaMaire R O，Serpanos D N.Two dimensional round-robin schedulers for packet switches with multipleinputqueues[J].IEEE/ACMTrans.Networking，Oct.2010，2（5）:471-482.

[14]Jeroen Famaey，F(xiàn)rederic Iterbeke，Tim Wauters，et al.Towards a predictive cache replacement strategy formultimedia content [J].Journalof Network and Computer Applications 2013，1（1）.

[15]張亞夫，宣二勇.高速交換矩陣調(diào)度器的FPGA設(shè)計[J].無線電工程， 2013（6）：4-5.

[16]朱謙，蔣林，蔡龍.分組交換技術(shù)在光傳輸網(wǎng)中的研究與設(shè)計[J].電子科技，2013（6）:1-3.

[17]邱春婷，劉紅彥，齊靜.一種改進(jìn)的Canny邊緣檢測方法[J].紡織高?；A(chǔ)科學(xué)學(xué)報，2014，27（3）：380-384.

The design of buffered crossbar switches

ZHOU Yan-peng，ZHANG Xing-ming
（National Digital Switching System Engineering and Technological R&D Center， Zhengzhou450002，China）

TN4

A

1674－6236（2017）19-0141-04

2016-08-02稿件編號201608010

周延鵬（1990—），男，河南洛陽人，碩士研究生，講師。研究方向：芯片設(shè)計。