Single Processor Computing

Question 1

Von Neumann Architecture

Answer 1

A stream of instructions executed in an order

Question 2

Control Flow

Answer 2

A prescribed sequence of instructions

Question 3

Stored Program

Answer 3

Instructions and program data stored in the same memory

Question 4

Fetch, Execute, Store

Answer 4

Load next instruction onto processor,
Operation is executed
Writes content back to memory

Question 5

Direct To Memory Architecture

Answer 5

Allows data to be directly sent to and from memory to processors.

Work stays in the memory

Question 6

Out-of-order instruction handling

Answer 6

Instructions can be processed in a different order.

Question 7

Why do modern processors use out-of-order instruction handling?

Answer 7

Increased performance with pipelining.

Question 8

Pipelining

Answer 8

Allowing the CPU to work on multiple smaller instructions at the same time.

Question 9

Execution time for pipelined instructions?

Answer 9

t(n) = (n + n[1/2])x

x = basic operation time
n = Linear operation time
n[1/2] = Sublinear operation time.

Question 10

Instruction level parallelism (ILP)

Answer 10

Finding independent instructions and running them in parallel.

Question 11

Speculative Execution

Answer 11

Assumes the test will turn out true or consistent.

Question 12

Prefetching

Answer 12

Data can be speculatively requested before any instruction needing it is actually encountered.

Question 13

Branch Prediction

Answer 13

Guessing whether a conditional instruction will evaluate to true and executing accordingly.

Question 14

von Neumann bottleneck

Answer 14

Transferring data from memory takes more time than actually processing the data.

Question 15

How does the memory hierarchy address the von Neumann bottleneck?

Answer 15

By reducing the number of times the CPU has to wait for data to be transferred

Question 16

Latency

Answer 16

The delay between the processor issuing a request from a memory item and the item arriving.

Question 17

Bandwidth

Answer 17

The rate at which data arrives at its destination after the initial latency is overcome.

Question 18

What role do registers play in the memory hierarchy?

Answer 18

Registers are the fastest and allow the CPU to access data instantly without going to slower caches or memory.

Question 19

What role do cache systems play in the memory hierarchy?

Answer 19

Cache stores frequently accessed data that the CPU might need without having the CPU go to the main memory.

Question 20

Cache Tags

Answer 20

Info keeping track of the location and status of data in the cache.

Question 21

What are the 3 types of cache misses in single-processor systems?

Answer 21

Compulsory: Caused when data is first accessed and is not present in the cache.

Capacity: Caused by data having been overwritten because the cache can not contain all your problem data.

Conflict: Caused by one data item being mapped to the same cache location as another.

Question 22

What additional type of cache miss occurs in multi-core systems?

Answer 22

Coherence: multiple processor cores have copies of the same data in their cache, but those copies become inconsistent due to changes.

Question 23

What two properties of typical program memory access patterns are exploited by cache systems?

Answer 23

Temporal Locality: When a memory location is accessed, it is more likely to be accessed again.

Spatial locality: When a memory location is accessed, it is likely that nearby memory locations will also be accessed.

Question 24

LRU Replacement Policy

Answer 24

Least Recently Used

Question 25

FIFO Replacement Policy

Answer 25

First In First Out

Question 26

Cache Line

Answer 26

The smallest unit of data on a cache.

Question 27

What property of program memory accesses do cache lines exploit?

Answer 27

Spatial locality.

Question 28

What effect does stride have on cache line efficiency?

Answer 28

If the cache line is large, then having a large stride means we'll only access a small part of it. If the cache line is very small, then striding wouldn't necessarily cause a problem.

Question 29

Cache Mapping

Answer 29

Deciding how data is stored on the cache.

Question 30

Direct Mapped Cache

Answer 30

Each memory block is mapped to only one specific cache location.

Question 31

Fully associative cache

Answer 31

Each memory block can be mapped to any cache location.

Question 32

K-way set associative cache

Answer 32

The cache is divided into a number of sets, each containing k cache lines.

Question 33

Cache Memory

Answer 33

Small, fast memory used to store frequently accessed data

Question 34

Dynamic Memory

Answer 34

Data that is currently being executed.

Question 35

Stall

Answer 35

Delay in the execution of instructions caused by a dependency between instructions.

Question 36

Cache Miss

Answer 36

When the data is not available in the cache and has to be fetch from main memory.

Question 37

Prefetch data stream

Answer 37

When the processor tries to predict what data will be accessed and fetch that data to the cache.

Question 38

What is a hardware prefetch and how is it different from a prefetch intrinsic?

Answer 38

Intrinsic = Controlled by software Hardware = Controlled by hardware

Question 39

What is Little’s Law? What does it tell us about the effect of latency on computing systems?

Answer 39

Concurrency = Bandwidth X Latency. Increasing latency will increase the build-up of requests and reduce performance.

Question 40

Why are memory banks used in memory systems?

Answer 40

To increase memory bandwidth. If multiple requests target the same bank (bank conflict), the requests must be handled in serial, which reduces memory bandwidth.

Question 41

What is a bank conflict?

Answer 41

When two consecutive operations access the same memory bank at the same time.

Question 42

What is the TLB? What function does it have in the memory hierarchy?

Answer 42

Translation Look-aside Buffer: a cache of frequently used page table entries, providing fast address translation of pages. If a program needs a memory location, the processor first checks the TLB, else it looks up the page in the main memory.

Question 43

What property would a program have that would cause performance degradation due to TLB misses?

Answer 43

Poor spatial locality

Question 44

How big is a typical TLB?

Answer 44

Between 64 and 512 entries.

Question 45

What are cache-aware and cache-oblivious algorithms?

Answer 45

Aware: Designed to take advantage of specific cache sizes. Oblivious: Designed to perform well on a wide range of sizes without requiring any knowledge of cache parameters.

Question 46

What is loop tiling and what is it used for?

Answer 46

Breaking up loops into smaller, nested loops to increase performance

Question 47

What is the motivation for multi-core architectures?

Answer 47

Separate cores can work on unrelated tasks, or introduce data parallelism.

Question 48

Define Core, Socket, and Node

Answer 48

Core: General Processing Unit of Distributed memory Socket: Connects a CPU to the motherboard Node: Contains multiple sockets accessing the same shared memory

Question 49

Cache Coherence

Answer 49

Ensuring all cached data are an accurate copy of the main memory.

Question 50

False Sharing

Answer 50

When multiple threads access different variables located in the same cache line.

Question 51

NUMA

Answer 51

Non-uniform memory access: For a processor running on some core, the memory attached to its socket is faster to access than the memory attached to another socket.

Question 52

First touch phenomenon

Answer 52

Dynamically allocated memory is not allocated until it’s first written to.

Question 53

What is arithmetic intensity and how do we compute it?

Answer 53

Number of operations per memory access. f(n) / n where f(n) is the number of operations it takes, and n is the number of data items that an algorithm operates on.

Question 54

What is the roofline model? What defines the roofline?

Answer 54

Visually expresses the arithmetic intensity and performance limits. Performance limit defines the roofline.

Question 55

How can we use the roofline model to optimize code performance?

Answer 55

To see if the code is limited by hardware or arithmetic throughput.