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
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
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
incis 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
inis set to 37. If
loadis selected, this second Mux16 will output the value from
in(i.e., 37), thus “jumping” ahead or, in this case, behind. If
loadis not selected, however, this second Mux16 will pass the previous Mux16’s value through.
- the result of this
loadMux16 is then passed to a third Mux16, which handles the
resetis 0, then we pass the value through as is. If
resetis one, however, then the Mux16 outputs all 0s, since its
binput 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
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
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
- the unadulterated current value from the register (all bits are low)
- the incremented value from the register (
- a new value from
- 0 (
Aaron uses a Mux4Way16 to handle each of these four cases. But to do so, the
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:
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
inc) to handle the logical cases.
- 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