Circuit retiming applied to decomposed software pipelining

Pierre-Yves Calland 1 Alain Darte 2 Yves Robert 1
1 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : This paper elaborates on a new view on software pipelining, called decomposed software pipelining. The approach is to decouple the problem into resource constraints and dependence constraints. Resource constraints management amounts to scheduling an acyclic graph subject to resource constraints for which an efficiency bound is known, resulting in a bound for loop scheduling. The acyclic graph is obtained by cutting some particular edges of the (cyclic) dependence graph. In this paper, we cut edges in a different way, using circuit retiming algorithms, so as to minimize both the longest dependence path in the acyclic graph, and the number of edges in the acyclic graph. With this technique, we improve the efficiency bound given for Gasperoni and Schwlegelshohn algorithm, and we reduce the constraints that remain for the acyclic problem. We believe this framework to be of interest because it brings a new insight into the software problem by establishing its deep link with the circuit retiming problem
Type de document :
Article dans une revue
IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 1998, 9 (1), pp.24-35. 〈10.1109/71.655240〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00856850
Contributeur : Equipe Roma <>
Soumis le : lundi 2 septembre 2013 - 16:04:53
Dernière modification le : vendredi 20 avril 2018 - 15:44:24

Lien texte intégral

Identifiants

Collections

Citation

Pierre-Yves Calland, Alain Darte, Yves Robert. Circuit retiming applied to decomposed software pipelining. IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 1998, 9 (1), pp.24-35. 〈10.1109/71.655240〉. 〈hal-00856850〉

Partager

Métriques

Consultations de la notice

116