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

1、ReSearCh0nParallelC0mputingandFault7rolerantinVieWShedAnalysisAlgorithmN刪ingNomalUniVersityFortheAcademicDegreeofMasterofEngineeringBYKunYangSupervisedbyPro￡WanfengDouSchoolofComputerScienceandTeclulologyN刪ingNormalUniVe

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

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

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