Introducing Probability into Chip Design

prostoalex writes "The August issue of Intel Developer Update has an interview with Shekhar Borkar, Intel Fellow and Director of Circuit Research at Intel Corp. talking about the future of microprocessor design and what goes on inside Intel Labs. Borkar tells why we need even faster processors and how probability will make its way into future chip designs - "It's like the shift from Newtonian mechanics to quantum mechanics. We will shift from the deterministic designs of today to probabilistic and statistical designs of the future.""

Comments

Re:Is this new?

[mgessner]

I can't speak for all branch prediction models, but in the PowerPC, the answer is yes, but it's static.

In the PowerPC, unless a hint is given by the programmer/compiler, forward branches (positive offset) are predicted as NOT taken, and backward branches are predicted as BEING taken.

This is simply because lots of branching (aside from function calls) takes place in for, while and do-while loops (or for, while, and repeat-until for you Pascal geeks :)

it is an old story

[wannasleep]

In the interview, a lot of things have been left out. The topic is first and foremost old. It goes back to the 80s. Statistical variations have always been taken into account by using worst cases. Problem is that the worst case approach sucks in the latest technologies, so more sophisticated methods have to be used. There has been a lot of research in the last 10 years (Check american, german, and italian universities, just to name few).
Also, the problem is old, meaning that analog designers had to deal with these problems since the early stages (example: the offset in the operational amplifiers is caused by transistor performance mismatch). Now, digital designs are affected too. First on the clocking network and now all the rest. Furthermore, it is widely known (in the community) that interconnect variations are of the same order of magnitude of the device (i.e. transistor)performance variations, and on the top of that dynamic effects (like cross talk) may severely affect the performance.
I don't agree with him on the fact that all the variations are gaussian, there is plenty of literature that states the contrary, and major chip makers know it very well.
Last but not least, there are already tools that deal with statistical variations, although none of them can handle a microprocessor, as they are mostly circtuit simulation-based. All in all, the good news is that awareness is spreading thru the designers.

Re:it is an old story

[fupeg]

I think there is a slight misunderstanding here. The "variance" of analogy systems is really just manufacturing fault tolerance. The manufacturing process is imperfect and so there is a standard error associated with each quality of a given component. This is a little different than the kind of variance that is related to quantum mechanics.

Imagine an AND gate that is a single silicon atom. For such a gate to be "open" a single electron would have to be "flow" through it. This requires the electron to bond to the atom and it's ability to do that is a function of the position of the other electrons in the silicon atom. Quantum mechanics tells us that the positions of these electrons is not determined UNTIL something (such as the electron in this case) interacts with the atom. Until the time of interaction, the electrons have no discrete positions but are instead described by probability distributions. So this is an AND gate that is non-deterministic. Not only will "not always work", but you have no way of knowing if will or will not until you fire an electron at it, and just because it "fails" once has no bearing on the probability of it "failing" again. This is similar to the analog analogy, but it is even less deterministic.

I think Brokar caused some of the confusion in his interview by bringing up the analogy of variance in speeds of P4 chips. For that to be an accurate analogy, each P4 chip's speed would also vary each time you measured it. Anyways, a chip designed around this kind of non-deterministic behavior would be impressive. And chips will have to be designed this way for the size of components to get much smaller (an atomic diameter is around 0.1 nm.)

Re:Is this new?

[Jugalator]

Oh, I see... The page now loaded for me, and it seems they're simply considering the fact that previously, hardware performance didn't vary that much, but now when we've got down to real small components -- down to atom level -- that are packed closely together, the probability that the chips will behave differently from environment changes becomes greater. And as the probability of chips "misbehaving" increases, there will also be an increasing need of chips that can take this probability of fluctations into account.

I first thought the article was about speeding up stuff by probabilities and statistics, but it's mostly about solving a currently theoretical problem that might soon become an actual, real world problem. And to solve that problem, we might even have to move away from some of the computer architecture as we know it today.

Re:Is that 1.999 repeating?

[Anonym0us Cow Herd]

An easier form of this proof that I used back in 1979 or thereabouts is when arguing with those who don't understand that 0.9999... is equal to 1. I had learned this proof even earlier from my excellent math teacher in high school.

Let x be 0.99999....

x = 0.9999....
10x = 9.9999...
10x - x = 9.9999... - 0.9999... = 9
10x - x = 9 (the infinite trail of nines drop off in the subtraction)
but also, 10x - x = 9x
So, 9x = 9
Therefore x = 1

With this form of the proof, it is easier to see how the trailing nines just drop off in the subtraction. After thinking about this, the key seems to be that after multiplying 0.9999... by ten, to get 9.9999..., you still have the same number (infinity) of nines behind the decimal point.

This idea has been around for ages

[Theovon]

Random number generators are used in ASIC and FPGA logic placement and interconnect routing.

The goal is to place and route logic in a way that meets the designer's timing and area constraints. The problem is that a deterministic algorithm for that is NP-complete. Instead of considering all possibilities, a number of randomly-generated possibilities are considered, with some ability to make adjustments when one is chosen.

The randomly-generated possibilities, of course, are not completely random -- it's a matter of multiple gates competing for the same fixed-location logic cell, etc. Who gets the one closest to where they all want to be? Where do you place the rest? What about others competing for THOSE locations? It's complicated. :)

Re:Infinity != Infinity, for all values of Infinit

[Anonym0us Cow Herd]

I'm not talking about different functions approaching infinity at different rates.

I'm talking about the fact that 9.99999.... minus nine is exactly 0.99999.....

Therefore 9.99999..... minus 0.99999.... must be exactly 9.

Re:I'm a non-believer.

[Charbal]

Alright. So, say that x is 0.99999... with an infinite number of nines. You claim that x is a number distinct from 1 (since you claim 1 - x is nonzero). Since the the rationals and irrationals are both dense in the reals, we know that if we pick any two distinct reals, we'll always have numbers between them. That is, it's impossible to pick a number and the "next" real number without skipping over any. Yet that is essentially what you've done by positing that the gap between these numbers is infinitely small.

Put in other terms,

1 - x = limit(n->infinity, 1 - sum(9*10^(-i), i=1..n)) = limit(n->infinity, 10^(-n))

So let y equal 1 - x. We can show that if y != 0, then 1 - x < y even with a finite number of digits. Just pick n to be the least integer which is at least -log(y)+1 and then 10^n < y just considering a finite number of digits, n.

That is, if you tell me what the nonzero gap between the numbers that you expect to see, one can show that the gap is less than that. Since the gap is a nonnegative number that is less than all nonzero (ie, positive) choices, it is zero.

Therefore, 0.9999999..... = 1.

On an even more off-topic note, has anyone else started to think that trolls that bring up controversial mathematical statements are probably the best way to get responses nowadays? Not to say that the OP was a troll, but if it was, congratulations on all the responses. Also, congratulations to the Monty Hall problem poster some days back that was a troll.

Re:Is that 1.999 repeating?

[ebuck]

How does a mathematically incorrect assumption become insightful here on Slashdot?

Infinitely repeating digits (aka 0.9...) don't share the same meaning as those that terminate (aka 0.9) treating them the same is inappropriate, and only useful in demonstrating the flaw in logic that they can be treated the same.

x = 0.9999...
10 = 10 * 0.9999...
10x - x = 10 * 0.9999... - 0.9999
10x + (-1)x = 10 * 0.9999... + (-1) * 0.9999...
(10 - 1)x = (10 - 1) * 0.9999...
9x = 9 * 0.9999...

Unless somewhere along the line you make the error of assuming that 0.9999... = 1, you cannot arrive at 9x = 9.

Re:Is that 1.999 repeating?

[Anonym0us Cow Herd]

Unless somewhere along the line you make the error of assuming that 0.9999... = 1, you cannot arrive at 9x = 9.

I never made such an assumption. Let's review my proof.

Let x = 0.99999.....

Now, don't you agree that 10x would be 9.999999..... ?

So far I am not assuming what you have said.

Now is it true that 9.9999.... minus 0.9999.... would be exactly 9? An infinite number of nines minus an infinite number of nines is zero.

But there is an even simpler proof that someone else mentioned. If there is a difference between 1 and 0.9999... then there must be some number in between these two. Would you be so kind as to tell me what what number is?

Re:Is that 1.999 repeating?

[Stalyn]

ahhh jeeze.

1. first you apply rational analysis to an irrational number but whatever.

x = 0.9999....

lim x = 1
x -> 1

lim 10x = 10

lets supposed x = 0.999
thefore 10x = 9.99
10x - x = 8.991

now again x = 0.9999...
10x = 9.9999....

10x - x = 8.999....1

the infinite series of 9s is reduced by one when you multiply it by 10. it is a common misconception that all infinites are equal, this is not true.

let x = 0.9999... where n is the number of decimal places.

x to the n places * 10 = x to the n - 1 places

proof

let n = 3

0.999 * 10 = 9.99
n = 2

let n = inf

0.9999.... * 10 = 9.9999....

n = inf - 1

lim n = inf
n -> inf

lim n - 1 = inf
n -> inf