Nice post; I had the same thought of using promises for memory access. I guess you could extend that to a massively-parallel design (promises for communication).
I think Torben Mogensen posted the same basic idea of replacing registers with 'temporal addressing' to Usenet back in the 90s -- comp.arch? comp.compilers? Boy, it's been a long time.
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.
The memory architecture hasn't been detailed, but from his claims of latency hiding I could see a memory load succeeding in a constant number of cycles and pushing a belt item tagged as unfilled memory, and then an actual attempt to read that belt item would cause a stall if it hasn't been filled yet.
Comments
Nice post; I had the same thought of using promises for memory access. I guess you could extend that to a massively-parallel design (promises for communication).
I think Torben Mogensen posted the same basic idea of replacing registers with 'temporal addressing' to Usenet back in the 90s -- comp.arch? comp.compilers? Boy, it's been a long time.
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!
The memory architecture hasn't been detailed, but from his claims of latency hiding I could see a memory load succeeding in a constant number of cycles and pushing a belt item tagged as unfilled memory, and then an actual attempt to read that belt item would cause a stall if it hasn't been filled yet.