Skip to contentSkip to conversation

The weird re-ordering issue of the Alpha arch'

DISCUSSION Yubin Ruan 3 participants 9 messages Apr 29, 2017 – May 9, 2017

lore
Share & tools
lore

Yubin Ruan

author
#0 lore raw

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

#1 lore raw
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

author
#2 lore raw
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

#3 lore raw
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

---
Yubin

Quoted 4 lines
Quoted 3 lines

[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html

author
#4 lore raw
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

---
Yubin

Quoted 4 lines
Quoted 3 lines

[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html

#5 lore raw
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,
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

---
Yubin

Quoted 4 lines
Quoted 3 lines

[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html

author
#6 lore raw
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,
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

---
Yubin

Quoted 4 lines
Quoted 3 lines

[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html

#7 lore raw

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,
Yubin

Quoted 8 lines

Thanx, Paul

Quoted 5 lines

Regards,
Yubin

Quoted 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

---
Yubin

Quoted 2 lines
Quoted 2 lines

[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/

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

author
#8 lore raw
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,
Yubin

Quoted 8 lines

Thanx, Paul

Quoted 5 lines

Regards,
Yubin

Quoted 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

---
Yubin

Quoted 2 lines
Quoted 2 lines

[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/

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