Temporal grouping in Streams

I have been working on a modified version of the Irregular Stream Buffer that considers the instruction time between consecutive memory accesses in it's stream definition, i.e. there are twice the average number of memory accesses between two accesses in the same program counter, so a new stream is created and the old one is discarded. Theoretically, this will benefit the program because the buffer will have a steady stream of new information. However, if the algorithm clears out the buffer too often, then the buffer will constantly be re-calibrating and will become inaccurate.

Frailty, thy name is visually intuitive representations of large quantities of arbitrary data

For my internship I have graphed the number of memory addresses that have been accessed by each individual PC (Program Counter), in order to analyze the distribution of accesses between programs. Simply recording the data yields a fairly obtuse bank of data: literally 2 long strings of unreadable numbers. To represent his data in an intuitive manner, I am using 3 different approaches:

1. Sort the PCs by their access frequency (i.e. the total number of accesses) and graph the expansion of the PCs so that the expansion is on the Y axis and the frequency is on the X axis.
2. Create a histogram expressing the expansion v. the number of PCs.
3. Create a cuumulative distribution function (CDF) graphing the PCs sorted by expansion v. the expansion. (This graph will constantly be increasing, so the importance is in the rate of increase.)

Fuzzy fuzzy access streams

In memory access streams there is a topic called "contraction", which refers to the ratio of the number of physical addresses to the number of structural addresses in an Irregular Stream Buffer. (You can read more about the Irregular Stream Buffer here.) A contraction of 1, i.e. having the same number of physical addresses and structural addresses, is best for caching because it means that accuracy will improve and the same thing will never the be cached twice.

Contraction has a close cousin, expansion. Expansion refers to the situation in which there are more structural addresses than physical addresses, so the Stream Buffer ends up having a larger than necessary memory footprint. Contraction refers to the opposite situation: there are more physical addresses than structural addresses, which leads to lost information.

Say we have the access stream
ABCDEF

Now, say we have the following access stream after this one
XBDCEF
This will cause expansion because this second stream will be recognized as a separate stream.

Alternatively, consider this access stream instead
AVWXYZ
This will cause contraction because this second stream will be recognized as a modification of the first access stream (assuming that the stream recognition system is lenient enough)

Give that man some soup

For many memory prefetching algorithms, it is necessary to predict the re-reference interval of a memory access, so that the memory can be moved to the cache before the memory is called for, vastly decreasing memory access time.

Consider the following address stream:

ACDACBBD

In this example, the re-reference interval of D would typically be 4, because there are 4 memory accesses between consecutive accesses of D(I'll get to the reason that I say "typically" in a second). This means that, given the following access stream

ACDACBBDACAC

it would be natural to prefetch D, because, based on the idea that D is accesses every 4 accesses, it would likely be the next address. However, in practice, it has been shown that the next memory access is more likely to be something like BBD. Why is that? Well, we're not quite sure, but studies have shown that prefetching based on the unique re-reference interval, i.e. the number of unique memory accesses between consecutive addresses, produces significantly better results. Under this model, the unique re-reference interval of the first example would be 3, since there are 3 unique memory addresses: A, B, and C. The problem is that keeping track of the data required to find the unique re-reference interval is extremely difficult to do efficiently, so, for the past 2 weeks, I have been researching methods to do this efficiently.

Some background information

I was told by my PI to graph the number of physical memory addresses that are passed through our simulator, and compare these to the structural addresses that these are mapped to. Many of the simulations didn't complete because the files' simpoints needed to be recompiled, so we recompiled the simpoints. To do all of this, we are using a software called Intel PIN tool that is a program through which one can run C++ code with a great deal of control over how the code is run. Simpoints are sets of instructions that are run. So, for example, if we compile 3 simpoints per benchmark, we are given 3 sets of output per benchmarks, each set being the result of ~25,000,000 instructions. We are using SPECfp as a benchmark, which is a standard floating-point algorithm benchmark that works by running state-of-the-art algorithms such as the Einstein evolution algorithm and quantum mechanical simulations.

I apologize that I can't give more accurate details as to the actual code that I'm working with, but I'm not really allowed to talk about it because the research is going towards an unreleased paper.

Good morning world

I'm splitting my time between the lasauil project that Neil, Ryan, and Evan are working on, and an internship with UT. For my internship I need to ssh into the UTCS computers, as well as a TACC (Texas Advanced Computing Center) allocations. Unfortunately, AISD blocks all SSH requests, so I've been trying to find ways around the block, with the help of Sam Grayson- I'm also contacting AISD directly about an exception. The work I am doing is related to cache architecture, specifically caching algorithms.

Graphing

Most libraries built for graphing data on web pages are large and clunky, so I opted to write my own client code to generate graphs of user data for the uil website. The data is given as two groups of time stamps and question ids, one for questions answered correctly and one for questions answered incorrectly. First, the data is normalized so that the time stamps are between 0 and 1, inclusive, so that the question with time stamp 0 is your first question answered and 1 is your last question answered. The data is then sorted and iterated through and graphed, keeping track of the ratio between your number of questions answered correctly and incorrectly, generating a graph of your general performance over time.

This style of data crunching is briefly very computationally intensive, so if users are opening a lot of pages it could chew up some bandwidth. Additionally, I'm not sure how well this will work if users have a very long history, but there won't be more data points than there are questions in the whole database, so that should be fairly easy for us to control.