Affiliations: Department of Comp. Science, University of Akron,
Akron, OH 44325-4003, USA | Department of Comp. Science, Erik Jonsson School of
Eng. & C.S., Box 830688, MS EC 31, Univ. of Texas at Dallas, Richardson, TX
75083-0688, USA. Tel.: +1 972 883 4193; Fax: +1 972 883 2349; E-mail:
edsha@utdallas.edu
Abstract: Many applications commonly found in digital signal processing and
image processing applications can be represented by data-flow graphs (DFGs). In
our previous work, we proposed a new technique, extended retiming, which can be
combined with minimal unfolding to transform a DFG into one which is
rate-optimal. The result, however, is a DFG with split nodes, a concise
representation for pipelined schedules. This model and the extraction of the
pipelined schedule it represents have heretofore not been explored. In this
paper, we develop new results regarding the construction of such graphs. We
develop scheduling algorithms for such graphs, and then discuss a way to reduce
the hardware requirements of such schedules. In the process, we state and prove
a tight upper bound on the minimum number of processors required to execute the
static schedule produced by our algorithms. We also construct an unfolding
algorithm for split-node graphs and combine it with our scheduling methods to
achieve rate-optimality in all cases. Finally, we demonstrate our methods on a
specific example.
Keywords: Parallel and distributed systems, compilers, optimization, modeling languages, programmable signal processors
