SSP 1995 project summary Parallel merge-sort for GIS vector data

Geographical Information Systems (GIS) permit the storage, display and manipulation of spatially referenced data. Continued rapid growth in the availability of digital cartographic data and satellite images is creating a demand for intensive computing to integrate and process large datasets. Such datasets can be collected and integrated from a wide variety of sources, including geological, political and census databases. This information can then be used to solve problems in areas such as environmental assessment, transportation, marketing, distribution, telecommunications, planning and resource management.

GIS processing is both computationally and I/O intensive. This makes GIS an ideal application for parallel processing, where performance and I/O can be increased in a modular and scalable way. Consequently the Edinburgh Parallel Computing Centre, in partnership with the Department of Geography, has developed GIS systems that exploit parallel processing technology.

A scalable, extensible, parallel library of core GIS operations has been designed and partly implemented to interface to some of the major commercial GIS packages. These core operations are polygon overlay, and conversion between raster and vector data formats.

These core operations have been designed in a modular fashion enabling the substantial reuse of code segments. Full parallel designs have been produced for all components of all operations.

The proposed Summer Student projects involve redesign and implementation of the vector data input module to use MPI instead of CHIMP. The projects also involve implementation of the outstanding components in this module.

The vector data input module performs the pre-processing and distribution of vector data necessary for both the polygon overlay and vector-to-raster conversion operations. Indeed similar processing and distribution of vector data is required by most vector GIS operations. This module is therefore an important building block for parallel GIS operations other than just polygon overlay and vector-to-raster conversion operations. It also necessary for operations such as vector topology creation, buffer generation and generalisation.

The vector data input module comprises three sub-phases :

• Sort This extracts the data necessary for the operations from the input datasets. This data is then processed and sorted before output to PUL-PF files.
• Join The data output by Sort are merge-sorted and combined.
• Geom Attribute Distribution (GAD) This takes the data out by Join and decomposes and distributes to Worker processes for Polygon Overlay or Vector-to-Raster conversion.

These sub-phases have been designed and partially implemented using CHIMP. Detailed design documents and pseudo-code also exist. All code is written in C. Two summer student projects would assist greatly in completing the implementation of the vector data input module. Once complete the vector data input module could be integrated with the Topology, Stitching and Output module currently being implemented by the Department Of Geography to produce a vector topology creation operation. Also by integrating the prototype polygon overlay module as well, a complete polygon overlay operation could be produced. This would therefore be amongst the first, if not the first, modular parallel GIS operations in the world and would represent a significant step in creating a library of parallel GIS operations. As such the results of the projects would be publishable in academic journals.

The project involves the following stages:

• MPI training and familiarisation with parallel GIS project and its coding conventions.
• Redesign Sort sub-phase message passing using MPI instead of CHIMP. Also assess impact of MPI implementation of PUL-PF and redesign accordingly.
• Implement redesigned Sort sub-phase integrating this with existing code on geom processing.
• Redesign Join sub-phase message passing using MPI instead of CHIMP and assess impact of MPI implementation of PUL-PF and PUL-active buffers and redesign accordingly.
• Implement redesigned Join sub-phase integrating this with existing code.

Robert Jackson worked on this project.

Compressed PostScript of the project's final report is available here (309367 bytes) .

Webpage maintained by mario@epcc.ed.ac.uk