基于GPU的樹形結(jié)構(gòu)數(shù)據(jù)處理.pdf

1、樹形結(jié)構(gòu)數(shù)據(jù)的應(yīng)用非常廣泛。并行計(jì)算的引入，可以減少處理大量數(shù)據(jù)的時(shí)間。近年來，利用顯示處理器(GPU)來并行處理樹形結(jié)構(gòu)數(shù)據(jù)取得了不少研究成果。然而，在這些研究中，樹在GPU中的存儲結(jié)構(gòu)，一般都只能用于存儲某一種類型的樹，并且只支持一種或者少數(shù)幾種樹的遍歷方式。本文提出了一種數(shù)據(jù)結(jié)構(gòu)，可以被用于存儲多種類型的樹，并且支持四種基本的樹的遍歷方式:先序遍歷，中序遍歷，后序遍歷和廣度優(yōu)先遍歷。因此大多數(shù)的有關(guān)樹的算法，都可以通過這種數(shù)據(jù)結(jié)構(gòu)

2、在GPU上實(shí)現(xiàn)。
　　本研究主要內(nèi)容包括：⑴提出一種應(yīng)用于GPU上的樹形數(shù)據(jù)結(jié)構(gòu)。⑵基于所提出的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)和實(shí)現(xiàn)了樹的四種遍歷方式：先序遍歷、中序遍歷、后序遍歷和廣度優(yōu)先遍歷。通過實(shí)驗(yàn)測試和分析四種遍歷方式在GPU上的時(shí)間消耗。⑶基于所提出的數(shù)據(jù)結(jié)構(gòu)以及遍歷方法，在NVIDIA GPU上設(shè)計(jì)和實(shí)現(xiàn)了加權(quán)樹相似度算法。通過對比實(shí)驗(yàn)研究探索GPU應(yīng)用的性能，并分析本文所提出的數(shù)據(jù)結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明利用GPU并行處理數(shù)據(jù)，可提高效率