程序代写代做代考 case study Fortran algorithm No Slide Title

No Slide Title

Image Processing
A case study for a domain decomposed MPI code

Reusing this material

This work is licensed under a Creative Commons Attribution-
NonCommercial-ShareAlike 4.0 International License.

http://creativecommons.org/licenses/by-nc-sa/4.0/deed.en_US

This means you are free to copy and redistribute the material and adapt and build on the
material under the following terms: You must give appropriate credit, provide a link to the
license and indicate if changes were made. If you adapt or build on the material you must

distribute your work under the same license as the original.

Acknowledge EPCC as follows: “© EPCC, The University of Edinburgh, www.epcc.ed.ac.uk”

Note that this presentation contains images owned by others. Please seek their permission
before reusing these images.

3

http://creativecommons.org/licenses/by-nc-sa/4.0/deed.en_US
http://creativecommons.org/licenses/by-nc-sa/4.0/deed.en_US
http://creativecommons.org/licenses/by-nc-sa/4.0/deed.en_US
http://creativecommons.org/licenses/by-nc-sa/4.0/deed.en_US
http://creativecommons.org/licenses/by-nc-sa/4.0/deed.en_US
http://creativecommons.org/licenses/by-nc-sa/4.0/deed.en_US

Domain Decomposition 1

• Starting with a big array:

4

Domain Decomposition 2

• Split it into pieces:

5

Domain Decomposition 3

• Assign pieces to processors:

6

Domain Decomposition 4

• Use Halos to deal with interactions

7

Edge detection / image reconstruction

8

hundreds of

iterations

single

pass

Edge detection

• Compare pixel to its four nearest neighbours

– pixel values are from 0 (black) to 255 (white)

• Pad 2D arrays with halos

– in serial code, halo values set to white (i.e. 255)

9

edge
i, j

= image
i+1, j

+ image
1, j+1

+ image
i-1, j

+ image
i, j-1

– 4 image
i, j

Image reconstruction

• Jacobi Solver to undo the simple edge detection algorithm

(a five-point stencil)

– simple example of discretised partial differential equation with

nearest-neighbour interactions

– actually solving

• Repeat many times

– in parallel, must update halo values from neighbours every iteration

10

new
i, j

=
1

4
old

i+1, j
+old

1, j+1
+old

i-1, j
+old

i, j-1
– edge

i, j( )

Ñ
2
image = edge

Domain Decomposition

• Different choices in C and Fortran

11

The case study

• I provide you with:

– More detailed printed instruction

– Tar-ball (Choice of C or Fortran)

• Input routine

• Output routine

• Couple of input files

• Tasks

– Write a serial code (with halos for fixed boundary conditions)

• check that the serial code works!!

– Distribute the work onto the processors; separate reconstructions

– Get the halos exchanged; single reconstruction, identical to serial

– Further suggestions on the instruction sheet

12