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

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

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