Project #3 – Parallel Sorting with OpenMP and MPI
SWE3021 Multicore Computing – Fall 2018
Due date: November 23 (Fri) 23:59pm
1 Goal
The purpose of this assignment is to give you experience writing a message passing program with MPI to building your understanding of message passing.
2 Game of Life
Game of Life is a cellular automaton formulated by the British mathematician, John Orton Conway in 1970. The “game” is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. The user just sets up the initial configuration and leaves the game to evolve on its own. Conway invented Life as a simplification of a much more complex model by John Von Neumann. Von Neumann had invented his automaton in a search for a hypothetical machine that could build copies of itself, and Conway’s Life can do the same. What particularly interests the computational community is that Life is Turing Complete, meaning it can compute any algorithm that a conventional computer can.
3 Details
The Game of Life models some genetic laws for birth, death, and survival. Consider a checkerboard consisting of an n-by-n array of cells. Each cell can be either alive (denoted by #) or dead (denoted by .).
The next state of each cell depends on the states of its neighbors. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:
• Any live cell with fewer than two live neighbors dies, as if caused by under-population.
• Any live cell with two or three live neighbors lives on to the next generation.
• Any live cell with more than three live neighbors dies, as if by over-population.
• Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.
The earliest interesting patterns in the Game of Life were discovered without the use of comput- ers. The simplest static patterns (“still lifes”) and repeating patterns (“oscillators”) were discovered while tracking the fates of various small starting configurations using graph paper, blackboards, physical game boards (such as Go) and the like.
For more information about this game, please refer to
https://en.wikipedia.org/wiki/Conway’s_Game_of_Life
1
4 Your Program
Your job is to write a parallel program to simulate Conway’s Game of Life.
• step1) Prompt a user to enter the size of a board (m). m is an arbitrarily large integer.
5
- step2) Prompt a user to enter how many generations to display (N).
- step3) Prompt a user to enter the state of cells, and store the states in a two-dimensional
array.
- step4) Let the master process display the final N’th generation. Note that the generation changes all at once. Only current cells are used to determine the next generation.
Note: You may assume inputs are always valid.
How to Parallelize
Your parallel version must use MPI to parallelize the computation. The grid (n by n array of cells) must be partitioned into small grids, with one (or more) row/column of padding on each side for cells whose values will be computed by other processors.
6
You can develop this program incrementally. For example,
• •
• •
First, get each process to do its local computation without any communication.
Second, start the communication by having processes exchange a single value (for example, each process with a left neighbor sends its upper-left cell, then each process with a right neighbor receives that value)
If exchanges of a single value work, change to receiving an entire column or row. Once one communication (e.g., send left/receive right) is working, add another.
Ghost Cells
Once the program is working, you should consider making the communication more efficient using so-called “ghost cells”. Ghost cells are cells in boundaries that are assigned to a neighbor process, but they are duplicated for performance reasons. By adding k rows and columns of ghost cells, each process will hold a copy of the data in neighbor processes simply to make the computations and message passing at the process easy. Besides this, we can reduce the number of message passing if we increase the number of rows and columns of ghost cells. Your program will take the number of additional columns and rows of ghost cells as an argument.
7 How to Run
If this is the first time you compile and run MPI programs in In-Ui-Ye-Ji cluster, you must add the following lines to your .bash_profile file.
#MPI_HOME MPI_HOME=/usr/local/openmpi-1.10.0 PATH=$PATH:$MPI_HOME/bin LD_LIBRARY_PATH=$LD_LIBRARY_PATH:$MPI_HOME/lib
export PATH export LD_LIBRARY_PATH
Once you added these lines, reload the .bash_profile by typing source ~/.bash_profile
Now you are ready to compile MPI programs using mpiCC compiler. 2
$ mpiCC -o project3 project3.cpp
For testing purposes, sample input and output files will be provided in /home/swe3021/project3/. Please copy them to your working directory and run the following mpirun command.
$ mpirun -np 16 ./project3 < input.txt > my_output.txt
This command will run 16 processes on your local host. To run your program on multiple hosts, you need to use the following command.
$ mpirun -hostfile hosts.txt -np 32 -loadbalance ./project3 < input.txt > my_output.txt
Note: < will read the text file (input.txt) and “redirect” the contents to the standard input so that your program can read the file with cin statements. The output of your program will be captured by another IO redirection operator “>” and stored in a file my_glider_output.txt.
$ diff my_output.txt sample_output.txt
The diff command displays any difference between two files. If it does not show any output, your output is correct.
For any question regarding this project, please post in Piazza Q&A so that we can share questions and answers with all other students and TAs. Also, please check Piazza regularly for any updates on this project.
8 How to Submit
To submit your project, you must name your code to project3.cpp and run multicore_submit command in your project directory in swin.skku.edu server.
$ multicore_submit project3 project3.cpp
This command will submit your code to the instructor’s account.
For any questions, please post them in Piazza so that we can share your questions and answers with other students. Please feel free to raise any issues and post any questions. Also, if you can answer other students’ questions, please don’t hesitate to post your answer. You would get some credits for posting questions and answers in Piazza.
3