ISSN:
1573-7640
Keywords:
Recurrence
;
static data flow
;
pipelining
;
companion pipeline
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract This paper investigates the principles of mapping linear recurrences on static data flow computers. For a linear recurrence with a single variable, the key is to properly introduce a feedback loop in the machine level data flow graphs. We show that, in order to achieve maximum pipelining, thecritical dependence delay of the recurrence must be matched with the necessarycomputational delay of the graph. Two possible mapping techniques are discussed, which are (1) changing the dependence delay by introducing an additional companion pipeline; (2) changing the computational delay by inserting FIFOs. The mapping of the Valfor-iter construct, the major language feature for expressing recurrences in Val, is outlined.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01414442
