[發明專利]面向數據無沖突程序的共享數據動態更新方法

有效

• 申請號: 201711473691.7
• 申請日: 2017-12-29
• 公開（公告）號: CN108170544B
• 公開（公告）日: 2020-08-28
• 發明（設計）人: 馬勝;王志英;何錫明;陸洪毅;沈立;陳微;劉文杰
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: G06F9/54
• 分類號: G06F9/54
• 代理公司: 湖南兆弘專利事務所(普通合伙) 43008
• 代理人: 周長清;胡君

本發明公開一種面向數據無沖突程序的共享數據動態更新方法，該方法包括：執行數據無沖突的并行程序過程中，CPU執行訪存指令時，識別共享數據請求并收集共享數據被訪問的歷史信息，當在同步點時，根據收集的所述共享數據被訪問的歷史信息對過期的共享數據執行動態更新或失效操作，其中對判定為第一類的共享數據執行動態更新操作，對判定為第二類的共享數據進行失效操作。本發明能夠自動實現共享數據的動態更新與失效操作，且具有實現方法簡單、網絡面積以及cache一致性協議開銷小、cache命中率高以及cache一致性協議的性能好等優點。

技術領域

本發明涉及共享存儲多核處理器（Shared-memory Multiprocessors）cache一致性協議技術領域，尤其涉及一種面向數據無沖突程序的共享數據動態更新方法。

背景技術

共享存儲多處理器是一種并行編程模型，提供了一個單一的地址空間來簡化并行編程。使用大容量、多級 cache 可以充分降低處理器對存儲器帶寬的需求，顯著的提高處理器性能，但是這必然造成多個緩存中同時備份一個共享值，這種共享數據的緩存就引入了緩存一致性的問題。Cache一致性問題即為兩個或者多個處理器通過各自的 cache 備份數據，如果不加以防范，它們就可能看到不同的值，為多處理器保持 cache 一致性的協議稱為 cache 一致性協議，即多處理器是采用了一種硬件的解決方案，通過引入協議來保持cache 的一致性。

目前多核處理器系統的軟件和硬件在高效地利用并行上面臨巨大的挑戰，隨著多核的發展，對于高性能的共享存儲的多核處理器的需求不斷的增加。Cache 一致性協議主要包括兩種類型：監聽協議和目錄協議，其中監聽協議通過有序網絡廣播一致性請求，保證所有節點以相同順序處理這些請求，目錄協議的一致性請求先在目錄進行排序，之后發往共享節點。但是目前的共享內存系統體系結構中由于是采用不能感知軟件的硬件設計，上述兩種類型協議存在以下問題：

基于目錄的一致性協議關鍵問題在于目錄開銷和間接的cache到cache的通信開銷：①目錄存儲開銷在保證共享資源的信息準確的同時要保證開銷最小。由完整的位向量目錄編碼特定地址的共享信息，需要的存儲空間是隨核心數線性增加，核心數目造成的存儲開銷會限制它的應用，而粗粒度的共享信息方案包含不準確的共享信息，本質上是犧牲性能以換取可擴展性；②目錄協議來源于延時和通信的開銷造成了很大的性能和功耗問題，目錄協議要求失效消息，回復消息和間接的cache到cache的事務（通過中間目錄）；③由于要處理數據訪問之間的競爭和許多的瞬間狀態，目錄協議正確性問題復雜且難以驗證。雖然有從業者提出許多種優化目錄組織結構，但是這些協議增加了實現的復雜性或者造成了性能、功耗上的開銷，還需要大量的一致性狀態。

監聽一致性不受目錄存儲開銷的限制，而監聽協議關鍵在于使用總線或者其他廣播方式來有序廣播協議事務，確保處理器在寫入一個數據之前，獲取對該數據項的獨占訪問，這樣直接廣播消息的方式相對于目錄協議具有低延時高性能的優勢，但監聽協議本質上是要有序的互連網絡，以確保所有核心都保持相同的順序來實現訪存請求一致性的原語，這有序的廣播網絡往往造成很大的開銷，并且對于可擴展的系統，監聽協議可能失去它的低延時高效的優勢。同時監聽協議兼容的互連網絡主要包括總線或crossbar （利用仲裁進行排序）或無緩沖環 （保證從一個有序節點按順序傳遞到所有節點），然而現有的片上系統互連規模的有序性很差，總線的互連受帶寬的限制，環形網絡存在延時問題，交叉開關的面積開銷會很大，而網格網絡本質是一種無序網絡，無法原生性的支持監聽協議。

目前的cache一致性協議復雜而低效，硬件優化方式受到不同程度的制約，而為了滿足一致性的定義，一致性協議必須對寫操作立即響應，失效共享數據的其它核cache備份，返回最新的數據，目錄協議通過目錄進行間接失效操作，這種cache到cache的失效操作增加了協議的事務延時，降低了協議的性能，同時增加了目錄存儲開銷，如上述監聽協議通過有序網絡廣播作廢請求，該類廣播方式即增加了整個協議的通信開銷。