前文聊了隊列管理的幾種典型電路，硬件邏輯簡單，代碼實(shí)現(xiàn)時容易操作。鏈表也是隊列管理的常用電路，相比前文的幾種結(jié)構(gòu)，會稍微復(fù)雜一些。

1 什么是鏈表

在非連續(xù)、非順序的物理存儲結(jié)構(gòu)上，通過指針的方式記錄元素的順序關(guān)系。在硬件電路中，通常使用generate組建table，記錄每個entry的內(nèi)容，除了有效位和Payload之外，還有l(wèi)ink_next，可能有head/tail信息。head/tail信息也可以基于隊列進(jìn)行單獨(dú)記錄，而不在table體現(xiàn)。

使用NEXT標(biāo)注鏈表下一個元素的位置，也即table對應(yīng)的標(biāo)號。

2 鏈表操作

使用鏈表作為隊列管理電路，涉及到的邏輯主要包括查找空閑entry、添加元素和釋放元素，其中添加和釋放需要先獲取tail或head位置。除此之外，如有其余需求，則做相應(yīng)處理。

2.1 查找entry

新請求輸入至隊列，可放置在table任意位置，需查找到一個空閑的entry添加該請求至相關(guān)隊列的尾部。一般來說，從table的index 0處開始查找，獲取第一個可用的entry，使用如下代碼。

always @* begin : gen_idle_entry
  integer i;
  reg flag;
  flag = 1'b0;
  for ( i = 0; i < TABLE_DEPTH; i = i + 1) begin
    if (~flag & table_entry_idle[i]) begin
      table_entry_sel[i] = 1'b1;
      flag = 1'b0;
    end else begin
      table_entry_sel[i] = 1'b0;
    end
  end
end

在Spinal Lib提供了一種簡潔的方式，可以參考一下。

def first[T <: Data](that : T) : T = new Composite(that, "ohFirst"){
  val input = that.asBits.asUInt
  val masked = input & ~(input - 1)
  val value = cloneOf(that)
  value.assignFromBits(masked.asBits)
}.value

除此之外，還可以用其余的查找方式，其實(shí)就是一種調(diào)度邏輯，如定義一個計數(shù)器，需要查找時則計數(shù)，檢查對應(yīng)entry是否空閑，但速度較慢。

2.2 添加元素

完成entry查找后，有兩方面內(nèi)容，一是將請求保存至entry內(nèi)，二是更新上一元素的NEXT信號。

將請求保存至entry，較為簡單，根據(jù)查找邏輯得到的sel信號選擇對應(yīng)entry，更新其內(nèi)容及其head/tail信號。

更新上一元素的NEXT信號及其head/tail信號。若table內(nèi)采用了tail信號，相關(guān)處理代碼如下，其中table_next信號可使用不帶復(fù)位的寄存器。

assign table_next_update[index] = table_valid[index] & table_tail[index] & (table_queue_id[index] == req_queue_id);
always @ (posedge clk) if (table_next_update[index]) begin
  table_next[index] <= req_table_entry;
end
always @ (posedge clk or negedge rst_n) begin
  if(~rst_n)
    table_tail[index] <= 1'b0;
  else if (table_next_update[index])
    table_tail[index] <= 1'b0;
  else if (req_table_sel[index])
    table_tail[index] <= 1'b1;
end

2.3 釋放元素

鏈表通常用于記錄操作的先后順序，tail添加，head釋放；但也有用于管理credit的場景，tail添加，也在tail釋放。

在鏈表的head釋放，主要需要完成兩個操作，一是釋放Entry，對valid進(jìn)行清零，二是head信號傳遞。首先，通過調(diào)度邏輯選取需釋放的鏈表Entry，獲取其NEXT信號，并將其valid信號進(jìn)行清零；然后，將NEXT所指向Entry的head信號進(jìn)行置位。若存在時序緊張，可將NEXT信號進(jìn)行打拍，但要注意valid清零與head置位是否存在功能時序要求。

在鏈表的tail釋放，是類似的，區(qū)別是需置位tail信號，基于釋放的Entry匹配獲取鏈表的上一元素，代碼如下。對于這一場景，也可以考慮使用逆向鏈表，釋放邏輯就跟上面的head釋放是類似的了，但添加元素會有所區(qū)別。插入一個問題，存在雙向鏈表的數(shù)據(jù)結(jié)構(gòu)，但從硬件來看，其實(shí)沒有必要，或者說硬件鏈表就是雙向鏈表，一側(cè)使用NEXT標(biāo)識，另一側(cè)使用NEXT匹配。

always @ (posedge clk or negedge rst_n) begin
  if (~rst_n)
    table_tail[index] <= 1'b0;
  else if (table_next_update[index])  // new entry added to tail
    table_tail[index] <= 1'b0;
  else if (req_table_sel[index])  // added as new entry
    table_tail[index] <= 1'b1;
  else if (release_grant & (table_next[index] == release_index))
    table_tail[index] <= 1'b1;
end

3 鏈表應(yīng)用

鏈表的特征是在無序的結(jié)構(gòu)內(nèi)記錄先后順序關(guān)系。理論來說，所有隊列管理電路都可以使用鏈表實(shí)現(xiàn)，但其需要一些邏輯開銷，并不適用于所有場景。個人理解，存在多個隊列和亂序釋放的場景，可以考慮使用鏈表。

只有單個隊列，直接使用FIFO就足夠了；順序釋放元素，其存儲結(jié)構(gòu)相當(dāng)于是順序釋放的，使用鏈表的必要性也不大。在亂序釋放的場景中，必定會存在離散的空閑Entry，若需要提高table的利用率，鏈表則是一個較優(yōu)解。

舉一個鏈表使用的典型例子。AXI接口的不同ID存在亂序返回的場景，發(fā)送至不同目的側(cè)的延時存在差別，上游存在多個源頭，且不同源頭又期望順序返回響應(yīng)。需要使用數(shù)據(jù)結(jié)構(gòu)記錄ID的狀態(tài)，可以使用鏈表維護(hù)ID的使用及其先后關(guān)系。新發(fā)出操作先從table獲取一個空閑的Entry，也即添加元素，使用該Entry的Index作為ID，基于源頭建立鏈表關(guān)系；操作返回后，則按順序釋放Entry，返回響應(yīng)。當(dāng)然，若僅存在一個源頭，或上游也無需順序返回響應(yīng)，使用鏈表的意義不大。

4 類FIFO的偽鏈表

考慮一個場景，需要較大數(shù)量的Entry，如256，實(shí)現(xiàn)鏈表結(jié)構(gòu)，可想而知，維護(hù)該鏈表所需的資源。另外，鏈表管理邏輯、Entry Payload 選取需要的MUX邏輯等等，在后端實(shí)現(xiàn)時，還可能出現(xiàn)Congestion風(fēng)險。

簡單的做法就是，將較大數(shù)量的Entry進(jìn)行分組，組內(nèi)按順序使用，不同組之間則使用鏈表NEXT指針。如將256分為16組，每組16個Entry，不同組之間基于鏈表維護(hù)，組內(nèi)Entry使用則按順序使用，同一組的16個Entry空閑或其空閑數(shù)量滿足要求后，可再分配使用。基于每組16個Entry進(jìn)行邏輯處理，不同組之間可添加寄存器打拍等等，降低Congestion風(fēng)險。

之前在做IP開發(fā)時，TLP轉(zhuǎn)AXI操作涉及到的ID分配和維護(hù)，就采用了這種偽鏈表的形式。每組32個Entry，例化了很多組，實(shí)現(xiàn)了AXI接口較大的Outstanding數(shù)量。將TLP轉(zhuǎn)化為AXI操作，需將較大的TLP報文切分為多個AXI操作，每個TLP報文作為一個隊列，由于TLP報文最大為4KByte，一個隊列最多只存在32個元素，多組之間就不再需要NEXT指針進(jìn)行維護(hù)了。每組內(nèi)進(jìn)行空閑Entry的搜索，找出連續(xù)且可用的最大數(shù)量的Entry，再供TLP轉(zhuǎn)換AXI時使用。

這一結(jié)構(gòu)相對簡單，存在的問題是會降低利用率。但是，從另一方面來看，在系統(tǒng)中，亂序是小概率的，順序是常見的，使用這一結(jié)構(gòu)可以達(dá)到期望的功能，在PPA方面也是較優(yōu)解。

5 小結(jié)

以上兩篇文章僅是簡單羅列了在過往工作中涉及到的隊列管理邏輯，未必全面，希望能對大家有一些啟發(fā)。