【摘要】：隨著信息技術(shù)的迅速發(fā)展,我們可以通過互聯(lián)網(wǎng)從世界各地接收和發(fā)送信息,然而,信息交互的過程中遇到了一個(gè)突出的問題：不同的平臺(tái)用到的數(shù)據(jù)格式可能是各種各樣的,也就是數(shù)據(jù)格式的異構(gòu)性問題。XML的出現(xiàn)為這一問題的解決提供了理論和技術(shù)支持。隨著Internet技術(shù)的不斷發(fā)展,XML技術(shù)的應(yīng)用也不斷擴(kuò)展。人們不僅可以運(yùn)用XML技術(shù)進(jìn)行銀行間的數(shù)據(jù)交換、圖書館對館藏書目的查詢檢索、企事業(yè)單位對文件檔案進(jìn)行管理,還可以用于電子商務(wù)、搜索引擎軟件等領(lǐng)域。XML技術(shù)在IT環(huán)境中扮演著越來越重要的角色,己逐漸成為互聯(lián)網(wǎng)上傳遞和交換信息的事實(shí)標(biāo)準(zhǔn)。 由于各個(gè)領(lǐng)域的XML數(shù)據(jù)量以爆炸性的速度增長,以及XML本身的重大改善,以傳統(tǒng)的串行方式對XML進(jìn)行查詢已經(jīng)不能滿足人們對查詢效率的要求,更高效率、更大吞吐量的XML查詢方法的研究顯得越發(fā)重要和迫切,如何加快XML查詢和如何提高查詢的吞吐量正在成為XML查詢技術(shù)的熱門研究課題。 目前,在XML數(shù)據(jù)查詢優(yōu)化方面,主要通過三種技術(shù)手段：利用成熟的數(shù)據(jù)庫技術(shù)優(yōu)化查詢、利用索引優(yōu)化查詢和利用并行技術(shù)優(yōu)化查詢。利用數(shù)據(jù)庫來優(yōu)化查詢的方法,主要是在傳統(tǒng)的關(guān)系型數(shù)據(jù)庫的基礎(chǔ)上,增加對XML數(shù)據(jù)結(jié)構(gòu)的支持,通過把XML數(shù)據(jù)映射成為關(guān)系型數(shù)據(jù)類型,進(jìn)而利用目前較為成熟的關(guān)系型數(shù)據(jù)庫管理技術(shù)對XML數(shù)據(jù)進(jìn)行存儲(chǔ)、查詢和管理。利用索引技術(shù)對XML數(shù)據(jù)的查詢進(jìn)行優(yōu)化的方法,主要是充分利用XML文檔自身的自描述性和半結(jié)構(gòu)化等特性,通過某種分類或者簡化的方法把XML數(shù)據(jù)進(jìn)行分類和建立索引,以此達(dá)到優(yōu)化管理、查詢的目的。這兩種方法是目前最流行和通用的方法,其本質(zhì)都是通過改善查詢算法的本身來達(dá)到優(yōu)化的目的。利用并行技術(shù)優(yōu)化查詢的方法是指通過當(dāng)前硬件具有強(qiáng)大的通用計(jì)算能力來支持XML并行查詢,這種方法的研究目前還很少見到,具有較大的研究價(jià)值和發(fā)展前景。 隨著GPU技術(shù)的迅速發(fā)展,特別是GPU通用計(jì)算(GPGPU)的提出和應(yīng)用,GPU以其高度并行的特性正在高性能計(jì)算領(lǐng)域發(fā)揮著巨大作用。因此,基于GPU的并行優(yōu)化技術(shù)也逐漸成為研究的熱點(diǎn)。 鑒于以上兩點(diǎn),本文結(jié)合XML查詢技術(shù)和GPU的并行優(yōu)化技術(shù)這兩個(gè)熱點(diǎn),主要研究了如何使用GPU強(qiáng)大的通用計(jì)算能力來加快XML數(shù)據(jù)查詢的效率問題,提出了基于CPU-GPU協(xié)同并行的XML數(shù)據(jù)查詢優(yōu)化算法。為了實(shí)現(xiàn)這個(gè)算法,我們需要引入一些公共基礎(chǔ)。首先,由于XML的文檔結(jié)構(gòu)是一個(gè)自上而下的樹形結(jié)構(gòu),節(jié)點(diǎn)與節(jié)點(diǎn)之間有著密切的關(guān)系,鑒于XML的這種特殊的文檔結(jié)構(gòu),我們需要對XML文檔節(jié)點(diǎn)進(jìn)行編碼。本文采用Dewey編碼對XML文檔進(jìn)行編碼,一是可以方便地管理和獲取節(jié)點(diǎn),二是可以利用節(jié)點(diǎn)的編碼迅速地將XML文檔從CPU端傳送到GPU端,并在GPU端快速反序列化,恢復(fù)XML文檔的樹形結(jié)構(gòu),以方便查詢的執(zhí)行。其次,由于對XML文檔的解析是一個(gè)非常耗時(shí)的工作,因此,為了避免每次查詢都要花費(fèi)過多時(shí)間來對XML文檔進(jìn)行解析,本文采用Xerces-C對XML文檔進(jìn)行解析,并將解析后的文檔存放到嵌入式數(shù)據(jù)庫BerkeleyDB中,以實(shí)現(xiàn)一次解析,永久查詢。 本文首先對XML和XML查詢語言、GPU發(fā)展現(xiàn)狀和NVIDIA的通用計(jì)算架構(gòu)——CUDA編程模型做了簡要介紹。然后提出了基于CPU-GPU協(xié)同并行的XML數(shù)據(jù)查詢優(yōu)化算法。算法首先實(shí)現(xiàn)一個(gè)代價(jià)分析模型,該模型用于估算查詢的代價(jià),以初步判斷該查詢是否需要進(jìn)行GPU并行執(zhí)行,如果需要進(jìn)行并行執(zhí)行,則算法采用查詢路徑和查詢數(shù)據(jù)量均衡分配相結(jié)合的并行分解策略。最后,采用CUDA架構(gòu)實(shí)現(xiàn)了簡化后的XML查詢語言XPath,并分析了該算法的性能。為了證明該算法的可行性,本文主要從查詢加速比和查詢時(shí)間兩個(gè)方面進(jìn)行了對比實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)表明,我們的并行模型比基于CPU串行方式進(jìn)行的XML查詢模型有更好的加速比和更高的吞吐量。
[Abstract]:......
【學(xué)位授予單位】：廣西師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類號(hào)】：TP311.13

【參考文獻(xiàn)】

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

1 施燕斌,劉春紅;XML簡介及其應(yīng)用淺析[J];高校圖書館工作;2002年02期

2 龔隨;;木桶原理[J];工會(huì)博覽(社會(huì)版);2007年06期

3 路燕,張亮,段起陽,施伯樂;一種基于DTD的XML索引方法[J];計(jì)算機(jī)研究與發(fā)展;2005年01期

4 靳強(qiáng)勇,李冠宇,張俊;異構(gòu)數(shù)據(jù)集成技術(shù)的發(fā)展和現(xiàn)狀[J];計(jì)算機(jī)工程與應(yīng)用;2002年11期

5 盧風(fēng)順;宋君強(qiáng);銀�？�;張理論;;CPU/GPU協(xié)同并行計(jì)算研究綜述[J];計(jì)算機(jī)科學(xué);2011年03期

6 任家東;馬瑞;;M*(k)-index構(gòu)造算法的改進(jìn)[J];計(jì)算機(jī)工程;2008年19期

7 魏東平;宗德君;孫華國;;基于DTD的XML索引查詢技術(shù)[J];計(jì)算機(jī)工程;2009年18期

8 萬靜;姜蓉;易軍凱;;基于雙路索引的XML查詢優(yōu)化研究[J];計(jì)算機(jī)工程;2010年15期

9 吳海濤;唐振民;;XML文檔的Dewey編碼生成算法[J];計(jì)算機(jī)工程;2010年19期

10 周傲英,胥正川,郭志懋,周水庚;VXMLR系統(tǒng)存儲(chǔ)模式的自適應(yīng)調(diào)整[J];計(jì)算機(jī)學(xué)報(bào);2004年04期

相關(guān)博士學(xué)位論文 前1條

1 白洪濤;基于GPU的高性能并行算法研究[D];吉林大學(xué);2010年

相關(guān)碩士學(xué)位論文 前4條

1 吳小霞;GPU高性能計(jì)算技術(shù)在晶格玻爾茲曼方法模擬中的應(yīng)用[D];廣西師范大學(xué);2011年

2 劉建華;基于關(guān)系數(shù)據(jù)庫的XML存儲(chǔ)查詢系統(tǒng)設(shè)計(jì)[D];合肥工業(yè)大學(xué);2004年

3 陳金森;XML搜索引擎中索引技術(shù)的研究[D];燕山大學(xué);2006年

4 譚兵;圖像顯著性區(qū)域檢測及其GPU并行計(jì)算[D];大連理工大學(xué);2012年

，

本文編號(hào)：2264406