Statistical Approach to NoC Design

Chip multiprocessors (CMPs) combine increasingly many general-purpose processor cores on a single chip. These cores run several tasks with unpredictable communication needs, resulting in uncertain and often-changing traffic patterns. This unpredictability leads network-on-chip (NoC) designers to plan for the worst-case traffic patterns, and significantly over-provision link capacities. In this paper, we provide NoC designers with an alternative statistical approach. We first present the traffic-load distribution plots (T-plots), illustrating how much capacity over- provisioning is needed to service 90%, 99%, or 100% of all traffic patterns. We prove that in the general case, plotting T-plots is #P-complete, and therefore extremely complex. We then show how to determine the exact mean and variance of the traffic load on any edge, and use these to provide Gaussian-based models for the T-plots, as well as guaranteed performance bounds. Finally, we use T-plots to reduce the network power consumption by providing an efficient capacity allocation algorithm with predictable performance guarantees.