可視域分析算法的并行化與容錯研究.pdf

1、ReSearCh0nParallelC0mputingandFault7rolerantinVieWShedAnalysisAlgorithmN刪ingNomalUniVersityFortheAcademicDegreeofMasterofEngineeringBYKunYangSupervisedbyPro￡WanfengDouSchoolofComputerScienceandTeclulologyN刪ingNormalUniVe

2、rsityApril2014摘要摘要地形數(shù)據(jù)規(guī)模的增加，數(shù)據(jù)分辨率的提高和數(shù)據(jù)復雜度的上升對數(shù)字地形分析算法形成了越來越嚴峻的挑戰(zhàn)?？梢曈蚍治鲎鳛閿?shù)字地形分析算法集的重要組成部分，其對計算系統(tǒng)的性能要求也越來越高。傳統(tǒng)的以單位時間內(nèi)處理指令數(shù)為衡量標準的串行計算系統(tǒng)已經(jīng)不能完全滿足目前的分析計算需求了，必須要使用并行計算的手段對其進行改造和處理。但是傳統(tǒng)的并行計算方法在提高地形分析的效率多集中在通用的粗粒度級別上，而細粒度級別上針對數(shù)字

3、地形分析算法特點的將并行體系架構與具體地學意義相結合的并行方法的研究還需要進一步發(fā)展和完善。首先，本文基于數(shù)字地形分析和并行計算技術，對可視域分析算法進行并行特征和數(shù)據(jù)依賴特征分析，提出可視域分析算法中數(shù)據(jù)的全局和局部數(shù)據(jù)依賴關系的概念，并對數(shù)據(jù)并行的一般策略進行探討，進而為數(shù)據(jù)劃分提供理論依據(jù)。其次，在等角劃分和等面積劃分的基礎上，本文提出一種基于計算窗口邊界的數(shù)據(jù)劃分的方法。該方法針對等角劃分中可能出現(xiàn)的視點隨機性影響并行效率的問題

4、，采用使用柵格擴展、填充的方法以及任務調(diào)度負載平衡的方法予以處理。再次，針對并行數(shù)字地形分析的數(shù)據(jù)密集型特點，本文提出一種面向并行可視域分析的檢錯方法，利用集群的計算加速能力對可視域分析計算過程進行冗余，并通過對計算結果的錯誤率統(tǒng)計實現(xiàn)了對錯誤的檢測，從而實現(xiàn)對由于諸如進程失效等原因所導致的計算結果錯誤的檢測。在此基礎之上，本文以并行檢錯為基礎，使用多副本技術實現(xiàn)了一種在并行結構體系下的地形分析容錯方法，為并行數(shù)字地形分析下常見的容錯問