Apparatus for transposition sorting of equal length records in overlap relation with record loading and extraction

• US 4,078,260 A
• Filed: 05/12/1976
• Issued: 03/07/1978
• Est. Priority Date: 05/12/1976
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Eswaran, Kapali P., Tung, Chin, Lum, Vincent Yu-Sun, Chen, Tien Chi
• Primary Examiner(s): Thomas, James D.
• Application Number:
  US05/685,859
• Time in Patent Office: 664 Days
• Field of Search: 340/172 S, 340/174 TF, 340/174 AA, 340/146.2, 364/900, 364/200
• US Class Current: 707/611
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence
• CPC Class Codes: G11C 19/00 Digital stores in which the information is moved stepwise, e.g. shift registers
• CPC Class Codes: G11C 19/0875 Organisation of a plurality of magnetic shift registers
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

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.

Claims

1. In an apparatus for rearranging N identificable 2m bit equal fixed length records, said apparatus including an externally controllable permutation network;

and information handling means adapted to respond to the records in the order of their arrival for loading the records into the network, for developing and applying control signals to the network so as to effectuate the physical rearrangement of the records, and for unloading the records from the network, the control signals being derived from comparisons of record indicia according to a predetermined algorithm;

wherein the improved permutation network comprises;

q sorting ladders, each of whose sorting time being a linear function of the number of records to be sorted, where q≧

1+log₃ (N+1)/4 , the ith ladder i≦

q includes;

n_i equal length shift register loops, n_i being constrained such that ##EQU4## Q_i being the remainder after assigning n_i to the ith ladder, if Q_i ≦

3, then n_i+1 can be set equal to Q_i, the ith ladder further includes;

a plurality of selectively operable dual mode switches connecting the loops such that each loop has no more than two adjacent switchable neighboring loops, and upon any boundary switch being set into a first mode responsive to a control signal, then the adjacent loops are cross connected in order to facilitate an exchange of any records circulating therein, upon the boundary switches to any loop being set into a second mode also responsive to a control signal, then the loop is maintained as a circulation path, one end loop of the ladder and the associated boundary switch coupling the information handling means and being operative as an input/output port; and

the permutation network further comprising;

clocking means for causing all the loops to move their contents in synchronism.

2. In an apparatus according to claim 1, wherein the information handling means includes means for serially loading and unloading N records into and from the aggregate of the q ladders, said q ladders being all respectively loaded or all respectively unloaded in the order of decreasing record capacity.

3. In an apparatus according to claim 1, the information handling means includes means for q way merging the records from the ladders.

4. In an apparatus according to claim 1, each loop has a capacity greater than or equal to the record size.

5. In an apparatus for rearranging N identifiable 2m bit equal fixed length records, said apparatus including an externally controllable permutation network;

and information handling means adapted to respond to the records in the order of their arrival for loading the records into the network, for developing and applying control signals to the network so as to effectuate the physical rearrangement of the records, and for unloading the records from the network, the control signals being derived from comparisons of record indicia according to a predetermined algorithm;

wherein the improved permutation network comprises;

a first and a second sorting ladder, the ladders respectively including n_i and n₂ equal length shift register loops, where n_i +n₂ ≧

N, n_i ≧

(3N-1)/4 , n₂ ≧

(n+1)/4 ;

each ladder further includes a plurality of dual mode switches;

said switches connecting the loops such that each loop has no more than two adjacent switchable neighboring loops, and upon any boundary switch being set into a first mode by a control signal, then the adjacent loops are cross connected in order to facilitate an exchange of any records circulating therein, upon the boundary switches to any loop being set into a second mode also responsive to a control signal, then the loop is maintained as a circulation path;

one end loop of each ladder and the associated boundary switch coupling the information handling means and being operative as an input/output port; and

clocking means for causing all th loops to move their contents in synchronism.