Path: utzoo!attcan!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!nosc!ucsd!rutgers!apple!baum
From: baum@Apple.COM (Allen J. Baum)
Newsgroups: comp.arch
Subject: Re: Help: Hashing on TLB input?
Message-ID: <16891@apple.Apple.COM>
Date: 9 Sep 88 19:20:25 GMT
References: <3907@psuvax1.cs.psu.edu> <22876@amdcad.AMD.COM>
Reply-To: baum@apple.UUCP (Allen Baum)
Organization: Apple Computer, Inc.
Lines: 25

[]
> tim@crackle.amd.com (Tim Olson) writes:
>  soohong@gondor.cs.psu.edu (Soohong Kim) writes:

>|     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. 
>| 
>|     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?

>.. stuff about how to avoid thrashing the TLB...
>The most obvious hash is to use the lsb's of the virtual address as an
>index into the TLB.  This is better than using the msb's, because
>addresses exhibit the principal of locality, so we want sequential pages
>to map to different TLB sets.  This scheme can be augmented in many ways.

Unfortunately, this is largely affected by how compilers and OS's allocate
pages. It is often not enough to use the LSBs, because then the first page
of every process would collide, or the heap (allocated to high mem.) would
collide with the stak d(in low mem., or vice versa), or user and system pages
would collide. So, the hashing that I've seen exclusive-ors the msb's of the
page number with the lsb's, sometimes reversing the bits of one half or the
other to really get them good and random.                                    
--
{decwrl,hplabs,ihnp4}!nsc!apple!baum		(408)973-3385