Wednesday 30 April 2014

Writing a Virtual CPU in C++ (Accumulators & Multiplication)

This post forms part of a series, you can start at Part One here.

First things first, armed with our Electronics code, containing our Binary Adder in C++ we can go to our CPU and change the arithmetic logic add function for our new "AddTwoBytes" electronics function...

We can also, for the first time set the Overflow flag!



We saw our first program ran once again, try out some more yourself...

However, we're still very much limiting our CPU, and before we can go much further we need to introduce to ourselves the idea that the CPU, rather then using a reserved byte in memory, or the two registers we already have it performs arithmetic into an intermediary location, a temporary store if you will, this was a natural evolution of real processors, they moved from having very few registers and using the memory to store intermediate values to using new internal registers.  As the electronics got cheaper and the processors for creating chips streamlined and one of the first things added was this temporary location.

So in our code where we see:

Register0 = Register0 + Register1;

Really the register has no idea about overflows it just holds a binary number, now we've included out Binary Adder we get the overflow, so really storing the resulting value back to register 0 is a bit of a fudge.

The real location it should go to is called the Accumulator, in fact when the Accumulator was added to processors it gave rise to a whole new way of thinking in computing, and some even call it "Accumulator Based Computing" or ABC.  I was very briefly introduced to this during my A-Level Computing course in 1994, however 20 years on I have yet to meet a recent software graduate who realises there was a time when we didn't store intermediates in the processor.

For using an Accumulator has become so ubiquitous as completely block out the idea of labouring saving values back and forth with the memory as we have been doing.  Indeed my wishing to highlight that using an Accumulator is not the same as storing to a register then saving to memory has been the reason behind our labouring over our registers and reserved memory!

To add an accumulator however we need a new specification for our CPU...


You can read more about accumulators and their history here.

So now we include the Accumulator, and fix the bugs I made by making a mistake in the last video :)


Armed with an accumulator, and the Overflow flag working, we can now implement our Multiply differently...

Clear Accumulator to zero
for each time add value to accumulator
if overflow halt

This is not an unreasonable implementation, it is also a lot shorter already, you see we're still building more and more into the CPU, and again because this is something which could be done by a program adding this is a complex operation, so our CPU is a CISC architecture.

However, we still need to store the count of times through the loop in memory and swap it back and forth, so we clearly need a new register in our CPU another accumulator, but one for counting iterative processes... How does a real processor handle this?

Well, the processor contains a Complex of arithmetic operation modules, and many of them operate in different ways, if it were to implement the Multiply program in the CPU itself, storing the bytes of instructions to carry out this would be code within the processor itself.  Code inside a processor like this is often called "Microcode", however, what we're after is not microcode because we know its slower, what we want is to use the accumulator for the cumulative addition of the multiply, and then we want to count how many multiplies into another register...

This use of iterating (repeating) additions to achieve a multiplication is quite old, but we're all about building up knowledge... so on our processor we need a new counter... And that is exactly what I'm going to call it.


Now we can add some new op codes, lets add them to clear the accumulator, load the next value in memory into the accumulator and clear the counter...


With these our multiply is going to contain microcode to clear the counter, load the two parameters into registers 0 and 1 then perform a loop.  The loop we're going to perform is summing into the accumulator, taking it as a parameter itself, and we're going to simplify that the logic controlling the counter is included in the cpu for us... Yes we're going to cheat.


Our machine code program just then was:

// Load 0 from 20
1
100
// Load 1 from 21
2
101
// Multiply
14
// Store accumulator to 0
22
// Store 0 to 22
5
22
// Print from 22
6
22

As you saw, we got our answer 15... You try some other multiplications... And of course see what happens when we over flow... think about adding op codes to report to your program whether it has an overflow, how would we check?  Would we load overflow into a register and then compare it?  Should we Halt the whole processor?

No comments:

Post a Comment