Method for avoiding cache misses during external tournament tree replacement sorting procedures

In a CPU having a main memory, a new use for a line-oriented cache coupling said memory for sort string generation of m records while minimizing the number of reference misses per record to said cache, said sort string generation being manifest as a nested ordering of keys of said records, comprising the steps of:

• (a) sizing and writing maximal sets of sub-tree nodes of a nested ordering of subsets resident in main memory into counterpart cache lines, said subsets being ones of m/s such subsets of s keys;
• (b) during a first pass, until said m/s subsets are exhausted, repeatedly calling m/s subsets of keys from main memory into cache and arranging each said subset into a partial nested ordering thereof including prefetching from main memory a cache line formed from a sub-tree of ancestor nodes immediate to the cached node selected for ordering, and writing said selected node to main memory;
• and
• (c) during a second pass, where t<s, repeatedly executing a t-way replacement selection merge in the cache from among at least one key selected from each of t nested orderings of said subsets resident in main memory until said m/s orderings are exhausted.

In a CPU having a main memory for storing program sequences and records, an LRU-managed cache coupling said memory, and means responsive to program sequences for accessing the contents of said main memory and said cache such that

• (1) upon a main memory location being read and its contents being concurrently stored in cache, further read references to the main memory location being routed to the cache, and
• (2) upon a main memory location being written, the same contents being concurrently written into cache,
• a new use for the LRU-managed cache for generation of sort strings of m records while minimizing the number of cache reference misses per record,
• said m records being initially stored in main memory,
• said sort string generation being manifest as a nested ordering of keys of the records,
• said method comprising steps of:
• (a) sizing and writing maximal sets of sub-tree nodes of a nested ordering of subsets resident in main memory into counterpart cache lines, said subsets being ones of m/s such subsets of s keys;
• (b) during a first pass, until m/s subsets have been exhausted, repeatedly calling m/s subsets of keys from main memory into cache and arranging each said subsets into a partial nested ordering thereof, including prefetching from main memory a cache line formed from a sub-tree of ancestor nodes immediate to the cached node selected for ordering, and writing said selected node to main memory;
• and
• (c) during a second pass, where t<s, repeatedly executing a t-way replacement selection merge in the cache from among at least one key selected from each of t partial nested orderings of the subsets resident in main memory until m/s such orderings become exhausted.

In a data processing system for performing an external selection tree replacement sort of a plurality of records, said system having a main memory and a line-oriented cache coupled to said memory, said selection tree having one or more sets of sub-tree nodes, an apparatus for minimizing the number of cache reference misses per record during said sort, said apparatus comprising:

• memory partition means in said main memory for sizing and writing into counterpart cache lines one or more said sets of sub-tree nodes such that no more than one node in each said cache line has a parent node in another cache line;
• selection means in said cache for identifying the cached sub-tree node having the minimum key within a sub-tree and for labeling said node as the replacement node;
• and
• prefetching means connected to said selection means for prefetching the cache lines containing ancestor nodes of said replacement node in response to identification of said replacement node.