Computer Science 400 Parallel Processing Siena College Fall 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:

• total number of palindromic words (to stdout)
• the number found by each worker (to stdout)
• the elapsed time for the compute phase (to stdout)

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.

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.

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