home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / arch / 12458 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  3.0 KB
  1. Path: sparky!uunet!UB.com!pacbell.com!sgiblab!darwin.sura.net!paladin.american.edu!howland.reston.ans.net!sol.ctr.columbia.edu!The-Star.honeywell.com!umn.edu!math.fu-berlin.de!mailgzrz.TU-Berlin.DE!cs.tu-berlin.de!godmar
  2. From: godmar@cs.tu-berlin.de (Godmar Back)
  3. Newsgroups: comp.arch
  4. Subject: IBM RS/6000 inverted pagetable / hashing alg.
  5. Date: 28 Jan 1993 21:18:20 GMT
  6. Organization: Technical University of Berlin, Germany
  7. Lines: 51
  8. Distribution: h
  9. Message-ID: <1k9iisINN10f@news.cs.tu-berlin.de>
  10. NNTP-Posting-Host: luckwill.cs.tu-berlin.de
  11.  
  12.  I'm working on a preparation on the IBM RS/6000 machine architecture,
  13. particularly its storage control system.
  14.  
  15. I've read a few articles dealing with that subject, but I can't figure
  16. out, how the hashing algorithm works. Let me give you a short explanation
  17. how I see these things upto the point I don't understand.
  18.  
  19.  The effective address of 32 bit is extended, using the segment ID
  20. addressed by the corresponding segment register, to a 52 bit wide
  21. virtual address. This virtual address is divided into a 40 bit wide part,
  22. (the 40 most significant bits, referred to as virtual pagenumber) and
  23. a 12 bit wide part containing the offset in the page.
  24.  
  25.  The purpose of an inverted pagetable is to assign the real 
  26. pagenumber to the virtual pagenumber. It contains one entry for
  27. every real page, that means, for instance, entry No. 4711 contains
  28. the virtual pagenumber of the virtual page currently mapped to the
  29. 4711st real page.
  30.  
  31.  During normal storage access you have to assign virtual pagenumbers to
  32. real pagenumbers, i.e. to find out which page table entry contains
  33. the virtual pagenumber you are referring to. This is done by hashing.
  34. A hashvalue is computed from the virtual pagenumber, and in a hashtable
  35. a possible index for the page frame table is looked up. Afterwards
  36. the virtual pagenumber is compared with the virtual pagenumber found
  37. in that entry of the page frame table with this looked up index.
  38. In case of collision you must follow a chained list in the pagetable.
  39.  
  40. The problem is, that the page frame table entry contains only the
  41. 27 high order bits of the virtual page number (which is 40 bit wide).
  42. How can you be sure, that the entry found in the hashtable contains the
  43. right virtual pagenumber ?
  44.  
  45.  Or, is it perhaps guaranteed by the hashing algorithm, that addresses
  46. with equal lower parts (the 13 low order bits) are always hashed to
  47. different indices in that hashtable, therefore providing different 
  48. anchors for these lists? This could probably be done by
  49. using those bits as some kind of subindex for the hashtable, maybe
  50. the least significant bits of the index. The remaining bits would be
  51. computed by hashing the 27 most significant bits. But that's just
  52. a supposition, I don't know it exact.
  53.  
  54. Another question is, how big the hashtable is, and if its size is fixed
  55. or not, and from which parameters it depends.
  56.  
  57. Thanks to everybody who has read upto this point, I'm sure that my
  58. german-style English must be quite difficult to understand.
  59.  
  60. Thank you very much in advance! Please e-mail reply.
  61.  
  62. Godmar
  63.