Prediction

I was re-watching the prediction video this morning. It seems like there are some serious advantages to the EBB chaining prediction approach, but it also seems like one drawback of it is that you completely lose the ability to make predictions about secondary or tertiary exits from an EBB, such as you might find in a loop within a loop. It seems like this makes the mill better at branchy or unstructred code at the expense of making it worse at the sort of code DSPs would typically excel at. Am I missing something?

This is obviously one of those details that had to be glossed over in the talk, but the line and instruction counts in the exit table can only refer to one stream. Are there two pairs of counts, one for each stream? Or have you worked out some trick to get by with just one.

I seem to recall that you mentioned you loaded new predictions on a function call in the talk, and that seemed rather frequent to me. Now that the security talk is out, are they actually loaded on portal calls?

It was mentioned in thew video that when there is a cold load of a program there is no history to use for prediction, so branch operations just guess. Might it be possible to prime the history with an annotation in source code? I suppose this could be an innate field in a branch instruction, or a separate instruction to to inform the predictor similar to __builtin_expect. The difference from __builtin_expect being, the value would only inform a cold predictor. It seems like this might be a large benefit for initial program performance; i.e., one of the larger factors in users’ subjective performance perception.

Something that was not addressed in this talk is virtual and indirect calls/jumps. Predicting these has significant effect not just with dynamic languages but as low-level as C++.

One facet would be virtual dispatch where the type of object being dispatched is generally the same across multiple executions at the same call site. The existing Mill predictor would naturally be able to learn this, and Java and JavaScript tend to have function rewriting to perform this type of prediction in software.

But often the type varies for a given call site. Unlike branch prediction, it’s not limited to a binary decision between two potential addresses. Opportunity to prefetch the next EBB can come from hoisting the load of the dispatch address, which can go pretty far in functions which perform processing themselves before the dispatch call. However, the software would need to be able to give this address to the exit chaining mechanism in order to gain value from this prefetch.

There are also concepts of history tables linked to object identity instead of call site address. With these, multiple call sites could benefit from a single knowledge update, but I don’t think they’re as appropriate for general purpose CPUs as they’re usually specific to object system ABIs.

Exactly right.

When the prediction facility was being designed, we decided that any unstable transfer point such as method calls (what Cliff Click calls “megamorphic”) would be of interest only if control passed through it frequently enough to keep the various target EBBs in the L2. Consequently we did not concern ourselves with issues of DRAM latency, and were primarily concerned with the miss-predict penalty (yes, the Mill has a penalty that is a third that of other architectures, but a stall is still a stall) and the L1/L2 latencies.

Next, we observed that the codes we looked at, and in our personal experience, megamorphic transfers tended to not be calls on leaf function. Instead, a megamorphic transfer usually led to a sequence of transfers that were not megamorphic, until control returned back through the megamorphic point. This reflects a program model in which a test point figures out the type of a datum, and then does stuff with the known type. Mill run-ahead prediction works well with this model, because once through the megamorph the subsequent control flow will predict well and will be prefetched ahead of need. Incidentally, the original source may not have been written to this model, but the compiler’s value-set analysis and inlining will tend to remove the type-checks internally to the known-type cluster, and even if it does not, the type will in fact be fixed and the transfers not be megamorphic.

The alternative model works less well, where the same object is subjected to a succession of leaf-function calls. Each of the calls will be megamorphic if the object is (and so will miss-predict frequently), and the leaf functions don’t have long enough transfer chains for run-ahead to win much.

This suggests an obvious optimization for the compiler: transform the latter structure into the former. This dimensionality inversion or transpose is the control space analogy to the re-tiling optimizations that are used to improve array traversal in the data space, and for all I know some compilers already do it. It should benefit any prediction mechanism, not just ours.

In an embedded system, with code in ROM, how can the prediction table get back into the load module?

Greetings all,

For some perspective on the economic value of improved prediction, you might enjoy reading about a recent, large ($862 million US) patent-infringement award against Apple. Here’s a news article:
http://arstechnica.com/tech-policy/2015/10/apple-faces-862m-patent-damage-claim-from-university-of-wisconsin/

And the underlying patent (US5781752):
https://www.google.com/patents/US5781752

To me, this says that:

* Improvements to prediction meaningfully improve performance of real CPUs.

* Even incremental improvements in prediction are worth hundreds of millions of dollars!

It will be most interesting to see how the Mill’s prediction (and anti-false-aliasing deferred load) mechanisms work in practice to improve single-thread performance.

Reposted from comp.arch with permission, as likely of general interest:
———————————————————————–

On 6/28/2017 1:47 PM, Stephen Fuld wrote:

The discussion in another thread about branch prediction versus exit prediction got me thinking, and that led me to realize that I didn’t fully understand Mill exit prediction. So let me ask some questions as a means of increasing my understanding.

What exactly are you keeping? The address of the instruction that is predicted to cause the exit? The address of the EBB that is predicted to be executed next? The number of cycles until the exit? I can see advantages for each, and perhaps even multiple things.

The latter two; see below.

I presume the “index” for the predictor is the starting address of the EBB. Is that correct?

More likely the entry index into the SRAM prediction table.The entry address of the executing ebb is in a specReg (whimsically called “entryReg”). That plus the target offset from the prediction gives the entry address you will exit to. Rinse repeat.

If the EBB contains a (perhaps) conditional subroutine call, is that temporary exit from the EBB handled by the exit predictor? I see problems with both yes and no answers. Or is there some other mechanism to handle this case?

Yes, every transfer of control involves a prediction. Eventually there will be a return prediction which takes the target from a conventional return-address stack.

What about conditional branches within the EBB? Are they not predicted at all?

There is no such thing on a Mill. You can branch to the beginning of yourself (one-ebb loops are *very* common on the Mill), but you can’t branch into the middle of any ebb including yourself.

Thanks in advance for helping my understanding.

This is more fully explained in http://millcomputing.com/technology/docs/#prediction, but here’s an overview:

Each logical entry contains some prediction history state, the details depending on the prediction algorithm(s) used; those are not program-visible and may vary by member. Possible keys include the entry address of the ebb that is going to exit; some history of such addresses; some perceptron or TAGE logic derived from such addresses, and so on. In general the Mill can use the same algorithms as any other ISA, but there are fewer entries (one per ebb rather than one per branch) but each entry has more prediction state (as described below vs. one taken/untaken bit). However it is done, the prediction logic must produce a prediction-table entry index and from that a prediction.

Each prediction contains two critical pieces, plus assorted niceties. One is the target, conceptually the address of the next ebb to execute. In practice it is the offset from the entry of the executing ebb, because all Mill branch-like things are entry-relative. As a result we don’t have to have a 60-bit address for each. In effect entry offsets form a linked list in the prediction table, so the prefetch logic can run arbitrarily ahead of fetch and execution. Other than representation, the target is similar to what is in a BTB.

The other crucial part of a prediction is a duration: the number of cycles between when the ebb is entered and when it exits. Duration is statically known; Mill is a statically scheduled exposed pipeline machine. If the duration in the prediction is three (for example) then the fetch and decode logic knows to fetch and decode exactly three (very wide) instructions before starting to fetch from the next ebb in the target chain.

Some of the niceties: rather than the duration being in cycles from the beginning of the ebb, the duration is in cache lines plus instructions within the last cache line. This both tells the prefetcher how many lines to munge, and also reduces the number of bits needed for duration in for large ebbs. Duration can overflow any fixed bit assignment of course; we have not yet determined whether injecting a dummy branch or simply permitting a mispredict at the end of large ebbs is better. Current our working sims use a dedicated set of logN representations for the long duration in lines. This will always mispredict (5 cycles) and may be over-eager in fetching from DRAM, but so far it looks like over-eager is better than under-eager. Pending measurement.

Another nicety: Mill code can have several (possibly conditional) calls in a single instruction; taken calls are executed in slot order and each can see the results of its predecessors. Each unconditional or taken call will have its own prediction, so an instruction-count duration is ambiguous if there are more than one. Consequently the duration is not only cache-lines+instructions but cache-lines+instruction+taken-calls.

There is a pretty conventional return-predictor; a table entry for a return uses a dedicated target value to indicate a return.

There is a transfer-kind code in the entry. This is used both to distinguish returns and to let the transfer hardware get a head start on the side-effects of the transfer: calls create stack and spiller frames and returns unwind them, the leave op discards in-flights, etc. Mill is very CISC, in the sense that single ops do a lot, not in the VAX-like sense in which ops are composed out of subops that must be parsed and interpreted in the context of the rest of the instruction; unlike x86 there is at most one memory access per operation. There’s good and bad in that. On the one hand a call (say) is conceptually simple, encodes densely, and is free of special cases. On the other hand the ISA gives you exactly one way to make a call, and you can’t tailor your own call protocol.

A great many loops on a Mill are one or only a few instructions in one or a few ebbs. As in many architectures there is a loop buffer on a Mill, or rather two of them. One of them holds the hardware signals coming from the decoder; the decoder is a 3-cycle process so we buffer up to three signal sets, and a special prediction tells the decode-and-issue to feed from the signals buffers rather than decoding around the loop. This doesn’t speed anything up (we issue every non-stall cycle regardless), but it does save power. The second loop buffer is the i$0 microcache that holds some small (per member) number of cache lines fully associative. If the lines of a loop, whether one or several ebbs, fit in i$0 then we avoid banging on the main instruction cache, again saving power.

An idea for debunking – this seems as good a place as any.

A fundamental issue that branch prediction attempts to solve is that there is no explicit clue as to a branch (or computed jump or call or return) target, until the actual PC-mutating instruction itself (is decoded).

This is directly analogous to the memory load problem – you don’t see the memory address until (the same instruction as when) the load result is supposed to be available.

So… why not solve it with explicit support for preload, rather than prediction.

In more (deliberately vague) detail:

Add a second register/buffer in the decode stage. Include an explicit ISA instruction to fetch the alternative instruction stream. As with ‘load from memory’, you can do this as soon as you know what the next (possible) PC/IP target is, which for most conditional and absolute branches/jumps/calls is known at compile-time. C++/JVM etc. ‘virtual’ call destinations, while dynamic, are also typically available at least several instructions before the actual PC/IP switch point (from linear execution).

You want, of course, to implement this in hardware at the level of i-cache lines, probably 32/64-byte units. At all times, your primary source of instructions is the linear execution path, but you have a prepared line of ‘alternative’ (possibly conditional or virtual or return) address instruction buffer.

The actual branch/jump/call/return instruction then reduces to a ‘switch-instruction-buffer’.

Even better, call/return for leaf call-points is a natural consequence – the return point is immediately available as the alternative instruction buffer after the ‘call’.

I seem to recall some history in this approach, but I don’t have any references at hand.

At a high level, it is entirely analogous to ‘prefetch… load’, which the Mill does explicitly as I recall.

So, is branch prediction actually necessary, or is it a reaction to pipelining on ISA’s which didn’t originally consider that they might be pipelined?

😀

• This reply was modified 7 years, 1 month ago by  rolandpj. Reason: clarification, grammar
• This reply was modified 7 years, 1 month ago by  rolandpj.
• This reply was modified 7 years, 1 month ago by  rolandpj.

Turning the question of branch prediction on its head. Would it be possible to have a CPU that does not need any branch prediction?
For example, the EBB has a single entry with multiple exit branches.
What about if one included in the EBB the first few instructions after each branch.
So, if a branch was taken, the CPU would already have the post branch instructions to execute before it needed the next EBB.
So, say we added 5 instructions after each branch to the EBB. While executing those 5 instructions, one could retrieve the next EBB. Once the next is retrieved, we could start offset by 5 instructions into the new EBB.
Ok, so there is a little duplication for those 5 instructions, but could one drop the whole need for prediction as a result?
Note “5 instructions” is arbitrary. Probably best to match the pipeline size or something like that.
This sort of approach is really only possible for a CPU that knows about the concept of a EBB, instead of individual instructions.

Regarding indirect jumps. I don’t understand how the predictor might predicts those. Particularly jump tables, where you start with an index variable, and do the equivalent of:
goto jump_table[index];
Do you know how the predictor predicts indirect jumps?