Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!samsung!noose.ecn.purdue.edu!dynamo.ecn.purdue.edu!hankd
From: hankd@dynamo.ecn.purdue.edu (Hank Dietz)
Newsgroups: comp.arch
Subject: Re: Throwaway: Speedup address formation for cache lookup
Summary: A few other throwaway tecnhiques: XOR and Gray Code
Message-ID: <1990Sep13.175819.11542@ecn.purdue.edu>
Date: 13 Sep 90 17:58:19 GMT
References: <AGLEW.90Sep11231456@dwarfs.crhc.uiuc.edu>
Sender: news@ecn.purdue.edu (USENET news)
Organization: Purdue University Engineering Computer Network
Lines: 29

In article <AGLEW.90Sep11231456@dwarfs.crhc.uiuc.edu> aglew@crhc.uiuc.edu (Andy Glew) writes:
>Here's another of my throwaway ideas[*]:
...
>Possible hacks to reduce the need to wait for the address addition:
>
>(1) Many addresses have limited carry propagation.  In the extreme case,
>    you could just OR the base+index together and send that to the cache quickly,
>    falling back to using the full addition in case of an error.
...
>(2) Most variables are accessed in only two possible ways:  either by a full pointer,
>    or by a single fixed base and offset.  Usually only one of the many possible
>    base+offset pairs is used.  If this statement is true for all variables
>    in a cache line, then triple the tags (one full address, one base+index)
>    might be used, with triple the match logic.

How about these instead:

[3]	Although ORing an offset in works fine give small offsets and a
	compiler which performs the appropriate data layout, the size
	constraint sucks.  Unlike OR, XOR can be used without imposing
	a size constraint.  Sure, the data structure's elements end up
	arranged in a rather random-looking memory sequence, but so what?
	This is well within the grasp of a smart compiler.

[4]	Gray codes only have one bit change for increment.  By using such an
	address encoding, things can be simplified, but this gets somewhat
	nasty to deal with...  I think.

						-hankd@ecn.purdue.edu