Computer Science 400
Parallel Processing

Siena College
Fall 2008

Lab 3: Multithreaded Palindromic Word Finder
Due: 5:00 PM, Thursday, September 25, 2008

Your task this week is to parallelize your working sequential implementation of the palindromic word finder from Lab 2, using the bag-of-tasks paradigm, implemented using the pthreads library. Your parallel program should use W worker threads, where W is a command-line argument. Use the workers just for the compute phase; do the input and output phases sequentially. Each worker should count the number of palindromic words that it finds. Sum these W values during the output phase. This avoids a critical section during the compute phase - you'll need to deal with others, though. Use 26 tasks in your program, one for each letter of the alphabet. In particular, the first task is to examine all words that begin with "a" (and numbers), the second task is to examine all words that begin with "b", and so on. During the input phase you should build an efficient representation for the bag of tasks; I suggest using an array, where the value in task[0] is the index of the first "a" word, task[1] is the index of the first "b" word, and so on. You can also use this array during the search phase to limit the scope of your linear searches. Your parallel program should also time the compute phase. You may use the timer.c and timer.h code from our class examples. Start the clock just before you create the workers; read it again as soon as they have finished.

Your program should have the following output:

For the timing tests, execute your parallel program on the four-processor Solaris nodes (wetteland or rivera) using using 1, 2, 3, and 4 workers. Run each test 3 times. In the file lab3.txt, include a table of results; it should contain all the values written to standard output for all 12 test runs, and a brief analysis of the speedup and parallel efficiency you have achieved.

When you are finished, submit using the turnin utility on the cluster as lab3. Please include your Makefile, your C source code (including the timer code from class, if you choose to use it), a brief README file expaining how to run your program, and the lab3.txt file that includes your timings and analysis. Please do not include object files or your executable.

Academic honesty guidelines: While the program is to be done

individually, I want to encourage you to ask questions and discuss the program with me, and with each other, as you develop it. However, no direct sharing of code is permitted. If you have any doubts, please check first and avoid problems later.

Grading guidelines: Your grade for the program will be

determined by correctness, design, documentation, and style, as well as the presentation of your timing results.