在數(shù)字芯片設計中，幾乎所有模塊都會涉及到隊列管理。輸入輸出的管理、不同數(shù)據(jù)流的調(diào)度、亂序數(shù)據(jù)的重排序、不同模塊的同步處理、資源管理，等等，均會涉及到隊列管理邏輯。如何選擇合適的硬件邏輯，對模塊的微架構有較大的影響，需要基于具體需求做綜合權衡后再做選擇。本文簡單羅列幾種隊列管理邏輯，均是個人曾經(jīng)實現(xiàn)過的。

1 最簡單的隊列-FIFO

First In First Out，用于輸入輸出之間的緩沖，吸收輸入側的突發(fā)流量。實現(xiàn)也比較簡單，深度固定的環(huán)形buffer，使用讀寫指針進行管理。需要注意的是，讀寫指針的管理，F(xiàn)IFO為空和FIFO為滿，讀寫指針均是相等的，需使用另外的標號進行處理。也有其余的實現(xiàn)方式，比如移位寄存器。

使用SpinalHDL實現(xiàn)FIFO的代碼如下。輸入輸出的push/pop，使用了valid/ready握手的Stream接口；使用Mem定義環(huán)形buffer，pushPtr/popPtr分別對應讀寫指針；特別關注risingOccupancy信號，push和pop沒有同時發(fā)生時，更新為push，該信號可用于標記FIFO的空滿狀態(tài)。讀寫指針相等且該信號為低，表示FIFO為空；讀寫指針相等且該信號為高，表示FIFO為滿。

// spinal/lib/Stream.scala
val io = new Bundle {
val push = slave Stream (dataType)
val pop = master Stream (dataType)
val flush= in Bool() default(False)
val occupancy = out UInt (log2Up(depth + 1) bits)
val availability = out UInt (log2Up(depth + 1) bits)
}
val ram = Mem(dataType, depth)
val pushPtr = Counter(depth)
val popPtr = Counter(depth)
val ptrMatch = pushPtr === popPtr
val risingOccupancy = RegInit(False)
val pushing = io.push.fire
val popping = io.pop.fire
val empty = ptrMatch & !risingOccupancy
val full = ptrMatch & risingOccupancy

io.push.ready := !full
io.pop.valid := !empty & !(RegNext(popPtr.valueNext === pushPtr, False) & !full) //mem write to read propagation
io.pop.payload := ram.readSync(popPtr.valueNext)

when(pushing =/= popping) {
risingOccupancy := pushing
}
when(pushing) {
ram(pushPtr.value) := io.push.payload
pushPtr.increment()
}
when(popping) {
popPtr.increment()
}

2 共享Buffer的多隊列FIFO

考慮一個場景，輸入的請求需要分發(fā)至不同的輸出側，下游存在反壓。簡單實現(xiàn)，基于不同的輸出分別設置FIFO，但可能存在資源浪費，某些數(shù)據(jù)流場景FIFO的利用率不高，尤其是在數(shù)據(jù)位寬較大的場景。

共享Buffer的多隊列FIFO，每個隊列的FIFO還是按照簡單隊列進行管理，基于每個隊列管理讀寫指針。但是，不再使用環(huán)形Buffer，每個buffer entry記錄其隊列號、隊列指針和Payload，如下圖所示。對于Payload位寬較小的場景，收益不大，若存在大位寬時，可有效提升Buffer的利用率。

將數(shù)據(jù)寫入Buffer時，先找一個Free Entry(Vliad為低)，將該數(shù)據(jù)所屬的隊列號及其對應的寫指針、Payload寫入到對應的Entry內(nèi)。讀取Buffer時，則使用隊列號和讀指針進行匹配，將命中的Entry內(nèi)容讀取出來。若讀寫指針所能描述的范圍比buffer深度大，則不需要額外的標號記錄空滿狀態(tài)。存在的問題，若buffer深度較大或隊列數(shù)量較多，隊列號和指針匹配邏輯會占用較多的資源。

3 重力FIFO

類似于排隊，從隊頭開始尋找可輸出的Entry，調(diào)度輸出并留下空位，后面的Entry再往前排，新輸入的請求則放置在隊列尾。如圖所示，存在有效數(shù)據(jù)的Entry，其前面的Entry被調(diào)度后留下空位，該Entry就像受到重力作用往下掉，因此我也稱之為重力FIFO。

該結構的問題，存在大量的移位，設想Payload位寬為32bit，深度為32，將近1kbit的寄存器在做移位處理，其功耗可想而知。但是對于一些具體場景，還是能夠帶來一些收益的，如隊列數(shù)量較大，甚至大于buffer深度；至于Payload位寬較大的場景，可考慮二次索引處理，Payload保存至另外的buffer，該結構內(nèi)的Payload Entry則緩存其索引信息。

4 Bitmap排序

先來看一個結構，深度為8的隊列，每個Entry使用8bit緩存8個Entry的狀態(tài)，若該狀態(tài)信號滿足觸發(fā)條件，如全為0，則調(diào)度該Entry內(nèi)容。

Bitmap排序就是使用了這一結構，在輸入請求進入隊列后，檢查當前隊列狀態(tài)，存在關聯(lián)請求的Entry位置置位為1，否則為0。若存在請求輸出之后，所有Entry狀態(tài)的對應位置均設為0。若某個Entry的狀態(tài)信號全為0，則請求調(diào)度輸出。其數(shù)據(jù)結構如下圖所示，其中0/1僅作為狀態(tài)信號的示例，并非實際場景。

該結構可以實現(xiàn)較為靈活的排序，隊列的數(shù)量幾乎不會受到限制，進入隊列的請求，也可修改其Mask Bitmap，動態(tài)刷新其先后關系。與重力FIFO類似，無需額外的數(shù)據(jù)結構保存其隊列關系，而是直接體現(xiàn)在原有結構內(nèi)。存在的問題，隊列深度會受到面積限制，面積與深度的平方成正比；另外，在動態(tài)更新Mask Bitmap之后，某些實現(xiàn)可能無法保證先后關系。

面積問題可以考慮用分級處理。如需實現(xiàn)256深度的隊列，其Mask Bitmap需要65536個寄存器實現(xiàn)Mask Bitmap。分解為8個32深度的隊列，需要的寄存器數(shù)量為8192；分解為16個16深度的隊列，寄存器數(shù)量為4096。

5 小結

隊列管理電路還有一個比較常見的實現(xiàn)，鏈表。在亂序數(shù)據(jù)的重排序、資源管理等等方面，通常會用鏈表實現(xiàn)，與上幾個結構相比，鏈表會復雜一些。該部分將在下篇描述。

除最簡單的FIFO之外，其余幾個都沒有代碼，如各位要有興趣，請留言，我可以再嘗試寫一些Spinal代碼實現(xiàn)。