Browse Prior Art Database

Arrangement for Speeding up Compare and Exchange Operations for Sort/Merge

IP.com Disclosure Number: IPCOM000077211D
Original Publication Date: 1972-Jun-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 5 page(s) / 121K

Publishing Venue

IBM

Related People

Tsui, F: AUTHOR [+2]

Abstract

Sort/merge - a most-often-used operation in commercial and administrative applications of data processing - consists mainly of comparing the control-field portions of records and arranging the records in desired sequence. Compare and exchange are, therefore, the two main functions used in sort/ merge. This arrangement allows the compare and exchange operations for sort/merge to be executed more directly, efficiently, and speedily. The basic idea of the arrangement is to create a facility for: comparing arbitrarily specifiable portions of two operands, with the objective of comparison (for ascending or descending order) also arbitrarily specifiable, and exchanging the operands (or their addresses) when the result of the comparison calls for it.

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

Page 1 of 5

Arrangement for Speeding up Compare and Exchange Operations for Sort/Merge

Sort/merge - a most-often-used operation in commercial and administrative applications of data processing - consists mainly of comparing the control-field portions of records and arranging the records in desired sequence. Compare and exchange are, therefore, the two main functions used in sort/ merge. This arrangement allows the compare and exchange operations for sort/merge to be executed more directly, efficiently, and speedily. The basic idea of the arrangement is to create a facility for: comparing arbitrarily specifiable portions of two operands, with the objective of comparison (for ascending or descending order) also arbitrarily specifiable, and exchanging the operands (or their addresses) when the result of the comparison calls for it.

This can be implemented by using an arrangement comprising the following components: (1) a "compare and exchange sequencing table" (to be called CEST for abbreviation) containing items which specify the sequence and range of the compare and exchange operations. A usable form which the table items can take is the following: (a) Each item is 4-bytes long, consisting of two 2-byte fields. The first 2-byte field contains: a 4-bit indicator field and a 12-bit displacement (4). The second 2-byte field can be used, either as an 8-bit mask field ("1"s for bit positions to be compared) and an 8-bit length field, or as a ]6-bit length field. (b) The 4-bit indicator field contains: A "c" bit which indicates "control-field" with "1" and remainder with "0" A "d" bit which indicates "descending" with "1" and ascending ' with "0" An "e" bit which indicates "end of table" with "1" and "non-last item" with "0" An "x" bit, not used, available for possible use for extensions. (2) Specification of a "compare and exchange records" (CXR) operation on records 1 and 2, either in the RS- OR SS-format of IBM System /360-370 instructions: (a) RS-Format: where R1 contains the first- byte address of Record 1, R3 contains the first-byte address of Record 2, and B2 and D2 give the effective address of the origin of the CEST table. The RS-format would be preferable, as it would have a shorter I-phase and shorter execution time, and also since bits 8 to 15 in the SS-format here do not designate one or two length counts, as the existing SS-instructions do. Moreover, in the RS- format, B(2) and D(2) give the CEST-origin address, which is similar to the "Translate" (TR) and "Translate and Test" (TRT) instructions using B(2) and D(2) to give the translation-table-origin address. Hence, much of the existing hardware for the table look-up can be used for the CXR purpose. (3) "Hardware (including microprogram) to interpret and execute the functions specified by the CXR-instruction and the CEST items. These include: (a) to obtain from CXR instruction and hold ready for use the first-byte addresses A(1), A(2) and A(T), of record 1, record 2, and CEST, respect...