【摘要】：針對計算資源日益增加的需求,單純提高處理器主頻的方式,已經(jīng)不再能夠提升計算機(jī)的性能了。因此,工業(yè)界引入了“多核”的概念,即在一個芯片上集成兩個或多個獨(dú)立的處理器,處理器之間共享內(nèi)存。在多核系統(tǒng)中,同樣的時鐘頻率,由于片上處理器個數(shù)的增加,每秒鐘執(zhí)行的指令數(shù)也隨著翻倍,這為解決處理器性能的瓶頸問題提供了新的思路。與此同時,多核系統(tǒng)也給并行處理提出了新的問題,如何能夠更好地利用多核的資源對程序進(jìn)行并行處理,成為當(dāng)今并行處理方面研究的一個熱點(diǎn)方向。事務(wù)的概念來源于數(shù)據(jù)庫,實踐證明了其是一種有效的并發(fā)控制手段。因此,將事務(wù)引入并行程序設(shè)計領(lǐng)域,形成了事務(wù)存儲的理論。事務(wù)存儲中的事務(wù),指的是被某個線程執(zhí)行的對內(nèi)存的一系列有序讀寫操作序列。這些序列或者全部被執(zhí)行并提交,或者一個也不執(zhí)行并恢復(fù)到執(zhí)行該序列之前的狀態(tài)。本文首先對現(xiàn)有的各類事務(wù)存儲系統(tǒng)進(jìn)行了分析,重點(diǎn)研究了基于Signature數(shù)據(jù)結(jié)構(gòu)的軟件事務(wù)存儲系統(tǒng)。然后針對軟件事務(wù)存儲系統(tǒng)中的三大基本功能分別進(jìn)行了研究,提出了新的優(yōu)化方案,并對這些方案進(jìn)行了仿真實驗。最后,將改進(jìn)后的功能整合起來構(gòu)成一個基于Signature的軟件事務(wù)存儲系統(tǒng)。本文的主要研究成果如下：(1)在研究了沖突檢測算法VHB的基礎(chǔ)之上,提出了一種基于Signature的新的沖突檢測算法VHTB。該算法不但對Signature的行與行之間進(jìn)行動態(tài)變換,而且對地址數(shù)據(jù)相對較少的情況采用了尚未使用的存儲空間來存儲哈希函數(shù)的True Bloom映射信息。這種并行實現(xiàn)的方式既可以對塊內(nèi)的行與行之間進(jìn)行并行搜索,降低延時,同時也可以降低誤判率。經(jīng)實驗測試VHTB算法的誤判率和中止率較VHB算法有了明顯的降低。(2) True Bloom和Hash Bloom是事務(wù)存儲中常用的沖突檢測算法,而這兩種算法各有其特點(diǎn),在此基礎(chǔ)之上將Signature區(qū)域劃分為兩個區(qū)域,對其中一個區(qū)域進(jìn)行True Bloom映射,對另一個區(qū)域進(jìn)行Hash Bloom映射,由此提出了一種沖突檢測算法Mix Bloom。實驗證明該算法較Hash Bloom算法有著較低的誤判率和中止率。(3)針對軟件事務(wù)存儲中數(shù)據(jù)版本管理的問題,提出了一種結(jié)合急切版本管理和惰性版本管理于一身的混合數(shù)據(jù)版本管理機(jī)制。在該機(jī)制中,混合數(shù)據(jù)版本管理器能夠根據(jù)沖突的數(shù)量進(jìn)行動態(tài)地雙向切換,從而選取最適合當(dāng)前狀態(tài)的數(shù)據(jù)版本管理策略。實驗證明混合數(shù)據(jù)版本管理策略在整體上取得了較好的性能,達(dá)到了預(yù)期的效果。(4)在現(xiàn)有的沖突解決策略的基礎(chǔ)上,結(jié)合各個沖突解決策略的優(yōu)點(diǎn),提出了一種沖突解決策略Synthesized。該策略綜合了若干因素,包括Polite的隨機(jī)指數(shù)回退、Karma的優(yōu)先級、Eruption的繼承優(yōu)先級以及Justice的權(quán)重等,形成一個綜合的沖突解決策略。實驗證明了該沖突解決策略與現(xiàn)有策略相比,有較高的事務(wù)提交數(shù)量。(5) Rochester STM是一種常用的軟件事務(wù)存儲系統(tǒng),該系統(tǒng)僅采用單一沖突解決策略來處理沖突。為解決這一問題,提出了一種復(fù)合型沖突解決策略Comprehensive。該策略在兩個事務(wù)發(fā)生沖突時根據(jù)兩個事務(wù)的丟棄成本、嘗試次數(shù)以及起始時間等因素來決定丟棄哪個事務(wù)。實驗證明了該沖突解決策略性能較其他沖突解決策略有顯著的提高。(6)設(shè)計并實現(xiàn)了一個支持多種基于Signature的沖突檢測算法的事務(wù)存儲系統(tǒng)RingSS (Ring Support Signature),并在RingSS中對本文中提出的改進(jìn)策略進(jìn)行了評測。結(jié)果表明,在該事務(wù)存儲系統(tǒng)中,通過使用新的策略,使系統(tǒng)的性能得到了提升。本文研究了多核環(huán)境下軟件事務(wù)存儲系統(tǒng)中的沖突檢測、數(shù)據(jù)版本和沖突解決等的相關(guān)問題,提出了新穎的解決方法,能夠有效地解決多核結(jié)構(gòu)上并行程序設(shè)計的關(guān)鍵問題。理論分析和大量的實驗結(jié)果證明了這些方法的有效性。這些方法和技術(shù)對于這一領(lǐng)域的研究工作具有參考價值。
[Abstract]:In view of the increasing demand for computing resources, the way to improve the primary frequency of the processor is no longer able to improve the performance of the computer. Therefore, the industry has introduced the concept of "multi core", that is, to integrate two or more independent processors on a single chip, shared memory between the processors. In a multi-core system, the same clock frequency. With the increase of the number of processors on the chip, the number of instructions executed per second doubles, which provides a new way of thinking to solve the bottleneck problem of processor performance. At the same time, the multi-core system also presents a new problem for parallel processing, how to make better use of multi core resources for parallel processing of programs and become today parallel. The concept of transaction is a hot topic. The concept of transaction comes from the database, and it has proved that it is an effective means of concurrency control. Therefore, the transaction is introduced into the domain of parallel programming to form the theory of transaction storage. Transactions in transaction storage refer to a series of read and write to memory executed by a thread. The sequence of operations. These sequences are or are all executed and submitted, or a state that is not executed and restored to the execution of the sequence. This article first analyzes the existing transaction storage systems and focuses on the software transaction storage system based on the Signature data structure. Then, it is aimed at the software transaction storage system. Three basic functions are studied, new optimization schemes are proposed and simulation experiments are carried out. Finally, the improved functions are integrated to form a software transaction storage system based on Signature. The main research results of this paper are as follows: (1) on the basis of the study of the conflict detection algorithm VHB A new conflict detection algorithm based on Signature VHTB., the algorithm not only dynamically transforms between the rows and rows of Signature, but also uses unused storage space to store the True Bloom mapping information of the Hashi function with relatively little address data. The parallel search between lines can reduce the delay and also reduce the misjudgment rate. The error rate and the abort rate of the VHTB algorithm are obviously lower than that of the VHB algorithm. (2) the True Bloom and Hash Bloom are the common conflict detection algorithms in the transaction storage, and the two algorithms have their own characteristics, and the Signature region is on the basis of this. Two regions are divided into two regions, and one region is mapped with True Bloom, and the other region is mapped by Hash Bloom. A conflict detection algorithm is proposed, Mix Bloom. experiment proves that the algorithm has a lower error rate and abort rate than Hash Bloom algorithm. (3) the problem of data version management in the storage of soft parts is proposed. A hybrid data version management mechanism combined with urgent version management and lazy version management. In this mechanism, the hybrid data version manager can dynamically switch two direction according to the number of conflicts to select the most suitable data version management strategy for the current state. The experiment proves the mixed data version management strategy. A better performance is achieved on the whole. (4) on the basis of the existing conflict resolution strategy and combining the advantages of each conflict resolution strategy, a conflict resolution strategy, Synthesized., is proposed to synthesize several factors, including Polite's exponential regression, the priority of Karma and the inheritance priority of Eruption. A comprehensive conflict resolution strategy is formed by the weight of the level and Justice. The experiment proves that the conflict resolution strategy has a higher number of transaction submissions compared with the existing strategy. (5) the Rochester STM is a common software transaction storage system, which only uses a single impulse solution decision to deal with the conflict. A complex conflict resolution strategy, Comprehensive., is proposed to decide which transaction is discarded according to the discarding cost of two transactions, the number of attempts and the starting time during the two transaction conflicts. The experiment proves that the performance of the conflict resolution strategy is significantly higher than that of other conflict resolution strategies. (6) design and implement the strategy. A transaction storage system RingSS (Ring Support Signature) supporting multiple Signature based conflict detection algorithms is presented, and the improved strategy proposed in this paper is evaluated in RingSS. The results show that the performance of the system is improved by using the new strategy in the transaction storage system. In the environment of software transaction storage system, such as conflict detection, data version and conflict resolution, a novel solution is proposed, which can effectively solve the key problems of parallel programming in multi-core structure. Theoretical analysis and a large number of experimental results prove the effectiveness of these methods. The research work in one field is of reference value.
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2013
【分類號】：TP333

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 肖明忠;代亞非;;Bloom Filter及其應(yīng)用綜述[J];計算機(jī)科學(xué);2004年04期

2 池靜;倪健;王華;邢秀娥;;Bloom Filter和Weighted Bloom Filter的比較與研究[J];河北師范大學(xué)學(xué)報;2006年04期

3 李s，

本文編號：2126931