1
$\begingroup$

I'm trying to explain why some complex process obeys Central Limit Theorem.

The process is a chip compiler that runs complex place & route algorithms. The input is an integer seed. It initializes the algorithms in a random way. The output is a real number, which determines quality of results; the higher the number - the better. Exact implementation of place & route algorithms is not known. But their goal is to reach quality of results be positive.

I run 100 compiles with different seeds. When I plot a histogram of the results, it looks like a normal distribution. I tried different designs, tool versions, etc., and always get nicely shaped normal distribution, but with different mean and variance.

I strongly suspect that Central Limit Theorem plays a role here. But why?

Why would a complex place&route algorithm obey CLT, if it has nothing to do with any random distribution. Or maybe the interpretation of the results has nothing to do with the CLT.

Below is a process block diagram and example of the results.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Your distribution does not look Normal: it is clearly left-skewed. Without information about the details of the calculations giving the results, it really is not possible to answer this question. $\endgroup$ – whuber Oct 16 '13 at 20:47
  • $\begingroup$ Right, the distribution doesn't look exactly like Normal. Perhaps, the number of samples (100) is not sufficient. It takes several hours to obtain a single sample. But I certainly see the trend - the more samples, the more bell-shaped the distribution becomes. $\endgroup$ – OutputLogic Oct 16 '13 at 22:17
  • 1
    $\begingroup$ You already have enough samples to demonstrate a significant departure from normality. It is unlikely additional samples will change the shape of the distribution appreciably. $\endgroup$ – whuber Oct 16 '13 at 22:57
  • $\begingroup$ I'm less concerned about getting exact Normal distribution. What's puzzling is general bell-like shapes that I'm getting each and every time. And its coming from a process that is unlike any random distribution. So the question is really if I can disprove that the process obeys CLT. $\endgroup$ – OutputLogic Oct 17 '13 at 0:16
  • 1
    $\begingroup$ And the answer is yes, there are ways to disprove the process is exhibiting CLT-like behavior: apply a distribution test to the data you have already collected. Getting "general bell-like shapes" is common and often has little to do with the CLT. But, once again, please note that you have not supplied any of the information about your process that would be needed for readers here to give you objective, informed, or relevant advice. $\endgroup$ – whuber Oct 17 '13 at 11:48
3
$\begingroup$

One important point that many seem to be confused about is the application of the Central Limit Theorem (CLT). The CLT applies to the arithmetic mean of a distribution—not the distribution itself. Given an increasing number of samples, the average of those samples tends to be normally distributed with the "mean mean" equal to the overall mean and the variance of that mean estimator proportional to the variance and the number of samples. The actual distribution itself is not going to be normal. If anything, the distribution of the samples (NOT their average) will flesh out the shape of the distribution and you will have a greater chance of seeing an extreme value the more samples are generated.

My hunch is that your routing score is probably an average of some values, and, as such, is the mean of some distribution. If so, as the mean of a distribution, under many conditions its own distribution will tend to the normal after enough samples are generated.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Although I don't know anything about circuit design, I'm confused as everyone else why you would expect results to cluster around the average. The CLT has to do not with the shape (as many have correctly pointed out) but the probability of each a data point landing into a random a subset. If the underlying process had a bi-modal distribution, most of the samples would have skinnier peaks.

If your random seeds determine the efficiency of their placement and there is some sort of upper and lower bound on performance then your numbers simply reflect the distribution of such locations.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I certainly didn't expect to see that results have bell-shaped form. I discovered this property accidentally, and now want to explore it further, because it's very helpful with what I'm doing. $\endgroup$ – OutputLogic Oct 18 '13 at 5:46
  • $\begingroup$ @OutputLogic which is great! I'm not sure how much the second part of that question helps answer your question ... it is hard to explain how deterministic and non-deterministic processes interact. Can you talk a bit more about what is confusing for you? (I'm actually working on a paper that tries to explain this to psychology and CS people right now!) $\endgroup$ – Indolering Oct 18 '13 at 16:24
  • $\begingroup$ The purpose of a random seed is to initialize chip place & route algorithm. However, the algorithm itself is deterministic. That means if you run it multiple times with the same seed, you'd get the same result. Meaning of the result is not the efficiency, but the measure of how close it is to the given constraints. So the upper bound means that the algorithm meets or even exceeds given constraints. The lower bound can theoretically any negative value, but practically there is some. $\endgroup$ – OutputLogic Oct 18 '13 at 20:42
  • $\begingroup$ So, why are you assuming that the place & route algorithms have anything to do with the CLT? It has to do with the random sampling of locations and how many starting positions will exceed your output constraints, whatever they happen to be. $\endgroup$ – Indolering Oct 19 '13 at 2:50
  • $\begingroup$ On the contrary, I'm observing certain behavior that looks like CLT, and trying to disprove it. If I cannot disprove it, it has far reaching implication to what I'm trying to do. $\endgroup$ – OutputLogic Oct 19 '13 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.