Apparatus for the sorting of records overlapped with loading and unloading of records into a storage apparatus4110837Abstract This invention describes an automatic sorter which consists of a linear array of n modules called permuters. Each permuter contains an upper-lower pair of registers, a comparison mechanism and gating arrangement to the permuters immediately above and immediately below. A sequence of N records, N being no larger than 2n, can be loaded, one at a time, into the sorter from the top during the "down mode": at the same time each of the permuters function to save the lower-ordered record in the lower register, to expel the higher ordered record to the permuter below, and to receive a record from above into the upper register. As soon as all records are loaded, the sorter enters the "up mode" of operation, in which each permuter keeps the higher ordered record in the upper register, expels the lower-ordered record through the top, and receives a record into the lower register. The uppermost permuter thus ejects one record at a time, in sorted order. There is no discernible sorting time, the sorting being completely overlapped by the loading and unloading of information records. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
______________________________________
REGISTER 9 11
RECORD 1 3
______________________________________
where the number in the record row indicates the value of the record's key field or other ordering indicia. If the sorter is in down mode, channel 21 of comparator 35 will be activated so that the lesser record of registers 9, 11 is transmitted over bus 37 to register 11 and the greater record of the register pair is transmitted over bus 39 to register 13. Thus after permutation the register contents are:
______________________________________
REGISTER 11 13
RECORD 1 3
______________________________________
If the sorter is in up mode, and assuming the Register/Record situation first recited above, channel 19 will be activated so that the lesser record of registers 9, 11 is transmitted over bus 47 to register 7 and the greater record of the register pair is transmitted over bus 49 to register 9. Thus after permutation in up mode (beginning with Records 1, 3 in register 9, 11, respectively) the register contents would be:
______________________________________
REGISTER 7 9
RECORD 1 3
______________________________________
The lower register of a pair at a given level could be empty, and this fact is indicated by its contents being coded as the largest possible record. Then the normal comparison will achieve the effect of push down during down mode, and pop-up during up mode. That is, if register 7, 11 or 15 is empty, during down mode these registers will, upon comparison, be occupied by the previous contents of registers 5, 9 and 13 respectively. During up mode, if registers 7, 11 or 15 are empty, a comparison will lead to the ascension of the previous occupants of registers 5, 9 and 13 respectively. During up mode, the permuted actions invariably bring an empty record (coded as all 1's) into register 15. The above treatment applies also when both upper and lower registers are empty. The case of valid lower register contents coupled with an empty upper register never occurs in a correctly used permuter. For completeness, the global output can be considered the lower register of a Permuter Zero. DETAILED STRUCTURE Having seen a broad implementation of the present invention with respect to FIG. 3 we shall now turn to FIG. 6 which shows a detailed implementation of the invention. The implementation of FIG. 6 is the same as that of FIG. 3 but with the appropriate control and gating means shown explicitly. Thus, registers 5, 7, . . . 15 are the same registers as seen in FIG. 3. Permuters 923, 935 and 929, seen in dash line, with their associated channels 27, 31; 19, 21; and 43, respectively, are the same as those seen in FIG. 3. Likewise, the input and the output are the same. Likewise the buses within the respective channels of FIG. 6 are the same as those in FIG. 3. Interconnection of, a typical register pair and its association with its permuter can be explained in detail with respect to Permuter Two. For example, registers 9 and 11 are gated at time pulse .phi.1 as inputs to the comparator 35. During up mode, at time pulse .phi.2, the outputs of this comparator are connected through gate 601 to upper channel 19 which is the two bus channel for transmitting the lesser and greater of the records from register pairs 9, 11 to registers 7 and 9, respectively, based on their ordering indicia. The lesser record thus crosses the permuter boundary to reside in the next permuter above. On the other hand during down mode at time pulse .phi.2 the outputs of this comparator are connected instead through gate 603 to lower channel 21, which is the two bus channel for transmitting the lesser and greater of the records from register pairs 9, 11 to registers 11 and 13, as shown, and the greater record thus crosses the permuter boundary to reside in the next permuter below. The same situations obtain for all permuters, except that the topmost permuter has no real next permuter above, but a fictitious Permuter Zero representing the global input and output. The global input is gated by proper time pulse signals also. The bottom-most permuter has no real next permuter below, but a data sink (path 25) and a source of all ones, the latter geing gated by proper time pulse signals. A system of delays is provided to avoid movement conflicts, with D4>D3 >D2 >D1. The delays are such that during the up mode data in the upper permuters are stored first and during the down mode data in the lower permuter are stored first. A time pulse .phi.2 should be long enough to allow for the longest delay plus the time to transfer one record. This delay-based system of course can be retraced by proper buffering. The description of Permuter One and Permuter Three of FIG. 6 is similar to that for Permuter Two, as was the case for FIG. 3. Timing means useful in the invention are seen in FIG. 5. The outputs of the timing means are signals .phi.1, .phi.2 and D, D discussed previously. Two phase clock 501 produces signals .phi.1, .phi.2 on lines 503, 505, respectively. Line 503 is connected to ring counter 507. Upon receipt of N pulses of .phi.1, N being equal to 6 in the examples shown in FIGS. 3, 4 and 6, and ring counter resets itself to 0 and issues a signal along path 508 to flip the flip-flop 509. Flip-flop 509 produces signals D and D from its upper and lower outputs, respectively. Upon receiving the reset signal along 508 at the count of N, one of the outputs currently has a 1 value and will condition AND 511 or 513 to allow reversal of flip-flop 509, and both D and D will be inverted, so that at time pulse .phi.2 the proper gating out of the comparators is made correctly. In operation, the timing means can be initially set to the down mode. For example, an external pulse line (not shown) can set flip-flop 509 to its One state to begin the down mode by activating D. Ring counter 507 is initialized to zero. Ring counter 507 then counts .phi.1 pulses and at reset time the contents of flip-flop 509 is reversed. This way D will be equal to 1 for the first N time cycles, and zero for the next N cycles. D will always be the negation of D. The operation continues, with signals D and D being alternatingly activated as desired, and many sorting tasks can be performed in succession, with proper identification of N.ltoreq.2n. DETAILED OPERATION A detailed description of permutation action of a given level, Level Two of the push-pop sorter, will now be given with respect to FIG. 6. A detailed description of sorting using all three permuters will be given subsequently. Assume the following records in the following registers in Permuter Two:
______________________________________
REGISTER 9 11
RECORD 1 3
______________________________________
where the number in the record row indicates the value of the record's key field or other ordering indicia. The clock pulse .phi.1 sends the records to comparator 35. If D=1, the sorter is in down mode, channel 21 will be activated by .phi.2 ANDed with D via delay D2 activating gate 603 so that the lesser record of registers 9, 11 is transmitted over bus 37 to register 11, and the greater record of the register pair is transmitted over bus 39 to register 13 (the upper register of the permuter below). Thus after permutation the register contents are:
______________________________________
REGISTER 11 13
RECORD 1 3
______________________________________
If the sorter were in up mode (D=0), and assuming the Register/Record situation first recited above, channel 19 will be activated by .phi.2, ANDed with not D (D) via delay D2 activating gate 601 so that the lesser record of registers 9, 11 is transmitted over bus 47 to register 7 (the lower register of the permuter above), and the greater record of the register pair is transmitted over bus 49 to register 9. Thus after permutation in up mode (beginning with Records 1, 3 in register 9, 11, respectively) the register contents would be:
______________________________________
REGISTER 7 9
RECORD 1 3
______________________________________
A detailed description of the sorting operation of my invention will now be given with respect to FIGS. 4, 5 and 6 taken simultaneously, to show actual operation of timing of one embodiment of my invention. In FIG. 4 we see that six records are to be inserted into the apparatus of this invention in down mode. The records are in the order 1, 2, 4, 5, 3, 6. They will be ejected from this apparatus in sorted order during up mode, namely 1, 2, 3, 4, 5, 6. As can be seen from FIG. 4 there are 12 timing periods. For convenience we have t.sub.k = t.sub.o + k cycles, a cycle being no smaller than (comparison time + data transfer time + maximal delay (D4) ). The registers in the apparatus are first reset to contain all 1's, then the apparatus is set to down mode (D=1). The input phase begins at t.sub.o with a dummy compare at .phi.1. At .phi.2, as seen from FIG. 4, record 1 is inserted into the upper register of Permuter One. Referring to FIG. 6 this is seen as an input record gated through gate 623 at .phi.2 into register 5. Thus just before time t.sub.1 we have:
______________________________________
REGISTER 5 7 9 11 13 15
RECORD 1 -- -- -- -- --
______________________________________
At time t.sub.1 during .phi.1 the records enter the comparators, since register 7 is empty (all ones), it appears to be the larger, and record 1, the smaller quantity for comparator 23, and is pushed down to register 7 during .phi.2 via gate 631 and path 41. The movement of empty records do not create any problems, and it suffices to say that they are uniformly pushed down by one register level; the previous contents of 15 is pushed through bus 25 and is ignored. During the same clock pulse .phi.2, a second record 2 enters the upper register in Permuter One as seen in FIG. 4. Referring to FIG. 6 again, this is seen as a record entering the input and being gated by gate 623 to register 5 at a delay D4>D3 to assure non-interference with the vacating record 1, now in register 7. We have just before time t.sub.2 :
______________________________________
REGISTER 5 7 9 11 13 15
RECORD 2 1 -- -- -- --
______________________________________
At this point of time, pulse .phi.1 activates the comparator 23. Since we are still in the down mode as seen from FIG. 4, the lower channel 31 is activated during .phi.2 and the lesser record, in this case record 1, is transferred over bus 41 to reside again in register 7 while the greater record, namely record 2 is transferred over bus 33 to register 9 in Permuter Two. At the same clock pulse, but with a different delay (D4>D3 >D2), a new record is loaded into register 5. The register/record situation just before time t.sub.3 reads:
______________________________________
REGISTER 5 7 9 11 13 15
RECORD 4 1 2 -- -- --
______________________________________
During .phi.1 of t.sub.3 the comparators are activated. Meaningful compares occur at comparator 23, while 29 and 35 serve only to push down the register contents. At .phi.2 a new record (5) enters register 5 while 1, 4, 2 occupy registers 7, 9 and 11, respectively. The delays assure non-interference of data so that the register contents just before time t.sub.4 are as follows:
______________________________________
REGISTER 5 7 9 11
RECORD 5 1 4 2
______________________________________
The next comparison involves two meaningful compares at .phi.1. Gate 603 opens first (with delay D2) to route records 4 and 2 into registers 11 and 13 respectively, then gate 631 at delay D3 routes 1, 5 into registers 7 and 9 respectively. At delay D4, a new record (3) is brought into register 5. Thus just before time t.sub.5 the register contents are:
______________________________________
REGISTER 5 7 9 11 13 15
RECORD 3 1 5 2 4 --
______________________________________
The next comparisons lead to the loading of 1, 3, 2, 5, 4 into registers 7, 9, 11, 13 and 15 respectively, and a new record (6) occupies register 5. At this point the contents of the registers, just before time t.sub.6 are:
______________________________________
REGISTER 5 7 9 11 13 15
RECORD 6 1 3 2 5 4
______________________________________
The input phase is now complete, and the sorter contents are half-sorted. At this point the up mode begins. Since D3<D2<D1 the upper channels are activated in sequence, the uppermost channel first. Pulse .phi.1 will again compare the register contents within each permuter, and the upper channels 27, 19 and 43 will be activated upon clock pulse .phi.2. Upon time t.sub.6, clock pulse .phi.1 gates the contents of register pairs for comparison. Then pulse .phi.2 activates the upper channels, the topmost one (27) first, so that record 1 emerges through gate 617 and path 3 to become global output at delay D1, concurrently record 6 is rerouted through gate 617, paths 45, 17 into register 5. At delay D2, record 2 is gated by gate 601 through path 47 of upper channel 19 into register 7 above, concurrently record 3 (being larger than 2) is made to go through path 49 into register 9. At delay D3, record 4 rises, through path 51 of upper channel 43 to register 11 and record 5 is recirculated via path 53 to register 13. The rudimentary upper channel below Permuter Three feeds all-ones to register 15 as an empty indication. Thus just before time t.sub.7 the contents of the registers are as follows:
______________________________________
REGISTER 5 7 9 11 13 15
RECORD 6 2 3 4 5 --
______________________________________
At the next .phi.1, the comparators are again activated. Upon .phi.2, after delay D1 Permuter 923 will transmit record 2 over bus 3 to the global output, while record 6, being the greater record of the pair will be transmitted over paths 45 and 17 back to register 5. Then in Permuter 935, after delay D2, the lesser record in the register pair, namely record 3 is transmitted over bus 47 to cross the permuter boundary into register 7 while the greater, namely record 4 is kept in register 9. After delay D3, Permuter 929 delivers record 5 upwards into register 11, the previous contents of register 15, carrying an empty indication, now occupies register 13, and a new set of all-ones occupies register 15 at delay D4. Just before time t.sub.8 the contents of the registers are as follows:
______________________________________
REGISTER 5 7 9 11 13 15
RECORD 6 3 4 5 -- --
______________________________________
During the next .phi.1 pulse the comparators are again activated in up mode. Upon .phi.2, after delay D1, record 3 which resides in the lower register of Permuter One, namely register 7 of FIG. 6, is the lesser record, and is gated over bus 3 to be the global output while record 6, which is the greater record of the record pair is made to reoccupy register 5. Similarly, with respect to Permuter Two, after delay D2, the lesser record of the register pair, namely record 4 residing in register 9, is gated over bus 47 to register 7, and record 5 is routed over bus 49 back to register 9. The empty contents in Permuter Three do not produce significant changes except the rising of an empty indication to register 11 above, at delay D3. Delay D4 leads to the replenishment of register 15 by an empty indication. Thus just before time t.sub.9 the registers and their contents are as seen below, records 1, 2, 3 having been delivered in sequence:
______________________________________
REGISTER 5 7 9 11 13 15
RECORD 6 4 5 -- -- --
______________________________________
During the next .phi.1 of t.sub.9, the comparators are again activated. Upon .phi.2 after dealy D1 the lesser of the two records in Permuter One, namely record 4, is gated over bus 3 to be the global output while the greater record, namely record 6, is retransmitted over bus 45 to register 5. After delay D2 in permuter 935, record 5 rises to occupy register 7. Thus, just before t.sub.10, the contents of the apparatus are as seen below:
______________________________________
REGISTER 5 7 9 11 13 15
RECORD 6 5 -- -- -- --
______________________________________
During the next .phi.1, the comparators are again activated. At this point there are only records in Permuter One so only the output of comparator 29 will be of any consequence. After delay D1, the lesser of the two records, namely record 5 will be gated on bus 3 to be the global output and the greater of the two records, namely record 6 will be gated over bus 45 to reoccupy register 5. Just before t.sub.11 the contents of the apparatus are as seen below:
______________________________________
REGISTER 5 7 9 11 13 15
RECORD 6 -- -- -- -- --
______________________________________
During the next .phi.1 the lone entry goes through the comparator as the lesser record, and during .phi.2 after delay D1 is ejected through bus 3. At time t.sub.12 therefore the output is complete, and has been delivered in non-decreasing sequence, at the regular rate of one record per cycle. Thus, we have seen that records were entered into the invented sorter in the order 1, 2, 4, 5, 3, 6 and emerged in sorted order 1, 2, 3, 4, 5, 6 with sorting completely overlapped with input and output of the records to and from storage. While the invention has been particularly shown and described with reference to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and detail, including but not limited to those above suggested, may be made therein without departing from the spirit, scope and teaching of the invention. For instance, the various delays can be removed if adequate buffer latches are provided to house the output records after comparison. Also, relatively trivial redefinitions of the compare result signals will enable the output to appear in non-increasing sequence. For symmetry we have used D1 through D4 as time delays, actually D1 could be zero. Accordingly, the apparatus and method herein disclosed are to be considered merely as illustrative and the invention is to be limited only as specified in the claims.
|
Same subclass Same class Consider this |
||||||||||