On optimal loop parallelization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On optimal loop parallelization

Full text

Pdf (495 KB)

Source

International Symposium on Microarchitecture archive
Proceedings of the 22nd annual workshop on Microprogramming and microarchitecture table of contents

Dublin, Ireland

Pages: 141 - 147

Year of Publication: 1989

ISBN:0-89791-324-8

Also published in ...

Authors

F. Gasperoni	Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY 10012
U. Schwiegelshohn	IBM Research Division, IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY
K. Ebcioğlu	IBM Research Division, IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598

Sponsors

IEEE-CS : Computer Society
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 18, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/75362.75411 What is a DOI?

ABSTRACT

The problem of automatic loop parallelization has received a lot of attention in the area of parallelizing compilers. Automatic loop parallelization can be achieved by several algorithms. In this paper we address the problem of time optimal parallelization of loops with conditional jumps. We prove that even for machines with unlimited resources there are simple loops for which no semantically and algorithmically equivalent time optimal program exists.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Thomas L. Adam , K. M. Chandy , J. R. Dickson, A comparison of list schedules for parallel processing systems, Communications of the ACM, v.17 n.12, p.685-690, Dec 1974 [doi>10.1145/361604.361619]
	2	A. Aiken , A. Nicolau, A Development Environment for Horizontal Microcode, IEEE Transactions on Software Engineering, v.14 n.5, p.584-594, May 1988 [doi>10.1109/32.6136]
	3	A. Aiken , A. Nicolau, Optimal loop parallelization, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.308-317, June 20-24, 1988, Atlanta, Georgia, United States
	4	Alexander Aiken , Alexandru Nicolau, Perfect Pipelining: A New Loop Parallelization Technique, Proceedings of the 2nd European Symposium on Programming, p.221-235, March 21-24, 1988
	5	Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
	6	Coffman E.G. Computer and Job-shop Scheduling Theory. John Wiley and Sons, 1976.
	7	Cytron R. Doacross: beyond vectorization for multiprocessors. In International Conference on Parallel Processing, pages 836-844, IEEE, August 1986.
	8	Ebcioglu K. Some design ideas for a VLIW architecture for sequential-natured software. In Proceedings of the IFIP WG 10.3 Working Conference on Parallel Processing, pages 1-21, North- Holland, April 1988.
	9	Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
	10	Fisher J.A. Trace scheduling: a technique for global microcode compaction. IEEE Transactions on Computers, C-30(7):478-490, July 1981.
	11	Fisher J.A. The VLIW machine: a multiprocessor for compiling scientific code. IEEE Computer, 17(7):45-53, July 1984.
	12	Foster C.C. and Riseman E.M. Percolation of code to enhance parallel dispatching and execution. IEEE Transactions on Computers, C- 21(12):1411-1415, December 1972.
	13	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	14	M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
	15	Padua D.A., Kuck D.J. and Lawrie D.H. Highspeed multiprocessors and compilation techniques. IEEE Transactions on Computers, C- 29(9):763-776, September 1980.
	16	David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
	17	Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Norwell, MA, 1988
	18	Riseman E.M. and Foster C.C. The inhibition of potential parallelism by conditional jumps. IEEE Transactions on Computers, C-21(12):1405-1411, December 1972.
	19	A. Uht, Requirements for optimal execution of oops with tests, Proceedings of the 2nd international conference on Supercomputing, p.230-237, June 1988, St. Malo, France [doi>10.1145/55364.55387]