摘  要： 在分析LOD內(nèi)在并行性的基礎(chǔ)上，利用通用的并行編程環(huán)境OpenMP對(duì)其進(jìn)行線(xiàn)程化,，提出了一種基于四叉樹(shù)網(wǎng)格劃分的并行簡(jiǎn)化算法,，并在四核計(jì)算機(jī)上應(yīng)用Intel parallel amplifier分析器按函數(shù)查看性能變化,，對(duì)比優(yōu)化前后的數(shù)據(jù),，結(jié)果表明并行化后的加速比和計(jì)算效率有了顯著提高。
關(guān)鍵詞： 多核,；并行,；LOD；四叉樹(shù),；OpenMP ,；Intel parallel amplifier

　計(jì)算機(jī)體系結(jié)構(gòu)正向多處理器以及多核架構(gòu)方向發(fā)展，多核平臺(tái)應(yīng)用越來(lái)越普及,。因此,，多核并行計(jì)算技術(shù)及其應(yīng)用已成為計(jì)算機(jī)領(lǐng)域新的發(fā)展趨勢(shì)，充分利用多核硬件可以有效提高系統(tǒng)應(yīng)用程序的性能,。計(jì)算機(jī)硬件繪圖技術(shù)一直在高速發(fā)展,，特別強(qiáng)調(diào)實(shí)時(shí)性、低延遲,、穩(wěn)定的圖像速度以及圖像清晰度,，但是現(xiàn)有技術(shù)仍然不能滿(mǎn)足3D場(chǎng)景的實(shí)時(shí)繪制。
    地形是自然界最復(fù)雜的景物之一,，要實(shí)時(shí)模擬具有真實(shí)感的大范圍三維地形,，最大的難點(diǎn)是如何精簡(jiǎn)并有效地組織地形數(shù)據(jù)，以達(dá)到高速度、高精確度的可視化目的,。為了獲得高效和理想的視覺(jué)效果和計(jì)算機(jī)處理的速度,，需要采用一種技術(shù)對(duì)場(chǎng)景中的模型進(jìn)行有效的處理。細(xì)節(jié)層次模型LOD（Level of Detail）是一種可以解決簡(jiǎn)化地形,、加快渲染速度的繪制方法,。然而大部分圖形系統(tǒng)或其他類(lèi)型的應(yīng)用程序仍然使用單線(xiàn)程，這就使多核系統(tǒng)平臺(tái)的資源并不能得到完全的利用,。針對(duì)細(xì)節(jié)層次模型采用四叉樹(shù)（Quad Tree）的數(shù)據(jù)結(jié)構(gòu),、待處理的數(shù)據(jù)量和計(jì)算量都非常大的特點(diǎn)，本文提出了一種在多核計(jì)算機(jī)上基于四叉樹(shù)劃分的并行模型簡(jiǎn)化算法,，對(duì)三維地形系統(tǒng)進(jìn)行優(yōu)化,。
1 多核并行程序設(shè)計(jì)
    多核并行計(jì)算技術(shù)是當(dāng)前計(jì)算機(jī)領(lǐng)域的研究熱點(diǎn)，在未來(lái)數(shù)年內(nèi),，隨著芯片內(nèi)核數(shù)量持續(xù)增長(zhǎng),，多核計(jì)算將成為一種廣泛普及的計(jì)算模式[1]。要想真正獲得多核處理器帶來(lái)的高效率,，軟件的發(fā)展必須跟上硬件的步伐,，而當(dāng)前多核處理器軟件總體滯后于硬件。多核處理器為實(shí)施計(jì)算任務(wù)的細(xì)粒度并行機(jī)制提供了必要的硬件基礎(chǔ),，只有在算法設(shè)計(jì)及軟件開(kāi)發(fā)能夠充分利用多核處理器的特性時(shí),，其優(yōu)勢(shì)才能真正體現(xiàn)出來(lái)。并行計(jì)算是指同時(shí)對(duì)多個(gè)任務(wù)或多條指令,，或多個(gè)數(shù)據(jù)項(xiàng)進(jìn)行處理[2],。目前適應(yīng)多核處理器并行算法的可行的解決方案是多線(xiàn)程化計(jì)算任務(wù)，并使計(jì)算負(fù)載能盡量均衡地分配到各個(gè)內(nèi)核上,。而計(jì)算任務(wù)的線(xiàn)程化存在的兩個(gè)難點(diǎn)是尋找任務(wù)中可并行計(jì)算成分與線(xiàn)程化工具的選擇,。
    OpenMP為共享地址空間的并行計(jì)算提供支持，具有使用簡(jiǎn)單的特點(diǎn),。它由一組小型的編譯器命令集組成,，包括一套編譯指令和一個(gè)用來(lái)支持它的函數(shù)庫(kù)，對(duì)于同步共享變量,、合理分配負(fù)載等任務(wù),，都提供了有效支持，具有簡(jiǎn)單通用,、開(kāi)發(fā)快速的特點(diǎn),。Intel Parallel Amplifier是Intel新推出的性能測(cè)試工具，使用Intel Parallel Amplifier可以簡(jiǎn)單快速找到多核性能瓶頸,。生成應(yīng)用程序后,，用Parallel Amplifier可對(duì)多種類(lèi)型函數(shù)進(jìn)行分析,，收集不同類(lèi)型的性能數(shù)據(jù)，查看結(jié)果并深入觀察造成某個(gè)問(wèn)題的相關(guān)源代碼,。其中熱點(diǎn)分析功能可識(shí)別出最耗時(shí)的函數(shù)以及是否有效利用了所有處理器內(nèi)核,。

    LOD細(xì)節(jié)層次是指對(duì)同一場(chǎng)景或場(chǎng)景中的物體，使用具有不同細(xì)節(jié)的描述方法得到一組模型,，供繪制時(shí)選擇使用[3],。LOD層次細(xì)節(jié)簡(jiǎn)化作為一種通用而有效的四叉樹(shù)算法，已在地理信息系統(tǒng),、虛擬現(xiàn)實(shí),、災(zāi)害仿真和戰(zhàn)場(chǎng)環(huán)境仿真等領(lǐng)域中有著重要的應(yīng)用。大規(guī)模地形LOD模型的預(yù)處理系統(tǒng)是一個(gè)完整,、穩(wěn)定的算法框架,，內(nèi)含的剖分、劃點(diǎn),、連線(xiàn)等操作都是一些并行性非常強(qiáng)的運(yùn)算過(guò)程,，滿(mǎn)足并行化的要求。在多核處理器計(jì)算環(huán)境中將這些操作進(jìn)行線(xiàn)程并行化,，可使LOD的運(yùn)行效率得到極大提高,，使系統(tǒng)資源得到充分利用。
2 LOD模型簡(jiǎn)化
    為了滿(mǎn)足大規(guī)模虛擬地形應(yīng)用在渲染速度和顯示分辨率等方面的要求,，應(yīng)采取一定的算法來(lái)簡(jiǎn)化地形數(shù)據(jù),。細(xì)節(jié)層次LOD是一種非常有效的控制場(chǎng)景復(fù)雜度的方法。該方法由Clark于1976年提出[4],，其基本思想是用具有多層次結(jié)構(gòu)要素的集合描述目標(biāo),。其基本原理是在不影響場(chǎng)景視覺(jué)效果的基礎(chǔ)上,，通過(guò)逐級(jí)簡(jiǎn)化景物的表面細(xì)節(jié)來(lái)減少場(chǎng)景的幾何復(fù)雜度,，以提高繪制算法的效率。當(dāng)物體覆蓋較小區(qū)域時(shí),，可以使用該物體描述較粗的模型并給出一個(gè)用于可見(jiàn)面判斷算法的幾何層次模型,，以便對(duì)復(fù)雜場(chǎng)景進(jìn)行快速的繪制。在場(chǎng)景的動(dòng)態(tài)顯示中,，當(dāng)視點(diǎn)距離某一物體很近時(shí),，它的圖像在屏幕上占據(jù)較多的像素，而當(dāng)視點(diǎn)距離它很遠(yuǎn)時(shí),，圖像在屏幕上占據(jù)很少的像素,，甚至是一個(gè)像素。在這種情況下用大量的三角形網(wǎng)格去精確地表示物體已經(jīng)沒(méi)有必要,，可以適當(dāng)合并一些三角形,，而不損失畫(huà)面的視覺(jué)效果,。這樣既保證場(chǎng)景的視覺(jué)效果，又能提高場(chǎng)景的繪制幀速,，改善系統(tǒng)的實(shí)時(shí)性,。
    LOD建模是采用一定的算法思想將原有的網(wǎng)格地形數(shù)據(jù)重組，得到一種更加便于實(shí)時(shí)繪制使用的數(shù)據(jù)結(jié)構(gòu),。本文所用到的LOD細(xì)節(jié)層次模型采用四叉樹(shù)的數(shù)據(jù)結(jié)構(gòu),，逐級(jí)劃分四叉樹(shù)直到某一種條件得到滿(mǎn)足為止。在用來(lái)描述地形的數(shù)據(jù)結(jié)構(gòu)中,，四叉樹(shù)非常有效,，它的每個(gè)節(jié)點(diǎn)（除葉子節(jié)點(diǎn)外）都有4個(gè)子節(jié)點(diǎn)，這4個(gè)子節(jié)點(diǎn)平均地劃分它們的父節(jié)點(diǎn)所占據(jù)的區(qū)域,，依次類(lèi)推,，直到葉子節(jié)點(diǎn)[5]。葉子節(jié)點(diǎn)是渲染和貼圖的最小單位,。分割的深度越大,，得到的分辨率就會(huì)越高，即分割深度每提高一層,，采樣的密度便提高一倍[6],。本文實(shí)驗(yàn)程序選用的四叉樹(shù)的深度為8，即采樣的密度為256×256個(gè)網(wǎng)格空間,，算法空間剖分如圖1所示,。圖中每一個(gè)正方形為四叉樹(shù)的一個(gè)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)保存了一定區(qū)域的信息,，包括經(jīng)緯度,、中心點(diǎn)的高度、邊節(jié)點(diǎn)的高度等,。

3 LOD多線(xiàn)程并行模型生成
3.1 四叉樹(shù)的構(gòu)建
    在利用四叉樹(shù)方法進(jìn)行LOD建模的過(guò)程中,，其關(guān)鍵就在于怎樣對(duì)原有的網(wǎng)格數(shù)據(jù)進(jìn)行四叉樹(shù)分層。四叉樹(shù)分層方法是從整個(gè)完整的地形出發(fā),，遞歸地把地形不斷地分割成相等的四個(gè)區(qū)域,，分割的深度越大，則得到的分辨率越高,。在進(jìn)行四叉樹(shù)分層的過(guò)程中,，由于四叉樹(shù)分層是針對(duì)(2n+1)×(2n+1)的規(guī)則網(wǎng)格而言的，數(shù)據(jù)格式應(yīng)盡量滿(mǎn)足規(guī)則網(wǎng)格的要求,，即網(wǎng)格數(shù)據(jù)必須是間隔均勻的正方形區(qū)域,。如果網(wǎng)格數(shù)據(jù)的大小不滿(mǎn)足該條件，則需要擴(kuò)展其幾何圖形,，擴(kuò)展部分的像素用空值填充,。其次在四叉樹(shù)分層過(guò)程中,，還必須滿(mǎn)足四叉樹(shù)中相鄰的兩個(gè)節(jié)點(diǎn)的層次最大不能相差1，否則在LOD模型連續(xù)拼接的地方就會(huì)出現(xiàn)裂縫,。其基本思路是先把地形一分為四,，用遞歸的方法對(duì)每個(gè)網(wǎng)格渲染。對(duì)每個(gè)網(wǎng)格,，如果達(dá)到最高精度,，則退出，如果不在視野內(nèi)也退出,；再對(duì)符合條件的網(wǎng)格遞歸下去,。本文實(shí)驗(yàn)利用OpenGL實(shí)現(xiàn)的地形場(chǎng)景渲染效果如圖2所示，對(duì)應(yīng)的地形網(wǎng)格模型如圖3所示,。

3.2 模型生成并行化
    OpenMP應(yīng)用程序接口是針對(duì)共享內(nèi)存多處理器體系結(jié)構(gòu)的可移植并行編程模型,，能夠支持并行計(jì)算時(shí)對(duì)線(xiàn)程和變量的靈活設(shè)置和控制。OpenMP經(jīng)常用于循環(huán)層并行,，但它同樣支持函數(shù)層并行,，在并行繪制系統(tǒng)中存在一些函數(shù)調(diào)用，可使用OpenMP提供的sections子句進(jìn)行函數(shù)級(jí)并行化,，前提是并行的函數(shù)之間無(wú)依賴(lài)性,。
    LOD并行模型簡(jiǎn)化算法需要考慮的因素主要是模型的剖分。對(duì)模型進(jìn)行適當(dāng)?shù)钠史?，從而?shí)現(xiàn)各模型分塊的并行簡(jiǎn)化,、任務(wù)分配與負(fù)載平衡，合理的任務(wù)分配能充分發(fā)揮并行計(jì)算的優(yōu)勢(shì),。為了使簡(jiǎn)化后的模型在LOD顯示時(shí)方便地調(diào)用,，直接應(yīng)用四叉樹(shù)對(duì)模型進(jìn)行并行剖分成為一種選擇。本文采用多線(xiàn)程的方法在初始化階段將地形模型進(jìn)行剖分,，四叉樹(shù)每個(gè)葉子節(jié)點(diǎn)所對(duì)應(yīng)的分塊內(nèi)的模型即為一個(gè)元任務(wù)塊,。每個(gè)四叉樹(shù)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)任務(wù)塊，由主節(jié)點(diǎn)按照任務(wù)分配策略將一個(gè)個(gè)元任務(wù)塊發(fā)送給子節(jié)點(diǎn)進(jìn)行并行簡(jiǎn)化,。實(shí)驗(yàn)環(huán)境選用的是四核計(jì)算機(jī),，且采用四叉樹(shù)結(jié)構(gòu)對(duì)原始模型進(jìn)行平均剖分；根據(jù)線(xiàn)程數(shù)等于CPU核數(shù)時(shí)性能最好原則,，設(shè)定為4線(xiàn)程。在四叉樹(shù)第一層剖分時(shí)把原任務(wù)塊平均分成四個(gè)子塊,，分別獨(dú)立地在四個(gè)工作區(qū)線(xiàn)程上完成指定深度的剖分任務(wù),，即把整個(gè)地形的工作量分配到四個(gè)處理核上同時(shí)工作。
3.3 OpenMP分塊設(shè)置過(guò)程
    在并行構(gòu)造中,，可以設(shè)置條件決定是否對(duì)可并行區(qū)域中的代碼塊作并行,。OpenMP提供了if 子句來(lái)實(shí)現(xiàn)條件并行,。設(shè)置條件并行先給每個(gè)線(xiàn)程平均分配一個(gè)任務(wù)塊，把整個(gè)區(qū)域的地形平均地分成四塊工作區(qū),，再用if 子句把地形分成四個(gè)均等的任務(wù)塊,。sections和section命令是OpenMP里用來(lái)設(shè)置分區(qū)的一種方式，先用sections定義一個(gè)區(qū)塊,，然后用section將區(qū)塊劃分成幾個(gè)不同的段,，每段都并行執(zhí)行。在每一個(gè)并行區(qū)域中都會(huì)有一個(gè)隱含的同步屏障,，執(zhí)行此并行區(qū)域的線(xiàn)程組在執(zhí)行完本區(qū)域代碼之前需要同步并行區(qū)域的所有線(xiàn)程,。因此要充分考慮任務(wù)分塊的均衡，以免浪費(fèi)CPU資源,。并行劃分程序部分代碼如下：
    #pragma omp parallel sections  if(i==1) num_threads(4)
    //定義一個(gè)生成四叉樹(shù)的并行區(qū)域
        {
            #pragma omp section
            西北分區(qū)塊NORTH WEST（NW）
            #pragma omp section
            東北分區(qū)塊NORTH EAST（NE）
            #pragma omp section
            西南分區(qū)塊SOUTH WEST（SW）
            #pragma omp section
            東南分區(qū)塊SOUTH EAST（SE）
        }
4 實(shí)驗(yàn)結(jié)果
    實(shí)驗(yàn)環(huán)境：Intel(R)Core(TM) 2 Quad CPU Q9400 @
2.66 GHz(4 CPUs) ,，3.00 GB內(nèi)存； Microsoft Visual Studio 2008,，Intel Parallel Amplifier(并行放大器),，OpenGL圖形庫(kù)，DirectX應(yīng)用程序接口,。
    實(shí)驗(yàn)數(shù)據(jù)為256 bit×256 bit的地形高度圖,，以分析draw、draw_point,、setup_quadtree函數(shù)為例,，測(cè)出單線(xiàn)程、雙線(xiàn)程和四線(xiàn)程的運(yùn)行時(shí)間,。對(duì)優(yōu)化前后的結(jié)果進(jìn)行比較,，獲得加速比和CPU效率。函數(shù)運(yùn)行測(cè)試數(shù)據(jù)如表1所示,，分析比較結(jié)果如圖4所示,。

    從實(shí)驗(yàn)結(jié)果可以看出，四叉樹(shù)算法的場(chǎng)景渲染函數(shù)經(jīng)過(guò)多線(xiàn)程優(yōu)化后執(zhí)行時(shí)間有很大的改進(jìn),，性能得到了較大的提升,。總的來(lái)說(shuō),，系統(tǒng)不僅實(shí)現(xiàn)了高分辨率的顯示效果,，而且實(shí)現(xiàn)了渲染速度的顯著提高。將工作任務(wù)平均地分配到四個(gè)線(xiàn)程上,，加速比和CPU利用率都得到了改進(jìn),，也看出多線(xiàn)程程序設(shè)計(jì)對(duì)于大型三維場(chǎng)景創(chuàng)建來(lái)說(shuō)是加快運(yùn)行速度、提高效率的很好的方法,。
    本算法提高了三維地形場(chǎng)景渲染系統(tǒng)生成的速度,，實(shí)現(xiàn)了高真實(shí)度的三維地形場(chǎng)景的可視化和快速漫游,，并采用了OpenGL編程實(shí)現(xiàn)了這個(gè)算法。通過(guò)實(shí)驗(yàn)說(shuō)明了該方法充分利用了多核平臺(tái)的優(yōu)勢(shì),，有效提高了系統(tǒng)的性能,。在LOD技術(shù)中，多核平臺(tái)的應(yīng)用將越來(lái)越廣泛,，還有很多內(nèi)容需要進(jìn)一步研究,，例如物體表面屬性色彩、紋理等的統(tǒng)一處理,，多分辨率模型的管理,，視點(diǎn)和視區(qū)有關(guān)的LOD生成和繪制算法，模型近似誤差度量標(biāo)準(zhǔn)以及多分辨率模型簡(jiǎn)化的并行化研究等,，因此本文的方法具有廣闊的應(yīng)用前景,。
參考文獻(xiàn)
[1] 周偉明.多核計(jì)算與程序設(shè)計(jì)[M].武漢:華中科技大學(xué)出版社,2009.
[2] 張林波，遲學(xué)斌,莫?jiǎng)t堯,，等.并行計(jì)算導(dǎo)論[M].北京：清華大學(xué)出版社,2006.
[3] 宋雙柱,薛群,孫立鐫.SLOPE法線(xiàn)生成算法的LOD技術(shù)在地形渲染中的應(yīng)用[J].哈爾濱理工大學(xué)學(xué)報(bào),2009,10
(5):63-65.
[4] CLARK J H.Hierarchical geometric models for visible surface algorithms[J].Communications of the ACM,1976,19(10):547-554.
[5] 李勝,俊峰.超大規(guī)模地形場(chǎng)景的高性能漫游[J].軟件學(xué)報(bào), 2006,17(3):535-545.
[6] 王磊,，毛利民，李騫.基于LOD的三維地形可視化[J].計(jì)算機(jī)與信息技術(shù), 2007,，15（7）：39-41.