Re: what's next for the linux kernel?

[Luke Kenneth Casson Leighton <lkcl@lkcl.net>]

On Sun, Oct 02, 2005 at 10:55:49PM -0400, Valdis.Kletnieks@vt.edu wrote:
> On Mon, 03 Oct 2005 01:54:00 BST, Luke Kenneth Casson Leighton said:
> 
> >  in the mid-80s), hardware cache line lookups (which means
> >  instead of linked list searching, the hardware does it for
> >  you in a single cycle), stuff like that.
> 
> OK.. I'll bite.  How do you find the 5th or 6th entry in the linked list,
> when only the first entry is in cache, in a single cycle, when a cache line
> miss is more than a single cycle penalty, and you have several "These are not
> the droids you're looking for" checks and go on to the next entry - and do it
> in one clock cycle?
 
  i was not privy to the design discussions: unfortunately i was only
  given brief conclusions and hints by the designer.

  my guess is that yes, as the later messages in this thread
  hint at, CAM is probably the key: 256 blocks of 32-bit CAM,
  something like that.

  CAM is known to help dramatically decrease execution time
  by orders of magnitude in linked list algorithms such as
  searching and sorting, esp. where each CAM cell has built-in
  processing, like the aspex.net massively-deep SIMD architecture has.

  l.