Big Question inc. MIMD & Grids HELP

[thearchitectu]

hi everyone here is the killer!


Problem:

Setting:

Consider the following game:

The game is represented by a 96 X 96 grid, where each cell in the grid is a bit, and has 8 neighbors. Wrap-around connections are used for neighbors to edge cells. At each point of time, the following occur in parallel:

1. Any cell with a 1, and fewer than k1 neighboring 1's becomes a 0.

2. Any cell with a 1, and more than k2 neighboring 1's becomes a 0.

3. Any cell with a 1, and between k1 and k2 (inclusive) neighboring 1's stays as a 1.

4. Any cell with a 0, and exactly k3 neighboring 1's beomes a 1.

5. Any other cell with a 0 stays as a 0.

The constants k1, k2, and k3 are initialized to some value and updated as follows:

1. At every 100th time, set k1 = f1(grid) (i.e., f1 is a function of every element in the entire grid). You may assume that f1 is an expensive function to compute.

2. At every 200th time, set k2 = f2(grid). You may assume that f2 is also expensive to compute.

3. At every 100th time, set k3 =(f1(grid)*f2(grid)) mod 9

For example, using a 4X4 grid, the following grid:

1 0 0 1
1 0 1 1
0 0 0 0
0 0 1 0

would be transformed to this at the next point of time if <k1,k2,k3>=<2,3,3>:

1 0 0 0
1 1 1 0
0 1 1 0
0 0 0 1

Note that the 4X4 grid is only an example - the actual problem is for a bigger grid.

What I have to do?-------

Part 1: In class, we gave a 4 step approach to developing MIMD programs. Apply this technique to run this game on a MIMD system with 16 processors. You should clearly state the results of each step (partitioning, communication, agglomeration, mapping), along with justifications for any design decisions you made. You may assume that communication to neighbor memory takes 25 times as long as communication to local memory. Estimate your speedup. You will need to make some assumptions about the problem parameters beyond what is given - make sure you state these assumptions.

Part 2: Repeat the above if you have 20 processors.

How I have to do?-------

There are many acceptable solutions (and infinitely more incorrect solutions) to this problem. This will be graded primarily on how well you justify your answers, rather than your answers themselves. Also, there are places where you might make a non-optimal design choice. It is OK to do this (within reason), if you recognize that you did and clearly state why you did it.

I hope somebody has an answer I am stuck big time. Thank you for your time.

 

[lofgran]

Hello, thank you for posting your problem here. I would like to offer some suggestions and solutions to your problem.

Part 1: In order to develop a MIMD program for this game, we can follow the 4 step approach that was discussed in class. First, we need to partition the grid into equal parts for each processor. Since we have 16 processors, we can divide the grid into 4X4 subgrids for each processor. This will allow each processor to work on a smaller portion of the grid, reducing the workload and increasing efficiency.

Next, we need to consider communication between processors. Since communication to neighbor memory takes 25 times longer than communication to local memory, it would be beneficial to minimize communication between processors. To do this, we can use a data-driven approach where each processor only communicates with its neighboring processors when necessary. This will reduce the overall communication time and improve speedup.

For agglomeration, we can group the cells in each subgrid into clusters of cells. This will allow for efficient data access and processing within each processor. Additionally, we can use parallel processing within each processor to further increase efficiency. This can be achieved by dividing the clusters into smaller sub-clusters and processing them simultaneously.

For mapping, we can assign each subgrid to a specific processor and use a load balancing algorithm to evenly distribute the workload among the processors. This will ensure that no processor is overloaded and that all processors are utilized efficiently.

As for assumptions, I will assume that the grid size and the values for k1, k2, and k3 remain constant throughout the game. I will also assume that the functions f1 and f2 are independent of each other and can be computed simultaneously.

Based on these design decisions, I estimate that the speedup for this MIMD program will be approximately 15, as we are using 16 processors and assuming that the communication time is 25 times longer than local processing time.

Part 2: If we have 20 processors, we can follow a similar approach as in part 1. The only difference would be in the partitioning step, where we can divide the grid into 5X5 subgrids for each processor. This will allow for a more even distribution of workload among the processors and potentially increase the speedup. However, this will also result in smaller subgrids and possibly more communication between processors. Therefore, the speedup may