Computer Architecture Chapters 3 to 5 Reviewer

PROGRAM EXECUTION IS CARRIED OUT AS FOLLOWS:

1. The CPU transfers instruction and when necessary their input data (operands) from the main memory to registers in the CPU.

2. The CPU executes the instruction in their stored sequence except when the execution sequence is explicitly altered by a branch instruction.

3. When necessary, the CPU transfers output data (results) from the CPU registers to main memory.

CPU-IO DEVICES COMMUNICATION APPROACHES:

1. Memory-mapped IO - this approach requires that memory locations and IO ports share the same set of addresses, so an address bit pattern that is assigned to memory cannot also be assigned to an IO port, and vice versa.[cite: 33] 2. IO-mapped IO - IO instructions are distinct from memory to which IO ports, not memory locations, respond.[cite: 33]

PROGRAMS EXECUTED BY A GENERAL-PURPOSE COMPUTER:

1. User Programs - A user or application program handles a specific application, such as word processing, of interest to the computer's users.[cite: 33] 2. Supervisor Programs - manages various routines aspects of the computer system on behalf of its users. It is typically part of the computer's operating system.[cite: 33]

ALL INSTRUCTIONS REQUIRE TWO MAJOR STEPS:

1. A fetch step during which a new instruction is read from the external memory M.

2. An execute step during which the operations specified by the instructions are executed.

TWO ESSENTIAL MEMORY-ADDRESSING INSTRUCTIONS ARE:

1. Load - AC := M(adr)[cite: 33] 2. Store - M(adr) := AC[cite: 33]

MOST RECENT CPUS CONTAIN THE FOLLOWING EXTENSIONS WHICH SIGNIFICANTLY IMPROVE THEIR PERFORMANCE AND EASE OF PROGRAMMING.

1. Multipurpose register set for storing data and addresses - replaces the accumulator AC and the auxiliary register DR and AR of our basic CPU. The set of general registers is now usually referred to as register files.

2. Additional data, instruction, and addresses types - most CPUs have instructions to handle data and addresses with several different word sizes and formats. Call and return instructions also simplify program design.

3. Register to indicate computation status - A status register indicates infrequent or exceptional conditions resulting from the instruction execution. It also indicates the user and supervisor states.

4. Program control stack - various special registers and instructions facilitate the transfer control among programs due to procedure calling or external interrupts. A CPU address register called a sack pointer automatically keeps track of the stack's entry point.

TWO MAIN NUMBER FORMATS:

1. Fixed-Point - It takes the form babBbc…bK where each bi is 0 or 1 and a binary point is present in some fixed but implicit position. This allows limited range of values and have relatively simple hardware requirements.

2. Floating-Point - it is consist of a pair of fixed-point numbers M,E which denote the number M x BE, where B is a predetermined base. This allow a much larger range of values but require either a costly processing hardware or lengthy software implementation.[cite: 33]

TWO BASIC BYTE STORAGE METHODS:

1. Big endian - the most significant byte of a word is assigned to the lowest address and the least significant byte is assigned to the highest address.

2. Little-endian - the lowest address is assigned to the least significant byte and the highest address is assigned to the most significant byte.

ADVANTAGES OF TAGS:

1. Determine the type of operand

2. Tag inspection permits the hardware to check for software errors, such as an attempt to add operands whose types are incompatible.

DISADVANTAGES OF TAGS:

1. Increase the memory size

2. Add to the system hardware costs without increasing computing performance.

IN SELECTING A NUMBER REPRESENTATION TO BE USED IN A COMPUTER, THE FOLLOWING FACTORS SHOULD BE TAKEN INTO ACCOUNT:

1. The number types to be represented; for example, integers or real numbers

2. The range of values (number magnitudes) likely to be encountered

3. The precision of the numbers, which refers to the maximum accuracy of the representation

4. The cost of the hardware required to store and process the numbers.

The primary advantage of the complement codes is that

subtraction can be performed by logical complementation and addition only.

ADVANTAGE OF THE EXCESS-THREE CODE

1. It may be processed using the same logic used for binary codes.

ADVANTAGES OF DECIMAL CODES:

1. Ease of conversion between the internal computer representation that allows only symbols 0, 1

2. External representation using the 10 decimal symbols 0,1,2…9.

DISADVANTAGES OF DECIMAL CODES:

1. They use more bits to represent a number than the binary codes. It requires more memory space.[cite: 33] 2. The circuity required to perform arithmetic using decimal operands is more complex than the needed for binary arithmetic.[cite: 33]

THE REPRESENTATION OF ZERO POSES SOME SPECIAL PROBLEM:

1. The mantissa must, of course, be zero, but the exponent can have any value, since 0 x BE = 0 for all values of E.

2. The desirability of representing zero by a sequence of 0-bits only.

RISC formats

serve to reduce both program length and what has been called the semantic gap between the user and the computer languages.

COMPLEX INSTRUCTIONS LEAD TO SEVERAL DIFFICULTIES, WHICH RISCS WITH THEIR SMALLER AND STREAMLINED INSTRUCTION SETS ATTEMPT TO MINIMIZE

1. The many instruction types and formats of CISC complicate the program control unit that decodes instruction op codes and issues the control signals that govern their execution.[cite: 33] 2. Fast, single-cycle instruction execution is harder to achieve with a complex instruction set, and it is more difficult for a compiler to optimize object-code performance.[cite: 33]

The purpose of an address field is to

point to the current value V(X) of some operand X used by an instruction.

THE ADDRESSING MODE OF X AFFECTS THE FOLLOWING ISSUES:

1. The speed with which V(X) can be accessed by the CPU[cite: 33] 2. The ease with which V(X) can be specified and altered[cite: 33]

MAIN DRAWBACK OF RELATIVE ADDRESSING:

Are the extra logic circuits and processing time needed to compute addresses.

THE REQUIREMENTS TO BE SATISFIED BY AN INSTRUCTION SET CAN BE STATED IN THE FOLLOWING GENERAL, BUT RATHER IMPRECISE, TERMS:

1. It should be complete in the sense that we should be able to construct a machine-language program to evaluate any function that is computable using a reasonable amount of memory space.

2. It should be efficient in that frequently required functions can be performed rapidly using relatively few instructions.

3. It should be regular in that the instruction set should contain expected opcodes and addressing modes

4. To reduce both hardware and software design costs, the instructions may be required to be compatible with those of existing machine.

Instructions are conveniently divided into following five types:

1. Data transfer instructions - which copy information from one location to another either in the processor's internal register set or in the external main memory.

2. Arithmetic instructions - which perform operations on numerical data.

3. Logical instruction - which include Boolean and other nonnumerical operations.

4. Program-control instructions - such as branch instructions, which change the sequence in which programs are executed.

5. Input-output (IO) instructions, which cause information to be transferred between the processor or its main memory and external IO devices.

THE MAJOR ATTRIBUTES OF RISCS

1. Relatively few instructions types and addressing modes

2. Fixed and easily decoded instruction formats

3. Fast, single-cycle instruction execution

4. Hardwired rather than microprogrammed control

5. Memory access limited mainly to load and store instructions

6. Use of compilers to optimize object-code performance.

INSTRUCTION CAN BE GROUPED INTO SEVERAL MAJOR TYPES:

1. Data Transfer - load, store, move register and input-output instructions[cite: 33] 2. Data Processing - arithmetic and logical instructions[cite: 33] 3. Program Control - conditional and unconditional branches[cite: 33]

TWO USEFUL TOOLS FOR SIMPLIFYING PROGRAM DESIGN BY ALLOWING GROUP OF INSTRUCTIONS TO BE TREATED AS SINGLE ENTITIES:

1. Macros- it is defined by placing a portion of assembly-language code between appropriate directives.

2. Subroutines - is also a sequence of instructions that can invoked by name, much like a single (macro) instructions. Unlike a macro, a subroutine definition is assembled into object code (CALL, JMP and RET)

EACH OPERAND SPECIFICATION IS DIVIDED INTO TWO PARTS:

1. An address field that points to the location of the first word of the operand

2. A length field L that indicates the number of words in the operand.

HIGH LEVEL VIEW OF A SERIAL ADDER THAT HAS D F/F AS THE CARRY STORE. ONE SUM BIT AND CARRY IS GENERATED PER CLOCK CYCLE.

1. Parallel Adders - in one clock cycle add all bits of two n-bit numbers as well as an external carry-in signal.

2. Ripple-carry adder - type of parallel adder. connecting full adders one full adders to generate 1 on its carry signal.

Subtracters

Subtraction is relatively simple with two's complement code because negation is very easy to implement. Adding -X to Y is equivalent to subtracting X from Y, so the ability to add negative numbers implies the ability to do subtraction.

Overflow

When the result of an arithmetic operation exceeds the standard word size n, overflow occurs.[cite: 33]

Carry-lookahead adders

A high-speed adder Compute the input carry needed by stage /directly from carry-like signals obtained from all the preceding stages.[cite: 33]

TWO AUXILIARY SIGNALS FOR CARRY-LOOKAHEAD ADDER

1. Generate[cite: 33] 2. Propagate[cite: 33]

Multiplication

usually implemented by some form of addition.

TWO MULTIPLICATION ALGORITHMS FOR TWOS COMPLEMENT NUMBERS

1. Robertson's Algorithm - will perform multiplication depending on the case occur.[cite: 33] 2. Booth's Algorithm - treats positive and negative operands uniformly, no special actions are required for negative numbers.[cite: 33]

Combinational array multiplier

can multiply large scale of numbers[cite: 33]

SEVERAL DIVISION DIFFICULTIES

1. Quotient overflow - too large to be placed for the answer[cite: 33] 2. Divided by zero error - when a number is divided to zero[cite: 33]

Division by repeated multiplication

division is performed efficiently and low cost.

TO SIMPLIFY THE DISCUSSION, WE MAKE THE FOLLOWING REALISTIC ASSUMPTIONS:

1. XM is an nM-bit binary (twos-complement or sign magnitude) fraction.

2. XE is an ne-bit integer in excess-2nE-1 code, implying an exponent bias of 2nE-1.

3. B = 2

FLOATING-POINT ADDITION AND SUBTRACTION HAVE THREE MAIN STEPS:

1. Compute YE-Xe a fixed-point subtraction.

2. Shift XM by YE- XE places to the right to form XM2XE-YE

3. Compute XM2XE-YE + YM a fixed-point addition or subtraction.

SEVERAL MINOR PROBLEMS ARE ASSOCIATED WITH EXPONENT BIASING

1. If biased exponent are added or subtracted using fixed-point arithmetic in the course of a floating-point calculation, the resulting exponent is doublly biased and must be corrected by subtracting the bias.

2. Another problem arises from the all-0 representation usually required of zero. If X x Y is computed as (XM x YM) x 2XE+ YE and either XM or YM is zero, the resulting product has an all 0-mantissa but may not have an all-0 exponent.

3. Overflow and Underflow - A floating point operation causes overflow if the result is too large or too small to be represented. However, the exponent overflows or underflows, an error signal indicating floating-point overflow or underflow is generated.

4. Guard Bits - to preserve accuracy during floating point calculations, one or more extra bits called guard bits are temporarily attached to the right end of the mantissa.

A COPROCESSOR INSTRUCTION TYPICALLY CONTAINS THE FOLLOWING THREE FIELDS:

1. An opcode Fo that distinguishes coprocessor instructions from other CPU instructions

2. The address Fi of the particular coprocessor to be used if several coprocessors are allowed

3. The type F2 of the particular operation to be executed by the coprocessor.

Drawback of Coprocessor

Unlike the CPU, it does not know the contents of the registers defining the current memory addressing mode.

Pipelining

is a general technique for increasing processor throughput without requiring large amounts of extra hardware. It is applied to the design of the complex datapath units such as multipliers and floating-point adders It is also used to improve the overall throughput of an instruction set processor.

Stages or segments

a pipeline processor consist of a sequence of m data-processing circuits, which collectively perform a single operation on a stream of data operands passing through them.

Advantage of pipeline

An m-stage pipeline can simultaneously process up to m independent sets of data operands[cite: 33]

T

pipeline's clock period

MT

Delay or latency of the pipeline[cite: 33]

1/T

Pipeline's throughput[cite: 33]

Latency For a non-pipelined processor:

NmT[cite: 33]

Latency For a pipelined processor:

[m + (N - 1)]T Where: N = number of Tasks, m = number of stages, T = pipeline's clock period[cite: 33]

ADDITION OF TWO NORMALIZED FLOATING-POINT NUMBERS X AND Y CAN BE IMPLEMENTED USING FOUR-STEP SEQUENCE:

1. Compare the exponents[cite: 33] 2. Align the mantissas[cite: 33] 3. Add the mantissas[cite: 33] 4. Normalize the result[cite: 33]

Feedback:

• The usefulness of a pipeline processor can sometimes be enhanced by including feedback paths from a stage output to the primary inputs of the pipeline.[cite: 33] - It enables the result computed by certain stages to be used in a subsequent calculation by the pipeline[cite: 33]

THE MAJOR CHARACTERISTIC OF A SYSTOLIC ARRAY CAN BE DEDUCED FROM THE PRECEDING EXAMPLE

1. It provides a high degree of parallelism by processing many sets of operands concurrently.

2. Partially processed data sets flow synchronously through the array in pipeline fashion, but possibly in several directions at once, with complete results eventually appearing at the array boundary.

3. The use of uniform cells and interconnection simplifies implementation.

4. The control of the array is simple, since all cells perform the same operations: however care must be taken to supply the data in the correct sequences for the operation being implemented.

5. If the X and Y matrices are generated in real time, it is unnecessary to store them before computing X x Y, as with most sequential or parallel processing techniques.

6. The amount of hardware needed to implement a systolic array.

SEPARATE A DIGITAL SYSTEM INTO TWO PARTS:

1. Datapath - is a network of functional and storage units capable of performing certain (micro) operations on data words

2. Control Unit - selects the functions to be performed at specific times and route the data through appropriate parts of the Datapath unit. Logically reconfigures the datapath to implement some specified instructions or program.

Multicycle operations

Single-cycle execution is a central goal of RISC design.

Single precision floating point

4 bytes[cite: 33]

Double-precision floating point

8 bytes[cite: 33]

Microprogram

an associated set of microinstructions in digital computers[cite: 33]

What are Microinstructions?

control the CPU at a very fundamental level of hardware circuitry

IMPLEMENTATION METHOD Two general approaches control unit design have evolved:

1. Hardwired - views the controller as a sequential logic circuit or fsm that generates specific sequences of control signals in response to externally supplied instructions. - designed with the usual goals of minimizing the number of components used and maximizing the speed of operation

2. Microprogrammed control unit - built around a storage unit called control memory, where all the control signals are stored in a program-like format resembling

Control Memory

stores set of microprograms designed to implement or emulate the behavior of the given instruction set.[cite: 33]

Microprogramming

makes control unit design more systematic by organizing signals into formatted words (microinstructions).

ON THE NEGATIVE SIDE, MICROPROGRAMMED CONTROL UNIT:

1. More costly to manufacture than hardwired due to the presence of control memory and its access circuitry.

2. Microprogrammed also tend to be slower because of the extra time required to fetch microinstructions from control memory. Hardwired control units use RISC, the reason it has fast instruction set.

DESIGN METHODS

1. Classical Method - attempts to minimize the amount of hardware by using only flip-flops to realize a P-state circuit[cite: 33] 2. One-hot Method - simplifies CU design and debugging[cite: 33]

STATE TABLES

1. Moore machine - output signal values depend on the current state an independent of the input[cite: 33] 2. Mealy machine - contrast with Moore[cite: 33]

Classical Method

1. Construct a P-Row state table that defines the desired input-output behavior

2. Select the minimum number p of D-type flip-flop and assign a p-bit binary code to each state

3. Design a combinational circuit C that generates the primary output signals {zi} and secondary outputs {Di} that must be applied to the flip-flops[cite: 33] Defined states: S0 = 0 0 - Begin, S1 = 0 1 - Swap, S2 = 1 0 - Sub, S3 = 1 1 - End

One-hot method

Binary state assignment always contains a single 1 - the "hot" bit - while all the remaining bits are 0.

1. Construct a P-row state table that defines the desired input-output behavior

2. Associate a separate D-type flip-flop Di with each state Si and assign the P-bit onehot binary code to each state.

3. Design a combinational circuit that generates the primary and secondary output signals {Di} and {zk} respectively. Di+ is defined by the logic equation.

Defined states: S0 = 0 0 0 1 - Begin, S1 = 0 0 1 0 - Swap, S2 = 0 1 0 0 - Sub, S3 = 1 0 0 0 - End

CPU Control Unit

DPU - datapath unit designed to execute the set of 10 basic single-address[cite: 33] PCU - program control unit is responsible for managing the control signals linking PCU to the DPU, as well as the control signals between the CPU and external memory M.[cite: 33]

RISC processors

are usually designed so that all instruction execution times are equalized to one CPU clock period Tc in length, making the cycles associated with the registertransfer operations into subcycles of Tc.[cite: 33]

Microprogramming is

a method of control-unit design in which the control signal selection and sequencing information is stored in a ROM or RAM called control memory, CM.

Microinstructions

activates the control signals at any time which is fetched from CM in much the same way an instruction is fetched from main memory.

Microprogram

is a set of related microinstructions.[cite: 33]

Emulator

is the set of microprograms that interpret a particular instruction set or machine language.[cite: 33]

Microassembler

is necessary to translate microprograms into executable programs that can be stored in the control memory.[cite: 33]

MICROINSTRUCTION'S TWO PARTS:

1. Control fields that specify the control signals to be activated

2. Address fields that contains the address in the CM of the next microinstruction to be executed.

CMAR

control memory address register[cite: 33]

MICROINSTRUCTION LENGTH IS DETERMINED BY THREE FACTORS:

1. The maximum number of simultaneous microoperations that must be specified, that is, the degree of parallelism required at the microoperation level

2. The way in which the control information is represented or encoded.

3. The way in which the next microinstruction address is specified.

WCM

Writable control memory allows us to change a processor's instruction set by changing the microprograms that interpret the instruction set.

Dynamically microprogrammable

if the control memory contents can be altered under program control, e.g. WCM[cite: 33]

Parallelism in microinstructions

Microinstruction formats take advantage of the fact that, at the microprogramming level, many operations can be performed in parallel.[cite: 33]

HORIZONTAL MICROINSTRUCTIONS:

1. Long formats

2. Ability to express a high degree of parallelism

3. Little encoding of the control information; Allows no encoding of control information. Specifies many microoperation.

VERTICAL MICROINSTRUCTIONS:

1. Short formats[cite: 33] 2. Limited ability to express parallel microoperations[cite: 33] 3. considerable encoding of the control information[cite: 33] Allows encoding of control information[cite: 33] Specify only one microoperation (no Parallelism)[cite: 33] Vertical instructions are broadly similar to RISC instructions, both in the small amount of parallelism they specify and in their single-cycle execution style.[cite: 33]

Microinstruction addressing

uPC, microprogram counter is the primary source of microinstruction address and can also be used as CMAR[cite: 33]

Microoperation timing

A single clock signal synchronizes the control signals, and its period can be the same as the microinstruction cycle period; this mode of control has been termed monophase.

Design of a typical microprogrammed control unit using the microinstruction format:

1. A condition-select field specifies the external condition to be tested in the case of conditional branch microinstructions

2. An address field contains the next-address field to be used when a branch condition is satisfied. A microprogram counter uPC provides the next microinstruction address when no branching is needed.

3. The rest of the microinstruction specifies in encoded or unencoded format the control signals that are activated to perform the desired microoperations.

THIS OPERATION CAN BE PERFORMED IN SEVERAL PHASES; THE FOLLOWING FOUR-PHASE INTERPRETATION IS REPRESENTATIVE:

1. Fetch the next microinstruction from the control memory CM.[cite: 33] 2. Transfer the contents of registers R1 and R2 to the inputs of the f.[cite: 33] 3. Store the result generated by the funit in a temporary register or latch L.[cite: 33] 4. Transfer the contents of L to the destination register R.[cite: 33]

WE USE THE MICROINSTRUCTION WHICH HAS THREE PARTS ARRANGED AS FOLLOWS:

1. A condition-selct field specifies the external condition to be tested in the case of conditional branch microinstruction.

2. An address field contains the next-address field to be used when a branch condition is satisfied.

3. The rest of the microinstruction specifies in encoded or unencoded format the control signals that are activated to perform the desired microoperations.

Instruction Pipeline

is a multifunction, reconfigurable pipeline designed to speed up a computer's performance by efficiently overlapping the processing of instructions.[cite: 33]

SIMPLEST INSTRUCTION PIPELINE:

1. Fetch Stage S1: uPC - microprogram counter, source of microinstructions; buffer register CM - control memory, stores microinstructions[cite: 33] 2. Execute Stage S2: uIR - microinstruction register, buffer register decoders - extract control signals from the microinstructions logic - choosing for branch addresses[cite: 33]

FOUR-STAGE PIPELINE:

1. IF: instruction fetching and decoding using the I-cache.

2. OL: operand loading from the D-cache to RF

3. EX: data processing using the ALU and RF

4. OS: operand storing to the D-cache from RF

THE FACTORS THAT THE PCU OF A SUPERSCALAR COMPUTER MACHINE THAT NEEDS TO BE TAKEN INTO ACCOUNT FOR THE SAID PART OF THE MACHINE TO DO ITS TASK:

1. Instruction type. For example, a floating-point add instruction has to be issued to a floating-point E-unit and not to an integer E-unit[cite: 33]

2. E-unit availability. An instruction can be issued to a pipelined E-unit only if no collisions will result, as determined by the pipeline's reservation table[cite: 33]

3. Data dependencies. To avoid conflicting use of registers, data-dependency constraints among the operands of the active instructions must be satisfied[cite: 33]

4. Control dependencies. To maintain high performance levels, techniques are needed to be reduce the impact of branch instructions on pipeline efficiency

5. Program order. Instructions must eventually produce results in the order specified by the program being executed. The results may be computed out-of-order[cite: 33]

ENUMERATE (IN BULLET FORM) AND DISCUSS BRIEFLY THE FACTORS THAT DETERMINE THE LENGTH OF MICROINSTRUCTIONS

1. The maximum number of simultaneous microoperations that must be specified.

2. The way in which the control information is represented or encoded.

3. The way in which the next microinstruction address is specified.

IT IS QUITE FEASIBLE TO MANUFACTURE AN ENTIRE SEQUENTIAL ALU FOR FIXED-POINT M-BIT NUMBER ON A SINGLE IC CHIP. ENUMERATE AND DISCUSS BRIEFLY THE WAYS ON HOW THE ALU COULD EASILY BE DESIGNED FOR EXPANSION TO HANDLE OPERANDS OF SIZE N = KM, OR ANY WORD SIZE N > M.

1. Spatial Expansion - connect k copies of the m-bit ALU in the manner of a ripple-carry to form a single ALU capable of processing km-bit words directly. The resulting array-like circuit is said to be bit sliced because each component ALU concurrently processes a separate "slice" of mbits from each km-bit operand.

2. Temporal Expansion - use one copy of the m-bit ALU chip in the manner of a serial adder to perform an operation on km-bit words in k consecutive steps (clock cycles). In each step the ALU processes a separate m-bit slice of each operand. This processing is called multicycle or multiple-precision Processing.

Processor-memory communication: (a) without a cache and (b) with a cache

Figure[cite: 33]

Overview of CPU behavior.

Figure[cite: 33]

Four-stage floating-point adder pipeline.

Figure[cite: 33]