Parallel Computing and APL
Vector 5:4, page 113
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 113
Abstract¶
Parallel computing is a subject rapidly increasing in importance. Parallel hardware has been available for some time. With the advent of chips such as the Transputer some of the hardware is beginning to demonstrate a level of technical maturity. Development of software has not progressed at the same speed. Useable operating systems for transputer based machines are only now appearing. Programming languages and the development of applications lag further behind. Much of the historical effort has concentrated on the development of parallelizing compilers for existing sequential language code. This paper shows how APL is already a highly developed parallel language and with some functional extensions can be made even more effective as a parallel language.
Introduction¶
The speed of development of computer hardware is such that the physical limits of design are rapidly being approached. The essential limits are in terms of:
SIZE ………………………… pathways only a few atoms wide
SPEED ……………………… close juxtaposition to shorten pathways
COMPLEXITY ……………… packing densities and connection patterns
Even with the development of quantum well devices [BATE88], the gains to be made are less than those already made in the development of semi-conductor devices.
Once physical limits have been reached, gains in speed will have to be derived by executing more than one instruction at a time - parallel processing. The performance gains that can be obtained by the use of parallel computing are almost limitless. The problem that remains is making use of the existing parallel hardware; parallel software is still in a relatively primitive state.
Classification of Parallelism¶
The range of parallel hardware already available is quite extensive. A difficulty arises over the classification of exactly what is parallel and what is not. The definitions of distributed and parallel machines certainly overlap. A range of taxonomies have been defined.
The simplest of these, by Flynn [SHARP87], describes the following classes:
SISD ………… Single instruction, single data (normal sequential processing)
SIMD ………… Single instruction, multiple data (vector processors)
MISD ………… Multiple instruction, single data (very rare, pipe-lines perhaps)
MIMD ………… Multiple instruction, multiple data (full parallel processing)
This classification is good for distinguishing between more traditional machine types (e.g. sequential and vector processors) and the truly parallel processors. It achieves little in terms of classifying the types of parallel machine. Sharp [SHARP87] refines Flynn’s classification scheme by sub-dividing the MIMD class into two. The MISD class can be regarded as a special case of the first of these new classes. Sharp’s full scheme is as follows:
SPS …………… Single processor executing scalar data (SISD)
SPA …………… Single processor executing array data (SIMD)
MPS …………… Multi-processor executing scalar data (MISD + MIMD)
MPA …………… Multi-processor executing array data (MIMD)
Classification of Software¶
The classification of hardware is a complex subject because there are many potential mechanisms for implementing parallelism. As far as software is concerned, the problem is much simpler. We will want to:
- Execute a single process on a scalar or array (SPS, SPA)
- Execute multiple processes on a scalar or array (MPS, MPA)
- Execute multiple processes on multiple arrays (MPA)
The divide is between function and data, the classification made by Sharp is ideal.
Parallel Software¶
Much of the research into parallel software has been dedicated to the conversion of sequential software (i.e. existing applications) into parallel software. This is to facilitate the execution of existing libraries of code on faster and more powerful parallel hardware.
The research has fallen into 3 main categories:
- Conversion of multi-tasking to parallel-tasking
- Parallelizing compilers
- New parallel languages or parallel extensions to existing languages
Multi-tasking to Parallel-tasking¶
Many uni-processor systems have emulated a form of parallel processing by the use of multi-tasking systems software. Even relatively simple single user operating systems have rudimentary multi-tasking facilities (e.g. the MS/DOS PRINT command).
The conversion of such multi-tasking systems to true parallel processing is an obvious, and fairly trivial task. A number of problems with the conversion concept can be identified, in particular there may be a failure to take advantage of all the opportunities for parallel processing. Since multi-tasking is a special feature implemented on uni-processor systems via carefully written systems software, not all the available opportunities for multi-tasking will have been taken advantage of. The cost involved in providing more and more multi-tasking capabilities is too great. The literal conversion from single processor to parallel processing systems will similarly fail to take advantage of all available opportunities for parallelism.
Much of the cost advantage provided by a conversion-only exercise will be lost if a more substantial process of re-writing is undertaken. This may, however, be the only realistic way to gain more significant benefits from parallel processing.
Even if operating system software is fully converted to parallel processing, all of the application software still has to be converted. Existing applications will continue to be non-parallel, many of the potential performance benefits remaining unrealised.
Parallelizing Compilers¶
Another approach to the introduction of parallelism is the creation of parallelizing compilers. These take sequential source code and attempt to detect, and take advantage of, the opportunities for parallel processing inherent in all such code.
The disadvantages of this approach are similar to those discussed above. In particular a parallelizing compiler can only detect parallelism in the code as it is currently written. There may exist other, explicitly parallel, algorithms which are more efficient. Perhaps knowledge based systems offer opportunities here - an intelligent parallelizing compiler that can recognise sequential algorithms and can substitute more efficient parallel ones.
There is however an additional cost. A great deal of effort may have been put into optimising the sequential algorithm, this will be wasted in the conversion to parallel processing. In addition, the optimised algorithm may be more difficult to translate into parallel code than a naive sequential algorithm.
The technologies discussed in this and the previous sections are essentially linked to migration/conversion exercises. The importance of this issue should not be underestimated; it is, however, a technology with a finite lifetime. Eventually the development of new parallel code will become the dominant issue and a key task in the search for increasing speed of execution.
Languages with Parallel Constructs¶
By far the best approach to the creation of parallel code is the use of explicitly parallel languages. These come in two major forms:
- parallel versions of existing languages (e.g. DAP-FORTRAN, PARLOG)
- new languages with explicit parallel constructs (e.g. OCCAM)
A major criticism can be levelled at both the above approaches - the parallelism still has to be programmed in; it does not arise as a natural consequence of the language syntax and algorithms used. The programmer is responsible for administering the parallelism, deciding which sections can be executed in parallel and which must be performed sequentially. As well as being difficult, this introduces a new potential source of errors into the programming process.
Even new parallel languages such as OCCAM are essentially enriched sequential languages, relying on constructs such as FOR-NEXT loops (though these may be executed in parallel). The code produced by the programmer is essentially sequential with some instructions to permit parallel execution. There is no encouragement to think in terms of parallel processes, and the instructions to permit parallelism may be omitted without penalty (until execution time).
Functional Languages¶
The functional programming paradigm has been proclaimed as being of great value for parallel processing. Many functional languages have been implemented, but few have achieved much commercial success. Perhaps the major exception is LISP. [MICH89] describes functional languages as having the following properties:
- a name is only ever associated with one value
- there is no fixed execution order
- new values are associated with new names via recursion or function calls
- functions can be treated as values
Following from the second property, functional languages provide many opportunities for parallel execution without formal language constructs. If there is no fixed execution order, then the constituent parts of a program may be executed in parallel. Since the parallelism is derived from functional independence, functional languages are best suited to the MPS form of parallelism.
APL as a Parallel Language¶
APL has some significant advantages for the implementation of parallel processing systems:
- parallelism is inherent in the language.
- many of the features of functional languages can also be found in APL.
In addition, by adding a single consistent extension to APL, the opportunities for parallelism can be significantly increased.
SPA Parallelism and APL¶
Single Process, Array data (SPA) parallelism is the form easiest to see in APL, it is apparent in even the simplest APL statements. Conversely, it is frequently the most difficult to implement in other forms of parallel language; this is especially true for functional programming languages. The difficulty arises from the recursive nature of such languages. Parallelizing compilers normally try to pick out this form of parallelism by looking closely at loops or recursion and attempting to “untangle” them in some way.
The difficulties of implementing SPA parallelism are discussed in detail in [SHARP87], chapter 9. On the last page of this chapter, the following appears:
“This chapter has, hopefully, indicated that some problems which initially do not appear suited to array processing may indeed be amenable to such methods. Any APL programmer will need little convincing of that, for many APL one-liners rely on manipulating vectors and matrices as whole objects. It might be argued that rather than adapting strictly sequential languages such as FORTRAN, we ought to have looked at compiling APL for array processes.....”
Consider the following APL statement:
If A and B are arrays, SPA parallelism is immediately apparent. This simplicity of implementation is the basis of IBM’s VECTOR processor version of APL2. The compilation of such code is discussed in [CHING88], which includes examples of the ease of translation into vector processor code. These points are also discussed in [BROWN88], and other examples are given in [BUCHHOLZ86].
Opportunities for SPA parallelism are increased in APL implementations with nested arrays. The EACH operator applies a function to each of the items in its argument(s). Thus if C is a nested array:
returns the shape of each item of C; perhaps the EACH operator should be renamed the PARALLEL operator! Using EACH, SPA parallelism can be applied to non-scalar (and thus, in APL2 nomenclature, non-pervasive) functions.
MPS/MPA Parallelism in APL¶
APL presents natural opportunities for Multi-Process parallelism (on scalar or array data). These are founded on the same basis as the implementation of MPS parallelism in functional languages. Consider the following fragment of function code:
Since the following points are all true:
- C is not changed after its initial assignment
- the result of each line is assigned to a different variable
- the third line makes no use of D
the order of execution of the last two lines of code is immaterial; they may, therefore, be executed in parallel. The same argument can be applied to the parallel execution of defined functions:
Assuming CALC1 and CALC2 have no global side effects, then parallel processing is possible for the first two lines. Note this is an additional argument for the avoidance of global variables. Note also that coalescing the lines of code has no effect on the potential for parallelism:
Whilst functional languages limit this form of parallelism to MPS (scalar data), APL allows both MPS and MPA parallelism. This results from APL’s ability to operate independently of the rank and shape of its data (subject to the constraints of conformability).
Extending APL for more Parallelism¶
One frequent proposal for the extension of APL is the implementation of function arrays. This has been discussed elsewhere in VECTOR (see for example [PIPER89] and the references given therein).
The case for function arrays is best illustrated by some simple examples:
can (in versions of APL that support strand notation) also be written:
a very similar expression:
has no equivalent compact form. The implementation of function arrays provides this compact form:
the expression:
is a function vector.
The applicability of such function arrays to parallel processing should be immediately apparent. User defined functions can also be stranded, so we can re-write the above example as follows:
Note that A and B have to be enclosed so that scalar extension is applied.
Pipe-lining in APL¶
One technique provided by the ability to strand functions is that of pipe-lining. For example, to read a file, format the resulting data and write an output file, code like the following might be written:
[..] EOF←0
[..] START:→EOF/END
[..] (EOF DATA)←READ_INP FILE
[..] RPT←FORMAT DATA
[..] WRITE_RPT REPORT
[..] →START
[..] END:
This may not be executed in parallel since it violates one of the rules listed in section 3.2 - the execution of each line depends on the result of the previous line. If function arrays can be used, however, a more concise formulation can be written:
[..] (DATA RPT)←↓''
[..] EOF←0
[..] START:→EOF/END
[..] (RPT EOF DATA)←(WRITE_RPT FORMAT READ_INP)RPT DATA FILE
[..] →START
[..] END:
The pipe-line construct in the above example permits the re-introduction of parallelism at least to a limited degree. All the functions execute once in parallel then wait for the rest to catch up, before iterating around the loop and commencing again. Note that at the end of file, additional processing is required to allow the FORMAT and WRITE_RPT functions to catch up and process the last couple of records.
Are Function Arrays Needed?¶
If we look at the above example carefully, we can see that by placing the 3 processing statements inside a subsidiary function we can achieve an identical result without function arrays:
[..] (DATA RPT)←↓''
[..] EOF←0
[..] START:→EOF/END
[..] (RPT EOF DATA)←PROC_REPORT RPT DATA FILE
[..] →START
[..] END:
∇RES←PROC_REPORT PARMS;DATA;FILE;RPT
[1] (RPT DATA FILE)←PARMS
[2] WRITE_RPT RPT
[3] RPT←FORMAT DATA
[4] (EOF DATA)←READ_INP FILE
[5] RES←(RPT EOF DATA)
∇
Despite this, I believe the explicit pipeline using function arrays is much clearer and more easily understood. If (under APL2) we implement an UNTIL operator, we can eliminate the coded loop from our function:
Note the right operand indicates which item of the explicit result is to be tested for the end condition. Also the left operand is the entire function vector, an array of functions being regarded as a function in its own right.
Compiling Parallel APL¶
The idea of compiling APL is now widely accepted. Several commercial products have already reached the market place. A compiler for a parallel APL could easily match the capabilities and performance of compilers for other parallel languages.
For badly written scalar-style APL code, the compiler could make use of all the technique in parallelizing compilers for other languages to optimise the APL code (perhaps this could even be de-compiled to show how the code could have been better written). At the very minimum, a parallel APL compiler could produce performance equivalent to a parallelizing compiler for a sequential language. If the full richness of the parallel constructs is utilised, better performance should be available.
Conclusions¶
Parallel computing is becoming more and more important as a technology. Hardware products are becoming increasingly commercially available, machines such as the Transputer have achieved a certain degree of acceptance in the market place. IBM’s entry into the commercial world with the 3090 Vector Processor signals another stage in the development of commercial parallel hardware.
Currently the weakness in parallel technology is the lack of effective parallel programming tools. APL represents an excellent parallel programming tool of unparalleled (sic) power. The parallelism is inherent in the APL syntax. Unlike functional programming languages, APL presents opportunities for SPA, MPS and MPA form of parallelism. All these forms are available without any additional language constructs.
The possibilities for parallelism can be further enriched in APL by the addition of arrays of functions. These do not necessarily provide additional opportunities for parallelism, they do, however, make existing opportunities easier to exploit.
References¶
[BATE88] The Quantum Effect Device: Tomorrows Transistor R.T. Bate, Scientific American Trends in Computing Special Issue (Scientific American, March 1988)
[BROWN88] An APL2 Description of the IBM 3090 Vector Facility Dr J. Brown, Proceedings APL88.
[BUCHHOLZ86] The IBM S/370 Vector Architecture W. Buchholz, IBM Systems Journal, Vol 25, No 1. 1986
[CHING88] A Vector Code Back End of the APL370 Compiler on IBM3090 Wai-Mee Ching and Andrew Xu, Proceedings APL88.
[MICHEALSON89] An Introduction to Functional Programming through Lambda Calculus G. Michealson, Addison-Wesley ISBN 0-201-17812-5
[PIPER89] Some Notes on Arrays of Functions D.B. Piper, Vector, Vol 6, No 1. July 1989
[SHARP87] An Introduction to Parallel and Distributed Processing J.A. Sharp, Blackwell Scientific Publications ISBN 0-632-01462-8
Other Sources of Information¶
Function Assignment and Arrays of Functions Dr J. Brown, Proceedings APL84.
Chips for Advanced Computing James Mundl, Scientific American Trends in Computing Special Issue (Reprinted from Scientific American, October 1987)
Programming for Advanced Computing D. Gelenter, Scientific American Trends in Computing Special Issue (Reprinted from Scientific American, October 1987)
Science Now, BBC Radio 4, 2nd January 1989
Private Communications R.J. Cocking, 1988
Private Communications D.M. Ziemann, 1988