Advanced Computing Group Assignment 2 SOLVED

ENEL464 Embedded Software and Advanced
Computing 
Group Assignment 2 Draft

1 Introduction
The purpose of this assignment is to implement a numerical algorithm on a desktop computer to
make the most efficient use of its caches and multiple cores.
The algorithm is Jacobi relaxation. This is an iterative algorithm used to approximate differential
equations, for example, Poisson’s and Laplace’s equations. Poisson’s equation can be used to find
the electric potential given a specified charge distribution or temperature given a specified heat
source. There are more efficient ways to solve this problem using Green’s functions and Fourier
transforms but that is not the purpose of this assignment.
2 Jacobi relaxation
The discrete form of Poisson’s equation,
∇2Vi,j,k = fi,j,k, (1)
can be solved iteratively using Jacobi relaxation, where for voxels inside the boundary at iteration
n
Vi,j,k,n =
1
6
?
Vi+1,j,k,n−1 + Vi−1,j,k,n−1 + Vi,j+1,k,n−1 + Vi,j−1,k,n−1 + Vi,j,k+1,n−1 + Vi,j,k−1,n−1 − ∆2
fi,j,k?
.
(2)
Here ∆ = ∆x = ∆y = ∆z is the spacing between voxels in metres. Voxels on the boundary (i = −1,
i = N, j = −1, j = N, k = −1, k = N) have a value 0. This is a Dirichlet boundary condition,
equivalent to a metal box at ground potential.
1
3 Implementation
Implement an algorithm for Jacobi relaxation in either C or C++. Your goal is to find a fast
implementation that will run on a CAE lab computer, making best use of the caches and multiple
cores.
Your implementation needs to work with an arbitrary 3-D source distribution f. The potential V
needs to be stored as a double data type.
4 Testing
Test your algorithm with a single point charge in the centre of the volume, i.e.,
fi,j,k =
(
1 i = N/2, j = N/2, k = Nz/2,
0 otherwise
, (3)
where the volume is comprised of N ×N ×N voxels. Note, your algorithm must work with arbitrary
source distributions.
5 Support
Only questions submitted via the ENCE464 assignment forum will be answered. Emails will be
quietly ignored.
6 Reports
The reports are to be submitted as PDF documents through the ENCE464 Learn page. They will
be submitted to TurnItIn for plagiarism checking.
Guidelines for writing a report are available at
https://eng-git.canterbury.ac.nz/mph/report-guidelines/blob/master/report-guidelines.
pdf.
Each report is to use a 12 point font and be no longer than four pages, excluding any appendices.
Ensure in your report that you discuss your implementation in terms of cache usage and core usage.
You should present profiling information showing which parts of your program takes the most time
to execute.
Your report should present the average time and standard deviation of the time to run 1000
iterations of your implementation for N = 101, 201, 301, 401, 501, 601, 701, 801, 901.
2