Transcript Module7

The Logic Machine
• We looked at programming at the high level
and at the low level.
• The question now is: How can a physical
computer be built to run a program?
• In this module, we look at computer hardware
and how it can be made to execute a program.
• In the early days of computing, a computer
was hard-wired to perform a specific task.
• A conceptual leap was that a program could
be stored in memory along with other data.
The Big Switch
• Modern electronic digital computers are
based on simple switches---lots of them.
• Switches come in a variety of forms: a light
switch, an electromechanical relay, a vacuum
tube, a transistor.
• By connecting enough switches in the right
way, a computing machine can be constructed
to perform any logical operation you want.
• Integrated circuits consisting of transistors
and other electronic components are
constructed photographically. Photographs
can be reduced in size to construct very small
integrated circuits.
Anatomy of a Switch
• A switch consists of three parts: an “in”, an
“out”, and a “control”. Think of a light switch.
• Normally open switch. Truth table.
• Normally closed switch. Truth table.
• You don’t have to think of a switch as being an
electrical switch.
• A switch can control the flow of water or the
flow of traffic or the rotation of mechanical
gears or any of a number of things.
• …which brings us to the viewpoint of thinking
of switches as controlling the flow of logic.
Logic
• It is known that any logical expression can be
generated from only three basic logical
operators.
• AND - “P and Q” is denoted PQ. Truth table.
• OR - “P or Q” is denoted P+Q. Truth table.
• NOT - “not P” is denoted P’. Truth table.
• Example of how a more complicated logical
expression can be built from the three basic
operators.
• Since P+Q=(P’Q’)’, we can get rid of OR and
reduce the number of basic logical operators
to only two---namely, AND and NOT.
Gates
• To build a computer which can carry out
logical expressions, “all” we have to do is
design circuit analogs of AND, OR, and NOT.
• The circuit analogs of AND, OR, and NOT are
called the AND gate, the OR gate, and the NOT
gate.
• The Logg-O program.
Gates
• Since OR can be written in terms of AND and
NOT, we need to build circuit analogs only for
AND and NOT.
• This can be done with simple switches.
• Once we can build gates from switches, we
can build any logical expression from the
basic gates.
• Think of the basic gates as “building blocks”.
• circuit - a collection of gates.
Gates
• Examples:
• A one-bit comparator. This is the example we
used to illustrate how to build a more
complicated logical expression from the three
basic operators.
• A one-bit half adder. This adds two bits (0 or
1) and produces their sum along with a carry.
• A one-bit full adder. This is constructed from
two half adders and includes provision for a
carry in.
• Several one-bit full adders can be hooked
together to add longer strings of bits.
On to Arithmetic
• To handle longer strings of binary bits, we can
enter the data in serial or in parallel.
• Example: 37 in binary is 100101.
In serial, 100101 would be input on one line
one digit at a time. Each digit corresponds to
an electrical pulse--high, low, low, high, low,
high. Similar to Morse Code. Simple, but slow.
In parallel, we decide in advance how many
digits our computer will use for numbers and
assign a separate line to each digit. 100101
requires 6 lines. More complex, but fast.
Addition
• As noted, addition of longer strings of bits is
done by combining one-bit adders.
• For example, an adder which adds two 4-bit
numbers input in parallel is constructed from
four one-bit adders.
• Multiplication is a bit more complicated, but is
essentially addition with shifting.
• By combining these basic building blocks in
ever more complex ways, circuits can be
designed to perform all the operations
associated with modern computers.
Control
• Now that we know (more or less) how to build
computer circuits, how do we control them?
That is, how do we program a computer?
• The trick is to design a computer so that,
every time it has to perform an operation, it
performs ALL operations and lets a program
set switches to determine which result to use.
• This is done using a multi-way switch called a
multiplexor.
• Example: A two-way multiplexor (MUX) which
determines whether the output is a or b.
Control
• Multiplexors can be combined to build an
arithmetic-logic unit (ALU).
• An ALU simultaneously performs all possible
operations on its inputs. The result that is
chosen by the select line is the output.
• Example: A two-function two-bit ALU to
perform addition a+b and multiplication ab.
• A decoder is the reverse of a multiplexor. It
sends its input to one of many possible output
lines depending on the value of the select line.
• Example: A four-way decoder.
Storage
• Finally, we need to add storage capability to a
computer to remember processed information.
• To add memory, we use a latch.
• latch - a circuit that can store a single 0 or 1.
• A latch can be constructed in a number of
ways using gates.
• Example: A latch constructed from two AND
gates, a NOT gate, and two NOR gates. (You
looked at the NOR gate in Lab 7.2.)
Operation of a Latch
•
1.
2.
3.
•
•
To store a bit d:
Set strobe=1.
Set input=d. This also sets output=d.
Set strobe=0.
As long as strobe=0, output=d.
To change the stored value, repeat steps 1,
2, and 3.
• Thus, the latch “remembers” the value d until
a new value of d is sent with strobe=1.
Memory
• Gates and latches can be used to build
memory.
• 1 MB of memory contains about 75 million
gates!
• 64 MB of memory contains about 4.8 billion
gates.
Architecture
• We now have a collection of basic building
blocks for computers.
• Switches -----> gates -----> arithmetic logic unit
and memory.
• How these building-block components are
combined to construct an actual computer is
called architecture.
• architecture - that which is visible to the
assembly language programmer.
• High-level programmers don’t have to worry
how a computer is put together; assembly
language programmers do.
Fetch-Execute Cycle
• To keep a computer operating in an orderly
fashion, a computer needs an internal clock.
• The ticks of a computer clock are measured in
millions of cycles per second (Hertz).
• Example: A 500 MHz computer has a clock
operating at 500 million Hertz.
• At one tick of the computer clock, the
computer fetches an instruction from memory.
• At the next tick, the computer begins to
execute the instruction.
• At subsequent ticks, the computer finishes
executing the instruction, fetches the next
instruction, executes it, and so on.