Machines with Memory - Models of Computation: Exploring the Power of Computing - page 137

We now derive explicit upper bounds to ( 3.4 ). Let Λ( k )= C ( 1, q ,2 q + 1 ) and Δ( k )=
D ( 1, q ,2 q + 1 ) when q = 2 k . Then, the inequalities of ( 3.4 ) become the following:

Λ( k + 1 ) ≤ Λ( k )+ C ( k )

Λ( 0 ) ≤ K 6

Δ( k + 1 ) ≤ Δ( k )+ D ( k )

Δ( 0 ) ≤ K 7

where K 6 = C ( 1, 1, 3 )= 7 b + 3and K 7 = D ( 1, 1, 3 )= 4. The solutions to these
recurrences are given below.

k−

j = 0 C

1

Λ( k ) ≤ ( j )

= 2 k ( K 1 k/ 2 + K 2 + K 3 − K 1 ) − kK 2 +( K 6 − ( K 2 + K 3 − K 1 ))

= O ( k 2 k )

k −

j = 0 D

1

Δ( k ) ≤ ( j )

= 2 k ( K 5 + K 4 + 2 ) k 2 +( 1

− − ( K 4 + 2 )) k +( K 7 − ( K 5 + K 4 + 2 ))

= O ( 2 k )

Here we have made use of the identity in Problem 3.1 .From( 3.5 )and( 3.6 ) we establish
the result of Theorem 3.9.8 .

3.10 Design of a Simple CPU
In this section we design an eleven-instruction CPU for a general-purpose computer that has a
random-access memory with 2 12 16-bit memory words. We use this design to illustrate how a
general-purpose computer can be assembled from gates and binary storage devices (flip-flops).
The design is purposely kept simple so that basic concepts are made explicit. In practice,
however, CPU design can be very complex. Since the CPU is the heart of every computer, a
high premium is attached to making them fast. Many clever ideas have been developed for this
purpose, almost all of which we must for simplicity ignore here.
Before beginning, we note that a typical complex instruction set (CISC) CPU, one with
a rich set of instructions, contains several tens of thousands of gates, while as shown in the
previous section, a random-access memory unit has a number of equivalent gates proportional
to its memory capacity in bits. (CPUs are often sold with caches, small random-access memory
units that add materially to the number of equivalent gates.) The CPUs of reduced instruction
set (RISC) computers have many fewer gates. By contrast, a four-megabyte memory has the
equivalent of several tens of millions of gates. As a consequence, the size and depth of the
next-state and output functions of the random-access memory, δ RMEM and λ RMEM , typically
dominate the size and depth of the next-state and output functions, δ CPU and λ CPU ,ofthe
CPU, as shown in Theorem 3.6.1 .