Sorting and merging of files in a multiprocessor

Details Sorting and merging of files in a multiprocessor Sorting and merging of files in a multiprocessor

1986-05-14

1992-01-28

Lee, Thomas C.

Boots, shoes, and leggings

3642481, 364252, 364260, 3642821, 3642831, 3642281, 364230, 364228, 3642283, 3642287, 3642303, 3642304, 3642362, 364DIG1, G06F 722, G06F 724, G06F 706

Patent

active

050848151

ABSTRACT:
In a multiprocessor system (FIG. 1), file sorting and merging operations are broken down into a series of partial-file sorts and partial-file merges which are executed in parallel by a plurality of processors (21-26). In a file sorting operation, an input file processor (24) distributes segments (201) of an input file (200) from disk (34) to a plurality of sort processors (21-23) in a round-robin fashion. Each sort processor sorts records (203) of each received segment according to a key, and stores the sorted segments on disk (35) in a temporary file (220). A merge operation is then performed on the sorted segments, treating each segment as an input file. In a merge operation, a plurality of merge processors (21-23) each retrieve a different plurality of sorted segments block (202)-by-block from the temporary file, merge the records of the retrieved segments, and supply records of the merged segments to an output file processor (26). The output file processor merges the records received from the plurality of merge processors and stores them in an output file (230) on disk (36).

REFERENCES:
patent: 4030077 (1977-06-01), Florence et al.
patent: 4078260 (1978-03-01), Chen et al.
patent: 4210961 (1980-07-01), Whitlow et al.
patent: 4514826 (1985-04-01), Iwata et al.
patent: 4567572 (1986-01-01), Morris et al.
patent: 4583194 (1986-04-01), Cage
N. Takagi and C. K. Wong "A Hardware Sort-Merge System", IBM J. Res. Develop., vol. 29, No. 1, Jan. 1985, pp. 49-67.
S. Todd, "Algorithm and Hardware for a Merge Sort Using Multiple Processors", IBM J. Res. Develop., vol. 22, No. 5, (9/78), pp. 509-517.
S. Even, "Parallelism in Tape-Sorting", Comms. of the ACM, vol. 17, No. 4, (4/74), pp. 202-204.
C. D. Thompson et al., "Sorting on a Mesh-Connected Parallel Computer", Comms. of the ACM., vol. 20, No. 4, (4/77), pp. 263-271.

Affiliated with

Also associated with

Rating

Sorting and merging of files in a multiprocessor does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Sorting and merging of files in a multiprocessor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sorting and merging of files in a multiprocessor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1864674