Modeling multi-threaded programs execution time in the many-core era

Multi-core have become ubiquitous and industry is already moving towards the many-core era. Many open-ended questions remain unanswered for the upcoming many-core era. From the software perspective, it is unclear which applications will benefit from many cores. From the hardware perspective, the tradeoff between implementing many simple cores, fewer medium aggressive cores or even only a moderate number of aggressive cores is still to debate. Estimating the potential performance of future parallel applications on the yet-to-be-designed future many cores is very speculative. The simple models proposed by Amdahl's law or Gustafson's law are not sufficient and may lead to overly optimistic conclusions. In this paper, we propose a more refined but still tractable execution time model for parallel applications, the SNAS model. % (\textbf{ManyCore Performance model (MCP model????)}). As previous models, the SNAS model evaluates the execution time of both the serial part and the parallel part of the application, but takes into account the scaling of both these execution times with the input problem size and the number of processors. For a given application, a few parameters are collected on the effective execution of the application with a few threads and small input sets. SNAS allows to extrapolate the behavior of a future application exhibiting similar scaling characteristics on a manycore and/or a large input set. Our study shows that the execution time of the serial part of many parallel applications tends to increase along with the problem size, and in some cases with the number of processors. It also shows that the efficiency of the execution of the parallel part decreases dramatically with the number of processors for some applications. Our model also indicates that since several different application scaling trends will be encountered, heterogeneous architectures featuring a few aggressive cores and many simple cores should be privileged