| Author |
Message |
Rich Walker
Guest
|
 Posted:
Thu Aug 18, 2005 12:15 am Post subject:
Re: Non Power of 2 Cache Sizes |
|
|
bob_jenkins@burtleburtle.net writes:
| Quote: | Hashing is becoming a lost art,
just like everything else of
importance in computing ;-)
That's not quite a haiku. Too many syllables.
|
All useful papers
Are in closed journals.
Much waste.
cheers, Rich.
--
rich walker | Shadow Robot Company | rw@shadow.org.uk
technical director 251 Liverpool Road |
need a Hand? London N1 1LX | +UK 20 7700 2487
www.shadow.org.uk/products/newhand.shtml |
|
| Back to top |
|
 |
Eugene Miya
Guest
|
| Posted:
Thu Aug 18, 2005 12:15 am Post subject:
Re: Non Power of 2 Cache Sizes |
|
|
In article <ddsgb9$4em$1@osl016lin.hda.hydro.com>,
Terje Mathisen <terje.mathisen@hda.hydro.com> wrote:
| Quote: | It should be easier to have non-power-of-two memory banks, since RAM is
a _lot_ slower than cache (presumably :-) anyway, and even before
multi-level caches became common there was a mainframe with something
like 17-way main memory. (Honeywell?)
|
The BSP.
Different firm.
-- |
|
| Back to top |
|
|
Terje Mathisen
Guest
|
| Posted:
Thu Aug 18, 2005 11:31 pm Post subject:
Re: Non Power of 2 Cache Sizes |
|
|
David Kanter wrote:
| Quote: | Nick Maclaren wrote:
In article <ddv7hu$is1$1@osl016lin.hda.hydro.com>,
Terje Mathisen <terje.mathisen@hda.hydro.com> writes:
|
|> > I don't know how easy it is to take modulo N for a fixed N is in
|> > hardware - the fact that doing it for a variable N is a pain proves
|> > little. As I have posted before, x%N for fixed N can be done a LOT
|> > faster for fixed but arbitrary N (i.e. ignoring setup costs) than
|> > for variable N in software, but still not fast enough for this use.
|
|> Fixed N, where N is on the form (2^n) +/- 1 can be done more or less (*)
|> in the same time as your example above, the code is similar.
Oh, yes, but the problem with numbers like that is that they aren't
rare as array sizes in programs. They may not be AS common as
powers of two, but 2^n+1 in particular is definitely common. It
falls naturally out of certain FFT designs. 2^n-1 is rarer, but
not rare.
The advantage of a non-modulo approach is that it doesn't have
the catastrophic failure mode when a critical array size matches
the cache size. All modulo approaches do, but array sizes tend
to follow certain patterns.
What exactly is the problem with having your array size match the cache
size? Sorry, ISTR something like this mentioned in H&P:aQa, I just
don't recall the exact problem.
|
Nothing at all, IF you always stride through all (or most of the entries
in order. It is particularly when you work with matrices and step along
them in the wrong direction that caches blow up.
Terje
--
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching" |
|
| Back to top |
|
|
Iain McClatchie
Guest
|
| Posted:
Sat Aug 20, 2005 12:04 am Post subject:
Re: Non Power of 2 Cache Sizes |
|
|
Joseph> But once you've hit this, the question becomes one of what
Joseph> compelling reason do you have to *not* have a power of 2?
There is more than one way to do non-power-of-two.
- There is an advantage to having fixed instruction sizes -- you
can do without a queue between fetch and decode.
- There is a hit rate advantage to smaller instructions, witness
Tensilica's 24-bit instructions.
- Fixed-size non-power-of-two-sized instruction require one of
two solutions that I know of:
1) A rotator mux after fetch. This can get pretty wide, with a
lot of wires. It is, of course, important not to get overly
impressed by expensive datapath bits that are easy to analyze,
because they're usually not a big deal compared to the expensive
control bits that surprise you late in the design.
2) Fixed-pattern packing. Itanium does it, to put 3 instructions
into 128 bits. I like the idea of 5 instructions in 128 bits,
myself.
Then finally there is the question of addressing these instructions.
My guess is that it would be fine to avoid any complicated
addressing logic, and simply make the 5th instruction in 128 bits
unaddressable.
Nick is going to jump in here and ask how we take an exception or
interrupt on that last instruction. I have a plan for that:
Remember the atomic basic blocks? They're back. If you take an
exception anywhere within the basic block, the entire block fails
and you restart the whole thing. If you don't like that
granularity, then you can restart on 128b boundaries. |
|
| Back to top |
|
|
Eugene Miya
Guest
|
| Posted:
Thu Sep 15, 2005 10:03 pm Post subject:
Re: Non Power of 2 Cache Sizes |
|
|
In article <ddsgb9$4em$1@osl016lin.hda.hydro.com>,
Terje Mathisen <terje.mathisen@hda.hydro.com> wrote:
| Quote: | multi-level caches became common there was a mainframe with something
like 17-way main memory. (Honeywell?)
|
Burroughs. I know the guy who did this (lives in Palo Alto).
-- |
|
| Back to top |
|
|
Eugene Miya
Guest
|
| Posted:
Fri Sep 16, 2005 9:34 pm Post subject:
Re: Non Power of 2 Cache Sizes |
|
|
In article <ddsgb9$4em$1@osl016lin.hda.hydro.com>,
Terje Mathisen <terje.mathisen@hda.hydro.com> wrote:
| Quote: | multi-level caches became common there was a mainframe with something
like 17-way main memory. (Honeywell?)
|
I noted:
| Quote: | Burroughs. I know the guy who did this (lives in Palo Alto).
|
BTW, Terje, if we ever have another ca-fest, I will see about getting Steve
to come, and you can talk to him about 17-way memories. And depending on
where in the bay area it gets held, I'll get Gordon Bell to join us.
Additionally in 2 weeks you are missing Gordon Moore talking locally.
-- |
|
| Back to top |
|
|
Terje Mathisen
Guest
|
| Posted:
Sat Sep 17, 2005 9:48 pm Post subject:
Re: Non Power of 2 Cache Sizes |
|
|
Eugene Miya wrote:
| Quote: | In article <ddsgb9$4em$1@osl016lin.hda.hydro.com>,
Terje Mathisen <terje.mathisen@hda.hydro.com> wrote:
multi-level caches became common there was a mainframe with something
like 17-way main memory. (Honeywell?)
I noted:
Burroughs. I know the guy who did this (lives in Palo Alto).
BTW, Terje, if we ever have another ca-fest, I will see about getting Steve
to come, and you can talk to him about 17-way memories. And depending on
where in the bay area it gets held, I'll get Gordon Bell to join us.
Additionally in 2 weeks you are missing Gordon Moore talking locally.
|
Don't keep reminding me that most of my real heroes are located 9
timezones away. Except for this, Oslo, Norway is a really great place to
live. :-)
Anyway, I've already marked my calendar for the week after Easter,
monday or tuesday would be perfect.
Terje
--
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching" |
|
| Back to top |
|
|
Eugene Miya
Guest
|
| Posted:
Tue Sep 20, 2005 12:15 am Post subject:
Re: Non Power of 2 Cache Sizes |
|
|
| Quote: | like 17-way main memory. (Honeywell?)
Burroughs.
BTW, Terje, if we ever have another ca-fest, I will see about getting Steve
to come, and you can talk to him about 17-way memories. And depending on
where in the bay area it gets held, I'll get Gordon Bell to join us.
Additionally in 2 weeks you are missing Gordon Moore talking locally.
|
In article <dghhcc$v92$1@osl016lin.hda.hydro.com>,
Terje Mathisen <terje.mathisen@hda.hydro.com> wrote:
| Quote: | Don't keep reminding me that most of my real heroes are located 9
timezones away.
|
Last Tuesday I had dinner with Gio Wiederhold and another ex-DARPA
program manager (Oscar). Oscar remarked how amazing living near
Stanford is. Although Oscar spent the last year having nothing to do
work technologies (he was on what we call a grand jury), he was
amazed how people and firms think.
I saw efforts at over half a dozen other universities fail.
This is not that every Stanford effort succeeds or gets blended into
google.
| Quote: | Except for this, Oslo, Norway is a really great place to live. :-)
|
Oh, I have no doubt. Erik Fair who wrote a version of NNTP is from
Norway. We didn't take you to the Norway store in Oakland.
I will get to Norway one of these days, but I also want to go much
further North as well.
| Quote: | Anyway, I've already marked my calendar for the week after Easter,
monday or tuesday would be perfect.
|
I don't know yet if I have time to attend Asilomar.
No one here has come forward to run the next ca-fest.
-- |
|
| Back to top |
|
|
Terje Mathisen
Guest
|
| Posted:
Tue Sep 20, 2005 8:15 am Post subject:
Going far north (Was: Re: Non Power of 2 Cache Sizes) |
|
|
Eugene Miya wrote:
| Quote: | Oh, I have no doubt. Erik Fair who wrote a version of NNTP is from
Norway. We didn't take you to the Norway store in Oakland.
I will get to Norway one of these days, but I also want to go much
further North as well.
|
Svalbard/Longyearbyen!!!
If you can ever manage a trip to Svalbard, preferably in the March-May
period, I guarantee you'll be amazed. The light at 78+ degrees north is
so spectacular that I really didn't believe it until I experienced it in
March 2004.
Try to imagine the most glorious sunset you've ever seen, only lasting
more or less all day. :-)
As a scientist you might even wangle an invitation to the Ny Ålesund
research station at N79.
Terje
--
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching" |
|
| Back to top |
|
|
Eugene Miya
Guest
|
| Posted:
Wed Sep 21, 2005 8:15 am Post subject:
Re: Going far north (Was: Re: Non Power of 2 Cache Sizes) |
|
|
In article <dgoeel$opp$1@osl016lin.hda.hydro.com>,
Terje Mathisen <terje.mathisen@hda.hydro.com> wrote:
Only time for one folow up.
| Quote: | NNTP / Norway.
further North as well.
Svalbard/Longyearbyen!!!
|
Well German friends have worked on Svalbard.
I am awaiting a Greenland bid, but also Northern Norway annd Iceland.
| Quote: | If you can ever manage a trip to Svalbard, preferably in the March-May
period, I guarantee you'll be amazed. The light at 78+ degrees north is
so spectacular that I really didn't believe it until I experienced it in
March 2004.
|
Earlier. Easily Feb.
| Quote: | Try to imagine the most glorious sunset you've ever seen, only lasting
more or less all day. :-)
As a scientist you might even wangle an invitation to the Ny Ålesund
research station at N79.
|
Oh, I have an idea. I have time (months) at 83S.
-- |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in