Browse Prior Art Database

Bubble Chip for Locating the Smallest Stored Key And for Sorting

IP.com Disclosure Number: IPCOM000051886D
Original Publication Date: 1981-Mar-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 5 page(s) / 50K

Publishing Venue

IBM

Related People

Chang, H: AUTHOR [+2]

Abstract

A bubble domain chip is shown which provides on-chip key sorting in order to locate the smallest stored key of many keys which are stored in many shift registers, and to provide an output of all the keys (and records) stored in order of ascending keys. The on-chip bubble components are shown in the figure. They comprise a shift register storage EO which is adjacent to an inverter/replicator IR. Another shift register storage E provides a record of eliminated keys and is adjacent to a replicator/annihilator RA2. A compressor storage is provided which has a 1-bit bubble pusher 10 for providing 1 bit during each cycle of the drive field for moving a bubble out of the compressor storage into an expander/detector ED.

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

Page 1 of 5

Bubble Chip for Locating the Smallest Stored Key And for Sorting

A bubble domain chip is shown which provides on-chip key sorting in order to locate the smallest stored key of many keys which are stored in many shift registers, and to provide an output of all the keys (and records) stored in order of ascending keys. The on-chip bubble components are shown in the figure. They comprise a shift register storage EO which is adjacent to an inverter/replicator IR. Another shift register storage E provides a record of eliminated keys and is adjacent to a replicator/annihilator RA2. A compressor storage is provided which has a 1-bit bubble pusher 10 for providing 1 bit during each cycle of the drive field for moving a bubble out of the compressor storage into an expander/detector ED. Another replicator/ annihilator RA1 is located between the compressor storage and a shift register storage C which is used to store current surviving records. Latches L are provided for filtering out eliminated keys, and a replicator/transfer gate unit RT is used to provide non-destructive readout of information into the storage registers SR1, SR2, ..., SRM. Registers SR1-SRM hold the keys, with the high order bit to the left and the low-order bit to the right of these registers. A decoder is associated with the registers for selective access of the registers SR1-SRM.

Prior to describing the operation of this bubble chip, some unique features of the chip will be described: 1. The smallest-key locating and key sorting are performed with bubble devices on a chip. Only the initial input and final output are communicated with the outside world through the I/O pins. Even when a large number of keys must be spread over several chips, the only connection between the chips will be the output of E-OR-C. These registers can be connected in serial or ANDed together in parallel. 2. The logic is performed in parallel. Consequently, the time required to locate the smallest key is proportional to the number of bits per key, but independent of the number of keys. For sorting, the time is proportional to N, where N is the number of records (or keys). By contrast, the time for sorting in a conventional random-access memory with a serial computer is proportional to N log N. 3. The several processing registers arranged in parallel and communicating with each other through the replicator/ annihilator is a structure novelty which allows the addition of more registers to execute more processing steps. 4. If there are duplicate keys, only one copy of each unique key is read out. A count of the number of duplicates is supplied. Thus, summary statistics on the contents of a field can be obtained rapidly along with a sorted list of the distinct keys. 5. It is also conceivable to use the structure to perform associative search, which can be reduced to find the smallest key in the following manner: Assume the keys are: 1 0 1 0 0 1 0 1 0 At the interface between the storage and processing...