THE ORGANIZATION AND PROGRAMMING OF A SIMPLE COMPUTER Richard R. Eckert
THE VON NEUMANN STORED-PROGRAM COMPUTER (Fig. 1) Most digital computers follow John Von Neumann's classical, stored-program model in their internal organization. In this model the computer is composed of the following functional parts: the central processing unit (CPU), the memory, and one or more input-output (I/O) units.
The CPU performs two basic functions: (1) It controls and coordinates the activities of the other parts of the computer and of its own component parts. This control function is performed by circuits which send out sequences of control signals that cause the various components of the computer to act at the correct times. (2) It processes information that it contains or that is sent to it by the other units. This processing function is carried out by circuits capable of performing arithmetic and logical operations on data contained within the CPU. The memory of a digital computer may be visualized as a series of compartments or cells, each of which can hold one binary number. Each cell has another number associated with it (called its address) that uniquely identifies which cell it is. The addresses of a given memory normally range from zero up to an integer that is one less than the capacity of the memory. The number stored within a given cell is called a word, and a stored word may be data that can be manipulated by the CPU or a code number representing an instruction that can be executed by the CPU. A sequence of coded instructions stored in memory that, when executed by the CPU, causes some specific task to be performed is known as a computer program. Input and output units provide communication between the computer and the external world of continuously-varying (analog) signals. These signals are unintelligible to the digital circuits within the computer, which respond only to discrete (1 or 0) signals. Input units convert analog signals from external world devices to the digital signals used inside the computer. Output units perform the inverse function. In most cases input and output devices are electro-mechanical in nature and much slower than the computer's CPU or its memory. Therefore an interface is needed to coordinate the transfer of data between the CPU and the I/O device. Such an interface is often called a port, and, as in the case of memory, each port may have a unique identifying address. BASIC CYCLE OF OPERATION (FETCH-DECODE-EXECUTE) All of the operations that occur within a digital computer are synchronized by a common clock that provides a regular stream of pulses. These pulses provide a time base for the basic fetch-decode-execute cycle that occurs inside the machine. During the fetch part of the cycle, the next coded instruction is brought into the CPU from memory. Decoder circuits then determine what the instruction is, sequencer circuits, in turn, output the appropriate series of control signals to cause the instruction to be executed. This latter phase is known as the execute part of the cycle. The basic fetch-decode-execute cycle is repeated continuously until the clock is stopped. CONNECTING THE COMPONENTS--THREE BUS ARCHITECTURE (Fig. 2) A "bus" is a common signal path that can be used for communication between pairs of receivers and transmitters selected from many (tens of thousands to millions of) possible candidates. Many digital computers have three-bus architectures in which the transfer of information between component parts requires three communication paths: an address bus, a data bus, and a control bus.
The address bus carries the address of the next piece of data to be transferred between the CPU and the memory or I/O units; the data bus carries the actual data to be transferred, and the control bus carries control signals from the CPU to memory and I/O units. Important control signals are: MEMR, which, when active, causes the data contained in the memory cell whose address is currently on the address bus to be placed on the data bus; MEMW which, when active, causes the information currently carried on the data bus to be stored into the memory cell whose address is on the address bus, IOR, which is like MEMR, except that the address is that of an input port; IOW, which is like MEMW, except that the address is that of an output port. A SIMPLE (FICTITIOUS) CPU (Fig. 3) To illustrate the internal organization, functioning, and programming of a digital computer, we now present a fictitious computer system. The CPU of this computer is about as simple as could be imagined. Its CONTROL SECTION contains a Program Counter (PC) register (sometimes called an instruction pointer) which always holds the memory address from which the next instruction is to be fetched. An Instruction Register (IR) receives each instruction as it comes in from memory. Decoder and controller/sequencer circuits output the correct series of control signals necessary to execute the instruction contained in the IR. The PROCESSING SECTION of the CPU contains an arithmetic-logic unit (ALU), which can perform operations on data contained in its two input registers: the accumulator (ACC) and register B. This very simple ALU is capable only of adding or subtracting. The ADD and SUBTRACT signals are provided by the CONTROL SECTION of the CPU. For each of these two functions, the ACC will contain the result of the operation after execution.
INSTRUCTION FORMATS (FICTITIOUS) FOR THE SIMPLE PROCESSOR Instructions for this machine are three digits long. The first digit (op-code field) specifies a code (0-9) for some basic instruction in the set of instructions that the machine can perform. The second two digits (operand field) specify an address (memory or I/O). For each type of instruction, the word contained in the memory cell or I/O port specified by the address contained in the operand field will be manipulated by the CPU. The op-code field specifies WHAT is to be done; the operand field specifies WHERE the data to be operated on is located. OPCODE OPERAND __________________ /_____/_____/_____/ <----- A 3-digit instruction A SAMPLE ( FICTITIOUS) INSTRUCTION SET The following table presents a set of instructions that may be executed on our fictitious computer. For each, the op-code number, a memory-aiding "mnemonic", and a description on what the instruction does are specified. OPCODE MNEMONIC MEANING ------------------------------------------------------------------------------------- 0 NOP No operation occurs. 1 LDA The data word contained in the memory address specified in the operand field of the instruction is copied into the ACC register. 2 STA Data in the ACC is copied to the memory cell whose address is contained in the instructions operand field. 3 ADD The word contained in the memory cell whose address is specified in the operand field is added to the contents of the ACC; the result replaces the former contents of the ACC. 4 SUB The word contained in the memory address specified in the operand field is subtracted from the ACC; the result replaces the former contents of the ACC. 5 IN Data contained in the input port whose address is given in the operand field is copied to the ACC. 6 OUT Data in the ACC is copied to the output port whose address is contained in the operand field. 7 JMP Fetch the next instruction from the memory address contained in the operand field (unconditional jump). 8 JN The next instruction is to be fetched from the address in the operand field if the ACC contains a negative number (conditional jump). 9 HLT Clock stops. INSTRUCTION CODING (A) MACHINE CODE (machine readable and executable) As mentioned above, for our simple computer, each instruction is one three-digit number. The first digit expresses the opcode and the second the operand. (In reality the digital circuits within the CPU would receive these numbers in binary (1 or 0) form so that they could react by opening or closing the proper switches, thereby causing the correct actions to occur.) Some examples of machine language instructions for our fictitious machine follow: Instruction Meaning ------------------------------------------------------------------------------------ 154 load the ACC from memory location 54 376 add to the ACC the contents of location 76 582 load the ACC with the word provided by the input device connected to port 82 712 fetch the next instruction from location 12 900 stop the clock (the 00 is arbitrary) (B) ASSEMBLY LANGUAGE CODE (symbolic, non-machine-executable) Since it is difficult to program in machine language, symbolic "assembly" languages have been devised in which there is a one-to-one correspondence between instructions written in these languages and their machine language counterparts. Both the machine language for a given computer and its associated assembly language are machine specific; they may not be used on computers with a different internal organization. An assembly language program consists of a sequence of assembly language statements. Each statement can be any of the following: 1. Instructions written in mnemonic form. There is a one-to-one correspondence between an assembly language instruction and the corresponding machine language instruction. A program called an "assembler" is usually used to translate assembly language instructions to their machine language counterparts. 2. Pseudo-ops. These statements are called pseudo-ops since they generate no machine language code. There are two general types: A. Data allocation pseudo-ops. These define data to be used; Memory space will be reserved to hold the data. These are like variables in a high-level language. Names can be given to the memory space allocated. An example is the DW (define word) pseudo-op. B. Assembler directives. These are statements that provide information to the assembler program. Examples are: END--end of program; ORG--change the current address; EQU--assign a value to a symbol (define a constant). 3. Macro definitions. A macro is a single statement that stands for a block of statements. We'll look at macros later in the course. Assembly language instructions have four fields: 1. An optional name field. This is a symbol that can be referenced by other statements. The assembler usually assigns the value of the current memory address to this symbol. The current address is kept track of by an assembler variable called the location counter. 2. The operation field. This is a mnemonic that represents the opcode (for an instruction) or the pseudo-op (for data allocation or assembler directives). This field is always present. 3. The operand field. This field contains information that specifies what is to be operated on (the object of the operation). It is almost always present. 4. An optional comment field. This is used for documentation purposes. Since, in general, assembly language instructions are so primitive, assembly language programs tend to be long and very obtuse. It is therefore very important that the comment field be used so that the reader of the program understands what each statement in an assembly language program is doing. Most assemblers require that a statement be placed on a single line with the various fields separated by white space (one or more blanks or tab characters). AN EXAMPLE ASSEMBLY LANGUAGE PROGRAM The following assembly language program is targeted for our simple computer. It makes use of several pseudo-ops mentioned above and mnemonics given above for the various opcodes in the instruction set of our machine. It computes the sum of the two numbers stored in memory locations 07 and 08 and then outputs the result to port 04. (Microsoft MASM and Borland TASM assembler conventions have been used.) Name field Operation field Operand field Comment field ------------------------------------------------------------------------------------- ;*** A program to add two numbers stored in memory and output the result *** ;*** First constants and data definitions *** OPORT EQU 04 ;OPORT stands for 04 ORG 07 ;Set location counter to start of data NUM1 DW 53 ;Assign value 53 to NUM1 NUM2 DW 41 ;Assign value 41 to NUM2 ;*** Now the instructions *** ORG 00 ;First instruction stored at address 0 LDA NUM1 ;Get first number ADD NUM2 ;Add second number OUT OPORT ;Output result HLT ;Stop computer's clock END ;Tell assembler program is done ASSEMBLING THE PROGRAM Most assemblers are two-pass assemblers. During pass 1 internal opcode tables are used to translate the mnemonics to their machine language opcodes. In addition any symbols appearing in the name field are placed in a symbol table along with their "values." In the case of data definition pseudo-ops like DW, the value is the current address (location counter). During pass 2 the any unresolved symbols are retrieved from the symbol table. (See the second example below.) Most assemblers will produce a human-readable file that shows both the machine language and the assembly language. The format is usually as follows: MACHINE LANGUAGE ASSEMBLY LANGUAGE address contents name operation operand comment For the simple adding program above, this file would look like the following (The comment field has been left blank): MACHINE LANGUAGE ASSEMBLY LANGUAGE address contents name operation operand --------------------------------------------------------------------------------- OPORT EQU 04 07 ORG 07 07 053 NUM1 DW 53 08 041 NUM2 DW 41 00 ORG 00 00 107 LDA NUM1 01 308 ADD NUM2 02 604 OUT OPORT 03 900 HLT END The symbol table would look like the following: Symbol Value ----------------------------------------------------------------------------------- OPORT 04 ;note that for equates the value of the symbol is in the operand field NUM1 07 ;for DWs the value of the symbol is the current location counter value NUM2 08 In this very simple program, nothing was done during assembler pass 2, since all symbols were in the symbol table at the time they were referenced. For our simple machine each instruction is exactly one word long. The assembler automatically increments the location counter for all instructions and DWs. In a real machine like the Intel processors, this is not the case. Instructions can be from 1 to 7 bytes long! WHAT HAPPENS DURING THE FETCH CYCLE -1st clock pulse: The contents of the PC are placed onto the address bus. -2nd clock pulse: The MEMR line of the control bus is activated. This causes memory to respond by placing the data contained in the location whose address is on the address bus onto the data bus. -3rd clock pulse: The IR receives the data that is on the data bus. At the same time the PC is incremented. The instruction is now safely in the IR, where it can be decoded; The PC points to the next instruction in memory. The execute portion of the cycle will now occur. What happens next depends upon what the instruction is. THE EXECUTE CYCLE OF SEVERAL INSTRUCTIONS OPCODE 0 -- NOP: -1st clock: Nothing occurs; the fetch cycle resumes on the next clock pulse. OPCODE 1 -- LDA: -1st clock: The least significant 2 digits (operand field) of the IR are sent out on the address bus. -2nd clock: MEMR becomes active on the control bus. This causes the contents of the selected memory cell to be placed on the data bus. -3rd clock: The contents of the data bus are received by the ACC. OPCODE 3 -- ADD: -1st clock: The least significant 2 digits of the IR go out on the address bus. -2nd clock: MEMR becomes active on the control bus causing the contents of the selected memory location to be deposited on the data bus. -3rd clock: The contents of the data bus are received by register B inside the CPU. -4th clock: The ALU's ADD signal is activated causing the contents of register B to be added to the ACC. The result of the addition is stored back into the ACC. OPCODE 6 -- OUT: -1st clock: The least significant 2 digits of the IR go out on the address bus. -2nd clock: The contents of the ACC go out on the data bus. -3rd clock: IOW becomes active on the control bus causing the contents of the data bus to be received by the selected output port. OPCODE 8 -- JN: -1st clock: If the contents of the ACC are negative, copy the least significant 2 digits of the IR to the PC; if not, do nothing. The result is that, if the ACC was negative, the PC will now be pointing to the jump address. The next fetch will then bring in the instruction stored at that address. If, on the other hand, the ACC was non-negative, the next fetch will bring in the next instruction in sequence, since, in that case, the PC was not altered. OPCODE 9 -- HLT: -1st clock: Stop the clock. The fetch-decode-execute cycle terminates. PROGRAM EXECUTION Let us now trace execution of the simple adding program we developed above. We assume that it has already been loaded into memory starting at address 0 and that the PC contains a 00. (On most real systems, the PC is automatically cleared to zero when the computer is turned on. There are, however, many other complexities involved in loading the first program into memory. We will not worry about those issues here.) We also assume that memory location 07 has already been loaded with 53 and location 08 with a 41 (both specified in the program. The fetch-decode- execute cycle is about to commence. The following table indicates what will be on the various buses and in the various cpu registers as each instruction is fetched and executed. Each line of the table represents the state of the machine after a new clock pulse arrives. In this table only changed entries are shown. CLK CPU REGISTERS SYSTEM BUSES WHAT'S HAPPENING # PC IR ACC B Address Control Data ---------------------------------------------------------------------------------- 00 Clock starts 1 00 00 Begin 1st fetch 2 MEMR 107 3 01 107 End 1st fetch 4 07 Begin 1st execute 5 MEMR 53 6 53 End 1st execute 7 01 Begin 2nd fetch 8 MEMR 308 9 02 308 End 2nd fetch 10 08 Begin 2nd execute 11 MEMR 41 12 41 13 94 ADD to ALU End 2nd execute 14 02 Begin 3rd fetch 15 MEMR 604 16 03 604 End 3rd fetch 17 04 Begin 3rd execute 18 94 19 IOW Result to output port End 3rd execute 20 03 Begin 4th fetch 21 MEMR 900 22 04 900 End 4th fetch 23 Begin 4th execute Clock stops
A MORE COMPLICATED EXAMPLE In this program we want to output the larger of two numbers stored in successive memory locations to port 1. In a high level language like C, the program would be something like: int num1=13, num2=17; if (num1 > num2) printf (num1); else printf (num2); A flow chart for this algorithm is shown below: ACC <-- NUM1 | ACC <-- ACC - NUM2 | | yes ACC < 0 ---------- | | | no | | | ACC <-- NUM1 | | | --------- | | | | <--------------- | | | ACC <-- NUM2 | | -------> | | Output ACC One possible assembly language program that implements this algorithm on our machine (with assembler translation after pass 1 also shown) is as shown below. Note that during pass 1, the forward-referenced symbols SECOND and OUTPUT are not yet in the symbol table (shown below the listing) when they are first encountered by the assembler, and therefore the JN and JMP instructions cannot be completely translated during pass 1. Instead they are flagged. MACHINE LANGUAGE ASSEMBLY LANGUAGE address contents name operation operand comment ----------------------------------------------------------------------------------- 10 ORG 10 ;start of data 10 13 NUM1 DW 13 ;1st number 11 17 NUM2 DW 17 ;2nd number 00 ORG 0 ;start of code 00 110 LDA NUM1 ;get 1st number 01 411 SUB NUM2 ;subtract 2nd 02 8?? JN SECOND ;2nd is bigger 03 110 LDA NUM1 ;1st is bigger 04 7?? JMP OUTPUT ;output result 05 111 SECOND: LDA NUM2 ;load 2nd 06 601 OUTPUT: OUT 1 ;out to port 1 07 900 HLT END The symbol table at the end of assembler pass 1 would look like: Symbol Value ------------------------------------------------------------------- NUM1 10 ;the value of the location counter for that symbol NUM2 11 ;the value of the location counter for that symbol SECOND 05 ;the value of the location counter for that label OUTPUT 06 ;the value of the location counter for that label During assembler pass 2, the two flagged instructions (the JN and the JMP) are examined again by the assembler. Now the symbols have values in the symbol table, so the machine language translation can be completed (8?? --> 805 and 7?? --> 706). As an exercise, now try to trace execution of this program. Assume that it has already been loaded into memory starting at location 00. Fill in a table similar to that of the adding example above that illustrates what is contained in the various CPU registers and what is on the buses during each step of execution for each case. Repeat the exercise assuming that address 10 (NUM1) contains a 25 and address 11 (NUM2) a 22. What would happen if the two locations contained the same value? As a second exercise, write an assembly language program targeted for this machine that will multiply two numbers stored in successive memory locations. (Hint: one way of doing multiplication is to perform successive adds. For example, if you were multiplying 4 x 3, it would be equivalent to set an accumulator to zero and then add 4 to that accumulator three times. To implement this algorithm, you will need to reserve a memory location for the current value of the accumulator and another for the current "count".)
