The Parallel Hierarchies pattern is a parallel extension of the Layers pattern approach [POSA96, Shaw95, SG96] with elements of functional parallelism. The order of operations on data is the most important feature. Parallelism is introduced when two or more components of a layer are able to exist simultaneously, performing the same operation. Components can be created statically, waiting for calls from higher layers, or dynamically, when a call triggers their creation.

• Perform computation as a hierarchy of ordered operations several times, in a single execution.
• Data is shared among layers.
• The same group of operations can be simultaneously performed several times on different pieces of data.
• Operations may be different in size and level of complexity.
• Dynamic creation and destruction of components is preferred over static, to achieve load balance.
• Improvement in performance is achieved when execution time decreases.

• Layer. The responsibilities of a layer component are to provide operations or functions to more complex level layers, and to delegate more simple subtasks to layers in less complex levels. During run-time, more than one component per layer is allowed to execute concurrently with others.

• The Client calls a component Layer A1 to perform Computation 1. This component calls to a component Layer B1, which similarly calls a component Layer C1. Both components Layer A1 and Layer B1 remain blocked waiting to receive a return message from their respective sub-layers. This is the same behaviour than the sequential version of the Layers pattern [POSA96].
• Parallelism is introduced when the Client issues another call for Computation 2. This cannot be serviced by Layer A1, Layer B1 and Layer C1. Another instance of the component in Layer A, called Layer A2 - that either can be created dynamically or be waiting for requests statically - receives it and calls another instance of Layer B, Layer B2, to service this call. Due to the homogeneous nature of the components of each layer, every component in a layer can perform exactly the same operation. That is precisely the advantage of allowing them to operate in parallel. Therefore, any component in Layer B is capable to serve calls from components in Layer A. As the components of a layer are not exclusive resources, it is in general possible to have more than one instance to serve calls. Coordination between components of different layers is based on a kind of client/server schema. Finally, each component operates with the result of the return message. The main idea is that all computations are performed in a shorter time.

• Partitioning. Initially, it is necessary to define the basic Layer pattern system which will be used with parallel instances: the computation to be performed is decomposed into a set of ordered operations, hierarchically defined and related, determining the number of layers. Following this decomposition, the component representative of each layer can be defined. For a concurrent execution, the number of components per-layer depends on the number of requests. Several design patterns have been proposed to deal with layered systems. Advice and guidelines to recognise and implement these systems can be found in [POSA96, PLoP94]. Also, consider the patterns used to generate hierarchies, like A Hierarchy of Control Layers [AEM95] and the Layered Agent Pattern [KMJ96].
• Communication. The communication required to coordinate the parallel execution of layer components is determined by the services that each layer provides. Characteristics that should be carefully considered are the type and size of the shared data to be passed as arguments and return values, the interface for layer components, and the synchronous or asynchronous coordination schema. In general, an asynchronous coordination is preferred over a synchronous one. The implementation of communication structures between components depends on the features of the programming language used. Usually, if the programming language has defined the communication structures (for instance, function calls or remote procedure calls), the implementation is very simple. However, if the language does not support communication between remote components, it is proposed the construction of an extension in the form of a communication subsystem. Design patterns can be used for this. Particularly, patterns like the Broker pattern [POSA96], the Composite Messages pattern [SC95], the Service Configurator pattern [JS96] and the Visibility and Communication between Control Modules and Actions Triggered by Events [AEM95] can help to define and implement the required communication structures.
• Agglomeration. The hierarchical structure is evaluated with respect to the expected performance. Usually, systems based on identical hierarchies present a good load-balance. However, if necessary, using the conjecture-test approach, layer components can be refined by combination or decomposition of operations, modifying their granularity to improve performance or to reduce development costs.
• Mapping. In the best case, each layer component executes simultaneously on a different processor, if enough processors are available. Usually this is not the case. An approach proposes to execute each hierarchy on a processor, but if the number of requests is large, some hierarchies would have to block, keeping the client(s) waiting. Another mapping proposal attempts to place every layer on a processor. This simplifies the restriction about the number of requests, but if not all operations require all layers, this may overcharge the some processors, introducing load-balance problems. The most realistic approach seems to be a combination of the both previous ones, trying to maximise processor utilisation and minimise communication costs. In general, mapping of layers to processors is specified static, allowing an internal dynamic creation of new components to serve new requests. As a "rule of thumb", a Parallel Hierarchies pattern system will perform best on a shared-memory machine, but a good performance can be achieved if it can be adapted to a distributed-memory system with a fast communication network [Pan96, Pfis95].

• The Parallel Hierarchies pattern, as the original Layers pattern, is based on increasing levels of complexity. This allows the partitioning of the computation of a complex problem into a sequence of incremental, simple operations [SG96]. Allowing each layer to be presented as multiple components executing in parallel allows to perform the computation several times, enhancing performance.
• Changes in one layer do not propagate across the whole system, as each layer interacts at most with only the layers above and below, that can be affected. Furthermore, standardising the interfaces between layers usually confines the effect of changes exclusively to the layer that is changed. [POSA96, SG96].
• Layers support reuse. If a layer represents a well-defined operation, and communicates via a standardised interface, it can be used interchangeably in multiple contexts. A layer can be replaced by a semantically equivalent layer without great programming effort [POSA96, SG96].
• Granularity depends on the level of complexity of the operation that the layer performs. As the level of complexity decreases, the size of the components diminishes as well.
• Due to several instances of the same computation are executed independently on different data, synchronisation issues are restricted to the communications within just one computation.
• Relative performance depends only on the level of complexity of the operations to be computed, since all components are active [Pan96].

• Not every system computation can be structured as layers. Considerations of performance may require a strong coupling between high-level functions and their lower-level implementations. Load balance among layers is also a difficult issue for performance [SG96, Pan96].
• Many times, a layered system is not as efficient as a structure of communicating elements. If services in upper layers rely heavily on the lowest layers, all data must be transferred through the system. Also, if lower layers perform excessive or duplicate work, there is a negative influence on the performance. In certain cases, it is possible to consider a Pipe and Filter architecture instead [POSA96].
• If an application is developed as layers, a lot of effort must be expended in trying to establish the right levels of complexity, and thus, the correct granularity of different layers. Too few layers do not exploit the potential parallelism, but too many introduce unnecessary communications. The granularity and operation of layers is difficult, but related with the performance quality of the system [POSA96, SG96, NHST94].
• If the level of complexity of the layers is not correct, problems can arise when the behaviour of a layer is modified. If substantial work is required on many layers to incorporate an apparently local modification, the use of Layers can be a disadvantage [POSA96].

• The homomorphic skeletons approach, developed from the Bird-Meertens formalism and based on data types, can be considered as an example of the Parallel Hierarchies pattern: individual computations and communications are executed by replacing functions at different levels of abstraction [ST96].
• Tree structure operations like search trees, where a search process is created for each node. Starting from the root node of the tree, each process evaluates its associated node, and if it does not represent a solution, recursively creates a new search layer, composed of processes that evaluate each node of the tree. Processes are active simultaneously, expanding the search until they find a solution in a node, report it and terminate [Fos94, NHST94].
• The Gaussian elimination method, used to solve systems of linear equations, is a numerical problem that can be solved using a Parallel Hierarchies structure. The original system of equations, expressed as a matrix, is reduced to a triangular form by performing linear operations on the elements of each row as a layer. Once the triangular equivalent of the matrix is available, other arithmetic operations must be performed by each layer to obtain the solution of each linear equation [Fos94].

Jorge Luis Ortega Arjona.