home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / arch / 8975 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  2.2 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!mips!sdd.hp.com!hpscdc!hplextra!hpcc05!aspen!morris
  2. From: morris@aspen.NSA.HP.COM (Dale Morris)
  3. Newsgroups: comp.arch
  4. Subject: Re: Caches and Hashing
  5. Message-ID: <1360025@aspen.NSA.HP.COM>
  6. Date: 19 Aug 92 17:41:07 GMT
  7. References: <1992Aug18.182506.23744@ross.COM>
  8. Organization: HP Networked Systems Architecture - Cupertino, CA
  9. Lines: 38
  10.  
  11. Preston Briggs writes:
  12.  
  13. > I don't understand what is people are suggesting here.  Are we talking
  14. > about scrambling addresses so that sequential accesses aren't
  15. > necessarily mapped sequentially to cache?  Is it some kind of
  16. > permutation or can to nearby items (where near is less than cache
  17. > size) ever collide?  Does stride 1 access still pay off?
  18. > 
  19. > Back in the good ol' days (before I heard of this idea, anyway), we
  20. > all had a rule we could live by:
  21. > 
  22. >     Elements in a vector don't interfere with each other
  23. >     (as long as the vector is smaller than cache).
  24. > 
  25. > This even held for direct-mapped caches, primitive beasts though they
  26. > are.  Of course, for a 4-way set-associative cache, we could plan on
  27. > keeping 4 vectors in cache, with no interference at all (as long as we
  28. > block the vectors to 1/4 the cache size).  And more ways of
  29. > associativity would allow even more complex applications to be
  30. > handled without problems.
  31. > 
  32. > Even with a direct-mapped cache, we can take advantage of the rule and
  33. > copy many randomly placed chunks of data into locations that are safe
  34. > (that is, we copy many things into a single vector).
  35.  
  36. The hash that HP uses does not disturb stride 1 access.  These are
  37. still the good old days for your rule.  I think you're right in
  38. thinking that breaking this rule would be a bad idea.
  39.  
  40. The function used hashes in bits that are not part of the 32-bit
  41. address space that the user sees.  Generally speaking, these bits are
  42. constant for each user process.  The hash serves only to randomize
  43. cache placement for one process' references versus anothers'.
  44.  
  45. ------------------------------------------------------------------------------
  46. Dale Morris        |  Now is the time, and now is the record...
  47. morris@nsa.hp.com   |          of the time.
  48. ------------------------------------------------------------------------------
  49.