close

Вход

Забыли?

вход по аккаунту

?

Online Algorithms and Competitive Analysis

код для вставкиСкачать
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
Документ
Категория
Презентации
Просмотров
10
Размер файла
696 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа