From an edge to the whole picture

Hi there!

It’s almost the end of summer holidays and the summer of HPC, and I still haven’t made to tell you everything about what I’m working on.

I was done with the CFD exercise so I started with a new one – image reconstruction. Actually, I was fiddeling with this exercise for a while during the first week within HPC and MPI workshop and implemented a serial a few parallel MPI versions of the code in C. Two weeks ago, I came back to this exercise again and re-implemented it in Python. The original application could only reconstruct an image in gray scale. I improved it so the application can also reconstruct colour images. Let’s take a look at it!

Fig.1: Colour edge detection.

The input is an image processed by an edge detector (as you can see in Fig. 1). The algorithm of reconstruction is very simple. The approach is iterative and the new pixel values are calculated using it’s neighborhood and the pixel in the edge detected image. The main aim was to parallelise the application using MPI (that’s not surprising). I started with 1D decomposition of the problem – maybe you remember my last blog post where I explained what 2D decomposition means. 1D decomposition is a bit simpler – just cut the grid (image in this case) into horizontal stripes, so that each processor can work on one stripe (see Fig. 2). You may ask me why I cut the grid into stripes just in this way. It’s related to methods for managing multidimensional arrays in a memory. Therefore we distinguish the row-major and column-major order in programming languages. Python is row-major in default (if you are using numpy arrays, you can also change the order).

Fig. 2: 1D decomposition

Fig. 3: 2D decomposition

Figure 2 with the Loch Ness monster clearly describes row-major order as well as the importance of using halo zones swapping to exchange data among processes during calculation (if you don’t remember what that means, see my previous blog post) – since the processes do not exchange any data, there are white stripes emerging in the image. Such a picture can’t be reconstructed properly.

I created an animation for you to illustrate how the algorithm works and how it converges to the final product. Check Fig. 4!

Fig. 4: Demonstration of how the algorithm works.

I tested several communication strategies and focused on blocking and nonblocking MPI point-to-point communications, investigated the benefits of virtual topologies and rank reordering. Fig. 5 with a plot shows how Python and C version stand in performance.

Fig. 5: Image Reconstruction Performance Results

Meanwhile in the Edinburgh – I’ve visited many new amazing places! I really love this city! Briefly and helter-skelter. Not sure if you’ve noticed but there’s a characteristic smell of the town – I find it like a smell of brewery. Seagulls, again! Those birds never sleep. I can hear them whole night. I ate a lobster (tasty, funny and a wonderful experience)! I was in North Berwick to see puffins (the small sea birds looking like small penguins). Unfortunately, it was too late because puffins are there only till the end of July. However, I enjoyed the town and its lovely beach a lot. Then, I also visited Pentlands hills – that day was very hot (real summer day, unbelievable! My nose slightly got a sunburnt). Sheep were following me on every single step. That’s not all. I visited a lot of new pubs and cafes, explored a new Sunday market with handmade stuff, clothes, food and drinks. I was in the historic Dean Village (real village in the middle of the city) and Royal Botanic garden which is quite huge and very nice place to relax. It truly worths visiting those places. And finally (but I’m sure I forget many things to tell) I took a cool silver tour in a distillery (Gaelics used to say “Slange-va” to say “Cheers”) and danced traditional Scottish dances. Everything is just pretty awesome, awesome, awesome!

New experiences – Petlands Hills, Botanic Garden, a strange and crazy girl, Zoidberg, Cramond.

Enjoy!

Marta