Path: utzoo!utgpu!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!cornell!uw-beaver!uw-june!rik
From: rik@june.cs.washington.edu (Rik Littlefield)
Newsgroups: comp.arch
Subject: Re: Content Addressible Memories
Message-ID: <6765@june.cs.washington.edu>
Date: 19 Dec 88 19:29:37 GMT
References: <00051@meph.UUCP> <6746@june.cs.washington.edu> <13582@srcsip.UUCP>
Organization: U of Washington, Computer Science, Seattle
Lines: 26

In article <13582@srcsip.UUCP>,shankar@src.honeywell.COM (Son of Knuth) writes:
> rik@june.cs.washington.edu (that's me) writes:
> > [problems with using a fixed width CAM to access words when the number
> >  of bits in the index is larger then the CAM width, in languages like
> > Icon and Awk that support associative tables]
> 
> It is not difficult to design CAMs with chaining capability.
> [description of one scheme involving matching the first part, then shifting
> the match bits, marking the second part, and so on.]

True, but misses the point.  These languages are heavily interpreted, with
dynamic typing and garbage collection.  Most programs do NOT spend the bulk
of their time executing table searches.  You'd get much more bang for the
buck by investing in faster cpu/memory than in CAM support for the tables.  

BTW, it isn't clear that small CAMs would even make the tables run faster.
These languages require "exact match" on table indices.  A good hash
implementation should require less than 2 probes, independent of table size,
and computing the hash is a matter of a few instructions.  It's just very
hard to believe that repeatedly reloading a CAM unit with hundreds or
thousands of entries would be faster.  CAM hardware might look better if you
needed partial matches on some interior and unpredictable part of the 
index, so that it would be hard to avoid looking at all the entries.  But how
often does that come up?

--Rik