Patterns for Parallel Software Design

3.2. 3.2 Parallel Layers

The Parallel Layers pattern is an extension of the original Layers pattern [POSA1] [POSA4] [Sha95] [SG96] with elements of functional parallelism. In this type of parallelism, two or more components of a layer are able to exist simultaneously, normally performing the same operation. Components can be created statically, waiting for calls from higher layers, or dynamically, when a call triggers their creation.

3.2.1. Example: Single-Source Shortest Path Algorithm

Searching is defined as a systematic examination of a problem space from an initial state and finishing at a particular final state or states. Each of the intermediate states, between the initial and the final states, are reached by operating on a given state. Such an operation is determined by an objective function that assures iteration to the final state. Any search problem can be conveniently represented using a graph composed of a set of vertices and edges. Each edge has a positive integer weight that represents the distance between the vertices it connects (Figure 3.6). The objective, therefore, is to search for the shortest path between the source vertex and the rest of the vertices.

Figure 3.6. An example of a typical graph

The Single-Source Shortest Path (SSSP) algorithm was originally proposed by Dijkstra, and described later by Chandy and Misra [CM88]. It is an efficient algorithm ...