Path: utzoo!attcan!uunet!seismo!sundc!pitstop!sun!ember!dre
From: dre%ember@Sun.COM (David Emberson)
Newsgroups: comp.arch
Subject: Re: Help: Hashing on TLB input?
Summary: TLB hashing
Keywords: TLB, hashing
Message-ID: <67901@sun.uucp>
Date: 12 Sep 88 19:35:12 GMT
References: <3907@psuvax1.cs.psu.edu>
Sender: news@sun.uucp
Distribution: na
Lines: 29

In article <3907@psuvax1.cs.psu.edu>, soohong@gondor.cs.psu.edu (Soohong Kim) writes:
> Could some one please enlighten me by explaining these?
> 
>     In Hwang & Briggs (Computer architecture and parallel processing) it is
> said that the virtual page number is first randomized by hashing before
> feeding it to the TLB. It is also said that the reason is for efficient use
> of the low-order TLB entries. And Vax/750 seems to avoid hashing by using
> a number of high-order bits and 5 low-order bits to select the set in the
> set-associative TLB.
> 
>     My questions are:
> (1) Why is it inefficient to use the Virtual page number directly?
> (2) How could hashing or bit-combination help in improving the efficiency?
> 
> Thank you.
> ---Soohong

Most programs tend to use the same parts of their virtual address spaces, i.e.
low pages for text and data, and high pages for stack.  If you just used the
virtual page number to address the TLB, you would be doing a lot of thrashing
between processes and would not be using the TLB efficiently.

What is typically done is to ex-or the low order bits of the virtual page
number (bits most likely to change) with the low order bits of the process ID
to generate a pseudo-random number which addresses the TLB.  This ensures that
all entries in the TLB are used to the same degree and thrashing between
contexts is minimized.

			Dave Emberson (dre@sun.com)