Sorting and merging of files in a multiprocessor

Claim 3

A multiprocessor apparatus for merging a plurality of sorted files, comprising: secondary memory means for storing files including the plurality of sorted files; a plurality of first processors, connected to the secondary memory means, each for merging files transferred thereto into a merged file a portion at a time wherein the merged file includes a plurality of the portions; means, connected to the secondary memory means and to the first processors, for transferring from the secondary memory means to each first processor a different plurality of the sorted files, each file of a plurality of the sorted files transferring to any first processor at any times as part of the merging of the plurality of the sorted files being a different file from the files of the other pluralities of the sorted files transferred to the other first processors; a second processor, connected to the first processors, for merging portions of the merged files transferred to the second processor from the first processors into an output file in parallel with merging of the transferred sorted files at the first processors; means, connected to the second processor and to the first processors, for transferring the merged file a portion at a time from each of the first processors to the second processor; and means, connected to the second processor, for storing the output file in the secondary memory means.

Claim 4

A multiprocessor apparatus for merging a plurality of sorted files, comprising: secondary memory means for storing files including the plurality of sorted files; a plurality of first processors, connected to the secondary memory means, each for merging files transferred thereto into a merged file a portion at a time wherein the merged file includes a plurality of the portions; means, connected to the secondary memory means and to the first processors, for transferring from the secondary memory means to each first processor a different plurality of the sorted files, each file of a plurality of the sorted files transferring to any first processor at any times as part of the merging of the plurality of the sorted files being a different file from the files of the other pluralities of the sorted files transferred to the other first processors; a second processor, connected to the first processors, for merging portions of the merged files transferred to the second processor from the first processors into an output file in parallel with merging of the transferred sorted files at the first processors; means, connected to the second processor and to the first processors, for transferring the merged file a portion at a time from each of the first processors to the second processor; and means, connected to the second processor, for storing the output file in the secondary memory means.

Claim 7

The method of claim 3 wherein the step of storing each sorted portion comprises the steps of: transferring each sorted portion from a plurality of the first processors to a fourth processor; merging at the fourth processor into a large sorted portion a plurality of sorted portions each transferred from a different first processor; and storing each large sorted portion in the secondary memory for storing sorted portions; and wherein the step of transferring a different plurality of sorted portions comprises the step of: transferring from the secondary memory for storing sorted portions to each second processor a different plurality of large sorted portions.

Claim 8

A multiprocessor apparatus for sorting an input file, comprising: secondary memory means for storing files including the input file; a plurality of first processors, connected to the secondary memory means, each for storing each input file portion transferred to the first processor from the secondary memory means; means, connected to the secondary memory means and to the first processors, for transferring from the secondary memory means to each first processor a different at least one portion of the input file, each portion of the input file transferred to any first processor at any times as part of the sorting of the input file portions being a different file portion from the portion of the input file transferred to the other first processors; means, connected to the secondary memory means and to the first processors, for storing each sorted portion in the secondary memory means; a plurality of second processors, connected to the secondary memory means, each for merging sorted portions transferred to the second processor from the secondary memory means into a merged portion; means, connected to the secondary memory means and to the second processors, for transferring from the secondary memory means to each second processor a different plurality of sorted portions; a third processor, connected to the second processors, for merging merged portions transferred to the third processor from the second processors into an output file; means, connected to the third processor and to the second processors, for transferring the merged portions from the second processors to the third processor; and means, connected to the third processor and to the secondary memory means, for storing the output file in the secondary memory means.

Claim 9

A multiprocessor apparatus for sorting an input file, comprising: secondary memory means for storing files including the input file; a plurality of first processors, connected to the secondary memory means, each for storing each input file portion transferred to the first processor from the secondary memory means; means, connected to the secondary memory means and to the first processors, for transferring from the secondary memory means to each first processor a different at least one portion of the input file, each portion of the input file transferred to any first processor at any times as part of the sorting of the input file portions being a different file portion from the portion of the input file transferred to the other first processors; means, connected to the secondary memory means and to the first processors, for storing each sorted portion in the secondary memory means; a plurality of second processors, connected to the secondary memory means, each for merging sorted portions transferred to the second processor from the secondary memory means into a merged portion; means, connected to the secondary memory means and to the second processors, for transferring from the secondary memory means to each second processor a different plurality of sorted portions; a third processor, connected to the second processors, for merging merged portions transferred to the third processor from the second processors into an output file; means, connected to the third processor and to the second processors, for transferring the merged portions from the second processors to the third processor; and means, connected to the third processor and to the secondary memory means, for storing the output file in the secondary memory means.

Claim 10

The apparatus of claim 5 wherein the means for storing each sorted portion comprise: a fourth processor of the multiprocessor apparatus connected to the first processors, for merging into a large sorted portion a plurality of sorted portions each received from a different first processor; means, connected to the fourth processor and to the first processors, for transferring each sorted portion from a plurality of the first processors to the fourth processor; and means, connected to the fourth processor and to the secondary memory means, for storing each large sorted portion in the secondary memory means; and wherein the means for transferring a different plurality of sorted portions comprise: means, connected to the secondary memory means and to the second processors, for transferring from the secondary memory means to each second processor a different plurality of large sorted portions.

Claim 13

The method of claim 7 wherein the step of transferring the merged records comprises the step of transferring the blocks of the merged records a block at a time from every first processor to the second processor, and wherein the step of merging at the second processor comprises the step of merging at the second processor the transferred blocks of the merged records a block at a time from every first processor.

Claim 14

A multiprocessor apparatus for merging a plurality of sorted files, comprising disk memory means for storing files including the plurality of sorted files; a plurality of first processors, connected to the disk memory means, each for merging records of blocks which are transferred to the first processor from the disk memory means into blocks of merged records, by merging at any time a block of each file of a plurality of files; means, connected to the disk memory means and to the first processors, for transferring from the disk memory means to each first processor a different plurality of the sorted files by transferring the blocks of each sorted file sequentially a block at a time, each file of a plurality of the sorted files transferred to any first processor at any times as part of the merging of the plurality of the sorted files being a different file from the files of the other pluralities of the sorted files transferred to the other first processors; a second processor, connected to the first processors, for merging blocks of the merged records transferred thereto from the first processors in parallel with merging of records into as-yet transferred blocks of the merged records at the first processors; means connected to the first processors and to the second processor, for transferring the blocks of the merged records a block at a time from each of the first processors to the second processors; and means, connected to the second processor and to the disk memory means, for storing the records merged at the second processor in an output file on the disk memory means.

Claim 15

A multiprocessor apparatus for merging a plurality of sorted files, comprising disk memory means for storing files including the plurality of sorted files; a plurality of first processors, connected to the disk memory means, each for merging records of blocks which are transferred to the first processor from the disk memory means into blocks of merged records, by merging at any time a block of each file of a plurality of files; means, connected to the disk memory means and to the first processors, for transferring from the disk memory means to each first processor a different plurality of the sorted files by transferring the blocks of each sorted file sequentially a block at a time, each file of a plurality of the sorted files transferred to any first processor at any times as part of the merging of the plurality of the sorted files being a different file from the files of the other pluralities of the sorted files transferred to the other first processors; a second processor, connected to the first processors, for merging blocks of the merged records transferred thereto from the first processors in parallel with merging of records into as-yet transferred blocks of the merged records at the first processors; means connected to the first processors and to the second processor, for transferring the blocks of the merged records a block at a time from each of the first processors to the second processors; and means, connected to the second processor and to the disk memory means, for storing the records merged at the second processor in an output file on the disk memory means.

Claim 16

The apparatus of claim 9 wherein the means for transferring the blocks of the merged records comprise means, connected to the first processors, for transferring the blocks of the merged records a block at a time from every first processor to the second processor; and wherein the second processor comprises a processor, connected to the means for transferring the blocks of the merged records, for merging the transferred blocks of the merged records a block at a time from every first processor.

Claim 19

The method of claim 11 wherein the step of storing in a temporary file comprises the steps of: transferring a plurality of sorted segments from a plurality of the first processors to a fourth processor; merging at the fourth processor into a large sorted segment the records of a plurality of the sorted segments each transferred thereto from a different first processor; and storing each large sorted segment in a temporary file on a disk memory.

Claim 20

The method of claim 11 in a multiprocessor system wherein the plurality of first processors comprises a plurality of non-overlapping sets of first processors, wherein the step of storing in a temporary file comprises the steps of: transferring from the first processors of each set to a different fourth processor the sorted segments sequentially a block at a time of one segment from each first processor of the set; merging at each fourth processor into a large sorted segment the records of blocks of a plurality of sorted segments one transferred thereto from each first processor of the set, sequentially one block of each sorted segment at a time, to obtain at each fourth processor at least one large sorted segment; and storing each large sorted segment in a temporary file on a disk memory of the at least one disk memory.

Claim 21

The method of claim 11 wherein the step of transferring the merged records comprises the step of transferring the merged records a block at a time from each second processor to the third processor; and wherein the step of merging at the third processor comprises the step of merging at the third processor the merged records transferred to the third processor from each second processor a block from each second processor at a time.

Claim 22

A multiprocessor apparatus for storing an input file, comprising: disk memory means for storing files including the file having a plurality of segments each having a plurality of different records; a plurality of first processors, connected to the disk memory means, each for sorting a segment at a time the records of each segment transferred to the first processor from the disk memory means, to obtain sorted segments each having a sequence of a plurality of contiguous blocks of different sorted records; means, connected to the disk memory means and to the first processors, for transferring from the input file a different at least one segment a segment at a time to each first processor, each segment of the input file transferred to any first processor at any times as part of the sorting of the input file segments being a different segment from the segments of the file transferred to the other first processors; means, connected to the disk memory means and to the first processors, for storing each sorted segment in a temporary file on the disk memory means; a plurality of second processors, connected to the disk memory means, each for merging the records of blocks transferred to the second processor from the temporary file, a block of each segment of a plurality of segments transferred to each second processor from the temporary file at a time; means, connected to the disk memory means and to the second processors, for transferring from the temporary file to each second processor a different plurality of the sorted segments sequentially a block of any one segment at a time; a merging processor, connected to the second processors, for merging records transferred thereto from the second processors; means, connected to the merging processor and to the second processors, for transferring the merged records from the second processors to the merging processors, and means, connected to the merging processor and to the disk memory means, for storing the records merged at the merging processor in an output file on the disk memory means.

Claim 23

A multiprocessor apparatus for storing an input file, comprising: disk memory means for storing files including the file having a plurality of segments each having a plurality of different records; a plurality of first processors, connected to the disk memory means, each for sorting a segment at a time the records of each segment transferred to the first processor from the disk memory means, to obtain sorted segments each having a sequence of a plurality of contiguous blocks of different sorted records; means, connected to the disk memory means and to the first processors, for transferring from the input file a different at least one segment a segment at a time to each first processor, each segment of the input file transferred to any first processor at any times as part of the sorting of the input file segments being a different segment from the segments of the file transferred to the other first processors; means, connected to the disk memory means and to the first processors, for storing each sorted segment in a temporary file on the disk memory means; a plurality of second processors, connected to the disk memory means, each for merging the records of blocks transferred to the second processor from the temporary file, a block of each segment of a plurality of segments transferred to each second processor from the temporary file at a time; means, connected to the disk memory means and to the second processors, for transferring from the temporary file to each second processor a different plurality of the sorted segments sequentially a block of any one segment at a time; a merging processor, connected to the second processors, for merging records transferred thereto from the second processors; means, connected to the merging processor and to the second processors, for transferring the merged records from the second processors to the merging processors, and means, connected to the merging processor and to the disk memory means, for storing the records merged at the merging processor in an output file on the disk memory means.

Claim 24

The apparatus of claim 15 wherein the means for storing in a temporary file comprise: a third processor, connected to the first processors, for merging into a large sorted segment the records of a plurality of sorted segments each transferred thereto from a different first processor; means, connected to the third processor and to the first processors, for transferring a plurality of sorted segments from a plurality of the first processors to the third processor; and means, connected to the third processor and to the disk memory means, for storing each large sorted segment in the temporary file on the disk memory means.

Claim 25

The apparatus of claim 15 wherein the plurality of first processors comprises a plurality of non-overlapping sets of first processors, and wherein the means for storing in a temporary file comprise: a plurality of third processors, connected to the first processors, each for merging into a large sorted segment the records of blocks of a plurality of sorted segments each transferred to the third processor from a different first processor sequentially one block of each sorted segment at a time, to obtain at each third processor at least one large sorted segment; means, connected to the third processors and to the first processors, for transferring from the first processors of each set to a different third processor the sorted segments sequentially a block at a time of one segment from each first processor of the set; and means, connected to the third processors and to the disk memory means, for storing each large sorted segment in the temporary file on the disk memory means.

Claim 26

The apparatus of claim 15 wherein the means for transferring the merged records comprise means, connected to the merging processor and to the second processors, for transferring the merged records a block at a time from each second processor to the merging processor, and wherein the merging processor comprises a processor, connected to the means for transferring the merged records, for merging records transferred to the merging processor from the second processors a block from each second processor at a time.