Misc

Question 1

what is the diameter of a p processor hypercube

Answer 1

log2p

Question 2

what is the bisection width of a 3d mesh with equal number of processors along all three dimensions. express the answer as a function of the number of processors given by p

Answer 2

p^(2/3)

Question 3

What two performance bounds are represented on a roofline plot?

Answer 3

Computational Peak Performance
Memory Bandwidth Peak (or Peak Bandwidth)

Question 4

According to the standard, under what conditions can the MPI_send call return to the calling procedure?

Answer 4

The MPI_Send call can return after the send operation is complete, which means either the message has been sent to the system buffer and is ready for transmission, or the send has been matched with a corresponding receive operation, depending on the implementation.

Question 5

For amdahl’s law, describe the function to derive the serial fraction

Answer 5

In Amdahl’s Law, the serial fraction (s) is derived from the part of the task that cannot be parallelized, divided by the total execution time.

Question 6

For ahmdahl’s law, give the equation to derive the speedup and efficiency given n processors

Answer 6

speedup (S) = 1 / (s + (1-s) / n)
efficiency (E) = S / n

the lowercase s represents the serial fraction

Question 7

For ahmdal’s law, give the equation to find the upper bound on performance

Answer 7

S_max = 1 / s

Question 8

Briefly state Little’s law in the context of memory system performance

Answer 8

Little’s law states that the number of elements in a queuing system is equal to the average wait time multiplied by the arrival wait. It can be used to describe bandwidth.

Question 9

What cache type has the lowest latency, direct mapped, k-way, or fully associative?

Answer 9

Direct mapped

Question 10

Which cache type has the highest hit ratio, direct mapped, k-way, or fully associative?

Answer 10

Fully associative

Question 11

What type of operation might you use MPI_Scan to perform?

Answer 11

MPI_Scan is often used for performing a prefix operation, such as calculating running totals or cumulative sums across an array distributed among multiple processors.

Question 12

In CUDA programs, what is a thread block?

Answer 12

In CUDA, a thread block (also called a block) is a group of concurrent threads that can cooperate among themselves through shared memory and synchronization.

Question 13

In CUDA programs what does the shared keyword do?

Answer 13

In CUDA, the __shared__ keyword is used to declare variables that are shared among all threads within the same block. This shared memory allows for faster inter-thread communication within a block.

Question 14

What is the difference between a compare split and a compare
exchange operation?

Answer 14

A compare-split operation is used in distributed computing, specifically in sorting algorithms. Given two sorted lists, it creates two new sorted lists such that all elements in the first list are less than or equal to all elements in the second list.

A compare-exchange operation, on the other hand, is a fundamental operation in parallel and distributed computing used in various algorithms. Given two values, it compares them and swaps them if they are out of order. It’s a basic building block for many sorting algorithms such as bitonic sort and bubble sort.

Question 15

What is the serial cost of the bitonic sorting algorithm?

Answer 15

The serial complexity (cost) of the bitonic sort algorithm is O(n log^2 n), where n is the number of elements to be sorted.

Question 16

Parallel quicksort: pivot selection

Answer 16

In parallel quicksort, a common approach to pivot selection is to select a random sample of elements from the array, sort this sample, and then use the median as the pivot. This is done to ensure a balanced partitioning and optimal load balancing across processors.

Question 17

Parallel quicksort: local rearrangement

Answer 17

Each processor then rearranges its local data such that all elements less than the pivot come before all elements greater than the pivot. This local rearrangement can be done in O(n/p) time, where n is the total number of elements and p is the number of processors.

Question 18

Parallel quicksort: global rearrangement

Answer 18

After local rearrangement, a global rearrangement is performed. Elements less than the pivot are moved to the lower half of the array, while elements greater than the pivot are moved to the upper half. This rearrangement could be achieved through an all-to-all communication, and takes O(n) time.

Question 19

Parallel quicksort: how may global rearrangement steps are required?

Answer 19

The number of global rearrangement steps in the parallel algorithm is log(p), where p is the number of processors. This is because with each step, the number of partitions doubles.

Question 20

Parallel quicksort: how much time does local rearrangement take?

Answer 20

The time for local rearrangement is O(n/p) since each processor is operating on its local data independently.

Question 21

Parallel quicksort: how much time does global rearrangement take?

Answer 21

The time for global rearrangement is O(n), as it involves communication between all processors.

Question 22

Parallel quicksort: What is an estimate of the running time
for parallel quicksort assuming ideal pivots are selected?

Answer 22

Assuming ideal pivots are selected (which would mean that the data is evenly distributed among the processors after each partitioning), the running time of the parallel quicksort algorithm is O(n log n / p + log^2 p). The first term accounts for local work and the second term accounts for the necessary synchronization and communication between processors.

Question 23

Parallel sample sort: what is the first step of the algorithm?

Answer 23

The first step in the parallel sample sort algorithm is data distribution. Each processor is given a roughly equal portion of the data to be sorted.

Question 24

Parallel sample sort: how are samples selected?

Answer 24

Samples are selected by having each processor pick a subset of values from its local data. These samples can either be random or regular intervals.

Question 25

Parallel sample sort: How are splitters created
(and what are splitters?)

Answer 25

The selected samples are then gathered together and sorted to create “splitters”. Splitters are selected values that divide the data into buckets. Each processor uses these splitters to partition its local data into buckets such that all values in a bucket are less than the next splitter and greater than or equal to the previous one.

Question 26

Parallel sample sort: Provide an estimate of the running time
for the parallel sample sort.

Answer 26

The running time of the parallel sample sort algorithm is O(n/p log(n/p) + n log p), where n is the total number of elements and p is the number of processors.

Question 27

Parallel sample sort: what happens after local rearrangement?

Answer 27

After local rearrangement, all values in the same bucket across different processors are gathered together. Each processor then sorts its own buckets.