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