Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Structured Scheduling of Recurrence Equations: Theory and Practice

Patrice QuintonContact Information and Tanguy RissetContact Information

(7)  Irisa, Campus de Beaulieu, 35042 Rennes Cedex, France
(8)  LIP, ENS Lyon, 46 allée d’Italie, 69364 Lyon Cedex 07
Abstract
We present new methods for scheduling structured systems of recurrence equations. We introduce the notion of structured dependence graph and structured scheduling. We show that the scheduling of recurrence equations leads to integer linear programs whose practical complexity is O(n3), where n is the number of constraints. We give new algorithms for computing linear and multi-dimensional structured scheduling, using existing techniques for scheduling non-structured systems of affine recurrence equations. We show that structured scheduling is more than one order of magnitude more efficient than the scheduling of corresponding inlined systems.

Keyword  parallelization of loop nests - structured recurrence equations - scheduling - automatic synthesis of parallel architectures - parallel vlsi architectures


Contact Information Patrice Quinton
Email: quinton@irisa.fr

Contact Information Tanguy Risset
Email: trisset@ens-lyon.fr
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb19
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)