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

1 最簡單的隊(duì)列-FIFO

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

使用SpinalHDL實(shí)現(xiàn)FIFO的代碼如下。輸入輸出的push/pop，使用了valid/ready握手的Stream接口；使用Mem定義環(huán)形buffer，pushPtr/popPtr分別對(duì)應(yīng)讀寫指針；特別關(guān)注risingOccupancy信號(hào)，push和pop沒有同時(shí)發(fā)生時(shí)，更新為push，該信號(hào)可用于標(biāo)記FIFO的空滿狀態(tài)。讀寫指針相等且該信號(hào)為低，表示FIFO為空；讀寫指針相等且該信號(hào)為高，表示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的多隊(duì)列FIFO

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

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

將數(shù)據(jù)寫入Buffer時(shí)，先找一個(gè)Free Entry(Vliad為低)，將該數(shù)據(jù)所屬的隊(duì)列號(hào)及其對(duì)應(yīng)的寫指針、Payload寫入到對(duì)應(yīng)的Entry內(nèi)。讀取Buffer時(shí)，則使用隊(duì)列號(hào)和讀指針進(jìn)行匹配，將命中的Entry內(nèi)容讀取出來。若讀寫指針?biāo)苊枋龅姆秶萣uffer深度大，則不需要額外的標(biāo)號(hào)記錄空滿狀態(tài)。存在的問題，若buffer深度較大或隊(duì)列數(shù)量較多，隊(duì)列號(hào)和指針匹配邏輯會(huì)占用較多的資源。

3 重力FIFO

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

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

4 Bitmap排序

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

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

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

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

5 小結(jié)

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

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