Copyright © 2002 Katrin Becker 1998-2002 Last Modified October 2, 2000 02:31 PM

Programming Assignment:

Cosequential Processing

(to be done individually) 

Design and write a program to calculate & analyse seek times for a merge of K runs using both Fibonacci and Cascade Merge approaches.
Input to the program will be:
N : the order of the merge (# of devices = N+1 - no default)
F : the size of the file in Megabytes (default = 1 Gigabyte)
M: the size of available memory (RAM) (default = 10 Megabytes)
R: the size of a record in bytes (default = 1000 bytes)
K: the # of runs (no default)
Output:
Include intermediate calculations at the end of each phase of the merge and print both the number of seeks and the relative file sizes (either in: 1000's of bytes, relative to one original run, or number of records)
Example of hand calculations:
Phase 1: 4 sets of 3 runs:
: 1/3 of RAM for each = 333,333 Bytes = 333 Records
: 1/3 of each run = 3 seeks/run * 3 runs = 9 seeks
: 4 sets to do = 9 * 4 = 36 seeks [36 SEEKS]
 
Phase 2: 2 sets of 3 runs (1 run in each set has 3,000 records in it)
: 1/3 RAM = 333 records
: 3 seeks/run * 3 runs = 9 seeks, but last file has 2,000 records left,
so 6 more seeks for it = 15 seeks per set
: 2 sets = 2 * 15 = 30 seeks [30 SEEKS]
 
Phase 3: 1 set of 3 runs (1 has 1000 rec., 1 has 3000 rec., 1 has 5000 rec.)
: 3 seeks/run * 3 runs = 9 seeks, but 2 runs have at least 2000 records
left, so 6 more seeks for each; 6 * 2 = 12 MORE seeks, but
the last run still has 2000 records left so 6 MORE for it
: 9 seeks + 12 seeks + 6 seeks = 27 seeks [27 SEEKS]
 
Phase 4: 1 set of 3 runs (lengths 9000, 5000, 3000 records)
: smallest size is 3000 rec. so 1/3 RAM = 9 seeks/run so
9 seeks/run * 3 runs = 27 seeks
: now 2 runs still have at least 2000 records left so
6 seeks for each * 2 of them = 12 seeks
: now last run has 4000 records left so 3*4 = 12 seeks
: 27 seeks + 12 seeks + 12 seeks = 51 seeks [51 SEEKS]
 
36 + 30 + 27 + 51 = 144 SEEKS TOTAL
see the sample calculations for more
The following information should be included in your output:
Phase #, number of sets of runs and their sizes
- total number of seeks per run (remember that larger runs in the same set will have more seeks)
Data:
Test your program on at least the following:
N
F (file size)
Mem.
Rec.
K
3
3100
100
10
31
3
3000
100
10
30
3
3200
100
10
32
3
100 [100 MB]
1 MB
1,000 b
50 runs
4
1,000 [1 GB]
10MB
1,000 b
50 runs
5
5,000 [5 GB]
5MB
1,000 b
500 runs
6
5,000 [5 GB]
10MB
1,000 b
500 runs
6
1,000,000 [1 TB]
10MB
1,000 b
1,000 runs
Hints:
Work on doing the calculations for inputs N & K, then work on how to allow F, M, R to vary.
Calculate seeks non-concurrently
Bonus:
[ 3 points ] calculate seeks when devices operate concurrently.
[ 1 point ] calculate actual speed of merge (in HOURS, MINUTES, SECONDS ) assuming a seek time of 5 ms
Copyright © 2002 Katrin Becker 1998-2002 Last Modified October 2, 2000 02:31 PM