Results 1 to 3 of 3

Thread: big Question inc. MIMD & Grids HELP!

  1. #1 big Question inc. MIMD & Grids HELP! 
    New Member
    Join Date
    Dec 2010
    hi everyone here is the killer!



    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.

    Reply With Quote  


  3. #2  
    Join Date
    Aug 2010
    The problem itself is a killer let alone the answer!
    I am not working on finding the answer but on understanding the question!

    Reply With Quote  

  4. #3  
    New Member
    Join Date
    Dec 2010
    yeah tell me about it. It is a total bullshit i have no idea what the hell this guy is asking for. I am thinking left and right but can not come up not even with an approach. any ideas ???
    Reply With Quote  

Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts