From ted@squall.cis.ufl.edu Sat Nov  6 20:31:40 1993
Received: from squall.cis.ufl.edu by SHASHA.CS.NYU.EDU (5.61/1.34)
	id AA12935; Sat, 6 Nov 93 20:31:38 -0500
Received:  by squall.cis.ufl.edu (5.61ufl/4.12)
	id AA02442; Sat, 6 Nov 93 20:31:33 -0500
Date: Sat, 6 Nov 93 20:31:33 -0500
From: "Ted Johnson" <ted@squall.cis.ufl.edu>
Message-Id: <9311070131.AA02442@squall.cis.ufl.edu>
To: shasha@SHASHA.CS.NYU.EDU
Status: RO

Dennis, This time I made a tar file of the figures and compressed it.
Then, I uuencoded it and broke the .uue file into 2 pieces, which follow.
do the opposite to get the figures.

1) zcmp.eps: This compares A1in-only and A1out-only
2) irlg5-2q.eps: investigate the effect of the size of A1in on hit rate
3) irlg8-2q.eps: "   "
4) zalgcp5: compare all algorithm with zipf input
	>>what is AQ (or is it AO, I can't quite read it)
5) zalgcp5: "    "
6) hitvhhot.eps: Show why 2Q, LRU/2 work (hit rates highest on hot items)
	>>not knowing anything, it looks as if percentile increases as heat
	>>does and yet the hit rate seems to decrease.
	>>need better labelling.
7) lc5_20.eps: I wanted to investiate responsiveness. I ran the algorithms for
   1,000,000 zipf references, then made a random permutation of the
   probabilities assigned to the items (so its a radical change of
   locality). This chart shows hit rates as a function of time after 
   the permutation.
	>>interesting that LRU/2 is smoother until 2Q 50%.
8) lc8_20.eps: "   "
9) scan2q10.eps: The next charts examine algorithm performance
   when the input contains scans.  1/3 of references are scans, 
   2/3 are zipf.  this particular chart investigates the sensitivity
   to the size of A1in (not much).
10) scan10_8.eps: compare algorithm performance
	>> is this a fair comparison for LRU/2 (how did you deal with its
	>> tunables). The hit ratios are very low. Is that ok?
11) scan20_5.eps: "  "
12) spar10_8: look at degredation of hit rate as compared to zipf-only
13) sper20_5: "  "
14) winhit.eps: run the algorithms on the windows traces. 
    I modified LRU/2 to use a FIFO buffer, as we discussed,
    and used the FIFO size that gave the best possible hit rate
    (there was an improvement) (to be replaced by the DB2 traces).
	>> great.
15) teopool.eps: the two-pool experiment.
	>> I forget, what does two-pool mean.

I tried to use a differnet font - thats probably causing problems.

	Ted

From ted@squall.cis.ufl.edu Wed Nov 10 14:28:58 1993
Received: from squall.cis.ufl.edu by shasha.cs.nyu.edu (5.61/1.34)
	id AA04667; Wed, 10 Nov 93 14:28:54 -0500
Received:  by squall.cis.ufl.edu (5.61ufl/4.12)
	id AA04686; Wed, 10 Nov 93 14:28:49 -0500
Date: Wed, 10 Nov 93 14:28:49 -0500
From: "Ted Johnson" <ted@squall.cis.ufl.edu>
Message-Id: <9311101928.AA04686@squall.cis.ufl.edu>
To: shasha@SHASHA.CS.NYU.EDU
Status: RO

Dennis,

Use the \special command to include postscript figures in a latex document:

---------------------------  cut -----------------------------------

\documentstyle[fullsize]{article}
\begin{document}

\begin{figure}
\vspace{3.8in}
\special{psfile=zalgcp5.eps  hscale=60 vscale=60 hoffset=0 voffset=-40}
\caption{compare algorithms with zipf input}
\label{vinsert.fig}
\end{figure}

\end{document}

---------------------------  cut -----------------------------------

the scaling is in percent, the offset in points (72 points = 1 inch).
this will print the figure on the page, but its not positioned well.
(I grabbed the settings from another document).
I can finetune the positionings, etc., when its my turn to edit.

For the comments on the figures:

zalgcp5
  A0 is the algorithm that places the B-1 hottest items in B-1 buffers,
and uses the last buffer to handle misses.
Its the optimal algorithm, thus the one to compare for an upper bound.
cite the following:

@book{CD73,
author={E.G. Coffamn and P.J. Denning},
title={Operating System Theory},
publisher={Prentice-Hall},
year=1973
}

hitvshot
The optimal algorithm is to lock the hottest items into the buffers,
and always miss on the cold items.  All algorithms have a high hit rate
on the hot items (where it counts) and a low hit rate on the cold items
(where it doesn't count).  2Q has the highest hit rate on the
hottest items, which it gains by permitting a lower hit rate on the cold items.
thats why 2Q does better overall.  LRU/2 fals inbetween.

lc5_20.eps
  This chart shows that while decreasing the size of A1 gives you a better
long-term hit rate, you sacrifice responsiveness. the hit rates at 0%
are the hit rates after 1,000,000 zipf references, and before the permutation.
when |A1|=|Am|/2, you are almost as responsive as LRU/2, but you have
a higher long-term hit rate.

scan10_8.eps
  THe comparison with LRU/2 is fair, since |A1in|=0 (1) for both algorithms.
Real traces have short bursts of locality, which is where the
tuning comes in.
The hit rates are low because you have little hope of getting hits on 1/3
of the references.  the hit rate is good on the remaining 2/3 of
the zipf references  (remember, 1/3 of references are scan references)

twopool.eps
  The idea here is to look at the buffer performance if you're
referencing data through an index.  the small pool (100) is the index pages,
the large pool are the data pages (10000).  The setup and parameters
are from the O'neils paper.  its a good candidate to omit
if we're tight on space.


	Ted

