2024年6月24日

编程代写｜COMP3221 MPI Programming Assignment and Analysis

这是一个MPI 编程相关的CS代写案例

1. Assignment guidance

Implement an MPI program that reads in an image file and outputs a histogram of the number of pixels with each grey scale value. Constructing the histogram should use multiple processes. The image files are in uncompressed .pgm (portable greymap) format, in which each pixel takes a single integer value corresponding to its greyscale value, with 0 for black and some value maxValue for white. The image dimensions and maxValue are provided in the first few lines of the image file1.

2. Assessment tasks

You are provided with code that reads in the image file and constructs the histogram in serial. You need to adapt the code so that it constructs the histogram in parallel using MPI. For the first part of this assignment, you should use collective communication routines wherever possible, including distributing the necessary global parameters (i.e. the number of image pixels per process, and maxValue) to all processes.

Once you have this working, you should then implement an alternative implementation for the distribution of global parameters that uses point-to-point communication in a binary tree pattern. This alternative should be automatically called if the number of processes numProcs is a power of 2; if it is not a power of 2, your code should continue to use your original version. Your submitted code should therefore include two versions of the distribution of global parameters, each being called depending on the number of processes specified when launching with mpiexec.

Once you have the final version of your code, perform timing runs, on either a School machine or your own, to determine the parallel execution time as the number of pro- cesses is varied (the provided code already outputs this time). The combination of numbers of processes and nodes is given in the file readme.txt, and you should insert your results and discussion into this file, and include it when submitting. You should also interpret your results in terms of your understanding of MPI and the architecture you used for these timing runs.

You have been provided with code that reads in the image file to a data array on rank 0, with additional padding values of -1 so that the total array size is a multiple of the number of processes (this is a common way of handling data sets of arbitrary size). An example of how to construct the histogram in serial is also included.

The provided files are:

cwk2.c : readme.txt : cwk2 extras.h :

image.pgm : makefile : plotHistogram.py :

Starting point for your solution.
Use to provide results of your timing runs, and interpretation. Routines to load the image and save the histogram. Do not modify this file; it will be replaced with a different version for assessment.
An image to test your code on.
A simple makefile (usage optional).
Plots the histogram file (usage optional). To use: python plotHistogram.py (assumes in same directory as the output file hist.out; expects Python 3).

3. General guidance and study support

If you have any queries about this coursework, visit the Teams page for this module. If your query is not resolved by previous answers, post a new message. Support will also be available during the timetable lab sessions.

It is recommended that you proceed incrementally, testing your code after each stage of your calculations. For the binary tree, you may find it useful to insert print statements showing which rank each process is sending to or receiving from, to ensure that all sends have corresponding receives.

Collective communication was covered in Lecture 10 and reduction in Lecture 11. For the binary tree, you may like to consider an upside-down version of the second binary tree considered in Lecture 11, as it is easier to code. Think carefully about which ranks

send data, and which receive, at each level of useful:

1<<n : if( n && ((n&(n-1))==0) ) :

int lev=1; while(1<<lev<=p)lev++; : 4. Assessment criteria and marking process

the tree. You may find the following

Evaluates as 2n.
Evaluates as true if n is a power of 2.
Finds the number of levels lev in a binary tree with p leaf nodes.

Your code will be checked using an autograder on Gradescope to test for functionality. Staff will then inspect your code the allocate the marks as per the mark scheme (see below)