The weird re-ordering issue of the Alpha arch'
Hi,
Remember a few weeks ago we discussed about the weird re-ordering issue of the Alpha arch', which is mentioned in Appendix.B in the perfbook? I got really confused at that moment. Paul gave me a reference to a SGI webpage(an email discussion actually), but that wasn't so understandable. Today I found a few words from Kourosh Gharachorloo[1], which are very instructional for me:
For Alpha processors, the anomalous behavior is currently only possible on a 21264-based system. And obviously you have to be using one of our multiprocessor servers. Finally, the chances that you actually see it are very low, yet it is possible.
Here is what has to happen for this behavior to show up. Assume T1 runs on P1 and T2 on P2. P2 has to be caching location y with value 0. P1 does y=1 which causes an "invalidate y" to be sent to P2. This invalidate goes into the incoming "probe queue" of P2; as you will see, the problem arises because this invalidate could theoretically sit in the probe queue without doing an MB on P2. The invalidate is acknowledged right away at this point (i.e., you don't wait for it to actually invalidate the copy in P2's cache before sending the acknowledgment). Therefore, P1 can go through its MB. And it proceeds to do the write to p. Now P2 proceeds to read p. The reply for read p is allowed to bypass the probe queue on P2 on its incoming path (this allow s replies/data to get back to the 21264 quickly without needing to wait for previous incoming probes to be serviced). Now, P2 can derefence P to read the old value of y that is sitting in its cache (the inval y in P2's probe queue is still sitting there).
How does an MB on P2 fix this? The 21264 flushes its incoming probe queue (i.e., services any pending messages in there) at every MB. Hence, after the read of P, you do an MB which pulls in the inval to y for sure. And you can no longer see the old cached value for y.
Even though the above scenario is theoretically possible, the chances of observing a problem due to it are extremely minute. The reason is that even if you setup the caching properly, P2 will likely have ample opportunity to service the messages (i.e., inval) in its probe queue before it receives the data reply for "read p". Nonetheless, if you get into a situation where you have placed many things in P2's probe queue ahead of the inval to y, then it is possible that the reply to p comes back and bypasses this inval. It would be difficult for you to set up the scenario though and actually observe the anomaly.
The above addresses how current Alpha's may violate what you have shown. Future Alpha's can violate it due to other optimizations. One interesting optimization is value prediction.
What I want to say is that next time you update the perfbook, you can take a few words from it. I mean, you can adopt the same schema like "Assume T1 runs on P1 and T2 on P2. P2 has to be caching location y with value 0....". That would make the perfbook more understandable :)
Regards,
Yubin
[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html
Quoted 42 lines · Yubin Ruan
Hi,
Remember a few weeks ago we discussed about the weird re-ordering issue of the Alpha arch', which is mentioned in Appendix.B in the perfbook? I got really confused at that moment. Paul gave me a reference to a SGI webpage(an email discussion actually), but that wasn't so understandable. Today I found a few words from Kourosh Gharachorloo[1], which are very instructional for me:For Alpha processors, the anomalous behavior is currently only possible on a 21264-based system. And obviously you have to be using one of our multiprocessor servers. Finally, the chances that you actually see it are very low, yet it is possible.
Here is what has to happen for this behavior to show up. Assume T1 runs on P1 and T2 on P2. P2 has to be caching location y with value 0. P1 does y=1 which causes an "invalidate y" to be sent to P2. This invalidate goes into the incoming "probe queue" of P2; as you will see, the problem arises because this invalidate could theoretically sit in the probe queue without doing an MB on P2. The invalidate is acknowledged right away at this point (i.e., you don't wait for it to actually invalidate the copy in P2's cache before sending the acknowledgment). Therefore, P1 can go through its MB. And it proceeds to do the write to p. Now P2 proceeds to read p. The reply for read p is allowed to bypass the probe queue on P2 on its incoming path (this allow s replies/data to get back to the 21264 quickly without needing to wait for previous incoming probes to be serviced). Now, P2 can derefence P to read the old value of y that is sitting in its cache (the inval y in P2's probe queue is still sitting there).
How does an MB on P2 fix this? The 21264 flushes its incoming probe queue (i.e., services any pending messages in there) at every MB. Hence, after the read of P, you do an MB which pulls in the inval to y for sure. And you can no longer see the old cached value for y.
Even though the above scenario is theoretically possible, the chances of observing a problem due to it are extremely minute. The reason is that even if you setup the caching properly, P2 will likely have ample opportunity to service the messages (i.e., inval) in its probe queue before it receives the data reply for "read p". Nonetheless, if you get into a situation where you have placed many things in P2's probe queue ahead of the inval to y, then it is possible that the reply to p comes back and bypasses this inval. It would be difficult for you to set up the scenario though and actually observe the anomaly.
Quoted 8 lines
The above addresses how current Alpha's may violate what you have shown. Future Alpha's can violate it due to other optimizations. One interesting optimization is value prediction.
What I want to say is that next time you update the perfbook, you can take a few words from it. I mean, you can adopt the same schema like "Assume T1 runs on P1 and T2 on P2. P2 has to be caching location y with value 0....". That would make the perfbook more understandable :)
Thank you -very- much, Yubin! I was not aware of this, and you are quite correct, it is -much- better than the current citation.
Thanx, Paul
Quoted 5 lines
Regards,
Yubin[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html
Quoted 47 lines · Paul E. McKenney
Quoted 46 lines · Yubin Ruan
Hi,
Remember a few weeks ago we discussed about the weird re-ordering issue of the Alpha arch', which is mentioned in Appendix.B in the perfbook? I got really confused at that moment. Paul gave me a reference to a SGI webpage(an email discussion actually), but that wasn't so understandable. Today I found a few words from Kourosh Gharachorloo[1], which are very instructional for me:For Alpha processors, the anomalous behavior is currently only possible on a 21264-based system. And obviously you have to be using one of our multiprocessor servers. Finally, the chances that you actually see it are very low, yet it is possible.
Here is what has to happen for this behavior to show up. Assume T1 runs on P1 and T2 on P2. P2 has to be caching location y with value 0. P1 does y=1 which causes an "invalidate y" to be sent to P2. This invalidate goes into the incoming "probe queue" of P2; as you will see, the problem arises because this invalidate could theoretically sit in the probe queue without doing an MB on P2. The invalidate is acknowledged right away at this point (i.e., you don't wait for it to actually invalidate the copy in P2's cache before sending the acknowledgment). Therefore, P1 can go through its MB. And it proceeds to do the write to p. Now P2 proceeds to read p. The reply for read p is allowed to bypass the probe queue on P2 on its incoming path (this allow s replies/data to get back to the 21264 quickly without needing to wait for previous incoming probes to be serviced). Now, P2 can derefence P to read the old value of y that is sitting in its cache (the inval y in P2's probe queue is still sitting there).
How does an MB on P2 fix this? The 21264 flushes its incoming probe queue (i.e., services any pending messages in there) at every MB. Hence, after the read of P, you do an MB which pulls in the inval to y for sure. And you can no longer see the old cached value for y.
Even though the above scenario is theoretically possible, the chances of observing a problem due to it are extremely minute. The reason is that even if you setup the caching properly, P2 will likely have ample opportunity to service the messages (i.e., inval) in its probe queue before it receives the data reply for "read p". Nonetheless, if you get into a situation where you have placed many things in P2's probe queue ahead of the inval to y, then it is possible that the reply to p comes back and bypasses this inval. It would be difficult for you to set up the scenario though and actually observe the anomaly.
The above addresses how current Alpha's may violate what you have shown. Future Alpha's can violate it due to other optimizations. One interesting optimization is value prediction.
Quoted 7 lines
Quoted 4 lines
What I want to say is that next time you update the perfbook, you can take a few words from it. I mean, you can adopt the same schema like "Assume T1 runs on P1 and T2 on P2. P2 has to be caching location y with value 0....". That would make the perfbook more understandable :)
Thank you -very- much, Yubin! I was not aware of this, and you are quite correct, it is -much- better than the current citation.
Hmm...that reminds me of some words in the perfbook. In the answer of quick quiz 4.17, you state that:
Memory barrier only enforce ordering among multiple memory references: They do absolutely nothing to expedite the propogation of data from one part of the system to another. This leads to a quick rule of thumb: You do not need memory barriers unless you are using more than one variable to communicate between multiple threads.
Is that only true for the Alpha processor? I mean, on platforms other than Alpha (e.g x86), memory barrier *do* expedite the propogation of data from one processor/core to other processor/core, even though that is not officially documented.
---
Yubin
Quoted 4 lines
Quoted 3 lines
[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html
Quoted 2 lines · Yubin Ruan
Quoted 1 line · Paul E. McKenney
On Sat, Apr 29, 2017 at 10:26:05PM +0800, Yubin Ruan wrote:
[ . . . ]
Quoted 11 lines
Hmm...that reminds me of some words in the perfbook. In the answer of quick quiz 4.17, you state that:
Memory barrier only enforce ordering among multiple memory references: They do absolutely nothing to expedite the propogation of data from one part of the system to another. This leads to a quick rule of thumb: You do not need memory barriers unless you are using more than one variable to communicate between multiple threads.
Is that only true for the Alpha processor? I mean, on platforms other than Alpha (e.g x86), memory barrier *do* expedite the propogation of data from one processor/core to other processor/core, even though that is not officially documented.
Can you point me at any unofficial documentation of this, for example, any performance measurements indicating that (for example) the mfence instruction speeds up the propagation of previous writes to other CPUs?
In the absence of such documentation, all I can really do is change "They do absolutely nothing to expedite..." to something like "They are not guaranteed to do anything to expedite..."
Thanx, Paul
Quoted 8 lines
---
YubinQuoted 4 lines
Quoted 3 lines
[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html
Quoted 19 lines · Yubin Ruan
Quoted 18 lines · Paul E. McKenney
Quoted 2 lines · Yubin Ruan
Quoted 1 line · Paul E. McKenney
On Sat, Apr 29, 2017 at 10:26:05PM +0800, Yubin Ruan wrote:
[ . . . ]
Quoted 11 lines
Hmm...that reminds me of some words in the perfbook. In the answer of quick quiz 4.17, you state that:
Memory barrier only enforce ordering among multiple memory references: They do absolutely nothing to expedite the propogation of data from one part of the system to another. This leads to a quick rule of thumb: You do not need memory barriers unless you are using more than one variable to communicate between multiple threads.
Is that only true for the Alpha processor? I mean, on platforms other than Alpha (e.g x86), memory barrier *do* expedite the propogation of data from one processor/core to other processor/core, even though that is not officially documented.
Quoted 8 lines
Quoted 3 lines
Can you point me at any unofficial documentation of this, for example, any performance measurements indicating that (for example) the mfence instruction speeds up the propagation of previous writes to other CPUs?
Hmm...I might had had too much drug at that moment. What I mean is that, on platform like x86, memory barrier instructions(e.g sfence) enforce that the order of some memory references are preserved as the same as in the origin processor by another processors. However, any speedup is not guaranteed.
Hey, I was hoping! ;-)
Thanx, Paul
Quoted 19 lines
Regards,
YubinQuoted 15 lines
In the absence of such documentation, all I can really do is change "They do absolutely nothing to expedite..." to something like "They are not guaranteed to do anything to expedite..."
Thanx, Paul
Quoted 8 lines
---
YubinQuoted 4 lines
Quoted 3 lines
[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html
Hi Yubin,
I never heard that memory barrier instructions can speedup other instructions (either read or write). My understanding is that under the covers a barrier instruction may need to, for example, flush pipeline to maintain program order, and to wait for the propagation of data to other CPU cores, which disturbs the normal execution process of other instructions instead of accelerating.
--Junchang
Quoted 87 lines · Yubin Ruan
Quoted 9 lines · Paul E. McKenney
Quoted 8 lines · Yubin Ruan
Quoted 7 lines · Paul E. McKenney
Quoted 2 lines · Yubin Ruan
Quoted 1 line · Paul E. McKenney
On Sat, Apr 29, 2017 at 10:26:05PM +0800, Yubin Ruan wrote:
[ . . . ]
Quoted 1 line
Hmm...that reminds me of some words in the perfbook. In the answer
of quick quiz 4.17,
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
you state that:
Memory barrier only enforce ordering among multiple memory
references: They do
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
absolutely nothing to expedite the propogation of data from
one part of the system
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
to another. This leads to a quick rule of thumb: You do not
need memory barriers
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
unless you are using more than one variable to communicate
between multiple threads.
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Is that only true for the Alpha processor? I mean, on platforms
other than
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Alpha (e.g x86), memory barrier *do* expedite the propogation of
data from one
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
processor/core to other processor/core, even though that is not
officially documented.
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Can you point me at any unofficial documentation of this, for
example,
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
any performance measurements indicating that (for example) the mfence instruction speeds up the propagation of previous writes to other
CPUs?
Quoted 2 lines
Quoted 2 lines
Hmm...I might had had too much drug at that moment. What I mean is
that, on platform
Quoted 1 line
Quoted 1 line
like x86, memory barrier instructions(e.g sfence) enforce that the
order of some memory
Quoted 1 line
Quoted 1 line
references are preserved as the same as in the origin processor by
another processors.
Quoted 3 lines
Quoted 1 line
However, any speedup is not guaranteed.
Hey, I was hoping! ;-)
Ah...sorry to dispoint you. :)
Maybe some memory barrier instructions do have some speedup side effect to "expedite" the propogation of previous writes. Maybe try to consult some Intel
engineer about this...?
It would be good to have some experiments to measure this. But currently I don't
know how to carry out the experiment myself. Do you have any plan or idea?Thanks,
YubinQuoted 8 lines
Thanx, Paul
Quoted 5 lines
Regards,
YubinQuoted 2 lines
In the absence of such documentation, all I can really do is change "They do absolutely nothing to expedite..." to something like "They
are
Quoted 9 lines
Quoted 9 lines
Quoted 9 lines
not guaranteed to do anything to expedite..."
Thanx, Paul
Quoted 5 lines
---
YubinQuoted 2 lines
Quoted 2 lines
AlphaReordering.html
Quoted 6 lines
Quoted 5 lines
Quoted 4 lines
Quoted 3 lines
Quoted 2 lines
Quoted 1 line
--
To unsubscribe from this list: send the line "unsubscribe perfbook" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 14 lines · Paul E. McKenney
Quoted 2 lines · Yubin Ruan
Quoted 1 line · Paul E. McKenney
On Sat, Apr 29, 2017 at 10:26:05PM +0800, Yubin Ruan wrote:
[ . . . ]
Quoted 8 lines
Hmm...that reminds me of some words in the perfbook. In the answer of quick quiz 4.17, you state that:
Memory barrier only enforce ordering among multiple memory references: They do absolutely nothing to expedite the propogation of data from one part of the system to another. This leads to a quick rule of thumb: You do not need memory barriers unless you are using more than one variable to communicate between multiple threads.
Quoted 7 lines
Quoted 3 lines
Is that only true for the Alpha processor? I mean, on platforms other than Alpha (e.g x86), memory barrier *do* expedite the propogation of data from one processor/core to other processor/core, even though that is not officially documented.
Can you point me at any unofficial documentation of this, for example, any performance measurements indicating that (for example) the mfence instruction speeds up the propagation of previous writes to other CPUs?
Hmm...I might had had too much drug at that moment. What I mean is that, on platform like x86, memory barrier instructions(e.g sfence) enforce that the order of some memory references are preserved as the same as in the origin processor by another processors. However, any speedup is not guaranteed.
Regards,
Yubin
Quoted 15 lines
In the absence of such documentation, all I can really do is change "They do absolutely nothing to expedite..." to something like "They are not guaranteed to do anything to expedite..."
Thanx, Paul
Quoted 8 lines
---
YubinQuoted 4 lines
Quoted 3 lines
[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html
Quoted 8 lines · Junchang Wang
Hi Yubin,
I never heard that memory barrier instructions can speedup other instructions (either read or write). My understanding is that under the covers a barrier instruction may need to, for example, flush pipeline to maintain program order, and to wait for the propagation of data to other CPU cores, which disturbs the normal execution process of other instructions instead of accelerating.
Yes you are right. I just messed it up, because, for example, on x86, a write memory barrier would guarantee that previous writes will arrive at other processors in their program order (which is not always the case for Alpha). And that is as if there are something pushing them...So I make that mistake...
Still, I would love to know what is your idea for testing whether this is true.
Thanks,
Yubin
Quoted 90 lines · Yubin Ruan
Quoted 88 lines · Paul E. McKenney
Quoted 9 lines · Yubin Ruan
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines · Yubin Ruan
Quoted 2 lines · Paul E. McKenney
Quoted 1 line · Yubin Ruan
[ . . . ]
Quoted 1 line
Hmm...that reminds me of some words in the perfbook. In the answer
of quick quiz 4.17,
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
you state that:
Memory barrier only enforce ordering among multiple memory
references: They do
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
absolutely nothing to expedite the propogation of data from
one part of the system
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
to another. This leads to a quick rule of thumb: You do not
need memory barriers
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
unless you are using more than one variable to communicate
between multiple threads.
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Is that only true for the Alpha processor? I mean, on platforms
other than
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Alpha (e.g x86), memory barrier *do* expedite the propogation of
data from one
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
processor/core to other processor/core, even though that is not
officially documented.
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Can you point me at any unofficial documentation of this, for
example,
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
any performance measurements indicating that (for example) the mfence instruction speeds up the propagation of previous writes to other
CPUs?
Quoted 2 lines
Quoted 2 lines
Hmm...I might had had too much drug at that moment. What I mean is
that, on platform
Quoted 1 line
Quoted 1 line
like x86, memory barrier instructions(e.g sfence) enforce that the
order of some memory
Quoted 1 line
Quoted 1 line
references are preserved as the same as in the origin processor by
another processors.
Quoted 3 lines
Quoted 1 line
However, any speedup is not guaranteed.
Hey, I was hoping! ;-)
Ah...sorry to dispoint you. :)
Maybe some memory barrier instructions do have some speedup side effect to "expedite" the propogation of previous writes. Maybe try to consult some Intel
engineer about this...?
It would be good to have some experiments to measure this. But currently I don't
know how to carry out the experiment myself. Do you have any plan or idea?Thanks,
YubinQuoted 8 lines
Thanx, Paul
Quoted 5 lines
Regards,
YubinQuoted 2 lines
In the absence of such documentation, all I can really do is change "They do absolutely nothing to expedite..." to something like "They
are
Quoted 9 lines
Quoted 9 lines
Quoted 9 lines
not guaranteed to do anything to expedite..."
Thanx, Paul
Quoted 5 lines
---
YubinQuoted 2 lines
Quoted 2 lines
AlphaReordering.html
Quoted 6 lines
Quoted 5 lines
Quoted 4 lines
Quoted 3 lines
Quoted 2 lines
Quoted 1 line
--
To unsubscribe from this list: send the line "unsubscribe perfbook" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 24 lines · Paul E. McKenney
Quoted 23 lines · Yubin Ruan
Quoted 21 lines · Paul E. McKenney
Quoted 2 lines · Yubin Ruan
Quoted 1 line · Paul E. McKenney
On Sat, Apr 29, 2017 at 10:26:05PM +0800, Yubin Ruan wrote:
[ . . . ]
Quoted 11 lines
Hmm...that reminds me of some words in the perfbook. In the answer of quick quiz 4.17, you state that:
Memory barrier only enforce ordering among multiple memory references: They do absolutely nothing to expedite the propogation of data from one part of the system to another. This leads to a quick rule of thumb: You do not need memory barriers unless you are using more than one variable to communicate between multiple threads.
Is that only true for the Alpha processor? I mean, on platforms other than Alpha (e.g x86), memory barrier *do* expedite the propogation of data from one processor/core to other processor/core, even though that is not officially documented.
Can you point me at any unofficial documentation of this, for example, any performance measurements indicating that (for example) the mfence instruction speeds up the propagation of previous writes to other CPUs?
Quoted 6 lines
Quoted 4 lines
Hmm...I might had had too much drug at that moment. What I mean is that, on platform like x86, memory barrier instructions(e.g sfence) enforce that the order of some memory references are preserved as the same as in the origin processor by another processors. However, any speedup is not guaranteed.
Hey, I was hoping! ;-)
Ah...sorry to dispoint you. :)
Maybe some memory barrier instructions do have some speedup side effect to "expedite" the propogation of previous writes. Maybe try to consult some Intel engineer about this...?
It would be good to have some experiments to measure this. But currently I don't know how to carry out the experiment myself. Do you have any plan or idea?
Thanks,
Yubin
Quoted 23 lines
Thanx, Paul
Quoted 19 lines
Regards,
YubinQuoted 15 lines
In the absence of such documentation, all I can really do is change "They do absolutely nothing to expedite..." to something like "They are not guaranteed to do anything to expedite..."
Thanx, Paul
Quoted 8 lines
---
YubinQuoted 4 lines
Quoted 3 lines
[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html