home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / arch / 8949 < prev    next >
Encoding:
Text File  |  1992-08-18  |  3.1 KB  |  70 lines
  1. Newsgroups: comp.arch
  2. Path: sparky!uunet!cs.utexas.edu!usc!wupost!rice!dawn.cs.rice.edu!preston
  3. From: preston@dawn.cs.rice.edu (Preston Briggs)
  4. Subject: Re: Caches and Hashing
  5. Message-ID: <Bt7KEF.8Lq@rice.edu>
  6. Sender: news@rice.edu (News)
  7. Organization: Rice University, Houston
  8. References: <1992Aug18.182506.23744@ross.COM>
  9. Distribution: usa
  10. Date: Wed, 19 Aug 1992 02:03:49 GMT
  11. Lines: 57
  12.  
  13. john@netnews.jhuapl.edu (John Hayes) writes:
  14. >
  15. >> There was an interesting idea in a recent article in Microprocessor
  16. >> Report.  The article was describing HP's PA-RISC.  Here is what caught
  17. >> my eye:
  18. >>         "The caches are direct mapped to eliminate the performance
  19. >>         impact of multiplexers that would be required with set-
  20. >>         associativity.  To reduce the cache miss rates, the addresses
  21. >>         are hashed before they drive the cache SRAMS."*
  22. >> 1) How much does hashing improve the miss rate of a direct-mapped
  23. >> cache?
  24.  
  25. mitch@sparhawk.com (Mitch Alsup) writes:
  26. >As usual, your milage may vary due to: Application, O/S, cache size.
  27. >With 65KByte sized caches, many applications see only 5% miss rate
  28. >(and with a 10 cycle miss penalty they achieve only 50% machine
  29. >peak performance).  With 1MByte sized caches one could expect ~1%
  30. >miss rate and therefore greater than 90% machine peak performance.
  31. >
  32. >Excellent Hashing can be expected to achieve 40% improvement (max--
  33. >Moyers rule of SQRT(2)-1 for performance gains).  This could allow
  34. >the 65KB cache to achieve 3% miss rates and 70% peak performance;
  35. >or the 1MB cache to achieve 94% machine performance.  Considerable
  36. >gains in the first case and useful in the second.  The 65KB cache 
  37. >PROBABLY would benefit LESS than the larger cache because it is
  38. >operating closed to its intrinsic COMPUSOLRY miss rate (it is smaller)
  39. >while the 1MB cache could benefit more IF the WORKING SET of the
  40. >applicationS fit in the cache.  Also note that the difference in the
  41. >miss rate for the larger cache in direct mapped configruation to
  42. >a set associative configuration is considerably smaller than that
  43. >of the smaller cache.
  44.  
  45. I don't understand what is people are suggesting here.  Are we talking
  46. about scrambling addresses so that sequential accesses aren't
  47. necessarily mapped sequentially to cache?  Is it some kind of
  48. permutation or can to nearby items (where near is less than cache
  49. size) ever collide?  Does stride 1 access still pay off?
  50.  
  51. Back in the good ol' days (before I heard of this idea, anyway), we
  52. all had a rule we could live by:
  53.  
  54.     Elements in a vector don't interfere with each other
  55.     (as long as the vector is smaller than cache).
  56.  
  57. This even held for direct-mapped caches, primitive beasts though they
  58. are.  Of course, for a 4-way set-associative cache, we could plan on
  59. keeping 4 vectors in cache, with no interference at all (as long as we
  60. block the vectors to 1/4 the cache size).  And more ways of
  61. associativity would allow even more complex applications to be
  62. handled without problems.
  63.  
  64. Even with a direct-mapped cache, we can take advantage of the rule and
  65. copy many randomly placed chunks of data into locations that are safe
  66. (that is, we copy many things into a single vector).
  67.  
  68. Wondering what the world is coming to,
  69. Preston Briggs
  70.