HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 3:58:05 PM
Last modification on : Friday, February 4, 2022 - 3:23:52 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:00:58 PM


  • 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⟩



Record views


Files downloads