Project Leader

Josep Llosa  (josepll@ac.upc.es)

Project Members

Eduard Ayguade (eduard@ac.upc.es)

Mateo Valero (mateo@ac.upc.es)

Javier Zalamea (jzalamea@ac.upc.es)

---

Project description

Software Pipelining is a loop scheduling technique that extracts parallelism from loops by overlapping the execution of  everal consecutive iterations. Unfortunately, even a throughput-optimal schedule with minimum register requirements, useless if it requires more registers than those available in the target machine.

In this project we are researching techniques for producing register-constrained modulo schedules. In particular we have evaluated the alternatives of adding Spill code and increasing the II. We show that, in general, increasing the II performs poorly and might not converge for some loops. We also propose an iterative spilling mechanism that can be applied to any  software pipelining technique and several heuristics in order to select variables to spill as well as to speed-up the spilling process.

 Currently we are researching a hybrid technique that selectively adds spill code, increases the II or does both to fit the register requirements in the available registers. With this technique we achieve speed-ups of up to 2.0 while reducing the memory traffic by about 2 for loops that require more registers than available. We also plan to research new software pipelining techniques to add spill code simultaneously with the scheduling of instructions.

---

 

Relevant publications

Heuristics for Register-Constrained Software Pipelining
Josep Llosa, Eduard Ayguade, and Mateo Valero
In 29th Annual IEEE/ACM International Symposium on Microarchitecture (Micro-29), pages 250-261, December 1996

Tecnicas Avanzadas de Codigo Spill.
Javier Zalamea, Josep Llosa, Eduard Ayguade and Mateo Valero
Research report #UPC-DAC-1998-52