Abstract
A technique, permitting us to find synchronization-free parallelism in non-uniform loops, is presented. It is based on finding affine space partition mappings. The main advantage of this technique is that it allows us to form constraints for finding mappings directly in a linear form while known techniques result in building non-linear constraints which should next be linearized. After finding affine space partition mappings, well-known code generation approaches can be applied to expose loop parallelism. The technique is illustrated with two examples.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Amarasinghe, S.P., Lam, M.S.: Communication optimization and code generation for distributed memory machines. In: Proceedings of the SIGPLAN’93 (1993) 126–138
Ancourt, C., Irigoin, F.: Scanning polyhedra with do loops. In: Proceedings of the Third ACM/SIGPLAN Symposium on Principles and Practice of Parallel Programming, ACM Press (1991) 39–50
Banerjee, U.: Unimodular transformations of double loops. In: Proceedings of the Third Workshop on Languages and Compilers for Parallel Computing (1990) 192–219
Boulet, P., Darte, A., Silber, G.A., Vivien, F.: Loop paralellelization algorithms: from parallelism extraction to code generation. Technical report (1997)
Collard, J.F., Feautrier, P., Risset, T.: Construction of do loops from systems of afffne constraints. Technical Report 93-15, LIP, Lyon (1993)
Darte, A., Risset, T., Robert, Y.: Loop nest scheduling and transformations. In Dongarra, J., Tourancheau, B., eds.: Enviroments and tools for parallel science computing. North Holland (1993)
Darte, A., Silber, G., Vivien, F.: Combining retiming and scheduling techniques for loop parallelization and loop tiling. Technical Report 96-34, Laboratoire de l’Informatique du Parallelisme (1996)
Feautrier, P.: Some efficient solutions to the affine scheduling problem, part i, one dimensional time. International Journal of Parallel Programming 21 (1992) 313–348
Feautrier, P.: Some efficient solutions to the affine scheduling problem, part ii, multidimensional time. International Journal of Parallel Programming 21 (1992) 389–420
Feautrier, P.: Toward automatic distribution. Journal of Parallel Processing Letters 4 (1994) 233–244
Huang, C., Sadayappan, P.: Communication-free hyperplane partitioning of nested loops. Journal of Parallel and Distributed Computing 19 (1993) 90–102
Kelly, W., Pugh, W.: A framework for unifying reordering transformations. Technical Report CS-TR-2995. 1, University of Maryland (1993)
Kelly, W., Maslov, V., Pugh, W., Rosser, E., Shpeisman, T., Wonnacott, D.: The omega library interface guide. Technical Report CS-TR-3445, University of Maryland (1995)
Lim, W., Lam, M.S.: Communication-free parallelization via affine transformations. In: Proceedings of the Seventh Workshop on Languages and Compilers for Parallel Computing (1994) 92–106
Lim, W., Lam, M.S.: Maximizing parallelism and minimizing synchronization with affine transforms. In: Conference Record of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (1997)
Pugh, W., D. Wonnacott: An exact method for analysis of value-based array data dependences. In: Workshop on Languages and Compilers for Parallel Computing (1993)
Quillere, F., Rajopadhye, S., Wilde, D.: Generation of efficient nested loops from polyhedra. International Journal of Parallel Programming 28 (2000)
Sass, R., Mutka, M.W.: Enabling Unimodular transformations. In: Proceedings of Supercomputing’94 (1994) 753–762
Wolf, M.E.: Improving locality and parallelism in nested loops. Ph.D. Dissertation CSL-TR-92-538, Stanford University, Dept. Computer Science (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beletskyy, V. (2003). Finding Synchronization-Free Parallelism for Non-uniform Loops. In: Sloot, P.M.A., Abramson, D., Bogdanov, A.V., Gorbachev, Y.E., Dongarra, J.J., Zomaya, A.Y. (eds) Computational Science — ICCS 2003. ICCS 2003. Lecture Notes in Computer Science, vol 2658. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44862-4_100
Download citation
DOI: https://doi.org/10.1007/3-540-44862-4_100
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40195-7
Online ISBN: 978-3-540-44862-4
eBook Packages: Springer Book Archive