Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!nrl-cmf!ames!killer!pollux!ti-csl!tilde.ti.com
From: Johnson@tilde.ti.com (Doug)
Newsgroups: comp.arch
Subject: Re: "General-purpose" architectures and symbolic languages
Message-ID: <70626@ti-csl.csc.ti.com>
Date: 22 Feb 89 17:29:42 GMT
References: <28113@ucbvax.BERKELEY.EDU> <7051@polya.Stanford.EDU>
Sender: djohnson@ti-csl.csc.ti.com
Lines: 72
In-reply-to: <7051@polya.Stanford.EDU>

In article <7051@polya.Stanford.EDU> you write:
  >I too am interested in such issues.
  >
  >One thing I've been wondering about is the compatibility of RISC-style
  >caches and Lisp Machine-style forwarding pointers.
  >
  >On Lisp Machines, the time required to check for invisible forwarding
  >pointers is generally hidden in time required for cache operation,
  >but I'm unsure of the details.  Do the new cache architectures still
  >allow this.  (I know they don't generally support such snazzy features.
  >The question is whether other design decisions directly conflict with
  >invisible forwarding.)

Forwarding pointers do not involve the cache on either the Explorer I or
Explorer II.  The Explorer I doesn't have a cache.  It uses microcode to
check the type of the data read and do the indirection if necessary.
It's strictly serial.

The Explorer II uses hardware in the read path to check the data type
and cause the CPU to do the indirection.  The major advantage is that it
eliminates the inline microcode check.  The Explorer II has a cache, but
the cache knows nothing about forwarding pointers -- they're just a
series of memory references.  

The essence of the problem is that the indirection is done based on the
type of the data fetched.  This is right in the critical path of the
memory interface.  Plus or minus a bit, the type check can't start until
the data could be presented to the CPU.  You either have to slow the
memory interface by the type check time, or have a way of saying "I
didn't mean it" after making the data available.  

Incidently, there is an analogous problem with implementing a read
barrier for incremental garbage collection.  You'd like to raise an
exception if a pointer to old space is read.  

  >
  >Also, is anybody doing any work on coordinating cache operation with
  >garbage collection?  With a large cache (100 KB or larger), you should
  >be able to have a small Newest generation (say, 50 KB) that is scavenged
  >completely within the cache -- no thrashing.
  >
  >Even if the Newest generation won't fit in the cache, you should be
  >able to avoid swapping a lot of cache blocks out by telling the cache
  >hardware if they only contain garbage.  (i.e., force them to appear
  >clean, so they won't be written back, or tell the cache to "create"
  >a block without actually reading in the corresponding block from
  >main memory).  It seems that this would cut cache-memory traffic by
  >approximately half (?) for the Newest generation.
  >
  >Anybody out there doing such work?

Bob Courts has a paper in the September 1988 CACM titled "Improving
Locality of Reference in a Garbage Collecting Memory Management System".
It focuses on the interaction between GC and virtual memory.  I suspect
much of the work applies to caches as well.

I strongly suspect that it's not worth worrying about for caches.
(Courts shows the significant advantages of worrying about virtual
memory.)  Unless your average cache lifetimes are long compared to the
interval between GC flips, the cache flushes caused by flips will be
small compared to those caused by normal running.  

This Explorer has been up for 236 hours and generation 0 (youngest) has
flipped 688 times -- averaging a flip every 21 minutes.  I couldn't turn
up any data on cache lifetimes in a quick look through my bookcase, but
I have the impression it's much shorter.  (Thought experiment:  A 5 mips
processor with a 128K byte cache, 20% load ratio, 1% miss rate, and
uniformly distributed misses will have an average cache life of about 3
seconds.)   Obviously, this comparison has a lot of holes in it, but
we're an order of magnitude apart.

-- Doug