Architectural Patterns for Parallel Programming

Shared Resource

The Shared Resource pattern is a specialisation of the Blackboard pattern [POSA96], lacking a control component and introducing aspects of activity parallelism, in which computations are performed, without a prescribed order, on ordered data. Commonly, components perform different computations on different data pieces simultaneously.

Examples
A Non-programming Example
Imagine a project of construction in general. An artifact (a building, a software program, a business program, etc.) is the result of the cooperation among several persons or teams, with different skills. Each one has different interests, responsibilities and perceptions of the project. All people or teams participate independently and simultaneously with different actions to achieve the result. A common objective and unity among them will produce a satisfactory result in time and consistent form. A Programming Example

Consider a printed circuit board router program [Chien93]. A route is a series of wires or nets from one pin to another on a circuit board. Complex circuit boards might have a large number of routes. Routes must avoid obstacles on the board and other routes. A parallel implementation proposes to process each route by independent components, searching simultaneously on a data structure (representing the grid of coordinates on the board) for the shortest route between pins. Each component accesses the data structure, proposing a new probable free coordinate to add to its route from a given start point on the board. If this is occupied by an obstacle or another route, the component makes another proposal. Once a coordinate is added, each component calculates the lowest total distance estimate for its route.

Problem

It is necessary to apply completely independent computations as sets of non-deterministic interactions on elements of some centralised, perhaps not even ordered, data structure. Consider for example, a knowledge exchange problem. Components communicate via a shared resource, each one indicating its interest in a certain data object. The shared resource provides such data immediately if no other component is accessing it. Data consistency and preservation are tasks of the shared resource. The internal representation or order of data is important, but the order of operations on it is not a central issue. Generally, performance as execution time is the feature of interest.

Forces

Taking the previous problem description and other elements of parallel design such as granularity and load balance [Fos94, CT92], the following forces can be found:

Preserve the order or integrity of data structure.

Each processing element performs simultaneously a different and independent computation on different pieces of data.

No specific order of data access by processing elements is defined.

Improvement in performance is achieved when execution time decreases.

Solution

Each component executes simultaneously, capable of performing different and independent operations, accessing the data as shared resource when needed. Parallelism is absolute among components: any component can be performing different operations on a different piece data at the same time, without any prescribed order. The restriction is that no piece of information is accessed at the same time by different components. Communication can be achieved as function calls to require a service from the shared resource. The Shared Resource pattern can be considered as an activity parallel variation of the Blackboard pattern [POSA96] without a control instance that triggers the execution of sources. An important feature is that the execution does not follow a precise order of computations [Shaw95, Pan96].

Structure

This pattern is based only on a shared resource as a central structure that controls the access of different sources. Usually, a shared resource component and several different source components simultaneously exist and process during the execution time (Figure 11).

Figure 11. Shared resource pattern.

Participants

Shared resource. The responsibility of a shared resource is to coordinate access of sources, preserving the integrity of data.

Source. The responsibilities of a source are to perform its independent computation, until requiring a service from the shared resource. Then, the source has to cope with any access restriction imposed by the shared resource.

Dynamics

A typical scenario to describe the basic run-time behaviour of the Shared Resource pattern is presented. All participants are simultaneously active. Every source performs a different operation, requiring the shared resource for operations. As soon as it finishes processing, returns to the calling source to continue its computations. Communications between sources are not allowed. The shared resource is the only common component among the sources (figure 12). The functionality of this general scenario is explained as follows:

Figure 12. Scenario of Shared resource pattern.

The Shared resource component is able to perform a couple of action, Op.R and Op.S. Each source starts processing, and calls the Shared resource to perform one of its operations. Sources perform different, independent operations.

Source A performs Op.A1, requiring the Shared resource to perform operation Op.R. At the same time, Source B and Source N start performing Op.B1 and Op.N1. The Shared resource returns a value to Source A.

Source N starts performing Op.N2, requiring now the Shared resource to perform Op.S. Meanwhile, Source A processes Op.A2, and Source B processes Op.B2. After some time, operation Op.B2 requires the Shared resource to perform again Op.R. This returns a value to Source N and continues with the call from Source B.

All operations continue in time, until all independent computations in the sources finish.

Implementation

The implementation process is based on the four stages mentioned above in the Context in general and Implementation in general sections.

Partitioning. The computation to be performed can be viewed as the effect of different independent computations on the data structure. Each source component is defined to perform a complete computation on the shared resource. Sources can be executed simultaneously due to their independent processing nature. However, the shared resource implementation should reflect a division and integrity criteria of the data structure, following the basic assumption that no piece of data is operated at the same time by two different sources. Therefore, sources may be implemented by a single entity (for instance, a process, a task, an object, etc.) that performs a defined computation, or a sub-system of entities. Design patterns in general [GHJV95, POSA96, PLoP94, PLoP95] may help with the implementation of the sources components as sub-systems of entities. Also, patterns used in concurrent programming like the Object group pattern [Maf96], the Active Object pattern [LS95], and Categorize Objects for Concurrency pattern [AEM95] can help to define and implement sources. Other design patterns like the Double-Checked Locking pattern [SH96], the Thread-Specific Storage pattern [HS97] and those presented in [McKe95] deal with issues about the safe use of threads and locks, and may provide help to implement the expected behaviour of the shared resource component.

Communication. The communication to coordinate interaction of sources and shared resource is represented by an appropriate communication interface that allows the access to the shared resource. This interface should consider the form in which requests are issued to the shared resource, and the format and size of the data as argument or return value. In general, an asynchronous coordination schema is used, due to the heterogeneous behaviour of the sources. The implementation of a flexible interface between sources and shared resource can be done using design patterns for communication, like the Service Configurator pattern [JS96], the Composite Messages pattern [SC95], and the Compatible Heterogeneous Agents and Visibility and Communication between Agents patterns [ABM96].

Agglomeration. The components and communication structures defined in the first two stages of a design are evaluated, comparing with the performance requirements. If necessary, operations can be recombined and reassigned to create different sets of source components with different granularity and load-balance. Usually, due to the independent nature of the sources, it is difficult to achieve a good performance initially, but at the same time, it is easy to perform changes on the sources without affecting the whole structure. The conjecture-test approach is used intensively, modifying both granularity and load-balance of source components to observe which combination can be used to improve performance. However, especial care should be taken with the load-balance between sources and shared resource. The operations of the shared resource should be lighter than any source computation, to allow a fast response of the shared resource to requests. Most of the computation activity is suppose to be performed by the sources.

Mapping. In the best case, trying to maximise processor utilisation and minimise communication costs, each component should be assigned to a different processor. Due to the number of components is usually expected to be not too large, enough parallel processor can be commonly available. Also, the independent nature of sources allows that each source component can be executed on a different processor. The shared resource also is expected to be executed on a single processor, and all sources should have communication access to it. However, if the number of processors is limited and less than the number of components, it is difficult and complex to load-balance of the whole structure. To solve this, mapping can be determined at run-time by load-balancing algorithms. As a "rule of thumb", systems based on the Shared resource patterns present a good performance when implemented on a MIMD (multiple-instruction, multiple-data) computer. Also, it would be very difficult to implement them for a SIMD (single-instruction, multiple-data) computer [Pan96, Pfis95].

Consequences
Benefits

Integrity of the Shared resource data structure is preserved by the restriction that no data piece is accessed at the same time by different components.

From the perspective of a parallel designer, this pattern is the simplest to develop due to the minimal dependence between components. Fundamentally, the operations on each data element are completely independent. That is, each piece of data can be computed on different machines, running independently as long as the appropriate input data are available to each one. It is relatively easy to achieve a significant performance in an application that fits this pattern [Pan96].

As its components (the shared resource and the component sources) are strictly separated, the Shared resource pattern supports changeability and maintainability [POSA96, Pan96].

The Shared resource pattern supports several levels of granularity. If required, the shared resource component can provide operations for different data sizes.

Due to source components perform different and independent operations, they can be reused in different structures. The only requirement for reuse is that the source to be reused is able to perform certain operations on the data type in the new shared resource [POSA96, Pan96].

A shared resource can provide fault tolerance for noise in data [POSA96, SG96].

The activities of synchronisation are defined and localised generally in the shared resource components, and restricted between the shared resource and each one of the source components.

Liabilities

Due to the different nature of each component, load balance is difficult to achieve, even when executing each component on a different processor. The difficulty increases if several components run together in a processor [Pan96].

Results in a shared resource application are difficult to reproduce. Inherently, computations are not ordered following a deterministic algorithm and its results are not reproducible [POSA96]. Furthermore, the parallelism of its components introduces a non-deterministic feature to the execution [Pan96].

Most shared resource structures require a great development effort, due to the variety of requirements in different problem domains [POSA96].

Even when parallelism is straightforward, often the shared resource does not consider the use of control strategies to exploit the parallelism of sources and to synchronise their actions. Due to this, in order to preserve its integrity, the design of the shared resource component must consider extra mechanisms or synchronisation constraints to access its data. An alternative is perhaps to use the Blackboard pattern [POSA96].

Known uses

Mobile robotics control is an application example of the Shared resource pattern. The software functions for a mobile robotics system has to deal with external sensors for acquiring input and actuators for controlling its motion and planning its future path in real-time. Unpredictable events may demand a rapid response: imperfect sensor input, power failures, mechanical limitations in the motion, etc. A solution example, the CODGER system, uses the Shared resource pattern to model the cooperation of tasks for coordination and resolution of uncertain situations in a flexible form. CODGER is composed of a "captain", a "map navigator", a "lookout", a "pilot" and a perception system, each one sharing information by a common shared resource [SG96].

A real-time scheduler is another application of the Shared resource pattern. The application is a process control system, in which a number of independent processes are executed, each having its own real time requirements, and therefore, no process can make assumptions about the relative speed of other processes. Conceptually, they are regarded as different concurrent processes coordinated by a real-time scheduler, accessing, for instance, computer resources (Consoles, printers, I/O devices, etc.) which are shared among them. The real-time scheduler is implemented as a shared resource component to give processes exclusive access to a computer resource, but does not perform any operation on the resource itself. Each different process performs its operations, requiring from time to time the use of the computer resources. The shared resource component grants the use of the resources, maintaining the integrity of the data read from or written to a resource by each different process [Han77].

A Tuple space, used to contain data, presents a Shared resource pattern structure. Sources can generate asynchronous requests to read, remove and add tuples. The tuple space is encapsulated in a single shared resource component that maintains the set of tuples, preventing two parallel sources from act simultaneously on the same tuple [Fos94].

Related patterns

The Shared Resource pattern is considered a specialisation of the Blackboard pattern [POSA96] without control component, and introducing aspects of activity parallelism Also, it is related to the Repository architectural style [Shaw95, SG96]. Other patterns that can be considered related to this pattern are the Compatible Heterogeneous Agents pattern [ABM96] and the Object Group pattern [Maf96].

Contact Information

Jorge Luis Ortega Arjona.

E-mail jortega-arjona@acm.org