ISSN:
1572-8102
Keywords:
dataflow programming
;
synchronous dataflow
;
memory management
;
multirate signal processing algorithms
;
SDF compiler
;
on-chip memory
;
minimum cuts
;
dynamic programming
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract In this paper, we formally develop techniques that minimize the memory requirements of a target program when synthesizing software from dataflow descriptions of multirate signal processing algorithms. The dataflow programming model that we consider is the synchronous dataflow (SDF) model [21], which has been used heavily in DSP design environments over the past several years. We first focus on the restricted class of well-ordered SDF graphs. We show that while extremely efficient techniques exist for constructing minimum code size schedules for well-ordered graphs, the number of distinct minimum code size schedules increases combinatorially with the number of vertices in the input SDF graph, and these different schedules can have vastly different data memory requirements. We develop a dynamic programming algorithm that computes the schedule that minimizes the data memory requirement from among the schedules that minimize code size, and we show that the time complexity of this algorithm is cubic in the number of vertices in the given well-ordered SDF graph. We present several extensions to this dynamic programming technique to more general scheduling problems, and we present a heuristic that often computes near-optimal schedules with quadratic time complexity. We then show that finding optimal solutions for arbitrary acyclic graphs is NP-complete, and present heuristic techniques that jointly minimize code and data size requirements. We present a practical example and simulation data that demonstrate the effectiveness of these techniques.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1008633809454
Permalink
