2
$\begingroup$

Where is program counter stored? CPU caches?

Also how big are these counters?

What happens if that memory has been filled up?

I know that it's a value that stores the next instruction for the CPU to process, as well as it increments with the size of the next instruction to cycle for the next instruction for the CPU to process, and the cycle continues, that's as far as I know, right?

$\endgroup$
  • $\begingroup$ What research have you done? This is covered in standard computer architecture textbooks. We expect you to do a significant amount of research before asking. $\endgroup$ – D.W. Jul 17 '15 at 0:11
  • $\begingroup$ @D.W. To be honest I am doing this kind of research, I was in Wikipedia reading everything about processors, and their instructions, as well as caches and SSE, and came across this, so I wanted to ask $\endgroup$ – OverCoder Jul 17 '15 at 1:11
  • $\begingroup$ I think it's possible you might have misunderstood my comment. We expect you to do research to try to answer your own question before asking here, and to tell us in the question what research you've done and what you've found. See, e.g., cs.stackexchange.com/help/how-to-ask. $\endgroup$ – D.W. Jul 17 '15 at 1:35
4
$\begingroup$

Inside a modern high-end CPU, the "program counter" is probably not stored in a single place. Superscalar out-of-order execution requires more than one instruction to be executing at a single time, some of them executing speculatively.

To understand what's going on, you need to consider what the program counter is used for. I'm going to use the Intel Core 2 microarchitecture as an example, mostly because it's the only decent-but-uncluttered diagram that I could find. Most modern high-end CPUs are broadly similar, in that they have a Tomasulo-like pipeline with register renaming. A RISC (e.g. MIPS or ARM) might have fewer decode stages. Also, not all CPUs implement a retirement register file; there are other methods which do the same job.

Nonetheless, let's go with this for the moment.

Intel Core 2 Pipeline

Instructions are (broadly speaking) streamed from the top to the bottom of the diagram. They start in the cache (and of course may have to be fetched into the cache), go through decoding and being stored in different buffers, until they end up in the reservation station. Here it waits until it is ready to execute.

When everything that an instruction needs becomes available, it goes to an execution unit. In the diagram, the yellow parts are the "normal" execution units (integer, floating point). There are also execution units for memory operations, but we'll ignore those for the purpose of this discussion.

When an instruction has finished execution, the results are posted on the results bus (called the "common data bus" in Tomasulo's original paper). These results may wake up instructions which depend on those results, and the cycle continues.

Now, think for a moment about what the program counter is used for.

First off, let's think about instruction fetch. It needs to know what address to send to the instruction cache for lookup. Most of the time, it's the next address. However, do consider that the cache line width isn't a single instruction; in this example it's 128 bits. So the instruction fetch unit actually increments its "program counter" by 16 bytes, no matter how big each instruction is.

Branch instructions complicate instruction fetch. Unconditional branches are straightforward once you've recognised them, so the instruction fetch unit gets some input from pre-decoded instructions.

Conditional branches are similar, except that the instruction fetch unit needs to decide whether to guess that the branch was taken or not taken to keep instructions flowing.

So the IFU has an idea about what the "program counter" is, but it is granular, working on a cache line at a time.

Now let's think about execution. The CPU would like to execute instructions out of order if it can, however things can happen which complicate that. The most obvious problem is if the IFU incorrectly predicted a conditional branch. However, instructions can also raise exceptions, and also the CPU might need to respond to an external interrupt.

To achieve this, the CPU needs to be able to recreate the CPU state as if it was executing instructions sequentially at the time that the control flow was interrupted. This is the job of the reorder buffer.

The reorder buffer is conceptually a queue of instructions, ordered by the "logical order" (i.e. the order that they would be executed if this was a scalar in-order processor). An instruction enters the queue as it travels down the fetch-and-decode path. Once it is in the ROB, it can execute out-of-order.

When an instruction completes, its entry in the ROB is updated noting that it is now complete. An instruction can leave the queue (it is "retired") if it has completed, and every instruction before it in logical order has completed or retired.

The "result" of many instructions is to write a value into a register. If that value is used by a subsequent instruction which is awaiting execution (i.e. it's in the reservation station), then this is handled by the internal results bus. Either way, the result is also stored in the instruction's entry in the ROB. This arrow is not shown on the diagram, but it happens.

When an instruction retires, any register write that it does is stored into the retirement register file. Because instructions are retired in-order, this register file actually stores the state of the machine registers exactly as they would be if the instructions were executed in-order. This is why it's also called the "program visible state". This is the view of the registers that the program "sees", what is saved and restored on a context switch, and so on.

So the second place where there the "program counter" is stored is here, in the instruction retirement unit. This is the program counter as the program sees it, without any speculation, but it's decoupled from instructions that are being fetched and executed.

As an aside, the ROB is also how faults and exceptions are handled. If a fault occurs, then the ROB for the faulting instruction is updated with information about the fault, and every instruction after it in the ROB is removed, along with a flush of the fetch-and-decode parts of the pipeline. This ensures that instructions after the fault don't "happen" even if they have been executed already: the results of those instructions never make it to the program-visible state. Speculative execution is handled in a similar way.

A third place where the program counter may be stored is in the ROB itself. It may be convenient to store the program counter of each instruction along with the instruction. Note that it may not be necessary to store the whole program counter; it may be sufficient to store enough information to recreate the program counter as needed.

A final place where the program counter may be stored is as a general-purpose register. Exactly what this means is a bit complicated to explain if you don't know how register renaming works, but some instructions might need the value of the program counter (e.g. it might be used for memory addressing in position-independent code), in which case transient copies may be stored in reservation station entries of instructions which use it.

So what I hope you can see here is that the real answer is "it's complicated". The program counter is different from other registers in a modern CPU, and there is no one place where it's really "stored", because more than one instruction is "happening" at any given point in time.

$\endgroup$
  • $\begingroup$ I didn't read the whole of your answer (sorry), but is your main point, "when you have pipelines, you'll have one PC register per stage"? $\endgroup$ – Raphael Jul 17 '15 at 6:09
  • 1
    $\begingroup$ My main point is that when you have out-of-order issue (and especially if you're superscalar) then the program counter is a property of the instruction, not a property of the CPU. $\endgroup$ – Pseudonym Jul 17 '15 at 7:10
  • $\begingroup$ This is the answer I am expecting, It's detailed as I want, although I had to read it multiple times to understand it, It was nice to read, thanks. $\endgroup$ – OverCoder Jul 17 '15 at 15:49
  • $\begingroup$ @Pseudonym Thank you for this excellent explanation! $\endgroup$ – Sujay Phadke Oct 6 '17 at 6:49
4
$\begingroup$

Program Counter is a register in the CPU hardware.

Effectively it's a digital counter so consists of binary latches where each latch represents a binary bit. Number of latches,ie the size of the PC depends on the processor architecture.

If overflow takes place in a Program Counter it simply wraps around, like a normal ring counter. For example if PC has a capacity of 100, it counts from 0 to 99. At 100 it goes back to 0. AT 101 value stored in PC is 1.

$\endgroup$
  • 2
    $\begingroup$ You may want to note that the PC register(s) (of course) stores only the PC of the currently running process(es). Those of currently stalled processes lie in memory, with the rest of the register contents. $\endgroup$ – Raphael Jul 16 '15 at 14:36
  • $\begingroup$ I tried to keep my answer to the point. OP didn't explicitly ask questions regarding working of the PC. Nevertheless thank you for reminding me. $\endgroup$ – Sagnik Jul 16 '15 at 14:39
  • $\begingroup$ Very nice answer, I also read that after an instruction ends, the PC increments with the size of that instruction to jump to the next one, but, WHERE is that PC stored? RAM? L1 Cache? Or just special part of the CPU that is capable of storing that value? $\endgroup$ – OverCoder Jul 17 '15 at 1:15
  • $\begingroup$ @Raphael Oh! this is something that was confusing to me, thanks for this clarification too, very useful. $\endgroup$ – OverCoder Jul 17 '15 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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