Objectives

• to give you experience writing MIPS assembly code
• to give you experience with data and control structures in MIPS

Admin

Marks

9 (towards total course mark)

Group?

This assignment is completed individually

Submit

give cs1521 assign1 prog.s or via Webcms3

Deadline

Wed 17 Jul 2019, 08:59:59

Late Penalty

0.08 marks per hour late (approx 1.9 marks per day) off the ceiling
(e.g. if you are 36 hours late, your maximum possible mark is 6.1/9)

Assessment

• 7 marks for auto-testing on a range of boards and board sizes
• 1 mark for commenting the code; you don’t need a comment on every line, but roughly one comment on each block of MIPS instructions that corresponds to a C statement
• 1 mark for readable code: sensible names, lining up opcodes and operands, …

For a guide to style, use the code in the lectures and tute solutions.

If your assembly code has syntax errors (according to spim) or run-time errors on all test cases, your auto-testing mark is limited to 2/7, depending on an assessment by your tutor.

Background

Conway’s Game of Life is a mathematical zero-player game whose history and rules are described well onWikipedia. It takes place on an infinite grid of cells, where each cell is either alive or dead. Each cell has eight neighbours: left, right, above, below, and diagonal. On each turn, the whole grid is examined, and the content of each cell is changed according to the following rules:

• Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
• Any live cell with two or three live neighbours lives on to the next generation.
• Any live cell with more than three live neighbours dies, as if by overpopulation.
• Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

In this assignment, you will implement a version of the Game of Life in MIPS assembly. It is different from the standard version in having a finite board. This means that some cells (on the edges) will have fewer than eight neighbours. The size of the board is determined by the data definitions included at the start of the program.

Setting Up

Create a new directory for working on the assignment, change into that directory, and then run the command:

unzip /web/cs1521/19T2/assignments/assign1/assign.zip

This will add the following files into the directory:

life.c

a working version of the Game of Life in C

board1.h

a 10×10 board state, for inclusion in life.c

board2.h

a 15×15 board state, for inclusion in life.c

prog.s

a template for the Game of Life program in MIPS

board1.s

an initial 10×10 board state and board size

board2.s

an initial 15×15 board state and board size

The C code in life.c is a working version of the Game of Life. It includes an initial state of the grid, reads a number maxiter for how many iterations to run, and then uses the rules to change the state maxitertimes, displaying the state after each iteration. It is not written in a style we would normally use, but is intended to be a little closer to how you would render it in MIPS.

1. #include <stdio.h>
2. #include <stdlib.h>
4. #include “board2.h”
6. int neighbours (int i, int j);
7. char decideCell (int old, int nn);
8. void copyBackAndShow (void);
10. int main (void)
11. {
12. int maxiters;
13. printf (“# Iterations: “);
14. scanf (“%d”, &maxiters);
16. for (int n = 1; n <= maxiters; n++) {
17. for (int i = 0; i < N; i++) {
18. for (int j = 0; j < N; j++) {
19. int nn = neighbours (i, j);
20. newboard[i][j] = decideCell (board[i][j], nn);
21. }
22. }
23. printf (“=== After iteration %d ===\n”, n);
24. copyBackAndShow ();
25. }
27. return 0;
28. }
30. char decideCell (int old, int nn)
31. {
32. char ret;
33. if (old == 1) {
34. if (nn < 2)
35. ret = 0;
36. else if (nn == 2 || nn == 3)
37. ret = 1;
38. else
39. ret = 0;
40. } else if (nn == 3) {
41. ret = 1;
42. } else {
43. ret = 0;
44. }
45. return ret;
46. }
48. int neighbours (int i, int j)
49. {
50. int nn = 0;
51. for (int x = -1; x <= 1; x++) {
52. for (int y = -1; y <= 1; y++) {
53. if (i + x < 0 || i + x > N – 1) continue;
54. if (j + y < 0 || j + y > N – 1) continue;
55. if (x == 0 && y == 0) continue;
56. if (board[i + x][j + y] == 1) nn++;
57. }
58. }
59. return nn;
60. }
62. void copyBackAndShow (void)
63. {
64. for (int i = 0; i < N; i++) {
65. for (int j = 0; j < N; j++) {
66. board[i][j] = newboard[i][j];
67. if (board[i][j] == 0)
68. putchar (‘.’);
69. else
70. putchar (‘#’);
71. }
72. putchar (‘\n’);
73. }
74. }

Note that the game board does not appear directly in the C code file. Instead it is #include‘d, to make it easier (slightly) to include a different initial state in the program. The board1.h file simply contains:

1. // Game of Life on a 10×10 grid
3. #define NN 10
5. int N = NN;
7. char board[NN][NN] = {
8. {1,0,0,0,0,0,0,0,0,0},
9. {1,1,0,0,0,0,0,0,0,0},
10. {0,0,0,1,0,0,0,0,0,0},
11. {0,0,1,0,1,0,0,0,0,0},
12. {0,0,0,0,1,0,0,0,0,0},
13. {0,0,0,0,1,1,1,0,0,0},
14. {0,0,0,1,0,0,1,0,0,0},
15. {0,0,1,0,0,0,0,0,0,0},
16. {0,0,1,0,0,0,0,0,0,0},
17. {0,0,1,0,0,0,0,0,0,0},
18. };
19. char newboard[NN][NN];

Note that the board1.h file contains a global variable which holds the board size. This is used by the C code, rather than referencing the #define‘d value, to make it more like what the assembly code does.

The intention of #include‘ing the initial board state is that people can write their own starting board states and share them with others without having to reveal their program code. Of course, you’ve already got the C program code, but this setup is aimed at the MIPS data/code files.

For example, the board1.s file looks like:

1. # board1.s … Game of Life on a 10×10 grid
3. .data
5. N: .word 10 # gives board dimensions
7. board:
8. .byte 1, 0, 0, 0, 0, 0, 0, 0, 0, 0
9. .byte 1, 1, 0, 0, 0, 0, 0, 0, 0, 0
10. .byte 0, 0, 0, 1, 0, 0, 0, 0, 0, 0
11. .byte 0, 0, 1, 0, 1, 0, 0, 0, 0, 0
12. .byte 0, 0, 0, 0, 1, 0, 0, 0, 0, 0
13. .byte 0, 0, 0, 0, 1, 1, 1, 0, 0, 0
14. .byte 0, 0, 0, 1, 0, 0, 1, 0, 0, 0
15. .byte 0, 0, 1, 0, 0, 0, 0, 0, 0, 0
16. .byte 0, 0, 1, 0, 0, 0, 0, 0, 0, 0
17. .byte 0, 0, 1, 0, 0, 0, 0, 0, 0, 0
19. newBoard: .space 100

Note that the definitions are intended to be analogous to the definitions in board.h. One difference is that MIPS assembly (as understood by SPIM) does not have an equivalent to C’s #define, and so the board size is repeated as a constant several times within the data definitions.

Exercise

The aim of this exercise is to complete the supplied program skeleton:

1. # COMP1521 19t2 … Game of Life on a NxN grid
2. #
3. # Written by <<YOU>>, June 2019
5. ## Requires (from `boardX.s’):
6. # – N (word): board dimensions
7. # – board (byte[][]): initial board state
8. # – newBoard (byte[][]): next board state
10. ## Provides:
11. .globl main
12. .globl decideCell
13. .globl neighbours
14. .globl copyBackAndShow
17. ########################################################################
18. # .TEXT <main>
19. .text
20. main:
22. # Frame: …
23. # Uses: …
24. # Clobbers: …
26. # Locals: …
28. # Structure:
29. # main
30. # -> [prologue]
31. # -> …
32. # -> [epilogue]
34. # Code:
36. # Your main program code goes here. Good luck!
38. main__post:
39. jr $ra
41. # Put your other functions here

You must implement the four functions given in the C code: main(), decideCell(), neighbours(), andcopyBackAndShow().

For testing, you will need to load both a board definition and your program code into the SPIM emulator to get a complete executable program. This is easy in qtspim, where you can load multiple files into memory before executing them. The spim command only accepts one code file, so you need to merge a boardX.sfile and your prog.s file to create a complete program. A simple way to do this is to run two commands:

cat board1.s prog.s > life.s
1521 spim -file life.s
# Iterations: 3
=== After iteration 1 ===
##........
##........
.###......
....#.....
....#.....
...##.#...
...##.#...
..##......
.###......
..........
=== After iteration 2 ===
##........
..........
####......
..#.#.....
....#.....
..........
..........
.#........
.#.#......
..#.......
=== After iteration 3 ===
..........
..........
.###......
..#.#.....
...#......
..........
..........
..#.......
.#........
..#.......

In order to conduct testing, you could compile the life.c program, run it to collect the expected output, then run the MIPS version to collect the observed output, and compare them, e.g.

gcc life.c
echo 3 | ./a.out > c.out
echo 3 | 1521 spim -file life.s | sed 1d > mips.out
diff c.out mips.out
... we expect no output here ...

If the output from diff(1) is empty, then the MIPS program is behaving as expected. Note that SPIM prints out a message on startup indicating where its exception handlers are located; you may need to ignore this line in the diff(1), or filter it out (e.g., using sed(1) to remove the first line, as shown above).

You should try this for at least the two supplied boards. Remember that you will need to edit life.c to change what’s #include‘d, then re-compile, then build a new life.s by merging prog.s with the corresponding boardX.s and repeating the above testing.

It would be great if people created new, more interesting, initial board state files, and made them available for others to use in their testing.

Things you should not do:

• use a cross-compiler to convert the above C code to MIPS assembler
• copy a solution from an online source (e.g., Github)

The whole point of this exercise is for you to better understand how assembly programs are built and how they work. The above two strategies ruin the point of this assignment, and are very obvious when we examine your work.

Extensions

(Worth kudos, but no marks)

• create some larger and more interesting initial board states
• detect the board entering a steady state or a short cycle
• handle non-square (i.e., rectangular) boards
• run the game continuously and use additional characters to provide animation
• develop and implement a faster or more compact algorithm for calculating the state of a cell for the next generation