SSP Project Summary:

Parallel Vector-topological data input for Geographical Informations Systems

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 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.

The designs for this work are about to be published in a Taylor and Francis book, so this would represent a useful test of this work and as such is publishable. Last year's SSP is referenced and the results quoted in this text.

Last year, an SSP student redesigned the Sort phase of the Vector Data input module to use MPI instead of CHIMP. This was implemented and tested successfully.

The proposal for this year's project is to redesign and implement the Join and GAD phases for MPI instead of CHIMP. An implementation of the Join phase with CHIMP currently exists and has been tested successfully. This first task is therefore a useful introduction to the GIS the project and MPI since essentially that is required is the reimplementation of the message passing code in Join. The second task requires much more effort since only a design (with pseudo-code) of the GAD phase using CHIMP exists. However this task uses much of the functionality previously implemented in the Sort and Join phases and therefore should be straightforward.

The project therefore consists of the following units.

• MPI training and familiarisation with parallel GIS project and its coding conventions. (1 week)
• Redesign and modify existing Join phase code to use MPI instead of CHIMP. (2 weeks)
• Integrate Sort and Join phases and test. (1 week)
• Redesign GAD phase message passing using MPI instead of CHIMP. (1 week)
• Implement redesigned GAD sub-phase. This reuses much of the functionality present in the Sort and Join codes. (3 weeks)
• Integrate Sort, Join and GAD phases and test. (1 week)
• Write final report. (1 week)

Expertise Required

Resources Required

Resources Supplied

Michal Rewienski worked on this project.

Compressed PostScript of the project's final report is available here (44 kbytes) .

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