International Business Machines Corporation

Chin Tung

Tien C Chen

Hsu Chang

Vincent Yu-Sun Lum

Share-Young Lee

Kapali P Eswaran

This invention describes a pipeline sorter, in which record-pairs are compared and conditionally swapped while being advanced along the pipeline synchronously. The pipeline sorter has the topology of a U-shaped tube, with regularly spaced crosspaths linking the two arms. Records are loaded one at a time, into the input arm synchronously, and emerge out of the output arm, also one at a time and synchronously. Within the sorter, at periodic time intervals a number of record-pairs at correlated positions of the U-tube are compared. Dependent on the comparison outcome, either the original records themselves, moving along vertical paths, or their permutation, moving along crosspaths, will arrive at the next down-stream positions. In this manner, as soon as the last record has been loaded, the correctly sorted output will begin to emerge, with the overall sorting time completely overlapped by the loading and unloading of records.

Apparatus for sorting records in overlap relation with record loading

An apparatus for sorting of equal length records with the sorting time maximally overlapped by the time taken for loading and unloading of records. The minimal structure consists of a decision mechanism linked to and associated with a network of ladder structures. The activity within the network is so synchronized that the sorting activity in most ladders occurs while some ladder within the network is still undergoing the loading of input data; and during the unloading phase, the individually sorted data from each ladder are merged concurrently to produce a sequence of sorted records. The overlap between sorting and loading varies from 0 for records requiring no loading/unloading, to 100% for multi-ladder networks with loading/unloading. A single ladder structure supporting a type of transposition sort is first described both in a full exchange scheme and a fast version. Then, the mechanism for loading/unloading equal length records to the single ladder is set forth. Next, the use of two ladders of dissimilar lengths for facilitating the overlap between loading/unloading and sorting is revealed. Lastly, the general multi-ladder case with which complete overlap is achieved terminates the specification. The ladders themselves are formed from a plurality of equal length loops connected by dual mode switches such that when a switch between a pair of adjacent loops is set electrically into the first mode ('on') the adjacent loops are cross-connected facilitating an exchange of any records circulating therein. When the two switches bounding a loop are electrically set in the second mode ('off'), the loop is maintained as a circulating path. An end loop of each ladder operates as an input/output port. In one embodiment, control signals for operating the dual-mode switches are developed by an external decision mechanism through the expedient of storing and comparing the keys of each record to be sorted, said signals control the switches in loading, sorting, merging and extracting. An alternate embodiment can employ a plurality of detectors to transmit the detected keys to a decision mechanism dynamically without previously copying the keys.

Apparatus for transposition sorting of equal length records in overlap

Information processing is conveniently achieved by a structure which uses a novel binary switch. The switch can steer two data streams so that they will either cross one another or bypass one another, depending upon external control. A linear array of shift register loops are linked together by these flow-steering binary switches to form a storage structure which is termed a ladder. The ladder provides a variety of data structures. For example, it can alternate between LIFO (last in-first out) and FIFO (first in-first out). It can also dynamically rearrange data items according to recency of usage, in order to improve average access time to any data item. The binary switch and the ladder structure are conveniently provided using magnetic bubble domain technology, although other technologies can also be used.

Ladder for information processing

An apparatus for performing efficient transposition exchange sorts among equal length records is described. The apparatus takes advantage of the flow steering property of linkable circulating storage loops to minimize the average access time by positioning information closer to the output port in a storage structure. The apparatus is formed from a linear array of equal size shift register loops each holding one record. The loops are switchably interconnected such that when two boundary switches are set in a first mode, the contents of each loop normally circulate wholly therewithin. Upon a common boundary switch being set in a second mode, the contents within a first loop flow into a second loop and vis-a-vis. By setting a common boundary switch to the second mode, the contents of a pair of adjacent loops are exchanged in the duration of one loop cycle time. Further exchanges can be started before a previous one is complete; this overlapping of operations can lead to an effective exchange rate of two exchanges per loop cycle. By repeating the exchange for consecutive pairs of loops, then the contents of any reference loop can be migrated to an output port D loops away in (D + 1)/2 loop cycle times.

Apparatus and machine implementable method for the dynamic rearrangement

A text editing system is described which is comprised of single technology elements. That is, the system is comprised of dynamic shift registers which are entirely implemented with either magnetic bubble domain devices or charge coupled devices. These shift registers can be randomly accessed using write and read decoders to provide great flexibility in entry, retrieval, and restoring of data. An editing shift register is used for text editing functions, such as insertion of data, deletion of data, etc. This editing shift register performs the data manipulation functions by using techniques such as freezing of data bits and bypassing of data bits in order to change the order of the data and to close gaps which may occur in the data. The shift registers used for storage and the editing shift register are characterized in that all data manipulation functions and all accessing functions do not require a change in the sequence of the drive field used to move the data bits.

Growing community of inventors

Saratoga, CA, United States of America

Chin Tung