Architectural patterns for parallel programming can be classified following the characteristics of parallel systems as the classification criteria. Pancake [Pan96], Foster [Fos94], and Carriero and Gelernter [CG88] have studied and proposed classifications according to the characteristics of parallel applications, and their relation with performance. All of them agree that in parallel programming, the nature of the problem to be solved is tightly related to the structure and behaviour of the program that solves it.

Architectural patterns for parallel programming are defined and classified according to the requirements of order of data and operations, and the nature of their processing components.

Requirements of order dictate the way in which parallel computation has to be performed, and therefore, impact on the software design. Following this, it is possible to consider that most parallel applications fall into one of three forms of parallelism: functional parallelism [Fos94], domain parallelism [Fos94], and activity parallelism [CG88], which depend on the requirements of order of operations and data in the problem.

• Functional parallelism can be found in problems where a computation can be described in terms of a series of time-step ordered operations, on a series of ordered values or data with predictable organization and interdependencies. As each step represents a change of the input for value or effect over time, a high amount of communication between components in the solution, in the form of a flow of data or operations, should be considered. Conceptually, a single data value or transformation is performed repeatedly [CG88, Fos94, Pan96].
• Domain parallelism involves problems in which a set of almost independent operations is to be performed on ordered local data. Because each component in the solution is expected to execute a relatively autonomous computation, the amount of communication between them can be variable, following fixed and predictable paths that can be represented as a network. It is difficult to conceive the computation as a flow of data among processing stages or sequential steps in an algorithm [CG88, Fos94, Pan96].
• Activity parallelism involves problems that apply independent computations as sets of non-deterministic transformations, perhaps repeatedly, on values of an ordered or unordered data structure. Activity parallelism can be considered between the extremes of allowing all data to be absorbed by the components or all processes to be divided into components. Many components share access to pieces of a data structure. As each component performs independent computations, communication between processing components is not required. However, the amount of communication is not zero. Communication is required between a component that controls the access of components to the data structure and the processing components [CG88, Pan96].

The nature of processing components is another classification criteria that can be used for parallel systems. Generally, components of parallel systems perform coordination and processing activities. Considering only the processing characteristic of the components, parallel systems are classified as homogenous systems and heterogeneous systems, according to the same or different processing nature of their components. This nature exposes properties that have tangible effects on their number in the system and the kind of communications among them.

• Homogeneous systems are based on identical components interacting in accordance with simple sets of behavioural rules. They represent instances with the same behaviour. Individually, any component can be swapped with another without noticeable change in the operation of the system. Usually, homogeneous systems have a large number of components, which communicate using data exchange operations.
• Heterogeneous systems are based on different components with specialised behavioural rules and relations. Basically, the operation of the system relies on the differences between components, and therefore, no component can be swapped with another. In general, heterogeneous systems are composed of fewer components than homogeneous systems, and communicate using function calls.

Based on these classification criteria, this paper presents five architectural patterns commonly used in parallel systems programming:

• The Pipes and Filters pattern is an extension of the original Pipes and Filters pattern [POSA96, Shaw95, SG96] for parallel systems, using a functional parallelism approach where computations follow a precise order of operations on ordered data. Commonly, each component represents a different step of the computation and data is passed from one computation stage to another along the whole structure.
• The Parallel Hierarchies pattern extends the original approach of the Layers Pattern [POSA96, Shaw95, SG96] for parallel systems, considering a functional parallelism in which the order of operations on data is the important feature. Parallelism is introduced when two or more hierarchies of layers are able to run simultaneously, performing the same computation.
• The Communicating Sequential Elements pattern is used when the design problem at hand can be understood in terms of domain parallelism. The same operations are performed simultaneously on different pieces of ordered data [Fos94, CT92]. Operations in each component depend on partial results in neighbour components. Usually, this pattern is presented as a network or logical structure, conceived from the ordered data.
• The Manager-Workers pattern can be considered as a variant of the Master-Slave pattern [POSA96] for parallel systems, introducing an activity parallelism where the same operations are performed on ordered data. Each component performs the same operations, independent of the processing activity of other components. Different pieces of data are processed simultaneously. Preserving the order of data is the important feature.
• The Shared Resource pattern is a specialisation variant of the Blackboard pattern [POSA96] introducing activity parallelism characteristics, where different computations are performed simultaneously, without a prescribed order, on ordered data.

Jorge Luis Ortega Arjona.