CS6068 Midterm Practice w Solutions

CS6068 Midterm Practice Exam  - With SOLUTIONS

1.What are three traditional ways that hardware designers make computers run faster? Please circle all that are true.
-faster clocks
-longer clock periods
-more work per clock cycle
-a larger hard disk
-adding more processors
-reducing the amount of memory

ans: 1,3,5

2.What are David Pattersonís Three Walls of Computer Architecture?
ans: Power, Memory, ILP

3. For a class of GPUs, what is appropiate measure to compare power consumption of different devices?
ans:Flops per watt

4.What techniques are computer designers today using to build more power-efficient devices? Please circle all that are true.
-having fewer, but more complex processors,
-having more, but less complex processors,
-maximizing the speed of the processor clock
-increasing the complexity of the control hardware

ans:2

5. Name four common patterns of parallel computation? For each pattern, discuss whether the many-core or multi-core architecture model is more appropriate.

ans:
Map redude: manycore
Pipe-and-filter: multi
Agents: multi
iterative: many

6. What is concurrency control, and discuss what is the difference between pessimistic an optimistic concurrency control?

ans: addresses conflict in simult access, pessimistic locks, optimistic transactions STM


7. How does Fork/Join parallelism differ from Kernel data-parallelism?

ans: in F/J main thread spawns to complete complex parallel tasks then joins mains, kernels uses large index sets and map simple tasks to threads

8. Circle all the true statements.
-A thread block contains many threads.
-An SM might run more than one thread block.
-A thread block may run on more than one SM.
-All the threads in a thread block might cooperate to solve a subproblem.
-All the threads that run on a given SM may cooperate to solve a subproblem.

ans:1,2,4

9. If we have a single kernel that is launched on many thread blocks, including block x and block y, the programmer can do which of the following: Circle all the true statements.
-specify that block x will run at the same time as block y
-specify that block x will run after block y.
-specify that block x will run on same SM as y
-none of the above

ans: none

10. Circle all the statements that are true.
-All threads from a block can access the same variable in that block's shared memory.
-Threads from two different blocks can access the same variable in global memory
-Threads from different blocks have their own copy of local variables in local memory.
-Threads from the same block have their own copy of local variables in local memory.

ans:1,2,3,4

11. At what level can barrier synchronizations be executed in CUDA:
-thread  -block  -grid   -device  -multi-device?

ans: block

12. What is a parallel map operation? Circle all problems that can be solved using map.
-sort an array -add one to each element of an array -sum elements in array -move data based on array of scatter addresses

ans: 2,4

13. Circle which operators are both binary and associative and therefore can be used in a reduction or scan.
-multiply -minimum -factorial -exclusive or -bitwise and -exponentiation -integer division

ans: 1,2,4,5

14. Using 1D global indexing, how would you specify the parallel execution mapping the ith thread to the task of reading and then squaring the ith item from an large array X in global memory.

int i = blockIdx.x * blockDim.x + threadIdx.x;
float x = X[i]
X[i] = x * x;


15.Circle all statements that are true. When running reduction code running on an input of size n?
-it takes at least n operations
-its work complexity is order of n
-its work complexity is order n*n
-its step-complexity is order of 1, independent of the size of the input.

ans: 2

16. Circle the correct answer. The number of steps in a reduction as a function of n is:
- square root of n
- log base 2 of n
- n
- n times log base 2 of n
ans: 2


17. Circle all that are true
- map operations have arguments that are functions with a single argument
- map operations can be applied to arrays of any number of dimensions
- map operations are generally very efficient on GPUs
- a compact operation requires a map operation to be performed.

ans:1,2,3,4

18. What is the impact of granularity on performance when considering the latency of global memory communication? What is the granularity of dot product of two vectors that reside in global memory?

Ans: The higher the granularity (computation to communication ratio) the greater the opportunities for latency hiding. The dot product has 1:1 computation to communication ratio.

19. What is the output of a max scan operation on the list of unsigned ints [5 4 7 3 1 8 2 6]?
Provide a solution to both inclusive and exclusive scans.

inc-scan
5 5 7 7 7 8 8 8
exc-scan
0 5 5 7 7 7 8 8


20. Compute the max (inclusive) scan of this input sequence 2 1 4 3 showing all work when using
a) the Hillis-Steele algorithm
b) the Blelloch algorithm

21. Explain which scan algorithm (Hillis-Steele or Blelloch algorithm) is best suited and why?
You are scanning a 512 element vector and a GPU that has 512 processors.

ans: Hillis-Steele would probably perform better, since its step complexity is half that of Blelloch.

22. Explain which scan (Hillis-Steele or Blelloch algorithm) is best suited and why?
You are scanning a 1 million element input vector in 512 processors machine.

ans: Hillis-Steele would probably perform worse, since its work complexity is logn times that of Blelloch.

23. Suppose you are computing a histogram with less than 10 bins. Discuss an efficient GPU solution. Indicate whether or not you need to use atomics to manage access to bins of the histogram.

ans: atomics would limit the parallelism to speedup of 10 = #bins. Using per thread private bin counts, followed by a reduction would be efficient.

24. True or false - In a scatter operation a syncthreads command is needed to overcome write conflicts.

ans: False

25. Is the compact parallel operation going to be most useful in scenarios where we delete a (small number) or a (large number) of elements?

ans:large

26. Is the compact parallel operation going to be most useful in scenarios where we need to run (cheap) or (expensive) function on filtered elements.

ans: expensive

27. Suppose we are running compact operations on a list of numbers with range from 1 to 1 million. Compact operation A, filters elements that are divisible by 17, and thus is only going to keep a very few of the input items. Compact operation B filters elements not divisible by 31, and thus is going to keep most of the input items. For each of the three phases of compact: predicate map, scan, and scatter phases of the compact operation, will A run faster, B run faster or will they take the same amount of time?
a. Predicate map  b. Scan  c. Scatter

ans:
a. same   b. same  c. A faster

28. What is the difference between latency and bandwidth? Which is more easily enhanced by advanced architectures? Given a sports-car traveling 100mph with 2 passengers versus a bus traveling 50mph with 20 people. Say the task is to tranport people 200 miles. How do the Bandwidths(in people deliverd per hour) and Latency (in hours) compare between the two vehicles?

ans: Sport-car latency: 2 hrs, bw: 1/hr; bus latency: 4 hrs, bw: 5/hr

29. How is Occupancy defined in Cuda, and why does it have an impact on performance?

ans: percent of active thread by total threads. High occupancy increases potential bandwidth hiding latency.

30. Show the contents of the CSR (Compressed Sparse Row) format for the following 5x5 matrix:
02300
10050
00400
00020

31. Consider the sparse matrix dense vector product problem, and the two different parallel methods tpr(thread per row) or tpe (thread per element).
a. Which approach will launch more threads?
b. Which approach will require more communication between threads?
c. Which approach will do more work per thread?
d. Which approach is more load balanced?

ans:
a. tpe
b. tpe
c. tpr
d. tpe