CHAPTER 10: PARALLEL PROCESSING

PIPELINED?

Instruction pipelining is a technique that implements a form of parallelism called instruction-level parallelism within a single processor.

It therefore allows faster CPU throughput (the number of instructions that can be executed in a unit of time) than would otherwise be possible at a given clock rate.

PIPELINING LESSONS

•          Pipelining doesn’t help latency of single task, it helps throughput of entire workload.
•          Multiple task operating simultaneously using different resources.
•          Potential speedup = Number of stapes
•          Time to “fill” pipeline and time to “drain” it reduces speeduP

PIPELINE SPEEDUP

1.      If all stages are balanced

Time between instruction (pipelined) = Time between instruction (non-pipelined) I p I    n e e I   d    n    k d k    f y j                                                      Number of stages

2.      If not balanced, speedup is less

3.      Speedup due to increased throughput

4.      Ideally 5 stage pipeline should offer nearly five fold improvement over the 800ps non-pipelined time.

SINGLE CYCLE STAGES

Five stages, one step per stage:                

 

PIPELINE REGISTER

DATAPATH WALKTHROUGHS

e.g:     slti $t2, $t1, 17  # if (t1 < 17) t2 = 1 else t2 + 0

STAGE 1: fetch this instruction, increment PC
STAGE 2: decode to determine it is an slti, then read register $t1
STAGE 3: compare value retrieved in Stage 2 with the integer 17
STAGE 4: idle
STAGE 5: write the result of Stage 3(1 if reg source was less than signed immediate, 0 otherwise) into register $t2

      

      e.g:                                                         

                                                 sw $t3, 17($t1)  # Mem [t1 + 17] = t3                                                      

STAGE 1: fetch this instruction, increment PC

STAGE 2: decode to determine it is a sw, then read register $t1 and $t3

STAGE 3: add 17 to value in register $t1(retrieved in Stage 2) to compute address

STAGE 4: write value in register $t3(retrieved in Stage 2) into memory address computed in Stage 3

STAGE 5: idle(nothing to write into a register)

WHY FIVE STAGES?

Could we have a different number of stages?

= Yes

So why do MIPS have five if instructions tend to idle for at least one stage?

= Five stages are the union of all the operations needede by all th instructions.

SINGLE CYCLE PERFORMANCE

Assume time for stages is

• 100ps for register read or write
• 200ps for other stages

Compare pipelined datapath with single-cycle datapath

PIPELINED HAZARD

A pipeline hazard refers to a situation in which a correct program stop to work correctly due to implementing the processor with a pipeline.

There are 3 fundamental types of hazard:

1.      Data Hazard

Arise when an instruction depends on the results of a previous instruction in a way that is exposed by overlapping of instruction in pipeline.

2.      Structural Hazard

Arise from resource conflicts when the hardware can’t support all possible combinations of overlapping instructions.

3.      Control Hazard

Arise from the pipelining of branches and other instructions that change the PC (Program Counter).

CHAPTER 7: THE PROCESSOR

SINGLE CYCLE CPU DATAPATH

That sure sounds complicated. So let's try making it sounds as simple as we possibly can. 

Before that, you need to know... what is a combinational circuit??

Credits to Google

A combinational circuit is only right if it comes together with some combinational elements.

Introducing the Combinational Logic - half adder & full adder.

Half Adder
- Two inputs and two outputs (carry and sum)

One output will represent sum and the other will represent carry.

Full Adder

- Three inputs and two outputs (carry and sum)

Now, something to not be confuse about - sequential circuit.

What is a sequential circuit??

Credits to Google

Sequential logic circuit is said to be a combinational logic circuit but with the addition of state (memory).

In sequential logic, we have 2 types - synchronous and asynchronous logic. I'm gonna be focusing on the synchronous logic circuit since most CPUs are that type. In synchronous logic, a sequence of repetitive pulses known as the clock signal is distributed to all the memory elements in the circuit. There is a technique known as pipeline, which purpose is to improve the clock rate.

Now, you need to know CPU clocking. Keep in mind that

single cycle = one instruction per second

Clock cycle is typically long to ensure each instruction to complete all stages without interruption. So, each cycle will take a constant amount of time to execute every instruction (in one cycle), regardless of the complexity of the instructions. It can be a big disadvantage of single cycle CPU as it operates at the speed of the slowest instruction to complete the exeution in one clock tick.

One cycle CPU consists of the following:-

Step 1: Instruction fetch (fetched from memory)
Step 2: Decode/ Register read (read the opcode to determine instruction types and field lengths)
Step 3: Arithmetic-Logic Unit (the real work; arithmetic, shifting, logic and comparisons)
Step 4: Memory Access (only for the load and store instructions as the others remain idle)
Step 5: Register write (write the result of some computation into a register)


Multiple cycles CPU on the other hand requires multiple cycles to execute a single instruction. The number of cycles needed to execute a certain instruction is flexible depending on the complexity of the instruction.

In the CPU, there are 2 other parts which is Control Unit and Datapath.

Control Unit
It does not execute any program instructions but instead it tells the datapath what needs to be done. It deals with the ALU and memory.

Datapath
It perform operations required by the program instructions.


To summarize, processor has 4 main functions which are fetch, decode, execute and write back. And the basic elements of a processor are:

1. Arithmetic Logic Unit (ALU)
- which is the core to arithmetic and logic operations

2. Floating Point Unit (FPU)
- specializing in solving numbers quicker than a basic microprocessor circuitry can

3. L1 and L2 cache memory
- saves time compared to retrieving data from the RAM

Briefly, processor is most commonly referred to as the Central Processing Unit (CPU) but

DO YOU KNOW?

CPU isn't the only processor in a computer. There is also Graphics Processing Unit (GPU) and other hardwares performing some processing independently within a computer!

The main competitors for processor in the current market - Intel and AMD

Pheww! Hope you find this post to be somewhat helpful. If there seems to be any mistake, don't hesitate to hit me up! Til then, ALL THE BEST!!

Glossary:

state - In computer science, the state of a digital logic circuit is a term used for all stored information.
clock rate - An indicator to the frequency of the processor's speed.
clock cycle - Measurement for a clock rate is clock cycles per second or the SI unit is known as hertz (Hz).
throughput - Number of instructions completed per second.
CPI - Cycles per instruction


Reference 1
Reference 2
Reference 3
Reference 4

CHAPTER 5: MIPS SIMULATOR

As we know, MIPS is the language for assembly language. But how do we use this language?

Like a pen, we need a piece of paper to write. Paper is the tools for the pen to be functioned. So is the MIPS. MIPS need a software as its platform to function.

5.1 SPIM
   
Spim is a self-contained simulator that runs MIPS32 programs. It reads and executes assembly language(MIPS) programs written for this processor and provides a simple debugger and minimal set of operating system services.
   
There is a few types of Spim and the one that we will learn is QtSpim.

List of Spim
1. spimsal (older version of spim)
2. Spim
3. xSpim
4. PCSpim
5. QtSpim

5.1 QtSpim

QtSpim is the latest version of spim and have been widely used nowaday. It is simpler and easier than previous version. Let's watch a video on how to use QtSpim Simulator!

Hopefully you guys find this information useful. That's all for me, thank you.

Reference 1
Reference 2

CHAPTER 1 : ARITHMETIC FOR COMPUTER ( Number System and Number Conversion)

CHAPTER 4: MIPS (Million Instructions Per Second)

Well hello! *do i need to introduce myself??

       For this chapter, I will be the one who will explain to you what is MIPS. So, what you will learn here is:

      1. MIPS Architecture
      2. Register       3. Comment (#)      4. Assembly Instruction     5. Memory Operand

4.1 MIPS Architecture

          

    - a unit of computing speed equivalent to a million instructions per second.

    - an early RISC processor. RISC processors typically support fewer and much simpler instructions.

4.2 Register

    - limited number of special location built directly into the hardware
    - needd to perform the operation (cannot perform without it)
    - very fast since registers are directly in hardware
    - only 32 registers in MIPS

• why? smaller the register, faster the performance

    - 1 register is 32 bits wide (32 bits = a word)

    - register preceded by $ in assembly language instruction

    - two formats for addressing:

• using register number e.g. $0 through $31
• using equivalent names e.g. $t1, $sp

    - special registers Lo and Hi used to store result of multiplication and division

• not directly addressable: contents accessed with special instruction mfhi ("move from Hi") and mflo ("move from Lo")   

    - stack grows from high memory to low memory

4.3 Comment

      In programming language, we create comment by putting '//' at the front. Hence,in assembly language (coding in MIPS), we use put '#' (hashtag) before the words.

#comment

    - hash (#) is used for MIPS comments

• anything from hash mark to the end of line is a comment
• will be ignored in the coding

4.4 Assembly Instructions

    - in assembly language, instruction is a statement

    - each instruction is executed exactly one with a simple command

    

     Syntax of instructions:

     The arrangement of coding ::       1(ON)  2(Ds),3(S1),4(S2)

     1(ON) ---> operation name (ADD, SUB, etc)

     2(S0)  ---> operand for getting result or we called it ('destination')

     3(S1)  ---> 1st operand for operation called ('source1')

     4(S2)  ---> 1st operand for operation called ('source2')

     example :   add  $s0,$s1,$s2 

    

     - Syntax is rigid

• 1 operator (add,sub, etc), 3 operands >> to keep hardware simple and fast

     :: Addition in assembly

         Example:               add  $s0,$s1,$s2  (in MIPS)

         is equal to:            a = b + c (in C)

   

     :: Subtraction in assembly

         Example:               sub  $s3,$s4,$s5  (in MIPS)

         is equal to:            d = e - f (in C)

4.5 Memory Operand

    

     - Main memory used for omposite data

     - To apply arithmetic operations

• load values from memory into registers
• store result from register to emory

     - memory is byte addressed

• each address identifies an 8-bit byte

     - words are aligned in memory

• address must be a multiple of 4

That's all from me. Hope you enjoys reading mine! Ppyong~

Reference

Reference

                

[EXTRA] CHAPTER 6: LANGUAGE OF THE COMPUTERS - Instruction Set Architecture (ISA)

Based on what I have introduced in the previous post, this time it will be about instruction set. If all I talked about was briefly the languages that computers use, now I will share about how it is being laid out in programs.

The high-level language is used to write out the Instruction Set Architecture (ISA). But first,

WHAT IS AN INSTRUCTION SET?

Instruction set is basically a set of commands that is to be carried out by the Central Processing Unit (CPU) of the computer in terms of machine language.

Simple instructions are made up of bit strings. Inside every instructions there are several important specifications that needs to be encoded.

1. Opcode

The first 6-bit of an instruction set is the opcode (“operation code”). It tells us what operation the CPU must carry out. Mnemonic language is used rather than hexadecimal code for simplicity and readability. 

2. Parameters

The rest of the instruction set contains parameters for the operation to work on. It can have registers, values and etc.

Now, ISA is the main interface between programming language and software with the main hardware component inside a computer. ISAs have unique assembly language that specifies how the program will run in a computer. 

WHERE INSTRUCTIONS ARE STORED?

Since instructions are sets of bit strings, there are mostly many instructions for every program and this requires some space in the memory. Inside the memory, the instructions are lined up in a consecutive manner with an address for each line of instruction. 

The relationship between CPU and Memory

Besides memory, a register also holds data temporarily. Registers can retrieve data whenever it is needed like how a memory works, though only a small volume can be stored. 

Example of instruction set:

MIPS Instruction Set

It uses 32-bit instructions which has R-Type Instructions, I-Type Instructions and J-Type Instructions. The opcode identifies the instruction which allow us to identify the instruction type.

x86 Instruction Set

It is one of the series of computer microprocessor developed by Intel for Intel 8086 CPU. It provides backward compatibility for older piece of hardware or software without the need to modify. Therefore x86 is the most prevalent ISA for desktop use. 

Glossary:

Mnemonic language: In assembly language, mnemonic is used to abbreviate various operations.
Parameters: Characteristics to customize a program.
Address: A unique number given to specify a particular set of instruction in memory.
Registers: Very small volume of memory located in the CPU itself.
Bit string: A sequence of bits that is represented by binary data. 


References:

Source 1
Source 2
Source 3

Picture credits:

https://www.eeweb.com/electronics-quiz/instruction-set-architecture
http://blog.biicode.com/bitscan-cpp-library-bit-strings/
http://math.hws.edu/javanotes/c1/s1.html

Ok so hope that summarizes what ISA is all about. Feel free to check out other topics for this syllabus! Your comments are highly welcome.

Til' next time, thanks for reading!

CHAPTER 3 : DIGITAL LOGIC SIMULATOR

Definition :

• A logic simulator is a computer program that allows designers and experimenters to conduct virtual tests of complex digital circuitry before working with any hardware.

Multimedia logic : is a drag and drop out logic design software. You can draw your logic design on the white canvas and then we cam simulate the circuit.

YOU CAN WATCH THIS VIDEO FOR YOUR REFERENCES !!!

There are some links for you guys to get the software with FREE !!!

Download 1

Download 2

• After downloaded and installed the software, you open it and will show you this :

• Then, you can draw your own logic design on the white canvas using "Palette" :

                                                                                 

SIMPLE STEP ON HOW TO CREATE A SIMPLE "OR" CIRCUIT

STEP 1 : Find logic OR in the palette, click the OR gate and place it(click) on the canvas.

STEP 2: Find the switch and click the switch, place on the canvas near the input of the gate.

The switch would like the figure below.

The purpose of using the switch is to test the truth table. If the switch is flipped up, it means 1 and 0 if it is flipped down.

STEP 3: Find the LED icon and place it front of the output of the gate.

Do not confuse with the 7 LED Segment!

STEP 4: To connect the component, use wire icon to connect each dot to the respective gate. Click at one end and drag to the other end.

STEP 5: Labels the input and output accordingly. Find icon capital A(that refers to Text label) and click next to the input. To edit the text, click the mouse palette on the palette(it will indicate as a selector) and double click the label Text to open Text properties. Type the input label on Text box. Click OK.

STEP 6: Simulate the logic by clicking the Simulate menu, choose Run. Or you can just click the Play button to run the simulation.

Test OR truth table by clicking the switch to see whether LED will light on if the condition met. In this logic, only when the switches is set to 1 then LED will light RED.

To stop the simulation, press STOP button.

This circuit can be saved into .lgi file or printed by using the file menu.

References :

Source 1

Source 2

Source 3