COM4521/COM6521 Parallel Computing with
Graphical Processing Units (GPUs)
Assignment (80% of module mark)
Deadline: 5pm Friday 17th May (Week 12)
Starting Code: Download Here
Document Changes
Any corrections or changes to this document will be noted here and an update
will be sent out via the course’s Google group mailing list.
Document Built On: 17 January 2024
Introduction
This assessment has been designed against the module’s learning objectives. The
assignment is worth 80% of the total module mark. The aim of the assignment is
to assess your ability and understanding of implementing and optimising parallel
algorithms using both OpenMP and CUDA.
An existing project containing a single threaded implementation of three algorithms has been provided. This provided starting code also contains functions
for validating the correctness, and timing the performance of your implemented
algorithms.
You are expected to implement both an OpenMP and a CUDA version of each of
the provided algorithms, and to complete a report to document and justify the
techniques you have used, and demonstrate how profiling and/or benchmarking
supports your justification.
The Algorithms & Starting Code
Three algorithms have been selected which cover a variety of parallel patterns for
you to implement. As these are independent algorithms, they can be approached
in any order and their difficulty does vary. You may redesign the algorithms in
1
your own implementations for improved performance, providing input/output
pairs remain unchanged.
The reference implementation and starting code are available to download from:
https://codeload.github.com/RSE-Sheffield/COMCUDA_assignment_c614d9
bf/zip/refs/heads/master
Each of the algorithms are described in more detail below.
Standard Deviation (Population)
Thrust/CUB may not be used for this stage of the assignment.
You are provided two parameters:
• An array of floating point values input.
• The length of the input array N.
You must calculate the standard deviation (population) of input and return a
floating point result.
The components of equation 1 are:
• σ: The population standard deviation
•
P = The sum of..
• xi = ..each value
• µ = The mean of the population
• N: The size of the population
σ =
sPN
i=1(xi − µ)
2
N
(1)
The algorithm within cpu.c::cpu_standarddeviation() has several steps:
1. Calculate the mean of input.
2. Subtract mean from each element of input.
3. Square each of the resulting elements from the previous step.
4. Calculate the sum of the resulting array from the previous step.
5. Divide sum by n.
6. Return the square root of the previous step’s result.
It can be executed either via specifying a random seed and population size, e.g.:
<executable> CPU SD 12 100000
Or via specifying the path to a .csv input file, e.g.:
<executable> CPU SD sd_in.csv
2
Convolution
You are provided four parameters:
• A 1 dimensional input array input image.
• A 1 dimensional output array output image.
• The width of the image input.
• The height of the image input.
Figure 1: An example of a source image (left) and it’s gradient magnitude (right).
You must calculate the gradient magnitude of the greyscale image input. The
horizontal (Gx) and vertical (Gy) Sobel operators (equation 2) are applied to
each non-boundary pixel (P) and the magnitude calculated (equation 3) to
produce a gradient magnitude image to be stored in output. Figure 1 provides
an example of a source image and it’s resulting gradient magnitude.
(3)
A convolution is performed by aligning the centre of the Sobel operator with a
pixel, and summing the result of multiplying each weight with it’s corresponding
pixel. The resulting value must then be clamped, to ensure it does not go out of
bounds.
The convolution operation is demonstrated in equation 4. A pixel with value
5 and it’s Moore neighbourhood are shown. This matrix is then componentwise multiplied (Hadamard product) by the horizontal Sobel operator and the
components of the resulting matrix are summed.
Pixels at the edge of the image do not have a full Moore neighbourhood, and
therefore cannot be processed. As such, the output image will be 2 pixels smaller
in each dimension.
The algorithm implemented within cpu.c::cpu_convolution() has four steps
performed per non-boundary pixel of the input image:
1. Calculate horizontal Sobel convolution of the pixel.
2. Calculate vertical Sobel convolution of the pixel.
3. Calculate the gradient magnitude from the two convolution results
4. Approximately normalise the gradient magnitude and store it in the output
image.
It can be executed via specifying the path to an input .png image, optionally a
second output .png image can be specified, e.g.:
<executable> CPU C c_in.png c_out.png
Data Structure
You are provided four parameters:
• A sorted array of integer keys keys.
• The length of the input array len_k.
• A preallocated array for output boundaries.
• The length of the output array len_b.
You must calculate the index of the first occurrence of each integer within the
inclusive-exclusive range [0, len_b), and store it at the corresponding index in
the output array. Where an integer does not occur within the input array, it
should be assigned the index of the next integer which does occur in the array.
This algorithm constructs an index to data stored within the input array, this is
commonly used in data structures such as graphs and spatial binning. Typically
there would be one or more value arrays that have been pair sorted with the key
array (keys). The below code shows how values attached to the integer key 10
could be accessed.
for (unsigned int i = boundaries[10]; i < boundaries[11]; ++i) {
float v = values[i];
// Do something
}
The algorithm implemented within cpu.c::cpu_datastructure() has two
steps:
4
1. An intermediate array of length len_b must be allocated, and a histogram
of the values from keys calculated within it.
2. An exclusive prefix sum (scan) operation is performed across the previous
step’s histogram, creating the output array boundaries.
Figure 2 provides a visual example of this algorithm.
0 1 1 3 4 4 4
0 1 3 3 4 7
1 2 0 1 3
+ + + + + + +
+ + + + + + + + + +
keys
histogram
boundaries
0 1 2 3 4 5 6
0 1 2 3 4
0 1 2 3 4 5
Figure 2: An example showing how the input keys produces boundaries in the
provided algorithm.
It can be executed via specifying either a random seed and array length, e.g.:
<executable> CPU DS 12 100000
Or, via specifying the path to an input .csv, e.g.:
<executable> CPU DS ds_in.csv
Optionally, a .csv may also be specified for the output to be stored, e.g.:
<executable> CPU DS 12 100000 ds_out.csv
<executable> CPU DS ds_in.csv ds_out.csv
The Task
Code
For this assignment you must complete the code found in both openmp.c
and cuda.cu, so that they perform the same algorithm described above
and found in the reference implementation (cpu.c), using OpenMP and
CUDA respectively. You should not modify or create any other files within
the project. The two algorithms to be implemented are separated into 3
methods named openmp_standarddeviation(), openmp_convolution() and
openmp_datastructure() respectively (and likewise for CUDA).
You should implement the OpenMP and CUDA algorithms with the intention of
achieving the fastest performance for each algorithm on the hardware that you
5
use to develop and test your assignment.
It is important to free all used memory as memory leaks could cause the
benchmark mode, which repeats the algorithm, to run out of memory.
Report
You are expected to provide a report alongside your code submission. For each of
the 6 algorithms that you implement you should complete the template provided
in Appendix A. The report is your chance to demonstrate to the marker that
you understand what has been taught in the module.
Benchmarks should always be carried out in Release mode, with timing
averaged over several runs. The provided project code has a runtime argument
--bench which will repeat the algorithm for a given input 100 times (defined
in config.h). It is important to benchmark over a range of inputs, to allow
consideration of how the performance of each stage scales.
Deliverables
You must submit your openmp.c, cuda.cu and your report document
(e.g. .pdf/.docx) within a single zip file via Mole, before the deadline. Your
code should build in the Release mode configuration without errors or warnings
(other than those caused by IntelliSense) on Diamond machines. You do not
need to hand in any other project or code files other than openmp.c, cuda.cu.
As such, it is important that you do not modify any of the other files provided
in the starting code so that your submitted code remains compatible with the
projects that will be used to mark your submission.
Your code should not rely on any third party tools/libraries except for those
introduced within the lectures/lab classes. Hence, the use of Thrust and CUB is
permitted except for the standard deviation algorithm.
Even if you do not complete all aspects of the assignment, partial progress should
be submitted as this can still receive marks.
Marking
When marking, both the correctness of the output, and the quality/appropriateness of the technique used will be assessed. The report
should be used to demonstrate your understanding of the module’s theoretical
content by justifying the approaches taken and showing their impact on the
performance. The marks for each stage of the assignment will be distributed as
follows:
6
OpenMP (30%) CUDA (70%)
Stage 1 (32%) 9.6% 22.4%
Stage 2 (34%) 10.2% 23.8%
Stage 3 (34%) 10.2% 23.8%
The CUDA stage is more heavily weighted as it is more difficult.
For each of the 6 stages in total, the distribution of the marks will be determined
by the following criteria:
1. Quality of implementation
• Have all parts of the stage been implemented?
• Is the implementation free from race conditions or other errors regardless
of the output?
• Is code structured clearly and logically?
• How optimal is the solution that has been implemented? Has good hardware
utilisation been achieved?
2. Automated tests to check for correctness in a range of conditions
• Is the implementation for the specific stage complete and correct (i.e. when
compared to a number of test cases which will vary the input)?
3. Choice, justification and performance reporting of the approach towards
implementation as evidenced in the report.
• A breakdown of how marks are awarded is provided in the report structure
template in Appendix A.
These 3 criteria have roughly equal weighting (each worth 25-40%).
If you submit work after the deadline you will incur a deduction of 5% of the
mark for each working day that the work is late after the deadline. Work
submitted more than 5 working days late will be graded as 0. This is the same
lateness policy applied university wide to all undergraduate and postgraduate
programmes.
Assignment Help & Feedback
The lab classes should be used for feedback from demonstrators and the module
leaders. You should aim to work iteratively by seeking feedback throughout the
semester. If leave your assignment work until the final week you will limit your
opportunity for feedback.
For questions you should either bring these to the lab classes or use the course’s
Google group (COM4521-group@sheffield.ac.uk) which is monitored by the
course’s teaching staff. However, as messages to the Google group are public to
7
all students, emails should avoid including assignment code, instead they should
be questions about ideas, techniques and specific error messages rather than
requests to fix code.
If you are uncomfortable asking questions, you may prefer to use the course’s
anonymous google form. Anonymous questions must be well formed, as there is
no possibility for clarification, otherwise they risk being ignored.
Please do not email teaching assistants or the module leader directly for assignment help. Any direct requests for help will be redirected to the above
mechanisms for obtaining help and support.
8
Appendix A: Report Structure Template
Each stage should focus on a specific choice of technique which you have applied
in your implementation. E.g. OpenMP Scheduling, OpenMP approaches for
avoiding race conditions, CUDA memory caching, Atomics, Reductions, Warp
operations, Shared Memory, etc. Each stage should be no more than 500 words
and may be far fewer for some stages.
<OpenMP/CUDA>: Algorithm <Standard Deviation/Convolution/Data Structure>
Description
• Briefly describe how the stage is implemented focusing on what choice of
technique you have applied to your code.
Marks will be awarded for:
• Clarity of description
Justification
• Describe why you selected a particular technique or approach. Provide
justification to demonstrate your understanding of content from the
lectures and labs as to why the approach is appropriate and efficient.
Marks will be awarded for:
• Appropriateness of the approach. I.e. Is this the most efficient choice?
• Justification of the approach and demonstration of understanding
Performance
Size CPU Reference Timing (ms) <Mode> Timing (ms)
• Decide appropriate benchmark configurations to best demonstrate scaling
of your optimised algorithm.
• Report your benchmark results, for example in the table provided above
• Describe which aspects of your implementation limits performance? E.g.
Is your code compute, memory or latency bound on the GPU? Have you
performed any profiling? Is a particular operation slow?
• What could be improved in your code if you had more time?
Marks will be awarded for:
9
• Appropriateness of the used benchmark configurations.
• Does the justification match the experimental result?
• Have limiting factors of the code been identified?
• Has justification for limiting factors been described or evidenced
?请加QQ：99515681 邮箱：99515681@qq.com WX：codinghelp