Sp07 CS61C Performance Competition: Conway's Game of Life

TA: David Eitan Poll (cs61c-tb@imail.eecs.berkeley.edu)

 

Ah, Life.  Mikey likes it.  You can spin for a number to move around the board, getting a job, having children, and paying off student loans.  You can even model it in a computer program!  I think we'll stick with the latter, but in all its forms, Life is good.  I know, I know…  Now that you've read that, you're going to tell me that I need to “get a life!”  Well, that's your job J.

--David Eitan Poll, Spring 07 CS61c TA

 

A “glider” as visualized by GOL in this project.

Updates

  • 05-07 -- Oracles for the performance competition are now available for Solaris/Sparc and Solaris/x86. Type "GOLNormal" or "GOLUnbounded" to run them.

    Because these oracles were posted late, we have extended the deadline of submission to be Thursday, May 10 at NOON.

  • 04-24 -- mips-gcc does not support C99 standard. If you are getting weird compile errors in mips-gcc but not gcc, then it is probably the case that you are violating ANSI/C89 standard presented in K&R. One of the main differences between C89 and C99 is declaration of variables. In C89, all variables need to be declared at the beginning of a function before they can be used. In other words, you can't introduce a new variable in the middle of a function.

Introduction

Ok, so here we are, more than half-way through the semester.  You've all learned a lot about how your programs are turned from text into machine code, and you may have begun to figure out some tricks that will help you optimize your code!  Well, now you have an opportunity to put that new knowledge to work!

 

Hence, the contest.  Now's your chance to show just how l337 you are!  Pit your skills against your fellow students as well as the TAs.  This is also an opportunity to score some major effort/participation points!  Bring it on!

Contest

So, here's the plan: What follows will be a number of categories for which you may submit code.  The code you submit will start off in C. Using the mips-gcc tool to compile with any flags mips-gcc accepts,  you're encouraged to tweak the assembly it produces for optimization. In short, you can not only optimize your code for C, but also for MIPS assembly too!

 

We will be running (and you will have access to, for testing) your code on a Sony Playstation 2 running Linux.  The beauty here is that the PS2 uses a real MIPS processor and will be able to run your code natively!

Getting to know the Emotion Engine

The Emotion Engine, the CPU of the PS2, runs a slightly different version of MIPS instruction set you are accustomed to in class. Thus, there are a series of PDF documents available that describe the processor in more detail. To truly optimize for a processor, you have to know the processor. Thus, it is in your best interest to gloss through the documentation available.

The Categories

Unless stated to be otherwise, all usage is exactly as in HW2.  Take note of the change to the output format and means.

I. Traditional

Here, you will optimize your code for the spec from the original HW2.  The only difference will be the output of your program.  Instead of producing a series of files for each generation, you will be expected to produce output of the form:


  <Generation #>

  <Rows> <Cols>

  0 1 0 1 ...

  1 0 0 1 ...

  ...

 

As in HW2, each line should end in a newline.  However, you will no longer be writing this data to a file.  Instead, you will print the final generation to the standard output (console).  The reason we're eliminating all of the file i/o is because of the speed of such operations.

 

Submissions will be scored by the CPU time necessary to complete the operations for a variety of boards that meet the restrictions given in the original assignment.

II. Unbounded

The final category is from the "Extra for Experts" section of the assignment.  This category removes the edges of the boards, allowing the board to be extended in every direction as far as necessary.  The board printed should align what is printed by the most negative/positive rows and columns of the living cells.  In other words, if my min row is -10, my max row is 10, my min column is -20, and my max column is 20, my output should look something like this:


  142

  21 41

  0 0 0 1 0...

  1 0 0 0 0...

  ...

 

Logically, it is impossible to have a first or final row/column of all 0's, as a cell must be alive in each of those places in order for the row or column to be printed.  Notice that the number of rows and columns is printed, rather than the min/max.  Input format is still the same, and we will specify how many generations to generate.  Submissions will be ranked by speed.

Handling Error Cases

Don't worry about it.  All input will be valid.  Segfaults are ok, but might negatively affect your score.  (When I say might, I mean will, and when I say will, I mean will significantly) J

Oracle

We will provide a non-MIPS (compiled Solaris code) version of oracles for the various categories... once we can get around to making them.

Example Boards

You have the original glider file that we gave you in HW2.

How to Compile

To compile your solution into MIPS, use the command:

 

  mips-gcc GOL.c -S

This will produce .s files that you can compile also with mips-gcc!

 

  mips-gcc GOL.s -o GOL

How to Run

Running your application is slightly more involved as you MUST be logged into nova to begin the process. 

First, while logged into nova using your account, use scp to copy files to the PS2.  You'll be able to login to the PS2 using your cs61c class account!  scp works just like cp, but over an ssh-like connection.  Here's what the command might look like:

  scp GOL cs61c-xx@192.168.128.192:~/GOL

 

You will be prompted for your password. If you are tired typing in the above scp command or can't remember how to setup the scp command, you can use scp-GOL to move your cross-compiled executable for you.

 

Now, you should ssh into the PS2 using the ssh-mips command. Remember, ssh-mips works, and only works, on nova.

 

Again, make sure you're logged in to nova before trying to ssh or scp into the PS2.

Things to Keep in Mind

DO NOT COMPILE (i.e. use GCC) ON THE PS2, as the PS2 is not made to be a server.  People will need to use the PS2 for testing their programs, so the less strain we put on the machine, the better.  Instead, use the cross-compiler (mips-gcc) on nova to compile, and then scp the compiled code over to the PS2.


However, we do understand the need to use gdb or other programs to make quick changes to certain files. Thus, try to refrain from using those programs for too long.


Finally, only use the PS2 for purposes related to the performance competition. Using the PS2 for personal use may warrant your disqualification from the tournament.

Submission

Submit your entry based on the categories you would like to enter. Use the following commands:

 

  submit contest-trad

  submit contest-unb

Submit all the files necessary to create and run your executable. The deadline for submission is Thursday, May 10 at 11:59:59am.

Beat the TAs

Some of the TAs will be submitting entries to the competition as well!  (I know I will!).  Can you beat them?  At the end of the competition, we will show you how you ranked compared to the TAs.  Could you really resist an opportunity to talk smack to your TA?

Acknowledgments

It's important to thank Michael Le for contributing his PS2 for use in this competition!  I would thank myself too, but... that's just rude. J