blue banner
//

Graduate Projects - Details

Computer Science Program

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
 
© Texas A&M University-Corpus Christi • 6300 Ocean Drive, Corpus Christi, Texas 78412 • 361-825-5700