Re: Parallel & RT GC (was Re: Real-Time GC (was Re: Widespread C++...?)

[kelvin@cs.iastate.edu (Kelvin Nilsen)]

beckwb@ois.com (R. William Beckwith) writes:

>: "Is there any work-in-progress by the large chip manufacturers to
>: design GC into their next-generation CPU architectures?  It seems
>: like the next logical step."

>I'm not looking for a complex solution.  I'm looking for the simplest
>design changes in instruction set, cache, and register files to
>accommodate transparent memory management.

Paul Wilson mentioned my proposed hardware support for GC.  In case 
anyone is interested in more information on this, I suggest the following
five references:

  Schmidt, Nilsen.  Performance of a Hardware-Assisted Real-Time Garbage
  Collector.  Sixth ASPLOS.  Oct. 1994.

  Nilsen, Schmidt.  Cost-Effective Object-Space Management for Hardware-
  Assisted Real-Time Garbage Collection.  ACM LOPLAS.  Dec. 1992.

  Nilsen.  Reliable Real-Time Garbage Collection of C++.  USENIX Computing
  Systems.  Fall 1994.

  Nilsen, Schmidt.  A High-Performance Hardware-Assisted Real-Time
  Garbage Collection System.  Journal of Programming Languages.  Jan. 1994.

  Nilsen.  Cost-Effective Hardware-Assisted Real-Time Garbage Collection.
  1994 ACM PLDI Workshop on Languages, Compilers and Tool Support for
  Real-Time Systems (ftp.cs.iastate.edu:/pub/kelvin/lcts-rts.PS.Z)
  (this paper provides an overview of the hardware prototype that is currently
  under development.  there are a number of recent innovations that we have
  introduced to reduce hardware costs and improve system flexibility)

>Why not design the CPU with the GC'tor in mind instead of designing the
>GC'tor with the CPU in mind.

>I just seems silly that hardware designers aren't thinking more about
>relieving us programmers from thinking about what memory we are currently
>using.

Our design proposes to place all of the special circuitry within a custom
memory module.  The design is portable between CPU architectures, and allows
memory to be cached.  The economic benefits are:

  1. Nobody (these days) would even think of designing such specialized
     support into a CPU.  The benefits have not been proven.  The costs
     are not well understood.  The investment required to deliver a 
     price/performance competitive CPU in today's marketplace is too
     huge.  By placing the custom hardware within the memory subsystem,
     we are able to provide the desired benefits without most of the
     costs of developing special-purpose CPUs.

  2. The hardware can operate at memory speeds rather than at CPU speeds.
     This simplifies the implementation.

  3. Since the memory architecture is portable between CPU architectures,
     we can separate issues of instruction-set compatibility from issues
     of real-time garbage collection support.  (It would be a real bummer
     if our custom-CPU died in the marketplace not because hardware-assisted
     GC was a bad idea, but because the instruction set simply wasn't
     "popular".)

Let me add a little bit of clarification on this topic:

  1. Our work has been motivated by the need to support tight worst-case
     time bounds on dynamic memory management routines while supporting 
     predictable memory utilization.  Given these requirements, hardware
     support seemed like the "right thing to do."

  2. If you do not need hard-real-time performance guarantees, then it
     is much more difficult to justify the costs of custom hardware.  There
     are many good software garbage collection techniques that perform
     well enough in the absence of custom hardware.

  3. On the other hand, if the proposed custom hardware is manufactured in
     large enough quantities, then it becomes commodity hardware and is
     much more affordable.  This may raise the ante.  Programmers will
     have higher expectations of their programming environments, and 
     garbage collection activities will be a more dominant part of a 
     "typical" system workload.  (We are trying to find some high-volume
     users for our system in order to bring the per-unit cost down.  
     Potential buyers include the video game, virtual reality, and 
     television-top multimedia box developers.)

  4. Lots of "good ideas" never go anywhere.  To turn a good idea into
     a useful capability requires huge amounts of technology development,
     salesmanship, risk taking, faith (blinders?), and a little bit of
     luck.  We have a "chip manufacturer" partner who is currently helping
     to bring this idea to the marketplace, but the partner is not one of
     the big names and they are extremely careful to control their risks
     and limit their investments.  A big part of "computer architecture"
     research seems to consist of simply learning how to "play your cards."



Kelvin Nilsen/Dept. of Computer Science/Iowa State University/Ames, IA  50011 
 (515) 294-2259   kelvin@cs.iastate.edu  uunet!cs.iastate.edu!kelvin