2 Computer Organization ( Terminal Session on this Machine )

2.1 Processors and Memory

There are two main components which have been part of nearly all computer systems ever designed and built. The first is called the processor (known also as the Central Processing Unit or CPU)and the second is called the memory. The processor is the part of a computer system which does the actual computing. That is, the part which adds, subtracts, multiplies and divides. Most processors can also compare values and perform conditional actions as a result of such comparisons. Many processors have instructions which perform various types of conversions between different representations of data.

The processor itself is divided into three components that carry out the various functions that the computer is capable of performing. The first component of the processor is the controller. The controller acts as a foreman that oversees the tasks of the processor. The controller looks at the next instruction to be executed and assigns the sub-tasks that must be accomplished to carry out that instruction to the other components of the processor.

Another component of the processor is the Arithmetic-Logic Unit (ALU). This unit is the part of the processor which performs the mathematical computations and logical tasks that we expect a computer to be able to do. Addition, subtraction, comparison, etc., are all carried out by the ALU.

The last component of the processor is a collection of one or more registers. Registers are special named memory cells in the processor where information is temporarily stored during various stages of a computation. The currently executing instruction, for example, resides in a register called the Instruction Register. Since modern processors can execute millions of instructions per second it is expected that information would not stay in a register for more than a few millionths of a second.

The memory unit of a computer is the place were both data and programs are stored. John Von Neuman, a mathematician and physicist, is generally credited with the idea of structuring a computer so that both data and programs are stored in the memory of a computer. Earlier computer designs had computer programs hard-wired into the processor which meant that when it was necessary to re-program a machine, the machine literally had to be re-wired. This was a very time consuming and error prone process. Modern computers, which store both programs and data in their memories, are sometimes called Von Neuman machines in honor of his contribution of this key idea.

A computer memory system is accessed (or read) by specifying the location (called an address) of the memory cell. The memory system then responds by producing a copy of the contents of that cell. The original value of the cell is not changed by this process. This is sometimes called a non-destructive read.

A computer memory system is changed (or written) by specifying the location of the memory cell together with the new value for that cell. The previous value stored in the cell is replaced by the new value. This is sometimes called a destructive write.

The values stored in a computer memory are simply numbers. Numbers are used to represent both data and instructions. In fact, one cannot distinguish instructions from data when examining the contents of a memory system. It is up to the programmer or operating system to keep track of which memory cells hold data and which are program instructions. Programs have been written which manipulate and produce programs. Such programs treat instructions as data. The usefullness of this idea was recognized by Von Neuman and was, perhaps, one of the motivating reasons for his stored program design for a computer.

The processor and memory unit are wired together wiring connections called buses. A bus is a low resistance connection consisting of 1 or more wires. There are three such connections. The first, called the address bus, is used by the processor to tell the memory system the number or location of the memory cell the processor wishes to access. The second bus is used to send data out to the memory. The third bus is used to transmit data and instructions to the processor.

A typical computer might be organized as indicated in the following diagram:

The processor contains a few memory cells, called registers, which are used for efficient temporary storage:

2.1.1 Processor Registers

The Contents of a memory cell or a register is simply a number. For purposes of illustration, suppose that each memory cell is large enough to hold numbers up to 4 decimal digits in size. Later, we will learn that most computers use the binary number system, but for now we will use the decimal number system in our model computer descriptions.

If a memory cell holds an an instruction, use the first two decimal digits represent the operation and the remaining digits to represent the adderess or location of the instruction operand.

2.1.2 Instruction format

Using this scheme, we could set up the following operation codes:

Operation		Code	Function

add			01	c(acc)=c(acc)+c(addr)
sub			02	c(acc)=c(acc)-c(addr)
load			03	c(acc)=c(addr)
store			04	c(addr)=c(acc)

Note: These codes do not correspond to any known real computer, but rather, they are the operation codes for a hypothetical model computer which we will use to illustrate important aspects of computer organization.

2.2 Two Simple Programs

Perhaps the shortest useful program we might write would move a value from one memory cell to another. This could be modeled by the Scheme expression:

(define q r)

To accomplish this task, it is necessary to first load the value of r into the accumulator and then store the accumulator in the memory cell q.

load		r
store		q

Consider a program which computes the following expression:

(define c (+ a b))

load	a
add	b
store 	c

It is possible to write a program which will translate from the Scheme version of this program to the symbolic form of the machine instructions shown above. Such a program, which translates from the Scheme notation, (define c (+ a b))
to the machine language:

load	a
add	b
store	c

is called a compiler.

The program must be stored in memory before it may be executed. Since we don't know exactly where in memory we wish to put either the program or the data items a, b or c, we can only partially translate the program into machine readable form as:

op	location
03	a
01	b
04	c

The memory system is a collection of memory cells, each having a number or address. The following diagram illustrates the organization of memory

Suppose we decide to locate the above program beginning in memory cell 4. Since the program takes 3 cells we might put the data in the first free cell after the last instruction in the program which means that we could define:

Symbol		Location
a		7
b		8
c		9

The final translated program then looks like:

2.3 Machine Language Program

location	operation		address
04		03			07
05		01			08
06		04			09

A program which translates from the symbolic form for a program

load	a
add	b
store	c

to the machine language form is called a symbolic assembler, or simply an assembler.

2.4 How the Computer Executes a Program

We next focus on how a computer executes such a program. Recall the organization of the processor:

The program counter register always contains the location of the next instruction to be processed. To get started executing this program we somehow have to set the contents of the program counter (pc) to 4 because this is the location of the first instruction of our program.

The following flow chart best explains how the processor executes a program.

2.4.1 Processor Flow Chart

2.4.2 Executing a Program

To illustrate the various steps in the processor flow chart we give the following trace of the execution of Program.

Step 0 Set initial value for the pc

pc	04
ir	?
acc	?

Step 1 (fetch)

pc	04
ir	0307
ac	?

Step 2 (increment pc)

pc	05
ir	0307
ac	?

Step 3 (execute)

pc		05
ir		0307
ac		22			(here we are supposing that
					 C(07) has been set to 22
					 somehow and also suppose
					 C(08) has been set to 5)

Step 4 (fetch)

pc	05
ir	0108
acc	22

Step 5 (increment pc)

pc	06
ir	0108
acc	22

Step 6 (execute)

pc	06
ir	0108
acc	25

Step 7 (fetch)

pc	06
ir	0409
acc	25

Step 8 (increment pc)

pc	07
ir	0409
acc	25

Step 9 (execute)

pc	07
ir	0409
acc	25		(contents of 09 changed to 25)

Step 10 (fetch)

pc	07
ir	0022
acc	25

Step 11 (increment pc)

pc	08
ir	0022
acc	25

Step 12 (execute)

pc	08
ir	0022
acc	25

Of course, at this point we have a problem since the ir does not contain an instruction.

This means we need some kind of more elaborate setup for placing programs in memory and starting and stopping programs. These are some of the tasks performed by a computer operating system.

2.5 A Scheme Model of the Computer.

The following Scheme definitions provide constructor verbs for making memory systems and processors described in Section 2.1. These definitions are useful in that they provide a more precise description of the model computer than is possible using the English language and, in addition, the provide a working model that can be examined, programmed and experimented with. This model uses two verbs, rep and list-subst, which are given below. A more complete description of these verbs will be given in Chapter 3.

2.5.1 The Memory Model

(define make-memory
  (lambda (mem-init)
    ; Set up initial memory values
    (let ((mem mem-init))
    ; The different user commands a model memory can perform
      (lambda msg
        (case (car msg)
          ((display-mem) mem)
          ((reset-mem) (set! mem mem-init))
          ((load-mem) (set! mem (cadr msg)))
          ((access) (list-ref mem (cadr msg)))
          ((store) (set! mem (list-subst mem (cadr msg) 								(caddr msg))))
          (else 'Unknown-memory-command))))))

A memory system is modeled as a list of numbers which are given as the initial argument to make-memory. For example, to setup a memory system containing the program we studied earlier, give the following definitions:

(define prog '(0 0 0 0 307 108 409 22 3 0))
(define mem (make-memory prog))

Then to access the value (load instruction) stored in memory cell 4 you could:

(mem 'access 4)

To store the value 10 in cell 3 you would write:

(mem 'store 3 10)

To see the contents of all of the memory system write:

(mem 'display-mem)

2.5.2 The Processor Model

(define make-processor
  (lambda (ac-init pc-init ir-init cc-init mem-init)
   ; Set up initial values for the registers and identify
   ; a memory unit attached to the processor
    (let ((ac ac-init)
          (pc pc-init)
          (ir ir-init)
          (cc cc-init)
          (mem mem-init))
    (define cpu
      (lambda ()
        ;fetch instruction
        (set! ir (mem 'access pc))
        ;increment pc
        (set! pc (+ pc 1))
        ;execute instruction
        (let ((decoded-ir (rep '(100 100) ir)))
          (case (car decoded-ir)
            ; add instruction
            ((1) (set! ac (+ ac (mem 'access
                                     (cadr decoded-ir)))))
            ; sub instruction
            ((2) (set! ac (- ac (mem 'access
                                     (cadr decoded-ir)))))
            ; load instruction
            ((3) (set! ac (mem 'access (cadr decoded-ir))))
            ; store instruction
            ((4) (mem 'store (cadr decoded-ir) ac))
            (else (error "Invalid-instruction"))))))
 ; The different user commands a model processor can perform
      (lambda msg
        (case (car msg)
          ((display-regs) (list (cons 'ac ac)
                                (cons 'pc pc)
                                (cons 'ir ir)
                                (cons 'cc cc)))
          ((display-mem) (mem 'display-mem))
          ((set-ac) (set! ac (cadr msg)))
          ((set-pc) (set! pc (cadr msg)))
          ((set-ir) (set! ir (cadr msg)))
          ((set-cc) (set! cc (cadr msg)))
          ((set-mem) (set! mem (cadr msg)))
          ((step) (cpu))
          ((run) (let loop ((i 1)) (cpu) (loop 1)))
          (else 'Unknown-processor-command))))))

To create a model processor p, you write:

(define p (make-processor 0 0 0 0 mem))

The zeros are initial values for the processor registers and mem specifies which memory is attached to the processor. The processor contains user commands for displaying and setting the registers. It can also be told to single step through a program one instruction at a time as well as run a program.

2.5.3 A Scheme Session Using the Computer Model

; A sample machine language program
; Starting at location 4
;       load  A
;       add   B
;       store C
;  A    dc    22
;  B    dc    3
;  C    dc    0

; Recall that our memory cells hold 4 decimal
; digits and we store one instruction or data
; item in each cell.  Each instruction has a
; 2 digit operation field and a 2 digit address
; field.
 
 (define prog '(0 0 0 0 307 108 409 22 3 0))
 
; Following is a sample session illustrating the
; use of the model of a computer

; Construct a memory unit called mem
;: (define mem (make-memory prog))
;mem

; Construct a processor called p which uses mem.
; The zeros are initial values for the registers.
;: (define p (make-processor 0 0 0 0 mem))
;p

; Set the pc register to first instruction in program
;: (p 'set-pc 4)
;#[undefined]

; Display the registers before starting
;: (p 'display-regs)
;((ac . 0) (pc . 4) (ir . 0) (cc . 0))

; Display memory contents
;: (p 'display-mem)
;(0 0 0 0 307 108 409 22 3 0)

; Execute one instruction (load A)
;: (p 'step)
;#[undefined]

; The registers after the load instruction
;: (p 'display-regs)
;((ac . 22) (pc . 5) (ir . 307) (cc . 0))

; Execute one instruction (add B)
;: (p 'step)
;#[undefined]

; The registers after the add instruction
;: (p 'display-regs)
;((ac . 25) (pc . 6) (ir . 108) (cc . 0))

; Execute one instruction (store C)
;: (p 'step)
;#[undefined]

; The registers after the store instruction
;: (p 'display-regs)
;((ac . 25) (pc . 7) (ir . 409) (cc . 0))

; Display memory after the store instruction
;: (p 'display-mem)
;(0 0 0 0 307 108 409 22 3 25)

; Execute one instruction
;: (p 'step)
;*** ERROR -- Invalid-instruction
; We tried to execute the contents of A = 22
; as an instruction.

; Display the registers after this error
;: (p 'display-regs)
;((ac . 25) (pc . 8) (ir . 22) (cc . 0))

; Reset the pc to 4 so we can run the program
; again
;: (p 'set-pc 4)
;#[undefined]

; Run the program
;: (p 'run)
;*** ERROR -- Invalid-instruction
; Same result as before

; Display memory
;: (p 'display-mem)
;(0 0 0 0 307 108 409 22 3 25)

; Display the registers
;: (p 'display-regs)
;((ac . 25) (pc . 8) (ir . 22) (cc . 0))

2.5.4 rep and list-subst

Following are the definitions for rep and list-subst which are used in the model computer:

; rep

; Compute the base-list representation of b.

; Given base-list which is the list of ratios of the relative
; place values of each digit in the representation of b and b
; which is an integer, rep computes a representation of b using
; the number system of base-list.
; Notice if the left most (or most significant) value in the
; base-list is zero, then any remaining quotient is returned
; as the most significant value in the result.  This value may
; not be a digit in the number system since no division is
; performed in this case.

(define rep
  (lambda (base-list b)
      (define rep-helper
        (lambda (divisors n result)
          (if  (null? divisors)
            result
            (let ((div (car divisors)))
              (if (= div 0)
                (cons n result)
                (rep-helper (cdr divisors)
                            (quotient n div)
                            (cons (remainder n div) result)))))))
      (rep-helper (reverse base-list) b '())))
 
; list-subst

; Given a list ls, an integer i and a replacement
; value v, list-change produces a new list having
; the same elements as ls except that the i th
; element has been substituted by v.  No error checking
; is done to insure that i is one of the list indices.
; This function is used in the store instruction of our
; modeled computer

(define list-subst
  (lambda (ls i v)
    (define subst-helper
      (lambda (cnt new-value lst result)
        (if (= cnt 0)
          (append (append result (list new-value))
                                    (cdr lst))
          (subst-helper (- cnt 1)
                        new-value
                        (cdr lst)
                        (append result (list (car lst)))))))
    (subst-helper i v ls '())))