L1 & L2

Question 1

What is the result of adding more transistors to a multiprocessor?

Answer 1

More performance

Question 2

What are the basic building blocks for integrated circuits?

Answer 2

Transistors

Question 3

Why is there an increase in number of cores per chip?

Answer 3

• Transistors are decreasing in size and clock frequency increases

Question 4

What are two effects of having smaller transistors?

Answer 4

• Smaller transistor -> faster switching and less power consumption

Question 5

True or False

Single processor speed is expected to keep increasing in the forthcoming years

Answer 5

False

Clock speed for single cores has physically reached its limit.
The solution is more cores.

Question 6

What are the implications of multi-core processors?

Answer 6

Hardware issues:
 Memory organization
 Connection of processors
 Processor type

Software issues:
 How to program to allow for parallelism

Question 7

What is Moore’s law?

Answer 7

Transistor count doubles every 1.5 years.
(Caused by transistor size reduction)

Question 8

Why do smaller transistors mean faster cores?

Answer 8

They have a faster swtich delay and can be clocked at a higher frequency.

But, a limit has been reached where cooling becomes a problem

Question 9

What is Dennard scaling? What led to its decline?

Answer 9

Dennard scaling: transistors size reduction results in less power consumption as more as packed on the same chip

Broke down in the mid-2000s mostly due to high current leakage

Question 10

Explain the difference between Instruction Level Parallelism, Process Level Parallelism and Thread Level Parallelism, outlining an issue introduced by each.

Answer 10

Instruction-level parallelism:
 Compiler/hardware automatically parallelises a sequential stream of instructions
 Issue: Limits parallelism due to dependencies between instructions

Process-level parallelism:
Process level parallelism does not require much effort from the programmer. Process level parallelism consists in running different applications on different cores.
Issue: increased overhead

Thread-level parallelism:
 The programmer divides the program into sequences of instructions in parallel
 Issue: data sharing between threads introduces the need for synchronsiation

Question 11

How is the total execution time calculation done for TLP in:
a. single core
b. multi-core

Answer 11

a. sum of each thread’s execution time
(t1 + t2 + .. + tn)

b. sum of each thread’s execution time / number of threads
( (t1 + t2 + .. + tn) / # of parallel threads)

Question 12

What can be used for array computations that perform the same computation on its elements?

Answer 12

Data parallelism

Question 13

What are some examples of data parallelism?

Answer 13

General:
- Matrix multiplication
- fourier transform

Graphics:
- Anti-aliasing
- Texture mapping
- Illumination and shading

Differential equations:
- Weather forecasting
- Engineering simulation
- Financial modelling

Question 14

What program structure increases the complexity of parallelism?

Answer 14

Program structure with large amounts of multiple-write data sharing

Question 15

Compare and contrast MPs and Chip MPs in terms of topology, connection, memory, and application.

Answer 15

Topology:
 MPs: Discrete elements
 Chip MPs: same chip

Connection:
 MPs: High-bandwidth network
 Chip MPs: On-chip network

Memory:
 Both utilize shared memory
 MPs may use private memory

Application:
 MPs: specific applications (supercomputers, web)
 Chip MPs: general purpose

Question 16

What are the 4 types of architectures in Flynn’s taxonomy?

Answer 16

o SISD: one instruction executed at a time processing one data element at a time

o SIMD: one instruction executed at a time operating on multiple independent streams of data

o MIMD: multiple sequences of instructions executed independently each one operating on a different stream of data

o SPMD: multiple instruction streams but with the same code on multiple independent streams of data

Question 17

What is an application of MIMD?

Answer 17

Chip multiprocessors

Question 18

What is an application of SIMD?

Answer 18

Vector’s processors, vector units, GPUs

Question 19

What is the worst case complexity for communication in a NxN grid?

Answer 19

2*(N-1) steps

Question 20

What is the worst case complexity for communication in a NxN torus?

Answer 20

N steps

Question 21

True or False.

In a grid interconnection, all cores have 4 neighbours.

Answer 21

False.

Edge cores of the grid have 2 or 3. In torus, all cores have 4 neighbours.

Question 22

How many neighbours does a 3D torus core have?

Answer 22

3*2 so 6 neighbours

Question 23

Explain the 3 options for interconnection.

Answer 23

Grid:
 Direct link to neighbours
 Private on-chip memory
 Staged communication with non-neighbours

Torus:
 Direct link to neighbours
 Private on-chip memory
 More symmetrical, more paths, and shorter paths
 Like folding the grid, so all cores have 4 neighbours

Bus:
 All cores linked to all cores
 Simple to build
 Constant latency

Question 24

Explain the difference between shared and distributed memory from a hardware and software view.

Answer 24

Shared: accessible from every part of the computation
 Hardware: Memory connected to all cores
 Software: Global; accessible from all threads; reads/writes

Distributed: accessible from only part of the computation
 Hardware: Memory connected to only one core
 Software: Local; accessible only by the owning thread; message passing

Question 25

Is data sharing efficient on distributed memory?

Answer 25

No, it is slow

Question 26

Is message passing efficient on shared memory?

Answer 26

It is fast but slower than data sharing