How to keep the instruction prefetcher filled up

Question

My understanding is that the Intel 8088 has this buffer which reads ahead in the instruction stream whenever it has a spare bus cycle or two, so that when the time comes to execute that instruction, if you're lucky, that instruction doesn't need to be fetched from DRAM because it's already done for you. So for each instruction there are two possibilities:

• The instruction has been fetched already and is ready to be decoded

• The instruction has not been fetched, and therefore the processor must stall until it has

It's not just luck though, because if there has recently been a spare cycle of the appropriate kind here or there, that instruction is more likely to have been fetched.

So presumably there are/were peephole optimisers that reorder the instruction stream to increase the likelihood that some of the later instructions can be fetched ahead of time. So how does the instruction stream need to be reordered then, to decrease the latency of this instruction prefetch buffer?

Answer 1

My understanding is that the Intel 8088 has this buffer which reads ahead in the instruction stream whenever it has a spare bus cycle or two, so that when the time comes to execute that instruction, if you're lucky, that instruction doesn't need to be fetched from DRAM because it's already done for you.

The buffer isn't some kind of optional read ahead,it is the instruction buffer. Before an instruction can be executed, it has to reside fully within the buffer. Only then it can be transfered, as a whole, to the execution unit.

What differentiates it from other machines with a similar fetch logic is that it doesn't start fetching when a new instruction is needed, but whenever there is empty storage within and there is a memory cycle without an outstanding data read or write request.

The instruction has been fetched already and is ready to be decoded

It will be already partially decoded by the BIU (Bus Interface Unit), for example to decide about its length.

The instruction has not been fetched, and therefore the processor must stall until it has

And the third one is a partially fetched instruction. Just it isn't a stall, it only means that now instruction fetches get priority over outstanding data fetches and the EU (Execution Unit) waits for the next one to be fetched in full.

It's not just luck though, because if there has recently been a spare cycle of the appropriate kind here or there, that instruction is more likely to have been fetched.

And there are many such cycles where the EU is busy but there is no outstanding data request to be handled.

So presumably there are/were peephole optimisers that reorder the instruction stream to increase the likelihood that some of the later instructions can be fetched ahead of time.

No need for such bloaty software as the likelihood for such 'holes' is rather large. Just keep in mind, every address calculation on the x86 takes 6-12 clock cycles (T-states). So as soon as there is a memory operand (i.e. not immediate or register), already one fetch can be made. Plus, of course, the cycle time for the instruction itself, which is anywhere between 2 (register-to-register move) and 133 (16-bit multiplication) clocks.

Having the EU wait for the BIU isn't anything special or a problem and by no means a fault of the BIU or software. It just means that the memory bus is saturated by the combined need of transfer for instructions and data into and out of the CPU, beyond the amount of cycles needed to compute. In fact, this is the desired state. Useful bus utilization is at maximum. In comparison, even the much acclaimed pipelining of the 6502 results in up to 25% waste cycles where the bus stalls (*1).

So, unless the instruction stream is made up of all register-to-register instructions of the simple kind, there will be plenty of room for instruction fetch. And at least on a 8086, even then it rarely runs empty, as these instructions are (mostly) 2 or 3 cycles with 1 or 2 bytes encoding. 1-Byte encoding with two-cycle execution means the bus is fully occupied with instruction fetch (2 bytes at once) while the EU is fully occupied with executing them - two (single byte) instructions per two byte fetch. It needs a stream of several two-byte register-to-register instructions to have it run low. Assuming a filled buffer in the beginning, it will need a sequence of 5 two byte instructions until the EU has to wait for one cycle. Since even a simple register-to-memory compare (like in a search loop) is already 9 cycles, there isn't much to fear.

Now on the 8088, the situation is worse due the limited bus size delivering only half the bandwidth. Here a sequence of several register-to-register instructions will make the EU wait for new instructions, as its 5-byte buffer will run empty soon. Again, this is not something that happens a lot in average code, as memory address calculation (and more complex instructions than such simple) will leave enough space for fetching; even with just half the bandwidth the effective throughput does not fall down to 50% (of an 8086) but still delivers 60-70%. Not bad for requiring only half the RAM and ROM chips :))

It's always helpful to keep in mind that this is just a buffer for one instruction at maximum length, not some kind of cache or the like. All it does is improve the performance and allow more complex instructions while decreasing chip complexity to handle them. Instead of having fixed 'points' marked within an instruction to fetch (parts of) the next instruction, it's an abstraction layer, so a mechanic independent of the execution can handle fetch.

Bottom line, a 8086/88 EU waiting for fetches is just one utilizing the bus at maximum, thus achieving already the highest possible speed.

So how does the instruction stream need to be reordered then, to decrease the latency of this instruction prefetch buffer?

Mix in some memory access, at best with way complicated addressing, and there will be plenty of room to keep the buffer filled ahead of time. That's also why compiler code - which is usually way more memory focused than assembly - rarely runs into this barrier. Of course, this means in turn that it is not using the full memory bandwidth like hand written Assembly does :))

Does the same go for the 8086?

(From a comment by Wilson)

Yes, as described above. On the 8086 it's just even harder to get it to stall. The buffer on a 8086 is 6 bytes instead of 5 for the 8088. The maximum instruction in original 8086/88 code is 5 bytes long (*2), thus the buffer only needs to be 5 bytes to deliver a whole instruction. Since the 8086 operates on a 16 bit bus, fetches will always be two bytes at once, thus filling in a full instruction can result in 6 bytes fetched.

---

*1 - Most of them due the second cycle of a single byte instruction - much the same way as with an 8086, except for completely different reasons.

*2 - No, except for REP, no prefix is part of the instruction when the buffer is considered, as segment or lock prefixes are instructions for the BIU, not the EU.

Answer 2

The 8088 and 8086 are microcoded CPUs, and need multiple cycles to execute each instruction. The fastest instructions take at least 2 cycles to execute, and most take much longer. Any instruction that accesses memory takes at least 8 cycles, and often more like 15-20. On the other hand memory accesses occupy the bus for 4 cycles.

It therefore follows that the only instructions that deplete the queue without chance to refill it are those short 2-3 cycle instructions. These are basically only register-to-register operations, excluding multiplies and divides. Register/immediate instructions take 4 cycles, but also fetch an extra instruction byte, so also deplete the queue.

As long as you disperse reasonable numbers of longer operations (including anything that involves a memory access, or multiply/divide operations) in the instruction stream, it should be unlikely that the instruction buffer underruns other than immediately after a jump.

Answer 3

On the 8088 (which was used in the original IBM PC and early clones thereof), but not on any of the other processors used in subsequent machines, a typical two-byte instruction will take eight cycles to fetch and 2-3 cycles to execute. Because of this disparity between instruction-fetch time and execution time, the memory bus will be almost never be idle except when executing long instructions like multiply/divide. Thus, in many cases the simplest and most accurate way of the estimating execution time for a piece of code is to simply count the memory operations and multiply by four. There are some cases that require more precise analysis of the timing relationship between the execution and bus-interface units, but in most of those the simplest way to determine execution time is to feed the code to an 8088 and measure it.

Interestingly, many books from the era when the 8088 was the dominant processor ignore instruction-fetch times. Consequently, they give optimization advice which would tend to be reasonable on future machines using the 8086 and 80286, but is in many cases just plain wrong on the 8088. For example, some such books suggest that if one needs to move DX to AX or vice versa, and don't care about what happens to the other register, using "XCHG AX,DX" will be smaller but slower than using "MOV AX,DX" or "MOV DX,AX". While that may have be a speed/space trade-off on some later CPUs, on the 8088 used in the PC the "slower" form is in practice almost always faster.

Note that even though effective address computation times may appear long, they are rarely sufficient to give the bus unit any idle time. An instruction like "add [bx+1234],ax" is four bytes long, which means it will take 16 cycles to fetch, and it will have to perform four bus operations (tying up the memory unit another 16 cycles) when it executes. One might look at the execution-unit time and think it's so huge that the bus unit would catch up, but since the instruction requires performing 8 bus operations, the time required for the effective address calculation really doesn't matter. If one did nothing but memory operations using short instructions, the bus interface unit might catch up with the execution unit (many short instructions that access memory have execution times that are a cycle or two longer than the time required to perform all the memory accesses) but most two-cycle instructions that don't access memory give the execution unit a 5-6 cycle advantage, so for most typical instruction mixes the memory-access times will dominate.