<p>Section 2.12 of <em>Accurate Throughput Prediction of Basic Blocks on Recent Intel Microarchitectures</em>[^1] explains how port are assigned, though it fails to explain example 4 in the question description. I also failed to figure out what role Latency plays in the port assignment.</p>
<blockquote>
<p>Previous work [19, 25, 26] has identified the ports that the µops of individual instructions can use. For µops that can use more than one port, it was, however, previously unknown how the actual port is chosen by the processor. We reverse-engineered the port assignment algorithm using microbenchmarks. In the following, we describe our findings for CPUs with eight ports; such CPUs are currently most widely used.</p>
<p>The ports are assigned when the µops are issued by the renamer to the scheduler. In a single cycle, up to four µops can be issued. In the following, we will call the position of a µop within a cycle an issue slot; e.g., the oldest instruction issued in a cycle would occupy issue slot 0.</p>
<p><strong>The port that a µop is assigned depends on its issue slot and on the ports assigned to µops that have not been executed and were issued in a previous cycle.</strong></p>
<p>In the following, we will only consider µops that can use more than one port. For a given µop m, let $P_{min}$ be the port to which the fewest non-executed µops have been assigned to from among the ports that m can use. Let $P_{min'}$ be the port with the second smallest usage so far. If there is a tie among the ports with the smallest (or second smallest, respectively) usage, let $P_{min}$ (or $P_{min'}$) be the port with the highest port number from among these ports (the reason for this choice is probably that ports with higher numbers are connected to fewer functional units). If the difference between $P_{min}$ and $P_{min'}$ is greater or equal to 3, we set $P_{min'}$ to $P_{min}$.</p>
<p>The µops in issue slots 0 and 2 are assigned to port $P_{min}$ The µops in issue slots 1 and 3 are assigned to port $P_{min'}$.</p>
<p>A special case is µops that can use port 2 and port 3. These ports are used by µops that handle memory accesses, and both ports are connected to the same types of functional units. For such µops, the port assignment algorithm alternates between port 2 and port 3.</p>
</blockquote>
<p>I tried to find out whether $P_{min}$ and $P_{min'}$ are shared between threads (Hyper-Threading), namely <strong>whether one thread can affect the port assignment of another one in the same core.</strong></p>
<p>Just split the code used in BeeOnRope's answer into two threads.</p>
<pre><code>thread1:
.loop:
    imul rax, rbx, 5
    jmp .loop

thread2:
    mov esi,1000000000
    .top:
    bswap eax
    dec  esi
    jnz  .top
    jmp thread2
</code></pre>
<p>Where instructions <code>bswap</code> can be executed on ports 1 and 5, and <code>imul r64, R64, i</code> on port 1. If counters were shared between threads, you would see <code>bswap</code> executed on port 5 and <code>imul</code> executed on port 1.</p>
<p>The experiment was recorded as follows, where ports P0 and P5 on thread 1 and p0 on thread 2 should have recorded a small amount of non-user data, but without hindering the conclusion. It can be seen from the data that the <code>bswap</code> instruction of thread 2 is executed alternately between ports P1 and P5 without giving up P1.</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>port</th>
<th>thread 1 active cycles</th>
<th>thread 2 active cycles</th>
</tr>
</thead>
<tbody>
<tr>
<td>P0</td>
<td>63,088,967</td>
<td>68,022,708</td>
</tr>
<tr>
<td>P1</td>
<td>180,219,013,832</td>
<td>95,742,764,738</td>
</tr>
<tr>
<td>P5</td>
<td>63,994,200</td>
<td>96,291,124,547</td>
</tr>
<tr>
<td>P6</td>
<td>180,330,835,515</td>
<td>192,048,880,421</td>
</tr>
<tr>
<td>total</td>
<td>180,998,504,099</td>
<td>192,774,759,297</td>
</tr>
</tbody>
</table>
</div>
<p>Therefore, the counters are not shared between threads.</p>
<p>This conclusion does not conflict with SMotherSpectre[^2], which uses time as the side channel. (For example, thread 2 waits longer on port 1 to use port 1.)</p>
<blockquote>
<p>Executing instructions that occupy a specific port and measuring their timing enables inference about other instructions executing on the same port. We first choose two instructions, each scheduled on a single, distinct, execution port. One thread runs and times a long sequence of single µop instructions scheduled on port a, while simultaneously the other thread runs a long sequence of instructions scheduled on port b. We expect that, if a = b, contention occurs and the measured execution time is longer compared to the a ≠ b case.</p>
</blockquote>
<hr />
<p>[^1]: Abel, Andreas, and Jan Reineke. &quot;Accurate Throughput Prediction of Basic Blocks on Recent Intel Microarchitectures.&quot; arXiv preprint arXiv:2107.14210 (2021).</p>
<p>[^2]: Bhattacharyya, Atri, Alexandra Sandulescu, Matthias Neugschwandtner, Alessandro Sorniotti, Babak Falsafi, Mathias Payer, and Anil Kurmus. “SMoTherSpectre: Exploiting Speculative Execution through Port Contention.” Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, November 6, 2019, 785–800. <a href="https://doi.org/10.1145/3319535.3363194" rel="nofollow noreferrer">https://doi.org/10.1145/3319535.3363194</a>.</p>
How are x86 uops scheduled, exactly?
<p>Modern x86 CPUs break down the incoming instruction stream into micro-operations (uops<sup>1</sup>) and then schedule these uops <a href="https://en.wikipedia.org/wiki/Out-of-order_execution" rel="noreferrer">out-of-order</a> as their inputs become ready. While the basic idea is clear, I'd like to know the specific details of <em>how</em> ready instructions are scheduled, since it impacts micro-optimization decisions.</p>
<p>For example, take the following toy loop<sup>2</sup>:</p>
<pre><code>top:
lea eax, [ecx + 5]
popcnt eax, eax
add edi, eax
dec ecx
jnz top
</code></pre>
<p>this basically implements the loop (with the following correspondence: <code>eax -&gt; total, c -&gt; ecx</code>):</p>
<pre><code>do {
  total += popcnt(c + 5);
} while (--c &gt; 0);
</code></pre>
<p>I'm familiar with the process of optimizing any small loop by looking at the uop breakdown, dependency chain latencies and so on. In the loop above we have only one carried dependency chain: <code>dec ecx</code>. The first three instructions of the loop (<code>lea</code>, <code>popcnt</code>, <code>add</code>) are part of a dependency chain that starts fresh each loop.</p>
<p>The final <code>dec</code> and <code>jne</code> are fused. So we have a total of 4 fused-domain uops, and one only loop-carried dependency chain with a latency of 1 cycle. So based on that criteria, it seems that the loop can execute at 1 cycle/iteration.</p>
<p>However, we should look at the port pressure too:</p>
<ul>
<li>The <code>lea</code> can execute on ports 1 and 5</li>
<li>The popcnt can execute on port 1</li>
<li>The <code>add</code> can execute on port 0, 1, 5 and 6</li>
<li>The predicted-taken <code>jnz</code> executes on port 6</li>
</ul>
<p>So to get to 1 cycle / iteration, you pretty much need the following to happen:</p>
<ul>
<li>The popcnt <em>must</em> execute on port 1 (the only port it can execute on)</li>
<li>The <code>lea</code> <em>must</em> execute on port 5 (and never on port 1)</li>
<li>The <code>add</code> <em>must</em> execute on port 0, and never on any of other three ports it can execute on</li>
<li>The <code>jnz</code> can only execute on port 6 anyway</li>
</ul>
<p>That's a lot of conditions! If instructions just got scheduled randomly, you could get a much worse throughput. For example, 75% the <code>add</code> would go to port 1, 5 or 6, which would delay the <code>popcnt</code>, <code>lea</code> or <code>jnz</code> by one cycle. Similarly for the <code>lea</code> which can go to 2 ports, one shared with <code>popcnt</code>.</p>
<p>IACA on the other hand reports a result very close to optimal, 1.05 cycles per iteration:</p>
<pre><code>Intel(R) Architecture Code Analyzer Version - 2.1
Analyzed File - l.o
Binary Format - 64Bit
Architecture  - HSW
Analysis Type - Throughput

Throughput Analysis Report
--------------------------
Block Throughput: 1.05 Cycles       Throughput Bottleneck: FrontEnd, Port0, Port1, Port5

Port Binding In Cycles Per Iteration:
---------------------------------------------------------------------------------------
|  Port  |  0   -  DV  |  1   |  2   -  D   |  3   -  D   |  4   |  5   |  6   |  7   |
---------------------------------------------------------------------------------------
| Cycles | 1.0    0.0  | 1.0  | 0.0    0.0  | 0.0    0.0  | 0.0  | 1.0  | 0.9  | 0.0  |
---------------------------------------------------------------------------------------

N - port number or number of cycles resource conflict caused delay, DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3), CP - on a critical path
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion happened
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256 instruction, dozens of cycles penalty is expected
! - instruction not supported, was not accounted in Analysis

| Num Of |                    Ports pressure in cycles                     |    |
|  Uops  |  0  - DV  |  1  |  2  -  D  |  3  -  D  |  4  |  5  |  6  |  7  |    |
---------------------------------------------------------------------------------
|   1    |           |     |           |           |     | 1.0 |     |     | CP | lea eax, ptr [ecx+0x5]
|   1    |           | 1.0 |           |           |     |     |     |     | CP | popcnt eax, eax
|   1    | 0.1       |     |           |           |     | 0.1 | 0.9 |     | CP | add edi, eax
|   1    | 0.9       |     |           |           |     |     | 0.1 |     | CP | dec ecx
|   0F   |           |     |           |           |     |     |     |     |    | jnz 0xfffffffffffffff4
</code></pre>
<p>It pretty much reflects the necessary &quot;ideal&quot; scheduling I mentioned above, with a small deviation: it shows the <code>add</code> stealing port 5 from the <code>lea</code> on 1 out of 10 cycles. It also doesn't know that the fused branch is going to go to port 6 since it is predicted taken, so it puts most of the uops for the branch on port 0, and most of the uops for the <code>add</code> on port 6, rather than the other way around.</p>
<p>It's not clear if the extra 0.05 cycles that IACA reports over the optimal is the result of some deep, accurate analysis, or a less insightful consequence of the algorithm it uses, e.g., analyzing the loop over a fixed number of cycles, or just a bug or whatever. The same goes for the 0.1 fraction of a uop that it thinks will go to the non-ideal port. It is also not clear if one explains the other - I would think that mis-assigning a port 1 out of 10 times would cause a cycle count of 11/10 = 1.1 cycles per iteration, but I haven't worked out the actual downstream results - maybe the impact is less on average. Or it could just be rounding (0.05 == 0.1 to 1 decimal place).</p>
<p>So how do modern x86 CPUs actually schedule? In particular:</p>
<ol>
<li>When multiple uops are <em>ready</em> in the reservation station, in what order are they scheduled to ports?</li>
<li>When a uop can go to multiple ports (like the <code>add</code> and <code>lea</code> in the example above), how is it decided which port is chosen?</li>
<li>If any of the answers involve a concept like <em>oldest</em> to choose among uops, how is it defined? Age since it was delivered to the RS? Age since it became ready? How are ties broken? Does program order ever come into it?</li>
</ol>
<h1>Results on Skylake</h1>
<p>Let's measure some actual results on Skylake to check which answers explain the experimental evidence, so here are some real-world measured results (from <code>perf</code>) on my Skylake box. Confusingly, I'm going switch to using <code>imul</code> for my &quot;only executes on one port&quot; instruction, since it has many variants, including 3-argument versions that allow you to use different registers for the source(s) and destination. This is very handy when trying to construct dependency chains. It also avoids the whole &quot;incorrect dependency on destination&quot; that <code>popcnt</code> has.</p>
<h2>Independent Instructions</h2>
<p>Let's start by looking at the simple (?) case that the instructions are relatively independent - without any dependency chains other than trivial ones like the loop counter.</p>
<p>Here's a 4 uop loop (only 3 executed uops) with mild pressure. All instructions are independent (don't share any sources or destinations). The <code>add</code> could in principle steal the <code>p1</code> needed by the <code>imul</code> or <code>p6</code> needed by the dec:</p>
<h3>Example 1</h3>
<pre><code>instr   p0 p1 p5 p6 
xor       (elim)
imul        X
add      X  X  X  X
dec               X

top:
    xor  r9, r9
    add  r8, rdx
    imul rax, rbx, 5
    dec esi
    jnz top

The results is that this executes with perfect scheduling at 1.00 cycles / iteration:

   560,709,974      uops_dispatched_port_port_0                                     ( +-  0.38% )
 1,000,026,608      uops_dispatched_port_port_1                                     ( +-  0.00% )
   439,324,609      uops_dispatched_port_port_5                                     ( +-  0.49% )
 1,000,041,224      uops_dispatched_port_port_6                                     ( +-  0.00% )
 5,000,000,110      instructions:u            #    5.00  insns per cycle          ( +-  0.00% )
 1,000,281,902      cycles:u   

                                           ( +-  0.00% )
</code></pre>
<p>As expected, <code>p1</code> and <code>p6</code> are fully utilized by the <code>imul</code> and <code>dec/jnz</code> respectively, and then the <code>add</code> issues <em>roughly</em> half and half between the remaining available ports. Note <em>roughly</em> - the actual ratio is 56% and 44%, and this ratio is pretty stable across runs (note the <code>+- 0.49%</code> variation). If I adjust the loop alignment, the split changes (53/46 for 32B alignment, more like 57/42 for 32B+4 alignment). Now, we if change nothing except the position of <code>imul</code> in the loop:</p>
<h3>Example 2</h3>
<pre><code>top:
    imul rax, rbx, 5
    xor  r9, r9
    add  r8, rdx
    dec esi
    jnz top
</code></pre>
<p>Then suddenly the <code>p0</code>/<code>p5</code> split is exactly 50%/50%, with 0.00% variation:</p>
<pre><code>   500,025,758      uops_dispatched_port_port_0                                     ( +-  0.00% )
 1,000,044,901      uops_dispatched_port_port_1                                     ( +-  0.00% )
   500,038,070      uops_dispatched_port_port_5                                     ( +-  0.00% )
 1,000,066,733      uops_dispatched_port_port_6                                     ( +-  0.00% )
 5,000,000,439      instructions:u            #    5.00  insns per cycle          ( +-  0.00% )
 1,000,439,396      cycles:u                                                        ( +-  0.01% )
</code></pre>
<p>So that's already interesting, but it's hard to tell what's going on. Perhaps the exact behavior depends on the initial conditions at loop entry and is sensitive to ordering within the loop (e.g., because counters are used). This example shows that something more than &quot;random&quot; or &quot;stupid&quot; scheduling is going on. In particular, if you just eliminate the <code>imul</code> instruction from the loop, you get the following:</p>
<h3>Example 3</h3>
<pre><code>   330,214,329      uops_dispatched_port_port_0                                     ( +-  0.40% )
   314,012,342      uops_dispatched_port_port_1                                     ( +-  1.77% )
   355,817,739      uops_dispatched_port_port_5                                     ( +-  1.21% )
 1,000,034,653      uops_dispatched_port_port_6                                     ( +-  0.00% )
 4,000,000,160      instructions:u            #    4.00  insns per cycle          ( +-  0.00% )
 1,000,235,522      cycles:u                                                      ( +-  0.00% )
</code></pre>
<p>Here, the <code>add</code> is now roughly evenly distributed among <code>p0</code>, <code>p1</code> and <code>p5</code> - so the presence of the <code>imul</code> did affect the <code>add</code> scheduling: it wasn't just a consequence of some &quot;avoid port 1&quot; rule.</p>
<p>Note here that total port pressure is only 3 uops/cycle, since the <code>xor</code> is a zeroing idiom and is eliminated in the renamer. Let's try with the max pressure of 4 uops. I expect whatever mechanism kicked in above to able to perfectly schedule this also. We only change <code>xor r9, r9</code> to <code>xor r9, r10</code>, so it is no longer a zeroing idiom. We get the following results:</p>
<h3>Example 4</h3>
<pre><code>top:
    xor  r9, r10
    add  r8, rdx
    imul rax, rbx, 5
    dec esi
    jnz top

       488,245,238      uops_dispatched_port_port_0                                     ( +-  0.50% )
     1,241,118,197      uops_dispatched_port_port_1                                     ( +-  0.03% )
     1,027,345,180      uops_dispatched_port_port_5                                     ( +-  0.28% )
     1,243,743,312      uops_dispatched_port_port_6                                     ( +-  0.04% )
     5,000,000,711      instructions:u            #    2.66  insns per cycle            ( +-  0.00% )
     1,880,606,080      cycles:u                                                        ( +-  0.08% )
</code></pre>
<p>Oops! Rather than evenly scheduling everything across <code>p0156</code>, the scheduler has underused <code>p0</code> (it's only executing something ~49% of cycles), and hence <code>p1</code> and <code>p6</code> are oversubcribed because they are executing both their <em>required</em> ops of <code>imul</code> and <code>dec/jnz</code>. This behavior, I think is consistent with a <em>counter-based</em> pressure indicator as hayesti indicated in their answer, and with <strong>uops being assigned to a port at issue-time, not at execution time</strong> as both
hayesti and Peter Cordes mentioned. That behavior<sup>3</sup> makes the <em>execute the oldest ready uops</em> rule not nearly as effective. If uops weren't bound to execution ports at issue, but rather at execution, then this &quot;oldest&quot; rule would fix the problem above after one iteration - once one <code>imul</code> and one <code>dec/jnz</code> got held back for a single iteration, they will always be older than the competing <code>xor</code> and <code>add</code> instructions, so should always get scheduled first. One thing I am learning though, is that if ports are assigned at issue time, this rule doesn't help because the ports are pre-determined at issue time. I guess it still helps a bit in favoring instructions which are part of long dependecy chains (since these will tend to fall behind), but it's not the cure-all I thought it was.</p>
<p>That also seems to be a explain the results above: <code>p0</code> gets assigned more pressure than it really has because the <code>dec/jnz</code> combo can <em>in theory</em> execute on <code>p06</code>. <em>In fact</em> because the branch is predicted taken it only ever goes to <code>p6</code>, but perhaps that info can't feed into the pressure balancing algorithm, so the counters tend to see equal pressure on <code>p016</code>, meaning that the <code>add</code> and the <code>xor</code> get spread around differently than optimal.</p>
<p>Probably we can test this, by unrolling the loop a bit so the <code>jnz</code> is less of a factor...</p>
<hr />
<p><sup>1</sup> OK, it is properly written <em>μops</em>, but that kills search-ability and to actually type the &quot;μ&quot; character I'm usually resorting to copy-pasting the character from a webpage.</p>
<p><sup>2</sup> I had originally used <code>imul</code> instead of <code>popcnt</code> in the loop, but, unbelievably, _IACA doesn't <a href="https://software.intel.com/en-us/forums/intel-architecture-code-analyzer/topic/296340#comment-1603915" rel="noreferrer">support it_</a>!</p>
<p><sup>3</sup> Please note that I'm not suggesting this is a poor design or anything - there are probably very good hardware reasons why the scheduler cannot easily make all its decisions at execution time.</p>