Browse Prior Art Database

Effective Run Allocation Algorithm for Concurrent External Mergesorts

IP.com Disclosure Number: IPCOM000105607D
Original Publication Date: 1993-Aug-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 47K

Publishing Venue

IBM

Related People

Teng, JZ: AUTHOR [+3]

Abstract

Disclosed is an effective run allocation algorithm that also takes into account the marginal return of allocating runs to an incoming merge to reduce the mean response time for concurrent mergesorts, where a merge has multiple sorted runs residing on disks.

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

Effective Run Allocation Algorithm for Concurrent External Mergesorts

      Disclosed is an effective run allocation algorithm that also
takes into account the marginal return of allocating runs to an
incoming merge to reduce the mean response time for concurrent
mergesorts, where a merge has multiple sorted runs residing on disks.

      Traditional approaches to dynamic run allocation for concurrent
merges determine the maximum number of runs and the corresponding
prefetch quantity based only on the current buffer availability (i.e,
the number of runs currently committed).  The marginal return of
allocating runs is not considered.  However, a substantial
performance improvement can be achieved if the marginal return is
also taken into account in the run allocation.  For example, if the
total number of runs requested is 60, allocating 50 or 51 may make
little difference, since more than one merge step is needed in both
cases.  However, increasing the number of runs from 59 to 60 can make
a tremendous difference, because the merge can be completed in a
single step, instead of 2, if 60 runs are allocated.

      Proposed is an improved run allocation algorithm which takes
into account both buffer availability and marginal gain.  Let
    (M + k - 1)/k be the high return points for a merge, where M is
the total number of runs requested, k = 1, 2, ...  M-1 is the number
of steps to complete the merge if
    (M + k - 1)/k     runs are allocated.  It...