Introduction
并行计算的作业，解决Red/Blue问题。何为Red/Blue问题？其实是这个作业原创的问题，就是为了让你练习OpenMP编程。
Problem
The Red/Blue computation simulates two interactive flows: an n by n board is initialized so cells have one of three colors: red, white, and blue, where white is empty, red moves right, and blue moves down. (The board may be initialized with 1/3 cells in read, 1/3 in white and 1/3 in blue and colors should be interleaved and spread across the board. You need to write a separate function board_init to initialize the board.) Colors wraparound to the opposite side when reaching the edge. In the first half step of an iteration, any red color can move right one cell if the cell to the right is unoccupied (white); on the second half step, any blue color can move down one cell if the cell below it is unoccupied (white); the case where red vacates a cell (first half) and blue moves into it (second half) is okay. Viewing the board as overlaid with t by t tiles (t divides n), the computation terminates if any tile’s colored squares are more than c% one color (blue or red).
Your Task
- Use MPI to write a solution to the Red/Blue computation.
- Assume the processes are organized as a one-dimensional linear array.
- It is fine to use a square grid, i.e. n by n grid for n being grid size.
- For simplicity assume n is divisible by t and t is divisible by the number of processes nprocs.
- Your program must produce correct results for nprocs being greater than or equal to one.
- Your program needs to ask for 4 user defined parameters (integers) as inputs: grid size n, tile size t, terminating threshold c, and maximum number of iterations max_iters.
- Your program needs to print out which tile (or tiles if more than one) has the colored squares more than c% one color (blue or red).
Submission
Your submissions will be marked on accuracy of results, suitability of the parallelism applied, and quality of your reports.
The report should be concise and clear (2-3 A4 pages) and should contain the following sections:
- Problem definition and Requirements
- Parallel algorithm design
- Implementation and Testing
- Manual (e.g. how to run the program, input and output)
You MUST attempt this assignment individually.
Tips
Step 1. Partition global grid for n/t x n/t processors
Step 2. Initialize half iteration (red) data structure
Step 3. Iterate within each t x t tile until convergence (guaranteed?)
Step 4. Initialize data structure – Compute new positions of red elts & associated white elts
Step 5. Communicate red boundary values
Step 6. Compute new positions of blue elts & associated white elts
Step 7. Communicate blue boundary values
Step 8. Check locally if DONE