home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / arch / 8948 < prev    next >
Encoding:
Internet Message Format  |  1992-08-18  |  4.9 KB
  1. Path: sparky!uunet!wupost!darwin.sura.net!mips!swrinde!cs.utexas.edu!loyola!ross.COM!sparhawk!mitch
  2. From: mitch@sparhawk.com (Mitch Alsup)
  3. Newsgroups: comp.arch
  4. Subject: Caches and Hashing
  5. Summary: HP Hashing direct mapped caches probably wins
  6. Message-ID: <1992Aug18.182506.23744@ross.COM>
  7. Date: 18 Aug 92 18:25:06 GMT
  8. Sender: news@ross.COM
  9. Distribution: usa
  10. Organization: Mitch Alsup Consulting
  11. Lines: 84
  12. Originator: mitch@sparhawk
  13. Nntp-Posting-Host: sparhawk
  14.  
  15. john@netnews.jhuapl.edu (John Hayes): Writes:
  16.  
  17. > There was an interesting idea in a recent article in Microprocessor
  18. > Report.  The article was describing HP's PA-RISC.  Here is what caught
  19. > my eye:
  20. >         "The caches are direct mapped to eliminate the performance
  21. >         impact of multiplexers that would be required with set-
  22. >         associativity.  To reduce the cache miss rates, the addresses
  23. >         are hashed before they drive the cache SRAMS."*
  24.  
  25. > This raises several questions in my mind:
  26. > 1) How much does hashing improve the miss rate of a direct-mapped
  27. > cache?
  28.  
  29. As usual, your milage may vary due to: Application, O/S, cache size.
  30. With 65KByte sized caches, many applications see only 5% miss rate
  31. (and with a 10 cycle miss penalty they achieve only 50% machine
  32. peak performance).  With 1MByte sized caches one could expect ~1%
  33. miss rate and therefore greater than 90% machine peak performance.
  34.  
  35. Excellent Hashing can be expected to achieve 40% improvement (max--
  36. Moyers rule of SQRT(2)-1 for performance gains).  This could allow
  37. the 65KB cache to achieve 3% miss rates and 70% peak performance;
  38. or the 1MB cache to achieve 94% machine performance.  Considerable
  39. gains in the first case and useful in the second.  The 65KB cache 
  40. PROBABLY would benefit LESS than the larger cache because it is
  41. operating closed to its intrinsic COMPUSOLRY miss rate (it is smaller)
  42. while the 1MB cache could benefit more IF the WORKING SET of the
  43. applicationS fit in the cache.  Also note that the difference in the
  44. miss rate for the larger cache in direct mapped configruation to
  45. a set associative configuration is considerably smaller than that
  46. of the smaller cache.
  47.  
  48. > 2) The argument for direct mapped caches is that they have a better
  49. > effective access time than set-associative caches because direct
  50. > mapped caches do not need multiplexers to select the data.  Would
  51. > the cost of hashing eliminate this advantage?  In other words:
  52. > would a direct mapped cache with hashing or a set-associative
  53. > cache (with associated multiplexers) give the best performance?
  54.  
  55. If one measures performance in nanoseconds per delivery of datums,
  56. it is quite possible that hashed accesses in direct mapped caches
  57. will perform better than set associative caches.  In HP's case, this
  58. is reinforced due to thier use of commodity SRAMS external to the 
  59. processor, and cannot, therefore, dink with the decoder to the ram
  60. arrays.  This should also be the case for internal VLSI ram arrays where
  61. the decoder can be set up to dink with the addresses (hash) with very
  62. little additional delay (100's of picoseconds).  Conversely, the
  63. output buffers can be setup to dink with the addresses driven to the
  64. SRAMs and incur very little additional delay (.5 ns).
  65.  
  66. On the other hand, if the TAG section is designed so that it has faster
  67. access times than the Data section of a VLSI-like cache, the tag access
  68. and set comparison can overlap the data access.  With this arrangement,
  69. the set selection can be driven as the data is sensed, and contribute
  70. negligably to the access time. (88200 uses this trick).  This requires
  71. that the tag section be about 4 gate delays faster than the data section.
  72. Careful SPICE modeling is REQUIRED.  Your mileage may vary.  This trick
  73. does not work with commodity SRAM chips because the access time for the 
  74. tags is commensurate with the access times for the data.  In any event,
  75. the gain from set associative caches dimminishes with large external
  76. caches (greater than 65KBytes).
  77.  
  78. > 3) What hash function does HP use?
  79.  
  80. Hopefully, one which places user code and user data in different cache
  81. locations than supervisor code and data.  If they also attempt to place
  82. I/O pages and data base pages separately from these others, then I can
  83. see considerable gain from hasing.  On the other hand, why cannot the 
  84. O/S and Linker conspire to place the pages in physical and logical locations
  85. so as to minimize these problems up front?
  86.  
  87. > I would be interestered to hear from anyone who knows the answer
  88. > to these questions from papers or first-hand knowledge.  I will
  89. > summarize to the net.
  90.  
  91. > * Case, Brian, "HP Reveals Superscalar PA-RISC Implementation",
  92. > Microprocessor Report, Vol. 6, No. 4, March 25, 1992, p. 17.
  93.  
  94. -------------------------------------------------------------------------------------
  95. Mitch Alsup        Currently at: mitch@ross.com An Independent Consultant
  96. (512)-263-5086     Evenings
  97. Disclaimer:        I speak for myself.
  98. -------------------------------------------------------------------------------------
  99.