Electronic Resource
Springer
The journal of VLSI signal processing systems for signal, image, and video technology
9 (1995), S. 211-232
ISSN:
1573-109X
Source:
Springer Online Journal Archives 1860-2000
Topics:
Electrical Engineering, Measurement and Control Technology
Notes:
Abstract In this paper we present a novel framework ofmulti-rate scheduling of signal processing programs represented by regular stream flow graphs (RSFGs). The main contribution of this paper is translating the scheduling problem of RSFGs into an equivalent problem in the domain of Karp-Miller computation graphs. A distinct feature of our scheduling framework—called themulti-rate software pipelining—is to allow maximum overlapping of operations from successive iterations, subject only to precedence constraints caused by data dependences. p ]We demonstrate that the scheduling of regular stream flow graphs can be formulated as a mathematical problem by capturing data dependences between two actors as a precedence relation between the firing of these actors. Using linear schedules, the problem is further translated into a linear program formulation. An efficient solution for the linear programming problem is obtained by first constructing what is called theprecedence graph. A polynomial-time solution is obtained by observing that the optimal computation rate is theminimum cost-to-time ratio cycle (MCTRC) in the precedence graph and using the well-established solution methods for the MCTRC problem. Finally, to minimize the buffer requirement for the obtained rate-optimal schedule, a graph coloring method based on thecyclic interval graph representation has been proposed.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02407086
Permalink
|
Location |
Call Number |
Expected |
Availability |