Path: utzoo!attcan!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!pasteur!ames!amdcad!news
From: news@amdcad.AMD.COM (Network News)
Newsgroups: comp.arch
Subject: Re: Help: Hashing on TLB input?
Message-ID: <22876@amdcad.AMD.COM>
Date: 9 Sep 88 02:29:45 GMT
References: <3907@psuvax1.cs.psu.edu>
Reply-To: tim@crackle.amd.com (Tim Olson)
Distribution: na
Organization: Advanced Micro Devices, Inc., Sunnyvale CA
Lines: 38
Summary:
Expires:
Sender:
Followup-To:

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

If a TLB is fully-associative, then the entire TLB is searched in
parallel for the virtual address, and no hashing is required.  However,
if the TLB is set-associative or direct-mapped, then a mapping must
exist from a virtual address to the set to examine.  This mapping (or
hashing) must make efficient use of the TLB by evenly distributing the
virtual addresses over all of the sets instead of clustering them into a
few sets.  Otherwise the TLB will thrash, causing performance
degradation.

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.  For example, if the virtual address space is divided up into 1/2
user and 1/2 supervisor, then the msb of the virtual address can be
included in the hash to allow user and supervisor page mappings to
coexist in the TLB without replacing each other (this is apparently what
is going on in the Vax/750 example.)

	-- Tim Olson
	Advanced Micro Devices
	(tim@crackle.amd.com)