Browse Prior Art Database

Write Read Chaining

IP.com Disclosure Number: IPCOM000077939D
Original Publication Date: 1972-Oct-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Melen, E: AUTHOR

Abstract

Seek and latency time for writing is eliminated, by always writing output blocks in the block preceding the next block read. In this fashion writing and reading can be command chained, and the same buffer can be utilized for both input and output. To accomplish this, disk space is organized in the following fashion:

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Write Read Chaining

Seek and latency time for writing is eliminated, by always writing output blocks in the block preceding the next block read. In this fashion writing and reading can be command chained, and the same buffer can be utilized for both input and output. To accomplish this, disk space is organized in the following fashion:

The blocks within a cylinder are allocated cyclically to P parts. For example, if there are 5 parts and 10 blocks/cylinder, blocks would be allocated like this: 1 2 3 4 5 1 2 3 4 5. There must be an equal number of blocks in each part within a cylinder. Thus in order not to waste any space, the number of blocks/cylinder should be a multiple of the number of parts.

During phase 1 of the sort, strings are distributed onto parts 1 through P-1. Every string must be contained within one part. During intermediate merge, the strings within one part are merged and longer strings are written on the preceding part (p coming before 1) starting with part 1, and continuing cyclically until there is one string/part. when the parts are merged by final merge phase onto user output.

In the example shown in the above table there are 5 parts, merge order is 4 and there are 40 strings distributed onto parts 1-4 like this: 16 16 4 4. The example was chosen to show that with proper distribution of strings onto parts, a form of final partial pass is achievable, in the sense that higher numbered parts can go through one merge pass less than lower numbered parts. However, if work area capacity is an issue, parts are usually full, and as they are equally large, they will contain equally many strings.

When work area capacity is no problem, a more efficient initial partial pass is achieved in the following fashion:

Only two parts are used, and merging is done back and forth between the two. When the number of strings is equal to M, final merge merges them onto output. During phase 1, the strings are written to both parts, by writing the same block twice command-chained. As the blocks are adjacent, duplications only costs the transport time, which is small if there are many blocks/track. After phase 1, the number of strings participating in an initial partial pass is known, and these are merged from part 2, the result replacing their copies in part 1. The number of strings in part 1 is now a power of M. which is merged by full passes.

As the technique is essentially a nondestructive update-in-place, chaining is necessary to keep track of strings. If forward chaining is used, it is necessary to know the disk address of the next block each time a block is written. As output address is determined b...