Closed Exercises

Question 1

Let’s consider a single-issue processor that can manage up to 4 simultaneous threads.
What are the values of the ideal CPI and the ideal per-thread CPI? (SINGLE ANSWER)
1 point

• Answer 1: Ideal CPI = 1 & Ideal per-thread CPI = 0.25
• Answer 2: Ideal CPI = 0.25 & Ideal per-thread CPI =0.25
• Answer 3: Ideal CPI = 0.5 & Ideal per-thread CPI = 2 Answer 4: Ideal CPI = 0.5 & Ideal per-thread CPI = 1
• Answer 5: Ideal CPI = 1 & Ideal per-thread CPI = 4

Answer 1

Answer 5: Ideal CPI = 1 & Ideal per-thread CPI = 4

I need to manage the number of threads devised by the number of issues

Question 2

Let’s consider a dual-issue SMT processor that can manage up to 4 simultaneous threads.
What are the values of the ideal CPI and the ideal per-thread CPI? (SINGLE ANSWER)
1 point

• Answer 1: Ideal CPI = 1 & Ideal per-thread CPI = 0.25
• Answer 2: Ideal CPI = 0.25 & Ideal per-thread CPI =0.25
• Answer 3: Ideal CPI = 0.5 & Ideal per-thread CPI = 2
• Answer 4: Ideal CPI = 0.5 & Ideal per-thread CPI = 1
• Answer 5: Ideal CPI = 0.25 & Ideal per-thread CPI = 4

Answer 2

Answer 3: Ideal CPI = 0.5 & Ideal per-thread CPI = 2

Threads decided by the number of issues

Question 3

Let’s consider a 4-issue SMT processor that can manage up to 4 simultaneous threads.
What are the values of the ideal CPI and the ideal per-thread CPI? (SINGLE ANSWER)
1 point
• Answer 1: Ideal CPI = 1 & Ideal per-thread CPI = 0.25
• Answer 2: Ideal CPI = 0.25 & Ideal per-thread CPI =0.25
• Answer 3: Ideal CPI = 0.25 & Ideal per-thread CPI = 1
• Answer 4: Ideal CPI = 0.25 & Ideal per-thread CPI = 4
• Answer 5: Ideal CPI = 4 & Ideal per-thread CPI = 0.25

Answer 3

Answer 3: Ideal CPI = 0.25 & Ideal per-thread CPI = 1

Threads devided by the number of issues

Question 4

What is the Flynn’s taxonomy?

Answer 4

• SISD: Single instruction stream, single data stream
- Uniprocessors (including scalar processors like MIPS, but also ILP processors such as superscalars)

• SIMD: Single instruction stream, multiple data streams - Vector architectures
- Multimedia extensions
- Graphics processor units

• MISD: Multiple instruction streams, single data stream - No practical usage => no commercial implementation

• MIMD: Multiple instruction streams, multiple data streams - Tightly-coupled MIMD (with thread-level parallelism)
- Loosely-coupled MIMD (with request-level parallelism)

Question 5

What is the idea of SIMD and its advantages

Answer 5

Central controller send the same instruction to multiple processing elements (PEs) for multiple data.

• Synchronized PEs with single Program Counter

• Each Processing Element (PE) has its own set of data
– Use different sets of register addresses

• Motivations for SIMD:
– Cost of control unit shared by all execution units
– Only one copy of the code in execution is necessary

Question 6

What are the types of SIMD machines?

Answer 6

Vector architectures

SIMD extensions

Graphics Processor Units (GPUs)

Question 7

How does a Vector architecture works?

Answer 7

Basic idea:
– Load sets of data elements into vector registers
– Operate on vector registers
– Write the results back into memory

Question 8

What is the difference between scalar and vector registers?

Answer 8

See picture 23

Question 9

What are GPUs specialized in

Answer 9

GPUs are specialized for parallel intensive computation

Question 10

How does GPU parallelize its computations

Answer 10

All operations are performed in parallel by the GPU using a huge number of threads processing all data independently

Question 11

How does the interaction between CPUs and GPUs occur?

Answer 11

The GPU (device) serves as a coprocessor for the CPU (host)

CPU and GPU are separate devices, with separate memory space addresses

The GPU has its own high-bandwidth memory

Serial parts of a program run on the CPU (host)

Computation-intensive and data-parallel parts are offloaded to the GPU (device)

Question 12

What is the main bottleneck in the CPU and GPU interaction?

Answer 12

Data movement between CPU and GPU is the main bottleneck
- Low bandwidth with respect to internal CPU and GPU since it exploits PCI Express (12-14GB/s)
- Relatively high latency
- Data transfer can take more than the actual

Question 13

What is operation chaining

Answer 13

Concept of forwarding extended to vector registers:
– A vector operation can start as soon as each element of its
vector source operand become available
– Even though a pair of operations depend on one another,
chaining allows the operations to proceed in parallel on separate elements of the vector.
– In this way, we don’t need anymore to wait for the last element of a load to start the next dependent instruction.

Question 14

What does the execution time of vector architectures depend on

Answer 14

• Execution time depends on three factors:
– Length of operand vectors (number of elements)
– Structural hazards (how many vector functional units)
– Data dependencies (need to introduce operation chaining)

• VMIPS functional units consume one element per clock cycle
– So, the execution time of one vector instruction is approximately given by the vector length

Question 15

What are convoys?

Answer 15

• Simplification: to introduce the notion of convoy
– Set of vector instructions that could potentially execute
together partially overlapped (no structural hazards)

• Sequences with read-after-write dependency hazards can
be in the same convoy via chaining

Question 16

What are chimes?

Answer 16

Chime is a timing metric corresponding to the unit of time to execute one convoy
– m convoys execute in m chimes (or time units)
– Simply stated: for a vector length of n, and m convoys in a program, n x m clock cycles are required
– Chime approximation ignores some processor-specific
overheads

Question 17

LV V1,Rx
MULVS.D V2,V1,F0
LV V3,Ry
ADDVV.D V4,V2,V3
SV Ry,V4

Let assume to have 1 LV/SV Unit & 1 ALU V Unit with chaining: how can we devise the above instructions into convoys? How many chimes does it take?

Answer 17

3 convoys:
1) LV MULVS.D (chaining)
2) LV ADDVV.D (chaining)
3) SV
Last store can not be put in the last convoy once we have only one LV/ST unit

3 convoys (3 chimes): 2 FP ops per element => 1.5 cycles per FP ops per element;

See picture 24

Question 18

How can a vector processor execute a vector faster than one element per clock cycle?

Answer 18

See picture 25

Question 19

How to handle a number of loop iterations not equal to the vector length?

What do you do when the vector length in a program is not exactly 64?
1. Vector length smaller than 64
2. Vector length unknown at compile time and maybe greater than MVL

Answer 19

See picture 26

Question 20

What to do when there is an IF statement inside the FOR loop code to be vectorized?

Answer 20

See picture 27

Question 21

How to handle bi-dimensional matrices?

Answer 21

See picture 28

Question 22

How to handle sparse matrices in vector processors?

Answer 22

See picture 29