Static scheduling and code generation from dynamic dataflow graphs with integer-valued control streams

Abstract

This paper extends the token flow model of Buck (see Memorandum No. UCB/ERL M93/69 (Ph.D. Thesis), EECS Dept., University of California, Berkeley, September 1993) and Lee (see IEEE Transactions on Parallel and Distributed Systems, vol.2, no.2, 1991), an analytical model for the behavior of dataflow graphs with data-dependent control flow, in two ways: dataflow actor execution may depend on integer rather than Boolean, control tokens, and multiphase implementations of actors are permitted. These extensions permit data-dependent iteration to be modelled more naturally, reduce the memory required for implementations, and result in bounded-memory solutions in more cases than before. A method for generating efficient single-processor programs from the graphs is also described.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>