CmpE300 - Analysis of Algorithms Programming Project
Aysu Sayın 20.12.2018
The project is to implement a parallel algorithm for image denoising with the Ising model using Metropolis Hastings algorithm. Algorithm works as follows: Image is given as a text file consisting of -1 and 1. Each value represents the value of the pixel in the corresponding place in the image file. This is stored in a two dimensional array. Then a pixel is selected randomly. A bit flip is proposed on this pixel. Now we need to decide if we want to flip the bit or not. To do so, acceptance probability is calculated with the following formula:
Z is the image at time step t generated from Ising model (parametrized by β) and X is generated by flipping a pixel of Z with a small probability π: γ = 1 /2 * log ((1 − π)/π). A random number is selected from [0,1] and if this random number is less than the acceptance probability, the bit is flipped. To make sure we selected enough pixel, we need to repeat this several times like 5 000 000. Since this is a huge number, the program will take a long time. We can use parallel programming to overcome this problem. One master processor reads the input file and distributes the input file equally among p slave processors. Then each slave processor runs the algorithm on their own part of the data. But to decide to flip a pixel on the edge, we need to communicate with the next processor. This is visualized below.
There is no GUI for this program. User must run this code via terminal. First you need to install Open MPI. Then, change the directory to the project directory. You can compile the code with the following command: mpicxx -g main.cpp -o mpi-project Now you can run the program with the given processor number n as follows: mpiexec -n [n] ./mpi-project [noisy-image.txt] [output-file.txt] [beta] [pi]
User needs to run the program with this command:
mpiexec -n [n] ./mpi-project [noisy-image.txt] [output-file.txt] [beta] [pi]
n: number of processors that will run this program (An integer value p where 200 is divisible by p-1)
noisy-image: Array representation of the image that is going to be denoised. Image size is 200x200. In txt format.
output-file: This file is created in the program and array representation of the denoised image is written to file. In txt format.
beta :The image is generated from Ising model (parametrized by β).(A double value between 0-1)
pi: Probability of flipping a pixel when creating the noisy image. (A double value between 0-1)
In the main function, first check if the arguments are given. If there are less than required arguments, print a warning message to the console and terminate the program. Then the variables are initialized. The processor with world rank 0 is the master processor. There a two dimensional array is declared and the input file is read and saved into this array. The image is needed to be sent to slave processors so it is divided into equal sizes and each row is sent separately by using MPI_Send() function. After each slave process finishes bit flips, master receives the flipped version of the image from each processor with MPI_Recv() function. Since both functions are blocking, there is no synchronization problem. MPI_Recv will wait until the message is received. Then it writes the result into the output txt file.
The other processors are called slave processors. First the array is received and stored in a two dimensional array called imageSubArr. This array is copied to flippedArr since we will need both in our calculations. (A helper function copy is defined.) A random number generator device is initialized since the bits are selected randomly. Also distributions are declared.Both dis0 and dis1 are integer distributions where dis0 is for selecting a row number and dis1 is for selecting a column number. dis2 is a double distribution in range [0,1]. For loop needs to be ran for a sufficient amount of iterations to choose nearly all pixels. Since the image size is 200x200, 500 000 iterations for whole image is sufficient. In the for loop after choosing i and j randomly from corresponding distributions, each processor sends it first row (except for processor with rank 1) and last row (except for last processor). Also, they receive the last row of the previous processor’s subarray (store it in preRow) and the first row of the next processor’s subarray (store it in nextRow). To prevent deadlock, the processes with even rank send the subarrays first and the ones with odd rank receives first. In order to calculate the acceptance probability we need to find the sum of the values around the selected pixel. If the selected pixel is on the edge, then we need to use preRow or nextRow too. So according to the value of i and j, the values on the preRow and nextRow are added to sum. There is a helper function called calculateSum to calculate the sum of the values within the given boundaries. So the upper and lower bounds are decided in if clauses as well and the result of the calculateSum function is added to sum. Then, acceptance probability acceptanceP is calculated according to the formula given in the Introduction. A random value between 0 and 1 is generated and if this value is less than acceptanceP then the pixel is flipped. After all for loop iterations, the flippedArr is sent to master process.
- Yinyang Example Run the program with the following command:
mpiexec -n 5 ./mpi_project yinyang_noisy.txt yy-out.txt 0.8 0.15
- Lena Example Run the program with the following command:
mpiexec -n 5 ./mpi_project lena200_noisy.txt lena-out.txt 0.8 0.15
Since the for loop in slave processors sends the last and first row each iteration, this takes a long time and this send and receive process is unnecessary in the most cases. A different strategy can be used here. For example, the initial state of the these rows can be sent before for loop. Whenever a value is changed on the edge, this row can be sent to the neighbor processor. But to do this, we need to use nonblocking send and receive functions. Thus, this becomes a synchronization problem.
Since I haven’t used C++’s random methods before, I wasn’t aware of the problems of rand() method. By using rand method, I wasn’t able to denoise the image properly. I spent so much time to figure what is wrong with my code. Also, I couldn’t find a proper tool for debugging MPI so I used cout’s to debug the code :( After searching online, I found other ways of defining random number generators. Also, using seed is a must when using random number generator in C++.
In conclusion, this project taught me how to use Open MPI and parallel programming. Also learning new concepts such as Monte Carlo Methods and Ising model was also great.