Concurrent Programming Coursework
Summary: You are required to implement the parallel prefix scan algorithm in c/mpi: Specification:
To have keyboard input of the number, n, of elements in the sequence
Process 0 will generate n random integers and broadcast these to the other processes as appropriate
Copyright By PowCoder代写 加微信 powcoder
Process 0 prints the input and output sequences onto the screen.
Note: use of MPI_Scan is explicitly forbidden.
Methodology:
There will be an in-class discussion of the algorithm in which we shall work together to identify the key issues and details of the algorithm – be prepared to ask questions in that session.
Deliverables:
1) A single source file prefix.c that can be compiled under MSYS2 using mpicc. This source file will contain all necessary c/mpi code. Codes provided for other frameworks (e.g. implemented using Microsoft Visual Studio with MPI are NOT ACCEPTABLE and will be awarded a mark of 0)
Your code must be properly documented to permit an experienced coder, who is unfamiliar with the prefix scan algorithm to understand and be able to modify or upgrade it.
– Good quality in code commentary is required
– Explicit testing showing sets of inputs and expected outputs is required
2) A very brief pdf report highlighting any significant code features to which you wish to draw attention and the results of your testing to convince the client of correct functionality and any comments on the limitations and scope for upgrade of the code.
Submission is only accepted via the assessment link on the Moodle page.
Marks and feedback will be provided within 15 working days of the submission deadline and each student will receive their completed copy of the marking rubric posted on Moodle. Further feedback can subsequently be requested by email.
Plagiarism: Students will naturally discuss the assignment between themselves, however each student’s submission must be wholly their own work. It is easier than you might think to spot both students sharing code and the use of third-party code downloaded from the internet etc. The full force of the University’s academic misconduct regulations will be invoked for any infringements.
The Prefix Scan Algorithm
Definition: Given a sequence, a, of input values (𝑎, 𝑎, 𝑎, 𝑎, 𝑎 … 𝑎)
the output sequence, b, is defined as (𝑏, 𝑏, 𝑏, 𝑏, 𝑏 … 𝑏) where 𝑏 = ∑ 𝑎
We note that 𝑏 = 𝑏 + 𝑎
Example: a= (1,2,3,4,5,6,7,8) then b= (1,3,6,10,15,21,28,36)
A simple serial C implementation of this algorithm might be
void prefix_scan(int n, int a[], int b[]){ b[0]=a[0];
for(int i=1;i