Part 11: Pros and Cons of Processors in Computer Architecture

by Jesmin Akther | Jan 16, 2022 | Computer Architecture

Vector Processors

For vector computations this kind of processor was designed. A vector is an array of operands of the same type. Consider the following vectors:

Vector A (a1, a2, a3, ……., an)
Vector B (b1, b2, b3,……., bn)
Vector C = Vector A + Vector B
= C(c1, c2, c3, …….,cn), where c1 = a1+ b1, c2 = a2 + b2, …..,Cn= an + bn.

A vector processor adds all the elements of vector A and Vector B using a single vector instruction with hardware approach.

Examples:

DEC’s VAX 9000, IBM 390/VF,CRAY Research Y-MP family, and Hitachi’s S-810/20, etc.

Array Processors or SIMD Processors:

This Array processors are also designed for vector computations. The key difference between an array processor and a vector processor is  a vector processor uses multiple vector pipelines, on the other hand an array processor deploys a number of processing elements to operate in parallel. An array processor contains multiple numbers of ALUs. Each ALU is provided with the local memory. The ALU together with the local memory is called a Processing Element (PE). An array processor is a SIMD (Single Instruction Multiple Data) processor. So using a single instruction, the same operation can be performed on an array of data which makes it suitable for vector computations.

Types of Microprocessors

Scalar and Superscalar Processors:

A processor  executes scalar data is called scalar processor. The simplest scalar processor makes processing of only integer instruction using fixed-points operands. A powerful scalar processor makes processing of both integer as well floating- point numbers. It contains an integer ALU and a Floating Point Unit (FPU) on the same CPU chip.

A scalar processor may be RISC processor or CISC processor.

Examples of CISC processors are:  Intel 386, 486; Motorola’s 68030, 68040; etc.
Examples of RISC scalar processors are: Intel i860, Motorola MC8810, SUN’s SPARC CY7C601, etc.

A superscalar processor has multiple pipelines and executes more than one instruction per clock cycle. Examples of superscalar processors are: Pentium, Pentium Pro, Pentium II, Pentium III, etc.

Other Three Types of Microprocessors namely, CISC, RISC, and EPIC.

They are as follows:

1. CISC (Complex Instruction Set Computer)

As the name suggests, the instructions are in a complex form. It means that a single instruction can contain many low-level instructions. For example loading data from memory, storing data to the memory, performing basic operations, etc. Besides, we can say that a single instruction has multiple addressing modes. Furthermore, as there are many operations in single instruction they use very few registers.

Examples of CISC are: Intel 386, Intel 486, Pentium, Pentium Pro, Pentium II, etc.

2. RISC (Reduced Instruction Set Computer)

As per the name, in this, the instructions are quite simple, and hence, they execute quickly. Moreover, the instructions get complete in one clock cycle and also use a few addressing modes only. Besides, it makes use of multiple registers so that interaction with memory is less.

Examples are IBM RS6000, DEC Alpha 21064, DEC Alpha 21164, etc.

3. EPIC (Explicitly Parallel Instruction Computing)

It allows the instructions to compute parallelly by making use of compilers. Moreover, the complex instructions also process in fewer clock frequencies. Furthermore, it encodes the instructions in 128-bit bundles. Where each bundle contains three instructions encoded in 41 bits each and a 5-bit template. This 5-bit template contains information about the type of instructions and that which instructions can be executed in parallel.

Digital Signal Processors (DSP):

DSP microprocessors specifically designed to process signals. They receive some digitized signal information, perform some mathematical operations on the information and give the result to an output device. They implement integration, differentiation, complex fast Fourier transform, etc. using hardware.

Examples of digital signal processors are:

Texas instruments’ TMS 320C25, Motorola 56000, National LM 32900, Fujitsu MBB 8764, etc.

Symbolic Processors

Symbolic processors are designed for expert system, machine intelligence, knowledge based system, pattern-recognition, text retrieval, etc. The basic operations which are performed for artificial intelligence are: Logic interference, compare, search, pattern matching, filtering, unification, retrieval, reasoning, etc. This type of processing does not require floating point operations. Symbolic processors are also called LISP processors or PROLOG processors.

Bit-Slice Processors:

The processor of desired word length is developed using the building blocks. The basic building block is called Bit-Slice where the building blocks include 4-bit ALUs, micro programs sequencers, carry look-ahead generators, etc. The word ‘slice’ was used because the desired number of ALUs and other components were used to build an 8-bit, 16-bit or 32-bit CPU.

Examples of Bit-Slice Processors were:

AMD-2900, AMD 2909, AMD 2910, AMD 29300 series, Texas instrument’s SN-74AS88XX series, etc.

Transputers

In a multiprocessor system, a transputer is a specially designed microprocessor to operate as a component processor. Transputers were introduced in late 1980’s. They were built on VLSI chip and contained a processor, memory and communication links. The communication link was to provide point-to-point connection between transputers. A transputer contains FPU, on-chip RAM, high-speed serial link, etc.

Examples of transputers are: INMOS T414, INMOS T800, etc. Where, T414 was a 32-bit processor with 2 KB memory. The T800 was FPU version of 32-bit transputer with 4 KB memory.

Graphic Processors

Graphics Processors are specially designed processors for graphics. Intel has developed Intel 740-3D graphics chip. It is optimized for Pentium II PCs, using a hyper pipelined 3D architecture with additional 2D acceleration. Like most 3D graphics chips, the I-740 will be marketed in performance, not the main stream category. It is designed mostly for such heavy multimedia uses as games and movies.

Part 10: Processors in Computer Architecture

by Jesmin Akther | Jan 16, 2022 | Computer Architecture

What Does Processor Mean?

A processor is an integrated electronic circuit that performs the calculations that run a computer. A processor performs arithmetical, logical, input/output (I/O) and other basic instructions that are passed from an operating system (OS). Most other processes are dependent on the operations of a processor.

• The terms processor, central processing unit (CPU) and microprocessor are commonly linked as synonyms. Most people use the word “processor” interchangeably with the term “CPU” nowadays, it is technically not correct since the CPU is just one of the processors inside a personal computer (PC).
• The Graphics Processing Unit (GPU) is another processor, and even some hard drives are technically capable of performing some processing.

Details of Processor

Processors are found in many modern electronic devices, including PCs, smartphones, tablets, and other handheld devices. Their purpose is to receive input in the form of program instructions and execute trillions of calculations to provide the output that the user will interface with.

A processor includes an arithmetical logic and control unit (CU), which measures capability in terms of the following:

• Ability to process instructions at a given time.
• Maximum number of bits/instructions.
• Relative clock speed.

Every time that an operation is performed on a computer, such as when a file is changed or an application is open, the processor must interpret the operating system or software’s instructions. Depending on its capabilities, the processing operations can be quicker or slower, and have a big impact on what is called the “processing speed” of the CPU.

Each processor is constituted of one or more individual processing units called “cores”. Each core processes instructions from a single computing task at a certain speed, defined as “clock speed” and measured in gigahertz (GHz). Since increasing clock speed beyond a certain point became technically too difficult, modern computers now have several processor cores (dual-core, quad-core, etc.). They work together to process instructions and complete multiple tasks at the same time.

Modern desktop and laptop computers now have a separate processor to handle graphic rendering and send output to the display monitor device. Since this processor, the GPU, is specifically designed for this task, computers can handle all applications that are especially graphic-intensive such as video games more efficiently.

A processor is made of four basic elements: the arithmetic logic unit (ALU), the floating point unit (FPU), registers, and the cache memories. The ALU and FPU carry basic and advanced arithmetic and logic operations on numbers, and then results are sent to the registers, which also store instructions. Caches are small and fast memories that store copies of data for frequent use, and act similarly to a random access memory (RAM).

The CPU carries out his operations through the three main steps of the instruction cycle: fetch, decode, and execute.

• Fetch: the CPU retrieves instructions, usually from a RAM.
• Decode: a decoder converts the instruction into signals to the other components of the computer.
• Execute: the now decoded instructions are sent to each component so that the desired operation can be performed.

Reduced Set Instruction Set Architecture (RISC)

The main idea behind is to make hardware simpler by using an instruction set composed of a few basic steps for loading, evaluating and storing operations just like a load command will load data, store command will store the data.

Characteristic of RISC:

1. Simpler instruction, hence simple instruction decoding.
2. Instruction come under size of one word.
3. Instruction take single clock cycle to get executed.
4. More number of general purpose register.
5. Simple Addressing Modes.
6. Less Data types.
7. Pipeling can be achieved.

Complex Instruction Set Architecture (CISC)

The main idea is to make hardware complex as a single instruction will do all loading, evaluating and storing operations just like a multiplication command will do stuff like loading data, evaluating and storing it.

Characteristic of CISC  

1. Complex instruction, hence complex instruction decoding.
2. Instruction are larger than one word size.
3. Instruction may take more than single clock cycle to get executed.
4. Less number of general purpose register as operation get performed in memory itself.
5. Complex Addressing Modes.
6. More Data types.

Both approaches try to increase the CPU performance.

• RISC: Reduce the cycles per instruction at the cost of the number of instructions per program.
• CISC: The CISC approach attempts to minimize the number of instructions per program but at the cost of increase in number of cycles per instruction.

Earlier when programming was done using assembly language, a need was felt to make instruction do more task because programming in assembly was tedious and error prone due to which CISC architecture evolved but with uprise of high level language dependency on assembly reduced RISC architecture prevailed.

Example – Suppose we have to add two 8-bit number:

• CISC approach: There will be a single command or instruction for this like ADD which will perform the task.
• RISC approach: Here programmer will write first load command to load data in registers then it will use suitable operator and then it will store result in desired location.

So, add operation is divided into parts i.e. load, operate, store due to which RISC programs are longer and require more memory to get stored but require less transistors due to less complex command.

Difference Between RISC and CISC

Part 9: Pipelined Datapath & Control in Computer Architecture

by Jesmin Akther | Jan 16, 2022 | Computer Architecture

PIPELINED DATAPATH

As with the single-cycle and multi-cycle implementations, we will start by looking at the datapath for pipelining. We already know that pipelining involves breaking up instructions into five stages:

• IF – Instruction Fetch
• ID – Instruction Decode
• EX – Execution
• MEM – Memory Access WB – Write Back

We will start by taking a look at the single-cycle datapath, divided into stages bu following figure

Figure 1 

The Pipeline Registers 

• IF/ID This provides an execution context for the ID (Instruction Decode and Register Fetch) stage of execution.
• ID/EX This provides an execution context for the EX (Execute) phase of instruction execution.  In particular, the discrete control signals generated by the control unit as a result of instruction decoding are stored here.
• EX/MEM This provides an execution context for the MEM (Memory Access or R-Type Instruction Completion) phase of instruction execution.  In addition , this register stores copies of the control signals required to complete both the MEM and WB phase of execution for this instruction.
• MEM/WB This provides an execution context for the WB (Write Back) phase of instruction execution.

As we can see, each of the steps maps nicely in order onto the single-cycle datapath. Instruction fields and data generally move from left-to-right as they progress through each stage. The two exceptions are:

• The WB stage places the result back into the register file in the middle of the datapath à leads to data hazards.
• The selection of the next value of the PC – either the incremented PC or the branch address à leads to control hazards. 

One way to visualize pipelining is to consider the execution of each instruction independently, as if it has the datapath all to itself. We can place these datapaths on a timeline to see their relationship. The stages are represented by the datapath element being used, shaded according to use.

Figure 2

In reality, these instructions are not executing in their own datapaths, they share a datapath.

The first instruction uses instruction memory in its IF stage in cycle 1. Then, in cycle 2, the second instruction uses instruction memory for its own IF stage.

Datapath Partitioning for Pipelining

Recall Figure 2 the single-cycle datapath, which can be partitioned (subdivided) into functional units as shown in Figure 2. Because the single-cycle datapath contains separate Instruction Memory and Data Memory units, this allows us to directly implement in hardware the IF-ID-EX-MEM-WB representation of the MIPS instruction sequence. Observe that several control lines have been added, for example, to route data from the ALU output (or memory output) to the register file for writing. Also, there are again three ALUs, one for ALUop, another for JTA computation, and a third for adding PC+4 to compute the address of the next instruction.

Partitioning of the MIPS single-cycle datapath developed previously, to form a pipeline processor. The segments are arranged horizontally, and data flows from left to right.

We can represent this pipeline structure using a space-time diagram similar . Here four load instructions are executed sequentially, which are chosen because the lw instruction is the only one in our MIPS subset that consistently utilizes all five pipeline segments. Observe also that the right half of the register file is shaded to represent a read operation, while the left half is shaded to represent write.

Partitioning of the MIPS single-cycle datapath developed previously, with replication in space, to form a pipeline processor that computes four lw instructions. The segments are arranged horizontally, and data flows from left to right, synchronously with the clock cycles (CC1 through CC7).

In order to ensure that the single-cycle datapath conforms to the pipeline design constraint of one cycle per segment, we need to add buffers and control between stages, similar to the way we added buffers in the multicycle datapath. These buffers and control circuitry are shown in Figure 5.4 as red rectangles, and store the results of the i-th stage so that the (i+1)-th stage can use these results in the next clock cycle.

In summary, pipelining improves efficiency by first regularizing the instruction format, for simplicity. We then divide the instructions into a fixed number of steps, and implement each step as a pipeline segment. During the pipeline design phase, we ensure that each segment takes about the same amount of time to execute as other segments in the pipeline. Also, we want to keep the pipeline full wherever possible, in order to maximize utilization and throughput, while minimizing set-up time.

For this to work, we need to add registers to store data between cycles.

This figure shows the addition of pipeline registers (in blue) which are used to hold data between cycles.

Following our laundry analogy, these might be like baskets between the washer, dryer, etc that hold a clothing load between steps. During each cycle, an instruction advances from one pipeline register to the next pipeline register. Note that the registers are labeled by the stages that they separate.

Pipeline registers are as wide as necessary to hold all of the data passed into them. For instance, IF/ID is 64 bits wide because it must hold a 32-bit instruction and a 32-bit PC+4 result.

Pipelined data path and control

A pipeline processor can be represented in two dimensions, as shown in Figure 1. Here, the pipeline segments (Seg #1 through Seg #3) are arranged vertically, so the data can flow from the input at the top left downward to the output of the pipeline (after Segment 3). The progress of an instruction is charted in blue typeface, and the next instruction is shown in red typeface.

There are three things that one must observe about the pipeline

1. First, the work (in a computer, the ISA) is divided up into pieces that more or less fit into the segments alloted for them.
2. Second, this implies that in order for the pipeline to work efficiently and smoothly, the work partitions must each take about the same time to complete. Otherwise, the longest partition requiring time T would hold up the pipeline, and every segment would have to take time T to complete its work. For fast segments, this would mean much idle time.
3. Third, in order for the pipeline to work smoothly, there must be few (if any) exceptions or hazards that cause errors or delays within the pipeline. Otherwise, the instruction will have to be reloaded and the pipeline restarted with the same instruction that causes the exception. There are additional problems we need to discuss about pipeline processors, which we will consider shortly.

It is easily verified, through inspection of Figure 1., that the response time for any instruction that takes three segments must be three times the response time for any segment, provided that the pipeline was full when the instruction was loaded into the pipeline. As we shall see later in this section, if an N-segment pipeline is empty before an instruction starts, then N + (N-1) cycles or segments of the pipeline are required to execute the instruction, because it takes N cycles to fill the pipe.

Work Partitioning. In the previous section, we designed a multicycle datapath based on the assumption that computational work associated with the execution of an instruction could be partitioned into a five-step process, as follows:

 Performance. Because there are N segments active in the pipeline at any one time (when it is full), it is thus possible to execute N segments concurrently in any cycle of the pipeline. In contrast, a purely sequential implementation of the fetch-decode-execute cycle would require N cycles for the longest instruction. Thus, it can be said that we have O(N) speedup. As we shall see when we analyze pipeline performance, an exact N-fold speedup does not always occur in practice. However it is sufficient to say that the speedup is of order N.

Pipeline Datapath Design and Implementation

The work involved in an instruction can be partitioned into steps labelled IF (Instruction Fetch), ID (Instruction Decode and data fetch), EX (ALU operations or R-format execution), MEM (Memory operations), and WB (Write-Back to register file). We next discuss how this sequence of steps can be implemented in terms of MIPS instructions.

 MIPS Instructions and Pipelining

In order to implement MIPS instructions effectively on a pipeline processor, we must ensure that the instructions are the same length (simplicity favors regularity) for easy IF and ID, similar to the multicycle datapath. We also need to have few but consistent instruction formats, to avoid deciphering variable formats during IF and ID, which would prohibitively increase pipeline segment complexity for those tasks. Thus, the register indices should be in the same place in each instruction. In practice, this means that the rd, rs, and rt fields of the MIPS instruction must not change location across all MIPS pipeline instructions.

Additionally, we want to have instruction decoding and reading of the register contents occur at the same time, which is supported by the datapath architecture that we have designed thus far. Observe that we have memory address computation in the lw and sw instructions only, and that these are the only instructions in our five-instruction MIPS subset that perform memory operations. As before, we assume that operands are aligned in memory, for straightforward access. 

In the next section, we will see that pipeline processing has some difficult problems, which are called hazards, and the pipeline is also susceptible to exceptions.

Pipeline Control and Hazards

The control of pipeline processors has similar issues to the control of multicycle datapaths. Pipelining leaves the meaning of the nine control lines unchanged, that is, those lines which controlled the multicycle datapath. In pipelining, we set control lines (to defined values) in each stage for each instruction. This is done in hardware by extending pipeline registers to include control information and circuitry.

 Pipeline Control Issues and Hardware

Observe that there is nothing to control during instruction fetch and decode (IF and ID). Thus, we can begin our control activities (initialization of control signals) during ID, since control will only be exerted during EX, MEM, and WB stages of the pipeline. Recalling that the various stages of control and buffer circuitry between the pipeline stages are labelled IF/ID, ID/EX, EX/MEM, and MEM/WB, we have the propagation of control shown in Figure.

Propagation of control through the EX, MEM, and WB states of the MIPS pipelined datapath.

Here, the following stages perform work as specified:

• IF/ID: Initializes control by passing the rs, rd, and rt fields of the instruction, together with the opcode and funct fields, to the control circuitry.
• ID/EX: Buffers control for the EX, MEM, and WB stages, while executing control for the EX stage. Control decides what operands will be input to the ALU, what ALU operation will be performed, and whether or not a branch is to be taken based on the ALU Zero output.
• EX/MEM: Buffers control for the MEM and WB stages, while executing control for the MEM stage. The control lines are set for memory read or write, as well as for data selection for memory write. This stage of control also contains the branch control logic.
• MEM/WB: Buffers and executes control for the WB stage, and selects the value to be written into the register file.

Figure shows how the control lines (red) are arranged on a per-stage basis, and how the stage-specific control signals are buffered and passed along to the next applicable stage.

Part 8: Pipeline Hazards & Solution in computer architecture

by Jesmin Akther | Jan 16, 2022 | Computer Architecture

Pipeline

Instruction Pipelining

• Similar to the use of an assembly line in a manufacturing plant
• An instruction has a number of stages

• This pipeline has two independent stages
  • The first stage fetches an instruction and buffers it
  • When the second stage is free, the first stage passes it the buffered instruction
• While the second stage is executing the instruction, the first stage takes advantage of any unused memory cycles to fetch and buffer the next instruction This is called instruction prefetch or fetch overlap
• Speed-up is unlikely for two reasons:
• The execution time will generally be longer than the fetch time
• Fetch stage may have to wait for some time before it can empty its buffer
• A conditional branch instruction makes the address of the next instruction to be fetched unknown
• Fetch stage must wait until it receives the next instruction address from the execute stage
• The execute stage may then have to wait while the next instruction is fetched. 

Solution for problem 2: 

• When a conditional branch instruction is passed on from the fetch to the execute stage, the fetch stage fetches the next instruction in memory after the branch instruction
  • Then, if the branch is not taken, no time is lost
  • If the branch is taken, the fetched instruction must be discarded and a new instruction fetched

Stages of instruction processing

• Fetch instruction (FI): Read the next expected instruction into a buffer
• Decode instruction (DI): Determine the opcode and the operand specifiers
• Calculate operands (CO): Calculate the effective address of each source operand. This may involve displacement, register indirect, indirect, or other forms of address calculation
• Fetch operands (FO): Fetch each operand from memory. Operands in registers need not be fetched
• Execute instruction (EI): Perform the indicated operation and store the result,if any, in the specified destination operand location
• Write operand (WO): Store the result in memory

Several other factors limit the performance

• If the six stages are not of equal duration, there will be some waiting involved at various pipeline stages
• Another difficulty is the conditional branch instruction, which can invalidate several instruction fetches

Flowchart: 

Six-Stage CPU Instruction Pipeline

Pipeline Performance

• The cycle time of an instruction pipeline is the time needed to advance a set of instructions one stage through the pipeline The cycle time can be determined as:

• Where:
• τ_i = time delay of the circuitry in the i^th stage of the pipeline
• τ_m = maximum stage delay (delay through stage which experiences the largest delay)
• k = number of stages in the instruction pipeline
• d = time delay of a latch, needed to advance signals and data from one stage to the next
• Time delay, d is equivalent to a clock pulse and 𝜏_𝑚 >>d
• Now suppose that n instructions are processed, with no branches
• Let T_k,n be the total time required for a pipeline with k stages to execute n instructions

• A total of k cycles are required to complete the execution of the first instruction, and the remaining n-1 instructions require n-1 cycles
• Consider a processor with equivalent functions but no pipeline, and assume that the instruction cycle time is kτ

Pipeline Hazards

• A pipeline hazard occurs when the pipeline, or some portion of the pipeline, must stall because conditions do not permit continued execution Referred to as also a pipeline bubble
• There are three types of hazards:
  • Resource
  • Data and
  • Control

Resource Hazards: 

• A resource hazard occurs when two (or more) instructions that are already in the pipeline need the same resource
• The result is that the instructions must be executed in serial rather than parallel for a portion of the pipeline
• Sometime referred to as a structural hazard

Data Hazards: 

• Occurs when there is a conflict in the access of an operand location
• Two instructions in a program are to be executed in sequence and both access a particular memory or register operand
• If the two instructions are executed in strict sequence, no problem occurs
• However, if the instructions are executed in a pipeline, then it is possible for the operand value to be updated in such a way as to produce a different result than would occur with strict sequential execution
• In other words, the program produces an incorrect result because of the use of pipelining 

Three types of data hazards

1. Read after write (RAW), or true dependency: An instruction modifies a register or memory location and a succeeding instruction reads the data in that memory or register location
   • A hazard occurs if the read takes place before the write operation is complete
2. Write after read (WAR), or anti-dependency: An instruction reads a register or memory location and a succeeding instruction writes to the location
   • A hazard occurs if the write operation completes before the read operation takes place
3. Write after write (WAW), or output dependency: Two instructions both write to the same location
   • A hazard occurs if the write operations take place in the reverse order of the intended sequence

                                                                                                Figure: RAW Data Hazard

 Control Hazards:

Also known as a branch hazard, occurs when the pipeline makes the wrong decision on a branch prediction and therefore brings instructions into the pipeline that must subsequently be discarded

Dealing with Branches

• Multiple Techniques:
  • • Prefetch branch target
    • Loop buffer
    • Branch prediction
    • Delayed branch

  Multiple Streams:

• A simple pipeline suffers a penalty for a branch instruction because it must choose one of two instructions to fetch next and may make the wrong choice
• A brute-force approach is to replicate the initial portions of the pipeline and allow the pipeline to fetch both instructions, making use of two streams
• There are two problems with this approach:
  • With multiple pipelines there are contention delays for access to the registers and to memory
  • Additional branch instructions may enter the pipeline (either stream) before the original branch decision is resolved

Prefetch Branch Target:

• When a conditional branch is recognized, the target of the branch is prefetched, in addition to the instruction following the branch
• This target is then saved until the branch instruction is executed
• If the branch is taken, the target has already been prefetched 

LOOP BUFFER : A loop buffer is a small, very-high-speed memory maintained by the instruction fetch stage of the pipeline and containing the n most recently fetched instructions, in sequence

• If a branch is to be taken, the hardware first checks whether the branch target is within the buffer
• If so, the next instruction is fetched from the buffer

The loop buffer has three benefits: 

• With the use of prefetching, the loop buffer will contain some instruction sequentially ahead of the current instruction fetch address
  • Thus, instructions fetched in sequence will be available without the usual memory access time
• If a branch occurs to a target just a few locations ahead of the address of the branch instruction, the target will already be in the buffer
  • This is useful for the rather common occurrence of IF–THEN and IF–THEN– ELSE sequences
• This strategy is particularly well suited to dealing with loops, or iterations; hence the name loop buffer
  • If the loop buffer is large enough to contain all the instructions in a loop, then those instructions need to be fetched from memory only once, for the first iteration
  • For subsequent iterations, all the needed instructions are already in the buffer 

Branch Prediction: Multiple techniques

• Predict never taken
• Predict always taken
• Predict by opcode
• Taken/not taken switch
• Branch history table 

Delayed Branch: It is possible to improve pipeline performance by automatically rearranging instructions within a program, so that branch instructions occur later than actually desired

Part 7: Datapath Design of Computer Architecture

by Jesmin Akther | Jan 16, 2022 | Computer Architecture

What is Datapath?

The component of the processor that performs arithmetic operations – P&H

The collection of state elements, computation elements, and interconnections that together provide a conduit for the flow and transformation of data in the processor during execution. – DIA

Datapath Design and Implementation

The datapath is the “brawn” of a processor, since it implements the fetch-decode-execute cycle. The general discipline for datapath design is to (1) determine the instruction classes and formats in the ISA, (2) design datapath components and interconnections for each instruction class or format, and (3) compose the datapath segments designed in Step 2) to yield a composite datapath.

Simple datapath components include memory (stores the current instruction), PC or program counter (stores the address of current instruction), and ALU (executes current instruction). The interconnection of these simple components to form a basic datapath is illustrated in Figure 4.5. Note that the register file is written to by the output of the ALU. The register file shown in Figure 4.6 is clocked by the RegWrite signal.

Figure 1. Schematic high-level diagram of MIPS datapath from an implementational perspective, adapted from [Maf01].

Implementation of the datapath for I- and J-format instructions requires two more components – a data memory and a sign extender, illustrated in Figure 2. The data memory stores ALU results and operands, including instructions, and has two enabling inputs (MemWrite and MemRead) that cannot both be active (have a logical high value) at the same time. The data memory accepts an address and either accepts data (WriteData port if MemWrite is enabled) or outputs data (ReadData port if MemRead is enabled), at the indicated address. The sign extender adds 16 leading digits to a 16-bit word with most significant bit b, to product a 32-bit word. In particular, the additional 16 digits have the same value as b, thus implementing sign extension in twos complement representation.

Figure 2. Schematic diagram of Data Memory and Sign Extender, adapted from [Maf01].

 R-format Datapath

Implementation of the datapath for R-format instructions is fairly straightforward – the register file and the ALU are all that is required. The ALU accepts its input from the DataRead ports of the register file, and the register file is written to by the ALUresult output of the ALU, in combination with the RegWrite signal.

Figure 3. Schematic diagram R-format instruction datapath, adapted from [Maf01].

 Load/Store Datapath

The load/store datapath uses instructions such as lw $t1, offset($t2), where offset denotes a memory address offset applied to the base address in register $t2. The lw instruction reads from memory and writes into register $t1. The sw instruction reads from register $t1 and writes into memory. In order to compute the memory address, the MIPS ISA specification says that we have to sign-extend the 16-bit offset to a 32-bit signed value. This is done using the sign extender shown in Figure 2.

The load/store datapath is illustrated in Figure 4, and performs the following actions in the order given:

1. Register Access takes input from the register file, to implement the instruction, data, or address fetch step of the fetch-decode-execute cycle.
2. Memory Address Calculation decodes the base address and offset, combining them to produce the actual memory address. This step uses the sign extender and ALU.
3. Read/Write from Memory takes data or instructions from the data memory, and implements the first part of the execute step of the fetch/decode/execute cycle.
4. Write into Register File puts data or instructions into the data memory, implementing the second part of the execute step of the fetch/decode/execute cycle.

Figure 4. Schematic diagram of the Load/Store instruction datapath. Note that the execute step also includes writing of data back to the register file, which is not shown in the figure, for simplicity [MK98].

The load/store datapath takes operand #1 (the base address) from the register file, and signextends the offset, which is obtained from the instruction input to the register file. The signextended offset and the base address are combined by the ALU to yield the memory address, which is input to the Address port of the data memory. The MemRead signal is then activated, and the output data obtained from the ReadData port of the data memory is then written back to the Register File using its WriteData port, with RegWrite asserted.

Branch/Jump Datapath

The branch datapath (jump is an unconditional branch) uses instructions such as beq $t1, $t2, offset, where offset is a 16-bit offset for computing the branch target address via PC-relative addressing. The beq instruction reads from registers $t1 and $t2, then compares the data obtained from these registers to see if they are equal. If equal, the branch is taken. Otherwise, the branch is not taken.

By taking the branch, the ISA specification means that the ALU adds a sign-extended offset to the program counter (PC). The offset is shifted left 2 bits to allow for word alignment (since 2² = 4, and words are comprised of 4 bytes). Thus, to jump to the target address, the lower 26 bits of the PC are replaced with the lower 26 bits of the instruction shifted left 2 bits.

The branch instruction datapath is illustrated in Figure 4.9, and performs the following actions in the order given:

1. Register Access takes input from the register file, to implement the instruction fetch or data fetch step of the fetch-decode-execute cycle.
2. Calculate Branch Target – Concurrent with ALU #1’s evaluation of the branch condition, ALU #2 calculates the branch target address, to be ready for the branch if it is taken. This completes the decode step of the fetch-decode-execute cycle.
3. Evaluate Branch Condition and Jump to BTA or PC+4 uses ALU #1 in Figure 5, to determine whether or not the branch should be taken. Jump to BTA or PC+4 uses control logic hardware to transfer control to the instruction referenced by the branch target address. This effectively changes the PC to the branch target address, and completes the execute step of the fetch-decode-execute cycle.

Figure 5. Schematic diagram of the Branch instruction datapath. Note that, unlike the Load/Store datapath, the execute step does not include writing of results back to the register file [MK98].

The branch datapath takes operand #1 (the offset) from the instruction input to the register file, then sign-extends the offset. The sign-extended offset and the program counter (incremented by 4 bytes to reference the next instruction after the branch instruction) are combined by ALU #1 to yield the branch target address. The operands for the branch condition to evaluate are concurrently obtained from the register file via the ReadData ports, and are input to ALU #2, which outputs a one or zero value to the branch control logic.

MIPS has the special feature of a delayed branch, that is, instruction I_b which follows the branch is always fetched, decoded, and prepared for execution. If the branch condition is false, a normal branch occurs. If the branch condition is true, then I_b is executed. One wonders why this extra work is performed – the answer is that delayed branch improves the efficiency of pipeline execution. Also, the use of branch-not-taken (where I_b is executed) is sometimes the common case.

Single-Cycle and Multicycle Datapaths

A single-cycle datapath executes in one cycle all instructions that the datapath is designed to implement. This clearly impacts CPI in a beneficial way, namely, CPI = 1 cycle for all instructions. In this section, we first examine the design discipline for implementing such a datapath using the hardware components and instruction-specific datapaths developed in previous section. Then, we discover how the performance of a single-cycle datapath can be improved using a multi-cycle implementation.

Single Datapaths

Let us begin by constructing a datapath with control structures taken from the results of previous section. The simplest way to connect the datapath components developed in the former section is to have them all execute an instruction concurrently, in one cycle. As a result, no datapath component can be used more than once per cycle, which implies duplication of components. To make this type of design more efficient without sacrificing speed, we can share a datapath component by allowing the component to have multiple inputs and outputs selected by a multiplexer.

The key to efficient single-cycle datapath design is to find commonalities among instruction types. For example, the R-format MIPS instruction datapath of Figure 3 and the load/store datapath of Figure 4 have similar register file and ALU connections. However, the following differences can also be observed:

1. The second ALU input is a register (R-format instruction) or a signed-extended lower 16 bits of the instruction (e.g., a load/store offset).
2. The value written to the register file is obtained from the ALU (R-format instruction) or memory (load/store instruction).

These two datapath designs can be combined to include separate instruction and data memory, as shown in Figure 6. The combination requires an adder and an ALU to respectively increment the PC and execute the R-format instruction.

Figure 6. Schematic diagram of a composite datapath for R-format and load/store instructions [MK98].

Adding the branch datapath to the datapath illustrated in Figure 5 produces the augmented datapath shown in Figure 7. The branch instruction uses the main ALU to compare its operands and the adder computes the branch target address. Another multiplexer is required to select either the next instruction address (PC + 4) or the branch target address to be the new value for the PC.

Figure 7. Schematic diagram of a composite datapath for R-format, load/store, and branch instructions [MK98].

ALU Control. Given the simple datapath shown in Figure 7, we next add the control unit. Control accepts inputs (called control signals) and generates (a) a write signal for each state element, (b) the control signals for each multiplexer, and (c) the ALU control signal. The ALU has three control signals, as shown in Table 1, below.

Table 1. ALU control codes

ALU Control Input       Function

——————    ————

000                  and

001                  or

010                  add

• sub
• slt

The ALU is used for all instruction classes, and always performs one of the five functions in the right-hand column of Table 1. For branch instructions, the ALU performs a subtraction, whereas R-format instructions require one of the ALU functions. The ALU is controlled by two inputs: (1) the opcode from a MIPS instruction (six most significant bits), and (2) a two-bit control field (which Patterson and Hennesey call _ALUop). The ALUop signal denotes whether the operation should be one of the following:

ALUop Input      Operation

————-   ————-

• load/store
• beq

10          determined by opcode

The output of the ALU control is one of the 3-bit control codes shown in the left-hand column of Table 4.1. In Table 2, we show how to set the ALU output based on the instruction opcode and the ALUop signals. Later, we will develop a circuit for generating the ALUop bits. We call this approach multi-level decoding — main control generates ALUop bits, which are input to ALU control. The ALU control then generates the three-bit codes shown in Table 1.

The advantage of a hierarchically partitioned or pipelined control scheme is realized in reduced hardware (several small control units are used instead of one large unit). This results in reduced hardware cost, and can in certain instances produce increased speed of control. Since the control unit is critical to datapath performance, this is an important implementational step.

Recall that we need to map the two-bit ALUop field and the six-bit opcode to a three-bit ALU control code. Normally, this would require 2^{(2 + 6)} = 256 possible combinations, eventually expressed as entries in a truth table. However, only a few opcodes are to be implemented in the ALU designed herein. Also, the ALU is used only when ALUop = 10₂. Thus, we can use simple logic to implement the ALU control, as shown in terms of the truth table illustrated in Table 2.

Table 2. ALU control bits as a function of ALUop bits and opcode bits [MK98].

In this table, an “X” in the input column represents a “don’t-care” value, which indicates that the output does not depend on the input at the i-th bit position. The preceding truth table can be optimized and implemented in terms of gates.

 Main Control Unit. The first step in designing the main control unit is to identify the fields of each instruction and the required control lines to implement the datapath shown in Figure 7.  Recalling the three MIPS instruction formats (R, I, and J), shown as follows:

Observe that the following always apply:

• Bits 31-26: opcode – always at this location
• Bits 25-21 and 20-16: input register indices – always at this location

Additionally, we have the following instruction-specific codes due to the regularity of the MIPS instruction format:

• Bits 25-21: base register for load/store instruction – always at this location
• Bits 15-0: 16-bit offset for branch instruction – always at this location
• Bits 15-11: destination register for R-format instruction – always at this location
• Bits 20-16: destination register for load/store instruction – always at this location

Note that the different positions for the two destination registers implies a selector (i.e., a mux) to locate the appropriate field for each type of instruction. Given these contraints, we can add to the simple datapath thus far developed instruction labels and an extra multiplexer for the WriteReg input of the register file, as shown in Figure 8.

Figure 8. Schematic diagram of composite datapath for R-format, load/store, and branch instructions (from Figure 4.11) with control signals and extra multiplexer for WriteReg signal generation [MK98].

Here, we see the seven-bit control lines (six-bit opcode with one-bit WriteReg signal) together with the two-bit ALUop control signal, whose actions when asserted or deasserted are given as follows:

• RegDst

Deasserted: Register destination number for the Write register is taken from bits 20-16 (rt field) of the instruction

Asserted: Register destination number for the Write register is taken from bits 15-11 (rd field) of the instruction

• RegWrite

Deasserted: No action

Asserted: Register on the WriteRegister input is written with the value on the WriteData input

• ALUSrc

Deasserted: The second ALU operand is taken from the second register file output (ReadData 2)

Asserted: the second alu operand is the sign-extended, lower 16 bits of the instruction

• PCSrc

Deasserted: PC is overwritten by the output of the adder (PC + 4)

Asserted: PC overwritten by the branch target address

• MemRead

Deasserted: No action

Asserted: Data memory contents designated by address input are present at the ReadData output

• MemWrite

Deasserted: No action

Asserted: Data memory contents designated by address input are present at the WriteData input

• RegWrite

Deasserted: The value present at the WriteData input is output from the ALU

Asserted: The value present at the register WriteData input is taken from data memory

Given only the opcode, the control unit can thus set all the control signals except PCSrc, which is only set if the instruction is _beq and the Zero output of the ALu used for comparison is true. PCSrc is generated by and-ing a Branch signal from the control unit with the Zero signal from the ALU. Thus, all control signals can be set based on the opcode bits. The resultant datapath and its signals are shown in detail in Figure 9.

Figure 9. Schematic diagram of composite datapath for R-format, load/store, and branch instructions (from Figure 4.12) with control signals illustrated in detail [MK98].

We next examine functionality of the datapath illustrated in 4.13, for the three major types of instructions, then discuss how to augment the datapath for a new type of instruction.

 Datapath Operation

Recall that there are three MIPS instruction formats — R, I, and J. Each instruction causes slightly different functionality to occur along the datapath, as follows.

 R-format Instruction Execution of an R-format instruction (e.g., _{add $t1, $t0, $t1}) using the datapath developed in Section 4.3.1 involves the following steps:

1. Fetch instruction from instruction memory and increment PC
2. Input registers (e.g., _$t0 and _$t1) are read from the register file
3. ALU operates on data from register file using the funct field of the MIPS instruction (Bits 5-0) to help select the ALU operation
4. Result from ALU written into register file using bits 15-11 of instruction to select the destination register (e.g., _$t1).

Note that this implementational sequence is actually combinational, becuase of the single-cycle assumption. Since the datapath operates within one clock cycle, the signals stabilize approximately in the order shown in Steps 1-4, above.

Load/Store Instruction Execution of a load/store instruction (e.g., _{lw $t1, offset($t2)}) using the datapath developed in previous section involves the following steps:

1. Fetch instruction from instruction memory and increment PC
2. Read register value (e.g., base address in _$t2) from the register file
3. ALU adds the base address from register _$t2 to the sign-extended lower 16 bits of the instruction (i.e., _offset)
4. Result from ALU is applied as an address to the data memory
5. Data retrieved from the memory unit is written into the register file, where the register index is given by _$t1 (Bits 20-16 of the instruction).

Branch Instruction. Execution of a branch instruction (e.g., _{beq $t1, $t2, offset}) using the datapath developed in previous Section involves the following steps:

1. Fetch instruction from instruction memory and increment PC
2. Read registers (e.g., _$t1 and _$t2) from the register file. The adder sums PC + 4 plus sign-extended lower 16 bits of _offset shifted left by two bits, thereby producing the branch target address (BTA).
3. ALU subtracts contents of _$t1 minus contents of _$t2. The Zero output of the ALU directs which result (PC+4 or BTA) to write as the new PC.

Final Control Design. Now that we have determined the actions that the datapath must perform to compute the three types of MIPS instructions, we can use the information in Table 4.3 to describe the control logic in terms of a truth table. This truth table (Table 4.3) is optimized as to yield the datapath control circuitry.

Table 3. ALU control bits as a function of ALUop bits and opcode bits [MK98].

Extended Control for New Instructions

The jump instruction provides a useful example of how to extend the single-cycle datapath developed in previous section, to support new instructions. Jump resembles branch (a conditional form of the jump instruction), but computes the PC differently and is unconditional. Identical to the branch target address, the lowest two bits of the jump target address (JTA) are always zero, to preserve word alignment. The next 26 bits are taken from a 26-bit immediate field in the jump instruction (the remaining six bits are reserved for the opcode). The upper four bits of the JTA are taken from the upper four bits of the next instruction (PC + 4). Thus, the JTA computed by the jump instruction is formatted as follows:

• Bits 31-28: Upper four bits of (PC + 4)
• Bits 27-02: Immediate field of jump instruction
• Bits 01-00: Zero (00₂)

The jump is implemented in hardware by adding a control circuit to Figure 9, which is comprised of:

• An additional multiplexer, to select the source for the new PC value. To cover all cases, this source is PC+4, the conditional BTA, or the JTA.
• An additional control signal for the new multiplexer, asserted only for a jump instruction (opcode = 2).

The resulting augmented datapath is shown in Figure 10.

Figure 10. Schematic diagram of composite datapath for R-format, load/store, branch, and jump instructions, with control signals labelled [MK98].

Limitations of the Single-Cycle Datapath

The single-cycle datapath is not used in modern processors, because it is inefficient. The critical path (longest propagation sequence through the datapath) is five components for the load instruction. The cycle time t_c is limited by the settling time t_s of these components. For a circuit with no feedback loops, t_c > 5t_s. In practice, t_c = 5kt_s, with large proportionality constant k, due to feedback loops, delayed settling due to circuit noise, etc. Additionally, it is possible to compute the required execution time for each instruction class from the critical path information. The result is that the Load instruction takes 5 units of time, while the Store and R-format instructions take 4 units of time. All the other types of instructions that the datapath is designed to execute run faster, requiring three units of time.

The problem of penalizing addition, subtraction, and comparison operations to accomodate loads and stores leads one to ask if multiple cycles of a much faster clock could be used for each part of the fetch-decode-execute cycle. In practice, this technique is employed in CPU design and implementation, as discussed in the following sections on multicycle datapath design. In Section 5, we will show that datapath actions can be interleaved in time to yield a potentially fast implementation of the fetch-decode-execute cycle that is formalized in a technique called pipelining.

Multicycle Datapath Design

In the previous sections, we designed a single-cycle datapath by (1) grouping instructions into classes, (2) decomposing each instruction class into constituent operations, and (3) deriving datapath components for each instruction class that implemented these operations. In this section, we use the single-cycle datapath components to create a multi-cycle datapath, where each step in the fetch-decode-execute sequence takes one cycle. This approach has two advantages over the single-cycle datapath:

1. Each functional unit (e.g., Register File, Data Memory, ALU) can be used more than once in the course of executing an instruction, which saves hardware (and, thus, reduces cost); and
2. Each instruction step takes one cycle, so different instructions have different execution times. In contrast, the single-cycle datapath that we designed previously required every instruction to take one cycle, so all the instructions move at the speed of the slowest.

We next consider the basic differences between single-cycle and multi-cycle datapaths.

Cursory Analysis. Figure 11 illustrates a simple multicycle datapath. Observe the following differences between a single-cycle and multi-cycle datapath:

• In the multicycle datapath, one memory unit stores both instructions and data, whereas the single-cycle datapath requires separate instruction and data memories.
• The multicycle datapath uses on ALU, versus an ALU and two adders in the single-cycle datapath, because signals can be rerouted throuh the ALU in a multicycle implementation.
• In the single-cycle implementation, the instruction executes in one cycle (by design) and the outputs of all functional units must stabilize within one cycle. In contrast, the

multicycle implementation uses one or more registers to temporarily store (buffer) the ALU or functional unit outputs. This buffering action stores a value in a temporary register until it is needed or used in a subsequent clock cycle.

Figure 11. Simple multicycle datapath with buffering registers (Instruction register, Memory data register, A, B, and ALUout) [MK98].

Note that there are two types of state elements (e.g., memory, registers), which are:

1. Programmer-Visible (register file, PC, or memory), in which data is stored that is used by subsequent instructions (in a later clock cycle); and
2. Additional State Elements(buffer registers), in which data is stored that is used in a later clock cycle of the same instruction.

Thus, the additional (buffer) registers determine (a) what functional units will fit into a given clock cycle and (b) the data required for later cycles involved in executing the current instruction. In the simple implementation presented herein, we assume for purposes of illustration that each clock cycle can accomodate one and only one of the following operations:

• Memory access
• Register file access (two reads or one write)
• ALU operation (arithmetic or logical)

New Registers. As a result of buffering, data produced by memory, register file, or ALU is saved for use in a subsequent cycle. The following temporary registers are important to the multicycle datapath implementation discussed in this section:

• Instruction Register (IR) saves the data output from the Text Segment of memory for a subsequent instruction read;
• Memory Data Register (MDR) saves memory output for a data read operation;
• A and B Registers (A,B) store ALU operand values read from the register file; and  ALU Output Register (ALUout) contains the result produced by the ALU.

The IR and MDR are distinct registers because some operations require both instruction and data in the same clock cycle. Since all registers except the IR hold data only between two adjacent clock cycles, these registers do not need a write control signal. In contrast, the IR holds an instruction until it is executed (multiple clock cycles) and therefor requires a write control signal to protect the instruction from being overwritten before its execution has been completed.

New Muxes. We also need to add new multiplexers and expand existing ones, to implement sharing of functional units. For example, we need to select between memory address as PC (for a load instruction) or ALUout (for load/store instructions). The muxes also route to one ALU the many inputs and outputs that were distributed among the several ALUs of the single-cycle datapath. Thus, we make the following additional changes to the single-cycle datapath:

• Add a multiplexer to the first ALU input, to choose between (a) the A register as input (for R- and I-format instructions) , or (b) the PC as input (for branch instructions).
• On the second ALU, the input is selected by a four-way mux (two control bits). The two additional inputs to the mux are (a) the immediate (constant) value 4 for incrementing the PC and (b) the sign-extended offset, shifted two bits to preserve alignment, which is used in computing the branch target address.

The details of these muxes are shown in Figure 12. By adding a few registers (buffers) and muxes (inexpensive widgets), we halve the number of memory units (expensive hardware) and eliminate two adders (more expensive hardware).

New Control Signals. The datapath shown in Figure 12 is multicycle, since it uses multiple cycles per instruction. As a result, it will require different control signals than the single-cycle datapath, as follows:

• Write Control Signals for the IR and programmer-visible state units  Read Control Signal for the memory; and            Control Lines for the muxes.

It is advantageous that the ALU control from the single-cycle datapath can be used as-is for the multicycle datapath ALU control. However, some modifications are required to support branches and jumps. We describe these changes as follows.

Branch and Jump Instruction Support. To implement branch and jump instructions, one of three possible values is written to the PC:

1. ALU output = PC + 4, to get the next instruction during the instruction fetch step (to do this, PC + 4 is written directly to the PC)
2. Register ALUout, which stores the computed branch target address.
3. Lower 26 bits (offset) of the IR, shifted left by two bits (to preserve alignment) and concatenated with the upper four bits of PC+4, to form the jump target address.

The PC is written unconditionally (jump instruction) or conditionally (branch), which implies two control signals – PCWrite and PCWriteCond. From these two signals and the Zero output of the ALU, we derive the PCWrite control signal, via the following logic equation:

PCWriteControl = (ALUZero and PCWriteCond) or PCWrite,

where (a) ALUZero indicates if two operands of the beq nstruction are equal and (b) the result of (ALUZero and PCWriteCond) determines whether the PC should be written during a conditional branch. We call the latter the branch taken condition. Figure 4.16 shows the resultant multicycle datapath and control unit with new muxes and corresponding control signals. Table 4.4 illustrates the control signals and their functions.

Multicycle Datapath and Instruction Execution

Given the datapath illustrated in Figure 12, we examine instruction execution in each cycle of the datapath. The implementational goal is balancing of the work performed per clock cycle, to minimize the average time per cycle across all instructions. For example, each step would contain one of the following:

• ALU operation
• Register file access (two reads or one write)
• Memory access (one read or one write)

Thus, the cycle time will be equal to the maximum time required for any of the preceding operations.

Note: Since (a) the datapath is designed to be edge-triggered and (b) the outputs of ALU, register file, or memory are stored in dedicated registers (buffers), we can continue to read the value stored in a dedicated register. The new value, output from ALU, register file, or memory, is not available in the register until the next clock cycle.

Figure 12. MIPS multicycle datapath [MK98].

Table 4. Multicycle datapath control signals and their functions [MK98].

In the multicycle datapath, all operations within a clock cycle occur in parallel, but successive steps within a given instruction operate sequentially. Several implementational issues present that do not confound this view, but should be discussed. One must distinguish between (a) reading/writing the PC or one of the buffer registers, and (b) reads/writes to the register file. Namely, I/O to the PC or buffers is part of one clock cycle, i.e., we get this essentially “for free” because of the clocking scheme and hardware design. In contrast, the register file has more complex hardware and requires a dedicated clock cycle for its circuitry to stabilize.

We next examine multicycle datapath execution in terms of the fetch-decode-execute sequence.

Instruction Fetch. In this first cycle that is common to all instructions, the datapath fetches an instruction from memory and computes the new PC (address of next instruction in the program sequence), as represented by the following pseudocode:

IR = Memory[PC]      # Put contents of Memory[PC] in Instr.Register

PC = PC + 4          # Increment the PC by 4 to preserve alignment

Where, IR denotes the instruction register.

The PC is sent (via control circuitry) as an address to memory. The memory hardware performs a read operation and control hardware transfers the instruction at Memory[PC] into the IR, where it is stored until the next instruction is fetched. Then, the ALU increments the PC by four to preserve word alighment. The incremented (new) PC value is stored back into the PC register by setting PCSource = 00 and asserting PCWrite. Fortunately, incrementing the PC and performing the memory read are concurrent operations, since the new PC is not required (at the earliest) until the next clock cycle.

Instruction Decode and Data Fetch. Included in the multicycle datapath design is the assumption that the actual opcode to be executed is not known prior to the instruction decode step. This is reasonable, since the new instruction is not yet available until completion of instruction fetch and has thus not been decoded.

As a result of not knowing what operation the ALU is to perform in the current instruction, the datapath must execute only actions that are:

• Applicable to all instructions and
• Not harmful to any

Therefore, given the rs and rt fields of the MIPS instruction format, we can suppose (harmlessly) that the next instruction will be R-format. We can thus read the operands corresponding to rs and rt from the register file. If we don’t need one or both of these operands, that is not harmful. Otherwise, the register file read operation will place them in buffer registers A and B, which is also not harmful.

Another action the datapath can perform is computation of the branch target address using the ALU, since this is the instruction decode step and the ALU is not yet needed for instruction execution. If the instruction that we are decoding in this step is not a branch, then no harm is done – the BTA is stored in ALUout and nothing further happens to it.

We can perform these preparatory actions because of the <i.regularity< i=””> of MIPS instruction formats. The result is represented in pseudocode, as follows: </i.regularity<>

• = RegFile[IR[25:21]] # First  operand = Bits 25-21 of instruction
• = RegFile[IR[20:16]] # Second operand = Bits 25-21 of instruction

ALUout = PC + SignExtend(IR[15:0]) << 2 ;   # Compute BTA

Where, “x << n” denotes x shifted left by n bits.

Instruction Execute, Address Computation, or Branch Completion. In this cycle, we know what the instruction is, since decoding was completed in the previous cycle. The instruction opcode determines the datapath operation, as in the single-cycle datapath. The ALU operates upon the operands prepared in the decode/data-fetch step, performing one of the following actions:

• Memory Reference: ALUout = A + SignExtend(IR[15:0])

The ALU constructs the memory address from the base address (stored in A) and the offset (taken from the low 16 bits of the IR). Control signals are set as described on p. 387 opf the textbook.

• R-format Instruction: _{ALUout = A op B}

The ALU takes its inputs from buffer registers A and B and computes a result according to control signals specified by the instruction opcode, function field, and control signals ALUop = 10. The control signals are further described on p. 387 of the textbook.

• Branch: if (A == B) then PC = ALUout

In branch instructions, the ALU performs the comparison between the contents of registers A and B. If A = B, then the Zero output of the ALU is asserted, the PC is updated (overwritten) with (1) the BTA computed in the preceding step, then (2) the ALUout value. If the branch is not taken, then the PC+4 value computed during instruction fetch is used. This covers all possibilities by using for the BTA the value most recently written into the PC. Salient hardware control actions are discussed on p. 387 of the textbook.

• Jump: PC = PC[31:28] || (IR[25:0] << 2)

Here, the PC is replaced by the jump target address, which does not need the ALU be computed, but can be formed in hardware as described on p. 387 of the textbook.

Memory Access or R-format Instruction Completion. In this cycle, a load-store instruction accesses memory and an R-format instruction writes its result (which appears at ALUout at the end of the previous cycle), as follows:

MDR = Memory[ALUout]      # Load

Memory[ALUout] = B        # Store where MDR denotes the memory data register.

For an R-format completion, where

Reg[IR[15:11]] = ALUout   # Write ALU result to register file

the data to be loaded was stored in the MDR in the previous cycle and is thus available for this cycle. The rt field of the MIPS instruction format (Bits 20-16) has the register number, which is applied to the input of the register file, together with RegDst = 0 and an asserted RegWrite signal.

Part 6: Arithmetic Logic Unit(ALU) Design of Computer Architecture

by Jesmin Akther | Jan 16, 2022 | Computer Architecture

Introduction to Arithmetic Logic Unit

In ECL, TTL and CMOS, there are available integrated packages which are referred to as arithmetic logic units (ALU). The logic circuitry in this units is entirely combinational (i.e. consists of gates with no feedback and no flip-flops).The ALU is an extremely versatile and useful device since, it makes available, in single package, facility for performing many different logical and arithmetic operations. Arithmetic Logic Unit (ALU) is a critical component of a microprocessor and is the core component of central processing unit.

Fig.1 Central Processing Unit (CPU)

ALU’s comprise the combinational logic that implements logic operations such as AND, OR and arithmetic operations, such as ADD, SUBTRACT. Functionally, the operation of typical ALU is represented as shown in diagram below,

Fig.2 Functional representation of Arithmetic Logic Unit.

Functional Description of 4-bit Arithmetic Logic Unit.

Controlled by the four function select inputs (S0 to S3) and the mode control input (M), ALU can perform all the 16 possible logic operations or 16 different arithmetic operations on active HIGH or active LOW operands. When the mode control input (M) is HIGH, all internal carries are inhibited and the device performs logic operations on the individual bits. When M is LOW, the carries are enabled and the ALU performs arithmetic operations on the two 4-bit words. The ALU incorporates full internal carry look-ahead and provides for either ripple carry between devices using the Cn+4 output, or for carry look-ahead between packages using the carry propagation (P) and carry generate (G) signals. P and G are not affected by carry in.

For high-speed operation the device is used in conjunction with the ALU carry look-ahead circuit. One carry look-ahead package is required for each group of four ALU devices. Carry look-ahead can be provided at various levels and offers high-speed capability over extremely long word lengths. The comparator output (A=B) of the device goes HIGH when all four function outputs (F0 to F3) are HIGH and can be used to indicate logic equivalence over 4 bits when the unit is in the subtract mode. A=B is an open collector output and can be wired-AND with other A=B outputs to give a comparison for more than 4 bits. The open drain output A=B should be used with an external pull-up resistor in order to establish a logic HIGH level. The A=B signal can also be used with the Cn+4 signal to indicate A > B and A < B.

The function table lists the arithmetic operations that are performed without a carry in. An incoming carry adds a one to each operation. Thus, select code LHHL generates A minus B minus 1 (2s complement notation) without a carry in and generates A minus B when a carry is applied.

Because subtraction is actually performed by complementary addition (1s complement), a carry out means borrow; thus, a carry is generated when there is no under-flow and no carry is generated when there is underflow.

As indicated, the ALU can be used with either active LOW inputs producing active LOW outputs (Table 1) or with active HIGH inputs producing active HIGH outputs (Table 2).

Table1: Function Table for active low inputs and outputs

Notes to the function tables:

1. Each bit is shifted to the next more significant position.
2. Arithmetic operations expressed in 2s complement notation.

H = HIGH voltage level

L = LOW voltage level

Table2: Function Table for active high inputs and outputs

Notes to the function tables:

1. Each bit is shifted to the next more significant position.
2. Arithmetic operations expressed in 2s complement notation.

H = HIGH voltage level

L = LOW voltage level

3. Logic Diagram

Fig.3 Logic Diagram of Arithmetic Logic Unit

Examples for arithmetic operations in ALU

Binary Adder-Subtractor

The most basic arithmetic operation is the addition of two binary digits. This simple addition consists of four possible elementary operations. 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 10. The first three operations produce sum of one digit, but when the both augends and addend bits are equal 1, the binary sum consists of two digits. The higher significant bit of the result is called carry .When the augends and addend number contains more significant digits, the carry obtained from the addition of the two bits is called half adder. One that performs the addition of three bits (two significant bits and a previous carry) is called half adder. The name of circuit is from the fact that two half adders can be employed to implement a full adder.

A binary adder-subtractor is a combinational circuit that performs the arithmetic operations of addition and subtraction with binary numbers. Connecting n full adders in cascade produces a binary adder for two n-bit numbers. The subtraction circuit is included by providing a complementing circuit.

Binary Adder

A binary adder is a digital circuit that produces the arithmetic sum of two binary numbers. It can be constructed with full adder connected in cascade, the output carry from each full adder connected to the input carry of the next full adder in the chain. Fig. 4 shows the interconnection of four full adder (FA) circuits to provide a 4-bit binary ripple carry adder. The augends bits of A and addend bits of B are designated by subscript numbers from right to left, with subscript 0denoting the least significant bit. The carries are connected in the chain through the full adders. The input carry to the adder is C0 and it ripples through the full adder to the output carry C4.The S output generate the required sum bits. An n-bit adder requires n full adders with each output connected to the input carry of the next higher order full adder.

Fig 4: 4-Bit Adder

The bits are added with full adders, starting from the position to form the sum bit and carry. The input carry C0 in the least significant position must be 0. The value of Ci+1 in a given significant position is the output carry of the full adder. This value is transferred into the input carry of the full adder that adds the bits one higher significant position to the left. The sum bits are thus generated starting from the rightmost position and are available for the correct sum bits to appear at the outputs.

The 4 bit adder is a typical example of a standard component. It can be used in many applications involving arithmetic operations. Observe that the design of this circuit by the classical method would require a truth table with 29 = 512 entries, since there are nine inputs to the circuit. By using an iterative method of cascading a standard function, it is possible to obtain a simple and straightforward implementation.

Binary Subtractor

The subtraction of unsigned binary numbers can be done most conveniently by means of complement. Subtraction A–B can be done by taking the 2’s complement of B and adding it to A. The 2’s complement can be obtained by taking the 1’s complement and adding one to the least significant pair of bits. The 1’s complement can be implemented with the inverters and a one can be added to the sum through the input carry.

The circuit for subtracting, A–B, consists of an adder with inverter placed between each data input B and the corresponding input of the full adder. The input carry C0 must be equal to 1when performing subtraction. The operation thus performed becomes A, plus the 1’s complement of B, plus 1.This is equal to A plus 2’s complement of B. For unsigned numbers this gives A–B if A ≥ B or the 2’s complement of (B–A) if A < B. for signed numbers, the result is A – B, provided that there is no overflow.

The addition and subtraction operations can be combined into one circuit with one common binary adder. This is done by including an EX-OR gate with each full adder. A 4-bit adder subtractor circuit is shown in fig 5. The mode input M controls the operation. When M = 0, the circuit is an adder, and when M = 1, the circuit becomes a subtractor. Each EX-OR gate receives input M and one of the inputs of B. when M = 0, we have B (Ex-OR) 0 = B. the full adder receive the value of B, the input carry is 0, and the circuit performs A plus B. when M = 1, we have B (Ex-OR) 1= B’ and C0 = 1. The B inputs are complemented and a 1 is added through the input carry. The circuit performs the operation A plus the 2’s complement of B. (The EX-OR with output is for detecting an overflow.)

Fig 5: 4-Bit Adder Subtractor

It is worth noting that binary numbers in the signed-complemented system are added and subtracted by the same basic addition and subtraction rules as unsigned numbers. Therefore, computers need only one common hardware circuit to handle both type of arithmetic. The user or programmer must interpret the results of such addition or subtraction differently, depending on whether it is assumed that the numbers are signed or unsigned.

 Examples for Logical operations in ALU

In a 4-bit Arithmetic Logic Unit, logical operations are performed on individual bits.

EX-OR

In a 4 bit ALU, the inputs given are A0, A1, A2, A3 and B0, B1, B2, B3. Operations are performed on individual bits. Thus, as shown in a fig.6, inputs, A0 and B0 will give output F0.

Fig.6 Ex-OR Gate                            Table 3: Ex-OR Gate Truth Table

Similarly, for other inputs (A1, A2, A3), outputs (F1, F2, F3) are given.

Also, when active low inputs (A0’, A1’, A2’, A3’and B0’, B1’, B2’, B3’) are taken, logical operation (here Ex-OR) can be done as shown in fig.7.

Fig.7 Ex-OR Gate with active low inputs      Table 4: Truth Table for Ex-OR Gate with active low inputs

Part 5: Control Unit Design of Computer Architecture

by Jesmin Akther | Jan 16, 2022 | Computer Architecture

Introduction of Control Unit and its Design

Control Unit is the part of the computer’s central processing unit (CPU), which directs the operation of the processor. It was included as part of the Von Neumann Architecture by John von

Neumann. It is the responsibility of the Control Unit to tell the computer’s memory, arithmetic/logic unit and input and output devices how to respond to the instructions that have been sent to the processor. It fetches internal instructions of the programs from the main memory to the processor instruction register, and based on this register contents, the control unit generates a control signal that supervises the execution of these instructions.

A control unit works by receiving input information to which it converts into control signals, which are then sent to the central processor. The computer’s processor then tells the attached hardware what operations to perform. The functions that a control unit performs are dependent on the type of CPU because the architecture of CPU varies from manufacturer to manufacturer. Examples of devices that require a CU are:

• Control Processing Units(CPUs)
• Graphics Processing Units(GPUs)

Functions of the Control Unit:

1. It coordinates the sequence of data movements into, out of, and between a processor’s many sub-units.
2. It interprets instructions.
3. It controls data flow inside the processor.
4. It receives external instructions or commands to which it converts to sequence of control signals.
5. It controls many execution units(i.e. ALU, data buffers and registers) contained within a CPU.
6. It also handles multiple tasks, such as fetching, decoding, execution handling and storing results.

Types of Control Unit:

There are two types of control units: Hardwired control unit and Micro programmable control unit.

1. Hardwired Control Unit:

In the Hardwired control unit, the control signals that are important for instruction execution control are generated by specially designed hardware logical circuits, in which we can not modify the signal generation method without physical change of the circuit structure. The operation code of an instruction contains the basic data for control signal generation. In the instruction decoder, the operation code is decoded. The instruction decoder constitutes a set of many decoders that decode different fields of the instruction opcode.

As a result, few output lines going out from the instruction decoder obtains active signal values. These output lines are connected to the inputs of the matrix that generates control signals for executive units of the computer. This matrix implements logical combinations of the decoded signals from the instruction opcode with the outputs from the matrix that generates signals representing consecutive control unit states and with signals coming from the outside of the processor, e.g. interrupt signals. The matrices are built in a similar way as a programmable logic arrays.

Control signals for an instruction execution have to be generated not in a single time point but during the entire time interval that corresponds to the instruction execution cycle. Following the structure of this cycle, the suitable sequence of internal states is organized in the control unit.

A number of signals generated by the control signal generator matrix are sent back to inputs of the next control state generator matrix. This matrix combines these signals with the timing signals, which are generated by the timing unit based on the rectangular patterns usually supplied by the quartz generator. When a new instruction arrives at the control unit, the control units is in the initial state of new instruction fetching. Instruction decoding allows the control unit enters the first state relating execution of the new instruction, which lasts as long as the timing signals and other input signals as flags and state information of the computer remain unaltered. A change of any of the earlier mentioned signals stimulates the change of the control unit state.

This causes that a new respective input is generated for the control signal generator matrix. When an external signal appears, (e.g. an interrupt) the control unit takes entry into a next control state that is the state concerned with the reaction to this external signal (e.g.

interrupt processing). The values of flags and state variables of the computer are used to select suitable states for the instruction execution cycle.

The last states in the cycle are control states that commence fetching the next instruction of the program: sending the program counter content to the main memory address buffer register and next, reading the instruction word to the instruction register of computer. When the ongoing instruction is the stop instruction that ends program execution, the control unit enters an operating system state, in which it waits for a next user directive.

2. Micro programmable control unit:

The fundamental difference between these unit structures and the structure of the hardwired control unit is the existence of the control store that is used for storing words containing encoded control signals mandatory for instruction execution.

In microprogrammed control units, subsequent instruction words are fetched into the instruction register in a normal way. However, the operation code of each instruction is not directly decoded to enable immediate control signal generation but it comprises the initial address of a microprogram contained in the control store.

• With a single-level control store:

In this, the instruction opcode from the instruction register is sent to the control store address register. Based on this address, the first microinstruction of a microprogram that interprets execution of this instruction is read to the microinstruction register. This microinstruction contains in its operation part encoded control signals, normally as few bit fields. In a set microinstruction field decoders, the fields are decoded. The microinstruction also contains the address of the next microinstruction of the given instruction microprogram and a control field used to control activities of the microinstruction address generator.

The last mentioned field decides the addressing mode (addressing operation) to be applied to the address embedded in the ongoing microinstruction. In microinstructions along with conditional addressing mode, this address is refined by using the processor condition flags that represent the status of computations in the current program. The last microinstruction in the instruction of the given microprogram is the microinstruction that fetches the next instruction from the main memory to the instruction register.

• With a two-level control store:

In this, in a control unit with a two-level control store, besides the control memory for microinstructions, a nano-instruction memory is included. In such a control unit, microinstructions do not contain encoded control signals. The operation part of microinstructions contains the address of the word in the nano-instruction memory, which contains encoded control signals. The nano-instruction memory contains all combinations of control signals that appear in microprograms that interpret the complete instruction set of a given computer, written once in the form of Nano instructions.

In this way, unnecessary storing of the same operation parts of microinstructions is avoided. In this case, microinstruction word can be much shorter than with the single level control store. It gives a much smaller size in bits of the microinstruction memory and, as a result, a much smaller size of the entire control memory. The microinstruction memory contains the control for selection of consecutive microinstructions, while those control signals are generated at the basis of nanoinstructions. In nano-instructions, control signals are frequently encoded using 1 bit/ 1 signal method that eliminates decoding

Part 4: Cache Memory & Mapping of Computer Memory Systems

by Jesmin Akther | Jan 16, 2022 | Computer Architecture

Key Characteristics of Computer Memory Systems and Performance of Memory:

Based on three performance parameters performance of Memory:

• Access time (latency): For random-access memory, this is the time it takes to perform a read or write operation
  • For non-random-access memory, access time is the time it takes to position the read–write mechanism at the desired location
• Memory cycle time: This concept is primarily applied to random-access memory and consists of the access time plus any additional time required before a second access can commence
  • This additional time may be required for transients to die out on signal lines or to regenerate data if they are read destructively
• Transfer rate: This is the rate at which data can be transferred into or out of a memory unit
  • For random-access memory, it is equal to 1/(cycle time)
• For non-random-access memory, the following relationship holds:

Where,

T_N = Average time to read or write N bits T_A = Average access time n = Number of bits

R = Transfer rate, in bits per second (bps)

Cache Memory Principles

• The cache contains a copy of portions of main memory
• When the processor attempts to read a word of memory, a check is made to determine if the word is in the cache. If so, the word is delivered to the processor
• If not, a block of main memory, consisting of some fixed number of words, is read into the cache and then the word is delivered to the processor
• When a block of data is fetched into the cache to satisfy a single memory reference, it is likely that there will be future references to that same memory location or to other words in the block

– Locality of reference

Cache Read Operation

Elements Of Cache Design

Mapping Function

Because there are fewer cache lines than main memory blocks, an algorithm is needed for mapping main memory blocks into cache lines. Further, a means is needed for determining which main memory block currently occupies a cache line. The choice of the mapping function dictates how the cache is organized. Three techniques can be used: direct, associative, and set associative.

Cache Memory is a special very high-speed memory. It is used to speed up and synchronizing with high-speed CPU. Cache memory is costlier than main memory or disk memory but economical than CPU registers. Cache memory is an extremely fast memory type that acts as a buffer between RAM and the CPU. It holds frequently requested data and instructions so that they are immediately available to the CPU when needed.

Cache memory is used to reduce the average time to access data from the Main memory. The cache is a smaller and faster memory which stores copies of the data from frequently used main memory locations. There are various different independent caches in a CPU, which store instructions and data.

Levels of memory:

• Level 1 or Register –
  It is a type of memory in which data is stored and accepted that are immediately stored in CPU. Most commonly used register is accumulator, Program counter, address register etc.
• Level 2 or Cache memory –
  It is the fastest memory which has faster access time where data is temporarily stored for faster access.
• Level 3 or Main Memory –
  It is memory on which computer works currently. It is small in size and once power is off data no longer stays in this memory.
• Level 4 or Secondary Memory –
  It is external memory which is not as fast as main memory but data stays permanently in this memory.

Cache Performance:
When the processor needs to read or write a location in main memory, it first checks for a corresponding entry in the cache.

• If the processor finds that the memory location is in the cache, a cache hithas occurred and data is read from cache
• If the processor does notfind the memory location in the cache, a cache miss has occurred. For a cache miss, the cache allocates a new entry and copies in data from main memory, then the request is fulfilled from the contents of the cache.

The performance of cache memory is frequently measured in terms of a quantity called Hit ratio.

Hit ratio = hit / (hit + miss) =  no. of hits/total accesses

We can improve Cache performance using higher cache block size, higher associativity, reduce miss rate, reduce miss penalty, and reduce the time to hit in the cache.

Cache Mapping:
There are three different types of mapping used for the purpose of cache memory which are as follows: Direct mapping, Associative mapping, and Set-Associative mapping. These are explained below.

1. Direct Mapping –
   The simplest technique, known as direct mapping, maps each block of main memory into only one possible cache line. or
   In Direct mapping, assign each memory block to a specific line in the cache. If a line is previously taken up by a memory block when a new block needs to be loaded, the old block is trashed. An address space is split into two parts index field and a tag field. The cache is used to store the tag field whereas the rest is stored in the main memory. Direct mapping`s performance is directly proportional to the Hit ratio.
2. i = j modulo m
3. where
4. i=cache line number
5. j= main memory block number

m=number of lines in the cache

For purposes of cache access, each main memory address can be viewed as consisting of three fields. The least significant w bits identify a unique word or byte within a block of main memory. In most contemporary machines, the address is at the byte level. The remaining s bits specify one of the 2^s blocks of main memory. The cache logic interprets these s bits as a tag of s-r bits (most significant portion) and a line field of r bits. This latter field identifies one of the m=2^r lines of the cache.

DIRECT MAPPING is the simplest technique, known as direct mapping, maps each block of main memory into only one possible cache line. The mapping is expressed as

𝒊 = 𝒋 𝒎𝒐𝒅𝒖𝒍𝒐 𝒎

Where, i = cache line number j = main memory block number m = number of lines in the cache

2. Associative Mapping:
In this type of mapping, the associative memory is used to store content and addresses of the memory word. Any block can go into any line of the cache. This means that the word id bits are used to identify which word in the block is needed, but the tag becomes all of the remaining bits. This enables the placement of any word at any place in the cache memory. It is considered to be the fastest and the most flexible mapping form.

Associative mapping overcomes the disadvantage of direct mapping by permitting each main memory block to be loaded into any line of the cache. In this case, the cache control logic interprets a memory address simply as a Tag and a Word field. The Tag field uniquely identifies a block of main memory. To determine whether a block is in the cache, the cache control logic must simultaneously examine every line’s tag for a match.

3. Set-associative Mapping:
This form of mapping is an enhanced form of direct mapping where the drawbacks of direct mapping are removed. Set associative addresses the problem of possible thrashing in the direct mapping method. It does this by saying that instead of having exactly one line that a block can map to in the cache, we will group a few lines together creating a set. Then a block in memory can map to any one of the lines of a specific set..Set-associative mapping allows that each word that is present in the cache can have two or more words in the main memory for the same index address. Set associative cache mapping combines the best of direct and associative cache mapping techniques.

In this case, the cache consists of a number of sets, each of which consists of a number of lines. The relationships are

m = v * k

i= j mod v

where

i=cache set number

j=main memory block number

v=number of sets

m=number of lines in the cache number of sets

k=number of lines in each set.

Set-associative mapping is a compromise that exhibits the strengths of both the direct and associative approaches while reducing their disadvantages. In this case, the cache consists of a number sets, each of which consists of a number of lines. The relationships are       Where, i =cache set number j= main memory block number m= number of lines in the cache number of sets k= number of lines in each set.

Application of Cache Memory:

1. Usually, the cache memory can store a reasonable number of blocks at any given time, but this number is small compared to the total number of blocks in the main memory.
2. The correspondence between the main memory blocks and those in the cache is specified by a mapping function.

Types of Cache –

• Primary Cache –
  A primary cache is always located on the processor chip. This cache is small and its access time is comparable to that of processor registers.
• Secondary Cache –
  Secondary cache is placed between the primary cache and the rest of the memory. It is referred to as the level 2 (L2) cache. Often, the Level 2 cache is also housed on the processor chip.

Locality of reference:
Since size of cache memory is less as compared to main memory. So to check which part of main memory should be given priority and loaded in cache is decided based on locality of reference.

Types of Locality of reference

5. Spatial Locality of reference
   This says that there is a chance that element will be present in the close proximity to the reference point and next time if again searched then more close proximity to the point of reference.
6. Temporal Locality of reference
   In this Least recently used algorithm will be used. Whenever there is page fault occurs within a word will not only load word in main memory but complete page fault will be loaded because spatial locality of reference rule says that if you are referring any word next word will be referred in its register that’s why we load complete page table so the complete block will be loaded.

Part 3: Interconnection Structure on Computer Architecture

by Jesmin Akther | Jan 15, 2022 | Computer Architecture

Interconnection Structure Overview

• The collection of paths connecting the various modules is called the interconnection structure.
• The preceding list defines the data to be exchanged. The interconnection structure must support the following types of transfers:
  • Memory to processor: The processor reads an instruction or a unit of data from memory
  • Processor to memory: The processor writes a unit of data to memory
  • I/O to processor: The processor reads data from an I/O device via an I/O module
  • Processor to I/O: The processor sends data to the I/O device
  • I/O to or from memory: For these two cases, an I/O module is allowed to exchange data directly with memory, without going through the processor, using direct memory access (DMA) 

BUS Interconnection

• A bus is a communication pathway connecting two or more devices
  • It is a shared transmission medium
  • Consists of multiple communication pathways, or lines, each line is capable of transmitting signals representing binary 1 and binary 0
• Multiple devices connect to the bus, and a signal transmitted by any one device is available for reception by all other devices attached to the bus
• If two devices transmit during the same time period, their signals will overlap and become garbled
  • Only one device at a time can successfully transmit
• A bus that connects major computer components (processor, memory, I/O) is called a system bus

Bus Interconnection Schemes

1. Single Bus

Single Bus Problems:

• Lots of devices on one bus leads to:

Propagation delays:

• Long data paths mean that co-ordination of bus use can adversely affect performance
• Bus may become bottleneck if aggregate data transfer approaches bus capacity

• Most systems use multiple buses to overcome these problems

BUS Structure

• A system bus consists, typically, of from about 50 to hundreds of separate lines
• Each line is assigned a particular meaning or function
• Any bus the lines can be classified into three functional groups: data, address, and control lines
• There may be power distribution lines that supply power to the attached modules 

DATA BUS

• The data lines provide a path for moving data among system modules

– These lines, collectively, are called the data bus

• The data bus may consist of 32, 64, 128, or even more separate lines, the number of lines being referred to as the width of the data bus
• Because each line can carry only 1 bit at a time, the number of lines determines how many bits can be transferred at a time
• Width: If the data bus is 32 bits wide and each instruction is 64 bits long, then the processor must access the memory module twice during each instruction cycle

ADDRESS BUS

• The address lines are used to designate the source or destination of the data on the data bus
• For example, if the processor wishes to read a word (8, 16, or 32 bits) of data from memory, it puts the address of the desired word on the address lines
• The width of the address bus determines the maximum possible memory capacity of the system.
• Typically, the higher-order bits are used to select a particular module on the bus, and the lower-order bits select a memory location or I/O port within the module
• For example, on an 8-bit address bus, address 01111111 and below might reference locations in a memory module (module 0) with 128 words of memory, and address

10000000 and above refer to devices attached to an I/O module (module 1)

 CONTROL BUS

• The control lines are used to control the access to and the use of the data and address lines
• Control signals transmit both command and timing information among system modules
  • Timing signals indicate the validity of data and address information
  • Command signals specify operations to be performed
• Typical control lines include:
  • Memory write, Memory read, I/O write, I/O read, Transfer ACK, Bus request, Bus grant, Interrupt request, Interrupt ACK, Clock, Reset

Interconnection set of components or modules

A computer consists of a set of components or modules of three basic types (processor, memory, I/O) that communicate with each other. In effect, a computer is a network of basic modules. Thus, there must be paths for connecting the modules. The collection of paths connecting the various modules is called the interconnection structure. The design of this structure will depend on the exchanges that must be made among modules.

The below figure suggests the types of exchanges that are needed by indicating the major forms of input and output for each module type.

Memory: Typically, a memory module will consist of N words of equal length. Each word is assigned a unique numerical address (0, 1, . . . , N – 1). A word of data can be read from or written into the memory. The nature of the operation is indicated by read and write control signals. The location for the operation is specified by an address.

I/O module: From an internal (to the computer system) point of view, I/O is functionally similar to memory. There are two operations, read and write. Further, an I/O module may control more than one external device. We can refer to each of the interfaces to an external device as a port and give each a unique address (e.g., 0, 1, . . . , M – 1). In addition, there are external data paths for the input and output of data with an external device. Finally, an I/O module may be able to send interrupt signals to the processor.

Processor: The processor reads in instructions and data, writes out data after processing, and uses control signals to control the overall operation of the system. It also receives interrupt signals.

Bus Interconnection Schemes

2. Multiple-Bus 

                                             Figure: Traditional bus architecture

SCSI : small computer system interface to support local disk drives, CD-ROMs, and other peripherals

Serial: serial port to support a printer or scanner

It is possible to connect I/O controllers directly onto the system bus. A more efficient solution is to make use of one or more expansion buses for this purpose o Allows system to support wide variety of I/O devices o Insulates memory-to-process traffic from I/O traffic.

Bus Arbitration

• More than one module may control the bus
• g. CPU or DMA controller
• Only one module may control bus at one time Arbitration may be centralised or distributed
• Centralised:
• Single hardware device controlling bus access
• Bus Controller
• Arbiter
• May be part of CPU or separate Distributed:
• Each module may claim the bus
• Control logic on all modules

Timing

• Defines co-ordination of events on bus

Synchronous Bus Operation

— Events determined by clock signals

— Control Bus includes clock line

— A single 1-0 is a bus cycle

— All devices can read clock line

— Usually sync on leading edge

— Usually a single cycle for an event

Asynchronous Bus Operation

• Data transfer control on the bus is based on the use of a handshake between the master and the slave

System Bus Read Cycle

• Processor places address and status signals on the bus
• Issues Read command after these signals stabilize indicating presence of valid address and control signals
• Appropriate memory decodes the address and responds by placing data on the data line
• Once data lines have stabilized, memory module asserts the Acknowledge line to signal the processor that data are available
• Once data is read by the master, it deasserts the Read signal
• The memory module drops the data and acknowledge lines
• The master removes the address information.

System Bus Write Cycle

• Master places the data on the data line at the same time as status and address lines
• Memory module responds to the write command by copying data
• Memory module then assert the acknowledge line
• The master drops the write signal and memory module drops the acknowledge signal

Part 2: Computer Structure structural Units or Components

by Jesmin Akther | Jan 14, 2022 | Computer Architecture

Computer Structure: Structural Units/Components

• This is the simplest possible depiction of a computer
• The computer interacts in some fashion with its external environment
• In general, all of its linkages to the external environment can be classified as peripheral devices or communication lines
• There are four main structural components:
• Central processing unit (CPU): Controls the operation of the computer and performs its data processing functions

– Often simply referred to as processor

• Main memory: Stores data
• I/O: Moves data between the computer and its external environment
• System interconnection: Some mechanism that provides for communication among CPU, main memory, and I/O
• A common example of system interconnection is by means of a system bus, consisting of a number of conducting wires to which all the other components attach. 

Top-Level Structure 

Processor Design & Instruction Execution

Overview

• At a top level, a computer consists of CPU (central processing unit), memory, and I/O components, with one or more modules of each type
• These components are interconnected in some fashion to achieve the basic function of the computer
• At a top level, we can describe a computer system by
  1. Describing the external behavior of each component—that is, the data and control signals that it exchanges with other components; and
  2. Describing the interconnection structure and the controls required to manage the use of the interconnection structure
• Virtually all contemporary computer designs are based on concepts developed by John von Neumann at the Institute for Advanced Studies, Princeton
• Such a design is referred to as the von Neumann architecture and is based on three key concepts:
  1. Data and instructions are stored in a single read–write memory
  2. The contents of this memory are addressable by location, without regard to the type of data contained there
  3. Execution occurs in a sequential fashion (unless explicitly modified) from one instruction to the next

Types of Programming

• Two types:
  • Hardwired Programming
  • Software Programming

• Figure b indicates two major components of the system: an instruction interpreter and a module of general-purpose arithmetic and logic functions
  • These two constitute the CPU
• Several other components are needed to yield a functioning computer
• Data and instructions must be put into the system and results must be shown in realizable forms
  • We need I/O module for that
• A place is also needed for storing the data and instructions
• We need Memory for that

GP Processor

• Figure illustrates these top-level components
• CPU exchanges data with memory
• For this purpose, it typically makes use of two internal (to the CPU) registers: a memory address register (MAR), which specifies the address in memory for the next read or write, and a memory buffer register (MBR), which contains the data to be written into memory or receives the data read from memory
• Similarly, an I/O address register (I/OAR) specifies a particular I/O device
• An I/O buffer (I/OBR) register is used for the exchange of data between an I/O module and the CPU

Function of GP Processor

• The basic function performed by a computer is execution of a program, which consists of a set of instructions stored in memory
• In its simplest form, instruction processing consists of two steps:
• The processor reads (fetches) instructions from memory one at a time and executes each instruction
• Program execution consists of repeating the process of instruction fetch and instruction execution
• The processing required for a single instruction is called an instruction cycle

Instruction Fetch and Execute

• In a typical processor, a register called the program counter (PC) holds the address of the instruction to be fetched next
• Unless told otherwise, the processor always increments the PC after each instruction fetch so that it will fetch the next instruction in sequence
• The fetched instruction is loaded into a register in the processor known as the instruction register (IR)
• The instruction contains bits that specify the action the processor is to take
• In general, these actions fall into four categories:
• Processor-memory: Data may be transferred from processor to memory or from memory to processor
• Processor-I/O: Data may be transferred to or from a peripheral device by transferring between the processor and an I/O module
• Data processing: The processor may perform some arithmetic or logic operation on data
• Control: An instruction may specify that the sequence of execution be altered
• For example, the processor may fetch an instruction from location 149, which specifies that the next instruction be from location 182. The processor will remember this fact by setting the program counter to 182
• Thus, on the next fetch cycle, the instruction will be fetched from location 182 rather than 150

A Hypothetical Processor 

The above figure illustrates a partial program execution, showing the relevant portions of memory and processor registers.1 The program fragment shown adds the contents of the memory word at address 940 to the contents of the memory word at address 941 and stores the result in the latter location. Three instructions, which can be described as three fetch and three execute cycles, are required:

1. The PC contains 300, the address of the first instruction. This instruction (the value 1940 in hexadecimal) is loaded into the instruction register IR and the PC is incremented. Note that this process involves the use of a memory address register (MAR) and a memory buffer register (MBR). For simplicity, these intermediate registers are ignored.
2. The first 4 bits (first hexadecimal digit) in the IR indicate that the AC is to be loaded. The remaining 12 bits (three hexadecimal digits) specify the address (940) from which data are to be loaded.
3. The next instruction (5941) is fetched from location 301 and the PC is incremented.
4. The old contents of the AC and the contents of location 941 are added and the result is stored in the AC.
5. The next instruction (2941) is fetched from location 302 and the PC is incremented.
6. The contents of the AC are stored in location 941.

Instruction Cycle State Diagram 

For any given instruction cycle, some states may be null and others may be visited more than once. The states can be described as follows:

1. Instruction address calculation (iac): Determine the address of the next instruction to be executed. Usually, this involves adding a fixed number to the address of the previous instruction. For example, if each instruction is 16 bits long and memory is organized into 16-bit words, then add 1 to the previous address. If, instead, memory is organized as individually addressable 8-bit bytes, then add 2 to the previous address.
2. Instruction fetch (if): Read instruction from its memory location into the processor.
3. Instruction operation decoding (iod): Analyze instruction to determine type of operation to be performed and operand(s) to be used.
4. Operand address calculation (oac): If the operation involves reference to an operand in memory or available via I/O, then determine the address of the operand.
5. Operand fetch (of): Fetch the operand from memory or read it in from I/O.
6. Data operation (do): Perform the operation indicated in the instruction.
7. Operand store (os): Write the result into memory or out to I/O.