3 ms·

Thanks for writing this, BeeOnRope! I'm not all the way though it yet, but I'm having trouble understanding the "eligible" column. There are a few nops with a

by rrss 7y ago

Thanks for writing this, BeeOnRope! I'm not all the way though it yet, but I'm having trouble understanding the "eligible" column. There are a few nops with a nonzero entries, and I haven't been able to figure out the pattern yet. I'd appreciate a clarification if you have a moment to spare.

BeeOnRope 7y ago
Sure. Here's the section from the post for context: <quote> Here, the eligible column indicates when the instruction is eligible for retirement in the sense that it has finished executing. nop instructions have no dependencies hence basically execute instantly (in fact, no not execute at all) and hence are eligible on cycle 0. The other instructions come eligible as defined by their position in the mov -> add -> ... dependency chain. The actual column shows when the instruction actually retires. You can build it by basically scanning down the eligible column and retiring up to 4 uops if their eligible cycle is less than or equal to the current cycle. </quote> Basically instructions [1] need to execute before they can retire. Instructions execute out-of-order when their inputs become ready and when some other constraints are met (e.g., their execution port is available). This post [2] is a good introduction. So here "eligible" is the cycle at which an instruction would be expected to complete execution (starting arbitrarily at cycle 0), if you have a chain of mov instructions they will be eligible at 0, 4, 8, 12, ... since this chain has latency 4. If you have a bunch of independent instructions with throughput 4/cycle, they would be become eligible at 0,0,0,0,1,1,1,1,2,2,2,2 since 4 can start every cycle and they take 1 cycle each. "Eligible" is relevant here because it defines when the instruction can retire. Unlike execution, retirement happens in order, so you can imagine the retirement unit maintaining a pointer to the oldest (i.e., "higher up" in source order) instruction, and asking "is it eligible yet?" every cycle. If yes, that instruction will be retired in addition to up to the 3 subsequent in-order instructions if they were also eligible. So from eligible cycle analysis we can reconstruct the retirement pattern (sometimes more than one pattern is possible, I didn't touch on this yet in this post). Let me know if it makes some sense? --- [1] Actually uops are what execute, but they are equivalent for this example. [2] https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introduction-to-dataflow-graphs/ https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introdu...
- nkurz 7y ago
  Coincidentally, this recent HN post also contains a fine introduction to processor internals of this sort: https://gamozolabs.github.io/metrology/2019/08/19/sushi_roll.html https://gamozolabs.github.io/metrology/2019/08/19/sushi_roll.... I know you (BeeOnRope) don't need the introductory parts, but you might appreciate the meat of his post.
  - BeeOnRope 7y ago
    Yes, I've read and it have been thinking about how to do this kind of synchronized counter reading from userspace, where it would be easier to access (even if you wanted to go the kernel route, this kernel is not publicly available). I really like this way of displaying per-cycle information from the performance counters. Very cool.
- rrss 7y ago
  Thanks. Sorry if I'm being thick, but I'm still having trouble seeing where the pattern for nops is coming from, in this example from the post: /- eligible | /- actual mov rax, [rax] ; 0 0 nop ; 0 0 nop ; 0 0 add rax, 0 ; 1 1 nop ; 0 1 nop ; 1 1 <------ ? nop ; 0 1 mov rax, [rax] ; 6 6 I would think that the fourth nop is eligible only at cycle 1 because only four uops can start each cycle, but then the fifth nop is also eligible at cycle 4. What's different about the fourth nop from the third and fifth?
  - BeeOnRope 7y ago
    You are not being thick. It was a typo on my part, I intended for all the nops to have 0 for their eligible column. As you point out, putting them all at 0 isn't even really accurate because only 4 can allocate (rename) a cycle, so the true eligible pattern should be 0-0-0-0-1-1-1-1-2-2-2-2 or something like that (it's more complicated than than because the mov/add also needs to allocate, so it's rp). I'm basically ignoring that assuming the front-end (including allocation) can keep up, or basically that the scheduler is infinitely large and always totally full. I am going to fix this to be more accurate but I'll have to unroll the loop a bit more for the difference between retire and eligible to make sense. BTW, this is just a few simple version of what llvm-mca -timeline view does: https://godbolt.org/z/ZrGXrH https://godbolt.org/z/ZrGXrH Timeline view simulates a simple CPU pipeline, and with -dispatch=4 -mcpu=Skylake it's pretty close to Skylake. Unfortunately, llcm-mca models "unlimited retire bandwidth" so if 100 instructions all become eligible in the same cycle, it will retire all 100. So it's not too helpful here in any cases where it would retire more than 4 per cycle (but it works for this example because that doesn't happen due to the dep chains). I didn't find any argument you can pass to limit retire bandwidth. In practice this is not a problem for most performance-oriented investigation because the retire limit isn't really a bottleneck, so reported performance from the tool is likely to be the same even though it simulates unlimited bandwidth.

by rrss 7y ago

BeeOnRope 7y ago

Sure. Here's the section from the post for context: <quote> Here, the eligible column indicates when the instruction is eligible for retirement in the sense that it has finished executing. nop instructions have no dependencies hence basically execute instantly (in fact, no not execute at all) and hence are eligible on cycle 0. The other instructions come eligible as defined by their position in the mov -> add -> ... dependency chain. The actual column shows when the instruction actually retires. You can build it by basically scanning down the eligible column and retiring up to 4 uops if their eligible cycle is less than or equal to the current cycle. </quote> Basically instructions [1] need to execute before they can retire. Instructions execute out-of-order when their inputs become ready and when some other constraints are met (e.g., their execution port is available). This post [2] is a good introduction. So here "eligible" is the cycle at which an instruction would be expected to complete execution (starting arbitrarily at cycle 0), if you have a chain of mov instructions they will be eligible at 0, 4, 8, 12, ... since this chain has latency 4. If you have a bunch of independent instructions with throughput 4/cycle, they would be become eligible at 0,0,0,0,1,1,1,1,2,2,2,2 since 4 can start every cycle and they take 1 cycle each. "Eligible" is relevant here because it defines when the instruction can retire. Unlike execution, retirement happens in order, so you can imagine the retirement unit maintaining a pointer to the oldest (i.e., "higher up" in source order) instruction, and asking "is it eligible yet?" every cycle. If yes, that instruction will be retired in addition to up to the 3 subsequent in-order instructions if they were also eligible. So from eligible cycle analysis we can reconstruct the retirement pattern (sometimes more than one pattern is possible, I didn't touch on this yet in this post). Let me know if it makes some sense? --- [1] Actually uops are what execute, but they are equivalent for this example. [2] https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introduction-to-dataflow-graphs/ https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introdu...

nkurz 7y ago
Coincidentally, this recent HN post also contains a fine introduction to processor internals of this sort: https://gamozolabs.github.io/metrology/2019/08/19/sushi_roll.html https://gamozolabs.github.io/metrology/2019/08/19/sushi_roll.... I know you (BeeOnRope) don't need the introductory parts, but you might appreciate the meat of his post.
- BeeOnRope 7y ago
  Yes, I've read and it have been thinking about how to do this kind of synchronized counter reading from userspace, where it would be easier to access (even if you wanted to go the kernel route, this kernel is not publicly available). I really like this way of displaying per-cycle information from the performance counters. Very cool.
rrss 7y ago
Thanks. Sorry if I'm being thick, but I'm still having trouble seeing where the pattern for nops is coming from, in this example from the post: /- eligible | /- actual mov rax, [rax] ; 0 0 nop ; 0 0 nop ; 0 0 add rax, 0 ; 1 1 nop ; 0 1 nop ; 1 1 <------ ? nop ; 0 1 mov rax, [rax] ; 6 6 I would think that the fourth nop is eligible only at cycle 1 because only four uops can start each cycle, but then the fifth nop is also eligible at cycle 4. What's different about the fourth nop from the third and fifth?
- BeeOnRope 7y ago
  You are not being thick. It was a typo on my part, I intended for all the nops to have 0 for their eligible column. As you point out, putting them all at 0 isn't even really accurate because only 4 can allocate (rename) a cycle, so the true eligible pattern should be 0-0-0-0-1-1-1-1-2-2-2-2 or something like that (it's more complicated than than because the mov/add also needs to allocate, so it's rp). I'm basically ignoring that assuming the front-end (including allocation) can keep up, or basically that the scheduler is infinitely large and always totally full. I am going to fix this to be more accurate but I'll have to unroll the loop a bit more for the difference between retire and eligible to make sense. BTW, this is just a few simple version of what llvm-mca -timeline view does: https://godbolt.org/z/ZrGXrH https://godbolt.org/z/ZrGXrH Timeline view simulates a simple CPU pipeline, and with -dispatch=4 -mcpu=Skylake it's pretty close to Skylake. Unfortunately, llcm-mca models "unlimited retire bandwidth" so if 100 instructions all become eligible in the same cycle, it will retire all 100. So it's not too helpful here in any cases where it would retire more than 4 per cycle (but it works for this example because that doesn't happen due to the dep chains). I didn't find any argument you can pass to limit retire bandwidth. In practice this is not a problem for most performance-oriented investigation because the retire limit isn't really a bottleneck, so reported performance from the tool is likely to be the same even though it simulates unlimited bandwidth.