Accelerating of line of sight analysis algorithms with parallel programming

Download

index.pdf

Date

2017

Author

Yılmaz, Gökhan

Metadata

Show full item record

Item Usage Stats

170
views

78
downloads

Line of sight (LOS) analysis is a set of methods and algorithms to determine the visible points in a terrain with reference to a specific observer point. This analysis is used in simulations, Geographic Information System (GIS) applications and games. For this reason, it is important to have a capability to get results quickly and facilitate analysis in such a way that the interaction with the changing reference points is possible. Van Kreveld, R2 and R3 are the most frequently used algorithms in line of sight analysis. The purpose of this research is to develop parallel adaptations of these particular algorithms by making use of the capabilities of a modern Graphics Processing Unit (GPU) and to evaluate these adaptations in terms of performance and memory usage. By analyzing which algorithm is more suitable to be implemented on the GPU, the algorithm that will provide the most appropriate and quick solution to the probing problem can be determined. In this research, Van Kreveld's algorithm, which is basically a sequential algorithm, was developed partly in parallel, and the speed-up was 1.5x compared to the sequential version of the algorithm. Speed-up rates increase up to 10.5x for R2 and 160x for R3 algorithms, respectively. The results can be used to combine CPU / GPU approaches in order to perform hybrid or full parallelization of Van Kreveld’s Algorithm on the GPU. The results presented in the thesis will serve as a guide for the selection of the appropriate algorithm by evaluating the strengths and weaknesses of different algorithms.

Subject Keywords

Geographic information systems., Parallel programming (Computer science).

URI

http://etd.lib.metu.edu.tr/upload/12620986/index.pdf
https://hdl.handle.net/11511/26798

Collections

Graduate School of Informatics, Thesis

Suggestions

OpenMETU
Core

Acceleration of line of sight analysis algorithms with parallel programming Yılmaz, Gökhan; Sürer, Elif; Temizel, Alptekin (null; 2017-11-23) Line of sight (LOS) analysis is a set of methods and algorithms to determine the visible points in a terrain with reference to a specific observer point. This analysis is used in simulations, Geographic Information System (GIS) applications and games. For this reason, it is important to have a capability to get results quickly and facilitate analysis in such a way that the interaction with the changing reference points is possible. Van Kreveld, R2 and R3 are the most frequently used algorithms in line of si...
ASSESSMENT OF RPIM SHAPE PARAMETERS FOR SOLUTION ACCURACY OF 2D GEOMETRICALLY NONLINEAR PROBLEMS BOZKURT, ÖMER YAVUZ; KANBER, BAHATTİN; Aşık, Mehmet Zülfü (World Scientific Pub Co Pte Lt, 2013-06-01) This study discussed the effects of shape parameters on the radial point interpolation method (RPIM) accuracy in 2D geometrically nonlinear problems. Four finite deformation problems with compressible Neo-Hookean material are numerically solved with the RPIM algorithm using the multi-quadric (MQ) radial basis function. Both regular and irregular node distributions are used. Their displacements and Cauchy stresses are compared for different values of shape parameters and monomial basis. It is found that the ...
Parallel implementation of the accelerated BEM approach for EMSI of the human brain ATASEVEN, YOLDAŞ; Akalin-Acar, Z.; Acar, C. E.; Gençer, Nevzat Güneri (Springer Science and Business Media LLC, 2008-07-01) Boundary element method (BEM) is one of the numerical methods which is commonly used to solve the forward problem (FP) of electro-magnetic source imaging with realistic head geometries. Application of BEM generates large systems of linear equations with dense matrices. Generation and solution of these matrix equations are time and memory consuming. This study presents a relatively cheap and effective solution for parallel implementation of the BEM to reduce the processing times to clinically acceptable valu...
Classification of remotely sensed data by using 2D local discriminant bases Tekinay, Çağrı; Çetin, Yasemin; Department of Information Systems (2009) In this thesis, 2D Local Discriminant Bases (LDB) algorithm is used to 2D search structure to classify remotely sensed data. 2D Linear Discriminant Analysis (LDA) method is converted into an M-ary classifier by combining majority voting principle and linear distance parameters. The feature extraction algorithm extracts the relevant features by removing the irrelevant ones and/or combining the ones which do not represent supplemental information on their own. The algorithm is implemented on a remotely sensed...
Development of free/libre and open source spatial data analysis system fully coupled with geographic information system Kepoğlu, Volkan Osman; Düzgün, H. Şebnem; Department of Geodetic and Geographical Information Technologies (2011) Spatial Data Analysis (SDA) is relatively narrower and constitutes one of the areas of Spatial Analysis. Geographic Information System (GIS) offers a potentially valuable platform for supporting SDA techniques. Integration of SDA with GIS helps SDA to benefit from the data input, storage, retrieval, data manipulation and display capabilities of GIS. Also, GIS can benefit from SDA techniques in which the integration of these techniques can increase the analysis capabilities of GIS. This integration serves fo...

Citation Formats

G. Yılmaz, “Accelerating of line of sight analysis algorithms with parallel programming,” M.S. - Master of Science, Middle East Technical University, 2017.