Thread and data level parallelism

Question 1

What is the difference between instruction-level-, thread-level- and data-level parallelism?

Answer 1

TLP increases overall throughput

ILP and DLP focus on increasing the IPC

Question 2

What is ILP?

Answer 2

Exploits parallelism within a program, e.g. OoO-to be able to execute multiple instructions simultaneously. (loops, etc.)

Question 3

What is TLP?

Answer 3

Exploits parallelism between independent threads. Running more applications in parallel, increases overall system performance.

However, does not necessarily make the individual applications perform better/faster.

Question 4

What is DLP?

Answer 4

Exploits parallelism by operating on multiple data points simultaneously. E.g. if a loop updates all elements of an array, can instead tell the program that a certain operation is to be done to all elements in the loop. Then this operation would be run at the same time for all array elements.

Question 5

What is throughput?

Answer 5

Total amount of completed instructions across all threads.

Higher throughput allows for more programs running simultaneously

Question 6

What is IPC?

Answer 6

Number of average instructions completed per cycle for a given thread.

Higher IPC gives more responsive programs

Question 7

What is a thread?

Answer 7

The execution of a program within a process

Question 8

What is multithreading?

Answer 8

Scheduling multiple threads on a single core.

Duplicate independent state for each thread (register file, PC, page table)

Memory sharing is done by using virtual memory

HW must support thread switching. Latency of this must be much lower than context switching

Question 9

What are two types of switch strategies?

Answer 9

Coarse and fine grained

Question 10

What are coarse-grained switch strategies?

Answer 10

Switch thread on long stall (L2 miss, TLB miss)

Advantage:
- Low HW cost due to slow thread switch
- Fast forward progress: thread is only switched when it would be delayed anyways

Disadvantages:
- CPU only issues from one thread. On stall, pipeline must be flushed before new thread can issue
- New thread must then refill pipeline from start - restart penalty
- Need added HW to detect costly stall and to start switch

Question 11

What are fine-grained switch strategies?

Answer 11

Switches between threads every cycle, interleaving the different threads.

Usually round-robin - skipping stalled threads

Advantages:
- Pipeline must not be refilled on stall
- Hides both short and long stalls

Cons:
- Slows down execution of individual threads
- Extra HW support

Question 12

What is simultaneous Multithreading (SMT)?

Answer 12

Thread switching happens within cycles, on open slots. An advantage is that we are much more likely to be able to fill up all available slots because of this.

The motivation for SMT is that dynamically scheduled processors already have HW mechanisms to support multithreading.
- Lots of physical registers because of register renaming
- Dynamic execution scheduling

Required hardware:
- Per-thread renaming table
- Separate PC
- Separate ROBs with commit capabilities

Question 13

What are some design challenges with SMTs? (3)

Answer 13

Need a large register file:
- Need a lot of physical registers to be able to map the architectural ones.

Must also avoid worsening the critical path:
- Don’t introduce additional bottlenecks
- From the issue to execution stage, need to make sure each thread is able to make as much progress, as if they were running on their own processor unit.

Make sure that threads don’t worsen the cache behaviour of other threads. This can happen if a working set of one thread only barely fit within the cache. The next thread will then need to evict to get its own data.
- Threads should be “good neighbours”
- Avoid evicting each others working set
- Possibly be able to share resources or have fairness between resources

Question 14

How does renaming work with SMTs?

Answer 14

Each thread have their own mapping table. So if threads are using the same instructions, these can be mapped to different physical instructions.

Question 15

Why don’t we need to add more physical registers to allow SMTs?

Answer 15

Because a thread only uses the whole physical register file when it runs at peak performance. In SMTs this won’t be the case, as the threads won’t be running at peak performance.

Question 16

What does an OoO pipeline look like with SMTs?

Answer 16

Separate PCs for each thread, used to fetch instructions from instruction cache. Fetch stage needs to support providing instructions to multiple threads at the same time.

Separate renaming units for each thread, with no crossing wires.

Separate ROOBs for each thread. (in-order commit, precise exceptions)

Question 17

How does Dynamic processors find parallelism?

Answer 17

Through OoO-execution of independent instructions

Question 18

What is the basic elements of DLP?

Answer 18

Designing systems around data elements directly, instead of exposing and exploiting parallelism.

Do this through vectorization

Question 19

What is vectorization?

Answer 19

Larger sets of associative data, where one operation is to be applied to all data points.

Question 20

What are SIMD?

Answer 20

Extend existing hardware features to enable a simplified form of vector execution

Splits registers into multiple data-elements. Execution units work on parallel lanes for each data element.

The programmer must convert their vectors to have formats (e.g. length) that are supported in hardware.

Question 21

What are vector architectures?

Answer 21

Explicitly introduce vector registers and -processing.

Vectors up to a max size is supported. This size is generally larger than the SIMD systems.

HW can be designed to speed ut vector fetch and addressing.

Question 22

What types of applications benefit from SIMD?

Answer 22

Ones using narrow data types (8-32 bit data). can fit multiple of these datatypes in a single register.

Can reuse existing register structures, and make minor modification to execution units to be able to fit multiple data type elements into single registers, and do operations on these.

Question 23

How is SIMD designed?

Answer 23

Use the full width of registers and split operations

Uses specific instructions to identify how to split up registers. (1x64, 2x32, etc.)

Question 24

Give an example on how registers can be modified in a SIMD design

Answer 24

Have a 64-bit register

Modify this into 4 16 bit registers

Question 25

What are some benefits of SIMD? (2 types)

Answer 25

Performance:
- Multiplicative factor of processing speed
- Latency stays the same

HW implementation has low cost
- logical operations already work
- ALU only need minor adjustments

Question 26

What are some limitations of SIMD? (4)

Answer 26

Instruction operand encoding sometimes gives bad alignment, causing less performance benefits.

Challenging to program. Programmer need to make sure data is aligned, as SIMD does not provide sophisticated addressing modes. The program is required to explicitly tile in cases where alignment is not exact.

No mask registers

Challenging to compile

Question 27

How does vector addition benefit from vactor architectures

Answer 27

for(i<-0 to 100) a[i] = b[i] + c[i]

In vector, all of these instructions can be done in a single instruction:
A = B + C

Question 28

What are some benefits of vector architectures (6)

Answer 28

Easier to program

Have a very explicit mode for parallelism, which makes for more efficient hardware.

Vectors are inherently independent, this gives a lot less control overhead

Gives a lot of data processing at any given time

Defining vector properties gives more freedom to how it will be implemented in HW. Can scale to different designs.

Vector processing can map well SW wise, by using vector_len properties.

Question 29

How are vector architectures designed?

Answer 29

Use vector registers, these are very large. These stores (Vector_len/Data_len) number of elements

FU execution time depends on type of operation and number of elements in a vector.

FUs support accesses from vector elements

Question 30

How are vector data loaded form memory?

Answer 30

Base address is calculated.

Vector data is then brought into vector registers.

Question 31

What are some limitation of vectors? (3)

Answer 31

Reduced performance for control flow dominated workloads

Data must be vectorizable

Mem system must be capable of servicing large amount of data (with low latency).

Program must be very responsive, even with large units of data being processed.

Question 32

How have SIMD and Vector converged over time?

Answer 32

SIMD extensions slowely morphed to be more vector like

SIMD is a constrained vector model

Vector is in general a powerful tool when doing data processing.

However, SIMD do not have the flexible vector addressing mode as vector architectures have.

Question 33

What is start-up time?

Answer 33

Time until first word is read/is back into system, after it has been requested

Question 34

After the initial start-up time, how much data should be provided per cycle afterwards from the memory cycle?

Answer 34

LANES * Data_len / cycles
In this case, as much data as possible is provided each cycle

Lanes: Number of parallel executions we can do per cycle

Data_len(DLEN): Amount of bits each data element has

This can be achieved using memory banks (interleaving)

Question 35

What must Vector architectures support to deal with load-stores with strides?

Answer 35

For example, matrix multiplication. Row from first matrix is multiplied with column from the other matrix. This mean that the Vector needs to be able to deal with adjacent and strided accesses.

Specify stride in instruction:
ld v1, number_elements, [base_address], stride

The same load instruction can be used to implement all different strides.

Question 36

What are sparse matrices, and some properties with these?

Answer 36

Mostly zero elements. The zero elements needs no processing, but can’t know if an element is zero or not, until we have already loaded it in.

Can use gather-scatter to take care of this issue

Question 37

What is gather-scatter in regards to sparse matrices?

Answer 37

Uses meta-data to find all 1-elements (gather)
Process these,
Write back to those elements in matrix (scatter)

LVI: Load Vector Indexed (gather)
SVI: Store Vector Indexed

Question 38

What is DLP acceleration?

Answer 38

Techniques to accelerate the performance of DLP

Question 39

What are 3 ways of accelerating DLP?

Answer 39

Speeding up dependency handling

Reducing impact of divergence

Parallelizing data element execution

Question 40

What is chaining of instructions?

Answer 40

Elements within a vector are independent. But there can still be dependencies between vectors.

In this case, each element of vector 2 has a true data dependence with the element in the same position, of vector 1.

Because some data elements from source vector will complete before the whole vector has completed. In this case, we can begin executing the next vector before the previous finishes.

By doing this we deconstruct vectors into registers. And issue dependent operands as soon as their source op are computed in the source vector

Question 41

What are multiple lanes?

Answer 41

Split vector execution across multiple execution units, instead of having whole vectors executing on one unit. Afterwards, we store the vector element results in their correct element in the result vector

Question 42

What are predicates (vector-mask control)?

Answer 42

Take outcome of if-else evaluation and create a mask vector with the elements that gives true as 1 and other as 0.

Apply operation to vector, only if mask entry is enabled. Rest of the elements become zero.

This ensures that an entire vector can still move as one.