FPGA中有狀態(tài)表項的存儲與管理

編 者 按

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

報文的依賴性

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

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

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

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

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

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

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

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

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

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

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

CFC

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

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

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

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

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

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

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

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