編 者 按

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

報(bào)文的依賴性

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

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

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

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

常見的依賴解決方法&劣勢(shì)

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

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

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

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

正常情況下會(huì)進(jìn)入Flow StateC、在進(jìn)行合并后將無法進(jìn)入到StateC。

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

CFC

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

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

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

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

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

每個(gè)緩存的組織形式如下所示：

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

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