前文聊了隊列管理的幾種典型電路，硬件邏輯簡單，代碼實現時容易操作。鏈表也是隊列管理的常用電路，相比前文的幾種結構，會稍微復雜一些。

1 什么是鏈表

在非連續、非順序的物理存儲結構上，通過指針的方式記錄元素的順序關系。在硬件電路中，通常使用generate組建table，記錄每個entry的內容，除了有效位和Payload之外，還有link_next，可能有head/tail信息。head/tail信息也可以基于隊列進行單獨記錄，而不在table體現。

使用NEXT標注鏈表下一個元素的位置，也即table對應的標號。

2 鏈表操作

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

2.1 查找entry

新請求輸入至隊列，可放置在table任意位置，需查找到一個空閑的entry添加該請求至相關隊列的尾部。一般來說，從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

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

2.2 添加元素

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

將請求保存至entry，較為簡單，根據查找邏輯得到的sel信號選擇對應entry，更新其內容及其head/tail信號。

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

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進行清零，二是head信號傳遞。首先，通過調度邏輯選取需釋放的鏈表Entry，獲取其NEXT信號，并將其valid信號進行清零；然后，將NEXT所指向Entry的head信號進行置位。若存在時序緊張，可將NEXT信號進行打拍，但要注意valid清零與head置位是否存在功能時序要求。

在鏈表的tail釋放，是類似的，區別是需置位tail信號，基于釋放的Entry匹配獲取鏈表的上一元素，代碼如下。對于這一場景，也可以考慮使用逆向鏈表，釋放邏輯就跟上面的head釋放是類似的了，但添加元素會有所區別。插入一個問題，存在雙向鏈表的數據結構，但從硬件來看，其實沒有必要，或者說硬件鏈表就是雙向鏈表，一側使用NEXT標識，另一側使用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 鏈表應用

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

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

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

4 類FIFO的偽鏈表

考慮一個場景，需要較大數量的Entry，如256，實現鏈表結構，可想而知，維護該鏈表所需的資源。另外，鏈表管理邏輯、Entry Payload 選取需要的MUX邏輯等等，在后端實現時，還可能出現Congestion風險。

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

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

這一結構相對簡單，存在的問題是會降低利用率。但是，從另一方面來看，在系統中，亂序是小概率的，順序是常見的，使用這一結構可以達到期望的功能，在PPA方面也是較優解。

5 小結

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