Parallel Computing

Abstract
Introduction
Message-passing
PVM (Parallel Virtual Machine)
jPVM
Message-Passing Interface (MPI)
OpenMP
Parallel Computing - Links

Abstract

In the last decade, researchers and scientists have investigated ways to leverage the power of inexpensive networked workstations for parallel applications. The Message Passing Interface (MPI) standard provides a common Application Programming Interface (API) for the development of parallel applications regardless of the type of multiprocessor system used. In the recent past, the Java programming language has made significant inroads as the programming language of choice for the development of a variety of applications in diverse domains. Having realised the significance of Java in the software developement arena, we propose to develop a reference implementation of MPI standard using Java programming language.

Here we have supplied a broad overview of the most important paradigms for developing parallel applications.

If we are thrusted to solve problems which are too complex with theoretical approaches and too expensive with empirical approaches, scientists turn to simulation models for solving this sort of problems. Some specific problems, such as global climate modeling demand more computational resources than a single processor machine can provide. With the cost of parallel computers outside the reach of most budgets, researchers instead form parallel supercomputers out of existing in-house workstations connected via a network.

If performance is an important criteria in a software product being developed, then the best option is to produce it in parallel/distributed version. Software, thus developed, can be made to run in a very high speed by using as many processors as possible in a concurrent setting instead of doing the same on a single processor. Theoretically if a software is allowed to run on 10 processors, for example, then correspondingly the rate of execution speed can go upto 10 times faster. Thus many large computational problems can be solved in a cost-effective manner by making use of the aggregate power and memory of many heterogeneous computing systems.

By making use of a variety of distributed communications software, the workload of large software applications can be split into many smaller tasks and shared among many available processors, which cooperate in accomplishing the original application. An another advantage with this is that the parallelized software can run on complex, heterogeneous sets of computing systems, which includes multi-processor systems.

Applications that benefit from parallel processing get divided roughly into business data processing and technical/scientific processing. Business data processing applications are characterized by record processing, and the size of the data typically creates significant I/O performance issues as well as the need for fast computation.

Technical and scientific applications tend to be compute-bound, that is, these applications require much processor computation, and have tended to be associated with the supercomputer. There are two primary paradigms used in the creation of most of these applications: Message-passing and Parallelizing compilers.

Parallel compilers are compilers that can create parallel execution from seemingly sequential program source code. These compilers can decompose a program and insert the necessary message-passing structures and other parallel constructs automatically.

In the early days of parallel processing, two or more processors shared the work to be done. The earliest versions had a master/slave configuration. One processor (the master) was programmed to be responsible for all of the work in the system and the other (the slave) performed only those tasks it was assigned by the master processor. This was due to the absense of necessary details for coding programs in such a way that machines can cooperate themselves in managing the resources concurrently and efficiently.

Then came symmetric multiprocessing systems (SMP). In an SMP system, each processor is equally capable and responsible for managing the flow of work through the system. The goal was to make SMP systems appear to programmers to be exactly the same as single processor, multiprogramming systems. But as the days went by, performance complexity happened to be a big stumbling block for this model to flurish.

That is, as the number of processors in SMP systems increases, the time it takes for data to propagate from one part of the system to all other parts, grows also. This resulted in high complexity. When the number of processors goes above, say 50, the performance benefit of adding more processors to the system is too small to justify the additional expense.

To overcome this critical problem of long propagation times, message-passing systems came into existence.

In these message-passing systems, programs that share data send messages to each other conveying that particular operands have been assigned a new value. In SMP model, there was a broadcast of an operand's new value to all parts of a system. But in these systems, the new value is communicated only to those programs which need to know the new value. Also in the place of shared memory, there is a network to support the transfer of messages between programs. This simplification permits even hundreds of processors to work together efficiently in one system with much reduced complexity. Thus message-passing systems are put in the class of massively parallel processing systems. Often message-passing systems are structured as clusters of processors. With each cluster the processors interact as in a SMP system. It is only between the clusters that messages are passed. Operands may be addressed either via messages or via memory addresses.

Message-passing has emerged as one of the more widely-used paradigms for expressing parallel algorithms. Its expressive power has proven adequate for writing parallel programs and its close match with the hardware of many current parallel computers (including workstation networks) has made it possible for the programs to exploit the full capabilities of most current hardware.

Message-passing is becoming a paradigm to being a "standard" approach for implementation of parallel applications.

Currently research works are going on for designing robust algorithms using message-passing paradigm and classifying applications in science and engineering based on message-passing. Also software development companies have taken up the job of developing exciting tools for PVM and MPI. Here comes a broad overview of each of these.

Parallel applications are developed with message passing libraries, freeing developers from the cumbersome task of network programming, and allowing developers to concentrate on their algorithms.

At present, both PVM and MPI (Message Passing Interface) are the most frequently used software tools for parallel programming according to the above mentioned message-passing paradigm.

PVM is an integrated set of software tools and libraries that emulates a general-purpose, flexible, heterogeneous concurrent computing framework on interconnected computers of varied architecture. The primary objective of the PVM system is to to enable such a collection of computing systems to be used cooperatively for concurrent or parallel computation.

In other words, PVM is a portable message-passing programming system, designed to link separate host machines to form a ``virtual machine'' which is a single, manageable computing resource. The virtual machine can be composed of hosts of varying types, in physically remote locations. PVM applications can be composed of any number of separate processes, or components, written in a mixture of programming languages such as C, C++ and Fortran. The system is portable to a wide variety of architectures, including workstations, multiprocessors, supercomputers and PCs.

A typical PVM system is composed of two parts. The first part is a daemon that resides on all the computers making up the virtual machine.

The second part of the system is a library of PVM interface routines. It contains a functionally complete repertoire of primitives that are needed for cooperation between tasks of an application. This library contains user-callable routines for message passing, spawning processes, coordinating tasks, and modifying the virtual machine.

The PVM computing model is based on the notion that an application consists of several tasks. Each task is responsible for a part of the application's computational workload. Sometimes an application is parallelized along its functions. That is, each task performs a different function, such as input, problem setup, solution, output, and display. This process is often called functional parallelism . A more common method of parallelizing an application is called data parallelism . In this method all the tasks are the same, but each one only knows and solves a small part of the data. This is also referred to as the SPMD (single-program multiple-data) model of computing. PVM supports either or a mixture of these methods. Depending on their functions, tasks may execute in parallel and may need to synchronize or exchange data.

PVM empowers users to exploit their existing computing systems to solve much larger computational problems in various fields at minimal additional cost. PVM is getting popular in accomplishing this sort of programming model.

PVM supports programs written in C, C++, and Fortran.

jPVM is an interface written using the JavaTM native methods capability which allows Java applications to use the PVM software.

jPVM extends the capabilities of PVM to the new, exciting, hype-filled world of Java Sun Microsystems Inc.'s architecture-independent programming language for the Internet. jPVM allows Java applications and possibly applets, and existing C, C++, and Fortran applications to communicate with one another using the PVM API.

This means one can build Java interfaces to existing C, C++, and Fortran programs and use PVM to ship data from those programs to the Java interface. Or he can use this as a communications package as he transit applications from C or C++ to Java.

Also jPVM is not an implementation of PVM written in Java TM. There is a package called JPVM that is a 'PVM-like library of object classes' for parallel programming in JavaTM.

XPVM: A Graphical Console and Monitor for PVM

XPVM provides a graphical interface to the PVM console commands and information, along with several animated views to monitor the execution of PVM programs. These views provide information about the interactions among tasks in a parallel PVM program, to assist in debugging and performance tuning.

MPI is a library specification for message-passing, proposed as a standard by a broadly based committee of vendors, implementors, and users. The goal of MPI is to develop a widely used standard for writing message-passing programs. The interface attempts to establish a practical, portable, efficient, and flexible standard for message passing.

In designing MPI, the MPI forum sought to make use of the most attractive features of a number of existing message passing systems, rather than selecting one of them and adopting it as the standard. Thus, MPI has been strongly influenced by work at the IBM T. J. Watson Research Center, Intel's NX/2, Express, nCUBE's Vertex, p4, and PARMACS.

The main advantages of establishing a message-passing standard are portability and ease-of-use. In a distributed memory communication environment in which the higher level routines and/or abstractions are build upon lower level message passing routines, the benefits of standardization are particularly apparent. Also the definition of a message passing standard provides vendors with a clearly defined base set of routines that they can implement efficiently, or in some cases provide hardware support for, thereby enhancing scalability.

MPI was designed for high performance on both massively parallel machines and on workstation clusters. MPI is widely available with both free and vendor-supplied implementations.

The diverse applications of MPI are given below.

Signal and image processing, data reorganization, target recognition, SAR; medical imaging, and other military-aerospace signal and imaging applications (e.g., radar, sonar). MPI is also widely used for CFD, weather modeling, financial applications, and seismic exploration.

Also there are some specific commercial MPI tools, which provide professional message passing for high-performance, parallel computing. It improves the performance of clusters running applications such as CFD simulation, weather modeling, financial modeling, seismic exploration, and protein folding.

In addition, there are math libraries based on the Vector, Signal, and Image Processing Library, which includes linear algebra, signal processing, image processing, scalar functionality, and vector and matrix view functionality

Nowadays an increasing number of parallel machines make use of the shared memory architecture. In this type of platform each processor has acess to a global memory store and processors communicate with one another by accessing the shared memory. This communication paradigm simplifies programming multiprocessor machines by removing the requirement for explicit communications.

Parallelisation of shared memory programs is mainly carried out using compiler directives. Until recently each manufacturer provided their own set of machine specific compiler directives, though they were very similar in style and functionality, meant that programs were not trivially portable. The OpenMP standard was designed to address this issue and to provide a standard interface to shared memory architectures.

Thus OpenMP is a specification for a set of compiler directives, library routines, and environment variables that can be used to specify shared memory parallelism. Its main objective is to ensure the long-awaited promise of single source portability for shared-memory parallelism.