Titre du document / Document title

Cyclo-static dataflow

Auteur(s) / Author(s)

BILSEN G. ⁽¹⁾ ; ENGELS M. ⁽¹⁾ ; LAUWEREINS R. ⁽¹⁾ ; PEPERSTRAETE J. ⁽¹⁾ ;

Affiliation(s) du ou des auteurs / Author(s) Affiliation(s)

⁽¹⁾ Katholieke Universiteit Leuven, Department E.S.A.T., Kardinal Mercierlaan, Leuven, BELGIQUE

Résumé / Abstract

In this paper, we present cyclo-static dataflow (CSDF), which is a new model for the specification and implementation of digital signal processing algorithms. The CSDF paradigm is an extension of synchronous dataflow that still allows for static scheduling and, thus, a very efficient implementation of an application. In comparison with synchronous dataflow, it is more versatile because it also supports algorithms with a cyclically changing, but predefined, behavior. Our examples show that this capability results in a higher degree of parallelism and, hence, a higher throughput, shorter delays, and less buffer memory. Moreover, they indicate that CSDF is essential for modelling prescheduled components, like application-specific integrated circuits. Besides introducing the CSDF paradigm, we also derive necessary and sufficient conditions for the schedulability of a CSDF graph. We present and compare two methods for checking the liveness of a graph. The first one checks the liveness of loops, and the second one constructs a single-processor schedule for one iteration of the graph. Once the schedulability is tested, a makespan optimal schedule on a multiprocessor can be constructed. At the end of this paper, we shortly introduce the heuristic scheduling method of our graphical rapid prototyping environment (GRAPE).

Revue / Journal Title

IEEE transactions on signal processing    ISSN  1053-587X   CODEN ITPRED 

Source / Source

1996, vol. 44, n^o2, pp. 397-408 (22 ref.)

Langue / Language

Anglais

Editeur / Publisher

Institute of Electrical and Electronics Engineers, New York, NY, ETATS-UNIS  (1991) (Revue)

Mots-clés anglais / English Keywords

Signal processing

;

Digital processing

;

Integrated circuit

;

Data flow

;

Optimal algorithm

;

Scheduling

;

Modeling

;

Synchronous

;

Multiprocessor

;

Mots-clés français / French Keywords

Traitement signal

;

Traitement numérique

;

Circuit intégré

;

Flot donnée

;

Algorithme optimal

;

Ordonnancement

;

Modélisation

;

Synchrone

;

Multiprocesseur

;

Mots-clés espagnols / Spanish Keywords

Procesamiento señal

;

Tratamiento numérico

;

Circuito integrado

;

Flujo datos

;

Algoritmo óptimo

;

Ordonamiento

;

Modelización

;

Sincrónico

;

Multiprocesador

;

Localisation / Location

INIST-CNRS, Cote INIST : 222 E3, 35400004476785.0220