Combinational vs sequential circuits

Clocking mechanism

• Defines when signals can be read and when they can be written.
  • To avoid situations like reading and writing happening at once.
• Needed to make the hardware behaviour predictable (and thus make it reliable).
• Edge-triggered clocking: state changes happen on clock edges.
  • ie, during transition from low → high or high → low.

MIPS

• A RISC architecture with many similarities with RISC-V.
• Microprocessor without Interlocked Pipeline Stages (MIPS).
• Assembly instructions are written using a different notation (uses $ sign).
• Like RISC-V, has optional extensions.
• Development has ceased by 2021 as the MIPS company is transitioning to RISC-V instead (announcement in March 2021).

Design principles

• Simplicity over regularity.
• Good design demands good compromises.

Instructions

• Arithmetic instructions can operate using 2 registers.
• Data transfer instruction can read/write using 1 register but cannot operate on them.
• R-type, I-type

A list of instructions

• `ld` instruction: load doubleword
• `sd` instruction: store doubleword
• `srai`: shift right arithmetic immediate
• `beq rs1, rs2, L1`: branch if equal

RISC-V fields

• opcode: indicates the instruction
• rd: destination register. Gets result of operation
• funct3: additional opcode field
• funct7: additional opcode field
• rs1: first source register
• rs2: second source register

RISC-V calling conventions for registers

Reference: https://riscv.org/wp-content/uploads/2015/01/riscv-calling.pdf

• x10 to x17: used for parameter passing
• x1: return address for procedures [²]¹
• x5 to x7 and x28 to x31: temporary registers (not preserved by the callee)
• x8 to x9 and x18 to x27: saved registers? (callee, ie called fn, maintains original value when returning)

I-type instruction format

R-type instruction format

S-type instruction format

Execution time (ET)

• aka response time.
• Time between the start and completion of an event.

ET = IC * CPI * T

where:

• IC: Instruction count
• CPI: Clock cycles per instruction
• T: Clock period (ie, 1/ν)

IC, CPI and T have an orthogonal relationship. We can't decrease one while keeping the other two same.

Decrease in one might lead to increase in the other two.

Ideally we would like all three to be minimized. But can't do it.

Performance

Performance = (1 / ET)

Speedup

speedup = (performance with enhancement) / (performance without enhancement)

which is same as

speedup = (ET with enhancement) / (ET without enhancement)

Amdahl's law

• Expresses the law of diminshing returns.

Speedup via parallelism is limited by that component of the application which cannot be enhanced (ie, the sequential component).

If a fraction (1-E) of the execution time E of an application cannot be enhanced for parallel implementation, then speedup is limited by a factor of 1 / (1-E).

Single cycle datapath

• Everything that needs to be done is done in the same clock cycle.
• Clock frequency will be low, as clock period is more. (bad)
• But CPI is also low (=1 ?) (good)

TODO Multi cycle datapath

Register file

• All 32 general purpose registers of the processor are stored in a structure called a register file.
• Any register in it can be accessed by specifying its number (register number).
• Register number input here is just 5 bits (2⁵ = 32) and is not 64 bits wide.

Program Counter (PC)

PC = PC + 4 (ie, 4 bytes = 32b)

Cache memories

Flash memory

• An Electrically Erasable Programmable ROM (EEPROM).
• Non volatile.

Advantages

• Allows a single program to expand its address space beyond the limits of the main memory.
• Allows sharing of main memory between different processes in a secure manner.

Virtual address

• Virtual page number
• Page offset

Translation Lookaside Buffer (TLB)

• Helps in translating virtual addresses to physical addresses.
• A special cache. Keeps track of recently used translations.
  • Simply loads physical address and protection tags from the (last level) page table.
• Effectively a 'translation cache'.
• When TLB is there, it is consulted before page register.
  • So TLB needs status bits like valid bit, dirty bit, etc.
• Needs status bits for:
  • valid bit
  • dirty bit
  • reference bit :: useful when LRU page replacement algorithm is used. Helps to find entries which were recently referenced/used.

RISC-V pipeline stages

RISC-V instruction set was designed to be pipelined.

IF → ID → EX → MEM → WB

 - IF  = Instruction fetch
 - ID  = Instruction decode
 - EX  = Execute operation
 - MEM = Data memory access
 - WB  = Write back results

RISC-V instructions classically take 5 steps:

1. Fetch instruction from memory.
2. Read registers and decode instruction.
3. Execute operation or calculate address.
4. Access operand in data memory if needed.
5. Write results back into a register if needed.

ie, the datapath is separated into 5 pieces, with each corresponding to a pipeline stage.

RISC-V

RISC-V instruction set was designed to be pipelined.

A RISC-V instruction takes 5 steps:

• Instruction fetched from memory
• Read registers and decode instruction
• Execute operation or calculate address
• Access operand in data memory (if needed)
• Write result into register (if needed)

ie, RISC-V pipeline consists of 5 stages.

Thankfully, in RISC-V:

• instructions are all of the same length (32b). Much easier to do pipelining.
  • en fait, x86 translate their instructions into regular instructions similar to RISC-V instructions.
• only few instruction formats.
• source and destination register fields are located in the same place in every instruction
• only load/store instruction have operands in memory => we can use execute stage (stage 3) to calculate memory address. (TODO: What's the advantage?)

Structural hazards

• Hardware can't support instruction combination that we wish to execute in the same clock cycle.
  • ie, a planned instruction can't execute in the proper clock cycle because the hardware doesn't support the combination of instructions that are set to execute.
  • eg: A functional unit that is needed is not available.

Data hazards

• Pipeline is stalled because one step of an instruction instruction cannot execute till one step of a previous instruction finishes.
  • due to dependence of an instruction on an earlier instruction that is still in the pipeline.

-- a RAW dependency
-- because add instruction won't produce output till stage 5 (WB)
-- whereas sub needs the input at stage 3?? (EX)
-- 3 clock cycles got to be spent waiting.
add x5, x6, x7
sub x8, x5, x8

-- I guess it would look something like
--
-- IF ID EX MEM WB
-- b  b  b  b   IF ID EX MEM WB
--
-- where b denotes a bubble/stall

add x1, x2, x3
sub x4, x1, x5

IF ID EX MEM WB
       ↓
       -→-
         ↓ 
   IF ID EX MEM WB

add x5, x6, x7   -- new value written to x5
sub x1, x5, x2   -- new value of x5 is being used

Control hazards

• aka branch hazard.
• arises from the need to make a decision based on the results of one instruction while others are executing.

Types of multiple issue processors

• Many types of multiple issue processors are there.
  • Differs in terms of the division of work between the compiler and processor
  • Decisions made statically compiler itself: Static multiple issue.
  • Decisions made dynamically at run-time: Dynamic multiple issue.
  • Usually practical multiple issue processors are a blend of static and dynamic.

Static multi issue processors

• Compiler usually does something to handle control and data hazards as well.
  • Like code rescheduling to reduce hazards, and static branch prediction.

Dynamic multi issue processors

• Dynamic multi issue processors are often termed superscalars.

Factors to consider in multiple-issue designs

• Packaging instructions into issue slots.
• Dealing with data and control hazards.

Out-of-order execution

• Instructions can be executed in a different order than the one in which they were fetched.
• Processor executes instructions in an order that preserves the data flow order of the program.

In-order issue → Out-of-order execution → In-order commit

Loop unrolling

• A technique employable by the compiler to enhance possibility of parallelism.
• Body of loop is 'unrolled' to have more ILP (instruction level parallelism) available by overlapping instructions from different iterations.
• Disadvantage :: More register resources needed.
  • More register pressure.
  • Increase in concurrency demands more resources.

// Following loop:
for(int i=0; i<16; ++i) {
  c[i] = a[i] + b[i];
}

// could be unrolled once to make it
for(int i=0; i<16; i+=2) {
  c[i] = a[i] + b[i];
  c[i+1] = a[i+1] + b[i+1]
}

Register renaming

• Eliminates dependencies that aren't true dependencies (ie, RAW data dependencies).
• For instructions that can be made independent if different register was used.
  • Because they just look like they are dependent but aren't actually so.
  • This is because of name dependence or antidependence.
  • No data values flow between the antidepedent instructions.
  • Because the 'dependence' is forced purely by the reuse of a name.
• Register renaming eliminates name dependencies while preserving true dependencies.
• Disadvantage :: More register resources needed.

-- WAR data dependency here
add x4, x2, x1
and x1, x2, x0

-- circumvented by renaming reg x1 → x3 in the `and` instruction
add x4, x2, x1
and x3, x2, x0

-- WAW data dependency here
add x9, x2, x1
and x9, x3, x1

-- circumvented by renaming reg x9 → x5 in the `and` instruction
add x9, x2, x1
and x5, x3, x1

Instruction reordering

ld x1, 0(x0)
ld x2, 4(x0)
add x3, x1, x2
sd x3, 12(x0)
ld x4, 8(x0)
add x5, x1, x4
sd x5, 16(x0)

could be made

ld x1, 0(x0)
ld x2, 4(x0)
ld x4, 8(x0)     -- reordered this instr
add x3, x1, x2
sd x3, 12(x0)
add x5, x1, x4
sd x5, 16(x0)

-- ie, here we just grouped the loads together and
-- the (data) hazard disappeared.

Latency of an instruction

Essentially time taken to finish executing that instruction. ie, its execution time.

nops

• An instruction that does nothing. Just filler.
• No operation.
• Does not change state.
• Acts essentially like a stall/bubble in the pipeline.
• Not counted while calculating CPI or IPC as it plays no role in enhancing performance.

PC relative addressing

• Addressing scheme where: address = PC + constant
• RISC-V uses PC-relative addressing for both conditional branches and jumps as the destination instruction tends to be located close by.

EPIC

Explicitly Parallel Instruction Computing

VLIW

• Very Large Instruction Word
• An ISA that launches many operations (that are defined to be independent) in a single 'wide' instruction.
• Multiple (independent) instructions are bundled together into a long instruction.

Execution time PERFORMANCE

Non-leaf procedures: Max element of array ASSEMBLY

# max-2
max2:
  bge x10, x11, max2end
  add x10, x11, x0
max2end:
  jalr x0, 0(x1)


# Maximum
maximum:
  # Initialize max and i
  ld x30, x5       # max = arr[0]
  addi x7, x0, 1   # i=1

loop:
  # Find offset
  slli x29, x7, 3  # offset=i*8

  # Find address of arr[i]
  add x29, x29, x5 # offset = offset + &arr[0]

  # Load arr[i]
  ld x10, 0(x29)   # cur = arr[i]

  # push return address to stack
  addi sp, sp, -8
  sd x1, 0(sp)

  # Call max2
  jal x1, max2

  # pop original return address from stack
  ld x1, 0(sp)
  addi sp, sp, 8

  # Copy return value
  add x30, x10, x0 # max = max2(max, cur)

  # Increment i
  addi x7, x7, 1   # i=i+1

  # Loop exit condition
  bne x7, x6, loop

  # Load storage address
  lui x31, 3345a
  addi x31, 204

  # Store result
  sd x30, 0(x31)

Non-leaf procedures: Factorial ASSEMBLY

long long int fact (long long int n) {
    if (n < 1) {
        return f;
    } else {
        return n * fact(n - 1);
    }
}

fact:
    bgt  x10, x0, recurse    # non-base case: n > 0
    addi x10, x0, 1          # return 1
recurse:
    addi  x2, x2, -16        # expand stack (x2 is SP)
    sw x10, 8(x2)            # save n to stack
    sw x1, 0(x2)             # save return address to stack
    addi x5, x10, -1         # calculate (n - 1)
    add x10, x5, x0          # set up (n-1) as argument to next function call
    jal x1, fact             # recursive function call
    lw x1, 0(x2)             # retrieve original return address
    lw x5, 8(x2)             # retrieve original n
    mul x10, x5, x10         # set up return value as (n * fact(n-1))
                             # mul available only in RV64M mulitply extension
over:
    jalr x0, 0(x1)           # return from fact() to caller function

Procedure calls PERFORMANCE

Unaddressed

• 2.4: First commercial computer was a decimal computer?

• Is li (load immediate) a RISC-V instruction? Mentioned in page 136 but not in the reference card.

• Which RISC-V assembler is being talked about in section 2.12 (page 124)

• Any difference between li x5 100 and addi x5 x0 100 performance-wise? (though li is a pseudo-instruction)

• Why the 0(x23) needed even when the offset is zero? Is it mandatory for some instructions like ld x6, 0(x5)?

• Class: ALU does 64b but then why registers only 32b?

Datapaths

-- d'accord matters here
add x1, x2, x3
add x1, x1, x4

add x1, x2, x3
add x1, x4, x4

RISC-V extensions

• M: Multiply instructions
• F: Floating point

Memory hierarchy

• p371: "SRAMs typically use 6-8 transistors per bit to prevent the information from being disturbed when read". Why this disturbance?

• [INFORMAL] p373: harddsik: 'entire drive is permanently sealed to control the en inside the drive': does that mean that if you open in it ourselves, it will no longer function if we put it back together.

• p374: all disk heads will be on the same track. Why this restriction? Any advantage?

• p375: does the speed at which the disks rotate have any bearing on its efficiency?

• Difference between l1/l2/l3 caches. Technology is different as wel?

  • What are caches usually made of anyway? SRAM?

• Cache miss => Instruct main memory for a read is same as a complete load instruction (maybe without instruction decode phase)?

• p400: Set associativity for caches with content addressible memories upto how much? Book says 8 and above.

• Increase in block size of cache means: advntge: more cache hits disadvntge: increase in miss penalty; any other disadvantages like more complex hardware maybe?

• What's the reason for using $ sign to denote cache? Is it really because it sounds like 'cash' or is there another reason?

• Regarding the section on VMs in textbook (p416): if we are running a single VM in our laptop, how does the hypervisor act? Does it manage both the host OS (our computer's os) and the guest OS (os used in the VM)? Or does the hypervisor play a greater role only when multiple guest VMs are running? Is hypervisor something that's part of the hardware or something that's software? What does enabling virtualization in the BIOS mean? Is it same as enabling hypervisor or something? Hypervisor sort of translates the instructions issued by the guest systems to that of host and maps the hardware to be used by the guests to actual hardware of the host, right?

• Are the secondary storage in smart phones flash memory? Is it so even in the old Nokia phones (with a physical keypad and all)? Or did they start being used in phones only after smart phones were made? Is this the kind of memory used even in small devices which can store just a few numbers like a glucose meter or a similar device being able to remember the last few measurements?

• p421: Virtual memory: RISC-V has 64 bit address but upper 16 bits are not used. Virtual address is 48bits. Why upper bits not used? (It later says that RISC-V also supports 39b and 57b virtual address spaces as well)

• Virtual memory: Which component does the virtual to physical address translation? How does it manage if we expand the physical memory by replacing the RAM with one of a higher capacity? Range of physical addresses would change right? So the addressing mapping part would also need to change.

• Virtual 'memory: A page fault to disk would result in millions of clock cycles to process'. Why would it need that many cycles? Does a typical harddisk access really take that long? And is an SSD faster than an HDD because the number of cycles needed for SSD is lesser?

• DONE p385: how many clock cycles or part of a clock cycle would it take to service a cache miss? So if the pipeline must stall? It's not stalling for just a few pipeline stages, but for entire clocks?

• DONE p385: Cache miss okay. But what's a write-miss? What could be missed when writing?