THE TOKEN FLOW MODEL

Abstract

This paper reviews and extends an analytical model for the behavior of dataflow graphs with data-dependent control flow. The number of tokens produced or consumed by each actor is given as a symbolic function of the Booleans in the system. Long-term averages can be analyzed to determine consistency of token flow rates. Short-term behavior can be analyzed to construct an annotated schedule, or a static schedule that annotates each firing of an actor with the Boolean conditions under which that firing occurs. Necessary and sufficient conditions for bounded-length schedules, as well as sufficient conditions for determining that a dataflow graph can be scheduled in bounded memory are given. Annotated schedules can be used to generate efficient implementations of the algorithms described by the dataflow graphs. 1. Introduction The principal strength of dataflow graphs is that they do not over-specify an algorithm by imposing unnecessary sequencing constraints between operators. Instead, th...