Milestone 2 Report

Margaret DeLap, James Shuma

CS 495

Major changes

There have been no major changes in the goals or the implementation of the project.

Accomplishments

We finished an initial implementation of a parallel version of Quine-McCluskey. Loosely defined, it uses static scheduling: i.e., for a set of implicants with n terms each, exactly n processes are created. This is unfortunate for performance, as it has nothing to do with the number of processors available. It is one thing we expect to change in the next, "dynamic" version. Although we call this version "static," it has some aspects that look suspiciously like dynamic scheduling. This is not really the case, though. Each process has its own queue, so there is one (non-shared) queue for each column in the QM table. Since no process takes work from another's queue, these queues really resemble an instance of message-passing more than they do one of dynamic scheduling.

Meeting the milestone

The queues on the NCSA Origins have been very slow, so we may not have all of the quantitative timing results we expected to have. In any case, we do have some descriptive results that can be used in the writeup for now.

Surprises

It was no surprise that this implementation does not perform well. Work travels from left to right in the QM table, and with static scheduling there is no opportunity for the "leftmost" processes, once it has no work left to do, to do work that exists on the right. Similarly, at the beginning the "rightmost" processes have nothing to do. This is likely an even bigger problem than the fact that the number of processes is unrelated to the number of processors available. We did find some situations that show that doing some extra computation to avoid communication speeds things up. Namely, avoiding adding redundant queue members allows processes to finish earlier and avoid requesting work that turns out to be redundant.

Revised schedule

Sun Mon Tue Wed Thu Fri Sat

Apr 12 13

14 15
Dynamic code (mid/shuma) 16
Dynamic timing (mid) 17
Dynamic writeup (mid/shuma) 18 19 20

21 22 23 24 25
Final code (mid/shuma) 26
Final timing 27
Final documentation

Apr-May 28 29 30
Final writeup 1 2
Poster session

	Sun	Mon	Tue	Wed	Thu	Fri	Sat
Apr						12	13
	14	15 Dynamic code (mid/shuma)	16 Dynamic timing (mid)	17 Dynamic writeup (mid/shuma)	18	19	20
	21	22	23	24	25 Final code (mid/shuma)	26 Final timing	27 Final documentation
Apr-May	28	29	30 Final writeup	1	2 Poster session

Resources needed

We do not expect to need resources other than those previously mentioned.