Module II
Central Processing Unit
Introduction
• CPU
• part of the computer that performs the bulk of data-processing operations
Fig: Major components of CPU.
General Register Organization
General Register Organization
• Memory locations are needed for storing
• pointers
• counters
• return addresses
• temporary results
• partial products during multiplication
• Time consuming
• More convenient and more efficient to store these intermediate
values in processor registers.
• Registers communicate with each other for
• direct data transfers and,
• while performing various micro operations.
Fig: Bus organization
for seven CPU registers
• Example:
• R1 R2 + R3
1. MUX A selector (SELA)
2 . MUX B selector (SELB)
3 . ALU operation selector (OPR)
4 . Decoder destination selector (SELD)
Control Word
• Binary selection inputs in the unit, and their combined value specifies a
control word
Table: Encoding of Register Selection Fields
Table: Encoding of ALU Operations
Example of Microoperations
• R1 R2 - R3
Examples of micro operations of CPU
• Efficient way to generate control words
• Store in a memory unit – control memory
• Microprogrammed control
Stack Organization
Stack Organization
• Stack
• Stores information - item stored last is the first item retrieved
• LIFO
• Memory unit and an address register
• Stack pointer (SP) - always points at the top item in the stack.
• Operations
• Push - operation of insertion
• Pop - operation of deletion
• Incrementing or decrementing the stack pointer register
Register Stack
• Stack
• a portion of a large memory or
• a collection of a finite number of memory words or registers
Fig: Block diagram of a 64-word stack
• Push operation
• SP SP + 1
• Increment stack pointer
• M [SP] DR
• Write item on top of the stack
• If (SP = 0) then (FULL 1)
• Check if stack is full
• EMTY 0
• Mark the stack not empty
• First item - at address 1
• Last item - at address 0.
• Pop operation
• DR M [SP]
• Read item from the top of stack
• SP SP - 1
• Decrement stack pointer
• If (SP = 0) then (EMTY 1)
• Check if stack is empty
• FULL 0
• Mark the stack not full
• Erroneous operation
• pushed when FULL = 1 or
• popped when EMTY = 1
Memory Stack
• A stand-alone unit or
• implemented in a random-access
memory attached to a CPU
• PC - fetch phase to read an instruction.
• AR – execute phase to read an operand.
• SP - push or pop items into or from the stack
Fig: Computer memory with Program, Data and Stack segments
• Stack communicate - data register DR
• Push operation:
• SP SP - 1
• M[SP] DR
• Pop operation:
• DR M[SP]
• SP SP + 1
• No provisions available for stack limit checks
• Stack limits checked – two processor registers
• One hold the upper limit (3000),
• Other hold the lower limit (4001).
• Push operation
• SP compared with the upper-limit register
• Pop operation
• SP compared with the lower-limit register.
• Two microoperations needed for either the push or pop
• (1) an access to memory through SP, and
• (2) updating SP.
• SP initial value.
• bottom address of the stack
• Advantage of a memory stack
• CPU can refer to it without specifying an address
Reverse Polish Notation
• Stack organization very effective for evaluating arithmetic expressions
• Common arithmetic expressions
• Infix notation
• Operator between the operands
• Ex: A * B + C * D
• Prefix notation (Polish notation)
• Operator before operands
• Postfix notation (Reverse Polish notation (RPN))
• Operator after operands
• A+B Infix notation
• + AB Prefix or Polish notation
• AB + Postfix or reverse Polish notation
• Reverse Polish notation suitable for stack manipulation
• Ex: A * B + C * D
• Reverse Polish notation AB * CD * +
• Evaluation
• Conversion from infix to reverse Polish notation
• must take into consideration the operational hierarchy
• Ex: (A + B) * [C * (D + E) + f]
• Reverse Polish notation
• AB + DE + C * F + *
Evaluation of Arithmetic Expressions
• Evaluating arithmetic expressions
• Most efficient way
• Reverse Polish notation, combined with a stack arrangement of registers
• First convert arithmetic expression into its equivalent reverse Polish notation
• Operands are pushed into the stack in the order in which they appear.
• Microoperations executed
• (1) the two topmost operands in the stack are used for the operation,
• (2) the stack is popped and the result of the operation replaces the lower operand
• Ex: (3 * 4) + (5 * 6)
• Reverse Polish notation: 34 * 56 * +
Fig: Stack operations to evaluate 3 * 4 + 5 * 6
Instruction Formats
Instruction Formats
• Control unit interpret each instruction code
• Provide the necessary control functions needed to process the instruction
• Instruction formats:
1. Operation code field - operation to be performed.
2. Address field - a memory address or a processor register.
3. Mode field – the way the operand or the effective address is determined
• Operands in memory or processor registers
• Memory - memory address
• Processor registers - register address
• k bits that defines one of 2k registers
• Instructions different lengths with varying number of addresses
• Number of address fields in the instruction format
• depends on the internal organization of its registers.
• Three types of CPU organizations:
1. Single accumulator organization.
2. General register organization.
3. Stack organization.
1. Single accumulator organization
• ADD X
• AC AC + M [X]
2. General register organization
• Three register address fields
• ADD R1,R2,R3
• R1 R2 + R3
• Two register address fields
• ADD R1,R2
• R1 R1 + R2
• Processor register or a memory word.
• ADD R1,X
• R1 R1 + M[X]
3. Stack organization
• PUSH and POP instructions with an address field
• PUSH X
• Operation-type instructions do not need an address field
• ADD
• Evaluate X = (A + B) * (C + D)
• Three-Address Instructions
• ADD R1,A,B R1 M[A]+M[B]
• ADD R2,C,D R2 M[C]+M[D]
• MUL X,R1,R2 M[ X ] R1 * R2
• Advantage
• Short programs
• Disadvantage
• Binary-coded instructions require too many bits to specify three addresses
• Two-Address Instructions
• MOV R1,A R1 M[A]
• ADD R1,B R1 R1 + M [ B ]
• MOV R2,C R2 M[C]
• ADD R2,D R2 R2 + M [ D ]
• MUL R1,R2 R1 R1 * R 2
• MOV X,R1 M[ X ] R1
• One-Address Instructions
• LOAD A AC M[A]
• ADD B AC AC + M [ B ]
• STORE T M[T] AC
• LOAD C AC M[C]
• ADD D AC AC + M [ D ]
• MUL T AC AC * M [ T ]
• STORE X M[ X ] AC
• Zero-Address Instructions
• PUSH A TOS A
• PUSH B TOS B
• ADD TOS (A+B)
• PUSH C TOS C
• PUSH D TOS D
• ADD TOS (C+D)
• MUL TOS (C+D) *(A+B)
• POP X M[X] TOS
Addressing Modes
Addressing Modes
• Way the operands are chosen during program execution dependent on the
addressing mode of the instruction.
• Addressing mode specifies a rule for interpreting or modifying the address
field of the instruction before the operand is actually referenced.
• Purpose of addressing mode techniques
1. To give programming versatility -- pointers to memory, counters for loop control,
indexing of data, and program relocation.
2. To reduce the number of bits in the addressing field of the instruction.
• Advantages
• flexibility for writing programs
• more efficient with respect to the number of instructions
• execution time
• Instruction cycle - three phases:
1. Fetch the instruction from memory.
2. Decode the instruction.
3. Execute the instruction.
Fig: Instruction format with mode field.
• Addressing modes modify the address field of the instruction
Implied Mode:
• Operands specified implicitly in the definition of the instruction
• Ex: "complement accumulator“ CMA
• All register reference instructions that use an accumulator
• Zero-address instructions - stack
Immediate Mode:
• Operand specified in the instruction itself
• Operand field
Register Mode:
• Operands are in registers
• k-bit field specify any one of 2k registers
Register Indirect Mode:
• Instruction specifies a register whose contents give the address of the
operand in memory.
• Selected register contains the address not the operand
• Memory address of the operand is placed in the processor register in a
previous instruction
• Advantage
• Address field of the instruction uses fewer bits
Autoincrement or Autodecrement Mode
• Similar to the register indirect mode
• Register is incremented or decremented after its value is used to
access memory.
• Necessary -- register refers to a table of data
Direct Address Mode:
• Effective address is the address part of the instruction
• Operand in memory and its address directly given in the address field
of the instruction.
• Branch-type instruction
• address field specifies the actual branch address.
Indirect Address Mode:
• Address field of the instruction gives the address where the effective
address is stored in memory
• Control fetches the instruction from memory
• Uses its address part to access memory to read the effective address.
• Some addressing modes
• address field of the instruction added with a register in the CPU.
• Effective address = address part of instruction + content of CPU register
Relative Address Mode:
• Content of the program counter added to the address part of the instruction
• Ex:
• PC = 825
• address part of the instruction = 24
• instruction at location 825 fetched
• PC incremented
• Effective address 826 + 24 = 850
• Used with branch-type instructions
• when the branch address is in the area surrounding the instruction word itself
• Results in a shorter address field in the instruction format
• Relative address can be specified with a smaller number of bits
Indexed Addressing Mode
• Content of index register added to the address part of the instruction
• Index register -- a special register that contains an index value
• Address field of the instruction defines the beginning address of a data
array
• Any operand in the array can be accessed with the same instruction if
index register contains the correct index value
Base Register Addressing Mode:
• Content of a base register added to the address part of the instruction
• Base register hold a base address
• Address field of the instruction -- a displacement relative to this base
address
• Adv:-
• facilitate the relocation of programs in memory
Numerical Example
Program Control
Program Control
• Program Counter
• Instructions are fetched from consecutive memory locations and executed.
• Program control type of instruction
• Change the program counter
• Cause the flow of control to be altered
• specify conditions for altering the content of the program counter
Program Control Instructions
• BR ADR
• Branch and jump instructions
• Conditional or unconditional
• Skip instruction
• zero-address instruction
• Increment program counter
• Call and return instructions
• Used with subroutines
• Compare and test instructions
• do not change the program sequence directly
• Used for setting conditions
• Compare
• subtraction between two operands
• Result not retained.
• status bits are set - carry bit, the sign bit, a zero indication, and an overflow condition
• Test instruction
• logical AND of two operands
• Result not retained
• Updates status bits
Status Bit Conditions
• Status Register
• Status bits
• condition-code bits or
• flag bits
• Bits are set or cleared by the operation performed in the ALU
• V = 1 if the output is greater than + 127 or less than - 128
Conditional Branch Instructions
• Relations between unsigned numbers
• Higher and lower
• Signed numbers
• Greater and less than
• Largest unsigned number in 8 bits is 255
• Ex: Let A = 11110000 and B = 00010100
• 240 - 20 = 220
• C -1 and Z - 0
• BHI, BHE and BNE - cause a branch
• signed numbers --- -128 to +127
• Let A = 11110000 and B = 00010100
• A is -16 (11110000 is the 2's complement of 00010000)
• Subtraction (- 16) - ( + 20) = -36
• Binary result 11011 100 (the 2' s complement of 001001 00)
• S = 1 (negative) and Z = 0
• BLT, BLE and BNE
Subroutine Call and Return
• Subroutine
• A self-contained sequence of instructions that performs a given computational task
• Subroutine call
• a branch is executed to the beginning of the subroutine
• After execution, a branch is made back to the main program
• Call subroutine instruction - an operation code and an address to the beginning of
the subroutine
• Instruction executed by performing two operations:
• (1) the address of the next instruction in the program counter stored in a temporary
location
• (2) control is transferred to the beginning of the subroutine
• Return from subroutine,
• transfers the return address from the temporary location into the program counter
• Temporary location
• first memory location of the subroutine
• in a fixed location in memory
• in a processor register
• in a memory stack
• Efficient way
• store the return address in a memory stack.
• When a succession of subroutines is called, the sequential return addresses can be
pushed into the stack.
• Return from subroutine - top of the stack transferred to the program counter
• Subroutine call microoperations:
• Return from subroutine
• Recursive subroutine
• If only one register or memory location -- destroys the previous return address
• stack -- each return address can be pushed into the stack without destroying any
previous values
Program Interrupt
• Handle a variety of problems that arise out of normal program sequence
• External or internal generated request
• Transfer program control from currently running program to another service program
• Interrupt procedure vs. subroutine call
• (1) Interrupt --- initiated by an internal or external signal rather than from the execution
of an instruction
• (2) Address of the interrupt service program --- determined by the hardware rather than
from the address field of an instruction
• (3) Interrupt --- stores the state of the CPU rather than storing only the program
counter
• After an interrupt and the service routine execution
• CPU must return to exactly the same state that it was when the interrupt occurred.
• State of the CPU
• 1. The content of the program counter
• 2. The content of all processor registers
• 3. The content of certain status conditions
• Program status word or PSW
• Collection of all status bit conditions in the CPU
• Stored in a separate hardware register
• Includes
• status bits from the last ALU operation
• interrupts that are allowed to occur
• CPU in supervisor or user mode.
• Supervisor or system mode
• executing a program that is part of the operating system
• User mode
• executing user programs
• Responding to an interrupt
• Store only the program counter
• Service program include instructions to store status and register content
• Store both program counter and all status and register content in response to an
interrupt
• Two sets of processor registers one for each CPU mode
• Not necessary to store the contents of processor registers
• Hardware procedure for processing an interrupt
• similar to the execution of a subroutine call instruction
• CPU state - a memory stack
• Beginning address of the service routine – to PC
• Beginning address --- determined by the hardware
• Some assign one memory location for all interrupts
• service routine determine the interrupt and service it
• Separate memory location for each possible interrupt
• CPU does not respond to an interrupt until the end of an instruction
execution.
• Before going to the next fetch phase, checks for any interrupt signals
• Last instruction in the service program is a return from interrupt instruction
• Stack popped to retrieve the old PSW and the return address.
• PSW transferred to the status register
• Return address to the program counter
Types of Interrupts
• Three types:
• 1. External interrupts
• 2. Internal interrupts
• 3. Software interrupts
• External interrupts
• External sources
• Input/output (l/0) devices – finished transfer of data
• circuit monitoring the power supply – power failure
• complete state of the CPU into a nondestructive memory
• Internal interrupts or traps
• illegal or erroneous use of an instruction or data
• register overflow
• attempt to divide by zero
• an invalid operation code
• stack overflow
• protection violation
• Difference between internal and external interrupts
• Internal interrupt
• initiated by exceptional condition in the program
• Synchronous with the program
• Program is rerun - internal interrupts will occur in the same place each time.
• External interrupt
• by an external event
• Asynchronous
• Program is rerun - depend on external conditions that are independent of the program being
executed at the time
• External and internal interrupts are initiated from signals that occur in the
hardware of the CPU
• Software interrupt
• Initiated by executing an instruction.
• Special call instruction that behaves like an interrupt rather than a subroutine call
• Initiate an interrupt procedure
• most common use of software interrupt -- supervisor call instruction
• switching from a CPU user mode to the supervisor mode
• User pgm - run in the user mode.
• When an input or output transfer is required,
• supervisor mode is requested by means of a supervisor call instruction.
• causes a software interrupt
• stores the old CPU state and brings in a new PSW that belongs to the supervisor
mode.
• pass information to the operating system