For this project, you will write a tetris game server for that runs on a multicore MIPS simulator. The goal of the project is to achieve high performance by splitting the work into multiple contexts that can be executed concurrently, and to protect accesses to shared data structures through locking.
We have provided you with a modified multi-core simulator for this assignment. Unlike the previous multi-core simulator you built in the previous project, this simulator accurately approximates the timing behavior of a multi-core processor. It has 10 inherent contexts. If your program uses only one of those contexts, the simulator idles for 90% of the time, and simulates instructions for 10% of the time. Consequently, solutions that are highly concurrent will execute much faster than solutions that are single-threaded. Do keep this in mind as you design your solution.
The game is a cooperative, parallel tetris. Any number of clients can connect, and each sees the same thing: a big tetris board with N buttons at the top for the N players, with N concurrent pieces falling. Any client can select a player to control by clicking the button (or using keys 1 through 7), then use left/right/up to move and rotate that player's piece. One person could try to juggle N players using a single client window, or a group of people could cooperate to manage the N falling pieces, while trying not to step on each others toes.
The server listens on a specified UDP port. It is configured with the board dimensions, and N (the number of players, between 1 and 7). All of these parameters, with the exception of the UDP port, are #defined at compile time. The UDP port is passed to the simulator at runtime, and the server does not need to know what port it is.
The client, which we provide, sends simple 2 byte UDP messages to the server. The first packet sent is a subscribe message, consisting of {'N', 0}. (The 'N' stands for no-op). The server should add the client's udp address (obtained from the message) to its list of subscribers. All remaining packets consist of {cmd, player} pairs, where cmd is one of 'N' for no-op (does nothing), 'L' for move-left, 'R' for move-right, 'S' for spin (aka rotate clockwise), or 'D' for down. The player field is a number from 1 to N, which is the piece that should be moved. The server should move the specified piece, if possible (i.e., such it will not bump into other falling pieces, or other pieces that have already landed). It should then immediately send a state update back to that client.
The server also implements gravity -- every 1 second or so, it should move all falling pieces down, and if that isn't possible, it should declare the piece 'landed' and start a new piece falling.
Lastly, the server sends periodic updates to all subscribed clients, every 1 second. This is the only kind of message ever sent by the server. It consists of 4 leading bytes specifying W, H, N, and a sequence number (for debugging), followed by W*H bytes specifying the board cell values for pieces that have landed, followed by N 4-byte-tuples specifying the falling pieces and the next pieces for each player. The exact format can be found in Protocol.java, with all the constants defining the cell types (S shape, L shape, Z shape, etc.). The 4-byte-tuple has a byte for X and Y coords, 4 bits for the current piece type, 4 bits for the current piece orientation, 4 bits for the next piece type (a preview), and 4 bits for the next piece orientation.
The end-of-game rules are just like normal tetris: is a new piece can't be placed at the top of the screen, game-over. Or if a new piece lands without having fully come on to the screen yet, game-over. The server immediately exits, which leaves the clients frozen at the end-of-game state.
To enable some of the functionality required in your program, several new system calls have been added. int rand(void) returns a random integer between 1 and 2147483647. void gettimeofday(int *sec, int *usec) stores the time of day second counter and microsecond counter into the specified variables. int network_read(struct datagram* dg) and int network_write(struct datagram* dg) receive and send packets of the format:
#define PAYLOAD_SIZE 1500
// Network packet structure
struct datagram {
unsigned int addr; // Peer address
unsigned short int port; // Peer port
int size; // Amount of data in payload
char payload[PAYLOAD_SIZE]; // Data
};
See the examples for how to use randomness and network functionality.
In order model real hardware as closely as possible, there is no system call to make a context sleep for a specified amount of time. In order delay an action, you can use the gettimeofday() system call in a busy loop.
The instructions ll and sc have been added to support locking across multiple cores. You can utilize these by calling the int test_and_set(int* lock) function, which is defined in test-include.h This will return the current value of *lock and set it to 1 in a single, atomic action.
The simulator implements 10 cores. To simulate the parallelism of real hardware, each time step takes the same amount of time, regardless of how many cores are being used. This means executing 1000 instructions on one core will take 10 times as long as executing 100 instructions on each core.
To achieve high performance, you should utilize multiple cores. A simple strategy is to have a network input context, a command processing context, a gravity context, and a network output context. Even better, you could have a dedicated context for processing the commands of each player.
To protect the data structures of your program, you will need to use the test_and_set system call to do locking. Queues should be used to pass network input to the command processing contexts. The specifics of how many contexts to create and how to divide work between them is left up to you, so feel free to do something different than the idea outlined here. We will be looking for evidence that you are using multiple contexts and are performing locking to protect shared data structures.
You can try out our example server for 4 players:
java -jar cs316-tetris-server/lib/tetris.jar 5000 4. The 5000 is the UDP port, and may be anything between 1024 and 65535. If you're using a shared machine, you should pick your own number to avoid conflicting with another student.
Then, start a client:
java -jar cs316-tetris/lib/tetris.jar localhost 5000 (add -v or -vv for verbose).
Download the Java client referenced above. You may also wish to download the example Java server to try it out. Download the randomness/network example from above and use it as a starting point for your MIPS program. This will provided you with the necessary test-include.h. You may run the simulator on the CSUGLAB Linux machines by typing /usr/local/cs316/p8/simulate -p N, where N is a number between 1024 and 65535 to use as the UDP port.
Unfortunately, CSUGLAB has a rather draconian firewall. If you are using their machines as opposed to your own Linux system for the tetris server, you'll need to run the tetris client on their machines as well. You can do this via remote X11 or VNC.
UPDATE: TCP support has been added. This means you can forward a TCP port over ssh and run the client on your local machine. The latest client will use TCP automatically if it cannot connect via UDP.
Put all of your code in a file named tetris.c and submit it via CMS.
Ask the TAs for help. We expect to see most students in office hours during the course of the project. Extra hours will be scheduled as needed.
If you suspect a bug in the provided simulator... ask Michael for help.