Choosing ALU functions

[jbloggz]

Hi,
I've just finished reading chapter 2 of the book and watching the videos for unit 2 on coursera and have a couple of questions about the choice of functions for the ALU.

1. How were the 18 different 'functions of interest' chosen? Why were these 18 chosen and others not?
2. Is there a minimum function set that is still able to create a useful ALU?

I understand that more complicated functions can be implemented in software using the basic hardware functions, but there must be some minimum list of hardware functions? Is there some functions the an ALU MUST implement in order to function in a computer? Or is it theoretically possible to create an ALU which only performs a NAND operation and build every other function in software?

I guess what I'm trying to figure out is, if I were to create my own ALU, is there a way to figure out if I have implemented enough hardware functions for the ALU to be useful? When the 18 functions were chosen for the HACK ALU, how did the creators know that they would enough?

Thanks for any insight anyone can provide!!

EDIT: I just finished building the ALU and I am quite impressed with how it is able to calculate the various functions. I especially like the way that the 2's complement format is exploited so that we can use things like [ -x = not(x) + 1 ] to create some of those functions. However, I'm still interested in how we know that the 18 functions will be enough to build a general purpose computer. Are they all necessary, or are some of them just 'nice' to have so we don't need to create them in software?

[ivant]

Theoretically, you probably need only NAND (or NOR) in the ALU and can implement everything else in software. The problem is, that it would be very inconvenient to write that software and also extremely slow. Such computer would not be practical one, and doesn't seem very useful for theoretical purposes either.

if you're interested in the theoretical aspect of computability, I can advise you to take a look at Turing machines and at Lambda calculus. Both are fascinating subjects, but are outside of the scope of this course.

I think the authors tried to balance between an ALU with fewer functions, so it's easy to implement, and ALU with enough functions to be practical to implement the software stack in the second part of the book. I think they've done a great job with that, though I wish they've included bit-shifting instructions in the ALU as well as stack instructions in the CPU.

[jbloggz]

Thanks for the response. I too, was wondering why there was no bit shifting in the ALU. It seems like a fairly reasonable thing to implement in the hardware. Once I've finished the course, it might be a fun task to go back and add it (and possibly other instructions) in the ALU. You also mentioned there not being stack instructions in the CPU. Does this mean the HACK computer doesn't have a call stack, or cannot handle recursion? How difficult a task would it be adding this to the computer?

So if there isn't really a 'minimum' list of instructions for an ALU, is there perhaps a minimum list to build a 'practical' ALU? Is there a list of functions that most ALU's tend to implement? I imagine 'adding' is probably on that list, along with a few of the other ones in the HACK ALU.

My ultimate goal once I finish both courses is to go back to the start and actually physically build the computer (using perhaps only 7400 series TTL chips). I understand that it is much more practical to run this course using the hardware simulator, however it still feels like cheating a bit. I wonder if anyone has managed to do this (build a physical HACK computer) and would have any advice....

[cadet1620]

Although not directly related to your question, you might find this forum thread interesting too.
Is the method used to make the Hack ALU an exception or the rule

--Mark

[cadet1620]

jbloggz wrote

You also mentioned there not being stack instructions in the CPU. Does this mean the HACK computer doesn't have a call stack, or cannot handle recursion? How difficult a task would it be adding this to the computer?

The Hack computer can handle recursion.  You will learn how to implement a stack with software in chapters 7 and 8.

It would not be too hard to add push and pop instructions using a dedicated SP register. There will also need to be instructions to manage the SP register.

It would be much harder to add hardware call and return because these instructions generally require multiple memory access cycles.

--Mark

[jbloggz]

Thanks, that thread was very insightful. Are the 'push' and 'pop' instructions what "ivant" was referring to about the lack of stack instructions in the CPU?

I'm probably getting a bit ahead of myself with all these questions, since I've only just finished chapter 2, but this stuff really does fascinate me. I've been working as a software developer for the past 2 years after completing a PhD in Mathematics, however I've always been uncomfortable with my ignorance about how computers actually work. I'm glad I stumbled across this course, it seems to be exactly what I've been looking for.