The TYR Dataflow Architecture: Improving Locality by Taming Parallelism

Architectures should aim to maximize parallelism within a machine's finite memories, but prior designs tend to extremes, either maximizing parallelism or minimizing state. In particular, prior unordered dataflow architectures suffer from a parallelism explosion that creates unbounded state, requires prohibitively large associative memories, and risks deadlock. The few architectures that successfully navigate the parallelism-state tradeoff are limited to embarrassingly parallel programs. Tyr is a new, general-purpose unordered dataflow architecture that achieves high parallelism with bounded state. The key insight is that prior unordered dataflow architectures are overly conservative, unnecessarily allocating tags from a single, global tag space. Tyr exploits program structure to break up tags into local tag spaces that operate independently. Local tag spaces eliminate tag competition between co-dependent parts of the program, provably guaranteeing forward progress with only two tags per local tag space. Tyr thus opens the door to an efficient, scalable implementation of unordered dataflow. Simulation of parallel programs demonstrates that Tyr achieves parallelism nearly identical to a naïve unordered dataflow architecture with orders-of-magnitude less state.