## Description

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