Can someone help me understand cache conscience radix sort? (excerpt from journal article attached)

Question

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). 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!

Answer 1

The naming in the pseudo-code seems to be making things more confusing than they need to be, and it also seems to be glossing over some detail, but here's what I think is going on.

Let's just jump right in on a small example. Suppose we have a data set, the integers 0-7 in binary: $000, 001, 010, 011, 100, 101, 110, 111$. But obviously they're not necessarily given to you in sorted order. Let's say the input is actually: $110, 101, 000, 010, 100, 111, 001, 011$.

If all this data fits in the cache, then you just run normal radix sort. That's the first branch of the if statement. For illustration, lets say that the cache can only hold two elements. Therefore, we end up in the else branch. The "reverse sorting" step splits the input into two sub-buckets based on the most significant bit. So we get two buckets:

$1: (10, 01, 00, 11)$ and $0: (00, 10, 01, 11)$. We recursively call our function on each of these smaller buckets. Since they are smaller, they might now fit inside the cache, and we could run normal radix sort.

So now we're in the recursive call on the first sub-bucket. The input is $1:(10, 01, 00, 11)$. However, our cache size is only 2. Therefore we move into the else branch again. We split the input into $11:(0,1)$ and $10:(1, 0)$. and call the function recursively. Now finally on each of these recursive calls, the input is small enough to fit in the cache, and we run normal radix sort.

The other recursive calls function similarly. Their pseudo-code seems to be missing how the partitions are pieced back together in a cache conscious way. Maybe this is obvious or covered elsewhere in the paper.