Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!pacbell!att-ih!ihnp4!inuxc!iuvax!pur-ee!hankd
From: hankd@pur-ee.UUCP (Hank Dietz)
Newsgroups: comp.arch
Subject: Re: Cache lookahead
Message-ID: <7755@pur-ee.UUCP>
Date: 22 Mar 88 18:36:06 GMT
References: <2769@mmintl.UUCP> <28200127@ccvaxa>
Organization: Purdue University Engineering Computer Network
Lines: 57
Summary: Software Cache Management "State-of-the-Art"

In article <28200127@ccvaxa>, aglew@ccvaxa.UUCP writes:
> I have a paper from Purdue EE entitled "Compiler Driven Cache Policy"
> which is basically about providing compiler control of cache.
> Their policy is called SCP - Software Cache Policy.
> Authors are Chi, C., and Dietz, H.G.
> June 1987.
...
> Someone from the CEDAR group at the U of I gave a talk showing that, in
> his research, software controlled caching was not a win.
> The trouble is, this is not a disproof - all we need is one existence
> proof.

Chi-Hung Chi is my PhD student at Purdue EE.  His thesis work is a complete
graph-based model for static (compile-time) memory management, especially
management of cache and registers.  His work differs from most other
software cache management schemes in that:

1. It is based on minimizing TOTAL REFERENCE TIME, NOT on MAXIMIZING
   cache HIT RATIO (this makes a very big difference!) and

2. It is complete cache management, rather than simple prefetch
   prediction.

An excellent register-allocation version of his technique appears in the
proceedings of HICSS 88:  "Register Allocation for GaAs-based Computer
Systems."  As for the cache management, we have many materials available on
this, but the following is the abstract of our latest paper "Improving Cache
Performance By Selective Cache Bypass" (sent to SUPERCOMPUTING 88):

	In traditional cache-based computers, all memory references are made
through cache.  However, a significant number of items which are referenced
in a program are referenced so infrequently that other cache traffic is
certain to "bump" these items from cache before they are referenced again.
In such cases, not only is there no benefit in placing the item in cache,
but there is the additional overhead of "bumping" some other item out of
cache to make room for this useless cache entry.  Where a cache line is
larger than a processor word, there is an additional penalty in loading the
entire line from memory into cache, whereas the reference could have been
satisfied with a single word fetch.  Simulations have shown that these
effects typicaly degrade cache-based system performance (average reference
time) by 10% to 30%.

	This performance loss is due to cache pollution; by simply forcing
"polluting" references to directly reference main memory -- bypassing the
cache -- much of this performance can be regained.  The technique proposed
in this paper involves the use of hardware which, under program control,
will determine whether each reference should be through the cache or
bypassing the cache and referencing main memory directly.  Several
inexpensive heuristics for the compiler to determine how to make each
reference are given.
     _        
    | \   __     _
    |  | |  |   / |  Compiler-oriented          Hank Dietz &
 _/ |  | |  |  /  |  Architecture               Chi-Hung Chi
/   |--| |__| |__/   Researcher from
\_  |  | | \  |      Purdue
  \ |    |  \  \
                \