A hybrid approach for efficient dataflow computing

A hybrid graph model for data-flow computation that integrates the concepts of `tagged-token´ graphs with those of `static´ graphs is presented. This model is based on partitioning the tagged-token graph into highly connected pieces that become a basic unit for activation and execution. A piece is activated in the same way as a tagged-token node. Execution of a piece consists of the firing of nodes within the piece according to static firing rules. An individual piece supports multiple concurrent activations by propagating successive wavefronts of tokens through the piece in a pipeline fashion. Pieces are restricted to being acyclic so that they can be pipelined. This hybrid model was developed to investigate the interaction of static and tagged-token data-flow computation. Hybrid computation is presented from the derivation of the model, through a discussion of the problems of pipelining certain kinds of graph node (e.g. merging operators and function invocators), to a logical description of a data-driven processor array implementing the model