Placeholder Image

字幕列表 影片播放

  • [MUSIC PLAYING - "JESU, JOY OF MAN'S DESIRING" BY JOHANN

  • SEBASTIAN BACH]

  • PROFESSOR: Well, up 'til now, I suppose, we've been learning

  • about a lot of techniques for organizing big programs,

  • symbolic manipulation a bit, some of the technology that

  • you use for establishing languages, one in terms of

  • another, which is used for organizing very large

  • programs. In fact, the nicest programs I know look more like

  • a pile of languages than like a decomposition of a problem

  • into parts.

  • Well, I suppose at this point, there are still, however, a

  • few mysteries about how this sort of stuff works.

  • And so what we'd like to do now is diverge from the plan

  • of telling you how to organize big programs, and rather tell

  • you something about the mechanisms by which these

  • things can be made to work.

  • The main reason for this is demystification, if you will,

  • that we have a lot of mysteries left, like exactly

  • how it is the case that a program is controlled, how a

  • computer knows what the next thing to do is, or

  • something like that.

  • And what I'd like to do now is make that clear to you, that

  • even if you've never played with a physical computer

  • before, the mechanism is really very simple, and that

  • you can understand it completely with no trouble.

  • So I'd like to start by imagining that we--

  • well, the way we're going to do this, by the way, is we're

  • going to take some very simple Lisp programs, very simple

  • Lisp programs, and transform them into hardware.

  • I'm not going to worry about some intermediate step of

  • going through some existing computer machine language and

  • then showing you how that computer works, because that's

  • not as illuminating.

  • So what I'm really going to show you is how a piece of

  • machinery can be built to do a job that you have written down

  • as a program.

  • That program is, in fact, a description of a machine.

  • We're going to start with a very simple program, proceed

  • to show you some simple mechanisms, proceed to a few

  • more complicated programs, and then later show you a not very

  • complicated program, how the evaluator transforms into a

  • piece of hardware.

  • And of course at that point, you have made the universal

  • transition and can execute any program imaginable with a

  • piece of well-defined hardware.

  • Well, let's start up now, give you a real concrete feeling

  • for this sort of thing.

  • Let's start with a very simple program.

  • Here's Euclid's algorithm.

  • It's actually a little bit more modern

  • than Euclid's algorithm.

  • Euclid's algorithm for computing the greatest common

  • divisor of two numbers was invented 350 BC, I think.

  • It's the oldest known algorithm.

  • But here we're going to talk about GCD of A and B, the

  • Greatest Common Divisor or two numbers, A and B. And the

  • algorithm is extremely simple.

  • If B is 0, then the result is going to be A. Otherwise, the

  • result is the GCD of B and the remainder when A is divided by

  • B.

  • So this we have here is a very simple iterative process.

  • This a simple recursive procedure, recursively defined

  • procedure, recursive definition, which yields an

  • iterative process.

  • And the way it works is that every step, it determines

  • whether B was zero.

  • And if B is 0, we got the answer in A. Otherwise, we

  • make another step where A is the old B, and B is the

  • remainder of the old A divided by the old B. Very simple.

  • Now this, I've already told you some of the mechanism by

  • just saying it that way.

  • I set it in time.

  • I said there are certain steps, and that, in fact, one

  • of the things you can see here is that one of the reasons why

  • this is iterative is nothing is needed of the last step to

  • get the answer.

  • All of the information that's needed to run this algorithm

  • is in A and B. It has two well-defined state variables.

  • So I'm going to define a machine for you that can

  • compute you GCDs.

  • Now let's see.

  • Every computer that's ever been made that's a

  • single-process computer, as opposed to a multiprocessor of

  • some sort, is made according to the same plan.

  • The plan is the computer has two parts, a part called the

  • datapaths, and a part called the controller.

  • The datapaths correspond to a calculator that you might

  • have. It contains certain registers that remember

  • things, and you've all used calculators.

  • It has some buttons on it and some lights.

  • And so by pushing the various buttons, you can cause

  • operations to happen inside there among the registers, and

  • some of the results to be displayed.

  • That's completely mechanical.

  • You could imagine that box has no intelligence in it.

  • Now it might be very impressive that it can produce

  • the sine of a number, but that at least is apparently

  • possibly mechanical.

  • At least, I could open that up in the same way I'm

  • about to open GCD.

  • So this may have a whole computer inside of it, but

  • that's not interesting.

  • Addition is certainly simple.

  • That can be done without any further mechanism.

  • Now also, if we were to look at the other half, the

  • controller, that's a part that's dumb, too.

  • It pushes the buttons.

  • It pushes them according to the sequence, which is written

  • down on a piece of paper, and observes the lights.

  • And every so often, it comes to a place in a sequence that

  • says, if light A is on, do this sequence.

  • Otherwise, do that sequence.

  • And thereby, there's no complexity there either.

  • Well, let's just draw that and see what we feel about that.

  • So for computing GCDs, what I want you to think about is

  • that there are these registers.

  • A register is a place where I store a number, in this case.

  • And this one's called a.

  • And then there's another one for storing b.

  • Now we have to see what things we can do with these

  • registers, and they're not entirely obvious what you can

  • do with them.

  • Well, we have to see what things we

  • need to do with them.

  • We're looking at the problem we're trying to solve.

  • One of the important things for designing a computer,

  • which I think most designers don't do, is you study the

  • problem you want to solve and then use what you learn from

  • studying the problem you want to solve to put in the

  • mechanisms needed to solve it in the computer you're

  • building, no more no less.

  • Now it may be that the problem you're trying to solve is

  • everybody's problem, in which case you have to build in a

  • universal interpreter of some language.

  • But you shouldn't put any more in than required to build the

  • universal interpreter of some language.

  • We'll worry about that in a second.

  • OK, going back to here, let's see.

  • What do we have to be able to do?

  • Well, somehow, we have to be able to get B into A. We have

  • to be able to get the old value of B into the value of

  • A. So we have to have some path by which stuff can flow,

  • whatever this information is, from b to a.

  • I'm going to draw that with by an arrow saying that it is

  • possible to move the contents of b into a, replacing the

  • value of a.

  • And there's a little button here which you push which

  • allows that to happen.

  • That's what the little x is here.

  • Now it's also the case that I have to be able to compute the

  • remainder of a and b.

  • Now that may be a complicated mess.

  • On the other hand, I'm going to make it a small box.

  • If we have to, we may open up that box and look inside and

  • see what it is.

  • So here, I'm going to have a little box, which I'm going to

  • draw this way, which we'll call the remainder.

  • And it's going to take in a.

  • That's going to take in b.

  • And it's going to put out something, the remainder of a

  • divided by b.

  • Another thing we have to see here is that we have to be

  • able to test whether b is equal to 0.

  • Well, that means somebody's got to be looking at--

  • a thing that's looking at the value of b.

  • I have a light bulb here which lights up if b equals 0.

  • That's its job.

  • And finally, I suppose, because of the fact that we

  • want the new value of a to be the old value of b, and

  • simultaneously the new value of b to be something I've done

  • with a, and if I plan to make my machine such that

  • everything happens one at a time, one motion at a time,

  • and I can't put two numbers in a register, then I have to

  • have another place to put one while I'm interchanging.

  • OK?

  • I can't interchange the two things in my hands, unless I

  • either put two in one hand and then pull it back the other

  • way, or unless I put one down, pick it up, and put the other

  • one, like that, unless I'm a juggler, which I'm not, as you

  • can see, in which case I have a

  • possibility of timing errors.

  • In fact, much of the type of computer design people do

  • involves timing errors, of some potential timing errors,

  • which I don't much like.

  • So for that reason, I have to have a place to put the second

  • one of them down.

  • So I have a place called t, which is a register just for

  • temporary, t, with a button on it.

  • And then I'll take the result of that, since I have to take

  • that and put into b, over here, we'll take the result of

  • that and go like this, and a button here.

  • So that's the datapaths of a GCD machine.

  • Now what's the controller?

  • Controller's a very simple thing, too.

  • The machine has a state.

  • The way I like to visualize that is that I've got a maze.

  • And the maze has a bunch of places

  • connected by directed arrows.

  • And what I have is a marble, which represents the state of

  • the controller.

  • The marble rolls around in the maze.

  • Of course, this analogy breaks down for energy reasons.

  • I sometimes have to pump the marble up to the top, because

  • it's going to otherwise be a perpetual motion machine.

  • But not worrying about that, this is

  • not a physical analogy.

  • This marble rolls around.

  • And every time it rolls around certain bumpers, like in a

  • pinball machine, it pushes one of these buttons.

  • And every so often, it comes to a place, which is a

  • division, where it has to make a choice.

  • And there's a flap, which is controlled by this.

  • So that's a really mechanical way of thinking about it.

  • Of course, controllers these days, are not built that way

  • in real computers.

  • They're built with a little bit of

  • ROM and a state register.

  • But there was a time, like the DEC PDP-6, where that's how

  • you built the controller of a machine.

  • There was a bit that ran around the delay line, and it

  • triggered things as it went by.

  • And it would come back to the beginning and

  • get fed round again.

  • And of course, there were all sorts of great bugs you could

  • have like two bits going around, two marbles.

  • And then the machine has lost its marbles.

  • That happens, too.

  • Oh, well.

  • So anyway, for this machine, what I have

  • to do is the following.

  • I'm going to start my maze here.

  • And the first thing I've got to do, in a notation which

  • many of you are familiar with, is b equal to zero, a test.

  • And there's a possibility, either yes, in

  • which case I'm done.

  • Otherwise, if no, then I'm going have to

  • roll over some bumpers.

  • I'm going to do it in the following order.

  • I want to do this interchange game.

  • Now first, since I need both a and b, but then the first--

  • and this is not necessary--

  • I want to collect this.

  • This is the thing that's going to go into b.

  • So I'm going to say, take this, which depends upon both

  • a and b, and put the remainder into here.

  • So I'm going to push this button first. Then, I'm going

  • to transfer b to a, push that button, and then I transfer

  • the temporary into b, push that button.

  • So a very sequential machine, it's very inefficient.

  • But that's fine right now.

  • We're going to name the buttons, t gets remainder.

  • a gets b.