Browse Prior Art Database

Method of Merging with a Coprocessor

IP.com Disclosure Number: IPCOM000105353D
Original Publication Date: 1993-Jul-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 2 page(s) / 72K

Publishing Venue

IBM

Related People

Bennett, BT: AUTHOR [+2]

Abstract

Disclosed is a method for managing the movement of data in the merge phase of an external disk sort in a system with a sort coprocessor. The method minimizes the number of disk I/Os.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Method of Merging with a Coprocessor

      Disclosed is a method for managing the movement of data in the
merge phase of an external disk sort in a system with a sort
coprocessor.  The method minimizes the number of disk I/Os.

      A known approach for external sorting in a conventional
computer system is as follows.  In the first phase of the sort,
sorted runs of data are created and written on disk in blocks.  The
location of each block and lowest key in the block are recorded for
each block.  The sequence of blocks ordered by lowest key is divided
into sets of blocks consecutive in this sequence and in the next
(merge) phase the blocks in these sets are read in together in an
order optimized for disk access.  After each set is read in, records
with keys not greater than the lowest key remaining in the workfile
are merged and placed in the output buffer.  Records can be merged
until all the blocks from the run with the next lowest key are
emptied and there is at most one non-empty block for each other run.
For a merge of M sorted runs with sets of size Ni, an input buffer of
Ni+M-1 blocks is required.  If the output buffer can hold all the
records in the input buffer and has an additional block to accomodate
a partially full block from the previous merge step then all full
blocks in the output buffer can be written out to the output file
concurrently with the reading in of the next set of input blocks.
Increasing Ni so that the output buffer is no longer large enough
will decrease the number of input I/Os but will also require that
sometimes the output buffer must be written out without overlap with
the input and more than one output I/O may be required per input I/O.
Thus the optimal Ni involves some tradeoffs.

      This method is extended so as to apply to a computer system
wherein the sorting and merging of records is done by a coprocessor
with separate storage.  It is assumed that the I/O subsyste...