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

1 什么是鏈表

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

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

2 鏈表操作

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

2.1 查找entry

新請(qǐng)求輸入至隊(duì)列，可放置在table任意位置，需查找到一個(gè)空閑的entry添加該請(qǐng)求至相關(guān)隊(duì)列的尾部。一般來說，從table的index 0處開始查找，獲取第一個(gè)可用的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提供了一種簡(jiǎn)潔的方式，可以參考一下。

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)度邏輯，如定義一個(gè)計(jì)數(shù)器，需要查找時(shí)則計(jì)數(shù)，檢查對(duì)應(yīng)entry是否空閑，但速度較慢。

2.2 添加元素

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

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

更新上一元素的NEXT信號(hào)及其head/tail信號(hào)。若table內(nèi)采用了tail信號(hào)，相關(guān)處理代碼如下，其中table_next信號(hào)可使用不帶復(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的場(chǎng)景，tail添加，也在tail釋放。

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

在鏈表的tail釋放，是類似的，區(qū)別是需置位tail信號(hào)，基于釋放的Entry匹配獲取鏈表的上一元素，代碼如下。對(duì)于這一場(chǎng)景，也可以考慮使用逆向鏈表，釋放邏輯就跟上面的head釋放是類似的了，但添加元素會(huì)有所區(qū)別。插入一個(gè)問題，存在雙向鏈表的數(shù)據(jù)結(jié)構(gòu)，但從硬件來看，其實(shí)沒有必要，或者說硬件鏈表就是雙向鏈表，一側(cè)使用NEXT標(biāo)識(shí)，另一側(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)系。理論來說，所有隊(duì)列管理電路都可以使用鏈表實(shí)現(xiàn)，但其需要一些邏輯開銷，并不適用于所有場(chǎng)景。個(gè)人理解，存在多個(gè)隊(duì)列和亂序釋放的場(chǎng)景，可以考慮使用鏈表。

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

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

4 類FIFO的偽鏈表

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

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

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

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

5 小結(jié)

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