| 本主題的第一部分主要以TI C64x DSP為例介紹cache緩存的基本概念， 解釋了為什麼需要cache，cache如何和主記憶體進行通信以及如何優化cache的性能。第二部分主要介紹了怎麼配置cache以及怎樣正确的使用cache，即如何保證cache的一緻性。其中有關于DMA的傳輸怎麼影響cache以及怎麼管理DMA傳輸的雙緩存。關鍵字：C64x DSP Cache DMA L1P L1D 直接映射 set-associative; |
| 處理器的cache是一塊存儲靠近處理器資料的高速存儲區。這幫助常用的指令和資料的快速通路進而提高計算性能。Cache可以視為平坦式記憶體，即認為cache是CPU靠近的可以很快通路的存儲器，本篇主要是TI的C64x的處理器為例介紹cache的基本概念和cache的基本術語，接下來就是利用cache的特性來進行優化存儲提高程式性能和資料吞吐率。 存儲組織結構 圖1的左邊的模型是一個平坦式記憶體系統架構，假設CPU和片記憶體儲空間都運作在300 MHz,存儲通路的延時隻有在CPU通路外存的時候才存在，而memory stall不會在通路片記憶體儲區時發生。如果CPU的頻率是600 MHz，那麼在通路這部分片記憶體儲區的時候還是存在等待周期的。不幸的是，想在片内實作足夠大的存儲區能運作在600 MHz會非常昂貴的，如果仍然讓片内的存儲區運作在300 MHz,那麼通路這些存儲區的适合會有一個周期的延時。  圖 1. 平坦和分層的存儲架構 一個解決方法是使用分層的存儲架構，有一個快速的靠近CPU的存儲區，通路沒有stall但是size很小，往外的記憶體空間很大，但是離CPU較遠，通路需要比較大的stall，靠近CPU的存儲區可以視為cache。 通路定位的規律 當然，這種解決方案隻有在CPU在大部分的通路都是隻針對最靠近它的存儲區時才是有效的，幸運的是，根據通路定位的規律，這一條可以保證。通路的定位規律表明程式在一個相對小的時間視窗對僅需要一個相對較小size的資料和代碼。資料定位的兩條規律:
|
 圖 2. 存儲通路定位的規律 圖2是空間關聯性的說明，一個6-tap的FIR濾波器的資料通路模式。如計算輸出y[0],從輸入緩沖區x[]讀取6個采樣點，當第一個通路發生時，cache控制器讀取x[0]以及後續位址的若幹個資料（取決于cache line的長度），從速度慢的存儲器加載一個cache line的資料需要一定的時鐘周期的CPU stall。這種加載的一個動機是x[0]後續的資料後面就要被通路到。這個對于FIR濾波器是顯然的，因為後面的5個采樣點(x[1]-x[5])就要被用到。後面的這5次存儲通路就隻需要通路高速cache就可以了。 |
| 當計算下一個輸出y[1]時，5個采樣點(x[1]-x[5])就可以重用了，隻有一個采樣點(x[6])需要重新加載。所有的采樣點都在cache内了，通路時不會有CPU stall了，這也就是剛才提到的時間關聯性，即上一步利用的資料在下一次進行中還是可能會被用到的。 Cache就是利用資料通路的時間和空間關聯性建立的，它讓對速度較慢的外存的通路次數盡可能的降低，而讓大部分的資料通路都由更高層次的cache存儲區來完成。 存儲區的速度 Cache系統通常包含以下3級：
每一層次的cache有不同的資料通路性能，相對的性能比較可以參考下面的表格。 表1. Cache性能，不同級别的存儲通路時間比較(a 500 MHz處理器). 圖3. C64x的兩級cache的通路流程 當處理器從存儲區請求資料通路時，首先在最高層次的cache内查找，然後再從次進階别的存儲區查找。當請求在cache内時就是cache命中，否則是一次cache miss。因而Cache系統的性能将取決于cache命中的比率。對于任意級别的cache，命中率越高性能越好。比如一個記憶體通路的L1 cache命中率為70%，L2 20%， 其他來自L3，那麼以圖3所示的性能下，平均一次記憶體的通路時間為 (0.7 * 4) + (0.2 * 5) + (0.05 * 30) + (0.05 * 220) = 16.30 ns 考慮圖4所示的TI TMS320C64x DSP的存儲架構，兩級的片内cache加上片外外存。一級Cache分成程式(L1P)和資料(L1D) cache，每個容量為16 Kbytes。L1緩存資料通路不會有存儲stall。L2存儲區分成L2 SRAM和L2 cache，無論是哪種配置，L2存儲區都需要兩個CPU周期完成一次資料通路。不同的DSP，L2的容量不同，如TMS320C6454 DSP,L2的大小為1Mbytes。最後是C64x DSP最大高達2GBytes的外存，外存的通路速度取決于使用的存儲器類型，但一般外存的頻率在100 MHz左右。圖4中的所有的cache(紅色)和資料通路都由cache控制器自動維護。 圖 4 TMS320C64x Cache結構 Cache的更新 Cache一直是主存的一個拷貝，因而需要cache能随時反映主存的内容。如果資料在cache内被更新，而主存裡沒有更新，這個cache内的資料就被稱為污染(dirty)資料，而資料在主存被更新但是cache内沒有更新，這時cache内的資料被稱為過時的(stale)資料。 Cache控制器使用一系列的技術來維護cache的一緻性。偵聽"Snoop"和強制更新"snarf" 是兩種常用的技術。偵聽是讓cache決定主存内的資料的處理影響到被cache的位址的資料。強制更新是把資料從主存拷貝到cache存儲器。 Cache通常比主存容量小得多，因而cache最終總會被填滿，這時新進入的資料總要代替那些已經在cache内的資料了。有很多種政策決定那些已經在cache内的資料被代替更新如随機代替，先進先出(FIFO)以及最遲不用的政策(LRU)，大部分的處理器都采用LRU，即把least-recently-used資料替換為最新的資料。這種政策由于考慮到資料通路的是時間相關性而非常有效。 |
| 直接映射的cache Caches要麼是直接映射的"direct-mapped"，要不就是組相關的"set-associative"。圖5是C64x的L1P cache，包含了512個32位元組的cache lines。每個外存位址總是映射到同一個cache line，如:
圖 5. 直接映射Caches. 為了儲存從外存拷貝的資料資訊，每個L1P的cache行包含如下資訊：
當CPU開始通路位址0020h時，假設cache已經被完全被設定無效了（invalidated），即沒有cache line包含有效資料。此時cache控制器開始根據目前位址的組(即位址的第5到13比特)來看對應的哪個cache line。對于位址0020h來說是cache line 1.然後cache控制器檢查line 1的标簽位，确認其是否對應于位址0020h到0039h，最後檢查有效位，發現其值為0,即該位址的資料并不在cache内，此時cache控制器标記一次cache miss。這次的miss讓控制器從外存加載整個cache line(0020h-0039h)，同時更新标簽tag位，并把有效位設定為1，同時加載的資料傳遞給CPU，此次資料通路結束。 當還需要繼續通路位址0020h時，cache控制器會繼續檢查組号和标簽域，并和存在标簽RAM的值比較，同時有效位的值為1，意味着此次是一個cache hit。 組相關Set-associate caches 組級聯的cache是直接映射cache的擴充，在直接映射的cache内，每個組隻包含一個cache line，而組級聯的cache則包含若幹個行，被稱為"ways."。圖6是C64x DSP的L1D cache，一個2-way組級聯cache。每個line 64位元組，供16Kbytes容量。 圖 6. 組關聯(Set-associative Caches). 為了儲存從外存拷貝的資料資訊，每個L1D的cache行包含如下資訊：
命中和錯過與直接映射的cache的規則一樣，隻不過此時的标簽域比較變成比較兩路的标簽是否和位址的标簽一緻。如果way 0命中，則取way 0相應的cache line的資料，如果way 1命中，則取way 1相應的cache line的資料。如果兩路都miss，則資料需要從外存取，此時LRU比特來決定哪路的相對應的cache line資料被替換。如果LRU位為0則配置設定在way 0，否則配置設定在way 1.LRU比特的值随着資料的通路會有所改變，當way 0的cache line被更新，此時LRU比特會被切換成1。需要注意的是，LRU位隻有在cache miss的時候才會被查詢，但它的狀态會在每次cache line被通路時更新，不管這次通路時命中還是miss，是讀還是寫。 跟L1P一樣，L1D也是讀配置設定(read-allocated),即新資料隻有在一次讀miss時菜更新。當寫miss時，是通過write buffer來寫入外存，而把L1D旁路了。當寫命中時，寫入到cache而不是立即更新外存，這是一種回寫cache，即CPU改變的資料會在稍後時刻再寫回到外存。 污染比特(dirty bit)表明目前cache line的資料被CPU更新但是還沒有被寫回到外存。開始時污染bit為0，但随着CPU寫cache行，相應的dirty位就被置1了，當cache行被從cache清除時，寫回到外存後該位又被清零。Cache行被從cache清除，一個可能是因為一個讀miss需要更新該cache行，一個原因可能因為使用者自己向cache控制器發送了回寫指令。 |
| 優化Cache性能 有三種類型的miss:
如果一個cache行被清除然後又被通路，那麼該行又要被加載到cache line。因而應該盡可能的避免資料在短時間内被清除，應盡可能的讓資料複用。能确定造成miss的原因會有效的防止後續的miss。如前所述，容量的miss主要因為cache的容量較小，如果産生capacity miss，最簡單的解決方法是增加cache大小，如C64x DSP的L2 cache可以被配置成SRAM或者cache，可以增加更多的L2空間給cache。另外的一個減少capacity miss的方法是減少特定時間内的資料通路量，如果改變資料的循環結構，盡可能的重用後再加載新資料。 如果存在conflict miss，那麼重新組織資料以讓同時通路的資料映射到不同的set（對于直接映射的cache，組織資料讓同時通路資料對應不同的cache line）。改變存儲區的布局讓資料配置設定的記憶體在通路時不會發生沖突。即良好的資料組織會減少cache miss，提高系統性能。 |
| 優化系統軟體提高Cache性能 優化軟體以提高cache性能跟平常的針對平坦式記憶體的優化類似，即有效的資料和代碼組織。比如合理的組織那些經常執行的函數在一個存儲區内，這樣組織是為了讓DMA有效的把代碼從外存拷貝到片内空間。函數的合理組合有利于提高時間和空間關聯性。 下面是一些優化cache性能的基本準則，先看一些準則，然後是一些執行個體。
Data reuse資料重用 如前所述，塊濾波在一個cache的環境下工作的很好。圖1中的FIR濾波就是一個例子。表2是其不同長度的FIR濾波的性能評估benchmark。随着濾波器長度的增加，在一個采樣點上的工作量增加，cache的效率也提升了。輸入資料為1024點的16-bit資料，FIR長度分别為16到64 taps (T). 表2. 濾波器長度和cache效率 起始,算法的循環buffer為空，配置設定在L1D，用輸入資料從L2空間來填充，一個填充的方法是使用預加載(pre-fetch,pre-load)函數來加載需要用到的資料。表3是使用預加載函數來進行優化得到的cache性能和不預加載的性能比較。 表3. 資料預加載能有效提高cache的效率 資料代碼的組織 前面的FIR濾波器的例子裡，輸入資料是連續的，但是有些函數并不能原生的連續通路資料，連續通路的可能是間隔很遠的兩個資料，如矩陣乘法和用一個查找表進行資料調整的交織器。輸入資料的随機讀取，輸出資料則是順序存放。這些亂序的輸入資料的讀取會造成cache的颠簸，即反複的cache清除和重新通路。是以合理的組織該查找表讓讀連續而寫亂序，因為L1D是read-allocated的，因而不會頻繁的更新cache，而寫資料可以直接被灌入L2。這種組織方式把cache的效率從60%提高到85%。 避免L1P的沖突conflict misses 前面提到了怎麼重新組織資料來提高cache的效率，類似的還有合理的代碼放置會提高L1P的性能。改變函數在連結時的次序來調整函數在記憶體的位置。表4是一個把短時内需要連續調用的函數放置在連續記憶體的例子。 表4. 一個通路函數的例子 假設函數function_1和function_2在L2空間是交疊的，如圖7所示。當調用function_1時，它會被配置設定到L1P (1)。後續的調用function_2會導緻它的代碼配置設定到L1P (2).而這部分的代碼映射和function_1有沖突，那麼當下一次疊代需要繼續讀function_1時，就會發生重新把function_1的代碼加載到L1P的颠簸。這種形式的cache miss完全可以通過重新安排程式代碼在記憶體的配置設定排序來避免。 |
| 算法分割與函數組合 另外的優化技術是分割算法，一個算法可能會分割成小片讓程式代碼不能完全放到L1P内或者資料不能完全放到L1D内。一個視訊的縮放應用程式提供了代碼分割和資料分割的執行個體。為了提高性能，縮放的時候不是先把整個圖像進行水準方向的縮放，然後進行垂直方向的縮放，而是把圖像分塊，先進行這一塊的水準和垂直方向的縮放，再進行後一塊的縮放。 圖8. 視訊縮放函數的資料流程圖 每個色彩被分成2個資料緩沖區，以亮度Y分量為例，有BufY0a和BufY0b。buffer内的資料先進行邊界擴充， 結果儲存到BufY1，然後調用scale_horz進行水準方向的縮放，中間結果儲存到RotBufY2，再調用scale_vert進行垂直反向的縮放，結果放在Buf_Y3，最後把各個分量的組合成輸出到L2空間。 除了對代碼和資料進行分割外，還可以針對相同資料進行處理的算法進行組合到同一片記憶體區域。例如針對Y分量進行操作的函數放在同一片相鄰的記憶體區域，同樣，還可以把Y分量的資料buffer放在臨近的資料空間。 通過資料和代碼的分割以及函數的組合，你可以把cache的有效率提高到90%以上，即大部分的資料和代碼的通路都在cache内完成的。 使用系統優化技術 圖9所示的是一個複數和9個輸入複數向量的點積比較。前面提到，像點積這種算法是不會重用輸入資料的，總是對每個輸入樣點采取很少的操作，然後就把資料存儲起來，這種很少的操作往往需要很少的時間運作，而為了提高資料的重用，應該讓一段資料做盡可能多的操作之後再儲存到存儲空間。如圖9中的針對複數向量的簡單運算的cache有效率僅為79%，如果采用系統級的優化政策，進行合理的函數功能劃分把針對同一塊資料的操作組合，cache的有效率能提高到93%. 圖9. 複數向量的引用 總結 Caches通過靠近CPU的較快的存儲器通路來提高系統帶寬提高代碼和資料的通路效率。Cache通常容量很小，速度很快，利用資料和代碼的通路時間和空間的關聯性來讓CPU盡可能從cache記憶體取資料和加載代碼，而最近CPU不通路的資料和代碼則放在片外的低層次的存儲空間。 需要進行對一段資料進行相當大處理運算的算法，如FIR濾波和FFT運算在cache系統裡效率很高，而那些疊代運算讓我們能擷取代碼和資料的重用提高cache的有效性。而諸如向量點積的運算不會重用輸入資料，運算量很少，可以通過分割代碼和資料、重新組織函數代碼的組合、資料重用等系統優化政策來提高cache的效率。 References
|
關鍵字：C64x DSP Cache DMA L1P L1D 直接映射 set-associative; 本主題的第一部分主要以TI C64x DSP為例介紹cache緩存的基本概念， 解釋了為什麼需要cache，cache如何和主記憶體進行通信以及如何優化cache的性能。第二部分主要介紹了怎麼配置cache以及怎樣正确的使用cache，即如何保證cache的一緻性。其中有關于DMA的傳輸怎麼影響cache以及怎麼管理DMA傳輸的雙緩存。