Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Vector Partitioning Apparatus

IP.com Disclosure Number: IPCOM000099701D
Original Publication Date: 1990-Feb-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 2 page(s) / 95K

Publishing Venue

IBM

Related People

Robinson, JT: AUTHOR

Abstract

Disclosed are apparatus and means for fast in-place partitioning of a vector of (key, data) entries in main storage based on comparison with a partitioning key so that after the partitioning operation is complete, all entries with a key less than or equal to the partitioning key are stored in an initial segment of the vector, and all entries in the remaining segment of the vector have keys greater than the partitioning key. Such a partitioning operation can be used for sorting following one of the known versions of the quicksort algorithm (*).

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

Vector Partitioning Apparatus

       Disclosed are apparatus and means for fast in-place
partitioning of a vector of (key, data) entries in main storage based
on comparison with a partitioning key so that after the partitioning
operation is complete, all entries with a key less than or equal to
the partitioning key are stored in an initial segment of the vector,
and all entries in the remaining segment of the vector have keys
greater than the partitioning key.  Such a partitioning operation can
be used for sorting following one of the known versions of the
quicksort algorithm (*).

      Referring to the figure, the partitioning operation is
initialized by loading the following registers:  (1) the left address
register, or LAR; (2) the right address register, or RAR; (3) the
partitioning key register, or PKR; and (4) the entry length register,
or ELR.  The PKR has two parts, a length part (PKRL) that specifies
the length of the keys within entries, and a key part (PKRK) that
contains the partitioning key.

      The component labelled GO compares LAR and RAR, and while LAR
is less than RAR, it generates a true output; otherwise, it generates
a false output.

      In the figure, the components labelled LQENTRY, LQADR, RQENTRY,
and RQADR each represent FIFO (first-in,-first-out) queues, all with
the same number of slots.  Write operations insert data at the end of
the queue, and read operations remove data from the front of the
queue.

      While the output of the GO component is true, the component
labelled LSCAN performs the following operations: (1) if the LQADR
queue is full wait for it to become non-full, then fetch ELR bytes
from the main storage address specified by LAR; (2) compare the first
PKRL bytes with PKRK; (3) if the result of the comparison is greater
than, write the ELR bytes to LQENTRY and write LAR to LQADR; (4)
increment LAR by ELR and repeat from (1).

      While the output of the GO component is true, the component
labelled RSCAN performs the following operations: (1) if the RQADR
queue is full, wait for it to become non...