CS 4960-01 Homework 7

Due: Monday, October 27th, 2008 10:45am

This homework is based on exercise 10 in chapter 4 of the textbook.

Computation Overview

The program uses an N by N array. Each element of the array is either white, red, or blue, as represented by the character ' ', 'r', or 'b', respectively. Half of the elements are white, one-fourth are red, and one-fourth are blue.

For example, the initial array might look like this if we draw the characters as pixels:

Blue elements want to fall down, wrapping to the top of the array when they fall off the bottom egde. Red elements want to fall right, wrapping to the left of the array when they fall off the right edge. An element can only fall if the adjacent cell is white. This process is specified more precisely below, but click on the image above to see it happen.

A single step consists of two parts:

1. Move every red element right one (wrapping from the right edge to the to the left edge), but only if the next position to the right (wrapping) is white at the beginning of the step.
2. Move every blue element down one (wrapping from the bottom edge to the to the top edge), but only if the next position down (wrapping) is white after the red-falling stage of the step.

As emphasized above, red movements for each step are based on the state at the beginning of the step, before any red movements. Blue movements for each step are based on the state half-way through the step: after all red movements, but before any blue movements.

Note that the total number of red and blue elements never changes; they just move to different array positions.

Your Task

Your first task is to implement the step transformation described above, building on the starter files that are supplied below. In array terms in this starter code, “down” means an increasing second index for the array, and “right” means an increasing first index; in other words, access the array as array[column][row] instead of the more common array[row][column] order (i.e., the instructor got the order wrong).

Your second task is to detect the following end conditions:

• Everything is stable, because nothing fell during the last step (so nothing will ever fall again).
• If you partition the array into sub-arrays of size T by T (where N divides evenly by T, so there are N/T times N/T sub-arrays), then at least one of the sub-arrays contains more than 50% red or more than 50% blue.

Ultimately, your program should simply report how many steps are needed until one of the above conditions are met. That is, for a given N, T, and initial board (as determined by a random seed that is supplied on the command line), your program should produce a number that corresponds to the number of steps taken to reach an end condition.

It's possible that neither of the ending conditions will happen for some configurations. For testing purposes, we use a specific random-number generator (supplied in a starter file) and a specific seed to obtain a specific expected result.

For large array sizes, such as N=512 and T=32, your OpenMP-based solution should obtain good speedup. The reference solution achieves a speedup close to 2 on the dual-processor CADE machines, a speedup of 1.6 under Mac OS X on a Core Duo, and a speedup of 1.6 under Linux for two threads on a 4-Xeon machine.

Starter Files

• hw7.c—this is the one you'll modify
• bsd_rand.c and bsd_rand.h—a random-number generator used by hw7.c

The size of the array N and the sub-array size T are #defined at the top of hw7.c. A command-line argument supplies a random-number seed for generating the initial array. If you change N in hw7.c to 100 and run it with the command-line argument 10, then it generates an array like the one depicted above.

The default output of the starter code is always 42. Your job is to make it print the number of falling steps needed to read one of the ending conditions (as described above).

If you set N to 100 and T to 10, then the correct result for the input seed 9 is 31 (a region has more than 50%), and the correct result for the input seed 11 is 39.

With N restore to 512 and T restored to 32, then the correct result for the input seed 9 is 133, and the correct result for the input seed 11 is 127.

Visualization Tools

If you run the starter code with an extra -show argument, then it prints each array state to stdout, and it doesn't print the final count.

The file hw7-anim.zip contains output for -show mode for N=100, T=10, and an input seed of 10, where the falling steps have been implemented and each board is printed in sequence. Before the first board, the size of the board is printed on its own line.

The show-rb.ss Scheme script can convert that kind of output into a picture using a little GUI. After unpacking hw7-anim.zip, you can view it on a CADE machine with

~mflatt/plt-x86/v4.1.1/bin/mred show-rb.ss < hw7-anim.zip

You could also install PLT Scheme to run the script on your own machine.

The visualization tool is completely optional. Your homework submission just needs to produce a single number as its output.