Revisiting the Decomposition of Karp, Miller and Winograd

Strasbourg, France July 24-July 26

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/ASAP.1995.522901

1995 IEEE International Conference on ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Alain Darte Articles by Fredric Vivien

	ASCII Text	x
	Alain Darte, Fredric Vivien, "Revisiting the Decomposition of Karp, Miller and Winograd," Application-Specific Systems, Architectures and Processors, IEEE International Conference on, pp. 13, 1995 IEEE International Conference on Application-Specific Array Processors (ASAP'95), 1995.

	BibTex	x
	@article{ 10.1109/ASAP.1995.522901, author = {Alain Darte and Fredric Vivien}, title = {Revisiting the Decomposition of Karp, Miller and Winograd}, journal ={Application-Specific Systems, Architectures and Processors, IEEE International Conference on}, volume = {0}, year = {1995}, issn = {1063-6862}, pages = {13}, doi = {http://doi.ieeecomputersociety.org/10.1109/ASAP.1995.522901}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Application-Specific Systems, Architectures and Processors, IEEE International Conference on TI - Revisiting the Decomposition of Karp, Miller and Winograd SN - 1063-6862 SP EP A1 - Alain Darte, A1 - Fredric Vivien, PY - 1995 KW - Uniform recurrence equations KW - multi-dimensional scheduling KW - automatic parallelization VL - 0 JA - Application-Specific Systems, Architectures and Processors, IEEE International Conference on ER -

Alain Darte, Ecole Normale Sup_rieure de Lyon

Fredric Vivien, Ecole Normale Sup_rieure de Lyon

This paper is devoted to the construction of multi-dimensional schedules for a system of uniform recurrence equations. We show that this problem is dual to the problem of computability of a system of uniform recurrence equations. We propose a new study of the decomposition algorithm first proposed by Karp, Miller and Winograd: we base our implementation on linear programming resolutions whose duals give exactly the desired multi-dimensional schedules. Furthermore, we prove that the schedules built this way are optimal up to a constant factor.

Index Terms:

Uniform recurrence equations, multi-dimensional scheduling, automatic parallelization

Citation:

Alain Darte, Fredric Vivien, "Revisiting the Decomposition of Karp, Miller and Winograd," asap, pp.13, 1995 IEEE International Conference on Application-Specific Array Processors (ASAP'95), 1995

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.