Every successive incarnation of dataflow scheduling uses a matching store and synchronization tokens on long-latency operations. You have them in Tomasulo's reservation stations at a very small scale (considering FUs as unpredictable), in the MTA throughout the memory system, in the D-RISC core of my research group, and quite a few others.
It's quite a common and recurrent idea really. However promises / dataflow tokens / I-structures / etc all are subject to a common flaw / problem: when you receive multiple completions simultaneously, which of them are you going to schedule first? This choice is highly non-obvious and has tremendous impacts on data locality.
Sure, the best reference is the paper by Culler et al. from 1992/1993:
David E. Culler, Klaus E. Schauser, and Thorsten von Eicken. Two fundamental limits on dataflow multiprocessing. In PACT ’93: Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, pages 153–164. North-Holland Publishing Co., Amsterdam, Netherlands, 1993. ISBN 0-444-88464-5.
Comments
Every successive incarnation of dataflow scheduling uses a matching store and synchronization tokens on long-latency operations. You have them in Tomasulo's reservation stations at a very small scale (considering FUs as unpredictable), in the MTA throughout the memory system, in the D-RISC core of my research group, and quite a few others.
It's quite a common and recurrent idea really. However promises / dataflow tokens / I-structures / etc all are subject to a common flaw / problem: when you receive multiple completions simultaneously, which of them are you going to schedule first? This choice is highly non-obvious and has tremendous impacts on data locality.
Thanks. Idle curiosity: do you know any introductory refs about that question and its impact? (which to schedule first)
Sure, the best reference is the paper by Culler et al. from 1992/1993:
David E. Culler, Klaus E. Schauser, and Thorsten von Eicken. Two fundamental limits on dataflow multiprocessing. In PACT ’93: Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, pages 153–164. North-Holland Publishing Co., Amsterdam, Netherlands, 1993. ISBN 0-444-88464-5.
A preprint is available as tech report CSD-92-716 from Berkeley: http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6259.html
Thanks!