To compute the levels of buffers and nodes, we proceed as follows: We first start with the input buffers and output buffers of constant nodes which are assigned level 0, and its consumer nodes are the nodes that are to be assigned a level next which are stored in nextNodesToSchedule. The procedure then picks nodes of nextNodesToSchedule to check whether all of its input buffers were assigned levels. If not, the node is removed from nextNodesToSchedule and will enter this set again once one of the further input buffers will be assigned a level. If all input buffers are assigned levels, the node is given the maximum of the levels of its input buffers plus one. If it is a SEL/SWT node, it is then put into the set nextNodesSelSwt since these are the borders of basic blocks. Otherwise, its output buffers are assigned levels, and their consumers are put in nextNodesToSchedule. If nextNodesToSchedule becomes empty, a node from nextNodesSelSwt is picked, and its output buffers are assigned a level, and its consumers are put in nextNodesToSchedule. If the node is a Switch node, however, we first only put the nodes of first half of output buffers in the set, and after that, the second set. The leveling procedure terminates when both the set nextNodesToSchedule and also nextNodesSelSwt became empty.

Compute some statistics for a leveled DPN; if beQuiet is false, these values are also printed to stdout. The result is a tuple containing the number of nodes numNodes, the number of buffers numBufs, the number of levels numLevels, the number of Copy nodes numC, the number of Dup nodes numD, the number of Swap nodes numS, the number of Join nodes numJ, the number of Kill nodes numK, and the number of operation nodes (MonOp and BinOp).

CreateDPN creates a new dpn given its name, input/output buffers, buffers to initialize and the array of nodes. The rest is automatically derived from the nodes array, i.e., the dataflow equations. Note that buffers having no producer have to be inputs, and that buffers having no consumer have to be outputs. However, the converse is false since we may read and write the same variable. Hence, we have to explicitly give inBuf and outBuf as arguments.

This function translates a given dataflow process network to the related dataflow program. For each node of the dataflow process network, there is a related instruction. Additionally, for each output port, there is a corresponding instruction to distinguish input and output ports (which could otherwise result in nonterminating computations).

Write dataflow process network in graphviz format to a stream ostr. For a leveled DPN, the function may be given an optional node ordering such that nodeOrd[i] is a sorted list of the nodes of level i. For simulation traces, it may be given an optional environment (step,nodesToFire,bufEnv,memEnv) such that it prints the content of the FIFO buffers as labels attached to the related edges. Finally, an set of edges may be given as an optional argument which are then drawn as thicker lines.

mapping a DPN to a scheduling problem with the help of a function rtMap that determines for each kind of PU the worst case execution time

This function is called with a token tk that shall be consumed by the dataflow instruction instr and that matches with the tokens in tkMatch. The function fires the node and returns (tkCons,tkProd,tkOut) containing the sets of consumed, produced and output tokens.

LevelizeBasicBlockDPN adds copy nodes on the edges of the given DPN such that all incoming edges of a node have the same level (max distance to an input or constant node). Parameter inLevel and outLevel enforce that all inputs are put in level zero and that all outputs are put in the maximal level, respectively. Recall that the level of a node is the maximum of the levels of its incoming buffers, and that the level of its outgoing buffers are the level of the node. The levels are determined by function ComputeLevelsASAP.

This DPN is a leveled DPN that requires for any node/buffer orders at least two processing units. The DPN has been found by an exhaustive search and showed that also leveled DPNs may required more than one PU.

MiniC2DPN translates a given MiniC program to an equivalent DPN. The details of this translation are published in Schn21a and Schn21b. Each thread of the MiniC program generates its own DPN whose input buffers are the global variables read by the thread and whose outputs are the global variables written by the thread. Read and written applies also to globally declared arrays, but these are not read and written as a whole; instead, the DPN will contain load/store nodes to access them.

Parse a MiniC program from string miniCfilename and write the DPNs generated for its threads as graphviz files in directory dirName. The MiniC program itself is also written as a file in that directory with the given name. Parameter syncCtrl is the same as for MiniC2DPN.

Compute a minimal number of vertex-disjoint paths that cover a given DPN. The function converts the DPN to a graph as expected by function MinimumNumberOfVertexDisjointPath and calls that function. The result is a pair (iedges,ipaths) where iedges is the set of selected edges, and ipaths is the set of vertex-disjoint paths.

This function computes a special DPN called the Rainbow graph which is alternatively obtained by a MiniC program for y=(x+1)*...*(x+n). It therefore must generate n copies of the input value x, must then add constants 1,...,n to these values, and must then multiply the results. It can be proved that the graph must contain for any order of the nodes a rainbow (crossing) of at least sqrt(n-1) nodes so that it requires an unbounded number of processing units (queues).

OptimizeKillCopyNodes repeatedly replaces nodes where all output buffers are consumed by Kill nodes with Kill nodes themselves. Moreover, the function also removes all Copy nodes and directly connects their producer and consumer nodes.

Parse a DPN from a string. The given string may or may not contain labels of the form pn@PU[p] separated by symbol ":" that declares a name pn (currently without use) and an assignment to a processing unit PU[p] that maps this node to PU p. The function returns a pair (dpn,nodeAsg) where dpn is the DPN, and nodeAsg is a map that maps node i to PU nodeAsg[i]. If the given DPN string has no labels of nodes, nodeAsg is an empty map.

write dataflow process network to an output stream ostr

print a dataflow program in text format to stream ostr

print a dataflow program in html to stream ostr

print a dataflow program in latex to stream ostr

print a given trace obtained by SimulateDPN for a given dpn to stream ostr

map dataflow processes to kinds of PU that will execute them

simulate a dpn with initial values for its input buffers provided by the inMap argument. Nodes are only enabled if their output buffers do not exceed maxBufSize (so that also a maximal buffer size is respected) and the simulation stops after at most maxSteps to avoid nontermination. The result is a list of tuples (step,nodesToFire,bufEnv,memEnv) describing a state of the dpn where step is the number of the step executed, nodesToFire is the set of nodes that were fired, bufEnv is the content of the buffers, and memEnv is the state of the global memory that holds the values of the arrays.

This function implements a simulator for a dataflow computer that executes programs of type DataflowInstruction[]. The inputs are given as a set of DataflowTokens that must also hold the initializations of loops. The program is executed until there are tokens left or until the maximal number of steps given in maxSteps is reached. The processor just picks the minimal token from tokQ and tries to fire the related node. If possible, the generated tokens are put into tokQ, otherwise, the fetched token is put into tokS until the other tokens required for firing will access them.

This function implements a simulator for a dataflow computer that executes programs of type DataflowInstruction[] with a token queue and token store.

write a sequence of graphviz files for a simulation trace (one file for each state in the simulation trace)

Write a sequence of graphviz files, convert them to pdf and join the generated pdf files into a single pdf file. After this, the generated graphviz files and their corresponding pdf files are removed.

Write a dataflow process network dpn to a file in graphviz format where the optional arguments optOrd (for a node ordering), optEnv (for values of the buffers), and optEdges (for highlighting certain edges) described in the specification of function DPN2Dot are used.

Write a CAL package (should be the given directory) that contains the kinds of DPN nodes implemented as CAL actors.

write a DPN to CAL format as an XDF file

write a node as a CAL actor to stream ostr; LD and ST are missing!

print a simulation trace in html

print a pair of token sets in html

print a pair of token sets in latex