Memory requirements for parallel programs

Parallel execution is normally used to decrease the amount of time required to nun a program. However, the parallel execution may require far more spa ce than that required by the sequential execution. Worse yet, the parallel space requirement may be very much more difficult to predict than the seque ntial space requirement because there are more factors to consider. These i nclude essentially nondeterministic factors that can influence scheduling, which in turn may dramatically influence space requirements. We survey some scheduling algorithms that attempt to place bounds on the amount of time a nd space used during parallel execution. We also outline a direction for fu ture research. This direction takes us into the area of functional programm ing, where the declarative nature of the languages can help the programmer to produce correct parallel programs, a feat that can be difficult with pro cedural languages. Currently the high-level nature of functional languages can make it difficult for the programmer to understand the operational beha vior of the program. We look at some of the problems in this area, with the goal of achieving a programming environment that supports correct, efficie nt parallel programs. (C) 2000 Published by Elsevier Science B.V. All right s reserved.