loading...
On the Removal of Anti and Output Dependences
Chicago, IL August 19-August 23
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ASAP.1996.5428291996 IEEE International Conference on ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
P. Calland, A. Darte, Y. Robert, F. Vivien, "On the Removal of Anti and Output Dependences," Application-Specific Systems, Architectures and Processors, IEEE International Conference on, pp. 353, 1996 IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP'96), 1996.
 
 
BibTex
x
 
@article{ 10.1109/ASAP.1996.542829,
author = {P. Calland and A. Darte and Y. Robert and F. Vivien},
title = {On the Removal of Anti and Output Dependences},
journal ={Application-Specific Systems, Architectures and Processors, IEEE International Conference on},
volume = {0},
year = {1996},
issn = {1063-6862},
pages = {353},
doi = {http://doi.ieeecomputersociety.org/10.1109/ASAP.1996.542829},
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 - On the Removal of Anti and Output Dependences
SN - 1063-6862
SP
EP
A1 - P. Calland,
A1 - A. Darte,
A1 - Y. Robert,
A1 - F. Vivien,
PY - 1996
KW - node splitting
KW - anti dependences
KW - output dependences
KW - dependence graph
KW - NP-completeness
KW - heuristics
VL - 0
JA - Application-Specific Systems, Architectures and Processors, IEEE International Conference on
ER -
 
In this paper we build upon results of Padua and Wolfe who introduce two graph transformations to eliminate anti and output dependences. We first give a unified framework for such transformations. Then, given a loop nest, we aim at determining which statements should be transformed so as to break artificial cycles involving anti or output dependences. The problem of finding the minimum number of statements to be transformed is shown to be NP-complete in the strong sense, and we propose two efficient heuristics.
Index Terms:
node splitting, anti dependences, output dependences, dependence graph, NP-completeness, heuristics
Citation:
P. Calland, A. Darte, Y. Robert, F. Vivien, "On the Removal of Anti and Output Dependences," asap, pp.353, 1996 IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP'96), 1996
Usage of this product signifies your acceptance of the Terms of Use.