Abstract
Automatic parallelization of imperative sequential programs has focused on nests offor-loops. The most recent of them consist in finding an affine mapping with respect to the loop indices to simultaneously capture the temporal and spatial properties of the parallelized program. Such a mapping is usually called a “space-time transformation.”
This work describes an extension of these techniques towhile-loops using speculative execution. We show that space-time transformations are a good framework for summing up previous restructuration techniques ofwhile-loop, such as pipelining. Moreover, we show that these transformations can be derived and applied automatically.
Similar content being viewed by others
References
U. Banerjee, Unimodular transformations of double loops. Technical Report CRSD Rpt. No. 1036, University of Illinois (August 1990).
M. S. Lam and M. E. Wolf, A loop transformation theory and an algorithm to maximize parallelism,IEEE Trans. on Parallel and Distributed Systems 2(4):452–471 (October 1991).
M. L. Dowling, Optimal code parallelization using unimodular transformations,Parallel Computing 16:157–171 (1990).
B. Lisper, Detecting static algorithms by partial evaluation, inProc. ACM SIGPLAN Symposium on Partial Evaluation and Semantics Based Program Manipulation, pp. 31–42 (June 1991).
C. Langauer, Loop parallelization in the polytope model, in E. Best (ed.),CONCUR '93 LNCS, Springer-Verlag,715, pp. 398–416 (1993).
J. P. Bonomo and W. R. Dyksen, Pipelined iterative methods for shared memory machines,Parallel Computing 11:187–199 (1989).
Y. Wu and T. G. Lewis, Parallelizing while loops, inProc. Intl. Conf. on Parallel Processing II:1–8 (1990).
M. J. Wolfe,Optimizing Supercompilers for Supercomputers, Pitman and The MIT Press (1989).
A. K. Uht, Requirements for optimal execution of loops with tests, inACM Int. Conf. on Supercomputing, St. Malo, France, pp. 230–237 (July 1988).
M. Griebl and Ch. Lengauer, On the space-time mapping of while-loops,Parallel Processing Letters (1994). To appear. Also available as Report MIP-9304, Fakultät für Mathematik und Informatik, Universität, Passau, Germany.
M. Griebl and C. Lengauer, On scanning space-time mapped while loops, in B. Buchberger, ed.,Parallel Processing: CONPAR 94-VAPP VI, Lecture Notes in Computer Science 854:677–688, Linz, Austria (1994). Springer-Verlag.
P. Feautrier, Some efficient solutions to the affine scheduling problem, part I, on dimensional time,Int. J. of Parallel Programming 21(5):313–348 (October 1992).
B. R. Rau and J. A. Fisher, Instruction-level parallel processing: History, overview and perspective,Journal of Supercomputing,7:9–50 (1993).
P. M. Kogge,Architecture of Symbolic Computers, McGraw-Hill (1991).
W. Richard Stark (ed.),Implementations of Distributed PROLOG, Series in Parallel Computing, Wiley, Chichester (1992).
R. H. Halstead,Design Requirements for Concurrent Lisp Machines, McGraw-Hill, pp. 69–105 (1989).
P. P. Tirumalai, M. Lee, and M. S. Schlansker, Parallelization of while loops on pipelined architectures,Journal of Supercomputing 5(2/3):119–136 (1991).
M. D. Smith, M. A. Horowitz, and M. S. Lam, Efficient superscalar performance through boosting,Proc. of the Fifth Int'l. Conf. on Architectural Support for Programming Languages and Operating Systems, pp. 248–259 (October 1992).
M. S. Lam and R. P. Wilson, Limits of control flow on parallelism, inProc. of the 19th Ann. Int'l. Symp. on Computer Architecture, pp. 46–57 (May 1992).
B. Ramkumar and L. V. Kalé, A join algorithm for combining AND parallel solutions in AND/OR parallel systems,Int. J of Parallel Programming 21(1):67–107 (1992).
A. Schrijver,Theory of Linear and Integer Programming, Wiley, New York (1986).
C. Ancourt, Code generation for data movements in a hierarchical memory machine,Int'l. Workshop on Compilers for Parallel Computers, MASI, Paris, pp. 91–102 (1990).
M. A. Ertl and A. Krall, Delayed exceptions—speculative execution of trapping instructions, in P.A. Fritzson (ed.),Int. Conf. on Compiler Construction, Springer-Verlag, Edinburgh, U.K.,LNCS 786:158–171 (April 1994).
P. Feautrier, Dataflow analysis of scalar and array references,Int. Journal of Parallel Programming 20(1):23–53 (February 1991).
C. Ancourt and F. Irigoin, Scanning polyhedra with DO loops, inProc. ACM SIGPLAN '91, pp. 39–50 (June 1991).
J.-F. Collard, P. Feautrier, and T. Risset, Construction of DO loops from systems of affine constraints,Parallel Processing Letters (1995).
P. Feautrier, Some efficient solution to the affine scheduling problem, part II, multidimensional time,Int. J. of Parallel Programming 21(6) (December 1992).
J.-F. Collard, Space-time transformation of while-loops using speculative execution, inProc. of the 1994 Scalable High Performance Computing Conf., IEEE Knoxville, Tenn., pp. 429–436 (May 1994).
P. Feautrier and M. Raji-Werth, Systematic construction of programs for Distributed Memory computers, Technical Report 91-40, MASI, Institut Blaise Pascal (June 1991).
J.-F. Collard and P. Feautrier, Automatic generation of data parallel code, in H.J. Sips (ed.),Proc. of the Fourth International Workshop on Compilers for Parallel Computers, Delft, The Netherlands, pp. 321–332 (December 1993).
P. Gachet, Ch. Mauras, P. Quinton, and Y. Saouter, A. language for the design of regular parallel algorithms, in F. Andre and J.P. Verjus (eds.),First European Workshop on Hypercube and Distributed Computers, Rennes, France, pp 189–202, North-Holland (October 1989).
P. Feautrier, Parametric integer programming,RAIRO Recherche Opérationelle 22:243–268 (September 1988).
M. Barnett and Ch. Lengauer, Unimodularity considered non-essential, inProc. CONPAR 92, VAPP V, LNCS, Lyon634:659–664 (September 1992).
J. Xue, An algorithm to automate non-unimodular transformations of loop nests, inThe 5th IEEE Symp. on Parallel and Distributed Processing, IEEE Computer Society Press, pp. 512–519 (1993).
W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery,Numerical Recipes in FORTRAN-The Art of Scientific Computing (2nd Ed.), Cambridge U. Press (1992).
Cray Research, Cray Fortran F77 Parallel Processing Guide. Doc. #SG-3074 5.0.
X. Redon and P. Feautrier, Scheduling reductions, inSupercomputing '94, Manchester, England (July 1994). ACM.
Author information
Authors and Affiliations
Additional information
Partly supported by the French CNRS Coordinated Research Program on Concurrency, Communication and Cooperation C3, PRC/MRE contract ParaDigme and DRET contract 91/1180
Rights and permissions
About this article
Cite this article
Collard, JF. Automatic parallelization ofwhile-loops using speculative execution. Int J Parallel Prog 23, 191–219 (1995). https://doi.org/10.1007/BF02577789
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02577789