3 ms·

Did my thesis trying to apply insights from Benford's law to the design of the adders in your CPU. The idea was you make your low order bits, which see more ac

Did my thesis trying to apply insights from Benford's law to the design of the adders in your CPU. The idea was you make your low order bits, which see more activity, slower and more power efficient and your high order bits faster and less efficient. Meet the same timing overall but with less energy on average. Sadly, memory addresses were close to pure entropy for my purposes and the savings I was able to get were only around 5%, not enough for all the effort.

bordercases 9y ago
Hm, wouldn't that pay off with time though?
wolfram74 9y ago
We try things, and sometimes, they even work. Good practice for when you do something that is worth the effort.
lisper 9y ago
Benford's law works for random variables drawn from a uniform distribution whose upper bound is itself a random variable with a uniform distribution. But memory addresses are not drawn from such a distribution. The upper bound of the distribution of memory addresses is almost always a power of 2.
- Symmetry 9y ago
  Yes, the fact that adders deal with so many memory addresses in practice means that the distribution of numbers I saw didn't end up working very much like Benford's law. The non-address data did but they weren't a large enough fraction of what was added together.
bsder 9y ago
Isn't the power consumption of a modern adder defined by the power of the carry chain activity rather than the bits? And I have no reason to believe that the carry chains obey Zipf's/Benford's law (average carry chain length is log2(n)). Bits are a local and transistor dominated function. Carry chains are non-local and interconnect dominated function. As an example I can twizzle between adding 0 to 0 and 0 to 1 all day long with very little power. If however I start adding 65535 to 0 and 65535 to 1, I'm going to start activating enormous amount of power.
- Symmetry 9y ago
  This depends in some part on your adder design. For the simplest adder, a ripple-carry adder, your power consumption is gong to scale with the width of the adder and an addition will take time proportional to the width to perform, with an energy cost proportional to to the width. This sort of adder doesn't really have any long lines for carrying bits long distances, everything is local once the data arrives at the adder. With carry-bypass or carry-lookahead you have a time of the square root of the width and the costs are both proportional to the width, a constant factor larger than with a ripple adder. These are the ones used in most higher performance CPUs, or were back in 2007 when I thesing. You have some long lines here but never more than square root width and a small number compared to the number of transistors. With tree adders you can add numbers in time proportional to the log of the width, costing a number of gates that grows as the square of the width. Now, if you assume that the inputs are all equally likely to be ones or zeros with no correlations then carry chains aren't likely to propagate very far up the tree. But as you point out if you happen to have an addition that creates a long carry chain then you'll end up switching most of the gates and using a lot of power. One of the things in my thesis that was actually practically useful was showing that you do frequently get long carry chains on real data meaning that the naive approach of counting gates works better for analyzing tree adders than trying to derive activity factors from simplified models of the inputs. These ones also have particularly long lines that have to be switched for long carry chains, and lots of them. I got my data from using this tool Intel puts out to instrument binaries like, say, 'ls' or 'mozilla' and reading out the inputs for every use of the adder. Well, random stretches of 100 uses anyways for the browser, otherwise I wouldn't have been able to store enough data.

bordercases 9y ago

Hm, wouldn't that pay off with time though?

wolfram74 9y ago

We try things, and sometimes, they even work. Good practice for when you do something that is worth the effort.

lisper 9y ago

Benford's law works for random variables drawn from a uniform distribution whose upper bound is itself a random variable with a uniform distribution. But memory addresses are not drawn from such a distribution. The upper bound of the distribution of memory addresses is almost always a power of 2.

Symmetry 9y ago
Yes, the fact that adders deal with so many memory addresses in practice means that the distribution of numbers I saw didn't end up working very much like Benford's law. The non-address data did but they weren't a large enough fraction of what was added together.

bsder 9y ago

Isn't the power consumption of a modern adder defined by the power of the carry chain activity rather than the bits? And I have no reason to believe that the carry chains obey Zipf's/Benford's law (average carry chain length is log2(n)). Bits are a local and transistor dominated function. Carry chains are non-local and interconnect dominated function. As an example I can twizzle between adding 0 to 0 and 0 to 1 all day long with very little power. If however I start adding 65535 to 0 and 65535 to 1, I'm going to start activating enormous amount of power.

Symmetry 9y ago
This depends in some part on your adder design. For the simplest adder, a ripple-carry adder, your power consumption is gong to scale with the width of the adder and an addition will take time proportional to the width to perform, with an energy cost proportional to to the width. This sort of adder doesn't really have any long lines for carrying bits long distances, everything is local once the data arrives at the adder. With carry-bypass or carry-lookahead you have a time of the square root of the width and the costs are both proportional to the width, a constant factor larger than with a ripple adder. These are the ones used in most higher performance CPUs, or were back in 2007 when I thesing. You have some long lines here but never more than square root width and a small number compared to the number of transistors. With tree adders you can add numbers in time proportional to the log of the width, costing a number of gates that grows as the square of the width. Now, if you assume that the inputs are all equally likely to be ones or zeros with no correlations then carry chains aren't likely to propagate very far up the tree. But as you point out if you happen to have an addition that creates a long carry chain then you'll end up switching most of the gates and using a lot of power. One of the things in my thesis that was actually practically useful was showing that you do frequently get long carry chains on real data meaning that the naive approach of counting gates works better for analyzing tree adders than trying to derive activity factors from simplified models of the inputs. These ones also have particularly long lines that have to be switched for long carry chains, and lots of them. I got my data from using this tool Intel puts out to instrument binaries like, say, 'ls' or 'mozilla' and reading out the inputs for every use of the adder. Well, random stretches of 100 uses anyways for the browser, otherwise I wouldn't have been able to store enough data.