基于多核環(huán)境的數(shù)據(jù)結(jié)構(gòu)設(shè)計.pdf

1、隨著多核處理器的普及，在桌面電腦和筆記本電腦上進(jìn)行并行程序設(shè)計已成為可能。然而，在并行概念尚未普及的今天，傳統(tǒng)的串行計算軟件只能導(dǎo)致多核的閑置，只有在算法設(shè)計及軟件開發(fā)時充分考慮并行性，多核處理器的優(yōu)勢才能真正發(fā)揮。數(shù)據(jù)結(jié)構(gòu)是軟件實現(xiàn)的數(shù)據(jù)類型，傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)是在串行模型下設(shè)計的。因此，研究并設(shè)計基于多核環(huán)境下的數(shù)據(jù)結(jié)構(gòu)具有一定的理論意義和較高的實用價值。
　　 本文主要在以下四個方面進(jìn)行了研究：
　　 (1)對多核環(huán)境

2、下樹形數(shù)據(jù)結(jié)構(gòu)的設(shè)計進(jìn)行了研究。主要考慮并行區(qū)域的選擇，并利用多線程的思想對二又樹進(jìn)行拆分，從而將任務(wù)（如二叉樹的搜索操作）分配到多個核上實現(xiàn)了并行執(zhí)行的目的。
　　 (2)對圖的并行數(shù)據(jù)結(jié)構(gòu)進(jìn)行了研究。多核環(huán)境下，根據(jù)無向圖的空間存儲特點，利用多線程的思想將其搜索過程中的循環(huán)迭代分配到多個線程上并行的執(zhí)行。
　　 (3)對線性遞歸的并行進(jìn)行了研究。結(jié)合多處理機中線性遞歸并行程序的設(shè)計，設(shè)計出基于多核環(huán)境的一種線性遞歸實