Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioniii [2012/02/26 23:28] – [The Problem] mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioniii [2012/02/27 03:25] (current) – [Designing the Algorithm] mugabej
@@ Line 17: / Line 17: @@
 ==== Designing the Algorithm ====
+=== Algorithm ===
+>>>>>>>>>>>>>When d<sub>i</sub> needs to be brought into the cache
+>>>>>>>>>>>>>>>>>>>>evict the item that is needed the farthest into the future
+  * This algorithm is called the //Farthest-in-Future Algorithm//
+=== Analysis ===
+  * A //reduced schedule//: With this schedule, a item d is brought into the cache in a step //i// only if a request to d has been made during the step //i// and d is not already in the cache. This schedule does the minimal work necessary in a given step.
+  * For a schedule that is not reduced, an item d can be brought into the cache even if there was no request fro d in step i
+  * Let S be a schedule that is not reduced:
+    * For a reduction of S(let's call it S**), when S brings in an item d that has not been requested in step i, S** pretends to bring it into the cache but doesn't actually do it, instead, it leaves it in the main memory.
+    * S** brings d into cache only in the next step j after which d is requested
+    * So, the cache miss incurred by S** in step j can be charged to the earlier cache operation performed by S in step i, when it brought it in d.
+    * Thus S** is a reduced schedule that brings in at most as many items as the schedule S
+  * Proving optimality of Farther-in-Future:
+    * Let S<sub>FF</sub> be a schedule produce by the Farthest-in-Future algorithm
+    * Let S* be the schedule that incurs the minimum possible number of misses
+    * -->Let S be a reduced schedule that makes the same eviction decisions as S<sub>FF</sub> through the first j items in the sequence, for a number j
+    * -->Then there's a reduced schedule S' that makes the same eviction decisions as S<sub>FF</sub>  through the first j+1 items, and incurs no more misses than S does.
+    * S<sub>FF</sub>  incurs no more misses than any other schedule S* and hence is optimal
+-->-->-->Proof: Course book, page 135-36
+\\
+\\
+  * The caching algorithm can be extended to deal with eviction decisions without knowing the future
+  * Caching algorithms under this requirement are variants of the //Least-Recently-Used(LRU) Principle which proposes eviction on an item from the cache that was referenced //longest ago//.\\
+\\
+I give this section a 7/10.