Hacker News new | comments | ask | show | jobs | submit login

This PDF explains what I discuss below in more detail: http://moodle.technion.ac.il/pluginfile.php/315285/mod_resou.... Prediction of aliasing is discussed on slide 25.

The patent in question pertains to an optimization of what these days you'd call "memory disambiguation." In a processor executing instructions out of order, data dependencies can be known or ambiguous. A known data dependency is, for example, summing the results of two previous instructions that themselves each compute the product of two values. An ambiguous data dependency is usually a memory read after a memory write. The processor usually does not know the address of the store until it executes the store. So it can't tell whether a subsequent load must wait behind the store (if it reads from the same address), or can safely be moved ahead of it (if it reads from a different address).

If you have the appropriate machinery, you can speculatively execute that later load instruction. But you need some mechanism to ensure that if you guess wrong--that subsequent load really does read from the same address as the earlier store--you can roll back the pipeline and re execute things in the correct order.

But flushing that work and replaying is slow. If you've got a dependent store-load pair, you want to avoid the situation where misspeculation causes you to have to flush and reply every time. The insight of the patent is that these dependent store-load pairs have temporal locality. Using a small table, you can avoid most misspeculations by tracking these pairs in the table and not speculating the subsequent load if you get a table hit. That specific use of a prediction table is what is claimed by the patent.

Maybe this is worth a patent, or maybe not. For what it's worth, I don't think anybody was doing memory disambiguation at all in 1996. Intel was one of the first (maybe the first) to do so commercially in the mid-2000's. Apple's Cyclone architecture also does it, and I think it was the first in the low-power SoC space to do it.




Alpha 21264 (also from '96) had load store buffers that would notice the dependence violations and flush the pipeline during speculative execution. Sparc and power also had this to some extent with write buffers. I can't think of any that used a predictor though to decide whether to execute speculatively or not back then, they all just either did or stalled on the first potential violation. The patent appears novel for the time to me, thank you for digging it up and explaining.


DEC was working on it, allegedly for EV8: https://www.cis.upenn.edu/~cis501/papers/store-sets.pdf. They cite to the inventor of the patent in question: "Independently, Moshovos et al. published a comprehensive description of memory dependence prediction. This is the first published work identifying that memory dependencies are problematic for out-of-order machines."


That's a great paper and insight, thanks again.


> Maybe this is worth a patent, or maybe not.

Maybe start with another question. What do you think the odds are that there was any kind of causal chain from the invention of this technique by the patent holder to Apple's use of the technique?


An early paper by the inventor on the technique is cited over 300+ in Google Scholar, including by Hennessy & Patterson.


Good to know. Maybe the patented is warranted. Can you also argue that the $862 million is appropriate?




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: