三角網(wǎng)格模型最短路徑并行算法的研究與實(shí)現(xiàn).pdf

1、近年來(lái)，由于三角網(wǎng)格模型在幾何建模、計(jì)算機(jī)圖形學(xué)、網(wǎng)格模型分片等領(lǐng)域的廣泛應(yīng)用，使得人們開始關(guān)注于三角網(wǎng)格模型上最短路徑問(wèn)題的研究。尋找任意兩個(gè)頂點(diǎn)間的最短路徑是三維網(wǎng)格模型的基本計(jì)算問(wèn)題。目前，已有的三角網(wǎng)格模型最短路徑算法大都是基于串行求解，隨著計(jì)算網(wǎng)格規(guī)模的不斷增大，算法的計(jì)算時(shí)間急劇增加。并行計(jì)算為快速求解大規(guī)模復(fù)雜問(wèn)題提供了一個(gè)有效途徑，采用并行方法能在更短的時(shí)間內(nèi)解決相同的問(wèn)題或在相同的時(shí)間內(nèi)解決更多更復(fù)雜的問(wèn)題，計(jì)算效率大

2、大提高。為降低求解三角網(wǎng)格模型上最短路徑問(wèn)題的時(shí)間開銷，以便節(jié)省計(jì)算時(shí)間進(jìn)行更深層次的研究，本文對(duì)三角網(wǎng)格模型最短路徑并行算法進(jìn)行研究，主要內(nèi)容包括：
　　 (1)提出并實(shí)現(xiàn)了基于多層k路劃分任務(wù)分配策略的矩陣乘最短路徑并行算法。該算法借用矩陣乘思想求解所有點(diǎn)對(duì)間最短路徑，創(chuàng)新性地引入圖劃分方法進(jìn)行并行任務(wù)分配。實(shí)驗(yàn)表明，相比采用傳統(tǒng)任務(wù)分配策略，該并行算法能夠有效降低處理器間的通信開銷，從而減少整個(gè)算法的計(jì)算時(shí)間。
　　

3、 (2)提出了采用消息傳遞MPI和共享存儲(chǔ)OpenMP多粒度混合編程的矩陣乘最短路徑并行算法。實(shí)驗(yàn)結(jié)果表明，由于充分利用了SMP機(jī)群兩級(jí)并行的優(yōu)點(diǎn)，該算法的并行性能和執(zhí)行效率明顯優(yōu)于MPI實(shí)現(xiàn)的矩陣乘最短路徑并行算法。
　　 (3)提出并實(shí)現(xiàn)一種基于局部細(xì)分法的三角網(wǎng)格模型最短路徑并行算法。局部細(xì)分法首先細(xì)分初始最短路徑鄰域內(nèi)三角面片上的邊構(gòu)造細(xì)分圖，然后基于該細(xì)分圖求解新的最短路徑，這種方法使得點(diǎn)對(duì)間的最短路徑可以沿三角網(wǎng)格

4、表面獲得。并行算法采用源分割法將圖的頂點(diǎn)分配到各處理器，所有處理器并行執(zhí)行局部細(xì)分算法求得所有點(diǎn)對(duì)間近似最短路徑。實(shí)驗(yàn)結(jié)果表明，該并行算法大大降低了求解所有點(diǎn)對(duì)間近似最短路徑的計(jì)算時(shí)間，取得了較好的并行性能，得到比矩陣乘最短路徑并行算法近似度更高的最短路徑結(jié)果。
　　 本文建立了基于Linux的SMP機(jī)群并行計(jì)算平臺(tái)，構(gòu)建了該平臺(tái)下MPI和MPI+OpenMP兩種并行程序設(shè)計(jì)環(huán)境。對(duì)本文提出的三角網(wǎng)格模型最短路徑并行算法在該實(shí)驗(yàn)