Information Technology Reference
In-Depth Information
This memory is called random-access because the time to access a word is the same for all
words. The Turing machine introduced in Section
3.7
has a tape memory in which the time
to access a word increases with its distance from the tape head.
The random-access memory in the model in Fig.
3.17
has
m
=
2
μ
storage locations each
containing a
b
-bit word, where
μ
and
b
are integers. Each word has a
μ
-bit address and the
addresses are consecutive starting at zero. The combination of this memory and the CPU
described above is the
bounded-memory RAM
. When no limit is placed on the number and
size of memory words, this combination defines the
unbounded-memory RAM
.Weusethe
termRAM for these two machines when context unambiguously determines which is intended.
DESIGN OF A SIMPLE CPU
The design of a simple CPU is given in Section
3.10
.(S e
Fig.
3.31
.) This CPU has eight registers, a
program counter
(PC),
accumulator
(AC),
mem-
ory address register
(MAR),
memory data register
(MDR),
operation code (opcode) regis-
ter
(OPC),
input register
(INR),
output register
(OUTR), and
halt register
(HALT). Each
operation that requires two operands, such as addition or vector
AND
,usesACandMDRas
sources for the operands and places the result inAC.Eachoperationwithoneoperand,such
as the
NOT
of a vector, uses AC as both source and destination for the result. PC contains the
address of the next instruction to be executed. Unless a jump instruction is executed, PC is
incremented on the execution of each instruction. If a jump instruction is executed, the value
of PC is changed. Jumps occur in our simple CPU if AC is zero.
To fetch the next instruction, the CPU copies PC to MAR and then commands the
random-access memory to read the word at the address in MAR. This word appears in MDR.
The portion of this word containing the identity of the opcode is transferred to OPC. The
CPU then inspects the value of OPC and performs the small local operations to execute the
instruction represented by it. For example, to perform an addition it commands the arith-
metic/logical unit (ALU) to combine the contents of MDR and AC in an adder circuit and
deposit the result in AC. If the instruction is a
load accumulator
instruction (LDA), the CPU
treats the bits other than opcode bits as address bits and moves them to the MAR. It then com-
mands the random-access memory to deposit the word at this address in MDR, after which it
moves the contents of MDR to AC. In Section
3.4.3
we illustrate programming in an assembly
language, the language of a machine enhanced by mnemonics and labels. We further illustrate
assembly-language programming in Section
3.10.4
for the instruction set of the machine de-
signed in Section
3.10
.
3.4.2 The Bounded-Memory RAM as FSM
As this discussion illustrates, the CPU and the random-access memory are both finite-state
machines. The CPU receives input from the random-access memory as well as from external
sources. Its output is to the memory and the output port. Its state is determined by the
contents of its registers. The random-access memory receives input from and produces output
to the CPU. Its state is represented by an
m
-tuple
(
w
0
,
w
1
,
...
,
w
m−
1
)
of
b
-bit words, one
per memory location, as well as by the values of
in wrd
,
out word
,and
addr
. We say that
the random-access memory has a
storage capacity
of
S
=
mb
bits. The RAM has input and
output registers (not shown in Fig.
3.17
) through which it reads external inputs and produces
external outputs.
As the RAM example illustrates, some FSMs are programmable. In fact, a program stored
in the RAM memory selects one of very many state sequences that the RAM may execute. The
Search WWH ::
Custom Search