Daniel Benedetti · W. Randolph Franklin

2014

Wenli Li, W. Randolph Franklin, Daniel N. Benedetti, and Salles V. G. de Magalhães. Parallel multiple observer siting on terrain. In 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2014). Dallas, Texas, USA, 4–7 Nov 2014.
[details] [full text] [poster]
Abstract
This paper presents the optimization and parallelization of the multiple observer siting program, originally developed by Franklin and Vogt. Siting is a compute-intensive application with a large amount of inherent parallelism. The advantage of parallelization is not only a faster program but also the ability to solve bigger problems. We have parallelized the program using two different techniques: OpenMP, using multi-core CPUs, and CUDA, using a general purpose graphics processing unit (GPGPU). Experiment results show that both techniques are very effective. Using the OpenMP program, we are able to site tens of thousands of observers on a 16385 × 16385 terrain in less than 2 minutes, on our workstation with two CPUs and one GPU. The CUDA program achieves the same in about 30 seconds.
BibTeX
```
@inproceedings{li-acmgis-2014,
    author = "Li, Wenli and Franklin, W. Randolph and Benedetti, Daniel N. and de Magalhães, Salles V. G.",
    title = "Parallel Multiple Observer Siting on Terrain",
    booktitle = "22nd {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems {(ACM SIGSPATIAL 2014)}",
    year = "2014",
    month = "4--7 Nov",
    href = "\bibhrefpp{182-acmgis2014-par-siting}{182-acmgis2014-par-siting-poster.pdf}",
    address = "Dallas, Texas, USA",
    customlinkposter = "https://wrfranklin.org/p/182-acmgis2014-par-siting-poster.pdf",
    mykey = "benedetti salles wenlili visviewshedsiting gpusiting parallelsiting parallel"
}
```
Guilherme Pena, Salles de Magalhães, Marcus Andrade, Randolph Franklin, Chaulio Ferreira, Wenli Li, and Daniel Benedetti. An efficient GPU multiple-observer siting method based on sparse-matrix multiplication. In 3rd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial) 2014. Dallas TX USA, 4 Nov 2014.
[details] [full text] [slides]
Abstract
This paper proposes an efficient parallel heuristic for siting observers on raster terrains. More specifically, the goal is to choose the smallest set of points on a terrain such that observers located in these points are able to visualize at least a given percentage of the terrain. This problem is NP-Hard and has several applications such as determining the best places to position (site) communication or monitoring towers on a terrain. Since siting observers is a massive operation, its solution requires a huge amount of processing time even to obtain an approximate solution using a heuristic. This is still more evident when processing high resolution terrains that have become available due to modern data acquiring technologies such as LIDAR and IFSAR. Our new implementation uses dynamic programming and CUDA to accelerate the swap local search heuristic, which was proposed in previous works. Also, to efficiently use the parallel computing resources of GPUs, we adapted some techniques previously developed for sparse-dense matrix multiplication. We compared this new method with previous parallel implementations and the new method is much more efficient than the previous ones. It can process much larger terrains (the older methods are restrictive about terrain size) and it is faster.
BibTeX
```
@inproceedings{bigspatial-2014,
    author = "Pena, Guilherme and de Magalhães, Salles and Andrade, Marcus and Franklin, Randolph and Ferreira, Chaulio and Li, Wenli and Benedetti, Daniel",
    title = "An efficient {GPU} multiple-observer siting method based on sparse-matrix multiplication",
    booktitle = "3rd {ACM SIGSPATIAL} International Workshop on Analytics for Big Geospatial Data (BigSpatial) 2014",
    year = "2014",
    month = "4 Nov",
    address = "Dallas TX USA",
    href = "\bibhrefpt{191-bigspatial-sparse-siting-2014}{191-bigspatial-sparse-siting-2014-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/191-bigspatial-sparse-siting-2014-talk.pdf",
    mykey = "visviewshedsiting benedetti marcus wenlili salles parallel"
}
```

2013

Wenli Li, W. Randolph Franklin, and Daniel Benedetti. Parallel multiple observer siting on terrain. In 23rd Fall Workshop on Computational Geometry. City College, New York City, USA, 25–26 Oct 2013. (extended abstract).
[details] [full text] [slides]

Abstract

Multiple observer siting has much inherent parallelism. We have parallelized the siting package using OpenMP and CUDA. The results show that both methods are effective for parallelizing the program. Although the overall speedups of the two methods are similar, which are about 16, the speedups of the constituent parts of the program are quite different.

BibTeX

@inproceedings{li-fwcg-2013,
    author = "Li, Wenli and Franklin, W. Randolph and Benedetti, Daniel",
    title = "Parallel Multiple Observer Siting on Terrain",
    booktitle = "23rd Fall Workshop on Computational Geometry",
    year = "2013",
    month = "25--26 Oct",
    address = "City College, New York City, USA",
    note = "(extended abstract)",
    href = "\bibhrefpt{173-fwcg2013-li-parallel-siting}{173-fwcg2013-li-parallel-siting-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/173-fwcg2013-li-parallel-siting-talk.pdf",
    mykey = "benedetti wenlili parallelsiting gpusiting parallel"
}

Daniel Benedetti, W. Randolph Franklin, and Wenli Li. CUDA-accelerated ODETLAP: a parallel lossy compression implementation. In 23rd Fall Workshop on Computational Geometry. City College, New York City, USA, 25–26 Oct 2013. (extended abstract).
[details] [full text] [slides]
Abstract
We present an implementation of Overdetermined Laplacian Partial Differentiation Equations (ODETLAP) that uses CUDA directly. This lossy compression technique approximates a solution to an overdetermined system of equations in order to reconstruct gridded, correlated data. ODETLAP can be used to compress a dataset or to reconstruct missing data. Parallelism in CUDA provides speed performance improvements over other implementation methods. ODETLAP is inspired by the Laplacian Partial Differential Equation, though it is capable of preserving local extrema. Typical compression techniques are limited to viewing data as being one dimensional. The ODETLAP algorithm instead utilizes the autocorrelation of data in multiple dimensions to perform compression. This allows for improved compression of higher dimensional datasets, as can be found in geographical and environmental data[1, 2]. ODETLAP requires the construction and solution approximation of a sparse over-determined linear system of equations. As a result, the algorithm is quite compute-intensive. Parallelization techniques offer means of improving performance of this algorithm. The CUDA libraries, Thrust and CUSP, will be utilized in this parallel implementation of ODETLAP The Thrust library provides means for construction of the overdetermined system matrix, while the CUSP library contains solvers for such systems.
BibTeX
```
@inproceedings{benedetti-fwcg-2013,
    author = "Benedetti, Daniel and Franklin, W. Randolph and Li, Wenli",
    title = "{CUDA}-Accelerated {ODETLAP}: A Parallel Lossy Compression Implementation",
    booktitle = "23rd Fall Workshop on Computational Geometry",
    year = "2013",
    month = "25--26 Oct",
    address = "City College, New York City, USA",
    note = "(extended abstract)",
    href = "\bibhrefpt{172-fwcg2013-benedetti-cuda-odetlap}{172-fwcg2013-benedetti-cuda-odetlap-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/172-fwcg2013-benedetti-cuda-odetlap-talk.pdf",
    mykey = "benedetti wenlili odetlap parallel"
}
```