W2A-021 Parallel programming-0.txt
ADVANCES IN ELECTRONICS AND ELECTRON PHYSICS, VOL. 85

Parallel Programming and Cray Computers

R. H. PERROTT

Department of Computer Science, Queen's University, Belfast, United Kingdom

I. INTRODUCTION

The development of sequential computers has been helped by the fact that the underlying hardware has essentially followed the same architectural model, known as the von Neumann model. The improvements in this model were caused primarily by advances in component technology; each improvement led to better performance in each generation of computers based on this model. Thus sequential computers have had a model of computation that formed a relatively stable base for the development of languages and tools. This is one of the main reasons for the widespread use of these tools and languages, however, the same cannot be said in the case of parallel machines.

Parallelism has always been utilised in component technology but only in the 1970s did it become explicitly available in a machine architecture for the programmer; e.g., the Cray-1. It was not until the 1980s that commercially available parallel machines incorporating a wide variety of architectures were introduced; e.g., AMT distributed array processor, Convex, Alliant, Hypercub, Cray X-MP.

It was the scientific community that first discovered the limitations of sequential machines in their applications. Applications such as weather forecasting were limited in their usefulness by the lack of sufficient processing power to deliver the results in a realistic time scale. The developments in component technology made it clear that the required increase in speed could never be obtained on sequential machines and that the only solution on offer was that of parallel computing.

Hence, one of the main promises of parallel processing is that the speed up in the execution of an application would be substantial and that this speed up would increase as the amount of parallelism in the system increases. As a consequence users would be able to attempt to solve larger problems as the machine's capabilities and functionality increases.

Such improvements are possible only because of the economics of mass produced VLSI components. The production of such components increasingly favours parallel systems built mainly from cheap processors. Early results of experiments using parallel machines report a price-performance advantage in the range of 10 to 30 times better than traditional machines (Wadsworth, 1988). However, such comparisons usually ignore the cost of software, in particular, the effort involved in programming the parallel machine, which has been shown to be a nontrivial exercise requiring considerable skill and expertise. The developments in parallel software are not so far reaching nor so nearly well understood as the developments in parallel hardware.

In the case of sequential computers the architectural model, the programming paradigms and the method of constructing algorithms all have a single objective. In the case of parallel computers there is at present no single architectural model to represent parallelism but rather a variety of different parallel architectures.

The main issue affecting the architectural model is how to organise multiple processors to execute in parallel. One of the first models was that of an array processor - the SIMD model - where multiple processors execute the same instruction but on different data; the processors operate under the control of a single processor, which broadcasts the instructions to be executed. Array processors are particularly suited to problems involving matrices, and some impressive results have been achieved. However, the main criticism of this model is that there is little flexibility in the architecture for problems that could benefit from the execution of different instructions at the same time - the MIMD model.

The earliest MIMD models were based on the shared memory concept, where all the processors are connected to the same memory. In this scenario the processors can execute different parts of an application concurrently, thus ideally reducing the time to execute the complete program. However, this model can lead to severe memory contention problems as the processors attempt to access the same data. There is some question as to whether this model will scale to larger orders of parallelism.

A more recent MIMD model is the distributed memory model, where each processor has its own local memory and processors communicate by passing messages. However, there is an overhead cost associated with such communication, which in many instances can be substantial. The amount of overhead is influenced by such factors as the distance between the two processors wishing to communicate and the interconnection topology. The distributed model is scalable to greater orders of parallelism than that currently implemented.

In the case of parallel software the choice of programming language is no longer confined to a single approach. The main division of these languages is into either imperative or declarative languages. The declarative group can be further divided into logic and functional languages while the imperative group consist of procedural and object-oriented languages.

All the various languages that have been proposed offer some different way of capitalising on the power of parallel machines. To date it is not clear if any one approach is substantially better than any other as enough experience has not yet been accumulated. In many cases the concepts have not been efficiently implemented on parallel machines. In addition there is a considerable lack of tools to assist in all aspects of parallel programming and debugging. One consideration, which was perhaps not so important with sequential languages, is the ability to prove a program correct. This is becoming increasingly important as parallel machines are applied to more crucial aspects of human applications. However, the criteria for judging a language's design that were established for sequential languages are still valid; criteria such as readability, simplicity, efficiency and expressiveness.

The third important aspect of programming parallel systems is the choice of algorithm. Studies have shown that transferring an efficient sequential algorithm to a parallel machine results in an inefficient parallel algorithm. It is now apparent that the design and construction of a new parallel algorithm for a particular application area can produce major performance improvements.

Hence, in the case of parallel systems there are three important and contributing factors; namely, the architectural model, the programming language and the choice of algorithm. The following sections concentrate on the programming language.

II. APPROACHES TO PARALLEL PROGRAMMING

Essentially, three main methods have been used to promote the wider use of parallel processing: (i) Extend an existing sequential language with features to represent parallelism. The advantage of extensions is that existing software can be transferred to a new parallel machine with relative cases. This is possible because programmers are already trained in the base language and can introduce the extensions gradually as they become more familiar with the situation in which they should be used and the effect they produce. However, experience to date has shown that extension languages have been limited to a certain range of hardware and to machines with a small number of processors. Problems have also been reported in the debugging of programs written in such languages, as the interaction of the sequential and the parallel features can give rise to difficulties in detecting errors. A more general problem is that many of these extensions have been developed by different groups using the same language base, which has led to nonstandard variants of the same language being produced, making the production of a standard for such languages difficult.

(ii) Implicit: use a sequential language but rely on the compiler to detect which parts of the program can be executed in parallel. Most of the work in this area is based on FORTRAN and examines the DO loops of the program to determine if it is possible to spread the iterations of the loop across different processors.

The advantage of such an approach is that existing sequential programs can be moved relatively inexpensively and quickly to the parallel machine. This can represent a substantial saving in development costs and is an attractive proposition for many purchasers of a new parallel machine. However, it is rare that the full parallelism of the program is exploited without the help of a programmer to restructure the program; this usually requires a reorganisation of the loops of the program so that the automatic detection techniques will work.

In the case of the construction of new programs it is advisable that a programmer have some knowledge of the detection techniques if as much parallelism as possible is to be detected. This represents a diversion for a programmer from the main task of program construction. In addition, such an approach inhibits the development of parallel languages and algorithms as it is confined to a sequential notation.

(iii) Develop a new parallel language. In this case a completely new parallel language is developed, ignoring all existing languages and applications. The main advantage of this approach is that a coherent approach to parallelism is presented. The parallel notation will enable a user to express directly the parallelism in an application and, in addition, will assist with the development of new parallel algorithms. However, it does mean that a user will have to rebuild the entire software base in the new language, which is a labour intensive, expensive and perhaps an error prone exercise. All existing applications are ignored, which requires courage on the part of the management of large installations, particularly since many new languages have not had the property of longevity.

III. IMPLICIT PARALLELISM

Recent years have demonstrated that parallel processors are now a viable and commercially successful product and that it is the software for these machines which is lagging behind and causing the most difficulties. The highly successful tactic of Cray in the 1970s, of providing a FORTRAN engine, a machine that would take existing FORTRAN programs and detect which parts could be automatically vectorised, is the objective for the newer breed of multiprocessors only now based on parallelism. The origins of many of these systems can be traced to the research of David Kuck at the University of Illinois on vectorisation technique. This research has been extended to incorporate the situation where many processors, possibly vector processors, share the same memory. The model used for most shared memory machines is very similar in nature. However there may be differences in how the processors and memory interact; for example, in the Cray X-MP the connections between processors and memory are direct while on the Alliant and Convex a bus is used to connect memory and processors. The latter machines incorporate a data cache memory to provide acceptable access times, but it is not significant enough to disrupt their classification as shared memory machines. Such factors are not relevant as far as the programming of these machines is concerned.

In general, the main tactic of parallelisation systems is to examine nested DO loops, with the object of vectorising the innermost loop and parallelising the outermost loop. The methods rely on data dependence analysis techniques that determine the flow of data in a program. This, in turn, enables statements to be identified that can be executed in parallel. Data dependence analysis is the cornerstone on which all automatic parallelism detection methods are built; the quality of a paralleliser is directly related to the quality of the dependence analyser.

Currently techniques are available for nested DO loops but have not yet been commercially applied to complete programs. This requires full interprocedural analysis - the tracking of data across procedure calls - to be performed on a user program. Once a compiler uses interprocedural information as a basis for compiling time decisions, data dependencies between procedures in a program can be resolved. The systems at Rice University and IBM provide a limited form of interprocedural analysis.

There are certain parallel programming situations that can be automatically parallelised without any user intervention. The most straightforward situation consists of loops with no data dependency between the iterations. In this case the iterations can be assigned to the processors either individually or in groups depending on the scheduling algorithms. In some systems the programmer can decide.

In other situations if there is a possibility of a data dependency the compiler takes a conservative view, which usually means that no parallelisation is attempted. The burden is then placed on the programmer to decide if the compiler's decision should be overridden; this is achieved by a user inserting compiler directives into the program code. This is particularly the case in situations where interprocedural analysis is required as most existing systems are not capable of performing this analysis. This is not always an easy decision and can require a considerable level of skill on behalf of the programmer. To help with parallelisation several manufacturers have incorporated into their hardware special features to handle synchronisation of the processors. This, in turn, can be used when processing, in parallel, different iterations of a DO loop that has data dependencies. For example, the Alliant machines have a concurrency control bus that is used to reduce the overhead involved in processor synchronisation and can be utilised in loops with data dependencies.
