Instructions

Loading...

En provenance du cours de Princeton University

Computer Science: Algorithms, Theory, and Machines

100 notes

Princeton University

Computer Science: Algorithms, Theory, and Machines

100 notes

This course introduces the broader discipline of computer science to people having basic familiarity with Java programming. It covers the second half of our book Computer Science: An Interdisciplinary Approach (the first half is covered in our Coursera course Computer Science: Programming with a Purpose, to be released in the fall of 2018). Our intent is to demystify computation and to build awareness about the substantial intellectual underpinnings and rich history of the field of computer science. First, we introduce classic algorithms along with scientific techniques for evaluating performance, in the context of modern applications. Next, we introduce classic theoretical models that allow us to address fundamental questions about computation, such as computability, universality, and intractability. We conclude with machine architecture (including machine-language programming and its relationship to coding in Java) and logic design (including a full CPU design built from the ground up). The course emphasizes the relationships between applications programming, the theory of computation, real computers, and the field's history and evolution, including the nature of the contributions of Boole, Shannon, Turing, von Neumann, and others. All the features of this course are available for free. No certificate will be offered upon completion.

À partir de la leçon

A COMPUTING MACHINE

Every programmer needs understand the basic characteristics of the underlying computer processor being used. Fortunately, the fundamental design of computer processors has changed little since the 1960s. In this lecture, we provide insights into how your Java code actually gets its job done by introducing an imaginary computer that is similar to both the minicomputers of the 1960s and the microprocessor chips found in today's laptops and mobile devices.

Data Types16:31

Instructions10:28

Operating the machine8:23

Machine language programming19:52

Rencontrer les enseignants

Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Computer Science
Kevin Wayne
Phillip Y. Goldman '86 Senior Lecturer
Computer Science

So now let's look at TOY's instructions and actually a TOY program.

So the fundamental point that we want to know right from

the beginning is that any 16-bit value defines a TOY instruction.

If you have 16-bits,

that's a TOY instruction,

and TOY will do something with that 16-bits.

So we have to describe what every 16-bit value means.

The first hex digit.

So this four hex digit is 16-bits.

The first one says which instruction and each instruction changes

the machine state somehow and some well-defined way

you can figure out exactly how it changes the machine state.

So, we've talked about the data type operations.

So that's add, subtract,

bitwise and, bitwise xor,

shift left, and shift right.

Those are opcodes one through six.

They implement data type operations,

and they change the values of a register.

So, we'll see precisely how,

but that's the way they change the machine state.

Then there's five instructions that are

devoted to moving data between registers and memory.

And those might change a register,

or they might change a memory cell.

Either bringing some from memory into a register or the other way.

So that's opcodes seven,

eight, nine, A, and B.

And again, we'll talk about precisely how they

differ in the ways that they change the state.

And then, the remaining five instructions are about flow of

control which instruction gets executed next.

These are the ones that are used to implement

Java abstractions like conditionals, loops, and functions.

And those are opcodes zero, C, D, E,

and F. What they change is the program counter.

And now, we'll look at precisely how each of the instructions do it.

Now, there's two different instruction formats that depends on opcode.

The first type is called RR,

and that's where the first digits,

the opcode, and then the three remaining digits specify registers.

Remember there's 16 registers,

so we can specify a register with the hex digit.

And for all the arithmetic instructions and a couple of other ones,

those three digits specify registers.

So when we say an added structure,

when the opcode is one,

then the next three digits represent,

the first one is the register that gets the result,

and the next two are the registers that contain the operands.

And that's true for all the ones that define data type operations and a few others.

And then, the other type of instructions are the ones that refer to memory.

In those, the first digit again is the opcode.

Next digit is a register which is specified registers suppose to be operated on.

And then, the next two digits are memory address,

so they refer to the memory.

Remember with two hex digits,

we can refer to one of the 255 memory locations.

So those two different types,

it's the opcode that determines how the instructions going to be interpreted.

So, for example, if we say one C A B,

that's an add instruction,

and it means add to R [A] and R [B] ,

the last two digits,

and put the results in R [C].

So now you know how to decode any 16-bit value that begins with 0001.

Any value like that is specifying

an add instruction is just different registers might be involved.

Or if we say eight, A, 15.

Remember this is 15 hex,

so it's actually 21.

That eight means load.

Then A means register A.

And then, the next two hex digits specify the memory location.

And it says load into register A the data that's in memory location 15.

And all the other instructions are defined similarly.

And we won't go through the details of all of them in lecture,

but there's a little table on the book side in the text,

and we'll put one up later that describes all the instructions.

And that's it, that's a description of what TOY does,

and with that, we're ready to start writing programs.

So let's look at a simple program.

The simplest possible program.

This is, say, "Hello world" for TOY.

So what we're going to do is add two integers.

And so, this is same memory locations.

10 through 16 have these values.

They're just four hex digits or 16-bit values,

and that's what a TOY program is.

So what this program does is load some operands from memory into the registers,

then uses the add instruction that gets you to add the contents,

and then puts the result back in memory.

So let's look at how this instruction does its thing.

So the most important thing,

really what characterizes it being a program,

is that the PC has the address of the first instruction.

So the PC's at 10 in the memory has this contents.

Here's what happens when the machine starts running.

So the first instruction says load into register A.

The data that's in memory 15.

And down at the bottom,

we have a trace of what's going on in the registers.

So what happens with that is,

if you look at memory 15 has 0008,

so that value is going to get loaded into register A.

And then, remember, all the machine does is increment the PC.

It actually does it before executing the instruction,

but that would be confusing for the simple examples,

so we do it after we execute the instruction.

And now that points to the next instruction.

And that next instruction says,

"Load into a register B the data that's in memory location 16."

Memory location 16 is got 0005.

So that's what gets into the register B.

Again, go to the next instruction.

Next instruction says, "Add register A and B and

put the result into register C." And right away,

remember, we're thinking hex all the time,

what's eight plus five.

You might be thinking it's 13,

but it's actually D. And again,

it won't take too long to be thinking in hex as we

go through examples in the book and even in these couple of lectures.

Okay. So now we have that result in register C,

but the registers really are internal, and as you see,

when we're programming we only have really access to what's in the memory.

So what we need to do is store that result that

we've computed in the register into memory.

And so that's the next instruction,

"Store what's in register C into memory location 17."

And so that's our D goes into location 17.

And then, PC increments again,

and the next instruction says, "Halt,

that's the end of the program, stop."

So that's a full example of a TOY program in operation illustrating load instructions,

arithmetic instructions, and store instruction.

And you can see even with just studying a few more instructions,

there is a lot of programs that you know how to write,

because you're used to learning a new programming regime.

And this one's a really simple one that's well specified,

and we'll do another much more complicated program later in this lecture.

So, the question comes out is,

"How do you know that a word is actually an instruction?"

And the answer to that is,

if the PC is got its address, it's an instruction.

Now, if we run the same program with different data,

we can further illustrate that point.

So again load into register A with severance in memory 15.

In this case, it's a big number minus 29,930,

which in twos complement 16-bit is actually 8 B 1 6.

Now we go to the instruction at number 11.

And that says, "Load into R [B] whatever's in memory location 16."

And memory location 16 has 1 C A B.

That's the number 7,339.

So that's what's in our registers.

And now, we're going to add those two numbers,

and we get the result A 7 C 1,

which happens to be minus 22,591 in decimal.

So just changing the data we can use the same program to compute result.

And, in fact, that's what we often do with computers.

We write a program,

and give it a bunch of different data values.

And absolutely, that's what people did with early computers.

They wrote programs provided various data values and computed the answers.

And again, we store our result in memory location 17, and halt.

So, if you want to know the question, well,

how can you tell whether a word is data?

Well, if you add it to another word, it's a data.

It might be the same bit values,

we have the same bit values in location 12 and location 16 in this situation,

but the first one is an instruction because the PC pointed to it,

and the second one is data because it got added to another number.

That's a fundamental concept that we're going to be coming back

to again and again in the next few lectures.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play