DTS202TC Fundamentals of Parallel Computing - Assingment 1: Rotate a grayscale image
Overview
The purpose of this assignment is to gain experience in C programming and parallel algorithm design. You are expected to write a C serial program to rotate a grayscale image (without parallelism), and provide a parallel algorithm design that speeds up the serial implementation. Identify the bottlenecks in your serial implementation and provide an outline of how you plan to parallelise the serial implementation. Highlight the performance improvements you expect after parallelisation and potential challenges you may have to overcome. You may include pseudo-code or explain your approach in plain English.
Learning Outcomes
A. Identify serial and parallel algorithm.
B. Appreciate basic principal and techniques in devising parallel algorithm.
I. Apply common parallel algorithm patterns.
K. Identify and solve a computational problem with parallel algorithm design and program.
Team policy
You are free to form your group up to 5 team members (with a minimum of two members), you need to submit all team members’ information before 13th Nov, 23:59 via LMO. Students who fail to do so will be randomly assigned to a team. Changes will not be allowed once the teams have been confirmed.
Avoid Plagiarism
Do not submit work from other teams.
Do not share code/work to students other than your own team members.
Do not read code/work from other teams, discussions between teams should be limited to high level only.
Do not use open-source code
Algorithm 1
1: new_height j height cosine./ jCj width sine./ j
2: new_width j width cosine./ jCj height sine./ j F Define the height and width of the new image rotated
3:
4: ori_centrew width=2
5: ori_centre_h height=2
6: new_centre_w new_width=2
7: new_centre_h new_height=2
8: for i D 0;1;2;:::;height 1 do
9: for j D 1;2;:::;width 1 do
10: 11: | x y | width ori_centre height ori_centre | _ _ | w h | j i F coordinates | of pixel with respect to the centre of original |
image
12:
13: new_x x cosine./ C y sine./
14: new_y y cosine./ x sine./
15: 16: | new | new_x new_y image | new_centre_ new_centre_ | w h | new_x new_y | 1 1 | F coordinates of pixel with respect to the centre of |
17: img_outŒnew_yŒnew_x img_inŒiŒj F make sure new_x and new_y are integers, and don’t forget to check the boundaries
18: end for
19: end for
1 Serial Version (30 points)
1.1 Image Rotation
Image rotation is one of the most common image processing algorithms. To complete the rotation we need to write the pixel value for each pixel in the new location. Using some High School geometry we can work out the relationship between the source coordinates (x, y) and the destination coordinates
(x0, y0)
x0 D x cos C y sin
(1) y0 Dx sin C y cos
A complete pseudocode has been provide in Algorithm 1.
You will see some dots after this simple rotation algorithm, don’t worry about that for this coursework.
1.2 Reading and Writing Image
You will need to read a PGM image, process the rotation, then write the rotated PGM image back to the file system. Plain PGM format is a simple grayscale graphic image format, each pixel is represented by its grey value number, with 0 being black and Maxval (defined in the PGM file) being white. The below image.pgm is given as an example, more detail pgm specifications can be found at http://davis.lbl.gov/Manuals/NETPBM/doc/pgm.html
image.pgm
P2 24 7 15 | ||||||||||||||
0 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 0 0 0 0 | 0 | 0 0 0 0 0 | 0 |
0 3 | 3 | 3 | 3 | 0 | 0 | 7 | 7 | 7 | 7 | 0 | 0 11 11 11 11 | 0 | 0 15 15 15 15 | 0 |
0 3 | 0 | 0 | 0 | 0 | 0 | 7 | 0 | 0 | 0 | 0 | 0 11 0 0 0 | 0 | 0 15 0 0 15 | 0 |
0 3 | 3 | 3 | 0 | 0 | 0 | 7 | 7 | 7 | 0 | 0 | 0 11 11 11 0 | 0 | 0 15 15 15 15 | 0 |
0 3 | 0 | 0 | 0 | 0 | 0 | 7 | 0 | 0 | 0 | 0 | 0 11 0 0 0 | 0 | 0 15 0 0 0 | 0 |
0 3 | 0 | 0 | 0 | 0 | 0 | 7 | 7 | 7 | 7 | 0 | 0 11 11 11 11 | 0 | 0 15 0 0 0 | 0 |
0 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 0 0 0 0 | 0 | 0 0 0 0 0 | 0 |
Your program should be compiled and executed by:
make
./rotate-image{degreeinint}
Your program read the im.pgm file and output an rotated image named im-rotated.pgm
2 Parallel Algorithm Design (30 points)
Now that you have a complete understanding of the task, do the following:
Identify and analyse the bottlenecks of your serial implementation using necessary profiling tools. (10 points), and
provide a design of a solution to speed up using parallel programming (20 points).
You do not need to do the actual coding for the parallel implementation, but only provide the detailed design with maximum 500 words. You may include pseudo-code or explain your approach in plain English. Highlight the performance improvements you expect after parallelisation and potential challenges you may have to overcome.
3 Peer Assessment (30 points)
Please review your peers based on the actual contributions. This will be done on LMO anonymously, each of the group members should login their LMO account and submit the marks individually. Marks should be submitted as soon as the group work submission is done. Peer review rubrics are attached in the appendix table.
4 Submission (10 points)
One of the group members must submit the following files:
rotate-image.c C code of the serial implementation .
A Makefile that will compile your code, make sure the output executable names are correct.
A report.pdf file contains all the source code and the parallel design. You should also include the Cover Page with the student ID of all group members (template can be found on LMO) in the first page of your pdf.
Once you have all the files, please put them in a single directory (named groupid-A1) and compress them into to a single .zip file. You must follow the following structure:
The assignment must be submitted via Learning Mall to the correct drop box. Only electronic submission is accepted and no hard copy submission. All students must download their file and check that it is viewable after submission. Documents may become corrupted during the uploading process (e.g. due to slow internet connections). However, students themselves are responsible for submitting a functional and correct file for assessments.
Please note that quality of report and correctness of submission will also be marked (10 points in total, 5 points for the quality of report, 5 points for the correctness of submission).
Table 1: Peer Review Rubrics
Marks 10 7 4 0
Contributions Routinely provides Usually provides Sometimes Rarely provides useful ideas when useful ideas when provides useful useful ideas when participating in the participating in the ideas when participating in the group discussion. group discussion. participating in the group discussion.
A leader who A strong group group discussion. A May refuse to contributes a lot of member who tries satisfactory group participate.
effort. hard! member who does
what is required.
Problem Actively looks Refines solutions Does not suggest or Does not try to solving for and suggests suggested by refine solutions, but solve problems or solutions to others. is willing to try out help others solve problems. solutions suggested problems. Lets by others. others do the work.
Working with Almost always Usually listens to, Often listens to, Rarely listens to, others listens to, shares shares, with, and shares with, and shares with, and with, and supports supports the efforts supports the efforts supports the efforts the efforts of of others. Does not of others, but of others. Often others. Tries cause "waves" in the sometimes is not a is not a good team to keep people group. good team member. player.
working well together.
