Compiler techniques and prefetching

Question 1

What are some good and bad features of compilers?

Answer 1

Good: Has good amount of time to decide what to do

Bad: Has less knowledge about a program

Question 2

When illustrating a pipeline. How can you visualize that some functional units take more than one cycle (e.g. FP)

Answer 2

Draw a loop from the end of the FU to the beginning of it

Question 3

What does compiler optimization aim to fix?

Answer 3

Reduce effect of stalling (hazard, FP operations, etc.)

Question 4

What can the compiler do to reduce the amount of stalls?

Answer 4

Static scheduling
Loop unrolling

Question 5

What is static scheduling?

Answer 5

• Reorder ‘independent’ instructions to places where the program might otherwise have stalls
• If an instruction, that is otherwise independent of other instructions, update the value of a register. If this register is in use by e.g. a load, because this load adds an offset to the register value, we can update this offset to fit the new register value. Meaning, the load address is still preserved.

Question 6

What is loop unrolling?

Answer 6

Place a number of iterations after each other.

If an operation is common for all iterations, e.g. ADD R1, R1, #-8.
If 4 iterations are placed after each other, this ADD can be removed from the iterations and placed at the bottom, but with an updated immediate value:
ADD, R1, R1, #-32

Instead of branching back to the loop label after every iteration, place the branch instruction after the iterations that has been placed after each other.
If 4 iterations are placed after each other, we only need to branch every 4 iterations, instead of the previous 1.

Question 7

How can static scheduling be used with loop unrolling?

Answer 7

When iterations has been layed out, we now have more iterations to possibly be able to reorganize.

An example is if every iteration contains independent ADD-instructions and every iteration contains a LOAD, the loads can first be placed directly after each other, and then the ADDs that are dependent on the loads. As the loads and ADDs now are far enough apart, we won’t need to stall the pipeline.

(Might need to use register renaming to avoid hazards)

Question 8

How can loop unrolling be done for dynamic loops?

Answer 8

Dynamic loops are loops that we do not know how many iterations they have. The number of iterations can for example depend on user input.

Do the unrolling in 2 stages:
- (n mod k), n: iterations, k: number of copies of body
- Execute (n mod k) times the body of the original loop (all the cases not dividable by k, meaning they do not fit the unrolling)
- Unroll the body and execute this (n/k) times

Most of the cases, n is large, meaning most of the time is spent on the unrolled loop.

Question 9

What are some cons of loop unrolling? (3)

Answer 9

Growth in code size: need more flash memory

For large loops: Can get multiple copies of instructions that takes up space in the L1 cache. Can increase instruction cache miss rate.

Register pressure: Requires a lot more registers. If we don’t have enough registers to allocate all live values, might lose all advantage of loop unrolling.

Question 10

What are the 3 types of cache misses?

Answer 10

Compulsary: First-reference miss, miss on infinite cache

Capacity: Would not happen in an infinite

Conflict: Because of restrictions on where a block can be placed. Does not occur in fully associative.

Question 11

What is prefetching?

Answer 11

Speculating on what accesses can happen in the future.

Bring the speculated data from lower parts of the memory hierarchy, and into the caches.

Question 12

What types of cache misses does prefetching aim to fix?

Answer 12

Compulsary misses

Question 13

What are some issues that prefetching needs to deal with?

Answer 13

Prediction: Need good predictions

Timeliness: Data need to be available at the right time.

Resources: Avoid cache and bandwidth pollution. If we use too much prefetching, we are taking up resources.

Question 14

What are some questions we need to consider when doing prefetching?

Answer 14

What addresses to fetch?

When to initiate a prefetch request?

Where in the memory hierarchy to place the prefetched data?

How should prefetching be done? (SW, HW, execution-based, cooperative)

Question 15

Why is it important to be careful when deciding what addresses to prefetch?

Answer 15

Prefetching uses resources, if the data that are prefetched are useless, we are wasting these resources.

(Bandwidth, cache space, prefetch buffer space, energy)

Question 16

How is the metric Accuracy calculated in prefetching?

Answer 16

Accuracy = Useful_prefetches / total_number_of_prefetches

Question 17

How do we know what to prefetch?

Answer 17

Predict based on previous access patterns.

Use the compiler’s knowledge of data structures (useful when doing software prefetching).

Prefetching algorithm.

Question 18

What are some consequences of timing in prefetching?

Answer 18

Prefetch too early: Data might be evicted before used. Can also evict data needed later

Prefetch too late: Data is not ready when requested, meaning the prefetch won’t hide the memory latency

Question 19

What can happen when prefetching is initiated too early?

Answer 19

Data might not be used before it is evicted from cache.

The prefetched data might evict other data that can be requested in the future.

Question 20

What can happen when prefetching is initiated too late?

Answer 20

Prefetching might not be able to hide the whole memory latency.

Question 21

How can a prefetcher be made more timelier?

Answer 21

Making it more or less agressive:
- More ahead of the processor access stream: done in HW, fetching more blocks at the same time, speculating further into the future.

• Move the prefetch instructions earlier or later in the code (done in SW)

Question 22

How can prefetching lead to cache pollution?

Answer 22

If prefetched data is stored in cache, it might evict useful data that would have been used in the future.

Question 23

Where can prefetched data be stored?

Answer 23

Cache:
- Simple to implement
- might cause cache pollution

Separate prefetch buffer:
- more complex design

Question 24

How does prefetch buffers add complexity? (5)

Answer 24

need to decide where to place the buffer.

When to acces the buffer (after cache miss, parallel to cache)

When to move data from buffer to cache

Buffer size

Coherency

Question 25

What are some things we need to decide when we store prefetch data in cache?

Answer 25

Are we treating the prefetch data the same as demand-fetched cache blocks?

As prefetched blocks only are predicted, meaning we do not actually know if they will be used. Might want to skew the replacement policy to favor demand-fetched blocks.

How much in favor should we skew the replacement policy?

Question 26

What are some pros and cons of fetching data to L1 or L2

Answer 26

Cons L1:
- More likely to evict demand-fetched blocks that will be used

Pros L1:
- If predictor is good, will have quicker access to this data

Pros L2:
- Much larger cache, less chance to evict demand-fetched blocks
-

Question 27

How can placement of the prefetcher itself affect performance?

Answer 27

Where the prefetcher is placed in the memory hierarchy, affects what access pattern it sees.

L1: All memory accesses, sees hits and misses

L2: Only sees misses from L1

L3: Only sees misses from L2

More complete access pattern (L1) can potentially give better accuracy and coverage. But because more requests are being examined, it is more bandwidth intensive.

Question 28

How is prefetching performed in hardware?

Answer 28

Have hardware that monitors prosessor accesses.

It memorizes these accesses, and finds patterns/strides within these.

Generate addresses automatically

Question 29

How is prefetching performed in software?

Answer 29

ISA provides prefetch instructions that can be inserted into programs by the programmer or compiler.

These works well only for “regular access patterns”

Question 30

What is execution-based prefetching?

Answer 30

Have a threads thar run ahead of the programs, and for example only performs load instructions.

Can be generated by the SW/programmer or HW

Question 31

How does an adjacent prefetcher work?

Answer 31

HW prefetcher

Prefetch the adjacent block of the block being requested.

Install data in cache

Question 32

How does a strided prefetcher work?

Answer 32

HW prefetcher

Searches for strided accesses (current block + n)

Triggered on successive cache misses.

Question 33

What is an issue with SW prefetching?

Answer 33

Causes instruction overhead
Timeliness: difficult to make sure that prefetched data arrives in cache when needed

Question 34

Give an example of how prefetching can be implemented in SW

Answer 34

for (…) {
prefetch(a[i + 1]);
prefetch(b[i + 1]);
sum = sum + a[i]*b[i]
}

Question 35

How does the intel L2 hardware prefetcher work?

Answer 35

Detects strides

Question 36

How does the intel L2 adjacent prefetcher work?

Answer 36

Fetches a pair of blocks of 128 bytes

Question 37

How does the intel DCU prefetcher work?

Answer 37

Fetches adjacent block into the L1-D cache

Question 38

How does the intel DCU IP prefetcher work?

Answer 38

Per instruction stride detection

Question 39

What are some software prefetching instruction implemented by Intel?

Answer 39

PREFETCH0: Into all levels
PREFETCH1: All levels except 1
PREFETCH2
PREFETCHHNTA: Into all levels, non-temporal data

0, 1, 2: What level to prefetch into

Excluding higher levels from instructions helps with prefetching less data into the smaller caches, and then avoiding evicting important demand-data.

Non-temporal data: Data that won’t be used again.Makes it easy for the replacement policy to know that this data should be evicted.

Question 40

What are some metrics used to evaluate prefetching?

Answer 40

Coverage

Accuracy

Timeliness

Question 41

What is the formula for Coverage?

Answer 41

Coverage = Eliminated_misses / total_misses_without_prefetching

Eliminated misses: Total misses without prefetching, minus the total misses with prefetching

Question 42

What is the formula for accuracy?

Answer 42

A = eliminated_misses / total_number_of_prefetches

Eliminated misses: Total misses without prefetching, minus the total misses with prefetching

Question 43

Formula for timeliness

Answer 43

On time prefetches / Usefull prefetches