Online Algorithms and Competitive Analysis Paging Algorithms вЂў Data brought from slower memory into cache RAM CPU Paging Algorithms вЂў Data brought from slow memory into small fast memory (cache) of size k вЂў Sequence of requests: equal size pages вЂў Hit: page in cache, вЂў Fault: page not in cache Minimizing Paging Faults вЂў On a fault evict a page from cache вЂў Paging algorithm в‰Ў Eviction policy вЂў Goal: minimize the number of page faults Worst case вЂў In the worst case page, the number of page faults on n requests is n. E.g. cache of size 4, request sequence p1 p2 p3 p4 p5 p6 p7 p8 p9 p10 p11 p12 Difficult sequences Cache of size 4, request sequence p1 p2 p3 p4 p5 p6 p7 p8 p9 p10 p11 p12 Sequence is difficult, for one it never repeats pages so it is impossible to have a page hit Compare to optimal p1 p2 p3 p4 p5 p6 p7 p8 p9 p10 p11 p12 p13 вЂ¦ is hard for everyone (i.e. 13 faults) p1 p2 p3 p4 p5 p1 p2 p3 p4 p5 p1 p2 p3 p4 вЂ¦ 8 faults Optimal algorithm knows the future Offline optimum Optimal algorithm knows the future, i.e. offline OPT. Compare online paging strategy to offline paging strategy Competitive Ratio Defined as : sup пЂўI cost of online algorithm on I cost of offline optimum on I Paging вЂў One of the earliest problems to be studied under the online model вЂў Competitive ratio defined by Sleator and Tarjan Competitive Ratio вЂў First appeared in the 1960вЂ™s in search context, e.g. вЂ“ вЂ“ вЂ“ вЂ“ вЂ“ вЂ“ вЂ“ On the linear search problem (Beck, 1964) More on the linear search problem (1965) Yet more on the linear search problem (1970) The return of the linear search problem (1972) Son of the linear search problem (Beck & Beck 1984) The linear search problem rides again (1986) The revenge of the linear search problem (1992) вЂў Shmuel Gal вЂ“ Search Games, Academic Press, 1980 вЂ“ The Theory of Search Games and Rendezvous (with Steve Alpern), Kluwer Academic Press, 2002 Paging Algorithms вЂў Least-Recently-Used (LRU) вЂў First-In-First-Out (FIFO) вЂў Flush-When-Full (FWF) Classes of Paging algorithms вЂў Lazy Algorithms: LRU and FIFO вЂў Marking Algorithms: LRU and FWF Paging вЂў Competitive analysis not always satisfactory, e.g. LRU вЂњas good asвЂќ FWF вЂў Real life inputs well understood and characterized (temporal + spatial locality) Goal: derive from first principles a new measure that better reflects observations in practice Theory 1. Commonly studied under competitive ratio framework 2. Worst case analysis 3. Marking algorithms optimal 4. In practice LRU is best 5. LFD is offline optimal 6. Competitive ratio is k 7. User is malicious adversary 8. No benefit from lookahead Systems 1. Commonly studied using fault rate measure 2. Typical case analysis 3. LRU and friends is best 4. LRU is impractical 5. Huh? 6. Competitive ratio is 2 or 3 7. User is your friend 8. Lookahead helps Fix the Theory-Practice disconnect 1. Make both columns match How? вЂў Fix reality or вЂў Fix the model A more realistic theoretical model is likely to lead to practical insights Previous work 1. Disconnect has been noted before. 2. Intense study of alternatives, viz. 1. 2. 3. 4. 5. 6. 7. 8. Borodin and Ben David Karlin et al. Koutsoupias and Papadimitriou Denning Young Albers et al. Boyar et al. Sleator and Tarjan + many others Theory: competitive ratio of paging algorithms вЂў k for LRU, FIFO, and FWF вЂў Thus LRU, FIFO, and FWF equally good вЂў Lookahead does not help Practice: вЂў вЂў вЂў LRU never encounters sequences with competitive ratio bigger than 4 LRU better than FIFO and much better than FWF Lookahead helps Previous work 1. Partial separation : вЂў вЂў вЂў вЂў вЂў Access graph model. Borodin, Raghavan, Irani, Schieber [STOC вЂ�91] Diffuse adversary. Koutsopias and Papadimitrou [FOCS вЂ�94] Diffuse adversary. Young [SODA вЂ�98] Accommodating ratio. Boyar, Larsen, Nielsen [WADS вЂ�99] Relative worst order ratio. Boyar, Favrholdt, and Larsen [SODA вЂ�05] Previous work вЂў вЂў Concave Analysis. Albers, Favrholdt, Gielet [STOC вЂ�02] LRU в‰ certain marking algorithms Adequate Analysis. Pangiotou, Souza [STOC 06] + many others. See survey L-O, Dorrigiv [SIGACT News вЂ™05] None provide full separation between LRU and FIFO and/or FWF Online motion planning 1. Commonly studied under competitive ratio framework 2. Worst case analysis 3. Continuous curved motions 4. Perfect scans 5. Flawless detection 6. No error in motion 7. Architects are your enemy Robotics 1. Commonly studied using distance & scan cost 2. Typical case analysis 3. Piecewise linear 4. Scanning error 5. High detection error 6. Forward & rotational lag 7. Architects are your friend вЂњArchitects are your friendвЂќ Most of the time, anyhow. Alternatives вЂў вЂў вЂў вЂў вЂў вЂў вЂў вЂў вЂў вЂў вЂў Turn ratio Performance Ratio Search Ratio Home Ratio Travel Cost Average Ratio Effective Ratio Smooth Analysis Concave Analysis Bijective Analysis Others Performance Ratio Defined as : maxp { length of search from s to p } maxq { length of path from s to q } вЂў general idea: focus on distant targets searches, those should be efficient вЂў allows high inefficiency for targetвЂ™s near-by Search Ratio Defined as : length of search from s to target p sup shortest off-line search from s to p пЂўp вЂў finer, fairer measure than competitive ratio вЂў many on-line вЂњunsearchableвЂќ scenarios suddenly practicable, e.g. trees Search Ratio Example: Searching for a node at depth h in a complete binary tree with unit length edges Competitive ratio = O(2h / h) Search ratio = O(1) Home Ratio Defined as : sup пЂўp length of search from s to target p shortest path from s to p where the position of p is known вЂў e.g. target has radioed for help, position known, shape of search area unknown Home Ratio вЂў Surprisingly, in some cases is as large as competitive ratio, e.g. street polygons вЂў [L-O, Schuierer, 1996] Travel Cost Defined as : sup { length of search from s to target p } пЂўp вЂў unnormalized вЂў similar to standard algorithmic analysis Average Ratio Defined as : avg sup пЂўP пЂўp length of search from s to target p shortest path from s to p вЂў Searching on the real line is 4.59 competitive on the average вЂў Doubling is 5.27 competitive Effective Ratio Defined as : ОЁ ratio + F(cost of computing solution) where ОЁ С” { Competitive, Performance, Turn, Search, Home, Average, etc.} вЂў Function F reflects the difference in computational and navigational costs вЂў Sensible adjustments n, n2, i.e. F(soltвЂ™n) = time / n2 Other considerations вЂў Robustness вЂў navigational errors вЂў detection errors (revisit area) вЂў Known probability densities of target location вЂў Time sensitive considerations Example вЂў Rescue in high seas (man overboard) вЂў High detection error вЂў Known probability density from ocean currents data вЂў Time sensitive (person must be found within 4 hours in North Atlantic) Search and Rescue (SAR) вЂў Current coast guard strategy вЂў scan high probability area вЂў when done . . . scan again вЂў if several vessels available, rescan Bijective Analysis cost ОЈn = {Пѓ1,Пѓ2,вЂ¦,Пѓ10}: the set of all possible input sequences of length n A(Пѓ) B(Пѓ) 5 7 3 9 7 5 3 7 5 7 6 7 4 3 10 7 6 6 8 10 Bijective Analysis cost Aв‰¤B Bв‰¤A A<B A(Пѓ) B(Пѓ) 5 7 3 9 7 5 3 7 5 7 6 7 4 3 10 7 6 6 8 10 Bijective Analysis A(Пѓ) Competitive ratio of A: 9 Competitive ratio of B: 4 5 7 3 9 7 5 3 7 5 7 OPT(Пѓ) 3 2 4 1 3 4 2 5 2 3 B(Пѓ) 6 7 4 3 10 7 6 6 8 10 Strict separation is complex Theorem If the performance measure does not distinguish between sequences of the same length, then no such separation exists ОЈ1 ОЈ2 ОЈ3 ОЈ* Input sequences Proof We prove strong equivalence of all lazy marking algorithms. I.e. given two marking algorithms A1 and A2, there is a one-to-one correspondence b() between inputs such that the performance characteristics of A1(I) are identical to A2(b(I)). Proof A Пѓ1 Пѓ2 Пѓ3 Пѓ1 Пѓ4 Пѓ4 Пѓ2 B Пѓ1 Пѓ2 Пѓ3 Пѓ1 Пѓ4 Пѓ4 Пѓ3 map any Пѓ2 in AвЂ™s sequence to Пѓ3 in BвЂ™s sequence Partitioning Input Space вЂў We need a natural model to partition space. How? ОЈ1 ОЈ2 ОЈ3 ОЈ* Input sequences Not all inputs are equal вЂў Adversarial model is wrong model for paging. вЂў The user is not out to get you (contrast this with crypto case). вЂў Compilers go to great lengths to preserve locality of reference. вЂў Designers go to great lengths to create cache friendly (conscious) algorithms. Updated model Competitive ratio Friendly models: вЂў Fault model, Torng [FOCS вЂ™95] вЂў Concave analysis, Albers et al. [STOC вЂ™02] ALG(I) nice(I) Cooperative ratio вЂў Agreement between user and algorithm about inputs which are: вЂ“ вЂ“ вЂ“ вЂ“ likely common good important Cooperative ratio вЂў Badly written code (not cache conscious) вЂ“ (Rightly) considered the programmerвЂ™s fault вЂ“ Paging strategy not responsible for predicting non-standard paging behaviour вЂў Well written code (cache conscious) вЂ“ Code can rely on well defined paging behaviour to produce better code (e.g. I/O model, cache oblivious model) Friendly models вЂў Torng fault model doesnвЂ™t fully separate пЃЊ вЂў Albers et al. concave analysis doesnвЂ™t either пЃЊ вЂў Bijective + concave analysis separates пЃЉ Concave analysis f( ): an increasing concave function Definition A request sequence is consistent with f if the number of distinct pages in any window of size n is at most f(n) Intuition Not too many consecutive newly requested pages, i.e. locality of reference Proposed by Albers et al. [AFG05], based on DenningвЂ™s working set model Subpartitioning of Input Space вЂў Subsets compatible with f( ) ОЈf3 ОЈ 4 ОЈ 5 f f Input sequences ОЈ* Bijective analysis Theorem. LRU в‰¤f,b A for all paging algorithms A Proof. Construct a continuation of b() such that b(Пѓв€™r)= b(Пѓ)в€™rвЂ™ and LRU(Пѓв€™r) в‰¤ A(b(Пѓв€™r)) Corollary. avg(LRU) в‰¤ avg(A) Strict separation Theorem For any given paging algorithm A there exists f such that A >f,avg LRU i.e. LRU is unique best [SODA вЂ™07] Strict separation Theorem For any algorithm A there exists f such that A >f,avg LRU Proof. We want to show avg(A) > avg(LRU). I.e. ОЈПѓ A(Пѓ) > ОЈПѓ LRU(Пѓ) Use double counting technique: Compute the number of faults at time i across all sequences, then add for i = 1..n. Strict separation ОЈПѓ A(Пѓ) > ОЈПѓ LRU(Пѓ) [sum by rows] Compute the number of faults at time i across all sequences, then add for i = 1..n. [sum by columns] This shows A(i, Пѓ) в‰Ґ LRU(i, Пѓ). Finally we exhibit one sequence Пѓ for which A(i, Пѓ) > LRU(i, Пѓ). Other results вЂў вЂў Lookahead: the next L items in the list are known in advance It does not improve competitive ratio of any of the standard strategies Theorem LRU with lookahead L is strictly better than LRU with lookahead LвЂ™ for all L > LвЂ™ Applications to other problems вЂў Similar open problem for List Update: вЂњAn important open question is whether there exist alternative ways to define competitiveness such that MTF and other good online algorithms for the list update problem would be competitiveвЂњ [Martinez and Roura]. вЂў Bijective analysis separates MTF from rest Applications to other problems вЂў вЂў вЂў Leads to better compression results for Burrows-Wheeler based compression BWT reorders text in a way that increases repetitions in text Reordering is compressed using MTF Applications to other problems Observation: BWT permutations have high locality of reference вЂў Use list update algorithms which are designed under locality of reference assumptions, instead of adversarial worst case inputs вЂў Leads to better compression Cooperative ratio for motion planning вЂў вЂў вЂў Robot must search efficiently scenes which are вЂњreasonableвЂќ Can perform somewhat worse in вЂњunreasonableвЂќ scenes Leads to adaptive-style analysis. E.g. define niceness measure of office floor plan in terms of orthogonality of scene, number of rooms/corridors, size of smallest relevant feature, etc. Other results вЂў It leads to deterministic algorithms that outperform randomized ones in the classical model. single bad case simple cases Under competitive ratio algorithm must tend to single bad case, even if at the expense of the simple case Randomized algorithm can toss a coin and sometimes do one, sometimes do the other Bijective analysis naturally prefers the majority of good cases Conclusions вЂў Introduced refined measurement technique for online analysis вЂў Resolved long standing open problem: LRU is unique optimum вЂў Bridged theory-practice disconnect вЂў Result applicable to вЂ“ List update (MTF is unique optimum) вЂ“ BWT compression вЂ“ Motion planning вЂў Leads to new cooperative analysis model

1/--страниц