Study Of Granularity Model And Faulty Tolerant Scheduling Mechanism Based On Parallel Analysis Of Digital Terrain

Digital Terrain Analysis (DTA) is one of important functions of the Geographic Information System software. At present, requirements for large-scale and high efficient DTA by many application fields are growing day by day, which is conflicted with low utilization ratio of computing resources. Existing methods for DTA have many difficulties in coping with massive Digital Elevation Model (DEM) data rapidly and efficiently, and even impossible to do that. Parallel computing provides new method for solving this problem. Traditional technologies of High Performance Computing (HPC) promote the efficiency in dealing with DEM data in part, but with the appearance of new technologies such as parallel computing cluster, multi-core processors and so on, new architecture oriented DTA algorithm is necessary to develop and perfect.First of all, in view of data and task intensive characteristics of parallel DTA and the characteristics of parallel computing platform, a uniform granularity model of data, task and structure is brought up to quantify. Dependence graph of granularity relationship is constructed in view of data and task splitting.Secondly, based on the general granularity model, data granularity model supporting DEM data-splitting regularly is constructed regards of the characteristics of grid DEM data. The attributes and relations of data granularity are defined in detail. Data granularity is quantized by attributes so as to put forward the atom data granularity based on page scheduling mechanism and poly data granularity upon storage strategy of quad tree. In favor of DEM data edge matching is assured by redundant column and row, as well as corresponding calculating method and partition methods are given. Based on atom data granularity and poly data granularity, along with structure granularity, data distribution method facing PDTA is provided.Thirdly, to fully take advantage of multi-core cluster systems, task parallel can better improve overall parallel processing efficiency. The63terrain factors in the DTA are analyzed carefully so as to specify the task granularity model realizing task and data decomposition of terrain analysis algorithms, which is quantized by attributes and relations. In order to clarify parallel relation, theory of Petri nets is introduced to construct parallel relation graph based on data and tasks parallel, and corresponding scheduling algorithms are proposed which provide theoretical basis for parallel scheduling. At last, to ensure large-scale parallel system operating stably, and the accuracy of the results, a two-level scheduling mechanism is proposed in view of data distribution and task scheduling. Parallel fault-tolerant scheduling algorithm based on redundancy mechanism is brought up to improve the reliability of the system.