[發明專利]用于高速緩沖存儲器替換的數據處理系統和方法

無效

• 申請號: 200580042315.1
• 申請日: 2005-12-05
• 公開（公告）號: CN101073051A
• 公開（公告）日: 2007-11-14
• 發明（設計）人: 薩伊納斯·卡爾拉帕勒姆;比約·托馬斯;納加拉杰·布薩
• 申請（專利權）人: 皇家飛利浦電子股份有限公司
• 主分類號: G06F9/38
• 分類號: G06F9/38;G06F9/46;G06F12/12
• 代理公司: 中科專利商標代理有限責任公司
• 代理人: 朱進桂

背景技術

當今的數據處理系統或處理器是基于特定存儲器分層分層結構的，包括具有不同速度和尺寸的存儲器。然而，??由于快速存儲器較昂貴，所以將存儲器分層分層結構組織為多個等級，其中每個等級比相鄰的下一等級的每個字節更小、更快速、更昂貴。通常，一個等級中的所有數據也可在下一等級中找到，并且可在該下一等級的下一等級中找到所有該下一等級的數據，直到達到分層分層結構的底層。具有多處理器環境的多任務數據處理系統通常包括同時在各個處理器上運行的多個應用程序。

高速緩沖存儲器是存儲器分層結構的第一等級，即，它是最靠近CPU或處理單元的存儲器。如果CPU請求可在高速緩沖存儲器中找到的數據項，則發生所謂的高速緩沖存儲器命中。然而，如果不能夠在高速緩沖存儲器中找到CPU所請求的數據項，則發生所謂的高速緩沖存儲器未命中。校正高速緩沖存儲器未命中并獲取所請求的數據項所需的時間取決于存儲器的等待時間和帶寬。等待時間對應于搜索塊的第一個字的時間，帶寬與搜索塊的剩余部分的時間有關，高速緩沖存儲器的基本概念是獲取這些數據項，這將需要在實際處理之前在即將到來的處理循環周期進行數據項的獲取。

一旦發生高速緩沖存儲器未命中，則高速緩沖存儲器控制器必須選擇當前存儲在高速緩沖存儲器中的數據項或塊，用要獲取的希望的數據項或數據塊來替換該數據項或塊。可隨機地、根據最近使用LRU或根據先入先出FIFO來執行實際的高速緩沖存儲器替換。通過均勻分配來執行隨機選擇，從而隨機地選擇塊。為了減少在下一到來的周期期間拋掉所需的信息的可能性，在最近很少使用的高速緩沖存儲器替換方案中記錄了對塊的訪問。因此，根據過去的訪問來計算預測，從而用最長時間段未用的塊來替換這些塊。然而，由于LRU高速緩沖存儲器替換策略計算量大，所以根據先入先出替換策略，確定最早的塊用于替換而不是LRU。

先入先出FIFO替換策略還可稱為循環選擇。這里，僅在未命中而不是每次命中時更新高速緩沖存儲器。通過更新數據、地址標記等來執行對塊的替換。將高速緩沖存儲器中由高速緩沖存儲器替換策略所選擇要替換的數據塊稱為犧牲塊。可將這種犧牲塊移動到犧牲緩沖器。將犧牲塊寫入存儲器分層結構中的相鄰等級中。

一般而言，平均存儲器訪問時間與命中時間加上未命中比率乘以未命中判罰之積的和相對應，一種減少未命中判罰的技術是采用多級高速緩沖存儲器。這里，忽略實際的CPU而關注于高速緩沖存儲器和主存儲器之間接口。通過在原始的高速緩沖存儲器和主存儲器之間添加另一級的高速緩沖存儲器，可將第一級的高速緩沖存儲器設計為足夠小以與快速CPU的時鐘周期相匹配，而第二級的高速緩沖存儲器可足夠大以捕獲要由CPU在到來的時鐘周期期間使用的充足的數據。

另一減少未命中判罰的技術是采用犧牲高速緩沖存儲器。這里，從例如L1高速緩沖存儲器的高速緩沖存儲器中丟棄的數據項(犧牲塊)可存儲在犧牲高速緩沖存儲器中。在已經從主存儲器或其它高速緩沖存儲器等級中取回了從高速緩沖存儲器中丟棄的數據(犧牲塊)時，可以以低等待時間來重新使用該數據項或數據塊。因此，這些被丟棄的數據項或數據塊被存儲在犧牲高速緩沖存儲器中。換言之，僅將由于高速緩沖存儲器未命中和隨后的高速緩沖存儲器替換而丟棄的數據項存儲在犧牲高速緩沖存儲器中。

這種犧牲高速緩沖存儲器通常是較小的完全相關的高速緩沖存儲器。該高速緩沖存儲器設計用于存儲由于沖突缺失或容量缺失而從CPU或L1高速緩沖存儲器中丟棄的塊。典型地將該高速緩沖存儲器設置在主高速緩沖存儲器及其替換路徑之間。僅將由于高速緩沖存儲器未命中而從L1高速緩沖存儲器中丟棄的塊存儲在其中。將其用于減少高速緩沖存儲器未命中判罰。

另一高速緩沖存儲器替換策略是最不經常使用的技術；其中，從高速緩沖存儲器中丟棄最不經常使用的塊，以為新預取數據創造空間。

關于高速緩沖存儲器替換技術，有兩個重要問題，即應該將哪個數據塊取回到高速緩沖存儲器中和應該從高速緩沖存儲器中丟棄哪個數據塊，使得新取回的數據塊可存儲在高速緩沖存儲器中而不是丟棄的數據塊。

發明內容

本發明的目的是提供一種數據處理系統，包括具有改進的高速緩沖存儲器替換能力的多個處理單元和高速緩沖存儲器，還提供了一種高速緩沖存儲器替換方法。

由根據權利要求1所述的數據處理系統以及根據權利要求5所述的高速緩沖存儲器替換方法來實現該目的。