Chap-05-Basic_Computer_Org_and_Design.pdf

Basic Computer Organization and Design 1 Reference: http://ecl.incheon.ac.kr/ We will study … ◼ Chapter 5: Basic Computer Organization and Design: ◼ Instruction Codes ◼ Computer Registers ◼ Computer Instructi...

Basic Computer Organization and Design 1 Reference: http://ecl.incheon.ac.kr/ We will study … ◼ Chapter 5: Basic Computer Organization and Design: ◼ Instruction Codes ◼ Computer Registers ◼ Computer Instructions ◼ Timing and Control ◼ Instruction Cycle ◼ Memory Reference Instructions ◼ Input-Output and Interrupt ◼ Complete Computer Description ◼ Design of Basic Computer ◼ Design of Accumulator Logic 2 Basic Computer ◼ Two components of Basic Computer (BC) : ◼ A processor ◼ A memory ◼ 4096 word ▪ 4096 = 212 : require 12 bits to select a word in memory ◼ Each word : 16 bits long 3 Instructions ◼ Program ◼ A sequence of (machine) instructions ◼ (Machine) Instruction ◼ A group of bits that tell the computer to perform a specific operation (a sequence of microoperations) ◼ Steps : ◼ The instructions of a program, along with any needed data, are stored in memory ◼ The CPU reads the next instruction from memory ◼ It is placed in an Instruction Register (IR) ◼ Control circuitry in control unit then translates the instruction into the sequence of microoperations necessary to implement it 4 Instruction Format ◼ An instruction is often divided into two parts : ◼ opcode (Operation Code) : specify the operation for that instruction ◼ address : specify the registers and/or locations in memory to use for that operation ◼ In BC: ◼ Memory contains 4096 (= 212) words --> needs 12 bits to specify which memory address this instruction will use ◼ bit 15 of an instruction : specify addressing mode (0: direct addressing, 1: indirect addressing) ◼ A memory word (hence an instruction) is 16 bits long --> opcode is 3 bits 5 Address Modes ◼ Term: Effective Address (EA) ◼ The address that can be directly used without modification to access an operand for a computation-type instruction, or as the target address for a branch-type instruction ◼ The address field of an instruction represents either : ◼ Direct address : the address in memory of the data to use (the address of the operand) ◼ Indirect address : the address in memory of the address in memory of the data to use 6 Processor Registers – (1) ◼ A processor has many registers to hold instructions, addresses, data, etc ◼ A processor in BC has : ◼ Program Counter (PC) : hold the memory address of the next instruction to get ◼ The memory in BC has 4096 locations --> PC only needs 12 bits ◼ Address Register (AR) : to keep track of what locations in memory it is addressing (in direct or indirect addressing) ◼ 12 bits in BC ◼ Data Register (DR) : When an operand is found, it is placed in DR for the processor to use it as data for its operation ◼ 16 bits in BC 7 Processor Registers – (2) ◼ A processor in BC has (cont’) : ◼ Accumulator (AC) : a single general purpose register in BC ◼ Significance of a general purpose register : it can be referred to in instructions! -- e.g., load a memory content to AC, save data in AC to a memory location, … (16 bits in BC) ◼ Temporary Register (TR) : a scratch register to store intermediate results or other temporary data ◼ 16 bits in BC ◼ Input Register (INPR) : hold an 8 bit character gotten from an input device ◼ Output Register (OUTR) : hold an 8 bit character to be sent to an output device ◼ Note: BC uses a very simple model of IO operations : ◼ Input devices are considered to send 8 bits of character data to the processor ◼ The processor can send 8 bits of character data to output devices 8 BC Registers ◼ Registers in BC: ◼ List of BC Registers 9 Common Bus System – (1) 10 Common Bus System – (2) 11 Common Bus System – (3) ◼ Three control lines (S2, S1, S0) control which register the bus selects as its input ◼ Either one of the registers will have its load signal activated, or the memory will have its write signal activated ◼ Will determine where the data from the bus gets loaded ◼ Not a 16-bit register? ◼ From 12-bit registers (AR, PC) : 0’s loaded onto the bus in high order 4 bit positions ◼ To a 8-bit register (OUTR) : the data from the low order 8 bits on the bus 12 BC Instructions – (1) ◼ BC Instruction Format 13 BC Instructions – (2) 14 Instruction Set Completeness ◼ A computer should have a set of instructions so that ◼ the user can construct machine language programs to evaluate any functions that are known to be computable ◼ Instruction types ◼ Functional instructions ◼ arithmetic, logic, and shift instructions ◼ ADD, CMA, INC, CIR, CIL, AND, CLA ◼ Transfer instructions ◼ data transfers between the main memory and the processor registers ◼ LDA, STA ◼ Control instructions ◼ program sequencing and control ◼ BUN, BSA, ISZ ◼ Input/output instructions ◼ input and output ◼ INP, OUT 15 Control Unit ◼ Control Unit (CU) of a processor translates from machine instructions to the control signals for the microoperations that implement them ◼ Control units are implemented in one of two ways : ◼ Hardwired Control ◼ CU is made up of sequential and combinational circuits to generate the control signals ◼ Microprogrammed Control ◼ A control memory on the processor contains microoperations that activate the necessary control signals ◼ Hardwired implementation of BC --> this chapter ◼ Microprogrammed implementation of BC --> later 16 Timing and Control ◼ Control Unit of BC 17 Timing Signals ◼ Generated by 4-bit sequence counter and 4×16 decoder ◼ The sequence counter can be incremented or cleared ◼ Example: T0, T1, T2, T3, T4, T0, T1,... ◼ Assume: At time T4, SC is cleared to 0 if decoder output D3 is active D3T4: SC ← 0 18 Instruction Cycle ◼ In BC, a machine instruction is executed in the following cycle : 1. Fetch an instruction from memory 2. Decode the instruction 3. If the instruction has an indirect address, Read the effective address from memory 4. Execute the instruction ◼ After an instruction is executed, the cycle starts again at step 1, for the next instruction ◼ Note: Every different processor has its own (different) instruction cycle 19 Fetch and Decode ◼ Fetch and Decode: ◼ Initially PC is loaded by address of first instruction and SC is cleared ◼ After each clock pulse, SC is incremented by 1 20 Determine Type of Instruction 21 Register Reference Instructions ◼ Register Reference Instructions are identified when : ◼ D7 = 1, I = 0, r = D7I’T3 = 1 ◼ Register reference instruction is specified in lower 12 bits (B0~B11) of IR ◼ Execution starts with timing signal T3 ◼ Bi = IR(i), i = 0, 1, 2, …, 11 22 Memory Reference Instructions – (1) ◼ The effective address of the instruction is in AR and was placed there ◼ during timing signal T2 when I = 0, or ◼ during timing signal T3 when I = 1 ◼ Memory cycle is assumed to be short enough to complete in a CPU cycle ◼ The execution of MR instruction starts with T4 23 Memory Reference Instructions – (2) ◼ AND to AC ◼ D0T4: DR ← M[AR] Read operand ◼ D0T5: AC ← AC  DR, SC ← 0 AND with AC ◼ ADD to AC ◼ D1T4: DR ← M[AR] Read operand ◼ D1T5: AC ← AC + DR, E ← Cout, SC ← 0 Add to AC and store carry in E 24 Memory Reference Instructions – (3) ◼ LDA: Load to AC ◼ D2T4: DR ← M[AR] ◼ D2T5: AC ← DR, SC ← 0 ◼ STA: Store AC ◼ D3T4: M[AR] ← AC, SC ← 0 ◼ BUN: Branch Unconditionally D4T4: PC ← AR, SC ← 0 25 Memory Reference Instructions – (4) ◼ BSA: D5T4: M[AR] ← PC, AR ← AR + 1 D5T5: PC ← AR, SC ← 0 before execution phase 26 Memory Reference Instructions – (5) ◼ ISZ: Increment and Skip-if-Zero D6T4: DR ← M[AR] D6T5: DR ← DR + 1 D6T6: M[AR] ← DR, if (DR = 0) then (PC ← PC + 1), SC ← 0 27 Flowchart for Memory Reference Instructions 28 Input-Output and Interrupt Assume: A terminal with a keyboard and a printer ◼ Input-output configuration INPR Input register - 8 bits OUTR Output register - 8 bits FGI Input flag - 1 bit FGO Output flag - 1 bit IEN Interrupt enable - 1 bit ◼ The terminal sends and receives serial information ◼ The serial info from the keyboard is shifted into INPR ◼ The serial info for the printer is stored in the OUTR ◼ INPR and OUTR communicate with the terminal serially and with the AC in parallel. ◼ The flags are needed to synchronize the timing difference 29 between I/O device and the computer Program Controlled Data Transfer ◼ Initially, FGI = 0 This means that INPR register is ready to receive data from input device but did not receive any data yet (INPR is empty) ◼ Initially, FGO = 1 This means that OUTR register is ready to receive data from AC to be sent to the output device (OUTR is empty) 30 Program Controlled Data Transfer 31 Input-Output Instructions 32 Program-Controlled Input/Output ◼ Input LOOP, SKI (device number) //Skip as Data is being transferred to AC BUN LOOP // Stay in Loop INP (device number) // Input Characters to AC ◼ Output LDA DATA // Load Accumulator LOP, SKO (device number) // Skip as date will be transferred to O/P BUN LOP //Stay in Loop OUT (device number) // Output Characters from AC ◼ Program-controlled I/O ◼ - Continuous CPU involvement – I/O takes valuable CPU time ◼ - CPU slowed down to I/O speed ◼ + Simple ◼ + Least HW 33 Interrupt Initiated Input/Output ◼ Open communication only when some data has to be passed --> interrupt. ◼ The I/O interface, instead of the CPU, monitors the I/O device : ◼ When the interface finds that the I/O device is ready for data transfer, it generates an interrupt request to the CPU ◼ Upon detecting an interrupt, the CPU : ◼ stops momentarily the task it is doing, ◼ branches to the service routine to process the data transfer, and then ◼ returns to the task it was performing. ◼ IEN (Interrupt-enable flip-flop R) ◼ can be set and cleared by instructions ◼ when cleared, the computer cannot be interrupted 34 Flowchart for Interrupt Cycle ◼ The interrupt cycle is a HW implementation of a branch and save return address operation. ◼ At the beginning of the next instruction cycle, the instruction that is read from memory is in address 1. ◼ At memory address 1, the programmer must store a branch instruction that sends the control to an interrupt service routine ◼ The instruction that returns the control to the original program is "indirect BUN 0" 35 Register Transfer Operations in Interrupt Cycle 36 Register Transfer Operations in Interrupt Cycle ◼ Register Transfer Statements for Interrupt Cycle R ← 1 if IEN (FGI + FGO)T0′ T1′ T2′  T0′ T1′ T2′ (IEN)(FGI + FGO): R ← 1 ◼ The fetch and decode phases of the instruction cycle must be modified → Replace T0, T1, T2 with R'T0, R'T1, R'T2 ◼ The interrupt cycle : RT0: AR ← 0, TR ← PC RT1: M[AR] ← TR, PC ← 0 RT2: PC ← PC + 1, IEN ← 0, R ← 0, SC ← 0 37 Complete Description – Flowchart of Operations 38 Complete Description – Microoperations – (1) 39 Complete Description – Microoperations – (2) 40 Prob 5-3 ◼ The following control inputs are active in the bus system shown in the Figure. For each case, specify the register transfer that will be executed during the next clock transition. 41  Prob 5-3 (cont.) ◼ Answer: ◼ (a) Memory read to bus and load to IR: IR ← M[AR] ◼ (b) TR to bus and load to PC: PC ← TR ◼ (c) AC to bus, write to memory, and load to DR: DR ← AC, M[AR]← AC ◼ (d) Add DR (or INPR) to AC: AC ← AC + DR 42 BC Instructions 43 Prob 5-9 ◼ The content of AC in the basic computer is hexadecimal A937 and the initial value of E is 1. ◼ Determine the contents of AC, E, PC, AR, and IR in hexadecimal after the execution of the CLA instruction. ◼ Repeat 11 more times, starting from each one of the register-reference instructions. The initial value of PC is hexadecimal 021. 44 Prob 5-9 (cont.) ◼ Answer: AC E PC AR IR Initial A937 1 021 CLA 0000 1 022 800 7800 CLE A937 0 022 400 7400 CMA 56C8 1 022 200 7200 CME A937 0 022 100 7100 CIR D49B 1 022 080 7080 CIL 526F 1 022 040 7040 INC A938 1 022 020 7020 SPA A937 1 022 010 7010 SNA A937 1 023 008 7008 SZA A937 1 022 004 7004 SZE A937 1 022 002 7002 HLT A937 1 022 001 7001 45 Prob 5-12 ◼ The content of PC in the basic computer is 3AF (all numbers are in hexadecimal). ◼ The content of AC is 7EC3. The content of memory at address 3AF is 932E. ◼ The content of memory at address 32E is 09AC. ◼ The content of memory at address 9AC is 8B9F. a) What is the instruction that will be fetched and executed next? b) Show the binary operation that will be performed in the AC when the instruction is executed. c) Give the contents of registers PC, AR, DR, AC, and IR in hexadecimal and the values of E, I, and the sequence counter SC in binary at the end of the instruction cycle. 46 Prob 5-12 (cont.) Answer: Memory Address Operand ◼ (a) 9 = (1 0 0 1) => I = 1, (001-D1) for ADD 3AF 932E ADD 32E I 32E 09AC 9AC 8B9F ◼ (b) AC = 7EC3 (ADD) DR = 8B9F AC = 0A62 E=1 ◼ (c) PC = 3AF + 1 = 3B0 IR = 932E AR = 9AC E=1 DR = 8B9F I=1 AC = 0A62 SC = 0000 47 48 Prob 5-13 ◼ Assume that the first six memory-reference instructions in the basic computer listed in the Table are to be changed to the instructions specified in the following table. ◼ EA is the effective address that resides in AR during time T4. ◼ Assume that the adder and logic circuit can perform the exclusive-OR operation AC AC  DR. ◼ Assume further that the adder and logic circuit cannot perform subtraction directly. The subtraction must be done using the 2' s complement of the subtrahend by complementing and incrementing AC. ◼ Give the sequence of register transfer statements needed to execute each of the listed instructions starting from timing T4. ◼ Note that the value in AC should not change unless the instruction specifies a change in its content. You can use TR to store the content of AC temporary or you can exchange DR and AC (DR  AC, AC  DR). 49 Prob 5-13 (cont.) 50 Prob 5-13 (cont.) 51 Prob 5-13 (cont.) 52 Prob 5-13 (cont.) 53 Prob 5-13 (cont.) 54 Prob 5-13 (cont.) 55 Prob 5-13 (cont.) ! 56  Prob 5-16 ◼ A computer uses a memory of 65,536 words with eight bits in each word. It has the following registers: PC, AR, TR (16 bits each), and AC, DR, IR (eight bits each). A memory-reference instruction consists of three words: an 8-bit operation-code (one word) and a 16-bit address (in the next two words). All operands are eight bits. There is no indirect bit. 1. Draw a block diagram of the computer showing the memory and registers as in Fig. 5-3. (Do not use a common bus). 2. Draw a diagram showing the placement in memory of a typical three-word instruction and the corresponding 8-bit operand. 3. List the sequence of microoperations for fetching a memory reference instruction and then placing the operand in DR. Start from timing signal T0. 57  Prob 5-16 (cont.) a) 58  Prob 5-16 (cont.) b) 59  Prob 5-16 (cont.) c) T0: AR  M[PC], PC  PC + 1 T1: IR(0-7)  M[AR], PC  PC + 1 T2: IR(8-15)  M[AR], PC  PC + 1 T3: DR  M[AR] 60 Prob 5-17 ◼ A digital computer has a memory unit with a capacity of 16,384 words, 40 bits per word. ◼ The instruction code format consists of six bits for the operation part and 14 bits for the address part (no indirect mode bit). ◼ Two instructions are packed in one memory word and a 40-bit instruction register IR is available in the control unit. ◼ Formulate a procedure for fetching and executing instructions for this computer. 61 Prob 5-17 (cont.) ◼ Answer: ◼ 1. Read 40-bit double instruction from memory to IR and then increment PC. ◼ 2. Decode opcode 1. ◼ 3. Execute instruction 1 using address 1. ◼ 4. Decode opcode 2. ◼ 5. Execute instruction 2 using address 2. ◼ 6. Go back to step 1. 62 Prob 5-18: ◼ An output program resides in memory starting from address 2300. ◼ It is executed after the computer recognizes an inerrupt when FGO becomes a 1 (while lEN = 1). ◼ a. What instruction must be placed at address 1? ◼ b. What must be the last two instructions of the output program? ◼ Answer: ◼ a. BUN 2300 ◼ b. ION BUN 0 I (branch indirect to address 0) 63  Prob 5-19: ◼ The register transfer statements for a register R and the memory in a computer are as follows (the X’s are control functions that occur at random): ◼ X3’ X1 : R  M[AR] Read memory word into R ◼ X1’ X2 : R  AC Transfer AC to R ◼ X1’ X3 : M[AR]  R Write R to memory ◼ The memory has data inputs, data outputs, address inputs, and control inputs to read and write as in Fig. 2-12. ◼ 1) Draw the hardware implementation of R and the memory in block diagram form. ◼ 2) Show how the control functions X1 through X3 select the load control input of R, the select inputs of multiplexers that you include in the diagram, and the read and write inputs of the memory. 64 Prob 5-19 (cont.): 65 Design of BC ◼ HW Components of BC : ◼ A memory unit : 4096 x 16 ◼ Registers : AR, PC, DR, AC, IR, TR, OUTR, INPR, SC ◼ Flip-Flops (status) : I, S, E, R, IEN, FGI, FGO ◼ Decoders : a 3x8 opcode decoder, a 4x16 timing decoder ◼ Common bus : 16 bits ◼ Control logic gates ◼ Adder and Logic circuit: connected to AC ◼ Control Logic Gates ◼ Input controls of the nine registers ◼ read and write controls of memory ◼ set, clear, or complement controls of the flip-flops ◼ S2, S1, S0 controls to select a register for the bus ◼ AC and ‘adder and logic circuit’ 66 Complete Description – Microoperations – (1) 67 Complete Description – Microoperations – (2) 68 Control of Registers and Memory ◼ Address Register (AR) : ◼ Scan all of the register transfer statements that change the content of AR : 69 Control of Flags ◼ IEN: Interrupt Enable Flag pB7: IEN ← 1 (I/O Instruction) pB6: IEN ← 0 (I/O Instruction) RT2: IEN ← 0 (Interrupt) p = D7IT3 (Input/Output Instruction) J = pB7 + (pB6)’ + (RT2)’ K = (pB7)’ + pB6 + RT2 Given mutual exclusion J = pB7 K = pB6 + RT2 70 Control of Common Bus 71 Design of Accumulator Logic ◼ Circuits associated with AC : ◼ All the statements that change the content of AC:: 72 Control of AC Registers ◼ Gate structures for controlling the LD, INR, and CLR of AC 73 Adder and Logic Circuit ◼ One stage of Adder and Logic Circuit : 74 Prob 5-20: ◼ The operations to be performed with a flip-flop F (not used in the basic computer) are specified by the following register transfer statements: xT3: F  1 Set F to 1 yT1: F  0 Clear F to 0 zT2: F  F’ Complement F wT5: F  G Transfer value of G to F ◼ Otherwise, the content of F must not change. ◼ Draw the logic diagram showing the connections of the gates that form the control functions and the inputs of flip-flop F. ◼ Use a JK flip-flop and minimize the number of gates. 75 Prob 5-20: (cont.) ◼ Answer: ◼ JF = xT3 + zT2 + wT5G ◼ KF = yT1 + zT2 + wT5G’ 76 Complete Description – Microoperations – (1) 77 Complete Description – Microoperations – (2) 78 Prob 5-22: ◼ Derive the control gates for the write input of the memory in the basic computer. ◼ Answer: ◼ Write = D3T4 + D5T4 + D6T6 + RT1 ◼ (M[AR] ← xx) 79 Prob 5-23: ◼ Show the complete logic of the interrupt flip-flop R in the basic computer. ◼ Use a JK flip-flop and minimize the number of gates. ◼ Answer: ◼ (T0 + T1 + T2)' (IEN) (FGI + FGO) : R ← 1 ◼ RT2 : R ← 0 80