Browse Prior Art Database

Merging With Offset Value Codes and the Vector Facility

IP.com Disclosure Number: IPCOM000037023D
Original Publication Date: 1989-Nov-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Case, DR: AUTHOR [+3]

Abstract

This invention describes an algorithm which uses "offset value codes" to merge sorted strings together effectively with the IBM 3090 Vector Facility. An offset value code is a way of coding the relationship between two keys, and presents a faster replacement-selection algorithm based on this code. The offset value code is formed by comparing two keys a halfword at a time. When two halfwords being compared are unequal, a "codeword" is formed by taking the offset and the value of the unequal halfword. Specifically, the offset value code is a 4-byte codeword consisting of two parts: the first two bytes specify the byte offset of the halfword just beyond the first unequal halfword; and the next two bytes contain the one's complement of the first unequal halfword.

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

Page 1 of 1

Merging With Offset Value Codes and the Vector Facility

This invention describes an algorithm which uses "offset value codes" to merge sorted strings together effectively with the IBM 3090 Vector Facility. An offset value code is a way of coding the relationship between two keys, and presents a faster replacement-selection algorithm based on this code. The offset value code is formed by comparing two keys a halfword at a time. When two halfwords being compared are unequal, a "codeword" is formed by taking the offset and the value of the unequal halfword. Specifically, the offset value code is a 4-byte codeword consisting of two parts: the first two bytes specify the byte offset of the halfword just beyond the first unequal halfword; and the next two bytes contain the one's complement of the first unequal halfword. Offset value codes have been used effectively for sorting and merging using the replacement- selection technique with scalar instructions for many years.

When using the Vector Facility to merge sorted lists of data, the most straightforward way to do this is to put the keys to be merged into the vector registers and issue instructions that compare data. However, when the size of the keys is larger than the size of the vector registers, more than one operation is needed for one set of keys. The processing could become very complicated and time consuming. This problem can be avoided by using the offset value codes to represent the keys. Offset value codes...