前情提要:本文主要闡述以下內容
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