I like this guy and his presentation style, it is good to see someone delivering seriously on an old idea: queue machines. (The "Belt" is the queue machine model revisited. I can't see a theoretical breakthrough here). But the Mill's realization that combines a queue model with VLIW and embedded spiller machinery is worth attention.
Some criticism however: no sign yet of how variable latencies in memory will be tolerated. Requiring fixed latency for FUs is problematic with cache misses and FU sharing between pipelines. Also his comparison between a 64-item belt and the 300+ registers of OoOE is unfair, since the 300+ registers will likely tolerate more latency than the smaller belt.
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.
As Ivan just pointed out to me privately, I meant "is the stack machine model revisited", not "queue". Queue and stack machines are quite different things. But the rest of the argument holds.
Comments
I like this guy and his presentation style, it is good to see someone delivering seriously on an old idea: queue machines. (The "Belt" is the queue machine model revisited. I can't see a theoretical breakthrough here). But the Mill's realization that combines a queue model with VLIW and embedded spiller machinery is worth attention.
Some criticism however: no sign yet of how variable latencies in memory will be tolerated. Requiring fixed latency for FUs is problematic with cache misses and FU sharing between pipelines. Also his comparison between a 64-item belt and the 300+ registers of OoOE is unfair, since the 300+ registers will likely tolerate more latency than the smaller belt.
I wrote a review of what I get from his first two talks here: http://staff.science.uva.nl/~poss/posts/2013/08/01/mill-cpu/
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.
As Ivan just pointed out to me privately, I meant "is the stack machine model revisited", not "queue". Queue and stack machines are quite different things. But the rest of the argument holds.
Part of the way the Mill handles memory latency will be in the next talk. Sign up at ootbcomp.com/mailing-list for an announcement of date and venue.
The spiller machinery seems to be quite similar to SPARCs register windows. SPARC requires software handlers for the overflow though.
The spiller concept is not new with us; there have been others besides SPARC to use the idea. Ours has no software handlers.
Ivan