From: tk@ai.mit.edu (Tom Knight)
Newsgroups: comp.arch,comp.lang.lisp
Subject: Re: Ideas for new LISP Machines
Date: 6 Apr 92 16:09:07 GMT
Article-I.D.: wheat-ch.TK.92Apr6120907
	<ktkt4iINN65g@boogie.cs.utexas.edu>
Followup-To: comp.arch
Organization: MIT Artificial Intelligence Lab
In-reply-to: wilson@cs.utexas.edu's message of 2 Apr 92 02:42:26 GMT

In article <ktkt4iINN65g@boogie.cs.utexas.edu> wilson@cs.utexas.edu (Paul Wilson) writes:

   The main thing you probably want is a very large second-level cache,
   big enough to hold the whole youngest generation of a generational
   gc.

In large parallel machines, large caches containing unused data are
not benign.  There is a cost to having data in your cache (the
requirement that it be updated) whether you use the data or not.  It
is not obvious that extremely large second level caches are desirable
in such parallel machines.

   Then you want nonblocking prefetching (software-controlled is
   OK) first-level cache so that you can prefetch the memory you're about
   to allocate.  Otherwise you'll miss your cache A LOT, because a
   high-performance Lisp system typically allocates (hence touches,
   dirties, and writes back) a lot of memory between garbage collections. 
 
While I certainly concur that you want a load/don't block instruction,
if you can guarantee that the data is freshly allocated, then you
don't have to prefetch the location into your cache.  You can simply
write it.  No one else can have a pointer to that memory (by
assumption, since you are freshly allocating it).  This is one of the
ways advanced languages can help hardware.  Don't throw the benefits
away.

   Have a look at the SPARC's tagged arithmetic instructions.  All they
   really do---if I recall correctly---is check to see if the low two
   bits are zeroes, and makes it easy (by setting condition codes?) to
   do a quick branch if they're not.  Steenkiste and Hennessy's paper
   on tags explains how to exploit conventional hardware's address
   decode logic (and object alignment constraints) to get some of the
   other benefits of tags, and how careful choice of tag values allows
   neat hacks so that they don't cost much.  

I think everyone has looked at these.  They are cute, but, especially
the version in the SPARC is little more than a joke, since the
checking is missing from almost everything except the add instruction.
We used to call these marketing tags at Symbolics, and my opinion of
them hasn't changed much.  While we might be able to do data typing
this way, the technique falls flat on its face for doing presence bits
for supporting futures or dataflow features in parallel
implementations.  Lucid found this out to their pain in the Alliant
QLisp implementation, for example.  You don't get good performance for
floats, of course, unless you are willing to butcher the precision of
your mantissas.  But hey, it's Unix.  It doesn't have to be right, as
long as it boots fast.

   The SPARC is the intellectual descendent of the SOAR chip from Berkeley.
   Dave Ungar's 1986 thesis talks about the cost/benefit analysis of tagging
   and other features for supporting dynamically typed languages like
   Lisp and Smalltalk.

   Ungar argues that most features don't really have an important impact
   on performance, or actually DEGRADE performance by affecting the CPU's
   basic cycle time and/or by making the chip harder to design and get to
   market.  (A 6 month late chip is slower just because the competition
   has gotten significantly faster in 6 months.)  And the LAST thing you
   want to do is interfere with the basic pipeline of a hot chip.

This argument is pure rubbish.  The alpha people are desperately
trying to figure out what profitable things to do with the 3 million
extra transistors available on the next generation die.  If you or
someone else can show me how tagging impacts the critical path of the
pipe, I might pay some attention.  Anyone who looks seriously at it
can see that the tagging paths are parallel to, shorter than, and
easier to implement than, for example, the add path.  The real
difficulties, which I don't want to minimize, have to do with fitting
the tags into power-of-two words, when the IEEE standard requires 64
bit precision.  Non power-of-two implementations face incredible
difficulties in interfacing with the rest of the computing world.  The
most profitable approaches probably involve coding non-floats as
various types of NANs in the double float format.

   Of the few features the SOAR folk DID decide were worth the effort and
   chip area, some are of questionable value now, because people have come
   up with better software techniques.  Register windows are an example---if
   you have a good register allocator in your compiler, and do snazzy inlining
   and aggressive optimizations, the register windows become much less
   useful.  (Ungar, Chambers, and Hoelzle have done wonderful things with
   compiling away the costs of dynamic dispatching... see their papers in
   the OOPSLA and SIGPLAN conferences of the last few years.)

Register windows were a bad idea, but had little to do with supporting
Lisp and Smalltalk.

   Another example is hardware support for incremental and generational gc's.
   MIT, Symbolics, and TI Lisp machines had invisible forwarding pointers
   in hardware, so that a copying collector could move objects around while
   the program was running.  That way, it didn't have to stop the running
   program to collect garbage.  Without hardware support, that would be
   very expensive.  But now Henry's invented a non-copying version of his
   incremental scheme, which avoids the problem entirely.

These techniques are very clever, but don't entirely solve the gc problems.
Write barriers are still very useful, low cost, and desirable, in my
opinion.

   Soar and SPUR (the Lisp-oriented RISC that followed SOAR) incorporated
   hardware support for the detection of intergenerational pointers. (That is,
   pointers from old data, which don't get gc'd often, into new data,
   which do.)  My 1989 OOPSLA paper shows why that's probably not
   the right thing to do anyway, and you're better off doing "card marking",
   where you just keep dirty bits.  Ungar has since improved on my scheme
   by using bytes as dirty bits, because byte stores are cheap and fast on
   most architectures.  (We just modified my GC to use Ungar's byte maps, too.)

Byte writes are a plague on the world.  Alpha does not support them,
for extremely good reasons having to do with the need to error correct
main memory contents on a byte boundary basis if you allow byte writes
-- or else do read-pause-writes for each write.  It's bad enough that
they felt it necessary to support 32 bit word writes.  I predict that
byte writes will not be "cheap and fast on most architectures" from
now on.

   Fast atomic byte stores are handy.  Atomic bit stores would be nice, too.
   You want them atomic because setting a byte or bit in a word shouldn't
   interfere with another thread's doing the same thing to a different
   byte or bit in the same word.

   I think that one nice hardware feature would be bit addressing, because
   then we could steal 10 low-order bits instead of just 2, and use more
   patterns for tags.  That's not likely, though, because the world pretty
   much assumes C pointers-to-character these days.  And 2 bits actually
   is adequate, if not ideal---it lets you distinguish between pointers,
   immediate integers, and a couple of other things.  For further 
   discriminations, you can consult object headers.

Bitwise writes would be even worse, for the same reasons.

   I think it's probably better to focus on better OS support and software
   techniques than on specialized hardware.   For example, you can do
   wonderful things with virtual memory protections, and take extra advantage
   of the parallel checking hardware you've already got---the TLB.

   In that respect, conventional architectures are fine, if the pages aren't
   too large.  The current trend toward huge pages is very annoying.  The new
   ARM 600 takes a more reasonable approach, having independently protectable
   1KB chunks within 4KB pages.  You at least want small units of protection,
   but there's no reason they should be the same as the unit of address
   translation.

The trend to large pages makes a great deal of sense due to increased
main memory size because of low costs and the large size of disk
cylinders.  It also allows relatively larger physically mapped first
level caches, where the page translation and the cache lookup happen
in parallel.  What you are really after is not larger page sizes, but
smaller units of control for write and read barriers.  These are not
the same, and it is a mistake to confuse them.  The ARM approach
sounds 1/2 right, probably for the wrong reasons, but now give me
write barriers.
Xref: sparky comp.arch:4753 comp.lang.lisp:1307