Browse Prior Art Database

Recirculation Sorter-Memory Architecture

IP.com Disclosure Number: IPCOM000039181D
Original Publication Date: 1987-Apr-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 2 page(s) / 50K

Publishing Venue

IBM

Related People

Ashley, DJ: AUTHOR [+2]

Abstract

A previously described sorting scheme [*] uses fixed length sorters to sort a long vector of data into a series of short but sorted vectors of data. These sorted vectors are then merged together to complete the sorting process. Recirculation architecture places the length of the sorted segments as a function of the randomness of the data. (Image Omitted) The vector of data to be sorted resides in memory. Reads made from memory to the sorter (push) repeat until the first element of data leaves the sorter to go to the holding cell. The memory recirculation selection will now write the data from the holding cell back to the source address of first element of data pushed into the sorter.

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 80% of the total text.

Page 1 of 2

Recirculation Sorter-Memory Architecture

A previously described sorting scheme [*] uses fixed length sorters to sort a long vector of data into a series of short but sorted vectors of data. These sorted vectors are then merged together to complete the sorting process. Recirculation architecture places the length of the sorted segments as a function of the randomness of the data.

(Image Omitted)

The vector of data to be sorted resides in memory. Reads made from memory to the sorter (push) repeat until the first element of data leaves the sorter to go to the holding cell. The memory recirculation selection will now write the data from the holding cell back to the source address of first element of data pushed into the sorter. This read, eject to holding cell, write to memory repeats until all elements of the vector have been pushed into the sorter (clock pulses = vector length). Zeros are forced into the top of the sorter (or force + depending on ascending or descending sort) equal to the number of X, Y registers (depth of sorter x 2) while continuing the writes from the holding cell to contiguous memory locations. The checking mechanism will monitor whether ascending or descending order has been met by determining X J Y

(Image Omitted)

or X < Y

_ for the clock pulse cycles required to push the final element into the holding cell. If the checker was not consistently reporting X > Y or X < Y throughout the push cycle, then the sorter _ will be initialized with all +...