在FPGA上如何使用non-blocking cache設(shè)計(jì)框架

帶寬是影響FPGA加速器的重要因素，因?yàn)榇罅康牟⑿杏?jì)算對(duì)數(shù)據(jù)量要求很大。如果加速器對(duì)數(shù)據(jù)的訪問(wèn)是不規(guī)則的，那么cache miss就會(huì)大大影響加速器性能。這篇來(lái)自FPGA2019會(huì)議的報(bào)告，向我們展示了如何來(lái)更好的處理cache miss問(wèn)題，提高對(duì)緩存的利用率以及提高加速器效率。

1. Cache miss的問(wèn)題

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

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

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

圖1.2 blocking cache的使用

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

圖1.3 non-blocking cache

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

圖2.1是一個(gè)基本的non-blocking cache結(jié)構(gòu)，它主要由cache array以及MSHR組成。Cache array中含有tag和數(shù)據(jù)，tag用來(lái)表示加速器請(qǐng)求的數(shù)據(jù)的在外存中的地址。通過(guò)tag可以判定請(qǐng)求的數(shù)據(jù)在cache中是否存在。MSHR首先被Kroft使用，它含有數(shù)據(jù)未被命中需要去外存獲取的具體信息：包括外存地址，用于判定加速器是否會(huì)再次命中相同的數(shù)據(jù)。還有cache的地址，用于決定從外存獲取的數(shù)據(jù)存儲(chǔ)到cache的位置，給哪個(gè)加速器使用。還有輸入請(qǐng)求確認(rèn)標(biāo)志，表示這個(gè)缺失的數(shù)據(jù)是否從外存讀取到?；静僮魇牵寒?dāng)加速器第一次從cache中獲取數(shù)據(jù)沒(méi)有命中，那么就在MSHR中記錄下相應(yīng)的信息和狀態(tài)，當(dāng)?shù)诙蜗嗤瑪?shù)據(jù)miss發(fā)生，除了在MSHR中記錄信息外，則啟動(dòng)從外部存儲(chǔ)器獲取數(shù)據(jù)，并更新到cache中。取回來(lái)的數(shù)據(jù)會(huì)根據(jù)MSHR中的信息將需要的數(shù)據(jù)發(fā)送給加速器。所以一個(gè)包含n個(gè)表項(xiàng)的MSHR有n個(gè)比較器用于比較數(shù)據(jù)地址，是否屬于同一個(gè)miss的數(shù)據(jù)等。使用non-blocking cache能夠提高運(yùn)算效率，減少等待時(shí)間，提高帶寬利用率。但是這種傳統(tǒng)的MSHR消耗很多邏輯資源，不利于規(guī)模擴(kuò)展。

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

圖2.2 更新cache

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

3. 對(duì)non-blocking cache的改進(jìn)

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

圖3.1 兩個(gè)MSHR被請(qǐng)求表項(xiàng)都被占用

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

圖3.2 Cuckoo hashing

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

圖3.3 可擴(kuò)展subentries

圖3.4 表項(xiàng)擴(kuò)展

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

4. 結(jié)論

本文主要總結(jié)了non-blocking cache的設(shè)計(jì)框架，以及在FPGA上如何使用。介紹比較簡(jiǎn)略，更詳細(xì)的資料還需要了解CPU體系中non-blocking cache的具體結(jié)構(gòu)。作者也處于學(xué)習(xí)之中，歡迎討論。

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