Milestone 1 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 implementing datastructures for implicants and tables of implicants, and used them to write Quine-McCluskey for a uniprocessor. More details about the design of the datastructures in particular will appear in the writeup scheduled to be done on Saturday. Our collected timing results so far are:

CPU time for n-term tables with all 2^n elements

n computation total
1        0.00  0.00
2        0.00  0.00
3        0.00  0.00
4        0.01  0.01
5        0.06  0.06
6        0.36  0.36
7        2.70  2.71
8       23.39 23.41

CPU time for n-term tables with 2^(n-1) randomly-selected elements

n computation  total 
1        0.00   0.01
2        0.00   0.01
3        0.00   0.00
4        0.00   0.01
5        0.01   0.02
6        0.03   0.03
7        0.05   0.07
8        0.20   0.23
9        1.00   1.05
10       5.02   5.15
11      26.02  26.52
12     131.05 133.03

Analysis of these results will follow in the uniprocessor writeup.

Meeting the milestone

We met the milestone, which was to finish uniprocessor Quine-McCluskey code and do some performance testing.

Surprises

There haven't been any major surprises yet. We may want to make some changes to the table datastructure, since some operations on it are very inefficient. For example, we sometimes need to add to the table, but avoid duplicate implicants; currently that takes linear time in the number of implicants already in the table.

Revised schedule

Sun Mon Tue Wed Thu Fri Sat

Mar 29* 30*
Uniprocessor writeup (mid)

Mar-Apr 31* 1* 2*
Parallel data structures (mid?/shuma?) 3* 4*
Locking code (shuma?) 5* 6*

7* 8 9
Static code (mid/shuma) 10
Static timing (mid) 11
Milestone #2
Static writeup (mid/shuma) 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)

*=mid out of town

	Sun	Mon	Tue	Wed	Thu	Fri	Sat
Mar						29*	30* Uniprocessor writeup (mid)
Mar-Apr	31*	1*	2* Parallel data structures (mid?/shuma?)	3*	4* Locking code (shuma?)	5*	6*
	7*	8	9 Static code (mid/shuma)	10 Static timing (mid)	11 Milestone #2 Static writeup (mid/shuma)	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)

Resources needed

We generate our own data sets (sets of implicants) through a script, so we don't need data sets from outside sources. We may use espresso to do some checking of implicant tables too large to check by hand. The only other issue is to start using more different types of machines, and make sure our software will work on all the machines we decide to use.