(1.鄭州大學(xué) 水利與環(huán)境學(xué)院， 鄭州 450001; 2.華北水利水電學(xué)院 巖土工程系， 鄭州 450011)

摘 要：

應(yīng)用緩存技術(shù)將中央處理器將要運行的數(shù)據(jù)文件直接調(diào)入緩沖存儲器，以提高中央處理器的有效資源利用率和大場景流域模型繪制的實時交互性?；诖四康模接懥烁鞣N存儲器之間的差異性以及當(dāng)前實時交互繪制大場景流域模型所存在的問題，分析了實現(xiàn)緩存技術(shù)的方法，并給出了主要的算法步驟，結(jié)果表明：應(yīng)用緩存技術(shù)不僅能夠充分利用中央處理器的有效資源，而且可以提高大場景流域模型繪制的實時交互性，使繪制大場景流域模型更加流暢、更加連貫。

關(guān)鍵詞：模型； 緩存技術(shù)； 存儲器； 實時交互繪制

中圖分類號：TP391文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2009)04-1297-02

Visualization oflarge scene watershed model in real-time and interactive manner based on cache technique

LI Xiao-gen1，2， WANG Zong-min1， HUANG Zhi-quan2

(1.School of Water Conservancy Environment， Zhengzhou University， Zhengzhou 450001， China; 2.Dept. of Geotechnical Engineering， North China Institute of Water Conservancy Hydroelectric Power， Zhengzhou 450011， China)

Abstract:

To apply cache technology fold the data files which were going to be operated in CPU to the buffer memory directly， which could improve the resources utilization rate of the CPU effectively and the visualizing of the large scene watershed model in real-time interactive manner. Based on this goal， firstly discussed the differences between all kinds of memory as well as the current questions of the visualizing the large scene watershed model in real-timeinteractive manner ， and then analyzed the methods to achieve cache technology， and presented the main algorithm steps to fold the data files. The results show that: the cache technique can not only take full advantage of the CPU resources effectively， but also improve the visualizing of the large scene watershed model in real-time interactive manner， which can make the visualizing of the large scene watrshed model more smooth and more coherent.

Key words：model; cache technique; memory; visualizing in real-time and interactive manner

計算機的存儲器可以分為輔助存儲器、內(nèi)存儲器、緩沖存儲器、寄存儲器。這四種存儲器中容量依次減小、運行速度依次增大，價格也由低到高。關(guān)于計算機的基本運行原理是：當(dāng)中央處理器（CPU）開始工作時首先讀取外存儲器中的數(shù)據(jù)文件，將需要運行的數(shù)據(jù)文件調(diào)入到內(nèi)存儲器中供CPU調(diào)用。由于外存儲器的磁盤片是機械式高速轉(zhuǎn)動，遠(yuǎn)遠(yuǎn)低于電流的速度，外存儲器的運行速度遠(yuǎn)遠(yuǎn)小于CPU的運行速度；而內(nèi)存儲器讀取數(shù)據(jù)是依靠其內(nèi)部電容的充放電來完成數(shù)據(jù)文件的讀取，其運行速度比CPU的運行速度也低近10倍以上。由于I/O向主存請求的級別高于CPU訪存，這就出現(xiàn)了CPU等待I/O訪存的現(xiàn)象，致使CPU空等一段時間，甚至可能等待幾個主存周期，從而降低了CPU的工作效率，極大地浪費了CPU的有效資源[1]。但是緩沖存儲器運行的速度要遠(yuǎn)遠(yuǎn)高于內(nèi)存儲器，如果將CPU將要運行的數(shù)據(jù)直接調(diào)入緩沖存儲器，可以極大地提高CPU的有效資源利用率。這里所說的是CPU的高速緩存，它采用一種特殊的算法，可以預(yù)知CPU下一步要運行的程序，所以它會提前將一些急需要的數(shù)據(jù)文件保存在高速緩存中，如果命中率高，計算機的運行速度就會很快。相對于沒有緩存的CPU，帶有緩存的CPU運行速度要快得多，尤其是帶有2級緩存的CPU。當(dāng)然，由于1級和2級緩存涉及到復(fù)雜的技術(shù)，擁有1級和2級緩存的CPU也要昂貴得多[2]。

1 緩存技術(shù)

高速緩存是一種特殊的存儲器子系統(tǒng)，其中復(fù)制了頻繁使用的數(shù)據(jù)，以利于CPU快速訪問。存儲器的高速緩沖存儲器存儲了頻繁訪問的隨機存取存儲器（RAM）位置的內(nèi)容及這些數(shù)據(jù)項的存儲地址。當(dāng)處理器引用存儲器中的某地址時，高速緩沖存儲器便檢查是否存有該地址。如果存有該地址，則將數(shù)據(jù)返回處理器；如果沒有保存該地址，則進(jìn)行常規(guī)的存儲器訪問。此時，CPU在訪問時就會增加I／O的讀取次數(shù)，出現(xiàn)CPU等待I/O訪存的現(xiàn)象，浪費了CPU的有效資源。因為高速緩沖存儲器運行速度比主RAM 存儲器速度快得多，如果應(yīng)用特定的緩存技術(shù)算法將一些急需要的數(shù)據(jù)文件保存在高速緩存中，提高中央處理器引用存儲器中某地址的命中率，那么就會極大地提高計算機的運行速度。

2 實時交互繪制大場景模型存在的問題

在大規(guī)模的三維流域模型場景中，為了實現(xiàn)實時交互的漫游功能，此功能雖為基本功能，但是系統(tǒng)需要根據(jù)用戶視點的移動情況從后臺數(shù)據(jù)庫中進(jìn)行動態(tài)數(shù)據(jù)調(diào)度。由于大場景流域模型數(shù)據(jù)量龐大，這樣就會帶來一系列的問題。例如當(dāng)需要的數(shù)據(jù)已經(jīng)進(jìn)入到視野范圍內(nèi)時再啟動數(shù)據(jù)調(diào)度機制，由于數(shù)據(jù)量龐大必然會導(dǎo)致繪制過程的不流暢、不連貫等現(xiàn)象，不能夠?qū)崿F(xiàn)實時交互性的目的。必須考慮如何將需要讀取的數(shù)據(jù)提前讀入內(nèi)存儲器，如果將需要讀取的數(shù)據(jù)提前讀入緩沖存儲器，那么繪制的效果將會更好[3]。如何確定哪些數(shù)據(jù)是將要運行的數(shù)據(jù)文件，這將涉及到數(shù)據(jù)的預(yù)存取問題[4]。關(guān)于數(shù)據(jù)的預(yù)存取是根據(jù)用戶視點在此前一段時間內(nèi)的移動規(guī)律，提前判定下一步用戶視點有可能到達(dá)的坐標(biāo)位置以及在該位置的瀏覽方向，將需要進(jìn)行繪制的大場景流域模型數(shù)據(jù)文件提前讀取到內(nèi)存儲器中，以提高大場景流域模型繪制的流暢性、連貫性；如果將需要進(jìn)行繪制的大場景流域模型數(shù)據(jù)文件提前讀取到緩沖存儲器中，則大場景流域模型繪制的流暢性和連貫性效果會更好[5]，這也是下文將要討論的重點問題。

由于大場景流域模型由原始數(shù)據(jù)DEM繪制而成，而DEM數(shù)據(jù)是典型的grid數(shù)據(jù)。由于最小的grid邊長是定值，進(jìn)行大場景流域模型數(shù)據(jù)分割時就非常簡單了，只要確定原始坐標(biāo)和grid的數(shù)量即可完成分割[6]。當(dāng)完成分割后對每個DEM分割數(shù)據(jù)塊進(jìn)行排列編碼，以方便日后準(zhǔn)確確定某一個數(shù)據(jù)塊的位置以及該數(shù)據(jù)塊與其他數(shù)據(jù)塊之間的位置關(guān)系，這樣根據(jù)實時監(jiān)測的用戶視點參數(shù)和用戶視點的運動規(guī)律就可以比較容易地判定將要進(jìn)入用戶視野的DEM數(shù)據(jù)塊了?？梢赃M(jìn)一步應(yīng)用相應(yīng)的算法將已經(jīng)判定的數(shù)據(jù)塊讀取到緩沖存儲器中[7]。

當(dāng)然其中還有很多問題需要解決，如用戶視點突然改變方向沒有按照正常的運動規(guī)律移動等非正?，F(xiàn)象[8]。在此假定已經(jīng)解決了大場景流域模型的預(yù)存取問題，下一步主要解決將需要讀取的DEM數(shù)據(jù)塊應(yīng)用相應(yīng)的算法調(diào)入到緩沖存儲器中，進(jìn)一步提高大場景模型繪制的實時交互性。

3 應(yīng)用緩存技術(shù)將大場景流域模型讀取到緩沖存儲器中的算法實現(xiàn)

下面僅給出了主要的算法步驟:

空閑表鏈表和散列隊列鏈表都為全局變量：

空閑鏈表頭指針：struct buffer *emp_link;

散列隊列頭指針數(shù)組：struct buffer *buf_link[M];

getblk(int num):緩沖區(qū)分配算法，為所申請的塊號分配緩沖區(qū)；

brelse(int num):釋放緩沖區(qū)。

int getblk(int num) //分配緩沖區(qū)算法

{

struct buffer *p;

struct buffer *temp;

while(1)

{

if(exist_buf(num)==1)

{

p=find_buf(num);

if(p->lock==1)

{

printf(\"\\The block is busy now! Please try again later.\\");

//print_emp();

//print_buf();

return 0;

}

釋放緩沖區(qū)算法

void brelse(int num) //釋放緩沖區(qū)算法

{

struct buffer *p;

p=find_buf(num);

add_emp(p);

p->lock=0;

}

4 結(jié)果分析

經(jīng)過實際運行和測試，計算機硬件配置為： Intel(R) Xeon(TM)CPU 3.0GHz，內(nèi)存2.0GB，顯示卡NVIDIA QUadro FX 3400的圖形工作站（Dell Workstation 670）上運行大場景流域模型（圖1）。由于應(yīng)用了緩存技術(shù)，CPU在讀取高速緩沖存儲器的數(shù)據(jù)時，命中率提高，減少了I／O的讀取次數(shù)，加快了計算機的運行速度。經(jīng)過八次運行測試，所需的平均時間為9.975 s（表1）；在系統(tǒng)研制過程中如果沒有應(yīng)用特定的緩存技術(shù)算法，而計算機按照正常狀態(tài)運行，CPU在讀取高速緩沖存儲器的數(shù)據(jù)時，讀取數(shù)據(jù)的命中率低，增加了I／O的讀取次數(shù)，經(jīng)過八次運行測試，所需要的平均時間為16.887 5 s（表1）。兩種狀態(tài)下，運行情況的比較在圖2中可以直觀地顯示出來，應(yīng)用緩存技術(shù)的系統(tǒng)運行時間遠(yuǎn)遠(yuǎn)小于無緩存技術(shù)的系統(tǒng)運行時間。



5 結(jié)束語

由以上圖表數(shù)據(jù)可以得出如下結(jié)論：

a)應(yīng)用緩存技術(shù)運行大場景流域模型經(jīng)過八次運行測試，平均耗費時間9.975 s；沒有應(yīng)用緩存技術(shù)運行大場景流域模型經(jīng)過八次運行測試，平均耗費時間16.887 5 s，平均耗費時間節(jié)省約7 s，相對節(jié)約時間為（16.8875-9.975）/16.8875×100%≈40.93%。

b)緩沖存儲器的運行速度遠(yuǎn)遠(yuǎn)高于內(nèi)存儲器的運行速度，利用緩沖存儲器的這一優(yōu)點應(yīng)用緩存技術(shù)可以提高計算機的運行速度。

c)應(yīng)用緩存技術(shù)將中央處理器將要運行的大場景流域模型數(shù)據(jù)文件直接讀取到緩沖存儲器中，極大地提高了CPU從緩沖存儲器讀取數(shù)據(jù)的命中率，充分利用了中央處理器的有效資源，提高了大場景流域模型繪制的實時交互性。

參考文獻(xiàn)：

[1]唐朔飛. 計算機組成原理[M].北京:高等教育出版社，2006.

[2]李小根，王宗敏，黃志全.基于內(nèi)存影射文件技術(shù)快速繪制大場景流域模型[J].計算機應(yīng)用研究，2009，26(2):527-528.

[3]謝強，于雅麗，丁秋林. 基于對象池和數(shù)據(jù)緩存技術(shù)的Web-OLAP系統(tǒng)[J]. 應(yīng)用科學(xué)學(xué)報，2007，25(2)：161-165.

[4]MADEIRA H，COSTA J，VIEIRA M. The OLAP and data warehousing approaches for analysis and sharing of results from dependability evaluation experiments[C]//Proc of International Conference on Dependable Systems and Networks. [S.l.]: IEEE Press， 2003:86-91.

[5]楊慶躍，楊冬青，唐世渭，等. Web 環(huán)境下OLAP對象池的研究與設(shè)計[J].計算機應(yīng)用，2005，25（1）：52-55.

[6]SATTLE K，GEIST I，SCHALLEHN E. Concept-based querying in mediator systems[J].The VLDB Journal， 2005(14):97-111.

[7]NI Jian， TSANG D H K， YEUNG I S H， et al. Hierarchical content routing in large-scale multimedia content delivery network[C]//Proc of IEEE International Conference on Communications. 2003:854-859.

[8]LIU Yan， GORTON L， LIU A，et al. Evaluating the scalability of enterprise JavaBeans technology[C]//Proc of the 9th Asia-Paclific Software Engineering Conference. Washington DC:IEEE Computer Society， 2002:74.