1

I'm reviewing some lecture slides and had a question on the following slide :

enter image description here

Assumptions (8 clocks to transfer data)
Up to 3 outstanding load requests.

The slide is illustrating that the number of useful math instructions that can run is limited primarily by the memory bus bandwidth. Of course the "8 clocks to transfer data" is a limit decided by the CPU architecture and memory bus but is my understanding correct that "Up to 3 outstanding load requests" is a limit decided by the program?

In other words, if we had a program that had "Up to Infinity outstanding load requests", then there would be no stalls and the memory bus bandwidth becomes a nonfactor? Of course in this case the program doesn't actually need to use any of the data loaded from memory to run the math instruction.

4 Answers 4

5

"Up to 3 outstanding load requests" is a limit decided by the program?

No, that's a limit imposed by the architecture. The program is on the vertical axis. The CPU imposes the limit by stalling execution of the fourth load request.

(There are architectures where the programmer or compiler has to keep track of this themselves, where instead of stalling you would have a fault or crash if you tried to issue too many outstanding loads. Similar to MIPS branch delay slots. This proved to be unpopular and is extinct)

"Up to Infinity outstanding load requests", then there would be no stalls and the memory bus bandwidth becomes a nonfactor?

You have this upside down: if the program makes zero load requests, then memory bus bandwidth becomes irrelevant.

Edit: let's have an architecture diagram of Haswell from this web page

Intel Haswell Execution Engine

The limiting factor is the availability of execution units or issue units, the small boxes at the bottom of the diagram. That's where the work is done. Each takes one or more cycles to do its work. Every cycle, the decode logic assigns instructions to ports (in the case of Haswell, up to four instructions per clock). But the execution unit must be available. So if you issue two reads, they go into port 2 and port 3, and you cannot issue any more reads until those have completed. But you can do other stuff at the same time, and Haswell will aggressively re-order instructions in order to find things to do.

(Where there are multiple boxes below a port, interpret that as "you can do ONE of these things at a time on this port")

4
  • Thanks! What are some practical reasons for the CPU to stall the fourth load request? I assumed each load request gets dispatched to the memory controller and the kernel gets interrupted when the controller finishes fetching the block but the CPU can do useful work in the meantime?
    – Carpetfizz
    Aug 23, 2023 at 16:27
  • 2
    @Carpetfizz The kernel is entirely irrelevant here, except when the MMU can't resolve a virtual address (e.g. due to swapping or accessing other unmapped memory, which will trigger an interrupt). The CPU can pre-fetch memory locations into its caches, but at the end the data has to be loaded into a physical register of the CPU. The number of registers is quite finite. Also, the instruction pipeline has limited depth, so the CPU can only "see" a limited number of instructions for out-of-order execution at the same time.
    – amon
    Aug 23, 2023 at 16:38
  • @amom Is it fair to say that the compute is just as "instruction depth limited" as it is "memory bandwidth limited"?
    – Carpetfizz
    Aug 23, 2023 at 16:47
  • 1
    @Carpetfizz I have added a diagram - while instruction pipeline depth matters, the processor can also be made "wider" rather than deeper to give you more compute per cycle.
    – pjc50
    Aug 24, 2023 at 9:35
3

I think the number of outstanding load requests is supposed to be limit decided by the CPU architecture. I haven't yet seen such graph or piece of information where the number of loads would be limit in out-of-order execution (but on the other hand I haven't seen that much information about out-of-order execution).

But there are certainly some limits like the size of reorder buffer for the number of instructions which can be executed in out-of-order. This is number of instructions from the first that isn't yet finished till the one we potentially try to execute.

Answer to your second question is that if the CPU doesn't need any data, then the bandwidth is of course nonfactor. But the data will certainly be eventually needed and it is most noticeable in branches where the data is used to decide which way to go.

Even when using branch prediction with high accuracy and infinite size of reorder buffer you will eventually reach a point where you find out that you are executing the wrong path (it can take long time till you find out because you are waiting for the data which tells you so) and you will need to throw away everything from the point where you started executing the wrong instructions. This effectively creates a stall as it is like the work was never performed.

2

"Up to Infinity outstanding load requests" would only occur if loads never finished, or you could issue "up to infinity" of them per clock. You can't get above (max issues per clock) * (clocks to service a load) because the oldest loads are finishing as fast as you can issue new ones, even with unbounded memory bandwidth.

That gives you the upper limit on how much memory bandwidth can possibly benefit throughput. Add any more and you can't utilise it all.

1

There are two places were load instructions can be "outstanding".

First is the load/store unit which has a tiny queue that load instructions are issued to when the queue is ready. That queue will only accept a very small number of incomplete requests; three is a lot here. The number will be balanced so it's enough to run memory access at full speed (let's say one slow access to RAM followed by very fast loads from L1 cache which you don't want to have to wait), and the complexity (this needs some very complicated hardware, and two requests is much much easier than three which is again much much easier than four).

Second, there is usually a massive buffer for reordering instructions, that may hold hundreds of instructions that have to wait either for their operands to be ready, or for their execution units to be ready. So if you have a mix of 100 load and 200 other instructions, the first three loads go to the memory access units, 97 go into the instruction reorder buffer, and every time the memory access unit has fewer than three outstanding loads, instructions are dispatched to it. Meanwhile other instructions continue executing.

In this example, if your instruction reorder buffer has 500 entries, and your code has 1000 load instructions, then those 500 entries will be filled, by that time maybe 20 loads are done and 20 more entries in the reorder buffer are filled, and then the processor's instruction dispatch stalls. Every time a load completes, an instruction is moved from the reorder buffer and dispatched to the load unit, and the instruction decoder adds one more instruction to the reorder buffer.

So for some time, the reorder buffer can hide latency and execution time of loads, but at some point you will slow down.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.