Browse Prior Art Database

Optimization Techniques for Recirculation Hardware Sorter

IP.com Disclosure Number: IPCOM000040051D
Original Publication Date: 1987-Sep-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 3 page(s) / 38K

Publishing Venue

IBM

Related People

Ashley, DJ: AUTHOR [+2]

Abstract

A previously described sorting method [*] accomplished sorting by recirculating an entire vector of operands through a hardware sorter (linear systolic array) until an "order count circuit" recognized sorted order throughout the vector of operands. The operands are retrieved from storage by use of read/write address registers which are initially set to the address of the first operand in the vector. The operands were accessed from memory sequentially until the last vector (Image Omitted) operand address resided in the read/write registers. The registers' address was then reset to the first operand for subsequent passes, such that the entire vector of operands was cycled through the sorter for each pass until order was recognized. Storage access time is the largest delay time associated with hardware sorting.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 3

Optimization Techniques for Recirculation Hardware Sorter

A previously described sorting method [*] accomplished sorting by recirculating an entire vector of operands through a hardware sorter (linear systolic array) until an "order count circuit" recognized sorted order throughout the vector of operands. The operands are retrieved from storage by use of read/write address registers which are initially set to the address of the first operand in the vector. The operands were accessed from memory sequentially until the last vector

(Image Omitted)

operand address resided in the read/write registers. The registers' address was then reset to the first operand for subsequent passes, such that the entire vector of operands was cycled through the sorter for each pass until order was recognized. Storage access time is the largest delay time associated with hardware sorting. A reduction in storage access time is accomplished using the optimization techniques described herein. Recirculation sorting [*] demonstrated that the "Z" (sorter depth) quantity of vector operands becomes ordered with each pass, such that if Z = 10 after pass one (1) 10 operands are ordered, for pass two (2) twenty operands, etc. By eliminating storage access for ordered operands on subsequent passes, sorting time is greatly reduced. Figs. 1A-1C illustrate a technique termed indexing. Pass 1 (Fig. 1A) is performed in the same fashion as that described previously in [*]. Pass #1 steps 0 through 4 have pushed 2Z quantity of operands into the sorter. Pass #1 steps 5 through 10 complete the access of N

(Image Omitted)

(vector length) operands interchanging read/write storage accesses by flushing (forcing) the residue operands in the sorter into an "order count circuit" prior to writing the operands back to memory. The "order count circuit" holds a copy of the previous and present operands written to memory and increments the count each time the previous operand was < or > the present _ _ operand. (Depends on ascend/descend order.) This "order count circuit", after completing pass #1, may now be used to index the read/write address registers past the storage addresses of operands already ordered. The minimum index per pass will equal Z. However, since the "order count circuit" also increments for the equals (=) compare results, the maximum index could be as much as N, the entire vector. This would be the case where many operands are the same or portions of the vector were already ordered. Pass #2 (Fig. 1B) will illustrate a technique termed oscillation. For oscillation the read/write addr...