Statistical estimation and evaluation for communication mapping in Network-on-Chip

In order to exploit the advantages in on-chip communication introduced by Network-on-Chip, many optimization algorithms have been proposed for a joint optimization on power and performance in communication mapping and routing. However, the optimality of solutions relative to these algorithms has been neglected in previous studies. To this problem, this paper proposes an early estimating approach to evaluate the optimality of the solutions for the first time. This approach is based on a statistical property that the overall solutions in solution space conform to a quasi-Gaussian distribution, which can be previewed by two parameters with a computation complexity of O(n4) as presented. The generality of our proposed approach makes itself extensible to other on-chip network options. Experiments on real and synthetic application benchmarks demonstrate an average error ratio less than 7% which tends to be even smaller when problem scales up. These results validate our early estimating approach on optimality evaluation as credible and efficient to boost its utility in the promising Network-on-Chip design.