loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
1995 IEEE International Conference on Application-Specific Array Processors (ASAP'95)
Revisiting the Decomposition of Karp, Miller and Winograd
Strasbourg, France
July 24-July 26
ISBN: 0-8186-7109-2
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
Usage of this product signifies your acceptance of the Terms of Use.