資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學資料結構中快取未命中的計數
在演算法分析中，我們計算操作和步驟。當計算機執行操作所需的時間比獲取該操作所需資料的時間長得多時，這基本上是合理的。如今，執行操作的成本遠低於從記憶體中獲取資料的成本。
許多演算法的執行時間主要取決於記憶體引用次數（快取未命中次數），而不是操作次數。因此，當我們嘗試設計一些演算法時，我們必須關注的不僅是減少操作次數，還要減少記憶體訪問次數。還必須專注於設計能夠隱藏記憶體延遲的演算法。
假設存在一個簡單的計算機模型，其中計算機的記憶體由L1快取、L2快取和主記憶體組成。我們使用ALU對暫存器(R)中駐留的資料執行一些算術和邏輯運算。
這是它的框圖：
從圖中我們還可以瞭解記憶體和快取的大小。主記憶體基本上是數百或數千MB。L2快取是MB的一小部分，L1快取是KB。暫存器大小為幾位元。當我們執行程式時，所有資料都在記憶體中。如果我們新增一些操作，例如ADD，則第一個數字將儲存到暫存器中，暫存器中的資料將被新增，然後結果將被寫入記憶體。
假設一個週期是將已在暫存器中的資料相加所需的時間長度。在這個模型中，從L1快取載入資料到暫存器所需的時間假設為兩個週期。如果所需資料不在L1快取中，但在L2快取中，則會發生L1快取未命中，所需資料將從L2快取取到L1快取和暫存器中，需要10個週期。當所需資料也不在L2快取中時，會發生L2快取未命中，所需資料將從主記憶體取到L2快取、L1快取和暫存器中，需要100個週期。然後，即使資料寫入主記憶體，寫入操作也計為一個週期，因為我們不會在繼續下一個操作之前等待完成寫入。
更新於：2020年8月10日
212 次瀏覽
廣告