Patterns and Skeletons for Parallel and Distributed Computing

Parallelism seeks to achieve better computation performance by simultaneously using multiple processors, either in one computer or across several computers connected in a network. Parallel computing has not yet become a routine way of solving problems faster, mostly because parallel machines are hard to program. A major reason for this unsatisfactory situation is that the convenience and correctness of parallel programming has often been neglected in favour of the foremost aim of parallelism — achieving very high absolute performance.

Today, conditions for the development of parallel and distributed systems would appear to be ideal. On the one hand, the demand for such systems is strong and growing steadily. Traditional supercomputing applications, Grand Challenges, require the solution of increasingly large problems, with new areas added recently, e.g. research on the human genome. The rapid growth of the Internet has given rise to geographically distributed, networked supercomputers (Grids) and to new classes of distributed commercial applications with parallelism on both the server and client side. On the other hand, bigger and more powerful systems are being built every year. Microprocessors are rapidly becoming faster and cheaper, enabling more processors to be connected in one system. New networking hardware with smaller latency and greater bandwidth is improving systems’ communication performance. Several levels of parallelism are available to the user: within a processor, among several processors in an SMP or a cluster, as well as parallelism among remote machines cooperating via the Internet.

Sequential programming has overcome its preoccupation with details of the machine organisation several decades ago. In contrast, the average parallel programmer spends a large amount of development time on organisational details like synchronisation, communication, marshalling, etc. Message passing libraries like MPI are useful aids at this level ¡ª but they give the programmer a large choice of complex options rather than removing organisational issues with bold abstractions.

Two important abstractions have contributed to create a reliable programming methodology for industrial-strength programs These are functional abstraction (which has received different names in programming languages, such as procedure, subroutine, function, etc), and data abstraction (also with different names such as abstract data type, object, package or simply module). In both abstractions two different pieces of information are distinguished:

Prototyping is an attractive general basis for experimentation with system design, where the design is refined in the light of prototype behaviour, leading in turn to prototype refinement. A prototype should be considerably cheaper to construct than the final system, and avoid commitment to fine implementation detail, while displaying the same gross input/output characteristics. Once the design has stabilised, the prototype provides a standard for the final system.

In many parallel applications high performance figures are reached at the expenses of software quality. The parallel structure of an application is decided by the programmer and wired in the application code. Resource management is carefully tuned “by hand”, compromising the possibility to reuse the code without substantial re-programming. Software is hard to maintain and to prove correct against specifications as single interactions need to be coded and managed.

After experiencing a considerable growth in the early 1980s, it is now recognised that parallel processing has yet to reach a stage where it delivers stable, efficient and portable software. For this reason, the design of programming models for parallel processing and the tools to support them is still an active research area [22]. Most models and tools are designed around basic communication primitives such as shared memory, message-passing or Remote Procedure Call (RPC). This chapter advocates the use of algorithmic skeletons as basic design primitives around which a complete development environment can be built. It starts by presenting the author’s classification of parallel algorithms, which is the basis for identifying the skeletons that are most relevant in practice. Then it describes experiences in building three programming environments based around the same skeleton (Static Iterative Transformation).

New and planned commercial and military distributed real-time and embedded (DRE) systems take input from many remote sensors, and provide geographically-dispersed operators with the ability to interact with the collected information and control remote effectors. In circumstances where the presence of humans in the loop is too expensive or their responses are too slow, these systems must respond autonomously and flexibly to unanticipated combinations of events at run time. Moreover, DRE systems are increasingly being networked to form long-lived “systems of systems” that must run unobtrusively and autonomously, shielding operators from unnecessary details, while simultaneously communicating and responding to mission-critical information at heretofore infeasible rates. In such environments, it is hard to enumerate, even approximately, all possible physical system configurations or workload mixes a priori.

Component integration has become an important area of research within the last decade ¡ª the intention being to combine a diverse set of custom and offthe-shelf components, from different vendors, to create applications. Components can implement simple functions, such as perform a matrix manipulation or perform a simple database query, or they can be more complex and wrap complete applications. Hence, the granularity of a component can vary from being coarse grained (when wrapping applications), to fine grained (when performing a simple database query). To facilitate the development of applications by combining components, an infrastructure is needed to enable components developed by different vendors to interoperate. The infrastructure must provide specialised services for managing, naming, locating and executing components, with standardisation efforts playing a crucial role in the process. Existing infrastructures such as DCOM from Microsoft, and CORBA/OMA from the Object Management Group (OMG), generally define this infrastructure in terms of (1) a component model, (2) containers which enable components to interact with services provided by the infrastructure, and (3) connectors, which enable components to interact with each other. The CORBA model for instance provides a platform independent language for defining component interfaces using an Interface Definition Language (IDL), and connectivity using an Object Request Broker (ORB). Infrastructure services within the CORBA model include persistence support, lifecycle support, a component naming service, a trading service for identifying services undertaken by components, and others.

Within the context of component based software, another concept has become increasingly important, and referred to as the “Grid”. The “Grid” or the “Computational Grid” (CG) signifies a component infrastructure that is based on the provision of infrastructure services which enable multi-vendor and

The growth of the Internet has unleashed a wave of innovations that are reshaping the way organisations interact with their partners and customers. In particular, the concept of electronically-accessible service (also known as e-service or Web service) has gained a considerable momentum as a paradigm for supporting both Business-to-Consumer (B2C) interaction and Business-to-Business (B2B) collaboration.

It is now feasible to manufacture chips having 100 M transistors. This is leading to the adoption of SOC (System-On-a-Chip) designs. Complexity, timeto-market pressure and evolving requirements push SOC design to reuse IP (Intellectual Property) blocks and build around programmable platforms. By opposition to the ASICs (Application Specific Integrated Circuits) where all the desired functionality is hardwired, programmable platforms contain programmable devices (such as processors) and specific functions are hardwired to meet some performance requirements; programmability offers flexibility, easy extensibility and adaptability to new requirements. This results in new challenges in the design process. Higher levels of abstraction must be defined. Description languages must handle both hardware and software components, and must be able to capture constraints and describe communication between them. CAD (Computer-Aided-Design) tools must allow integration of IP blocks, HW/SW (hardware/software) partitioning and communication mapping to obtain the expected performance. And finally verification must handle integrated hardware and software modules.