Path: utzoo!yunexus!geac!geaclib!daveb
From: daveb@geaclib.UUCP (David Collier-Brown)
Newsgroups: comp.arch
Subject: Re: Content Addressible Memories
Message-ID: <3491@geaclib.UUCP>
Date: 18 Dec 88 22:28:22 GMT
Article-I.D.: geaclib.3491
References: <15041@mimsy.UUCP>
Organization: GEAC Computers, Toronto, CANADA
Lines: 49

> In article <1929@scolex> seanf@sco.COM (Sean Fagan) writes:
>>I think that CAM would help AWK in many circumstances ....

From article <15041@mimsy.UUCP>, by chris@mimsy.UUCP (Chris Torek):
> Well, no and yes.
> 
> Awk wants to associate by arbitrary-length strings.  You would be faced
> with a choice of variable length matching in hardware, with a very long
> maximum, or limiting the match length, and both padding input as
> necessary and breaking up long associations.  CAMs are, at present,
> much better with fixed-length tags.

And then again, yes and no...

  Awk (and SNOBOL, and Icon) use a straightforward mapping of their
variable-length strings into table (array) elements, aimed at fast
execution on a sequential processor without CAM.  That does not mean
that one cannot come up with a mapping for processors with CAM...

  About 5 years ago, I worked on the NDX "fast indexing" machine,
discussed in an IEEE Computer special issue (in a box here somewhere
(:-)).  Its purpose in life was finding documents [elements]
containing data which matched certain boolean search terms
[indices]. Since the search terms were NOT small or fixed-length, we
munged them enthusiastically to allow a fast-search processor
(29xx bit-slices) to look through a meg or so of surrogates
[indices]. Specifically we used eight orthogonal hash functions to
fold them into a fixed-size search space with small (and predictable)
possibility of getting false drops [erronious fetches].

  This is generalizable to languages like awk, and possibly to
others with a need for fine-grained parallellism (prolog, I think).

  I do wonder if CAMs should not be treated as devices, though, and
not folded into those language(s) which do not actually need them...
As Henry Spencer points out, a machine with just CAMs runs a good
chance of being outperformed by one with valves too.  

  On the third hand, if a CAM was part of the critical "inner loop"
of the language implementations (as in prolog unifications?), it
would be an obvious candidate for inclusion in the machine...
Perhaps in the fpp socket?

--dave (I remember the CAFS. Whatever happened to the CAFS?) c-b
-- 
 David Collier-Brown.  | yunexus!lethe!dave
 Interleaf Canada Inc. |
 1550 Enterprise Rd.   | He's so smart he's dumb.
 Mississauga, Ontario  |       --Joyce C-B