Browse Prior Art Database

Execution of Grade, Member, Index and Insert Using VLSI Sorter

IP.com Disclosure Number: IPCOM000043677D
Original Publication Date: 1984-Sep-01
Included in the Prior Art Database: 2005-Feb-05
Document File: 1 page(s) / 11K

Publishing Venue

IBM

Related People

Kovacs, LA: AUTHOR

Abstract

Several designs for VLSI hardware sorters sort numeric or character data as fast as the operands can be moved into and out of the sorter, that is, N operands can be sorted in 2N machine cycles. Several other functions related to sorting can be performed with the aid of such a device, and these functions are described here in terms of a programming language (APL) functions (but their equivalents can be found in almost any application). APL function "grade" is performed by adding sufficiently wide shift registers to the VLSI sorter. The first of these registers receives the output of a counter during the input phase of a sort, so that each data item of a sequence has associated with it its index number or position in the sequence. The indices are shifted along with the data items, but do not take part in the comparisons.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 100% of the total text.

Page 1 of 1

Execution of Grade, Member, Index and Insert Using VLSI Sorter

Several designs for VLSI hardware sorters sort numeric or character data as fast as the operands can be moved into and out of the sorter, that is, N operands can be sorted in 2N machine cycles. Several other functions related to sorting can be performed with the aid of such a device, and these functions are described here in terms of a programming language (APL) functions (but their equivalents can be found in almost any application). APL function "grade" is performed by adding sufficiently wide shift registers to the VLSI sorter. The first of these registers receives the output of a counter during the input phase of a sort, so that each data item of a sequence has associated with it its index number or position in the sequence. The indices are shifted along with the data items, but do not take part in the comparisons. The search functions, "member" and "index", are performed much faster on a sorted list. They, therefore, are done by first sorting the list, and then doing a binary search on the sorted data and the matching indices. "Index" requires both sorted data and the matching indices. The "insert" function is performed by appending the new data to the end of the list and then re-sorting it. This is practical because the VLSI sorter is so fast.

1