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.
Bits, registers, and memory
Loading...
From the course by Princeton University
Computer Science: Algorithms, Theory, and Machines
82 ratings
From the lesson
CENTRAL PROCESSING UNIT
In this lecture, we provide the last part of our answer to the question "How does a computer work?" by developing a complete circuit for a computer processor, where every switch and wire is visible. While vastly different in scale, this circuit, from a design point of view, has many of the same characteristics as the circuits found in your computer and your phone.
Meet the Instructors
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Kevin WaynePhillip Y. Goldman '86 Senior Lecturer
Computer Science
Combinational circuits that we considered in the last lecture,
just compute and just do their thing.
It provide values on wires as inputs and the computed values available in the outputs.
What we want to look at now is
a very important idea that we want to have circuits that remember things.
Unfortunately, as with the switch that we used as the basis for combinational circuits,
there's a very tiny component that we can
use as the basis for all of the circuits with memory.
That's what we're going to consider next.
So, a sequential circuit is a circuit that has feedback,
that has loops in it.
Now, just as with computer programs,
when you add loops to a circuit,
you're introducing a whole new level of complexity in the behavior of the circuit.
One would be extremely careful about how we introduce feedback.
And the reason that we use sequential circuits is the idea of memory.
It really makes the difference between a calculator and a computer,
but fortunately we can get by with
a pretty small set of basic abstractions just as with combinational circuits.
Again, we have on and off,
we have wires that propagate on and off values,
we have switches that we can control propagation through the wires,
we're automatically controlling the switches.
And now we're going to add something new which is called a flip flop and that's
a very simple circuit with feedback that remembers a value.
That's what we're going to talk about next.
So the thing is,
if you have loops and circuits,
then the behavior is going to depend on the sequence of switch operations,
and so we need some very tight control on this.
So here's just the simplest possible example.
If you have two switches that are each blocked by the other,
so these are two switches connected in power dots and they each block the other one.
Now we're going to pay attention to
the value on the wire that comes out of this little unit,
but the thing about it is that the state is determined by whichever one switches first.
So for example, if the one on the bottom is the first to switch
and therefore block the power dot on the bottom from going to the output,
then the state is going to be zero,
that output line will be off.
But if the one at the top switches first,
then the power dot on the left is connected to the output and the output is the one.
And the thing about this is,
depending on which one switches first,
if it gets in one of these two states,
it's going to stay in that state.
So once it's set, the state never changes,
but the thing is it's dependent on this kind of
random event of which is going to switch first.
One of them will switch first even if it's only by a tiny amount,
and as soon as it does,
then the circuit enters the stable state.
So that's our basic building block for memory circuits.
This is a tiny circuit,
the tiniest that we can imagine that remembers something.
It remembers which one switched first.
What we're going to do is add some controls so we control which one switches first.
But once we've done that,
we're going to take advantage of the fact that the circuit remembers.
Now, this is the main feedback,
like 99.99 percent of the feedback on our circuits are a little tight,
things like this, little memory bits,
and the reason is that if you have bigger feedback loops,
you can get unpredictable behavior.
So here's the same thing extended to three switches that block one another.
And again, the state is determined by whichever one switches first,
but it's not stable.
These switches keep blocking each other and switching around and goes in the cycle.
That's called a buzzer,
and actually, if you build your switches with the relays,
the physical electromagnets we talked about last time,
it actually makes a buzzing sound and
actually old doorbells or old-sounding buzzer is exactly that.
It's just a relay turning on and off through and that stable cycle like this.
So because of that kind of behavior,
we want to stay away from long feedback loops or at
least make sure we have very tight control over long feedback loops.
The main way is to put all our feedback just in the two-switch feedback.
So there we go.
That's the idea of memory and now what we want to do is
control when the switch switches and that's what a flip-flop is.
We'll use the old historical terms.
There are many different types of flip-flops initially,
but we're going to use what's called an SR flip-flop and the idea is to add
control lines to the switches to set the state,
basically determine which switch switches first.
So the R line which is called reset sets the state to zero and the S line which is called
set sets the state to the one and the output is called Q and that's always available.
So this is what it looks like.
So you can see if the R line is on,
then it's going to block the switch at the bottom from
switching and then the state is going to be zero.
That's just as if that switch switched first.
In contrast, the S line,
and we'll look at more detail,
is going to set it so the other one as if the other one
switched first and it'll always remember that.
If you look at these as components,
it's two NOR gates that are interconnected.
The classic notation is that it is called a cross-coupled NOR gates.
So two simple NOR gates that are cross-coupled, that's a flip-flop.
So just look at an example,
so if R is up,
so in this example R is set to one and S is zero,
and you can see R blocks the power dot at the left and that means the other switch,
the other power dot at the right is on,
and now even when we turn R off,
then the power at the left is going to be blocked.
So it's as if the switch at the bottom switched first and we
kind of forced it by putting R on and that means the output is zero.
On the other hand, if we set S to one,
then it's as if the switch at the top
has switched which connects the power dot at the left to
the output puts the thing in state one
and then even when S goes off and it stays in that state.
We never put both R and S on at the same time,
so we don't have to worry about that then we're talking
about which one goes off first and they have the same kind of problem.
So with the R and S line,
we can control what value goes in to
the feedback loop and that's the essence of a circuit with memory.
Now there are some physical considerations
that come into play here depending on the switch technology.
So if the switches are really slow versus the delay,
but we're not going to worry about those.
We're going to assume that we've got
a difference in that switching time in the delay through the wires.
It's sufficient that we don't have those kinds of problems.
In real life, you might have to worry about timing a bit.
So I don't want to minimize those,
but let's just abstract them away because it does depend on the technology.
So we're going to assume when R goes one,
then we set it to zero.
When S goes one,
we set it to one and that happens pretty quickly compared to everything else.
So what we're going to do now
is implement a memory bit that even give us more precise control.
What we want to do is provide data value on an input wire
instead of fooling with too much with the S and R controls directly and
we're going to have a control wire for every memory bit that
if that's the one that enables the actual change in the flip-flop value
and then the flip-flop value is always available as
output,and you know this is the reason that we
don't need to worry so much about timing as we have
these extra controls to make sure that things happen in the way that we want.
We'll talk a little bit about that a little later,
but it's just one piece of operation that makes our circuits reliable.
It's possible to make our circuits reliable and lots of technologies.
So if we want to set the value of our flip-flop to one,
then we put one on the input and then we turn this write control wire on.
Usually, we think of turning this on just briefly,
just enough to get the flip-flop to
flip for a few gates and then we turn it off right away.
So now you can see with that write on and the input one,
we end those two signals and then feed that to S,
so S is going to be one if and only if both R input is one and write is on,
and when S is one,
then the flip-flop gets the value one,
and at the same time the other end gate on the left has the second input is the opposite.
It is going to block and so R will be
zero always when the input is one and then when write goes off,
then the flip-flop has its new value.
So all we assume is that a quick write pulse gets
the flip-flop to change and that time it's pretty
small by comparison with everything else in the circuit,
and similarly, with zero we do the opposite.
Zero signal in is going to wind up with R being one and S being zero always,
and when the write pulse comes on which sets the flip-flop value to zero,
and then even when right goes away, it stays zero.
That's our basic unit of memory,
memory bit that operates in this way.
You give it an input,
give it a write pulse,
remembers that input value until the next time it gets it
write pulse and the output value is always available.
Our computers and our computer circuits are filled, filled,
filled with memory bits as most of it is these.
So it's important to understand how they work.
Again we're exercising very tight control over what
happens in the feedback loop and that's how we get our circuits to be reliable.
So here's an application of memory bit.
It's a circuit that's got just one memory bit in it
and we're going to use it to implement the clock that drives our computer.
So we'll have another assumption about the physical world and that is that we can
get a regular on-off pulse from the physical world somewhere.
Even Von Neumann needed this and imagined it in the terms of
oscillations of some physical material
and we make two assumptions about our clock signal.
First is that the duration of
the time when it's one is just enough to trigger a flip-flop,
and number two, and we'll talk about this a little more later,
is that the duration between pulses is pretty long.
There might be lots of flip-flops that have to stabilize and we assume that that
duration between pulses is long enough for the longest chain of flip-flops to stabilize.
Analysis of this is sometimes difficult and actually in
real computers what they do is make
that interval very long to make sure the computer
works and then they make it shorter and shorter until it stops working,
make it a little bit longer and then sell it to you.
That's absolutely what they do, build computers nowadays.
Okay, so what we're going to do now is attach that clock signal to a memory bit and
that it's going to give us the signals that we need
to get the fetch to execute that we use to drive the computer.
So you can think of this physical clock as
just the minute hand spinning
around and every time it hits that little triangle at the left,
it makes a pulse, and again,
there's lots of ways we could do that and the clock itself
in the physical world has a run control wire that starts the clock.
So when you press the run button on the front of the computer that turns on the clock,
it starts spinning around and makes the clock pulses.
There's also a halt control wire that stops it.
So now what we do is,
so we get the run to start, a halt to stop,
what we do is we take the output of the memory bit,
what it remembers and we take the output and the negation of that output.
So right at the bottom, we put a not gate.
So we have two signals that we give out,
one called fetch and one called execute,
and they are always the opposite of one another.
So our computer, when it's running,
it either got fetch high or it's got execute high and the other one is zero always.
They are absolutely the negation of one another and then
we take that signal and we feed it back in to the input to
the flip-flop and so what's going to happen is since
the write enable line is fed by the clock pulse,
every time the clock ticks,
the flip-flop is going to change its value.
It remembers what its value was the last time
the clock ticked and it changes to the new value.
That one bit is what we need to
implement the sequence of fetch and execute that control the CPU.
That's a very useful one bit circuit, one memory bit.
It's a circuit with that one little loop of feedback. It's quite useful.
We actually use a more complicated one that we want to add in the write pulses.
So I might as well talk about that one now.
It's just a slightly more complicated version of this clock.
What we want is we want to have a fetch signal and then fetch write pulse.
So the fetch part of the computation,
things happen but nothing gets written until the write pulse happens and that
write pulse is a short one that just gets flip-flops to change and same with execute,
and to get that, we just end our two signals to the fetch-execute clock.
So the fetch write pulse is just fetch and
clock and the execute write pulse is just execute and clock.
And that's what we're going to use to implement our fetch/execute cycles,
the ones that these signals are going to turn on
control wires that change the state of all our components.
And this diagram looks complicated,
but it's really just pointing out that there's going to
be four distinct times in this clock cycle,
which repeats endlessly where interesting things happen.
So fetch comes high,
and then some control lines come along.
And then fetch right happens,
and that causes certain flip flops to change.
And execute comes high,
and certain control lines go on,
and then execute right happens and certain flip flops change.
And that cycle is going to continue over and over and over again.
And that's what's going to drive
the changes in the circuit that implement our instructions.
And all of this is made possible by a single bit connected to a simple clock.
But of course most of our memory circuits are more complicated.
So, let's look at registers.
So, a register is a bunch of bits.
So, here's a 4-bit register.
And again, our convention is to take inputs at the top,
and provide outputs at the bottom,
and to have blue control lines in the middle.
So we have an input bus in this example.
This input bus is representing the 4-bit values zero one zero one, or maybe five.
And then those are available on the input bus,
but they're just sitting there,
they're not being used,
because the right control is off.
So we might have different values on the output bus,
those are the current values of what's in the memory bit.
In this case one one zero zero,
which maybe represents 12.
And so, if we give it a right pulse,
then what's supposed to happen is,
the values and the input bus go into the memory bit,
and are available on the output bus.
So, in this case right is off,
so now when we turn right on,
then we get those values put into the memory bits,
and available on the output bus.
And the implementation is quite simple,
it's just a sequence of memory bits,
just connected to the buses.
And the right pulse controls all of them.
And in TOY-8, this is
precisely what holds the address for the PC or for a bit register like this.
We need an 8-bit register to hold the current instruction.
It's the same thing just with eight bits.
And our actual processor register also is an 8-bit register that's exactly like this.
So, sequence of memory bits connected with buses and the right pulse,
that's a register and that's three of the main components of our CPU circuit.
And then we can extend the same idea to get a memory bank.
So, now we've got two to the n words.
In the case of TOY-8 little n is three 8-bit words.
In this example that will show right here,
we're going to have a four word memory that are
each six bits just so you can see all the gates.
And again to emphasize that our design is
parametrized just by really the number of bits in a word,
in the number of words or the number of bits in the address.
So, this is the exact same design,
it's going to work even when the end is 30 or in which case they'd be a billion words.
In this case when n is two and this case this is four words.
So we have to give in bits of address input that's over the left,
and then however many bits per word,
we have an input bus,
and then the value of some word,
the word whose address we give,
is the one that's available on the output bus.
That's a memory bank.
And then we also have a right pulse,
and the memory bank has the property that when the right pulse becomes one,
then whatever's on the input bus gets loaded into the selected word,
and its value is available on the output bus.
So, it's the sequence of registers.
Register sort of on each row,
except that we use the address to select one of them
to work like the register on the previous slide.
So, here's the implementation.
So for every memory word,
in this case there's four words,
each with six bits.
So, we have w bits going across for each word,
and those are just memory bits just as before.
Now, over at the left,
we have a decoder demux.
So, remember if we take the address bits,
those address bits and then there is a value that comes in,
that's the right enable.
So, there's exactly one pair of lines that becomes high.
That's what the decoder demux does for us.
And all the rest of those lines are zero.
That's what we call them selection lines.
The address selects which part of the memory is going to be active.
In this case, we say right enable is high,
so they're both one.
If right enable was off,
then top one would be zero.
But either way only that word,
in this case the bitzer one zero or two,
is the one that's selected.
And then, what we need to do is as we've selected a word we want it's value,
but we have to collect the output values,
only one of them is going to matter for each bit position,
the one for the selected words,
so only one of them could possibly be one.
And so all we need to do,
is collect them together in a big tall or gate,
that goes from top to bottom ending the contents of the memory bit with the select line.
So that's one hot marks that we've used before,
and those things then take the selected word right to the output bus.
So, these are all components that we've seen before,
and just put together to implement the memory that gives us the behavior that we want.
And of course, in TOY-8 this is going to be our implementation of our main memory.
So, this example where you can see all the switches is 24 bits.
So, for TOY-8 it's bigger,
it's 16 8-bit words,
so that's 128 different bits.
And the decoder demux has 16 different gate,
it takes four bits as address,
but otherwise it's the same.
It's got an input bus,
it's got an output bus,
it's got an address selector word,
and it's got the right control signal.
That's our main memory bank for TOY-8.
So, again a major component of that TOY-8 computer.
And again, if you implemented the circuit for TOY,
there would be 256 16-bit words that'd be hard to see at every switch for sure.
But wouldn't really add much insight.
So, the input bus comes from the register,
now the output bus goes to the register in the instruction register,
and the address bits come from the PC.
And we'll see how the memory connects up to the other components.
And again, your computer might have a billion bits,
you need a electron microscope to see them all,
but the design is the same.
So that's starting from the idea of a simple flip flop across coupled nor gates,
we get several of the main components of our toy computer.
We get the clock that has one flip flop,
in it one bit of memory,
we get our registers and we get our main memory.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
