Discover Your Island University

Graduate Projects

View

Project ID: 380
Author: Huy V. Tran
Project Title: A MASSIVELY PARALLEL LINE SIMPLIFICATION ALGORITHM USING AN ASSOCIATIVE COMPUTING MODEL
Semester: 1 2011
Committe Chair: Dr. Michael Scherger
Committee Member 1: Dr. Petru-Aurelian Simionescu
Committee Member 2: Dr. Dulal Kar
Project Description: Line simplification is a process of reducing the number of line segments and vertices to represent a polyline. This reduction in the number of line segments and vertices can improve the performance of spatial analysis applications. The classic Douglas-Peucker algorithm developed in 1973 has a complexity of O(mn), where n denotes the number of vertices and m the number of line segments. Its enhanced version proposed in 1992 has a complexity of O(n log n). In this report, we present a parallel line simplification algorithm using a parallel Multiple-instructionstream Associative Computing model (MASC). Using one instruction stream of the MASC model, our algorithm has a parallel complexity of O(n) in the worst case using n processing elements. The parallel algorithm is implemented using Chapel, a parallel programming language being developed by Cray Inc. The performance of the parallel program was then evaluated on different parallel computers.
Project URL:   380.pdf