Week 14: Exercises

1. Parallel Primality Test

Write a program that takes two integers n and t on the command line. The integer n may have any value that fits in 64 bits (so you should store it in a long). The program should test whether n is prime, using t threads to perform the computation in parallel. To achieve this, the program should assign to each thread a range of possible factors that it should test.

If any thread finds a factor of n, the program should print "not prime" and immediately exit. If no thread finds any factor, the program should print "prime".

2. Parallel Sort

Suppose that a machine has 8 cores.

a) How could you use parallel computation to speed up a mergesort?

b) How could you use parallel computation to speed up a quicksort?

c) Choose one of these sorting algorithms and implement your parallelization idea from part (a) or (b). Now create a large array of random numbers and try sorting it with and without your parallelization. Does the parallelization actually help?