Stack-Tagged Dataflow

Dynamic Dataflow allows simultaneous execution of instructions in different iterations of a loop, boosting parallelism exploitation. In this model, operands are tagged with their associated instance number, incremented as they go through the loop. Instruction execution is triggered when all input operand with the same tag become available. However, this traditional tagging mechanism often requires the generation of several control instructions to manipulate tags and guarantee the correct matching. To address this problem, this work presents Stack-Tagged Dataflow, a tagging mechanism that uses stacks of tags to reduce control overheads in dataflow, while isolating context from different nested loops. Push instructions at the beginning of loops will create a new context, while Pop instructions, at the end of the loop, will restore the original context tags. Experimental results show that Stack-Tagged Dataflow is a viable solution, suggesting that a hybrid compiling approach can be used to enable Stack-Tags only when needed.