A new guaranteed heuristic for the software pipelining problem.

We present yet another heuristic for the software pipelining problem. We believe this heuristic to be of interest because it brings a new insight to the software pipelining problem by establishing its deep link with the circuit retiming problem. Also, in the single resource class case, our new heuristic is guaranteed, with a better bound than that of Gasperoni and Schwiegelshohn's heuristic. Finally, we point out that, in its simplest form, our algorithm has a lower complexity.Nous présentons une nouvelle heuristique pour le problème du pipeline logiciel. Nous montrons, par cette nouvelle approche, l'existence d'un lien étroit entre le problème du pipeline logiciel et le problème de resynchronisation des circuits. De plus, nous montrons que dans le cas de ressources identiques, notre heuristique est garantie (avec une borne de garantie meilleure que celle obtenue pour l'heuristique de Gasperoni et Schwiegelshohn) et, dans sa forme non optimisée, une complexité moindre