1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215
//! MLCR: Machine-Learning-based Cache Replacement //! //! MLCR trains a neural network to "guess" how long time will pass before the cache block is //! accessed again. In other words, it provides a qualified guess to approximate the ideal Bélády's //! algorithm without a time machine. //! //! MLCR is slow, because it needs to train a neural network, but in many cases, the added //! precision pays off by greatly reducing the number of cache misses. As such, it should only be //! used when the cached medium is significantly slower than training the network (e.g. hard disks or //! internet downloads). extern crate nn; use nn::NN; use std::{cmp, f64}; use std::collections::{BinaryHeap, HashMap}; /// A clock tick count. /// /// Every touch (i.e. read) increments the _clock_ yielding a new _tick_. This tick is roughly used /// as a measure for the time passed (the actual time is irrelevant as it doesn't change the state /// of the cache). /// /// This tick count is used in the neural network model for the next hit prediction. type Tick = u32; /// The ID of a cache block. /// /// The ID uniquely identifies a particular cache block inhabitant. It is used in the prediction /// model and should thus be chosen carefully as representing the inner data (e.g. the disk /// address) in order to achieve least cache misses. pub type Id = u64; /// A cache block. /// /// This represents the state of a particular cache block. struct Block { /// The two last times the block was used. last_used: [Tick; 2], /// The tick where the block was added. instated: Tick, /// The number of times the block has been touched. times_used: u32, } impl Block { /// Convert the block data into a vector. fn as_vec(&self, id: Id) -> Vec<f64> { vec![id as f64, self.instated as f64, self.last_used[0] as f64, self.last_used[1] as f64, self.times_used as f64] } } /// A next usage prediction. /// /// This contains a prediction produced by the neural network, estimating when is the next tick, /// the block will be touched. #[derive(PartialEq)] struct Prediction { /// The ID of the block we're predicting. id: Id, /// The prediction produced by the neural network. /// /// Note that this does not represent a tick, but rather a monotone function thereof. prediction: f64, } impl cmp::Ord for Prediction { fn cmp(&self, other: &Prediction) -> cmp::Ordering { if self.prediction < other.prediction { cmp::Ordering::Less } else { cmp::Ordering::Greater } } } impl cmp::PartialOrd for Prediction { fn partial_cmp(&self, other: &Prediction) -> Option<cmp::Ordering> { Some(self.cmp(other)) } } impl cmp::Eq for Prediction {} /// An iterator over the coldest (best candidates for replacement) to hotter cache objects. /// /// This iterators from the objects predicted to be used in the farthest future to the nearest /// future. /// /// In other words, this goes over the best to worse candidates for replacement, trimming, or /// clearing. pub struct ColdIter { /// A binary heap over the predictions ordered by distance into the future. heap: BinaryHeap<Prediction>, } impl Iterator for ColdIter { type Item = Id; fn next(&mut self) -> Option<Id> { self.heap.pop().map(|Prediction { id, .. }| id) } } /// A learning cache tracker. /// /// This keeps track of cache blocks. /// /// A cache block represents some data, which is not managed by the cache tracker. The cache block /// is said to be _touched_ when this data is used in some way. /// /// The _ideal replacement_ is the block which is used in the most distant future. As this is not /// possible to know in advance, we make a prediction or a _approximate ideal replacement_, which /// is based around various data points of the block such as the time of the last uses, or the /// number of touches. /// /// The aim of the cache tracker is to provided _approximate ideal replacements_. Numerous /// algorithms for making these predictions exists (examples are LRU, PLRU, LFU, MFU, MRU, ARC, /// etc.), but MLCR uses an approach which is radically different: It feeds the data points into a /// neural network and lets this estimate the tick of the next touch. pub struct Cache { /// The blocks in this cache tracker. blocks: HashMap<Id, Block>, /// The neural network mapping blocks to the ticks of next touch. nn: NN, /// The clock. /// /// This increments on every touch. clock: Tick, } impl Cache { /// Tick the clock. fn tick(&mut self) { self.clock += 1; } /// Create a new cache tracker. pub fn new() -> Cache { Cache { blocks: HashMap::new(), nn: NN::new(&[5, 6, 1]), clock: 0, } } /// Touch a cache block. /// /// This should be called whenever the object `id` represents is used (read, written, etc.). /// /// This will train the neural network with the new data. pub fn touch(&mut self, id: Id) { { // Get the block we need. let block = self.blocks.get_mut(&id).unwrap(); // Apply a bijective map from the clock to a float on the range (0,1), which can be // fed to the network. let goal = (self.clock as f64 * 0.01).tanh(); // Train the neural network with the existing data against the clock. self.nn.train(&[(block.as_vec(id), vec![goal])]); // Update the block with last used data. block.last_used[0] = block.last_used[1]; block.last_used[1] = self.clock; // Increment the frequency counter. block.times_used += 1; } // Tick the clock. self.tick(); } /// Insert a new cache block into the cache tracker. pub fn insert(&mut self, id: Id) { self.blocks.insert(id, Block { last_used: [!0; 2], instated: self.clock, times_used: 0, }); } /// Remove a cache block. pub fn remove(&mut self, id: Id) { self.blocks.remove(&id); } /// Get an iterator over blocks from cold to hot. pub fn cold(&mut self) -> ColdIter { // Build a heap over the predictions. let mut heap = BinaryHeap::new(); for (&id, block) in self.blocks.iter() { // Predict the next use. let prediction = self.nn.run(&block.as_vec(id))[0]; println!("{} - {}", id, prediction); // Push the prediction to the heap. heap.push(Prediction { id: id, prediction: prediction, }); } ColdIter { heap: heap, } } /// Get at iterator over blocks to remove to trim the cache tracker to `to`. /// /// Note that this won't remove the blocks, and this should be handled manually with the /// `remove` method. pub fn trim(&mut self, to: usize) -> ::std::iter::Take<ColdIter> { self.cold().take(self.blocks.len() - to) } }