Retiming synchronous data-flow graphs to reduce execution time

Author

O´Neil, Timothy W. ; Sha, Edwin H M

Author_Institution

Dept. of Comput. Sci. & Eng., Notre Dame Univ., IN, USA

Volume

49

Issue

10

fYear

2001

fDate

10/1/2001 12:00:00 AM

Firstpage

2397

Lastpage

2407

Abstract

Many common iterative or recursive DSP applications be can represented by synchronous data-flow graphs (SDFGs). A great deal of research has been done attempting to optimize such applications through retiming. However, despite its proven effectiveness in transforming single-rate data-flow graphs to equivalent DFGs with smaller clock periods, the use of retiming for attempting to reduce the execution time of synchronous DFGs has never been explored. In this paper, we do just this. We develop the basic definitions and results necessary to express and study SDFGs. We review the problems faced when attempting to retime an SDFG in order to minimize clock period and then present algorithms for doing this. Finally, we demonstrate the effectiveness of our methods on several examples

Keywords

data flow graphs; signal processing; synchronisation; SDFG; clock period; execution time; retiming; synchronous data-flow graphs; Clocks; Computer science; Delay; Digital signal processing; Process design; Programming environments; Signal design; Signal processing; Signal processing algorithms; Time factors;

fLanguage

English

Journal_Title

Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

1053-587X

Type

jour

DOI

10.1109/78.950794

Filename

950794