[發(fā)明專利]一種事務(wù)性內(nèi)存的實(shí)現(xiàn)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 200810239010.5
• 申請(qǐng)日: 2008-12-04
• 公開(kāi)（公告）號(hào): CN101425052A
• 公開(kāi)（公告）日: 2009-05-06
• 發(fā)明（設(shè)計(jì)）人: 范彬;吳承勇
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院計(jì)算技術(shù)研究所
• 主分類號(hào): G06F13/42
• 分類號(hào): G06F13/42
• 代理公司: 北京泛華偉業(yè)知識(shí)產(chǎn)權(quán)代理有限公司
• 代理人: 王 勇

技術(shù)領(lǐng)域

本發(fā)明涉及多線程環(huán)境下事務(wù)的處理，特別涉及一種事務(wù)性內(nèi)存的實(shí)現(xiàn)方法。

背景技術(shù)

隨著多核體系結(jié)構(gòu)的發(fā)展和普及，傳統(tǒng)的串行編程模型不再適合多核體系結(jié)構(gòu)的需要。擺在編程語(yǔ)言和編程工具的設(shè)計(jì)者面前的問(wèn)題是：如何提供一種復(fù)雜性較低，并且適用于多核體系結(jié)構(gòu)的編程模型？事務(wù)性內(nèi)存便是在這一背景下提出的，在參考文獻(xiàn)1“M.Herlihy，J.Eliot?B.Moss：Transactional?Memory：Architectural?Support?for?Lock-Free?Data?Structures.Proceedings?of?the?20th?annual?international?symposium?on?Computerarchitecture，1993”中最早提出了事務(wù)性內(nèi)存的概念。所述的事務(wù)性內(nèi)存是一種并行編程模型及其實(shí)現(xiàn)的統(tǒng)稱，它的基本思想是提供一種粗粒度的編程語(yǔ)言結(jié)構(gòu)——事務(wù)，并保證事務(wù)中包含的訪存操作具有原子性的特征。此處所述的原子性是事務(wù)的一個(gè)特征，舉例而言，若在兩個(gè)線程Ta和Tb各自包含一組訪存操作Ma和Mb(Ma和Mb中可能含有多條訪存指令)，則在Ta和Tb并行執(zhí)行的過(guò)程中，Ma執(zhí)行時(shí)看到的內(nèi)存映像或者是Mb全部執(zhí)行完畢的結(jié)果，或者是Mb完全沒(méi)有執(zhí)行的結(jié)果，對(duì)于Mb的執(zhí)行也有類似的約定。

程序員在使用事務(wù)性內(nèi)存模型編寫程序時(shí)，只需將若干組可能相互沖突的訪存操作全部聲明為事務(wù)，就可以保證這些組訪存操作的原子性。原子性是確保并行程序正確性的重要特性，事務(wù)性內(nèi)存通過(guò)非常易于理解的方式令程序員表達(dá)了這種并行程序內(nèi)在的性質(zhì)。除了正確性之外，并行程序的性能也是編程人員關(guān)注的重要方面，事務(wù)性內(nèi)存實(shí)現(xiàn)的優(yōu)劣和應(yīng)用程序性能有著非常緊密的聯(lián)系。一個(gè)高效的事務(wù)性內(nèi)存的實(shí)現(xiàn)可以令使用該模型編寫的應(yīng)用具有良好的單線程性能和多線程環(huán)境下的可擴(kuò)展性。

事務(wù)性內(nèi)存的實(shí)現(xiàn)過(guò)程一般包括元數(shù)據(jù)的管理、沖突的檢測(cè)、沖突的解決等幾個(gè)部分。在實(shí)現(xiàn)方法上，事務(wù)性內(nèi)存的實(shí)現(xiàn)可以分為純軟件實(shí)現(xiàn)，純硬件實(shí)現(xiàn)和混合式實(shí)現(xiàn)。純軟件實(shí)現(xiàn)就是將實(shí)現(xiàn)中涉及的幾個(gè)部分全部通過(guò)軟件實(shí)現(xiàn)(通常以一個(gè)庫(kù)的方式提供)，相應(yīng)的，硬件實(shí)現(xiàn)就是將這幾部分全部通過(guò)硬件實(shí)現(xiàn)(通常是提供能夠?qū)崿F(xiàn)相應(yīng)功能的機(jī)器指令)。而混合式的實(shí)現(xiàn)方式對(duì)軟硬件進(jìn)行了分工，根據(jù)軟硬件自身的功能特點(diǎn)實(shí)現(xiàn)事務(wù)性內(nèi)存的不同部分。一般來(lái)說(shuō)，軟件實(shí)現(xiàn)方式比硬件實(shí)現(xiàn)方式更為靈活，能夠支持更多的語(yǔ)言特性，但在性能上不如硬件實(shí)現(xiàn)，且在硬件事務(wù)性內(nèi)存平臺(tái)上編寫的應(yīng)用也難以移植到其他平臺(tái)上。混合式的實(shí)現(xiàn)方式能夠發(fā)揮軟硬件各自的長(zhǎng)處，相對(duì)于軟件實(shí)現(xiàn)和硬件實(shí)現(xiàn)來(lái)說(shuō)是一種更為有效的事務(wù)性內(nèi)存實(shí)現(xiàn)方案。

在現(xiàn)有技術(shù)中，已經(jīng)存在采用混合式實(shí)現(xiàn)方式實(shí)現(xiàn)事務(wù)性內(nèi)存的方法，例如，在參考文獻(xiàn)2“B.Saha，A.Adl-Tabatabai，Q.Jacobson：ArchitecturalSupport?for?Software?Transactional?Memory.Proceedings?of?the?39th?AnnualIEEE/ACM?International?Symposium?on?Microarchitecture，2006”中，提出了一種混合式事務(wù)性內(nèi)存方案，該方案將一個(gè)純軟件模式和軟硬件模型相結(jié)合。其優(yōu)點(diǎn)在于：通過(guò)運(yùn)行時(shí)系統(tǒng)的支持，該方案具有較好的易編程性；將軟硬件相結(jié)合后，硬件能夠去除冗余的讀攔截和降低讀集合一致性檢測(cè)的開(kāi)銷，加速已有軟件事務(wù)執(zhí)行的作用。其缺陷在于：1)硬件功能相對(duì)簡(jiǎn)單，軟件在讀攔截和沖突檢測(cè)方面仍然需要付出較大開(kāi)銷；2)該方法只是減少但并沒(méi)有避免讀集合一致性檢測(cè)，當(dāng)出現(xiàn)高速緩存塊換出時(shí)，仍需進(jìn)行讀集合一致性檢測(cè)。實(shí)驗(yàn)表明，讀攔截和讀集合一致性檢測(cè)開(kāi)銷是軟件事務(wù)性內(nèi)存開(kāi)銷的主要組成部分，因此，該方案中混合模型的性能相對(duì)還不夠好。