Looking at the access patters of the studied applications
and their working sets, we observe:
Several of the studied applications
have periodic access patterns.
For example, in fig. 1 we
clearly see that the LU application
has an initialization phase and six periods
where LU accesses the same pages over and over again.
Some other applications,
like the BT (fig. 3),
MG (fig. 4), and SP
(fig. 5) also have periodic access patterns.
It seems that these applications access the same pages over and over
again.
Most applications
make long sequential accesses.
For example, in fig. 1 we see that the LU applications
accesses several pages in ascending order during some phases,
and in descending order during other phases.
Similar observations can be made for the
BT (fig. 3),
MG (fig. 4), SP
(fig. 5), and
XLATR (fig. 8)
applications.
Although other applications, like GCC and ESIM, do not seem to make
long sequential accesses,
careful observations of fig. 14(b),
and fig. 16(c), also reveals that these applications
make long sequential accesses to some of their data as well.
Working set sizes may change rapidly.
Several of the applications
depict abrupt changes in the
size of their working set.
For example, fig. 1 shows
that most of the time the working set size of LU is
around 600 pages; however, during short time intervals
it may rise as high as 4000 pages - an order
of magnitude increase.
In most cases, between those abrupt working set changes, the
application accesses a small number of (usually the same)
pages. It is interesting to note that none of our examined
applications depicts smooth changes between working sets.
Applications move between different working sets so rapidly,
that these moves appear as spikes in figures
1 to 5.
Applications that appear to have no regularity in the access
patterns at all, may show very regular access patterns when viewed
at the appropriate granularity.
For example, the N-BODY simulation seems to have little locality
at first glance as figure 2 indicates.
Although the N-BODY simulation has clear preference to two subsets of its pages
(indicated by the two dark parallel stripes), there seems to be no regularity
in accessing these pages. In search of any hidden regularity in
the application, we ``zoomed'' in the access patterns
as follows: we marked the accessed pages in intervals that are
128K references long, and plotted the results in figure 13(b).
To allow the appropriate viewing granularity, figure 13(b)
plots the access patterns only up to 100 million references.
Dark rectangles and triangles
that cover a part of the figure suggest that the application
prefers a specific subset of its pages during certain time intervals.
However, after the 50th million reference, the application appears to have
no regular access pattern at all.
To see if this is true, we ``zoomed'' in the access patterns
once again as follows:
we marked the accessed pages in intervals that are
1024 references long, and plotted the results in figure 13(c).
We see that a periodic access pattern starts to emerge, with a period
of about 25,000 references long. Similarly, GCC and GZIP seem to have no
regularity in their access patterns.
However, after appropriate zooming shown
in figures 14(b), and 15(b),
regular access patterns start to emerge.
It can be easily seen now, that
GCC and GZIP have clearly identifiable sequential (GCC)
and periodic (GZIP)
access patterns.
It seems that locality of reference and regularity in access
patterns manifest themselves only when viewed at the
appropriate distance.
Database applications may have more locality and regularity,
from what can be seen at a first glance.
For example, the query OO7-Q7 shown in fig.
11 has very regular access pattern: it
makes long sequential accesses
to its data.
On the other hand, the SQL application seems to have little regularity
in its accesses, as shown in fig. 12 and
17(a), and as reported in [4].
To reveal any hidden regular access patterns that may reside in SQL,
we renamed the page numbers as follows: the first page accessed by SQL
was given the name 0, the second page to be accessed by SQL was
given the name 1, etc. Figures 17(b) and 17(c)
plot the page accesses of the SQL application to these re-numbered pages.
We can easily see in figure 17(c) that SQL favors a
specific subset of its pages, giving preference in accessing repeatedly
the same clusters of pages. Simulation results
show that the SQL trace has a significant amount
of locality of reference - much more than what can be seen at a
first glance [2].
Finally, the database benchmark
OO7-T1 (fig. 10)
appears to have no regular access pattern, but this
should be expected, because this benchmark makes a random walk
of the assembly hierarchy.
