1. Homepage
  2. Programming
  3. Concurrent Programming Coursework 2024 - Prefix Scan Algorithm in C/MPI

Concurrent Programming Coursework 2024 - Prefix Scan Algorithm in C/MPI

Engage in a Conversation
Concurrent ProgrammingCPrefix ScanMPI

Concurrent Programming Coursework 2024 CourseNana.COM

Summary: You are required to implement the parallel prefix scan algorithm in c/mpi: CourseNana.COM

Specification: CourseNana.COM

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 Process 0 prints the input and output sequences onto the screen. CourseNana.COM

Note: use of MPI_Scan is explicitly forbidden. CourseNana.COM

Methodology: CourseNana.COM

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. CourseNana.COM

Deliverables: CourseNana.COM

  1. 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) CourseNana.COM

    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. CourseNana.COM

    • -  Good quality in code commentary is required CourseNana.COM

    • -  Explicit testing showing sets of inputs and expected outputs is required CourseNana.COM

  2. 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. CourseNana.COM

Submission is only accepted via the assessment link on the Moodle page. CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

The Prefix Scan Algorithm CourseNana.COM

Definition: Given a sequence, a, of input values (𝑎􏰀, 𝑎􏰁, 𝑎􏰂, 𝑎􏰃, 𝑎􏰄 ... 𝑎􏰅􏰆􏰁)
the output sequence, b, is defined as (𝑏􏰀, 𝑏􏰁, 𝑏􏰂, 𝑏􏰃, 𝑏􏰄 ... 𝑏􏰅􏰆􏰁) where 𝑏􏰇 = ∑􏰇􏰈􏰉􏰀 𝑎􏰈 CourseNana.COM

We note that 𝑏􏰇 = 𝑏􏰇􏰆􏰁 + 𝑎􏰇
Example: a= (1,2,3,4,5,6,7,8) then b= (1,3,6,10,15,21,28,36) CourseNana.COM

A simple serial C implementation of this algorithm might be CourseNana.COM

void prefix_scan(int n, int a[], int b[]){ b[0]=a[0]; CourseNana.COM

for(int i=1;i<n;++i) b[i]=b[i-1]+a[i]; CourseNana.COM

} CourseNana.COM

Parallel Prefix Scan Algorithm CourseNana.COM

Initialise b with a 12345678 CourseNana.COM

Up Phase CourseNana.COM

Note those elements in cells of index 2, 4, 6 ,8 ...,i.e. spaced by steps of 2
Each such cell’s value is replaced by the sum of the current value and the value in the cell 1 place before it. All other cells keep CourseNana.COM

the same value CourseNana.COM

􏰊􏰊􏰊􏰊 CourseNana.COM

1
Note those elements in cells of index 4, 8, 12 ,16 ...,i.e. spaced by steps of 4 CourseNana.COM

Each such cell’s value is replaced by the sum of the current value and the value in the cell 2 places before it. All other cells keep the same value CourseNana.COM

1 CourseNana.COM

􏰊􏰊 CourseNana.COM

133
Note those elements in cells of index 4, 8, 12 ,16 ...,i.e. spaced by steps of 8 CourseNana.COM

Each such cell’s value is replaced by the sum of the current value and the value in the cell 4 places before it. All other cells keep the same value CourseNana.COM

133 CourseNana.COM

􏰊 CourseNana.COM

1 3 3 10 5 11 7 36 This is continued until, as just reached in this example, there are no further changes. CourseNana.COM

CourseNana.COM

Down Phase CourseNana.COM

Note those elements in cells of index 4, 8, 12 ,16 ... i.e. spaced by steps of 4 (i.e. one less than the highest reached in the up phase) CourseNana.COM

Each such cell’s value contributes to a sum of the current value and the value in the cell 2 places after it. All other cells keep the same value CourseNana.COM

133 CourseNana.COM

􏰊 CourseNana.COM

1 3 3 10 5 21 7 36 Note those elements in cells of index 2, 4, 6 ,8 ...,i.e. spaced by steps of 2 CourseNana.COM

Each such cell’s value is contributes to a sum of the current value and the value in the cell 1 places after it. All other cells keep the same value CourseNana.COM

1 CourseNana.COM

􏰊􏰊􏰊 CourseNana.COM

13 36 We could compress this into the following to succinctly show the evolution to the final result. CourseNana.COM

1 Noting cells spaced by steps of 2 Noting cells spaced by steps of 4 Noting cells spaced by steps of 8 CourseNana.COM

Noting cells spaced by steps of 8 CourseNana.COM

Noting cells spaced by steps of 4 1 Noting cells spaced by steps of 2 CourseNana.COM

13 36 CourseNana.COM

Outlined dells are the noted ones per round and shaded cells are those whose value has changed
A different example illustrates the need to
pad with zeros the total number of elements to a power of 2 CourseNana.COM

311 0 0 CourseNana.COM

12 0 0 4 CourseNana.COM

57 CourseNana.COM

57 57 57 CourseNana.COM

3 10 57 CourseNana.COM

3 10 57 CourseNana.COM

Get in Touch with Our Experts

WeChat (微信) WeChat (微信)
Whatsapp WhatsApp
Concurrent Programming代写,C代写,Prefix Scan代写,MPI代写,Concurrent Programming代编,C代编,Prefix Scan代编,MPI代编,Concurrent Programming代考,C代考,Prefix Scan代考,MPI代考,Concurrent Programminghelp,Chelp,Prefix Scanhelp,MPIhelp,Concurrent Programming作业代写,C作业代写,Prefix Scan作业代写,MPI作业代写,Concurrent Programming编程代写,C编程代写,Prefix Scan编程代写,MPI编程代写,Concurrent Programmingprogramming help,Cprogramming help,Prefix Scanprogramming help,MPIprogramming help,Concurrent Programmingassignment help,Cassignment help,Prefix Scanassignment help,MPIassignment help,Concurrent Programmingsolution,Csolution,Prefix Scansolution,MPIsolution,