Hi All,

I've been thinking on how to implement a zoned CART; and I think I have
found a nice concept.

My ideas are based on the initial cart patch by Rahul and the
non-resident code of Rik.

For a zoned page replacement algorithm we have per zone resident list(s)
and global non-resident list(s). CART specific we would have a T1_i and
T2_i, where 0 <= i <= nr_zones, and global B1 and B2 lists.

Because B1 and B2 are variable size and the B1_i target size q_i is zone
specific we need some tricks. However since |B1| + |B2| = c we could get
away with a single hash_table of c entries if we can manage to balance
the entries within.

I propose to do this by using a 2 hand bucket and using the 2 MSB of the
cookie (per bucket uniqueness; 30 bits of uniqueness should be enough on
a ~64 count bucket). The cookies MSB is used to distinguish B1/B2 and
the MSB-1 is used for the filter bit.

Let us denote the buckets with the subscript j: |B1_j| + |B2_j| = c_j.
Each hand keeps a FIFO for its corresponding type: B1/B2; eg. rotating
H1_j will select the next oldest B1_j page for removal.

We need to balance the per zone values:
 T1_i, T2_i, |T1_i|, |T2_i|
 p_i, Ns_i, Nl_i

 |B1_i|, |B2_i|, q_i

agains the per bucket values:
 B1_j, B2_j.

This can be done with two simple modifications to the algorithm:
 - explicitly keep |B1_i| and |B2_i| - needed for the p,q targets
 - merge the history replacement (lines 6-10) in the replace (lines
   36-40) code so that: adding the new MRU page and removing the old LRU
   page becomes one action.

This will keep:

 |B1_j|     |B1|     Sum^i(|B1_i|)
-------- ~ ------ = -------------
 |B2_j|     |B2|     Sum^i(|B2_i|)

however it will violate strict FIFO order within the buckets; although I
guess it won't be too bad.

This approach does away with explicitly keeping the FIFO lists for the
non-resident pages and merges them.

Attached is a modification of rik his non-resident code that implements
the buckets described herein.

I shall attempt to merge this code into the Rahuls new cart-patch-2 if
you guys don't see any big problems with the approach, or beat me to it.

Kind regards,

-- 
Peter Zijlstra <a.p.zijlstra@chello.nl>