Topic #1 Module: Computing a Julia Set

Augment your program so that it saves the image to a file called julia.bmp, which stores the image in the bmp format. A bmp file consists of two parts:

To make the above easier you are first provided with a helper C function, write_bmp_header(), which writes to a file the 40-byte header required for a bmp file. [Download source of write_bmp_header()]

/* write_bmp_header():
 *
 *   In:
 *      f: A file open for writing ('w') 
 *      (width, height): image dimensions
 *   
 *   Return:
 *      0 on success, -1 on failure
 *
 */

int write_bmp_header(FILE *f, int width, int height) {

  unsigned int row_size_in_bytes = width * 3 + 
	  ((width * 3) % 4 == 0 ? 0 : (4 - (width * 3) % 4));

  // Define all fields in the bmp header
  char id[3] = "BM";
  unsigned int filesize = 54 + (int)(row_size_in_bytes * height * sizeof(char));
  short reserved[2] = {0,0};
  unsigned int offset = 54;

  unsigned int size = 40;
  unsigned short planes = 1;
  unsigned short bits = 24;
  unsigned int compression = 0;
  unsigned int image_size = width * height * 3 * sizeof(char);
  int x_res = 0;
  int y_res = 0;
  unsigned int ncolors = 0;
  unsigned int importantcolors = 0;

  // Write the bytes to the file, keeping track of the
  // number of written "objects"
  size_t ret = 0;
  ret += fwrite(id, sizeof(char), 2, f);
  ret += fwrite(&filesize, sizeof(int), 1, f);
  ret += fwrite(reserved, sizeof(short), 2, f);
  ret += fwrite(&offset, sizeof(int), 1, f);
  ret += fwrite(&size, sizeof(int), 1, f);
  ret += fwrite(&width, sizeof(int), 1, f);
  ret += fwrite(&height, sizeof(int), 1, f);
  ret += fwrite(&planes, sizeof(short), 1, f);
  ret += fwrite(&bits, sizeof(short), 1, f);
  ret += fwrite(&compression, sizeof(int), 1, f);
  ret += fwrite(&image_size, sizeof(int), 1, f);
  ret += fwrite(&x_res, sizeof(int), 1, f);
  ret += fwrite(&y_res, sizeof(int), 1, f);
  ret += fwrite(&ncolors, sizeof(int), 1, f);
  ret += fwrite(&importantcolors, sizeof(int), 1, f);

  // Success means that we wrote 17 "objects" successfully
  return (ret != 17);
}

Second, here is a code fragment that shows how to write the pixels in a 1-D pixed array to a bpm file (opened as file output_file) after the header has been written:

// Writing the pixels after the header
for (y=0; y < height; y++) {
  for (x=0; x < width; x++) {
    fwrite(&(pixels[y * 3 * width + x * 3]), sizeof(char), 3, output_file);
  }
  // padding in case of an even number of pixels per row
  unsigned char padding[3] = {0,0,0};
  fwrite(padding, sizeof(char), ((width * 3) % 4), output_file);
}

Given the above, it should be straightforward to augment your program so that it produces a bmp file of the Julia set. Verify that the produced image is as shown below (by opening in whatever image viewing application, or a Web browser):

Once this is done, you are ready to go on to Activity #2, in which we make the program parallel!

Augment your program so that each process allocates space to store the pixels it needs to compute, and then computes them. A process must only allocate space for the pixels it needs to compute. In practice, each process runs on a different hosts, and one wishes to compute a large image that does not fit in the memory of a single host (which is one of the main motivations for going the "distributed-memory computing" route).

Have each process print its rank and time (using MPI_Wtime(), which returns a double) right before performing the computation and right after performing the computation!. Our cluster is not completely homogeneous, and these (simulated) times will show it.

The main difficulty here is keeping local vs. global indexing straight. That is, although as programmers we think of the image as an array of, say, N pixels, no N-pixel array is ever allocated in the program (only smaller arrays allocated by each process).

Augment your program so that the Julia set is saved to a bmp file. This requires some coordination between the processes:

First you must pick one process to create the file and write the header to it (it is typical to pick process of rank 0). Second, each process, after its done computing its pixels, waits for a "go ahead!" message from its predecessor, writes to the file, and then sends a "go ahead!" message to its successor. The exceptions are the process with rank 0, which does not need to wait for a message, and the last process, which does not need to send a message. It doesn't really matter what these messages contain (e.g., they can be a single byte, or even zero-byte messages), as the whole purpose is to just have processes wait for their predecessors, not really receive meaningful data from them.

Warning: Make sure that your processes compute in parallel. That is, all processes compute together, and then they take turn writing what they have computed to the file.

Experiment with different numbers of processors and different values of n, and check that your bmp file is correct (valid, and contains the correct image).

Augment your program so that each process allocates space to store the pixels it needs to compute, and then computes them. As in the previous activity, the main difficulty here is keeping local vs. global indexing straight. It is a bit more complex than for Activity #2 due to the use of a 2-D data distribution.

Have each process apply a tint to the pixels it handles, by passing value rank2 (i.e., the square of the rank) as the 5th argument to function compute_julia_pixel() (instead of passing the default 1.0 value).

Augment your program so that the Julia set is saved to a bmp file. The difference with Activity #2 is that now each process holds a tile, and yet the file must contain the pixels in row major order. So each process will have to append many times to the file, writing one piece of a row at a time. As a result, more complex coordination is required compared to Activity #2.