Exam Preparation Questions

Question 1

Flynn’s Taxonomy classifies computer architectures as:
A) Single/multipleCPUs anddistributed/shared memory
B) Single/multipleinstruction andsingle/multipledata
C) CPUs/GPUs anddistributed/shared memory

Answer 1

B) Single/multipleinstruction andsingle/multipledata

Question 2

Which system requires parallel computing with message passing to write computer programs?
A) A multicorelaptop
B) A NUMA computer node
C) A multi-node computer cluster

Answer 2

C) A multi-node computer cluster

Question 3

What is the bisection width of this network? (10 connections)

A) 2
B) 4
C) 6

Answer 3

B) 4

Question 4

What is the advantage of a binary tree topology over a mesh topology?
A) Binary tree has a better diameter
B) Binary treehas more edges per node
C) Binary tree has a better bisection width

Answer 4

A) Binary tree has a better diameter

Question 5

The communication complexity is …

using Distributed
addprocs(4)
N = 1600
ftr = @spawnat 2 sum(A)
s = fetch(ftr)

A) O(N)
B) O(N^2)
C) O(N^3)

Answer 5

B) O(N^2)

Question 6

Which MPI directive would you use to send a copy of a 2D matrix to all processes from one process?

A) MPI_Bcast
B) MPI_Scatter
C) MPI_Allreduce

Answer 6

A) MPI.Bcast

Question 7

Which one would you use to send a large message to avoid duplicating data?
A) MPI_Bsend
B) MPI_Ssend
C) MPI_Send

Answer 7

B) MPI_Ssend

Question 8

Each process computes a set of rows of C = A * B. What is the communication complexity in each worker?
A) O(1)
B) O(N^3/P)
C) O(N^2)

Answer 8

C) O(N^2)

Question 9

When parallelising matrix multiplication: C = A * B, which partition leads to the best computation/communication ratio?

A) Each processcomputes one row of C
B) Each process computes onecolumn of C
C) Each process computes a set of rows of C

Answer 9

C) Each process computes a set of rows of C

Question 10

Can we use latency hiding in the Jacobi method?
A) No, because allcomputationsdepend on thepreviousiteration
B) Yes, because computation of interior value scan overlap communication
C) No, because all values depend on neighbouring values

Answer 10

B) Yes, because computation of interior value scan overlap communication

Question 11

Which of the following suggestions does NOT solve the incorrect behaviour of the parallel Floyd algorithm?
A) Communicate row k using standard sends
B) Communicate row k using synchronous sends
C) Use MPI.Barrier in each iteration

Answer 11

A) Communicate row k using standard sends

Question 12

Which are the data dependencies for each worker in Gaussian elimination at iteration k>1?
A) Workers withrows > kneed theentire row k
B) Workers with rows > k need all rows>= k
C) Workers with rows > k need only part of row k

Answer 12

C) Workers with rows > k need only part of row k

Question 13

What can be done to solve the load imbalance of block partitioning in Gaussian elimination?
A) Use a cyclic distribution of rows
B) Use a replicated workers model
C) Use a 2D block partition

Answer 13

A) Use a cyclic distribution of rows

Question 14

In parallel TSP, there may be load imbalance because
A) It is impossible todivide the searchtree evenly
B) We don’t know before hand how long the paths in the search tree are
C) Some workers might be able to do more pruning than others

Answer 14

C) Some workers might be able to do more pruning than others

Question 15

How to cheat with speedups?
A) Use a fast compiler and a slow network
B) Use a slow compiler and a fast network
C) Use very small problem sizes

Answer 15

B) Use a slow compiler and a fast network

Question 16

Which law gives the more pessimistic optimal speedup for a large parallel computation?
A) Amdahl’s law
B) Gustafon’slaw
C) Amdahl’s and Gustafson’slaws are equivalent

Answer 16

A) Amdahl’s law

Question 17

Which elements of v are needed in CPU 2 to compute this sparse matrix-vector product?

A) The entirevector v
B) v[5] and v[6]
C) v[2] and v[6]

Where:
CPU 1: v1, v2, v3
CPU 2: v4, v5, v6

Answer 17

C) v[2] and v[6]

Question 18

Which strategy is used to improve load balance while reducing communication in the POP simulation software?

A) Cyclic partitions
B) Hierarchical block distribution
C) Computation ensembles

Answer 18

B) Hierarchical block distribution