A New class of algorithms for software pipelining with resource constraints

Abstract : This report presents a new class of algorithms for loop software pipelining in the presence of resource constraints. This new approach allows to generate optimal code with restect to throughput even for processors with complex resource constraints which make them hard to program even by hand. It consists of two steps : first, we build the reservation table for the body of the software pipelined loop by packing the elementary reservation tables of the different tasks as if the tasks were independent, the length of the global reservation tables then determines the throughput of the loop, second we determine the schedule of each iteration of the loop so that all data dependencies are satisfied and the resource usage conforms with the previously computed reservation table. We show that, in order to reach the optimal throughput (induced by the highest used resource or critical resource), the loop may need to be unrolled. In some important and general cases, we provide theoretical results on the unwinding degree necessary to achieve the optimal throughput. We also show how this class of softaware pipelining algorithms can be used to generate code for the explicitly advanced pipelines found in the Intel i860 processor.
Type de document :
[Research Report] RR-2033, INRIA. 1993
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:58:05
Dernière modification le : vendredi 16 septembre 2016 - 15:19:38
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:00:58



  • HAL Id : inria-00074638, version 1



Christine Eisenbeis, D. Windheiser. A New class of algorithms for software pipelining with resource constraints. [Research Report] RR-2033, INRIA. 1993. 〈inria-00074638〉



Consultations de la notice


Téléchargements de fichiers