前情提要：本文主要闡述以下內容

Q1: Banyan網絡是什麼，有哪些特點？

是一種蝶形的互聯（交換）網絡，在特定的條件下可以實現無阻塞路由

Q2: Banyan網絡可以用在哪些地方？

以數字芯片設計為例，BANYAN網絡可以用於：

1、LDPC碼編譯碼算法的ASIC實現

2、數字芯片設計中的數據分離、匯聚操作

一、交換網絡

寬泛的說，所有存在多個源數據和多個目的數據交換的地方，都存在交換網絡。例如通信網絡中的ATM交換網絡，以太交換網絡。電子電路中的FPGA芯片互連網絡等都屬於各自領域中的交換網絡。

本文將要介紹的是一種結構簡單高效、廣泛應用的交換網絡--BANYAN NETWORK。它是一種樹型的網絡結構，具有靈活，自選路由，唯一路徑等特點。基於BANYAN網絡的這些特點，以LDPC編譯碼領域及交換領域的兩個應用實例來詳細展開，介紹如何在數字芯片設計中如何使用BANYAN 網絡，完成所需要的功能，以及節省芯片邏輯資源，優化芯片PPA（power-perform-area）的目的。

在此之前首先介紹一下常用的交換網絡結構：A、Crossbar；B、Banyan network、C、Benes network

A. CROSSBAR網絡

crossbar網絡拓撲結構

Crossbar 網絡是互連網絡中最一般的形式，是最嚴格意義下的無阻塞開關網絡。Crossbar 網絡由 N 個輸入和 N 個輸出構成，有 N²個交叉點，通過控制每個節點開關的狀態，可以實現任意輸入與輸出之間的無阻塞連接，且每個輸出通道都可以獨立輸出任意一個輸入通道的數據。缺點是當通道數N增加，Crossbar 網絡節點開關數迅速增加，網絡復雜度迅速增大。

switch狀態：cross + bar

Crossbar 網絡中每個節點稱為一個switch，每個switch有兩種狀態,“BAR”代表直通狀態，“CROSS”表示交換狀態。後續介紹的網絡節點也都采用switch構成。

B. BANYAN網絡

Banyan網絡拓撲結構

Banyan 網絡是一種內部阻塞結構型的互聯網絡。采用瞭一種蝶形的互聯結構，節點開關數目遠小於Crossbar網絡。以16×16 的 Banyan 網絡為例，每一級有 N∕2 個開關，共有 log2N 級，開關總數為8*4=32。而N=16的Crossbar網絡需要16²=256個開關。 但是Banyan網絡中會存在路徑沖突,使得有些輸出排序得不到實現。目前有許多方式可以消除Banyan 網絡的路徑沖突與阻塞，例如通過banyan網絡與逆banyan網絡的串聯構成的雙banyan互連網絡能有效地解決路徑的沖突與阻塞，這種串聯的雙banyan互連網絡就是benes網絡。

C. BENES網絡

15ef5d30552f0de438702f2fd3d54232benes網絡的拓撲結構

Benes網絡是電路交換中著名的可重排無阻塞網絡，Benes網絡實際上相當於兩個banyan類網絡背對背連接，然後中間兩級合並為一級。假設總入線/總出線數為N，banyan網絡級數為log2N那麼Benes網絡級數為2log2N - 1

二、BANYAN網絡的特點

單平面非擴展型的簡單BANYAN網絡的開關隻有兩種狀態，

1、banyan基於樹型結構：輸入端為根節點，輸出端為葉子節點；

2、banyan網絡的級數：設級數為k級，k=log2N，N=總入線數/出線數，2k=N，每級有N/2個交換單元；（以2為底是因為每個交換單元都是2 x 2的）

3、自選路由：在入端給定出端地址（二進制），不需要外加控制命令，信息可根據出端地址來自動選路；

4、構造遞歸性：構造一個2N x 2N的banyan網絡，需要2組N x N的banyan網絡（ 以及 N個 2 x 2的交換單元，並使第1組的 N x N的 N條出線分別與N個 2 x 2交換單元的某一條入線相連，使第2組的 N x N的 N條出線分別與N個 2 x 2交換單元的另一條入線相連。(QC-LDPC碼使用)

5、惟一路徑特性：每一個入口都可以路由到任意出口，且網絡的任何一條出線與任何一條出線之間有且隻有一條路徑；(數據分離使用)

6、內部競爭性：banyan網絡的任意一條入線與出線之間都具有惟一的一條通路，但各入線與出線之間的存在公共的通路，當某個2X2的開關出現上播/下播時，會產生內部競爭。

三、BANYAN網絡的應用

A. LDPC碼中的BANYAN移位器

LDPC編譯碼器中常用的移位網絡有三種：

1) Barrel-shifter（對數桶型移位器）

2) QSN-network

3) Banyan-network

不同的移位器網絡在控制復雜度，靈活性，資源代價中的某個、或多個維度有優勢。不存在一個既擁有低復雜度和高靈活性，同時資源小的移位網網絡。 實際電路設計時，通常都是綜合考慮PPA（power-perform-area）的trade-off後，選用最合適的方案。

1) Barrel-shifter

對數桶形移位器結構簡單，由多級mux搭建，支持固定位寬的循環移位操作。每級的mux共享同一個單bit的控制信號。以位寬 Zmax 為8的桶形移位器為例，共需要 3 級移位，每級則需要8個mux。設每級mux的控制信號分別為{p3,p2,p1,p0}，當shift=13時

13 = {color{salmon}{1}}*2^{3}+{color{salmon}{1}}*2^{2}+{color{salmon}{0}}*2^{1}+{color{salmon}{1}}*2^{0}

所以shift=13時，{p3,p2,p1,p0}={1, 1, 0, 1}。

總結：對於Barrel-shifter

->優點： 控制邏輯簡單，二進制的移位值直接作為每層的控制信號。

->缺點： 隻支持固定位寬的循環移位操作。

2) QSN-network

9eb372a03781f58f9e36579f508b0af5

QSN 網絡通過左、右移位網絡同時對同一組數據分別進行左/右循環移位，再將兩者移位後的結果mux後輸出，從而得到一個移位值k≤數據位寬N的任意循環移位網絡。使用方式如下:

總結：對於QSN-network

->優點： 可以支持≤N的位寬的循環移位操作。

->缺點： 相當於使用瞭2.x倍Barrel-shifter的資源。

3) Banyan-network

Banyan 網絡可以采用遞歸的方法逐級進行構造。根據蝶形網絡的特點，任意一個 N*N 的 Banyan 網絡可以由兩個 N/2*N/2 的 Banyan 網絡和 N/2 個 2×2 的 switch 構成。且新構造的 Banyan 網絡可以設置為一個N維的置換網絡{color{navy}{}}或者拆分為兩個N/2 維的置換網絡單獨使用。

這種拆分的靈活性十分適合LDPC編譯碼器的硬件實現，以CCSDS衛星深空通信標準的QC-LDPC碼為例，協議規定的的碼長范圍從128、256......~8192。均為2的冪次方。采用Banyan 網絡作為移位器的話，可以輕松地實現小碼長的並行處理，進而利用多包並行提升編譯碼器的吞吐率。

總結：對於Banyan network

->優點： 天然支持多路並行處理，靈活度很高，能以2的冪次方拆分單獨使用。

e.g，N16的Banyan = 2個N8的移位器 ··· = 8個N2的移位器。

->缺點： Banyan網絡中的每一個switch都需要單獨控制，控制邏輯相對復雜。

B. 利用Banyan網絡實現數據的匯聚與散射

在數字芯片的設計中，通常，我們希望使用通用的方法解決同一類型的問題，而不僅僅是采用if...elseif...遍歷所有的情況。粗暴遍歷的方式對於軟件代碼而言會增加CPU處理時間的消耗，對於硬件電路而言則會增加芯片面積復雜度、時序風險等。

現在我們考慮以下場景：數據分離（去無效數據），且匯聚有效數據（按照原始的相對順序排列）

假設數據分離場景有如下約束與需求：

1、 輸入數據總位寬一定（固定256bit）

2、 輸入數據可以被均分為一系列數據量相同的最小單元（下圖列舉瞭unit=8、16、32、64bit，4種場景）

3、 無效數據可以在輸入數據的任意位置

4、 數據輸出時，輸入有效數據在低位密排，且輸入有效數據的相對位置保持不變

解分離實現方式1：超大mux暴力實現

unit=32bit情形

1、每個輸出節點的unit都可能來自於任一輸入節點，mux可以實現此功能，對於每個輸出節點，需要使用1個位寬為32bit的mux8。

2、一共有8個輸出節點，共計需要8個位寬為32bit的mux8。

3、unit長度∈{2，4，8，16，32，64，128，256}，共有8種場景，假設每種場景的mux數量相等，則為瞭兼容每種unit的大小，需要使用8*8個32bit位寬的8選1mux。

4、資源統計：mux8=（4+2+1=7）個mux2，則總資源為8*8*7*32=14336mux2，將mux2折算為1.5門則資源≈ 2Wgate

僅僅是處理256bit的數據就要使用2Wgate，並且，這樣巨大的mux網絡對後端實現而言簡直是災難，會造成congestion過大，core利用率低等一系列問題；會進一步導致後端佈局佈線困難，導致芯片面積增加。

解分離實現方式2：Banyan移位網絡實現

下面嘗試利用Banyan網絡的重排無阻塞特性實現數據分離。原問題的本質是一個數據匯聚的問題，要求數據輸出時，輸入有效數據在低位密排，且輸入有效數據的相對位置保持不變；所以，任意有效數據的輸出節點序號<=其輸入節點序號。

1、在以上條件的約束下，正向Banyan網絡可以作為無阻塞網絡使用。以unit=32bit為例，banyan網絡狀態如下，其中有效輸入節點集合為{0,3,4,6,7}，路由到對應的輸出節點所經過的路徑如下圖所示：

2、註意此時的Banyan網絡是單向無阻塞的，如果采用逆Banyan移位網絡，則會出現路由沖突。如下圖所示，可以看到此時輸入節點4的路徑與節點0的路徑在①處發生瞭沖突，節點6的路徑②處發生瞭沖突，一個節點不能同時存在兩個數據。並且由於路徑的唯一性，此沖突無法避免。根本原因是輸入節點0和節點4在第一級共用同一個switch，出現瞭競爭。而每個switch的狀態隻能為cross或者bar。

072dbf6fdb43374df9d63bc42f88539a

3、每級開關Banyan網絡自選路由特性：

將輸入數據由節點3路由到輸出節點1，途中經過的每一級switch單元的開關狀態需要分別設置為{0, 1, 0}。這裡，我們可以利用banyan網絡自路由的特性來得到每級的switch單元的狀態：{s2，s1，s0} = in[2:0] ^ out[2:0]

每個有效的輸入到輸出節點路徑的switch狀態分別為：

以輸入節點3為例，將輸入節點3與輸出節點1分別寫成2進制形式011與001，則開關狀態{s0，s1，s2} = 011 ^ 001 = 010。

4、資源統計：位寬256bit的Banyan網絡，層數為8，每層需要256個mux2，則8*256=2048個mux2，考慮每個switch單獨控制≈ 0.5Wgate