[發明專利]一種基于片上多核處理器共享cache的動態公平劃分方法

有效

• 申請號: 200910243653.1
• 申請日: 2009-12-18
• 公開（公告）號: CN101739299A
• 公開（公告）日: 2010-06-16
• 發明（設計）人: 方娟;蒲江
• 申請（專利權）人: 北京工業大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 劉萍

技術領域

本發明屬于計算機體系結構領域，具體涉及一種基于片上多核處理器共 享cache的動態公平劃分方法。

背景技術

多核處理器已成為今后微處理器發展的重要趨勢，目前主流的片上多核 處理器(chip?Multiprocessor，簡稱CMP)大多使用私有一級(或一級和二 級)Cache(即為高速緩存)，共享二級(或三級)Cache的片上存儲結構。 這種結構通過共享二級(或三級)Cache和更低的存儲層，最大限度地提高 資源利用率來避免重復開銷。然而，隨著并發執行線程數量的增加，存儲層 所承受的壓力也在不斷地增大。最近的研究表明，共享Cache的沖突訪問對 處理器的性能影響很大，而CMP中共享Cache的分配主要由LRU(Least Recently?Uesed)策略隱式決定，設計高效的共享Cache劃分算法成為當前研 究的重要問題。

目前對共享Cache劃分策略的研究幾乎都是針對如何提高吞吐量的，對 公平性的研究極少。公平性是一個關鍵的優化問題。如果多用戶系統采用的 是單線程處理器，那么操作系統(OS?operated?system)線程調度器通過合理 的分配時間片就可以保證所有線程公平的運行。但是如果多用戶系統采用的 是CMP處理器，所有被調度運行的線程共享Cache資源，在缺乏公平性情況 下，會出現線程餓死和優先級反轉等問題。為了保證所有線程公平，單純依 靠操作系統線程調度器是不夠的，系統硬件必須提供相應的支持。實際上， 在多用戶系統中，公平性比吞吐量更加重要，因為沒有哪個用戶愿意等待更 長的時間。因此，將公平性作為CMP結構下主要的優化目標，可以簡化操作 系統的設計，并且可以顯著提升系統整體性能。

公平性就是所有的線程有相同的機會獲得其運行所要求的資源，并保證 沒有線程餓死。但公平并不意味著所有線程具有相同的吞吐量。通常情況下， 公平和效率(其主要指標為系統吞吐量)相互影響和制約，一方的提高有時 會帶動另一方的改善，但有時會削弱另一方。在某些特殊情況下，則會嚴重 影響另一方導致系統失衡。例如追求效率最大化時，會嚴重削弱系統的公平 性。所以Cache的劃分方案必須很好的平衡公平和效率，以達到最佳設計目 標。

因為公平性的定義沒有給出定量的指標，所以公平性參數亦是眾說紛紜。 一個被廣泛接受的參數是定義T_dedi為線程i獨占整個Cache的執行時間，T_shri為線程i與其余線程共享Cache的執行時間，則最公平的理想情況如式(1) 所示，

Tshr1Tded1=Tshr2Tded2=...=TshrnTdedn---(1)]]>

該等式被稱為執行時間公平性標準數。Seongbeom?Kim提出了一個公平 優先的cache劃分方案，其公平性參數為式(2)，