交叉節(jié)點緩存crossbar交換結構設計

周延鵬，張興明

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

交叉節(jié)點緩存crossbar交換結構設計

周延鵬，張興明

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

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

crossbar；交換結構；調(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

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

1 CICQ交換結構設計

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

CICQ交換結構工作流程可分為4步，

第一步：包到達過程，即包進入輸入端口后按照包信息緩存到對應端口的對應VOQ[1-9][11-12]緩存隊列；

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

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

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

圖1 CICQ結構框圖

1.1 輸入端口

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

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

圖2 輸入端VOQ

1.2 交叉端

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

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

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

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

1.3 輸出端

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

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

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

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

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

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

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

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依次降低的順序，假設第一次0端口有請求，就從0端口開始，仲裁結果就是0，并將請求緩存至“上一次請求寄存器”跳至步驟6）；

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

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

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

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

8）結束。

2.2 輸出調(diào)度

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

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

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

3 仿真驗證

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

測試激勵說明：

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

3.1 調(diào)度仿真

輸入調(diào)度：

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

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

輸出調(diào)度：

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

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

3.2 系統(tǒng)仿真

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

圖6 系統(tǒng)仿真

3.3 硬件開銷

硬件開銷如圖7所示。

圖7 硬件開銷

4 結 論

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

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

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

[3]蔣泳波，高速交換結構多播技術研究[D].西安：西安電子科技大學，2013.

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

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

[6]戴藝，蘇金樹，孫志剛.高性能新型交換結構綜述[J].電子學報，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)絡的一種高效自尋路交換機制研究[D].成都：電子科技大學，2013.

[10]鄭若鹢.CICQ交換結構的調(diào)度算法分析[J].電腦與信息技術，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].計算機工程與設，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設計[J].無線電工程， 2013（6）：4-5.

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

[17]邱春婷，劉紅彥，齊靜.一種改進的Canny邊緣檢測方法[J].紡織高?；A科學學報，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—），男，河南洛陽人，碩士研究生，講師。研究方向：芯片設計。