Top Up Prev Next Bottom Contents Index Search

8.1 Introduction

Boolean-controlled dataflow (BDF) is a domain that can be thought of as a generalization of synchronous dataflow (SDF). It supports dynamic flow of control but still permits much of the scheduling work to be performed at compile time. The dynamic dataflow (DDF) domain, by contrast, makes all scheduling decisions at run time. Thus, while BDF is a generalization of SDF, DDF is still more general. Accordingly, the BDF domain permits SDF actors to be used, and the DDF domain permits BDF actors to be used. This chapter will assume that the reader is familiar with the SDF domain.

The BDF domain can execute any actor that falls into the class of Boolean-controlled dataflow actors. For an actor to be SDF, the number of particles read by each input porthole, or written by each output porthole, must be constant. Under BDF, a generalization is permitted: the number of particles read or written by a porthole may be either a constant or a two-valued function of a particle read on a control porthole for the same star. One of the two values of the function must be zero. The effect of this is that a porthole might read tokens only if the corresponding control particle is zero (FALSE) or nonzero (TRUE). The control porthole is always of type integer, and it must read or write exactly one particle. Although the particles on the control porthole are of integer type, we treat them as Booleans, using the C/C++ convention that zero is false and nonzero is true.

We say that a porthole that conditionally transfers data based on a control token is a conditional porthole. A conditional input porthole must be controlled by a control input. A conditional output porthole may be controlled by either a control input or a control output. These restrictions permit the run-time flow of control to be determined by looking only at the values of particles on control ports. The compile-time scheduler determines exactly how the flow of control will be altered at run time by the values of these particles. It constructs what we call an annotated schedule, which is a compile-time schedule where each firing is annotated with the run-time conditions under which the firing should occur.

The theory that describes graphs of BDF actors and their properties is called the token flow model. Its properties are summarized in [Buc93b] and developed in much more detail in [Buc93c].

The BDF scheduler performs the following functions. First, it performs a consistency check analogous to the one performed by the SDF scheduler to detect certain types of errors corresponding to mismatches in particle flow rates [Lee91a]. Assuming that no error is detected, it then applies a clustering algorithm to the graph, attempting to map it into traditional control structures such as if-then-else and do-while. If this clustering process succeeds in reducing the entire graph to a single cluster, the graph is then executed with the quasi-static schedule corresponding to the clusters. (It is not completely static since some actors will be conditionally executed based on control particle values, but the result is "as static as possible.") If the clustering does not succeed, then the resulting clusters may optionally be executed by the same dynamic scheduler as is used in the DDF domain. Dynamic execution of clusters is enabled or disabled by setting the "allowDynamic" parameter of the default-BDF target.

Top Up Prev Next Bottom Contents Index Search

Copyright © 1990-1997, University of California. All rights reserved.