Rice University
COMP 422/534
Parallel Computing
Spring 2020
Assignment 1
Now due: 5:00pm Monday 17 Feburary (postponed from Friday February 14 due to spring recess)
Please review the policies on misconduct and late work in the course syllabus before you begin the assignment.


Parallel Exploratory Search using Cilk Plus

Othello (also known as Reversi) is a strategy game played on an 8 x 8 gameboard. The rules to the game and a brief explanation of strategy issues are available on the Wikipedia page for Reversi. There is an online version of the game that you can play to familiarize yourself with the game.

You will use NOTS (nots.rice.edu) for your assignment. Additional instructions for using NOTS and Cilk Plus on NOTS are included later on this page.

Distribution and collection of assignments will be managed using GitHub Classroom. You can accept the assignment at the following URL https://classroom.github.com/a/LthkIvXs. When you accept the assignment, it will provide you with a clone of a GitHub repository that contains a copy of a sequential program that enables two human players to play Othello. A copy of that program can also be found here. You may use this program as you see fit to get a jump start on your assignment. You may include any or all of the provided code in your submitted program. Feel free to use the code directly as the basis for your parallel solution. Some of you may be uncomfortable with the board representation that used in the sample code which represents one color's disks in each of the 64 positions of the board using bits of a 64-bit integer. If so, you may choose to rewrite the code using a 64-element array of characters as the board representation. While this is less compact, it is equally acceptable. If you would find it more intuitive to develop your own solution from scratch rather than building upon the code provided, that is fine as well, but not necessary.

Write a shared-memory parallel program in Cilk Plus that enables the computer to play the game. Implement the computer player as a parallel function that plays Othello/Reversi by searching n moves ahead to select the "best board position" for its move. For example, searching 1 move ahead for Player 1 means selecting best legal move for Player 1 based only on comparing the board states that would result from any of the possible legal moves for Player 1. Searching 2 moves ahead for Player 1 means selecting the move that would result in the best board position after Player 1's move followed by Player 2's best move. This process of considering alternating moves generalizes naturally to consider lookaheads of n moves. Note that if one player cannot move, his opponent can move again if any legal moves remain; your search should account for this accordingly. You should use either the minimax or negamax algorithm to choose the best move. Note: Constructing a sophisticated board evaluator to compute the best strategic move is beyond the scope of the assignment. A simple board evaluator that computes the best move by maximizing the difference between the number of your disks and the number of the opponents disks on the board will suffice.

Unless you specifically design your program to be deterministic, the sequence of moves the computer player performs will be unpredictable. You are required to use a Cilk Plus reducer to enforce determinism in your program by using it to deterministically select a move from the set of one or more moves with the best score. The Intel Cilk++ SDK Programmer's Guide describes reducers and how to work with them. Examples in directory /projects/comp422/cilkplus-features-tutorial/reducers and the comments in the reducer include files in /opt/apps/software/Core/icc/2018.2.199-GCC-6.4.0/compilers_and_libraries_2018.2.199/linux/compiler/include/cilk on NOTS should be helpful in understanding how to use reducers or write a custom reducer. You can use a provided reducer or write a custom reducer. If you want to write a custom reducer, you can parameterize a cilk::reducer_max template.

Input specification

The sample input file given here specifies that the computer will play both sides of the game and that each player will search seven moves ahead to select where to place its disk.

Output specification

Given an input file as specified above for two computer players, the program should run to completion. When the program begins, it should print the initial game board configuration. After each move, the program should print the 'row,column' position of the move, specify which disks were flipped, indicate how many disks were flipped, and reprint the game board. At the end of the game, the program should print out the final game board, the total number of disks for each player, and announce the winner.

Experiments

Submitting your Assignment

Your assignment should be submitted in two parts. You will submit your assignment by commiting your source files, Makefile, and report to your GitHub Classroom repository. If you have trouble using GitHub and come up against the deadline for submitting your assignment, email the instructor a tar file containing your source code and your report.

COMP 422 Grading Criteria

COMP 534 Grading Criteria

Using NOTS

You can log into nots.rice.edu on campus using Log into NOTS using your Rice University netid password.

NOTS is not directly accessible from off-campus locations. You will need to attch to the Rice University network using VPN and then you will be able to ssh to NOTS.

Setting up Cilk Plus on NOTS

To load the suite of Cilk Plus tools, first set your module path

Next, load the module that contains paths to the Cilk Plus compiler and tools.

The Cilk Plus compiler is icpc.

Data Race Detection Tools

To check your program for data races, you will need to use cilkscreen. To check your program for data races with cilkscreen, simply launch your program with cilkscreen:

Using SLURM on NOTS

While you can develop your program on one of the login nodes on NOTS, you should run your experiments on one of the compute nodes using the SLURM job manager. You can obtain a private node to run your job on by requesting a node for an interactive session using

A copy of this command is included in the file interactive among the provided files in your GitHub Classroom repository.

I strongly recommend developing and testing your code (with small lookahead depth) on the login node to avoid the surprise of having your editor be killed as your interactive session on a compute node expires. See the documentation on Using NOTS under the tab "Submitting Jobs" for more information about using SLURM.

Your sample repository includes a SLURM batch script submit.sbatch that you can launch with SLURM's sbatch utility. The sample batch script runs the othello program with each of 1..16 cores. You can run edit the final few lines to run othello just once or run it multiple times in a sequence of experiments.

Using HPCToolkit

To use HPCToolkit with Cilk Plus, load the HPCToolkit module.

Information about how to use HPCToolkit can be found in its User's Manual. There is also a tutorial that you can watch on Youtube.
31 January 2020 - Initial revision.