Now we're going to use those same basic ideas that we used for the program counter to put together an entire computer processor. So again, just remember that, just as with your actual computer if you to pry it open, we're thinking of the CPU as just a circuit inside the TOY-8 machine. And we're not going to worry about the interface to the outside world at all. Well, I guess, on off, we gotta have power in all our power docks. And run, we assume that when a programmer presses the run button, then there's a wire that comes into the circuit that goes up. But in terms of getting stuff loaded into the memory through the switches and lights, we'll leave that stuff out. It's an easy addition, but maybe the memory gets loaded with lasers or some other way. And actually, in modern computers, actually, there's lots of different ways to load the memory. So what we're concerned with is that that the machine's got some state that's got the program in it say what happens when the wrong button is pressed. Okay, so again, let's review our components. We have our ALU, our Memory, our Register, our PC. Our instruction register, our Control, and the Clock, and we'll look at the connections on the next slide. We already talked about these, but we're also going to need bus muxes for the register. because there's, well, three things that connect to the register and for the memory address, because there's two things that connect to the memory address. Those are the basic components. So the next thing we do is have to look at the bus connections. How exactly do we have to connect these components together? And that's dependent on the instructions that we want to implement. So for all instructions, we have to get the fetch. So that is, what do we have to do in a fetch? We have to get a word out of the memory. Get a word out of the memory, its address is in the PC. So we have to connect the PC to the memory address. And then, to get the word out of the memory, it's the output of the memory, it's gotta go into the instruction register. So in order to do a fetch of an instruction, we need these bus connections. Address going from the PC into the memory address. And the output of the memory going into the instruction registry. Halt instruction, no information. That's the control line we'll talk about on the next slide. What about arithmetic constructions? Well, arithmetic constructions, we have to get a word out of the memory. What word do we get out of the memory? Its address is given in the address bits of the instruction register. So we take the four address bits out of the instruction register, and those have to connect up to the memory. That's a second connection to the memory, that's what goes into the address mux. Two connections to the memory, from the PC and from the four bits of the instruction register. And we have to raise a line to select between them. So that's getting the address from the instruction register to the memory, but we also have to get the word out of the memory into the ALU. So add an extra connection over on the left there. Taking the output of the memory into the ALU as well as to the IR. Again, that's an output connecting to two components. So we can just do that with a T connection. So then, we also need our second argument is from the register into the ALU. So this is all just to make an add or xor or int happen. So now we've connected up our memory word and our register contents to the ALU. And the way to get it, through the address. And then we have to take the result and that has to go into the register, eventually. But since there's a lot of things going to the register, we just connect it to R mux. And again, we've got multiple connections to the R mux. So for example, load address, we have to take the address bits from the instruction register and bring them around over to the R mux as a candidate for going into the register. And then the output of that R mux goes into the register. And again, we have multiple connections to R, that's why we have the mux. So load instruction, we've already used. We have to get the instruction register address connected to the memory. And then the word from the memory has to go into the register. So a new little tab appeared at the left connecting the memory output at the bottom into the R mux, that's the third connection to the register. And finally, for store, again, we already have the connection from the instruction register address to the memory address. But now what do we have to do in a store? We have to get the contents of the register into the memory. So now the output of the register goes straight up and then over to the left into the ALU. We just need to connect over to the right to also go into the memory. So that's the data path for the connection for the store instruction. And then the last one is branch if zero. Branch if zero, in order to do that, we're going to have to get the address from the instruction register into the PC. That's the input to the PC that we talked about when we did the PC. So that's all our bus connections for our entire TOY-8 computer. Different instructions call for different connections, and when we have multiple inputs to a component, we have to include a mux. And just by systematically considering each of these, we can see what we need. That's the first part of the job. Second part of the job is the control wires. Well, we've already talked about control wires for each one of these components. This is by component, so we just need to enumerate them. For the clock, when we press RUN, it goes on. And when HALT happens, it goes off. So that's control wire that go into the clock component. And most of these control wires come out of the control circuit, that we'll talk about next. So what goes into the control circuit is the signals raised by the clock. That's our FETCH, FETCH WRITE, EXECUTE, and EXECUTE WRITE. So our clock produces those signals. And control, as we'll see in the next slide, is a combinational circuit that uses those signals to provide control wire sequences for all the other control wire in the circuit. So for example, the ALU, there's ADD, XOR and AND. Those are the ones that select which should be computed up which should go to the output bus. For each of the muxes like the R MUX, there's the three possibilities. Do we want to select that input that is connected to the ALU, the memory or the instruction register. Then there's the WRITE for the instruction register when it's time to write it. That's the WRITE pulse and for register and another one for the instruction register. The memory's got its WRITE pulse. And then the PC has, are we going to INCREMENT or LOAD? Those are selections for the internal mux. And then the PC WRITE signal. And then the last two are the selection lines for the address mux Those are all the control wires for the TOY-8 CPU. So those are the wires that we have to layout. And the last thing we have to talk about is control. And that's a circuit that does the control wire sequencing. We get the behavior we want by lighting up these control wires in particular sequences. So the inputs for control are the four wires from the clock, and those come in at the top. We also need the opcode from the instruction register because what we do depends on which instruction we're executing. We also need the contents of R, and that's for the branch on zero. And follow those are zero, and the opcode is seven, we're going to do a different thing, I'm sorry, is E, we're going to do a different thing, then if not, that's branch on zero. And the outputs of this control circuit are all the 15 control wires that we just enumerated for all the CPU components. The important thing to remember about control is that it's just a simple combinational circuit. If we remove the cover, we have a combinational circuit that is going to do the job of deciding which control wires to light up, depending on what the opcode is. And so we'll just make a table for all the things that we want to have happen, and implement the conditions expressed in that table with a combinational circuit. The key feature of this circuit in the middle is a couple of demultiplexers that are based on the opcode. So there's three opcode bits, and these demultiplexers have eight outputs, one going left and one going right. The signal, the demultiplexer takes three bits and it takes a signal, and then it produces on the addressed output of the value of that signal. So this has the effect of the one on the left, it's tied in with FETCH. Sorry, the one on the left is tied in with EXECUTE, and the one on the right is tied in with EXECUTE WRITE. So when EXECUTE comes high, it will light up one of those eight outputs on the left. And when EXECUTE WRITE becomes high, one of the eight outputs on the right will be lit up according to the instruction. So only one of those lines is on. But let's look at the tables now on the left. For all instructions, when FETCH becomes high, we need to raise the control line that selects the input to the memory address should come from the PC. So that's the ADDRESS MUX PC line. And you can see that FETCH, which is labeled left at the top, goes all the way through the circuit and comes out with that control line on. And also, we always increment the PC, except in the case that branch on zero if the register's zero. And there's a gate in there that takes all the inputs from the register, and takes whether it's the branch instruction and lights that up. And then for FETCH WRITE, we just want to write the instruction register. So FETCH WRITE goes right through the whole circuit and does an IR WRITE signal down at the bottom. And EXECUTE WRITE always writes the PC. So over on the right, we light up the PC. And then for each instruction there's logic, like for example, the arithmetic instructions. Add instruction is opcode one, so the second gate down, and the multiplexer is the only one that turns one. So it turns on ALU ADD. And then it'll also need to select the ALU line of the register MUX. So all of those instructions go down into an OR GATE that lights up that line and so forth. You can check every one, for every one instructions which control lines it lights up. And it's exactly the ones that we need in order to get the state change that the instruction specifies. Control turns the clock sequence into a sequence of control wires. Those control wires cause changes in the memory module, changes in states that really implement what the instructions want to do. You can study those in the book or in the books that are around this slide. So let's take a look at how our sample program which loads a word from memory, adds to it another word from memory, stores the result in memory. We'll see how that's implemented through a sequence of control signals. Again, we assume that the program is loaded in the memory somehow. The first instruction, address of the first instruction one is in the PC, and we press the run button. And we're going to look at the sequence of control signals. So the first thing that happens is FETCH signal comes out of the clock. The clock is just going to repeatedly do FETCH, FETCH WRITE, EXECUTE, EXECUTE WRITE, as we described. And FETCH through control is connected to the PC selection line for the ADDRESS MUX. That means that we're going to want to get a word out of memory for FETCH, and what word is it is the word whose address is in the PC, the first instruction, the one at address one, memory location one. So now when FETCH WRITE comes up, control sets that to IR WRITE, that's what we want to do every time FETCH WRITE comes up because we want to change the value in the instruction register to be the instruction to be executed. Well, how exactly does that happen? Well, the instruction register has only one input, that input is the memory output. So what word of memory is on those memory output lines? Well, it's the one that's addressed, selected in the ADDRESS MUX, and that one is selecting the value in the PC. So those output lines contain the contents of memory location one, which is A5. And when we give the FETCH WRITE pulse, that value gets stored in the instruction register. That's simple as that. That's what happens for every instruction. FETCH sets the address MUX PC line. FETCH WRITE sets the IR WRITE pulse, which causes the word from the memory to be loaded into the instruction register. Okay, so now that's a load instruction. So the next thing that happens is EXECUTE, which through control, sets the appropriate line for the load instruction. So it has to happen for the load instruction. Well, first thing is PC increment. A PC increment happens for every instruction, except maybe branch on zero, so we're going to setup so that when the WRITE signal comes the PC's going to increment. So that we do that by selecting that PC increment line in the PC. Then what else has to happen for a load instruction? Well, we're going to want to get a word out of memory and put it into the register. So what word do we want to get out of memory? Well, the one whose address bits are in the instruction register. So that means we set the selection line for the memory's address MUX to choose the address bits of the instruction register. And then the other thing we want is we want that word to go into the register, but that has to happen through the MUX. The memory output is connected to the register MUX but we have to do the selection line which selects that output to be the one that's loaded into the register. So now, when EXECUTE WRITE happens with all these control lines on, two things happen. First, the PC gets incremented PC WRITE just enables the value that is out of the incrementer to get loaded into the PC. And the second thing that happens is since the address MUX is set to use the address from the instruction register, that's memory word five. Then the contents of memory word five, which is 05, gets loaded into the register, because that's the input that's chosen by the register MUX. So that's our first instruction executed through this sequence of control signals. Now the same thing is going to happen. We're going to load our next instruction which is the ADD instruction for memory location six. So now that instruction is in the instruction register. So now when the execute signal comes from the clock, we always go fetch, FETCH WRITE, EXECUTE, EXECUTE WRITE. So when the execute signal comes we want to set up for the ADD. So how do we set up for the ADD instruction? Again, we want to increment the PC for an ADD instruction. Then we want to select the result of the adder from the ALU so the ALU ADD is selected. And now we want the result to go into the register. But now that has to go through the MUX, the ALUs connected to the register, but we have to light up the ALU selection line for that MUX. So the result computed by the ALU will go into the register. So know when we click execute write, then I think about what's going to happen. Execute write is going to enable writing the register. It's going to enable writing the PC. So writing the register, because of the way the controls line are set up is going to add the word at the address memory location to the word in the register. And it's going to put the result back into the register on that right pole and the PC WRITE is going to implement the PC. Now, again, we'll load up the next instruction which is a store instruction, it's the C7 instruction. So, a store instruction, it's again, it's going to increment the PC. And store instruction, we want to set the, again memory instruction where they're referred too, it's address is given in the instruction register. That's number 7, and then what happens at EXECUTE WRITE for the store instruction is a memory write signal So what value gets written into the memory, well let's look at the connections that we have set up. So first of all the address of the word that's affected is selected through the address MUX to be the address bits of the instruction register, which is 7. So it's word 7 that's affected. And what value gets put in there? Well the only input to the memory comes in at the top. And where does it come from? Well, you see it comes from the register. So the value that's in the register gets stored in the memory. And again, the PC gets incremented. So, that's our third instruction executed and now the PC is at 4 and so again we fetch our next instruction and that's the halt. And then what happens in execute is that that lights up the halt signal which stops the clock. So that's that sequence of controls signals that executes that program and gets the two numbers executed. And you can see that any program is going to result in a sequence of control signals like that that is going to affect the change of state that's needed. So that is how your computer works. Now we've not covered a lot of details, but really this basic idea really is at the root of implementing a computing circuit. Here's a complete TOY-8 CPU. And if you take the covers off, and look carefully, you can see every control signal, every bus, every memory bit in this circuit. Our whole design goal for the last four lectures was to get to this point where you could really see how a computer circuit works. Now here's a close up of a real microprocessor, and an expert could identify the bits in this image. I just want to make the point that there's really no difference between our drawing and this drawing other than scale. So we have maybe a 1 bit per square centimeter and this thing has maybe 25 billion bits per square centimeter but in terms of the conceptual design, they're not different. So how does your computer work? All the details are very interesting. But somebody might ask, well you took a course in computer science. How does the computer work? And it's worthwhile to try to think of the basic ideas that we've covered. So there's a circuit known as a CPU that's built of very simple elements which is that are connected by wires. And what it does is, it processes information that's encoded in binary, even including its own instructions. That's the fundametal concept of the Vine Norman machine. Circuits that have feedback, we use to implement memories, tiny circuits. That tiny elements make big circuits. And what instructions do is move information among the memories. Specify operations or implement mathematical functions like I had named that are based on Boolean logic. And it all works because of clock pulses, regular clock pulses that activate sequences of control signals that cause the state changes that implement the machine instructions. Almost everything else is implemented as layers of software. Everything that you're familiar with from your applications to your display and so forth, it's implemented as software layer of abstraction. Each layer that adds a vast amount of additional power and scope, but the basic concept and the basic machine is relatively simple. It's just that it does it at an amazing size, scope, and speed. So, that's the last slide of content and I just want to revisit what we promised at the beginning. So this course is supposed to be a brief introduction to computer science. In our goals to, first of all to empower you to exploit available technology and we covered data structures and link structures and algorithm design. A lot of basic information that are going to help you solve applications problems. Then we want to build awareness of intellectual underpinnings and the idea of universality, and computability, and intractability. Absolutely give you some idea of the limitations and opportunities of what we can compute. And then we wanted to demystify computer systems. And that's what our TOY machine and our TOY circuit in this lecture were all about. So I hope we can check that one off for many of you as well. There's much more information available on the web and in our book. And I also want to take this opportunity to thank Kevin Wayne who you haven't seen on screen but who has worked with me for 15 years on developing these materials. Kevin and I have learned quite a lot during the 15 years we've been working on this and we hope that many of you have learned a lot as well. And there's much more to learn available in the book and on the book site. And if you're interested in more, consider taking a algorithms and we'll see you there.
