Computersysteme

Half Adder

Full Adder

Carry Lookahead Adder Propagate

ALU Control

Wann ist bei der ALU die Flag Z gesetzt?

all of the bits of Result are 0

Wann ist bei der ALU C gesetzt?

Cout of Adder is 1 AND ALU is adding or subtracting (ALUControl is 00 or 01)

Wann ist bei der ALU das overflow Bit gesetzt?

ALU is performing addition or subtraction (ALUControl1 = 0) AND A and Sum have opposite signs AND A and B have same signs for addition (ALUControl0 = 0) OR A and B have different signs for subtraction (ALUControl0 = 1)

Wie werden bits im DRAM gespeichert?

In einer Kapazität.

DRAM Speicher

SRAM Speicher

PLAs (Programmable logic arrays)

AND array followed by OR array

Combinational logic only

Fixed internal connections

FPGAs (Field programmable gate arrays)

Array of Logic Elements (LEs)

Combinational and sequential logic

Programmable internal connections

FPGAs Bestandteile

LEs (Logic elements): perform logic

IOEs (Input/output elements): interface with outside world

Programmable interconnection: connect LEs and IOEs

Some FPGAs include other building blocks such as multipliers and RAMs

LE’s (Logic Elements) bestehen aus:

LUTs (lookup tables): perform combinational logic

Flip-flops: perform sequential logic

Multiplexers: connect LUTs and flip-flops

Execution Time

= (#instructions)(cycles/instruction)(seconds/cycle)

CPI

Cycles/instruction

clock period

seconds/cycle

IPC

instructions/cycle = IPC

ALU Control erweitert

Single cycle Critical Path

𝑻𝒄_𝒔𝒊𝒏𝒈𝒍𝒆 = 𝒕𝒑𝒄𝒒_𝑷𝑪 + 𝟐𝒕𝒎𝒆𝒎 + 𝒕𝑹𝑭𝒓𝒆𝒂𝒅 + 𝒕𝑨𝑳𝑼 + 𝒕𝒎𝒖𝒙 + 𝒕𝑹𝑭𝒔𝒆𝒕𝒖𝒑

Multicycle critical path:

Temporal Locality:

Locality in time

• If data used recently, likely to use it again soon

• How to exploit: keep recently accessed data in higher levels of memory hierarchy

Spatial Locality:

• Locality in space

• If data used recently, likely to use nearby data soon

• How to exploit: when access data, bring nearby data into higher levels of memory hierarchy too

Hit Rate

Miss Rate

Capacity Cache

Number of data bytes in cache

Block Size

Bytes of data brought into cache at once

Number of Blocks

Number of blocks in cache

𝐵 = 𝐶 /b

Degree of associativity (𝑵)

Number of blocks in a set

Number of sets (𝑺)

Each memory address maps to exactly one cache set

𝑆 = B / N

Direct Mapped

1 block per set

N-way set associative

N blocks per set

Fully associative

all cache blocks in 1 set

LRU (Replacement policy)

the least recently used block in a set evicted

„Am längsten nicht verwendet“

Complex to implement

LFU

the least used used block in a set evicted

“Am wenigsten verwendet”

A frequently referenced page is only replaced after many misses and thus blocks the cache

Reference bit

it is a approximated versions of Least Recently Used (LRU)

A bit is set on access and cleared in time intervals

Write hit: Write through (cache)

update the cache AND update the main memory immediately

Pros: Data consistency with main memory guaranteed (I/O, multiprocessor)

simple

Cons:

Frequent accesses to the main memory

Loss of performance

Write-Hit: Copy-Back

refresh the cache AND marks the block "dirty" only update the main memory later when the block is removed from the cache

often also referred to as write-back

Pros:

Write hit is much faster

Less frequent accesses to the main memory

Cons:

Data inconsistency with the main memory

Read miss is slower (due to copy-back)

A dirty block needs to be synced before replacing

N-Way set associative (Management data/bits)

Tag

Valid Bit

(Dirty Bit)

Bits for Replacement Policy

Number of Blocks:

Number of Sets * Ways

Direct Mapped (Management Data Bits)

Tag

Valid Bit

(Dirty Bit)

Page Size

amount of memory transferred from hard disk to DRAM at once

Page table

lookup table used to translate virtual addresses to physical addresses

Adress Translation

Virtual Pages Example:

Page Table Organisation

Entry for each virtual page

Entry fields:

Valid bit: 1 if page in physical memory

Physical page number: where the page is located

What is VPN ?

index into page table

Control Hazard

When the flow of instruction addresses is not sequential

Unconditional branches (jal, jalr)

Conditional branches (beq, bne, ...)

Exceptions

Branch Target Buffer

CPI (Rechnung)

Dynamic Branch Prediction: 1-Bit Predictor

2-Bit Predictor:

2-stage Multiplier

^

Steps in Out-of-Order Execution (Simpler Scheme 2**)

Pseudo Instructions