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