Method for avoiding cache misses during external tournament tree

Details Method for avoiding cache misses during external tournament tree Method for avoiding cache misses during external tournament tree

1991-12-23

1994-10-11

Kulik, Paul V.

Boots, shoes, and leggings

395425, 364DIG1, 36422281, 3642229, 364243, 3642434, 36424341, 364246, G06F 724

Patent

active

053554787

ABSTRACT:
A method and apparatus for avoiding line-accessed cache misses during a replacement/selection (tournament) sorting process. Prior to the sorting phase, the method includes the steps of sizing and writing maximal sets of sub-tree nodes of a nested ordering of keys, suitable for staging as cache lines. During the sort phase, the method includes the steps of prefetching into cache from CPU main memory one or more cache lines formed from a sub-tree of ancestor nodes immediate to the node in cache just selected for replacement. The combination of the clustering of ancestor nodes within individual cache lines and the prefetching of cache lines upon replacement node selection permits execution of the full tournament sort procedure without the normally-expected cache miss rate. For selection trees larger than those that can fit entirely into cache, the method avoids the second merge phase overhead that formerly doubled the sorting time necessary for larger cache sizes.

REFERENCES:
patent: 3611316 (1971-10-01), Woodrum
patent: 3713107 (1973-01-01), Barsamian
patent: 3931612 (1976-01-01), Stevens et al.
patent: 4090249 (1978-05-01), Chen et al.
patent: 4210961 (1980-07-01), Whitlow et al.
patent: 4417321 (1983-11-01), Chang et al.
patent: 4575798 (1986-03-01), Lindstrom et al.
patent: 4962451 (1990-10-01), Case et al.
patent: 5175857 (1992-12-01), Inoue
patent: 5179699 (1993-01-01), Iyer et al.
patent: 5179717 (1993-01-01), Sato et al.
patent: 5210870 (1993-05-01), Baum et al.
patent: 5224217 (1993-06-01), Zangenehpour
patent: 5274805 (1993-12-01), Ferguson et al.
patent: 5287494 (1994-02-01), Garcia et al.
Knuth, Donald E., "The Art of Computer Programming," vol. 3/Sorting and Searching, 1973, pp. 247-266, Addison-Wesley Publishing Company, Inc.
Tremblay, Jean-Paul et al, "An Introduction to Data Structures with Applications," 1984 by McGraw-Hill, Inc., pp. 678-696.

Affiliated with

Also associated with

Rating

Method for avoiding cache misses during external tournament tree does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for avoiding cache misses during external tournament tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for avoiding cache misses during external tournament tree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1665651