|
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.
-
Write a shared-memory parallel program in Cilk that solves a graph coloring problem provided in an input file. (Cilk is installed on Ada in /projects/comp422/pkgs/cilk. Also see slide 41 of Lecture 6.) Sample input files are provided in /project/comp422/assignment1/inputs, generated from the Rice Scalar Compiler Group. The number of colors to be used is specified as a command-line argument. The output is simply the number of feasible solutions found.
A sequential program for constraint-satisfaction search with forward checking is
included in /project/comp422/assignment1/ForwardChecker.c. You may use this program as you
see fit to get a jump start on your assignment. Feel free to use
the code directly as the basis for your parallel solution. In addition a paper on parallelizing constraint-satisfaction search problems published in ICPP 1988 can be found here.
-
Compile and run your program on each of 1 to 4 processors on an Ada node using an input data set of your choice, such that the sequential execution time is at least 10 seconds long and there is at least one feasible solution found. Make sure that all executions return the same value for number of solution found. Record the execution time for each of the runs using the Unix "time" command. Also measure the sequential execution time of the equivalent C program to be used as the baseline for reporting speedup.
-
Write a document that describes how your parallel program works. This document
should not include your program, though it may include pseudo-code that sketches key elements of the
parallelization strategy. Explain how your program exploits
parallelism. Explain why you chose to exploit parallelism in this
way. Were there any opportunities for parallelism that you chose not
to exploit? If so, why? Explain how the parallel work is synchronized.
Prepare a table that includes your timing measurements for executions on 1 to 4 processors, and include speedup relative to sequential execution time of the equivalent C program. Include the input values used for the executions (interference graph and number of colors).
Discuss your findings on the speedup and the quality of the
parallelization. You may optionally include timings from executions with additional data sets.
Note: the time of a sequential execution of your program is not
the same as the execution time of a Cilk program on 1 process. To
collect the sequential execution time of your program, copy it into a
file with a .c suffix, elide the Cilk keywords (#define to them to
white space), compile it with gcc
using the same optimization level as the program compiled by cilkc and
measure the wall clock time using the Unix "time" command.
Submitting your Assignment
Your assignment should be submitted in three parts.
-
A single source file containing your Cilk program.
- Input file(s) used for the run(s) described in the report.
- 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
-
20% Program correctness.
-
20% Program scalability and performance.
-
30% Program clarity, elegance and parallelization. The program should be
well-documented internally with comments.
-
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:
- Implement a more efficient (but functionally equivalent) sequential program as a baseline. For example, without loss of generality, you can assign node 1 in the graph a fixed color, and then multiply the number of solutions that you obtain for the remaining nodes by K, where K is the number of colors.
- Solve the extended problem of determining the minimum number of colors needed to color the given graph, by (say) a binary search for different values of K between 1 and N (where N is the number of nodes/vertices in the graph).
- Try the sample graph coloring problems available from Princeton with the added twist of identifying the maximum number of move pairs that can be eliminated over all legal colorings, as discussed in slide 3 of Lecture 7.
- Use your implementation of parallel constraint-satisfaction search to solve the N-queens problem, and compare the resulting sequential and parallel performance with the N-queens example program provided in the Cilk release.