An Improved Parallel Algorithm using GPU for Siting Observers on Terrain
Departamento de Informatica, Universidade Federal de Vicosa (UFV), Vicosa, MG, Brazil
16th International Conference on Enterprise Information Systems (ICEIS), 2014
@InProceedings{iceis-2014,
author={Guilherme C. Pena and Marcus V.A. Andrade and Salles V.G. Magalhaes and W. Randolph Franklin and Chaulio R. Ferreira},
title={An Improved Parallel Algorithm using {GPU} for Siting Observers on Terrain},
booktitle={16th International Conference on Enterprise Information Systems (ICEIS)},
year={2014},
month={27–30 April},
address={Lisbon},
note={url{http://www.iceis.org/Home.aspx}},
href={bibhrefpt{177-ICEIS2014-pena-site-gpu}{177-ICEIS2014-pena-site-gpu-talk.pdf}}
}
This paper presents an efficient method to determine a set of observers (that is, where to site them) such that a given percentage of a terrain is visually covered. Our method extends the method proposed in (Franklin, 2002) including a local search heuristic efficiently implemented using dynamic programming and GPU parallel programming. This local search strategy allows to achieve a higher coverage using the same number of observers as the original method and thus it is possible to obtain a given coverage using a smaller number of observers. It can be an important improvement since an observer can represent an expensive facility such as a telecommunication tower. The proposed method performance was compared with that of other methods and the tests showed that it can be more than 1200 times faster than the sequential implementation (with no use of dynamic programming and no GPU parallel programming) and, also, more than 20 times faster than a previous parallel method presented in (Magalhaes et al., 2011).
June 6, 2014 by hgpu
