On Fri, Nov 12, 2010 at 1:10 PM, Nilay Vaish <[email protected]> wrote:
I tried couple of ideas for improving the performance of the
findTagInSet()
function. These include having one hash table per cache set and replacing
the hash table with a two dimensional array indexed using <cache set,
cache
way>. Neither of these ideas showed significant enough change in the
percentage of the time taken by isTagPresent() function to come to a
definite conclusion.
I looked the assembly code generated for the isTagPresent() function. Note
that the compiler inlines the funtion findTagIsPresent(). The assembly
code
is about 100 lines long. Again, the find function for std::hash_map gets
inlined. There is one division operation in the code and several load
operations. If we were to assume that the hash function is able to keep
the
average occupancy of each bucket close to 1, then I think the time taken
by
the function would be determined by the time taken by the loads. It might
be
that a lot of loads end up missing in the cache.
I'm a little surprised that the direct cache set indexing approach was not
faster since I'd think that would be far less than 100 instructions, but
you're right that issues like whether loads hit or miss in the cache will
have a large impact.
As far as reordering the tags is concerned, since the hash_map is not
directly under our control, we will have to delete the tag entry in the
hash
table and insert it again to make sure that it is the first entry that is
searched.
The reordering only makes sense if we replace the hash table with a more
conventional tag array.
Right now I am profiling with coherence protocol as MOESI_hammer. I am
thinking of profiling using a different protocol to make sure that it is
not
an artifact of the protocol in use.
That sounds like a good idea.
All in all, we would ideally like to both speed up individual calls and
reduce the number of calls. IIRC, gprof indicated that findTagInSet() was
called 4-5X more frequently than there were cache accesses, which makes no
sense to me; it seems like a typical cache hit should only require a single
tag lookup.
That's another thing to keep in mind, is that typical programs really have
very high cache hit rates, so another approach is to look at what happens
in
the process of servicing an L1 cache hit and optimize that path as much as
possible.
Steve
