Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074638
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 3:58:05 PM
Last modification on : Thursday, February 11, 2021 - 2:50:07 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:00:58 PM

Identifiers

  • HAL Id : inria-00074638, version 1

Collections

Citation

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

Share

Metrics

Record views

196

Files downloads

177