Computer Architecture

The other day I was studying some algorithms used in the file system and buffers that the Unix system used. I was fascinated by the cleverness and engineering intuition behind the implementation. The engineer inside of me screamed in excitement, “Holy shit! This is the real deal.” Now I have a crazy idea. Why not build my own operating system from scratch? Sounds insane, right? Yes, this scares me. I have no idea whatsoever, but with the right knowledge and, most of all, the right mindset, I think this can be accomplished, though it may take years and years. This is why you are reading this, as this is me documenting my journey. So let’s dive into this voyage. ...

As we are building a computer, though it’s virtual, from the ground up, we should all ask ourselves a question. What actually is a computer? Hmm, time to think deep. In my opinion, a computer is a glorified calculator. More specifically, it’s a high-speed adder, capable of doing millions and billions of additions per second. But you may ask, “Shut up! Computers do crazy calculations.” Yes, you are right, but every operation and calculation you think of can be, and is, derived from the addition operation. ...

I was very excited to learn how the heck, using just logic gates, we can build memory to store bits. It turns out that, using just two NOR gates, we can store 1 bit. The two NOR gates are configured such that one input of the gates is the set and reset input respectively, whereas the other inputs are connected to the output of the opposite gate. Now, connecting the input of one gate to the output of the other gate creates a kind of feedback loop by which the previous state of the circuit determines or influences the current state. It’s the nature of a feedback system. ...

Yes, I have implemented RAM. First, I want you to have a look at it: export class RAM { private data: SharedArrayBuffer; private dataView: Uint8Array; private totalBytes: number; constructor() { // max address lane is 32 bits, so max ram size is 2 pow 32 this.totalBytes = Math.min(2 ** 32, 1 * 1024 * 1024); this.data = new SharedArrayBuffer(this.totalBytes); this.dataView = new Uint8Array(this.data); } getBuffer() { return this.data; } read8(address: Bit32) { const dataNum = this.dataView.at(this.addressToIndex(address)); if (dataNum !== undefined) { return decimalToBinary(dataNum, 8) as Bit8; } } write8(address: Bit32, data: Bit8) { const dataNum = binaryToDecimal(data); this.dataView[this.addressToIndex(address)] = dataNum; } private addressToIndex(address: Bit32): number { const index = binaryToDecimal(address); if (index >= this.totalBytes) { throw new HardwareExpection( HardwareExceptionType.MemoryFault, `Invalid address to RAM: 0x${index.toString(16)}`, index ) } return index; } } Whereas in the register I used an array variable to store the values, the RAM uses SharedArrayBuffer. It is similar to ArrayBuffer, which is a raw binary buffer. The array buffer is quite similar to real memory because it is also laid out contiguously in memory, one byte after another, just like actual RAM. Thus, it provides good performance when accessing and manipulating the buffer. ...

As I was studying computer architecture, we implemented logical gates, combined logical gates to build an adder circuit, implemented flip-flops with a combination of logical gates to store a bit of information, and by combining multiple flip-flops, we implemented registers and memory. We have the tools necessary for computation, but as you can see, without a human punching in every number and setting/resetting circuits, no complex computation is possible yet. Taking multiplication as an example, we need to store one number in memory/register, enter another number as the input to the adder, sum it, then store the value in the accumulator, and repeat the process until the multiplication is complete. It’s a hassle. So automation is required. ...

The previous day, we just began to automate our machine with a counter. It’s definitely a stepping stone. And we also introduced what an instruction might look like for our machine. Now suppose we have just added two values in registers r1 and r2 and stored the value in register r3 with an ADD instruction. Now suppose we want to store the added value in r3 to memory for later use. For this, we will have a STORE instruction that could take the value from the register and store it at a memory address. ...

Yesterday, we got into detail about multiplexers. Now, you might be thinking that with n select inputs, we could output any of the 2ⁿ data inputs through a single output line. Now, isn’t it possible that we could pass the data from a single input to any of the multiple output lines? Think of it this way: while with a multiplexer we narrowed multiple input lines down to a single output line with a selector, similarly, we could have a device that does the exact opposite. It takes a single input data line and, with the proper selector bits, passes it to one output line among the multiple ones. And this is called a demultiplexer. ...

As usual, I was doing my study on the microprocessor and computer architecture. I was skimming through the ALU part, and as far as my understanding went, I had already implemented the adder. For logical operations, it seemed pretty obvious: the whole CPU/computer is built upon the foundation of these logical gates, so the Logic Unit must contain these gates to operate on ‘N’ number of inputs. But I was wrong, or rather, I had no idea about other binary operations that might be useful enough to be implemented at the hardware level with dedicated circuitry. The first one I encountered was the Logical Shifter. ...

As promised, I have come up with an elegant solution for implementing the right shifter. Initially, I was thinking of building a separate circuit for it and then using a 2-to-1 multiplexer so that the appropriate circuit could be selected. But as I was implementing this circuit, I came up with a realization: Isn’t right shifting just the reverse—or perhaps the exact opposite—of left shifting? Let’s investigate it ourselves. Say we have an 8-bit binary number: ...

Previously, I have talked extensively about the circuitry for logical left/right shifters and, with position inversion, implemented both left and right shifting using just the left shifter circuit, paired with position inverters in case of a right shifter. We have already built it. Today, my ambitious plan is to again modify the shifter circuitry so that this same shifter circuit, with additions/modifications to some components, can perform both shifting operations as well as rotation operations—yes, in both directions. ...

It has been more than two days since I started working on a unified logical/arithmetic shifter and rotator circuit. It is getting increasingly complex, especially after adding the arithmetic right shifter and, more importantly, the rotate-through-carry logic. But slowly, I am getting a better understanding of the design, and I am now getting close to completing and thoroughly testing it. Let’s first talk about the arithmetic right shifter. We have already had a thorough explanation of the left and right logical shifters. Their usefulness comes from operations such as multiplication and division by powers of two, as we have already discussed. ...

It’s been long, I guess the shifter made me shift the day when I should have posted. But, not going to lie, I was skimming through both the logical and arithmetic shift operations and the rotation operations too. I have used mathematics and the inversion law to normalize the bit position and have just a single left shifter/rotator circuit for both directions. But there was just one more operation where I had to really think deep and analyze: rotate through carry. ...

We have come across the arithmetic part, which was binary addition and subtraction. We have also come across the logical parts, such as AND, OR, NOT, and XOR gates. Now, the natural progression is to combine these circuitries to form a unit. So, that’s the ALU. Let’s have my implementation presented as follows. I first had a 1-bit ALU, which is a simpler circuitry: // control signals // [ input 1 invert, input 2 invert/negetive, ...operations(2 bit)] // operations // [0,0] -> AND // [0,1] -> OR // [1,0] -> XOR // [1,1] -> ADD export function aluBit1(carryIn: Bit, inp1: Bit, inp2: Bit, controlBits: Bit4): [result: Bit, carryOut: Bit] { const inp1Invert = controlBits[0]; const inp2Invert = controlBits[1]; const operationBits = controlBits.slice(2) as Bit2; const inp1Transformed = xorGate(inp1, inp1Invert); const inp2Transformed = xorGate(inp2, inp2Invert); const andResult = andGate(inp1Transformed, inp2Transformed); const orResult = orGate(inp1Transformed, inp2Transformed); const xorResult = xorGate(inp1Transformed, inp2Transformed); const [addResult, carryOut] = fullAdder(carryIn, inp1Transformed, inp2Transformed); const result = mux4To1( [ andResult, orResult, xorResult, addResult, ] , operationBits ); return [result, carryOut]; } There are four control bits in total. The first two are for inverting the two inputs, and the remaining two are inputs to the mux to select the desired primitive operations. With 2 bits for operation control, we get a total of four unique operations. I have chosen AND, OR, XOR, and ADD. You might think: where is the NOT operation? What about subtraction? How can we get other gates, such as NOR and NAND? Those are some legitimate queries. ...