Parallel polygon line shading: the quest for more computational power from an existing GIS algorithm

Abstract

Utilising the powerful resources of a parallel computer has become a technique available to the GIS software engineer for increasing the performance of such complex software systems. This paper discusses the effectiveness of both automatic and manual parallelising techniques with a view to making an assessment as to whether the inherent sequential structure of GIS software is a detrimental factor inhibiting the use of such techniques. With the aid of the Scan Line Fill (SLF) algorithm in GIMMS, it has been shown that whilst automated parallelization has no merits in this case, a significant performance benefit can be achieved with algorithm redesign at the macro level to exploit the natural geometric parallelism inherent within the algorithm. However, the results illustrate that the full potential of this approach will not be appreciated until the I/O bottleneck is completely overcome, as opposed to merely avoided.