基于多核環(huán)境的數(shù)據(jù)結構設計.pdf

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

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