CISC 372: INTRODUCTION TO PARALLEL PROGRAMMING
Spring 2000
Individual Programming Assignment 3
Due Date: start of class, Tuesday, April 25, 2000

Objectives

The objective of this assignment is to write an MPI program that attempts to achieve load balancing for a problem for which a static data distribution is not appropriate.

Project Description

Your project consists of implementing and executing a parallel MPI spelling checker that seeks to achieve load balancing through dynamic data(work) distribution. That is, there is no fixed static data distribution scheme, but tasks are distributed at runtime as a worker completes a task and needs more work to do.

Basic Spelling Checker Operation:
The spelling checker that you are to implement will also be very simple. Your spelling checker will ask the user for a word to check, read in a dictionary of words from a dictionary file, and then dispatch searching tasks to the processors. The program should report if the word is spelled correctly. If the word is incorrect, then words in the dictionary that are within one mismatch of the word or within one gap of the word should be reported.

For example:

	
	TOOO = word to check 
	TOOL = word within one match 
	TOO = word within one gap
	AOOO = word within one match

A serial version of the spelling checker is located on porsche in  pollock/public/seqdict.c. A dictionary file of over 25K words is there also, called dictionary. Look at the sequential code, and compile and execute it to see how it works.

A Parallel Version:
For your parallel version:

• Give the query word to all worker processes. Note: You are only searching for a single word at a time, not trying to parallelize searches for different queries at the same time.

• Research parallel searching methods or develop one on your own to use the multiple processes to speed up the search for this word in the dictionary. This parallel algorithm part is left to you to think!

• Print out a single message (not one from each process) indicating that the word was in the dictionary, or up to 10 close words if the word was not found in the dictionary. For simplicity, if the word does not match, you only need to keep track of no more than 10 close words.

Experiments and Experimental Report

You should perform several experiments with your code. Be sure not to include the input and output as part of your timings. Be sure to take several timings for the same data point, but you only need to present the average of them after you are convinced you have a stable number for that data point, in your graphs below.

1.

Time your code for 1, 2, 4, and 8 processes for a fixed task size given to each process. Plot a graph that shows how the timings change as number of processes changes.

2.

Time your code for 8 processes for several different task sizes. Plot a graph that shows how the timings change as the task size changes. Make sure you include some extreme cases like task size of 1 and some very high number.

Your experimental report should consist of the following sections in this order. It is strongly recommended that you type your report using a word processor rather than handing in a hand-written report.

1.

Cover Page: Title, author, course number and semester, date.

2.

Project Summary: In one paragraph, summarize the activities of the lab, and in particular, describe the algorithm that you implemented for the parallel version.

3.

Collected Timing Data. In this section, you present your experimental data, in a clear graphical form. You do not have to show charts of your raw numbers, but we should be able to tell what your averages of the raw numbers were reading the graphs.

You should have a graph for each experimental comparison study performed, thus, 2 graphs.

4.

Analysis. In English, describe what your timing results show, and try to explain why they are that way. Discuss what you believe to be a reasonable task size for your parallel dictionary search program, based on your results.

5.

Appendix. A script that includes your parallel program, compilation, and a run of your program on more than 1 processor.

SPECIAL NOTE: This assignment requires a dictionary file of considerable length. For this, create a link to  pollock/public/dictionary by ln -s  pollock/public/dictionary dictionary. This dictionary has over 20,000 words, one per line. In order to avoid excess network traffic (and getting me in trouble by slowing down the system!), be sure to have only the master process reading from the dictionary. Do not have the workers all reading from the dictionary file.

ALSO A NOTE ON INDIVIDUAL VERSUS GROUP ASSIGNMENTS: This is an individual assignment, not a group assignment. You should not be collaborating with other students. You may talk to each other to clarify the specification of the assignment, but your solution should be your own.

About this document ...

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 lab3.tex.

The translation was initiated by Lori Pollock on 2000-04-12