O'Reilly logo

Patterns for Parallel Software Design by Jorge Luis Ortega-Arjona

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required