Architectural Patterns for Parallel Programming

Parallel programming is characterised by a growing set of parallel architectures, paradigms and programming languages. This situation makes difficult to propose just one approach containing all the details to design and implement parallel software systems. The architectural patterns proposed here are proposed as an effort to help a programmer to decide a starting point when designing a parallel program. Thus, all the patterns contained here share similarities in their context and implementation.

Context in general

Start the design a software program for a parallel system, using a certain programming language for certain parallel hardware. Consider the following context assumptions:

The problem involves tasks of a scale that would be unrealistic or not cost-effective for other systems to handle and lends itself to be solved using parallelism.

The hardware platform or machine to be used is fixed, offering a reasonably good fit to the parallelism found in the problem.

The language that will be used, based on a certain programming paradigm, is already determined, and a compiler version is available for the parallel platform.

In general, the existence of an available parallel platform and a programming language are considered as a basic context condition when starting the design and implementation of a parallel program. They are determinant of the performance that can be achieved, and also influence the design of software. Once fixed, the decision to use one architectural organisation or another relays mainly on the characteristics of the problem. This work focuses more precisely on these characteristics. Each pattern represents a form to identify how operations can be performed in parallel and/or how data can be operated simultaneously.

Implementation in general

Also, as an effect of the context, the implementation of all these patterns share the same steps, intended to describe an architectural exploratory approach to design, in which hardware-independent features are early considered, and hardware-specific issues are delayed in the implementation process. This method structures the implementation process of parallel software based on four stages [Fos94, CSG97]:

Partitioning. The computation to be performed and/or the data operated are decomposed into operations and/or data pieces, defining possible components for the parallel program. During this stage, practical hardware-dependent issues are ignored. The attention is focussed on recognising the opportunities for parallel execution. In general, architectural pattern components are implemented using design patterns [POSA96].

Communication. The communication to coordinate process execution is determined, defining appropriate communication structures between processing components. In general, architectural communication structures are also based on design patterns [POSA96]

Agglomeration. The components and communication structures recognised in the previous steps are evaluated in accordance with performance requirements. In the case of parallel systems, usually a conjecture-test approach is used, in which components are recombined several times into larger components, aiming to maximise processor utilisation and reduce communication costs.

Mapping. Components are assigned to real processors, trying to satisfy the attempts of the agglomeration stage. Mapping can be defined static or dynamic, depending directly on hardware issues.

The approach presented here is intended to deal with the implementation issues from an architectural point of view. During the first two stages, attention is focused on concurrency and scalability characteristics. In the last two stages, attention is aimed to shift locality and other performance-related issues. Nevertheless, it is preferred to present each stage as general considerations for designing each pattern, instead of provide details about precise implementation of participants. These implementation details are pointed more precisely in the form of references to design patterns for concurrent, parallel and distributed systems of several other authors [Sch95, Sch98a, Sch98b].

Further reference about features of parallel hardware platforms and parallel languages can be found in [CSG97, Fos94, Para98, Perr92, Pfis95, Phil95, ST96]. Also, good advice and guidelines about platform and language selection for performance, related with speed-up and scalability, can be found in [Pan96, PB90].

Pipes and Filters pattern

Parallel Hierarchies pattern

Communicating Sequential Elements pattern

Manager-Workers pattern

Shared Resource pattern

Contact Information

Jorge Luis Ortega Arjona.

E-mail jortega-arjona@acm.org