- #1
thearchitectu
- 1
- 0
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.
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.