記憶體階層與快取

直接映射快取(direct-mapped cache)

想像一個寄物處,你的票號就是你的置物櫃號,由固定規則算出:你號碼的末兩位「就是」你的櫃號。找你的外套快得不得了——你直接走向那一個櫃子,不必搜尋。但有個陷阱:所有號碼末兩位相同的人都得共用那一個櫃子,所以兩個這樣的人不能同時各寄一件外套。直接映射快取正是如此:每個記憶體塊在快取中只被允許住在「一個」位置。

規則是對位址做算術。位址被切成位移(列內第幾個位元組)、索引(用哪個快取槽,算法是區塊號對槽數取模)、與標籤(其餘部分,用來確認身分)。要查一個位址,你直接走到它索引指名的那個槽——沒有選擇、沒有平行搜尋——把那裡存的那一個標籤和位址的標籤比對。相符且有效就是命中;不符就是未命中,進來的區塊直接覆寫那一個槽裡原有的東西。這讓直接映射快取成為最簡單、最快、最便宜的做法:單一次標籤比對,完全不需替換決策。

代價是衝突未命中。因為每個區塊只有一個家,兩個(或更多)剛好映射到同一槽的熱區塊會不斷把彼此淘汰、來回顛簸,即使快取其餘部分還空著。一個在兩個位址相撞的陣列間交替的迴圈,在直接映射快取裡可能命中率近乎零,而組相聯快取輕鬆就能應付。所以直接映射是用較高的衝突未命中率,換取較低的命中時間與較簡單的硬體——有時划算(尤其對較大的低層快取),有時不然。把它理解為一路組相聯最好:相聯度光譜上最簡單的那一點。

一個有 256 條列的快取使用 8 個索引位元。若 0x1000 與 0x2000 的這 8 個索引位元相同,它們就共用一個索引;接著一個同時觸碰兩者的迴圈會在那一個槽上來回拋接——大量衝突未命中——而另外 255 個槽閒置不用。

每個區塊恰有一個允許的槽:查找最快,但碰撞造成衝突未命中。

「直接映射」不代表小或差——它代表相聯度為 1。它的弱點純粹是衝突未命中;對大型的最後一層快取,其簡單與速度可能勝過偶發的碰撞,這正是為何相聯度是取捨、而非單向的升級。

又稱
one-way set-associative cache直接對映快取