RC16. Making a Program Counter

Daily dispatches from my 12 weeks at the Recurse Center in Summer 2023

Next step on the road to a DIY computer is a program counter. This is an important component of our CPU since each consecutive output specifies a memory address where a program instruction resides (I think).

The PC’s state (it’s the current count of program counter) is stored on a register, and the unit has inc, load, and reset bits, which specify whether the value on the register should be incremented by one, whether it should load a new value from in (I believe this will be used in jump commands), or whether the register value should be reeset to 0. The way we handle these scenarios is through three successive Mux16’s, which act as conditional statements that successively transform the register value depending on the inc, load, and reset bits (so, in this sense, not unlike [the pipeline structure that defines the ALU[(https://www.datadoodad.com/recurse%20center/RC12/).

To walk through it, then: Let’s say our register value is 129.

• that value (129) and its incremented value (130) are output to the first Mux16. If inc is set to 1, the Mux16 outputs the incremented value (130), else it outpus the untransformed value(129)
• the 16-bit result is passed to a second Mux16 along with a 16-bit input from in. Let’s say in is set to 37. If load is selected, this second Mux16 will output the value from in (i.e., 37), thus “jumping” ahead or, in this case, behind. If load is not selected, however, this second Mux16 will pass the previous Mux16’s value through.
• the result of this load Mux16 is then passed to a third Mux16, which handles the reset flag. If reset is 0, then we pass the value through as is. If reset is one, however, then the Mux16 outputs all 0s, since its b input is pulled low.

The result of this pipeline is our output. However, that output is also loaded into the register (whose load bit is always pulled high, so that it is always loading whatever the circuit is outputting, thus “remembering” its previous count). And in that sense, it would be more accurate to say that the register does not store the PC’s current count, but its previous count.

An interesting feature of this structure is that the reset bit clobbers the load bit, which in turn clobbers the inc bit. So in other words if inc, load, and reset are all high, the PC will output 0, since the final step in the pipeline is to reset the incremented and then loaded value.

Program Counter Variations

Here are a few variations my fellow nand2tetris-ers came up with. While the above architecture seems simplest, these are useful since they help clarify the workings of the PC.

Something that makes Suvash’s variation interesting is that the register in this case only loads a new value if there’s a new value to load. If the inc, load, and reset bits are all 0, then the register doesn’t load anything since we’re telling the PC essentially to do nothing – don’t increment the existing value, don’t load a new value, and certainly don’t reset the value to zero. If any one of those bits is 1, however, the register’s load goes high and it remembers, which makes sense because, in this case, the value is being modified in some way.

This variation is also helpful since it makes clear that the register’s value is only relevant in the case that inc is high. If we’re not incrementing but are loading and/or resetting, we don’t really care about the register’s value, since it’s getting replaced anyway. Hence the first Mux16’s a input is pulled low: either this Mux16 outputs the register’s incremented value or all 0s.

And actually, that observation is making me wonder whether the third Mux16 which handles the reset bit is necessary at all. I think it may not be, since if inc is low and load is low, the second Mux16 is outputting 0 already, and the reset bit in this case would have the responsibility only of telling the register to load (which it would due to the OR logic at bottom right).

Aaron’s variation is more complex, but these’s something to be learned here as well. We know that we want one of four outputs from our PC depending on the load, reset, and inc bits:

• the unadulterated current value from the register (all bits are low)
• the incremented value from the register (inc is high)
• a new value from in (load is high)
• 0 (reset is high)

Aaron uses a Mux4Way16 to handle each of these four cases. But to do so, the reset, load, and inc bits have to undergo some logic.

Miccah’s variation is the newest addition and the one that rocked my world the most. A Mux8Way16, of course! In the original PC above, we have three Mux16’s chained together – among other things, Miccah’s variation makes the crucial observation that these three consecutive Mux’s can be collapsed into a single Mux8Way16. It hadn’t occurred to me to draw up the truth table, but once we have that (which, it bears mentioning, retains the hierarchy from before re: reset clobbering load clobbering inc), it’s just a matter of assigning the desired outputs to each of the Mux8Way16’s eight inputs. Miccah’s also helps clarify Aaron’s observation about the PC needing to output one of four things, however it uses the Mux8Way16’s three input select bits (in this case reset, load, and inc) to handle the logical cases.

Also today

• Drew out some RAM-related schematics
• Still meeting new folks through coffee chats
• Linked List brain melt in neetcode group
• Paired with nand2tetris crew on the above program counters
• Paired on someone’s deep learning project