1、軟件天地文章編號:1008-0570(2010)04-1-0210-03微計(jì)算機(jī)信息(測控自動(dòng)化)2010年第26卷第4-1期三維地形顯示中數(shù)據(jù)緩存與調(diào)度算法研究Datacachingandschedulingalgorithmin3-Dterrainvisualization(1.中國科學(xué)院對地觀測與數(shù)字地球科學(xué)中心;2.中國科學(xué)院研究生院)魯萌1,2劉建波楊進(jìn)LUMengLIUJian-boYANGJin摘要:存儲調(diào)度是大規(guī)模地形可視化算法的重要組成部分,但近年來對其研究較少。本文重點(diǎn)討論了可視化實(shí)現(xiàn)中比較常用的調(diào)度算法:系統(tǒng)調(diào)用和操作系統(tǒng)頁面置換算法,對其進(jìn)行了詳細(xì)的分析,指出兩種方法相

2、同的本質(zhì):都是依據(jù)程序執(zhí)行的過程中對內(nèi)存的局部訪問特點(diǎn)設(shè)計(jì)的。可視化過程對內(nèi)存的需求不同于程序執(zhí)行的局部性,地形瀏覽有其特殊性。根據(jù)地形瀏覽的特點(diǎn),本文提出了一種專門用于地形瀏覽的預(yù)取和替換相結(jié)合的存儲策略。并用兩個(gè)評價(jià)準(zhǔn)則驗(yàn)證了方法的有效性。關(guān)鍵詞:大規(guī)模地形可視化;預(yù)取;替換;存儲調(diào)度中圖分類號:TP311.132.3文獻(xiàn)標(biāo)識碼:A技術(shù)創(chuàng)新Abstract:Storageschedulingisprincipalforlargeterrainvisualizationalgorithm,butrecentlytheresearchisless.First,thisarticlefocuse

3、sonthemorecommonlyusedschedulingmethodinvisualrealization:SystemcallandPagesreplacementalgorithmofOperat-ingSystemandpointsoutthesamenatureofthetwomethodsthattheyarebasedonlocalaccesstomemoryintheprocedures.Therearedifferentdemandformemorybetweenterrainbrowseandcoderunning.Secondthearticlecontrivesa

4、kindofstoragestrate-gythatiscombinationofprefetchingandreplacement.Thenewmethodisdevotedtoterrainvisualization.Twoevaluationcriteriaver-ifiedtheeffectivenessofthemethod.Keywords:largeterrainvisualization;prefetch;replacement;storageschedule1引言大規(guī)模地形數(shù)據(jù)的顯示在游戲、地形仿真、虛擬現(xiàn)實(shí)中應(yīng)用廣泛,是當(dāng)前可視化研究的熱點(diǎn)之一。地形簡化和數(shù)據(jù)的離核調(diào)度是提

5、高顯示性能的重要方法。對于地形數(shù)據(jù)巨大的三角形數(shù)量,簡化算法使顯卡的繪制能力滿足顯示的需要;數(shù)據(jù)離核調(diào)度是通過地形數(shù)據(jù)存儲管理的預(yù)取和優(yōu)化的調(diào)度策略使地形顯存的存儲能力,從而提高三維數(shù)據(jù)顯數(shù)據(jù)的存儲不超出內(nèi)存、示性能,達(dá)到瀏覽平滑的目的。本文重點(diǎn)研究三維地形顯示時(shí)數(shù)據(jù)的存儲管理的預(yù)取與調(diào)度算法。在大規(guī)模三維地形數(shù)據(jù)顯示時(shí),結(jié)合LOD(LevelOfDetail)多分辨率模型、數(shù)據(jù)的金字塔分塊等技術(shù)實(shí)現(xiàn)大地形數(shù)據(jù)的out-of-core算法時(shí),提高數(shù)據(jù)在存儲介質(zhì)間的轉(zhuǎn)移性能(外存到主存,到顯存),以及設(shè)計(jì)內(nèi)、外存的高效調(diào)度算法是實(shí)現(xiàn)快速實(shí)時(shí)繪制的保證。本文首先對現(xiàn)有的預(yù)取、調(diào)度算法進(jìn)行分析比較,

6、深入分析了地形瀏覽對內(nèi)存訪問特點(diǎn)不同于程序執(zhí)行的局在數(shù)據(jù)分層分塊的基礎(chǔ)上,結(jié)合以前的算法,考慮到視點(diǎn)、部性。分配存儲的大小、金字塔塊大小等因素,提出了適用于大規(guī)模地形顯示的預(yù)取和調(diào)度算法.最后在LOD模型的基礎(chǔ)上,使用本文提出的數(shù)據(jù)緩存調(diào)度算法對大規(guī)模地形數(shù)據(jù)顯示性能進(jìn)行測試,并對測試結(jié)果給予分析。魯萌:在讀碩士研究生基金項(xiàng)目:基金申請人:劉建波;項(xiàng)目名稱:國家科技支撐計(jì)劃-國家空間數(shù)據(jù)獲取與應(yīng)用應(yīng)急協(xié)同體系和數(shù)據(jù)共享服務(wù)平臺-應(yīng)急空間數(shù)據(jù)分中心系統(tǒng);基金頒發(fā)部門:科學(xué)技術(shù)部2相關(guān)的研究在大規(guī)模地形顯示算法研究中,已經(jīng)使用了一些成熟的、簡單可行的存儲介質(zhì)之間的調(diào)度算法作為高效顯示的重要輔助詳細(xì)

7、研究,預(yù)取算法也很少被涉及。本部方法,但鮮有對其系統(tǒng)、分總結(jié)了兩大類被廣泛使用的調(diào)度方法和幾種預(yù)取策略。2.1數(shù)據(jù)塊的調(diào)度算法:2.1.1直接利用操作系統(tǒng)的系統(tǒng)調(diào)用MapViewOfFile(windows)/mmap(linux)這種系統(tǒng)調(diào)用方法是把硬盤上指定的文件和虛擬內(nèi)存地址空間中的一部分相關(guān)聯(lián),根據(jù)需要把外存上的頂點(diǎn)高程數(shù)組調(diào)入內(nèi)存。不同于一般的分層分塊調(diào)度,把需要的數(shù)據(jù)調(diào)入內(nèi)存、選擇替換塊等工作由操作系統(tǒng)實(shí)現(xiàn),從而利用對應(yīng)用透明的操作系統(tǒng)的分頁調(diào)度機(jī)制實(shí)現(xiàn)離核數(shù)據(jù)訪問。系統(tǒng)要做的只是根據(jù)簡化算法對頂點(diǎn)的訪問順序設(shè)計(jì)數(shù)據(jù)在緩存中的存放規(guī)則,保證訪問數(shù)據(jù)在緩存中的連貫性,滿足操作系統(tǒng)調(diào)度

8、所需的所以數(shù)據(jù)連貫數(shù)據(jù),使頂點(diǎn)的排列順序與訪問頂點(diǎn)的順序一致。在外存中的排列依賴于簡化算法對數(shù)據(jù)的遍歷方式,根據(jù)數(shù)據(jù)的遍歷方式組織數(shù)據(jù)的排列。這種方法的優(yōu)點(diǎn)是不需要考慮具體的調(diào)度算法,只需要一個(gè)系統(tǒng)調(diào)用命令,簡單易實(shí)現(xiàn),適用于各種簡化算法和各種不同的數(shù)據(jù)存放順序。但這種數(shù)據(jù)的存放順序只針對于簡化數(shù)據(jù)的順序,而沒有考慮到對未來將要訪問數(shù)據(jù)的預(yù)取。如果加入預(yù)取機(jī)制,數(shù)據(jù)的存放順序不僅要考慮簡化時(shí)訪問的順序,還要考慮對訪問數(shù)據(jù)的預(yù)取,這是不可行的。所以加入預(yù)取策略后,不能直接利用操作系統(tǒng)的調(diào)度策略,并不能有效地減少缺頁系統(tǒng)調(diào)用的次數(shù)。并且系統(tǒng)調(diào)用的實(shí)現(xiàn)前提是所有數(shù)據(jù)按序存放在外存中,沒有對數(shù)據(jù)分層分

9、塊,沒考慮在多分辨率三角形剖分框架現(xiàn)場總線技術(shù)應(yīng)用200例(2008bak52b05)-年郵局訂閱號軟件天地有的根據(jù)被繪制的幀序號和數(shù)據(jù)塊的精細(xì)層度決定被替換出的優(yōu)先級。綜合相關(guān)預(yù)取策略,由于瀏覽的不確定性,很少有替換和預(yù)取結(jié)合的算法。綜上所述,目前大量使用的替換算法都是基于操作系統(tǒng)中程序執(zhí)行的規(guī)律設(shè)計(jì)的,對內(nèi)存的訪問有局部性,也有重復(fù)性,而瀏覽顯示有其自身的特點(diǎn),雖然也有局部性,但對內(nèi)存的訪問變換頻率更大,范圍更廣。本文設(shè)計(jì)了一種適合于各種存儲環(huán)境的三維地形數(shù)據(jù)瀏覽的緩存預(yù)取和替換相結(jié)合的方法。中LOD的空間關(guān)系,并不適合于網(wǎng)絡(luò)傳輸、數(shù)據(jù)分散于其他更粗級別的存儲等情況。2.1.2各種基于分塊

10、機(jī)制的調(diào)度策略用于繪制的數(shù)據(jù)塊的調(diào)度策略類似于操作系統(tǒng)的頁面替換算法。由于地形繪制的特殊性,現(xiàn)在常用的替換算法對操作系統(tǒng)頁面替換算法進(jìn)行了改進(jìn)。下面列舉了繪制時(shí)幾種常用的地形數(shù)據(jù)塊調(diào)度策略:策略:在上一次繪制用到的數(shù)據(jù)塊有“最近未使用”很大可能在下一次繪制中也會用到。為每個(gè)數(shù)據(jù)塊設(shè)置一個(gè)標(biāo)“活動(dòng)”志,如果數(shù)據(jù)塊在當(dāng)前或上一次繪制中被用到,標(biāo)志設(shè)為,兩次都沒用到設(shè)為“不活動(dòng)”。把數(shù)據(jù)塊以數(shù)組的形式順序存放,替換時(shí)從數(shù)組頭開始查找第一個(gè)“不活動(dòng)”的數(shù)據(jù)塊。這種方法“抖動(dòng)”現(xiàn)象。由于每次替換的都是距雖然實(shí)現(xiàn)簡單,但容易產(chǎn)生3一種適用于多種存儲環(huán)境的三維地形快速瀏覽的緩存調(diào)度方法三維地形

11、顯示的整個(gè)過程可以分為數(shù)據(jù)裝載、三維紋理與頂點(diǎn)生成以及繪制三部分,各部分所耗費(fèi)的時(shí)間表現(xiàn)出極大地差異。由于三維地形顯示時(shí)三個(gè)不同過程耗費(fèi)時(shí)間存在數(shù)量級離數(shù)組頭最近的可用的數(shù)據(jù)塊,數(shù)組后面的可用的數(shù)據(jù)塊往往上的差別,因此通過適當(dāng)?shù)木彺媾c調(diào)度方法就可以顯著提高最很久不被替換,還可以進(jìn)一步改進(jìn),如記錄每次搜索到的位置,每終顯示性能。次從上一次的替換位置開始搜索。頂點(diǎn)塊和紋理塊一一對應(yīng)。分配的存儲空間要適中,分配的策略:這是近年來大規(guī)模地形繪制“最近最少使用”內(nèi)存空間越大,命中率越高,但替換時(shí)所需的搜索時(shí)間也就越中最常用的方法。認(rèn)為最近繪制中用到的數(shù)據(jù)塊有很大可能在長。太小就會出現(xiàn)“抖動(dòng)

12、”,根據(jù)當(dāng)前設(shè)備內(nèi)存大小和顯示效果要以后繪制中還會用到,以此來近似預(yù)測以后繪制的情況。LRU存儲空間分為繪制區(qū)域和預(yù)取區(qū)求,分配一個(gè)合適的存儲空間。策略是對FA策略的進(jìn)一步改進(jìn),不只記錄上一次繪制和當(dāng)前域兩部分,繪制區(qū)域存放當(dāng)前顯示窗口內(nèi)需要繪制的數(shù)據(jù)塊,當(dāng)繪制的情況,它記錄的是繪制過程中較多的次數(shù)的統(tǒng)計(jì)信息,所繪制區(qū)域沒有把存儲空間占滿時(shí),預(yù)取以后可能訪問到的數(shù)據(jù)以需要的數(shù)據(jù)結(jié)構(gòu)比FA復(fù)雜,用計(jì)數(shù)器或雙鏈表等方法都可塊放入剩余的空閑區(qū)域即預(yù)取區(qū)域。以實(shí)現(xiàn)。這種方法以前主要適用于對操作系統(tǒng)指令執(zhí)行的預(yù)測:繪制區(qū)域只存放當(dāng)前需要的數(shù)據(jù)塊,視點(diǎn)拉近,繪制需要更在前面幾條指令中使用頻繁的頁面很可能在

13、后面的幾條指令精細(xì)層次的數(shù)據(jù)塊,產(chǎn)生缺塊申請;視點(diǎn)拉遠(yuǎn),視野范圍變大,需中頻繁使用。但地形數(shù)據(jù)的訪問有其特殊性,下面的方法就是對要顯示距離視點(diǎn)較遠(yuǎn)的數(shù)據(jù)塊;視角改變和視點(diǎn)移動(dòng),顯示數(shù)據(jù)它的改進(jìn)。塊的范圍改變;這些情況下,如果所缺的數(shù)據(jù)塊在預(yù)取區(qū)域中,則“最近最少使用誤差優(yōu)先隊(duì)列”策略在方法+:LRU加入繪制區(qū)域的列表中;如果不在預(yù)取區(qū)域中,則需要向外部存的基礎(chǔ)上,對搜索到的所有最近最少使用的數(shù)據(jù)塊根據(jù)LOD細(xì)儲請求調(diào)入,獲取時(shí)間很長,影響顯示效率。節(jié)層次分類,粗粒度的LOD數(shù)據(jù)塊覆蓋的區(qū)域較廣,所以細(xì)粒3.1數(shù)據(jù)塊的預(yù)取策略度的LOD數(shù)據(jù)塊優(yōu)先被替換出去。由此可以衍生出對LRU的

14、根據(jù)各種可能出現(xiàn)的視點(diǎn)變換操作,采用如下預(yù)取策略:各種改進(jìn)方法。視角改變和視點(diǎn)移動(dòng)的情況,預(yù)取顯示范(1)考慮視點(diǎn)拉遠(yuǎn)、“工作集時(shí)鐘”策略在某一時(shí)間段內(nèi)訪問的數(shù)據(jù)+:,同時(shí)為了場景轉(zhuǎn)換圍四周邊緣外的數(shù)據(jù)塊,與邊緣處層次相同。塊的集合叫做工作集,在瀏覽中跟蹤工作集,并保證工作集的所平滑,預(yù)取繪制范圍外圍四周最粗級別的數(shù)據(jù)塊,粒度較粗,所占有數(shù)據(jù)塊都在內(nèi)存或顯存中,不被替換。這種思想加入時(shí)鐘算法空間較少,調(diào)入的優(yōu)先級較高。就是WSClock算法。記錄當(dāng)前繪制以前的N次繪制,如果數(shù)據(jù)(2)考慮視點(diǎn)拉近的情況,預(yù)取當(dāng)前顯示數(shù)據(jù)塊更精細(xì)級別塊至少有一次被用到,就認(rèn)為數(shù)據(jù)塊屬于當(dāng)前的工作集,

15、不能被的數(shù)據(jù)塊,會占用較大的空間,調(diào)入的優(yōu)先級最低。替換出去。這種方法比LRU還要苛刻。根據(jù)預(yù)取區(qū)域的大小,按照優(yōu)先級次序調(diào)入預(yù)取塊。改變視另外還有許多為操作系統(tǒng)設(shè)計(jì)的改進(jìn)的頁面替換算法,但點(diǎn)時(shí),繪制區(qū)域裝載完畢后,搜索替換策略選中的數(shù)據(jù)塊,替換優(yōu)這些算法都是根據(jù)操作系統(tǒng)的程序執(zhí)行的特點(diǎn)設(shè)計(jì)的,即認(rèn)為先級較高的預(yù)取塊,直至存儲空間裝滿。在進(jìn)程執(zhí)行的一段時(shí)間內(nèi),所需要的頁面變化很少,也就是訪問3.2數(shù)據(jù)塊的替換策略的局部性。但對于地形瀏覽來說,雖然也存在局部訪問的特點(diǎn),如圖1所示,每次改變視點(diǎn)時(shí),把內(nèi)存中的數(shù)據(jù)塊分為兩大但局部的范圍不同,并且沒有考慮到LOD、以及瀏覽的特點(diǎn),所類:在繪制和預(yù)取范

16、圍內(nèi)、不在繪制和預(yù)取范圍內(nèi)。首先把所要以以上通用算法對于地形瀏覽來說性能并不是最好。所以需要繪制的數(shù)據(jù)塊做標(biāo)記到繪制區(qū)域,需要從外存調(diào)入時(shí),根據(jù)替換根據(jù)這種應(yīng)用的特點(diǎn)設(shè)計(jì)適合于地形瀏覽的替換算法。策略,從“不在繪制和預(yù)取范圍內(nèi)”的數(shù)據(jù)塊中選取替換塊,如果2.2預(yù)取策略“不在繪制和預(yù)取范圍內(nèi)”的數(shù)據(jù)塊不存在,從“在預(yù)取范圍內(nèi)”數(shù)據(jù)塊的預(yù)取就是對瀏覽方式的預(yù)測,瀏覽具有隨機(jī)性、不的數(shù)據(jù)塊中選取。然后,在組織預(yù)取區(qū)域時(shí),如果還有“不在繪制可預(yù)測性,預(yù)測十分困難,也難于測試,只能考慮普遍性。把需要和預(yù)取范圍內(nèi)”的數(shù)據(jù)塊,檢索需要預(yù)取的數(shù)據(jù)塊是否已經(jīng)存駐留在內(nèi)存中的場景區(qū)域分為可見區(qū)域和可見區(qū)域擴(kuò)展。擴(kuò)

17、展在,如果不存在,再根據(jù)替換策略選取替換塊。區(qū)域考慮到瀏覽時(shí)上、下、左、右、前、后移動(dòng)以及旋轉(zhuǎn)。有的則考慮到LRU及其改進(jìn)方法評判依據(jù)的片面性,本文提出了把視景體的運(yùn)動(dòng)趨勢分為前進(jìn)、后退、左移、右移、左轉(zhuǎn)、右轉(zhuǎn),把一種選取替換塊的新方法,該方法使用四個(gè)影響因子預(yù)測未來一個(gè)囊括所有運(yùn)動(dòng)趨勢的規(guī)則等腰梯形范圍作為預(yù)可見區(qū)域,瀏覽的可能性,全面體現(xiàn)了地形繪制的特點(diǎn)。但沒有考慮到上一個(gè)方法中的前、后移動(dòng),即改變視點(diǎn)的遠(yuǎn)近。對每個(gè)載入存儲區(qū)域的數(shù)據(jù)塊設(shè)置四個(gè)參數(shù),分別是是訪PLC技術(shù)應(yīng)用200例：/年-211-技術(shù)創(chuàng)新軟件天地問次數(shù)、最近的訪問時(shí)間、與視點(diǎn)的距離、數(shù)據(jù)塊所屬的LOD層次,前三個(gè)參數(shù)每次繪

18、制時(shí)都要更新。選取替換塊時(shí),具體實(shí)現(xiàn)方法如下:“訪問次數(shù)”和“數(shù)據(jù)塊所屬的LOD層次”進(jìn)行1)分別依據(jù)從小到大排序,依據(jù)“當(dāng)前訪問時(shí)間與最近訪問時(shí)間的差”和“與視點(diǎn)的距離”進(jìn)行從大到小排序,記錄每次排序數(shù)據(jù)塊在序列中的位置(數(shù)值相同的記錄第一個(gè)位置),分別為L1,L2,L3,L4。2)用這四個(gè)數(shù)值定義一個(gè)重訪系數(shù)C。根據(jù)四個(gè)因素的重要程度分別給予的權(quán)重K1,K2,K3,K4,則,C越大再次訪問的可能性越大,可以試驗(yàn)不同的k。裝載繪制區(qū)域時(shí),每次選取重訪系數(shù)最小且不在繪制范圍內(nèi)數(shù)據(jù)塊的替換,直到當(dāng)前繪制的塊全部被載入。可以試驗(yàn)不同的權(quán)重找出命中率最高的組合。本文的試驗(yàn)采用了四個(gè)參數(shù)權(quán)重相同的重訪

19、系數(shù)計(jì)算方法。微計(jì)算機(jī)信息(測控自動(dòng)化)2010年第26卷第4-1期技術(shù)創(chuàng)新參考文獻(xiàn)1LindstromP,PascucciV.TerrainSimplificationimplified:AGeneralFrameworkforView-DependentOut-of-CoreVisualization.IEEETransactionsonVisualizationandComputerGraphics,2002.1-252LindstromP,PascucciV.Visualizationoflargeterrainsmadeeasy.ProceedingsofIEEEVisualizat

20、ion2001.SanDiego,California:IEEEPress,2001.363-3703R.W.CarrandJ.L.Hennessy.WSClock-asimpleandeffectivealgorithmforvirtualmemeorymanagement.Proceedingsof8thSymposiumonOperatingSystemsPrinciples,1981:87-954CignoniP,GanovelliF.Out-of-CoreVisualisationofVeryLargeLandscapeonCommodityGraphicsPlatforminICV

21、S2003,2003,LNCS2897:21-295李勝,季俊峰。超大規(guī)模地形場景的高性能漫游。軟件學(xué)報(bào),2006,17-3:535-5456魏曉平,彭曉明。基于OpenGL組件庫的飛行過程可視化仿真J。微計(jì)算機(jī)信息,2008,8-1:257-258作者簡介:魯萌(1983-),女(漢),山東人,中國科學(xué)院對地觀測與數(shù)字地球科學(xué)中心碩士研究生,研究方向:衛(wèi)星數(shù)據(jù)發(fā)布;楊進(jìn)(1975-),男(漢),北京人,中國科學(xué)院對地觀測與數(shù)字地球科學(xué)中心,副研究員,研究方向:遙感數(shù)據(jù)與信息的管理與發(fā)布技術(shù)。Biography:LUMeng(1983-),Female(Han),Shandong,GUCAS,

22、CEODE,Master,Major:thepublicationofremotesensingdata.(100086北京中國科學(xué)院對地觀測與數(shù)字地球科學(xué)中心)魯萌劉建波楊進(jìn)圖1存儲策略示意圖4實(shí)現(xiàn)及試驗(yàn)結(jié)果為了驗(yàn)證本文方法的正確性和有效性,分別對LRU算法和本文提出的算法進(jìn)行仿真測試。用改變視點(diǎn)或視角時(shí)數(shù)據(jù)塊緩存的命中率即待顯示的數(shù)據(jù)在緩存中的概率來檢驗(yàn)預(yù)取策略,用選取替換塊所需要的檢索時(shí)間來檢驗(yàn)替換算法。在測試時(shí),事先將顯示窗口移動(dòng)軌跡存儲在一個(gè)文本文件中。該文件中的移動(dòng)軌跡模擬用戶訪問數(shù)據(jù)時(shí)的上、下、左、右、前、后、改變視角、往復(fù)、跳躍與隨機(jī)操作等運(yùn)動(dòng)。LRU算法與本文提出的算法均按照

23、該文本規(guī)定的移動(dòng)軌跡進(jìn)行操作,這樣就保證試驗(yàn)結(jié)果的客觀性。試驗(yàn)結(jié)果如下(n為預(yù)分配存放數(shù)據(jù)塊的數(shù)量):表1LRU與多因子調(diào)度策略性能比較(100086北京中國科學(xué)院研究生院)魯萌(CenterforEarthObservationandDigitalEarth,TheChineseAcademyofSciences,Beijing,100086,China)LUMengLIUJian-boYANGJin(TheChineseAcademyofSciences,Beijing,100086,China)LUMeng通訊地址:(100086北京北京市海淀區(qū)北三環(huán)西路45號中國遙感衛(wèi)星地面站)魯萌(收稿日期:2009.04.17)(修稿日期:2009.07.