帶寬是影響FPGA加速器的重要因素，因為大量的并行計算對數據量要求很大。如果加速器對數據的訪問是不規則的，那么cache miss就會大大影響加速器性能。這篇來自FPGA2019會議的報告，向我們展示了如何來更好的處理cache miss問題，提高對緩存的利用率以及提高加速器效率。

1. Cache miss的問題

假設DDR可以提供12.8GB/s的帶寬，FPGA上的并行加速器的數據輸入帶寬為0.8GB/s，可以并列16個這種加速器。這些加速器通過arbiter來直接訪問DDR。如果它們訪問的數據是連續規則的，那么DDR的帶寬可以被充分利用。但是這些加速器需要的數據在DDR中并不是規則排列的，如圖1.1。這樣就會造成頻繁的訪問DDR，這樣DDR的帶寬就不夠用，造成的結果就是加速器會受到延遲，效率無法得到提升。就如同圖1.1所示，實際上有效利用的DDR帶寬只有0.8GB/s。

圖1.1 不規則數據需要造成頻繁訪問DDR

一種解決問題的方法是使用blocking cache，將還沒有用到的數據緩存起來以便之后使用。然而這樣存在兩個問題：一個是如果緩存中沒有需要的數據，那么就需要從DDR中獲取數據，這就會有很大延遲，因為對DDR的數據進行隨機訪問是非常耗時的；另一個是緩存的使用效率很低，內部大部分數據都不能被及時消耗，以便等待被利用到。

圖1.2 blocking cache的使用

另外一種解決的辦法是non-blocking cache，這正是本文提出的方法。這種方法的關鍵是加速器可以允許一定數量的cache miss。Cache miss不會阻塞對后面數據的獲取。這就要求前后的數據沒有依賴關系，而且允許的cache miss數量足夠多，能夠允許在這些時間可以從DDR中獲取miss的數據，否則一樣會造成加速器等待喂數。

圖1.3 non-blocking cache

2. 傳統的Non-blocking cache結構

圖2.1是一個基本的non-blocking cache結構，它主要由cache array以及MSHR組成。Cache array中含有tag和數據，tag用來表示加速器請求的數據的在外存中的地址。通過tag可以判定請求的數據在cache中是否存在。MSHR首先被Kroft使用，它含有數據未被命中需要去外存獲取的具體信息：包括外存地址，用于判定加速器是否會再次命中相同的數據。還有cache的地址，用于決定從外存獲取的數據存儲到cache的位置，給哪個加速器使用。還有輸入請求確認標志，表示這個缺失的數據是否從外存讀取到。基本操作是：當加速器第一次從cache中獲取數據沒有命中，那么就在MSHR中記錄下相應的信息和狀態，當第二次相同數據miss發生，除了在MSHR中記錄信息外，則啟動從外部存儲器獲取數據，并更新到cache中。取回來的數據會根據MSHR中的信息將需要的數據發送給加速器。所以一個包含n個表項的MSHR有n個比較器用于比較數據地址，是否屬于同一個miss的數據等。使用non-blocking cache能夠提高運算效率，減少等待時間，提高帶寬利用率。但是這種傳統的MSHR消耗很多邏輯資源，不利于規模擴展。

圖2.1 non-blocking cache的基本結構和操作

圖2.2 更新cache

圖2.3 MSHR邏輯結構

3. 對non-blocking cache的改進

為了能夠有效擴展MSHR，可以使用多個MSHR，每個MSHR有n個表項，這樣相比于使用一個MSHR能節省邏輯資源。但是這涉及到一個問題，如果一個配置MSHR的請求在多個MSHR表都有沖突，那么就造成配置MSHR表的等待。這樣就導致了加速器運算的等待，不能夠執行下一條指令。

圖3.1 兩個MSHR被請求表項都被占用

解決辦法就是Cuckoo hashing算法。假設有兩個MSHR表，T1和T2。每個r個表項。每個元素通過函數h1和h2來確定表項位置，即：T1[h1(x)]，T2[h2(x)]。為了插入表項內容x，檢查T1對應位置是否空，如果空，就插入。如果非空就檢查T2，如果T2也非空，這就是沖突的情況，那么就插入到T2中，將原來的內容z替換。然后z再去查詢T1表，如此循環進行。這樣就不會造成阻塞。

圖3.2 Cuckoo hashing

還有一個問題是，MSHR中的表項subentries大小是固定的，如果要擴展表項的subentries，那么所有的內容都是同等擴展，這樣可能有一些內容并不需要那么大。所以為了能夠有效利用存儲資源，論文作者提出了動態可擴展subentries內容的方法。將tag和subentries分隔開分別存儲，這樣如果有更多加速器miss相同的數據，那么就可以在一個subentries表后再擴展需要的subentries。這樣就是在需要級聯的subentries中增加指針來級聯到下一個subentries表。

圖3.3 可擴展subentries

圖3.4 表項擴展

圖3.5 整體結構

4. 結論

本文主要總結了non-blocking cache的設計框架，以及在FPGA上如何使用。介紹比較簡略，更詳細的資料還需要了解CPU體系中non-blocking cache的具體結構。作者也處于學習之中，歡迎討論。

文獻
1 Stop Crying Over Your Cache Miss Rate:
Handling Efficiently Thousands of Outstanding Misses in FPGAs, Mikhail Asiatici and Paolo Ienne, February 26, 2019