Rice University
COMP 422
Parallel Computing
Spring 2008
Programming Assignment 1
Complete by 5pm on Friday, Feb 8, 2008


Parallel Constraint-Satisfaction Search and its Application to Graph Coloring

Constraint-satisfaction problems arise frequently in engineering design applications. These problems are computationally intensive and well suited for speedup through parallel processing. This assignment explores parallelization of constraint-satisfaction search algorithms that use forward checking. It is well known that some form of look-ahead, as in forward checking, reduces the sequential execution time for the application thereby making it a more credible candidate for parallelization than simple backtracking. This assignment will use graph coloring as the application to test your constraint-satisfaction search program. The problem of coloring a graph has found a number of applications such as register allocation in compilers, scheduling, frequency assignment in mobile radios, and pattern matching.

Submitting your Assignment

Your assignment should be submitted in three parts.
  1. A single source file containing your Cilk program.

  2. Input file(s) used for the run(s) described in the report.

  3. Your writeup about the program.
Send an email to both myself and the TA with all three parts as attachments. Parts 1 and 2 should be sent as text files, where as Part 3 containing your writeup can be in text, Word, or PDF formats. The hard deadline is 5pm on February 8, 2008.

Grading Criteria

  1. 20% Program correctness.
  2. 20% Program scalability and performance.
  3. 30% Program clarity, elegance and parallelization. The program should be well-documented internally with comments.
  4. 30% Writeup. Your grade on the writeup includes the quality of the writing (grammar, sentence structure), whether all of the required elements are included, and the clarity of your explanations,
NOTE: we will run your program on additional inputs to test 1. and 2.

Extra Credit

You have the option of attempting any or all of the following for extra credit (up to an additional 10% for each) on this assignment: