編 者 按

一篇2014年的論文:《CACHE FOR FLOW CONTENT: SOLUTION TODEPENDENT PACKET PROCESSING IN FPGA》,主要講述在FPGA中有狀態表項的存儲與管理。感興趣的可以閱讀原文。

報文的依賴性

在CPU中，存在一種“write-read miss”的場景，即新的數據還未寫回就要去讀存儲器，導致數據依賴。

在FPGA與ASIC中報文的流水線處理中，也存在報文的依賴性問題。在流水線結構中，每個報文占據固定的時間周期數，處理時牽涉到對表項的讀和寫。下圖為例:

理想情況下應為左圖,packet1的寫操作從時鐘周期的角度來講發生在packet2的讀操作之前，如此兩個報文之間即使存在相互依賴性也沒有任何影響。

然而隨著操作變得復雜，可能導致到圖右的狀態，即Packet2的讀請求發生在Packet1的寫請求之前，如果packet2和packet1之間存在依賴性，則此時將會發生功能型的錯誤：

常見的依賴解決方法&劣勢

第一種最簡單的方法就是碰撞預防：

通過插入空拍來避免數據挨的太近，當然壞處就是帶寬的浪費，自然下下之策。

第二種方法即碰撞補償。碰撞補償允許數據以背靠背的形式呈現，當數據沖突將要發生時，相同數據流的信息將會被合并處理：

如上圖所示，假定包處理的跨度為三個報文，當一個數據包n到達時，其會與n+1、n+2進行比較，如果n依賴于n+1或者n+2，則其信息將會合并到n+1或者n+2中進行處理，n將會被禁用。這種方式對于所有的信息都由數據包本身攜帶是沒有問題的，但如果有些信息是由流當前狀態、數據包信息、中間結果一些列所決定的那么久不太適用。考慮下面的例子：

正常情況下會進入Flow StateC、在進行合并后將無法進入到StateC。

第三種方法就是CPU Cache的概念。

CFC

在CFC中，Cache基于流的關鍵信息作索引(如五元祖哈希)

上圖中n、n+1、n+2存在依賴關系，n、n+1的寫操作將會被寫入到Cache中。

這里有一點需要注意的是對于任何一個報文而言，其從數據Cache讀出到數據寫回的時鐘數不應超過報文在流水線中占據的時鐘周期數T(如果超過了則意味著一個報文無法在時鐘周期T內完成數據的處理)。

這里的Cache可以認為是一個深度為1的全關聯Cache。對于Cache的容量的考慮可以參考下圖：

指定一個窗口，其跨度為一個數據包從進入處理到寫回的周期，窗口隨著數據包滑動。上圖中窗口的寬度為N+1個數據包(數據包1的狀態寫回發生在數據包N+1處)，則上圖中需要的緩存數即為N。

每個緩存的組織形式如下所示：

Content為Cache的主要內容，用于存儲流的相關信息。Tag和Validity為輔助信息。Tag可以為流的hash值。通過hash比較判斷是否存在匹配。Validity則用于標識該條流是否有效。

對于Cache中每個cache entry的維護，可以采用如下策略。為每個entry維護一個計數器。計數器的初始值為0，標識無效，其他值則有效。當一個entry被建立使用時，其計數器值設置為N，此后每進入一個數據包值就減1，直到為0，標志其無效，將其數據寫回SDRAM。但如果來了一個命中該entry的數據，那么其計數器值將直接恢復為N。如此，對于任何一個到來的數據報文，其都可以找到一個匹配的entry或者一個空的entry來進行緩存(其實這里的替換策略就是LRU)。