PAPER CODE NO. EXAMINER: Fabio Papacchini COMP528-JAN21 DEPARTMENT: Computer Science FIRST SEMESTER EXAMINATIONS 2020/21 Multi-Core and Multi-Processor Programming EXPECTED TIME: 3 hours INSTRUCTIONS TO CANDIDATES • The exam consists of FOUR questions. You must answer ALL questions • The expected writing time for the exam is 3 hours • You may write your answers using a word processor (please export the document to PDF before submitting), or you may write your answers by hand and either scan them, or take photos of them. If you write answers by hand, then both the handwriting and the scanned copy must be legible in order to be accepted. • The exam will be released at 9am on Friday 30 April 2021. You will then have 24 hours in which to prepare your answers, and the final deadline for submissions is 9am on Saturday 01 May 2021. All times and dates are BST (GMT +1). • All answers should be combined into a single PDF that should be uploaded to the relevant CANVAS area for the COMP528-JAN21 course 2020-2021. • Late submissions will not be accepted. PAPER CODE COMP528-JAN21 page 1 of 5 Continued Question 1 1. What are the reasons for the fast development and wide use of multi-core processors? What hardware approaches have been developed to overcome the limitations imposed by a single core processor? [7 marks] 2. Consider two small HPC clusters C1 and C2 where • C1 is composed of 4 nodes with 8 processors each, and each processor has 15 cores running at a fixed frequency of 2.5 GHz; and • C2 is composed of 2 nodes with 12 processors each, and each processor has 20 cores running at a fixed frequency of 2 GHz. How you would evaluate their peak performances? Assuming 2 floating point operation per CPU core cycle, which of the two small clusters has a better peak performance? [5 marks] 3. In your own words, explain and comment on Amdahl’s Law and Gustafson’s observation. For the former (i.e., Amdahl’s law), provide its equation, and define each used variable. Explain what is meant by “speed up” and express the theoretical maximum speed-up as a function of the serial proportion of a code. [8 marks] 4. A serial code takes 300 minutes to run. Timing different parts of the code shows that 294 of 300 minutes are spent on a parallelisable portion of the code. Using Amdahl’s Law, how long would it take to run a parallel version of the code on 3 cores? Assuming Amdahl’s Law is correct, what would be the parallel efficiency on 3 cores? And what is the maximum speed- up possible for this code on this architecture? [5 marks] Question 2 1. Describe the MPI Scatter and MPI Gather collectives, explaining what buffers are required to be allocated and initialised on which process. NOTE: the description should discuss both the high-level idea behind them, and the more practical aspects in an implementation. [8 marks] 2. Explain what a deadlock is, provide an example of an MPI program which might result is a deadlock, and provide a possible solution to your example (HINT: you do not have to provide PAPER CODE COMP528-JAN21 page 2 of 5 Continued the whole code, but just the relevant lines causing the deadlock and making clear which pro- cesses are executing them) [8 marks] 3. Explain what affects the time to send messages in an HPC cluster, and how a reduction pat- tern can have a positive impact on the total wall clock time. [5 marks] 4. Explain what is wrong in the following C code, and propose a possible solution. You can assume that each process has the integer array x initialised, NUM is an integer provided as input, and the number of processes is less than NUM. MPI_comm_size(MPI_COMM_WORLD, &size); MPI_comm_rank(MPI_COMM_WORLD, &myRank); int stepSize = NUM/size; int start = myRank*stepSize; int finish = start + stepSize; int global_sum=0; int local_sum = 0; for(i=start; i
local_sum += x[i] } MPI_Reduce(&local_sum, &global_sum, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD); if(rank==0) printf("Sum: %f", global_sum); [4 marks] Question 3 1. Consider the following serial C code where a, b and res are vectors (of N floats) and N is a positive integer previously read in by the program. res = 0.0; for (i=N - 1; i > 0; i--) { res = res * (b[i]-a[i]); } PAPER CODE COMP528-JAN21 page 3 of 5 Continued Explain how you would parallelise this using OpenMP, giving the full and exact code needed to appropriately parallelise this loop, bearing in mind good programming practices [5 marks] 2. Explain, via the use of an example, what is wrong in the following code, and how you would fix it. You can assume that all variables have been initialised before the provided code (you might want to state what their values are for your example). #pragma omp parallel default(none) shared(NUM,A,B,x,y) private(i,j,k) { #pragma omp for nowait for(i=0;ix[i] = A * x[i]; } #pragma omp for for(j=0;jk = NUM-j-1; y[j] = B * x[k]; } } [7 marks] 3. When writing OpenMP programs, it is fundamental to understand the “scope” of variables within a parallel region. For a given variable x, describe in words, and potentially via an example and/or diagram, what happens in each of the following cases: (1) x is defined as private(x), (2) x is defined as shared(x), and (3) x is defined within a reduction directive (e.g., reduction(+:x)). [6 marks] 4. Different approaches can be taken when implementing a parallel program (e.g., shared mem- ory vs distributed memory), each of which has its advantages and disadvantages. Provide at least four statements about differences and/or similarities between the two main approaches discussed in the lectures. [7 marks] Question 4 1. Describe, potentially with the use of diagrams, what task parallelism and data parallelism are. Which one of these two kind of parallelism is better suited for implementation on GPUs? PAPER CODE COMP528-JAN21 page 4 of 5 Continued Explain you answer. [6 marks] 2. Explain the steps you would take to implement the serial code fragment below as a parallel operation on a GPU as a 1D CUDA kernel. You should include how to change the code to become a CUDA kernel, including portability for invocation on any number of threads larger than num (where there are num elements of x, y and z). void saxpy(float *z, float A, float *x, float *y, int num) int i; for (i=0; i{ z[i] = x[i] - A * y[i]; } [8 marks] 3. Explain the differences of using openMP or openACC to offload part of a parallel computation to a GPU. [5 marks] 4. Choose one between the two “emerging technology” FPGA and Quantum Computing. De- scribe the chosen technology and how it differs from traditional CPU computing. [6 marks] PAPER CODE COMP528-JAN21 page 5 of 5 End 欢迎咨询51作业君