Patterns for Parallel Software Design

3.4. 3.4 Manager–Workers

Manager–Workers is a variant of Master-Slave [POSA1] [POSA4] for parallel systems, considering an activity parallelism approach in which both algorithm and date are divided and the same operations are performed on ordered data. The variation is based on the fact that components of this pattern are proactive rather than reactive [CT92]: each processing component performs the same operations simultaneously and independently of the processing activity of other components. However, it is important for the order of data to be preserved [Ort04] [OR98].

3.4.1. Example: the Polygon Overlay Problem

In the polygon overlay problem the objective is to obtain the overlay of two rectangular maps, A and B, each covering the same area that is decomposed into a set of non-overlapping rectangular polygons. This kind of problem frequently arises in geographical information systems, in which the first map might represent, for example, soil type, and the second vegetation. Their overlay shows how combinations of soil type and vegetation are distributed. Overlaying both maps creates a new map consisting of the non-empty polygons in the geometric intersection of A and B. To simplify this problem, all polygons are non-empty rectangles with vertices on a rectangular integer grid of N × M (Figure 3.21). Input maps also have identical extents, so that each be covered completely by its rectangular decomposition, and the data structures representing the maps is small enough to fit ...