Abstract | ||
---|---|---|
This paper elaborates on a new view on software pipelining, called decomposed software pipelining, and introduced by Gasperoni and Schwiegelshohn, and by Wang, Eisenbeis, Jourdan, and Su. 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 Schwiegelshohn 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. |
Year | DOI | Venue |
---|---|---|
1998 | 10.1109/71.655240 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | Field | DocType |
resource constraints management amount,software problem,acyclic graph,dependence graph,dependence constraint,circuit retiming applied,longest dependence path,decomposed software pipelining,resource constraint,acyclic problem,acyclic graph subject,computer architecture,kernel,resource management,computational complexity,software pipelining,vliw,circuits,software engineering | Retiming,Acyclic dependencies principle,Strength of a graph,Software pipelining,Computer science,Parallel computing,Directed acyclic graph,Real-time computing,Moral graph,Feedback arc set,Directed acyclic word graph,Distributed computing | Journal |
Volume | Issue | ISSN |
9 | 1 | 1045-9219 |
Citations | PageRank | References |
26 | 0.97 | 9 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
pierreyves calland | 1 | 84 | 6.16 |
Alain Darte | 2 | 888 | 56.40 |
Yves Robert | 3 | 850 | 68.62 |