×

Architecture-independent loop parallelisation. (English) Zbl 0952.68033

Distinguished Dissertations. London: Springer. xviii, 172 p. (2000).
The distinguished Dissertation by R. C. Calinescu addresses the automatic parallelization of regular loop computations involving dense data structures. An extensive collection of parallelization techniques is presented for template-matching scheduling of loop computations using the BSP-model as target platform. The two types of loop nest parallelization techniques of 1. template-matching and 2. automatic parallelization techniques are addressed in this work in Chapters 5 (40 pages) and 6 (23 pages).
Their exposition uses almost half of the work, which is organized in 9 chapters and 4 appendices, of which we list only the titles: 1. Introduction, 2. Bulk-synchronous parallel model 5, 3. Data dependence analysis and code transformation, 13, 4. Communication overheads in loop nest scheduling, 23, 5. Template-matching parallelization, 43, 6. Generic loop nest parallelization, 85, 7. A strategie and a tool for architecture-independent loop parallelization, 109, 8. The effectiveness of architecture-independent loop parallelization, 125, 9. Conclusion, 139, Appendix A. Theorem proofs, 145, Appendix B. Syntax of the BSPscheduler input language, 151, Appendix C. Syntax of the BSPscheduler output language, 155, Appendix D. Automatically generated code for example 7.5, 157, Bibliography, 161, Index, 171.

MSC:

68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
68-02 Research exposition (monographs, survey articles) pertaining to computer science
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68N20 Theory of compilers and interpreters
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDFBibTeX XMLCite