Assignment #3

Assignment #3

Due: November 13 before 16:00
To be done individually.

Grading

IPC and synchronization (including internal documentation): 50%
Display and input file implementation: 10%
Report: 30%
Testing and results: 10%

Change Log

November 12

Updated due date to November 13 (as agreed last week in class).

November 10

Allowed students to violate the restriction on minimal usage of shared memory.

October 30

Nadim's visualization library and sample life code made available.

October 27

Changed due date to November 12 (which leaves you with three weeks to complete the final assignment)

If you encounter any issues that have not been specified, you may make use of reasonable assumptions provided that these are clearly and explicitly stated in your report and are not in conflict with any of the assignment specifications. You may submit a partial solution to any of the components of this assignment. Grading will be balanced according to the difficulty of each component and the fraction completed.

Introduction

The Game of Life (GOL) was invented by Cambridge mathematician John Horton Conway in the late 1960s. The game, based on cellular automata theory, is played on an infinite grid of cells, each of which has eight neighbouring cells. A cell may be occupied by an organism or empty.

The rules for deriving the next generation from the current one are extremely simple:

If an occupied cell has 2 or 3 occupied neighbours in the current generation, it remains alive, otherwise it dies of loneliness or overcrowding
If an unoccupied cell has 3 occupied neighbours in the current generation, it becomes alive.

Despite its apparent simplicity, GOL exhibits incredible richness in its behaviour, and thus, has been the subject of intense study over the years. A quick search on the web will reveal many pointers and simulations of the game.

Conway's rules were chosen so that simple initial patterns can grow and change for a considerable period of time before coming to an end in three possible ways:

fading away completely
settling into a stable configuration that remains unchanged thereafter
entering an oscillating phase which repeats an endless cycle of two or more periods

Your Task

Your task for this assignment will be to implement a 3D version of the GOL, played on the six faces of a cube. The cells along the edges and at the corners of the cube will all be influenced by their neighbours on the other faces. Note that the corner cells only have seven neighbours each, but the rules of the game are still the same. Each of the six faces will be updated by a separate process. At the end of each iteration, the processes must synchronize (using Sys V semaphores) and communicate the state of shared cells (i.e. all edge and corner cells) through shared memory (using Sys V shared memory primitives). Only the shared cell values should be written to shared memory.

New: Because one process must have access to the state of all six faces in memory in order to display the cube using the graphics library, you are permitted to violate the restriction given above. However, bonus marks will be granted if you take the more elegant approach and continue to satisfy the display requirements without violating this restriction.

After every iteration, your program should output the state of each face as an NxN grid in ASCII format. Occupied cells are indicated by an asterisk (*) and unoccupied cells are left blank. The value of N may be defined in a header file, but your program must allow this value to be changed and still work correctly (within reasonable limits).

You have been provided with a simple GL library to provide an elegant 3D graphical visualization of your cube. This will be explained in further detail during the tutorial of Monday, November 2.

Testing

For testing purposes, you may choose to read in the starting patterns from a file or generate them randomly. Regardless, your program, when invoked with the command line argument, -test must initialize the cube with the following pattern, placed at the top-left corner of each face:

  **
 **
  *

This simple pattern is known to produce very interesting effects in the 2D case.

Submitting your assignment

You must submit a hardcopy consisting of the following:

a title page with your name, student number, and list of the assignment components you have completed

a brief report, containing the following:

a brief introduction to the purpose of the assignment without repeating the specifications themselves
a description of your synchronization and sharing strategy
a brief discussion of any bugs or limitations of your programs

The report should keep to a maximum of six pages, excluding test results; anything beyond the six-page limit will not be read. Avoid discussion of the graphics code that was provided to you. As always, flowcharts are punishable by being forced to sit through a one-week session of court testimony by Bill Gates, trying to explain how his company doesn't engage in unfair business practices.

your source code listings (with adequate internal documentation, of course)

sample output of three consecutive iterations of your program, demonstratating synchronization across multiple edge boundaries of the cube; this output should be generated in ASCII format, one NxN grid per face, with the results of each iteration printed on a separate page

In addition to the hardcopy submission, you must provide an electronic version of your assignment in UNIX tar(8) format, encoded with uuencode(1). The electronic submission will be compiled and tested automatically on one of the systems in the ECE undergraduate lab. The electronic submission must contain:

all of the source code required to compile your program under the Sun systems in the ECE undergraduate lab
a Makefile (see make(1)) for generating the program. The executable program must be named life

by sending an email message to the instructor.

Your message must be sent by November 12, 16:00. Assignments will not be considered complete if they have not been submitted both in hardcopy and electronically or if the two versions of the source code differ. Incomplete submissions will not be marked. The hardcopy and electronic versions may be submitted at different times within the assigned deadline.

In order to allow for automatic processing, your submission message must be formatted as specified in the following paragraphs. An unproperly formatted message will be automatically bounced back to the sender and the submission will not be considered complete. You may then correct the errors and resubmit. However, you may not resubmit after a properly formatted message has been accepted: please make sure that your files contain exactly what you wish to submit.

The "Subject:" field of your email message must have the following format: 427-A3-YOUR_STUDENT_ID, with the digits of your student ID number in place of YOUR_STUDENT_ID; do not write anything else in the subject; do not write anything in the message other than the tar file.

The tar file must create, when opened, a directory named with your student ID, containing all the source files (there may be subdirectories, if needed) and the Makefile as described above. An optional file named README may be included, containing instructions for the correct compilation and use of the library. Do not include any non-text files (e.g. compiled executables, relocatable objects), since they may be handled improperly by the email software, causing corruption of the entire tar file. Make sure that all files are in UNIX text format (lines terminated by a line-feed character, ASCII 10): use a converter if you edit them on a PC under MS-DOS/Windows.

An example sequence of UNIX shell commands that creates and sends a tar file as specified follows [comments in square brackets]:

[Create the source directory for student with id 952334.]
   % mkdir ./952334

[Copy all the sources in it.]
   % cp foo.c bar.c baz.c flop.c README ./952334

[Create the tar file with the directory content.]
   % tar cvf 427-A3-952334.tar ./952334

[Uuencode the tar file]
   % uuencode 427-A3-952334.tar 427-A3-952334.tar > 427-A3-952334.tar.uu

[Send it with the proper subject field.]
   % mail -s "427-A3-952334"  < 427-A3-952334.tar.uu

If the submission is correct, you will receive an automatic acknowledgement in reply. Otherwise, the message will be refused, and an explanatory error message will be sent to you.