Skip to main content
Log in

Automatic parallelization ofwhile-loops using speculative execution

  • Published:
International Journal of Parallel Programming Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. U. Banerjee, Unimodular transformations of double loops. Technical Report CRSD Rpt. No. 1036, University of Illinois (August 1990).

  2. 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).

    Article  Google Scholar 

  3. M. L. Dowling, Optimal code parallelization using unimodular transformations,Parallel Computing 16:157–171 (1990).

    Article  MathSciNet  Google Scholar 

  4. 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).

  5. C. Langauer, Loop parallelization in the polytope model, in E. Best (ed.),CONCUR '93 LNCS, Springer-Verlag,715, pp. 398–416 (1993).

  6. J. P. Bonomo and W. R. Dyksen, Pipelined iterative methods for shared memory machines,Parallel Computing 11:187–199 (1989).

    Article  MATH  Google Scholar 

  7. Y. Wu and T. G. Lewis, Parallelizing while loops, inProc. Intl. Conf. on Parallel Processing II:1–8 (1990).

    Google Scholar 

  8. M. J. Wolfe,Optimizing Supercompilers for Supercomputers, Pitman and The MIT Press (1989).

  9. A. K. Uht, Requirements for optimal execution of loops with tests, inACM Int. Conf. on Supercomputing, St. Malo, France, pp. 230–237 (July 1988).

  10. 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.

  11. 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.

  12. 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).

    Article  MATH  MathSciNet  Google Scholar 

  13. B. R. Rau and J. A. Fisher, Instruction-level parallel processing: History, overview and perspective,Journal of Supercomputing,7:9–50 (1993).

    Article  Google Scholar 

  14. P. M. Kogge,Architecture of Symbolic Computers, McGraw-Hill (1991).

  15. W. Richard Stark (ed.),Implementations of Distributed PROLOG, Series in Parallel Computing, Wiley, Chichester (1992).

    Google Scholar 

  16. R. H. Halstead,Design Requirements for Concurrent Lisp Machines, McGraw-Hill, pp. 69–105 (1989).

  17. 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).

    Article  Google Scholar 

  18. 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).

  19. 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).

  20. 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).

    Article  Google Scholar 

  21. A. Schrijver,Theory of Linear and Integer Programming, Wiley, New York (1986).

    MATH  Google Scholar 

  22. 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).

  23. 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).

  24. P. Feautrier, Dataflow analysis of scalar and array references,Int. Journal of Parallel Programming 20(1):23–53 (February 1991).

    Article  MATH  Google Scholar 

  25. C. Ancourt and F. Irigoin, Scanning polyhedra with DO loops, inProc. ACM SIGPLAN '91, pp. 39–50 (June 1991).

  26. J.-F. Collard, P. Feautrier, and T. Risset, Construction of DO loops from systems of affine constraints,Parallel Processing Letters (1995).

  27. P. Feautrier, Some efficient solution to the affine scheduling problem, part II, multidimensional time,Int. J. of Parallel Programming 21(6) (December 1992).

  28. 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).

  29. P. Feautrier and M. Raji-Werth, Systematic construction of programs for Distributed Memory computers, Technical Report 91-40, MASI, Institut Blaise Pascal (June 1991).

  30. 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).

  31. 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).

  32. P. Feautrier, Parametric integer programming,RAIRO Recherche Opérationelle 22:243–268 (September 1988).

    MATH  MathSciNet  Google Scholar 

  33. M. Barnett and Ch. Lengauer, Unimodularity considered non-essential, inProc. CONPAR 92, VAPP V, LNCS, Lyon634:659–664 (September 1992).

    Google Scholar 

  34. 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).

  35. 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).

  36. Cray Research, Cray Fortran F77 Parallel Processing Guide. Doc. #SG-3074 5.0.

  37. X. Redon and P. Feautrier, Scheduling reductions, inSupercomputing '94, Manchester, England (July 1994). ACM.

Download references

Author information

Authors and Affiliations

Authors

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

Reprints 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

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02577789

Key words

Navigation