Can someone help me understand cache conscience radix sort? (excerpt from journal article attached)
Article:
CC-Radix: a Cache Conscious Sorting Based on Radix sort
============================================================================== (IEEE 2003)
I'm trying to figure out what the author means by this section:
Explanation of CC-Radix For clarity reasons, we explain the recursive version of CC-Radix sort as shown in Figure 3. However, we use the iterative implementation of CC-Radix for the evaluations in this paper because it is more efficient. The parameters of CC-Radix are bucket, which is the data set to be sorted, and b, which is the number of bits of the key that still have to be sorted. Constant b is explained below.
CC-Radix(bucket, b)
￼if fits in cache (bucket) then
Radix sort(bucket, b )
￼￼￼￼￼￼else
sub-buckets = Reverse sorting(bucket, )
for each sub-bucket in sub-buckets
CC-Radix(sub-bucket, )
endfor
￼￼￼￼￼endif
end
Figure 3. Pseudocode of CC-Radix The algorithm starts by checking whether the data struc- tures to sort bucket fit in cache level Li. Those data struc- tures are vectors S and D and the counter vectors C, one for each of the digits of the key. If so, CC-Radix calls Radix sort. If the data structures do not fit in cache level , the algorithm partitions that bucket into sub-buckets by sorting the bucket by the most significant digit using the counting algorithm (explained above). 603
Here, we call this process of partitioning, Reverse Sorting, and it takes into account the computer architecture of the machine. For each sub-bucket, the CC-Radix sort is called again. Note that the first call to the routine processes the com- plete data set. Further calls to the routine process sub- buckets. Note also that certain subsets of the data may need more Reverse sorting calls than others depending on the data skew.
Now, we explain the details of Reverse sorting and the sizing of the parameters of Radix sort. Reverse sorting. After each call of Reverse sorting, the number of digits that remain to be sorted for a specific sub- bucket is decremented by one.
I don't understand the "Reverse Sorting" part of this - how is that supposed to work?
I know this is a long shot, but I'm really stuck on what they mean. Any help is appreciated! 705