PARALLELIZING A GIS ON A SHARED ADDRESS SPACE ARCHITECTURE

Visualization applications-like flight simulators and virtual reality environments-use geographic information systems to represent actual te rrain. Applications like these impose stringent restrictions on accept able performance and response time. Sequential methods do not meet the se requirements, but parallel methods can. The authors are developing a high-performance GIS on an SGI Challenge, a 16-processor machine wit h a shared address space architecture. They describe how they parallel ized a key GIS operation using a message-passing algorithm. As part of the GIS project, the authors evaluated the effect of parallelizing an important GIS operation: range query. They parallelized range query u sing data partitioning (to reduce synchronization) and dynamic load ba lancing (to improve speedup). They found these approaches do achieve t he performance required for many GIS applications. The approach descri bed here links two diverse approaches to the design of parallel archit ectures and algorithms. Parallel architectures have emphasized either shared address space or message passing; algorithms either the PRAM or message-passing models. The authors advocate a different link between the architecture and algorithms-their range query operation uses a me ssage-passing algorithm, yet is appropriate for a SASA architecture.