如何處理cache miss問題以提高加速器效率呢？

引言

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

01

Cache miss的問題

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

圖1.1 不規(guī)則數(shù)據(jù)需要造成頻繁訪問DDR

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

圖1.2 blocking cache的使用

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

圖1.3 non-blocking cache

02

傳統(tǒng)的Non-blocking cache結(jié)構(gòu)

圖2.1是一個基本的non-blocking cache結(jié)構(gòu)，它主要由cache array以及MSHR組成。Cache array中含有tag和數(shù)據(jù)，tag用來表示加速器請求的數(shù)據(jù)的在外存中的地址。通過tag可以判定請求的數(shù)據(jù)在cache中是否存在。MSHR首先被Kroft使用，它含有數(shù)據(jù)未被命中需要去外存獲取的具體信息：包括外存地址，用于判定加速器是否會再次命中相同的數(shù)據(jù)。還有cache的地址，用于決定從外存獲取的數(shù)據(jù)存儲到cache的位置，給哪個加速器使用。還有輸入請求確認標志，表示這個缺失的數(shù)據(jù)是否從外存讀取到。

基本操作是：當加速器第一次從cache中獲取數(shù)據(jù)沒有命中，那么就在MSHR中記錄下相應(yīng)的信息和狀態(tài)，當?shù)诙蜗嗤瑪?shù)據(jù)miss發(fā)生，除了在MSHR中記錄信息外，則啟動從外部存儲器獲取數(shù)據(jù)，并更新到cache中。取回來的數(shù)據(jù)會根據(jù)MSHR中的信息將需要的數(shù)據(jù)發(fā)送給加速器。所以一個包含n個表項的MSHR有n個比較器用于比較數(shù)據(jù)地址，是否屬于同一個miss的數(shù)據(jù)等。使用non-blocking cache能夠提高運算效率，減少等待時間，提高帶寬利用率。但是這種傳統(tǒng)的MSHR消耗很多邏輯資源，不利于規(guī)模擴展。

圖2.1 non-blocking cache的基本結(jié)構(gòu)和操作

圖2.2 更新cache

圖2.3 MSHR邏輯結(jié)構(gòu)

03

對non-blocking cache的改進

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

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

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

圖3.2 Cuckoo hashing

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

圖3.3 可擴展subentries

圖3.4 表項擴展

圖3.5 整體結(jié)構(gòu)

結(jié)論

本文主要總結(jié)了non-blocking cache的設(shè)計框架，以及在FPGA上如何使用。介紹比較簡略，更詳細的資料還需要了解CPU體系中non-blocking cache的具體結(jié)構(gòu)。

審核編輯：劉清