text: In competitive parallel computing, the identical copies of a code in a phase of a sequential program are assigned to processor cores and the result of the fastest core is adopted. In the literature, it is reported that a superlinear speedup can be achieved if there is an enough fluctuation among the execution times consumed by the cores. Competitive parallel computing is a promising approach to use a huge amount of cores effectively. However, there is few theoretical studies on speedups which can be achieved by competitive parallel computing at present. In this paper, we present a behavioral model of competitive parallel computing and provide a means to predict a speedup which competitive parallel computing yields through theoretical analyses and simulations. We also found a sufficient condition to provide a linear speedup which competitive parallel computing yields. More specifically, it is sufficient for the execution times which consumed by the cores to follow an exponential distribution. In addition, we found that the different distributions which have the identical coefficient of variation (CV) do not always provide the identical speedup. While CV is a convenient measure to predict a speedup, it is not enough to provide an exact prediction.
  @cite_9: With the advent of multi-cores and many-cores, traditional techniques that seek only to improve FLOPS of performance or the degree of parallelism have hit a roadblock with regards to providing even greater performance. In order to surmount this roadblock, techniques should more directly address the underlying design objectives of an application. Specific implementations and algorithmic choices in applications are intended to achieve the underlying realism objectives in the programmer's mind. We identify two specific aspects of this realism that traditional programming and parallelization approaches do not capture and exploit to utilize the growing number of cores. The first aspect is that the goal of minimizing program execution time can be satisfactorily met if the program execution time is low with sufficiently high probability. We exploit the fact that randomized algorithms are available for many commonly used kernels, and that the use of parallelism can achieve very low expected execution times with high probability for these algorithms. This can provide speedups to parts of the application that were hitherto deemed sequential and ignored for extracting performance via multi-cores. The second aspect of realism that we exploit is that important classes of emerging applications, like gaming and interactive visualization, have user-interactivity and responsiveness requirements that are as important as raw performance. Their design goal is to maximize the functionality expressed, while maintaining a high and smooth frame-rate. Therefore, the primary objective for these applications is not to run a fixed computation as fast as possible, but rather to scale the application semantics up or down depending on the resources available. Our framework intends to capture the responsiveness requirements of these applications as they pertain to expressed realism and automatically scale the application semantics expressed on every architecture, including very resource-rich many-cores.
  @cite_12: With core counts on the rise, the sequential components of applications are becoming the major bottleneck in performance scaling as predicted by Amdahl's law. We are therefore faced with the simultaneous problems of occupying an increasing number of cores and speeding up sequential sections. In this work, we reconcile these two seemingly incompatible problems with a novel programming model called N-way. The core idea behind N-way is to benefit from the algorithmic diversity available to express certain key computational steps. By simultaneously launching in parallel multiple ways to solve a given computation, a runtime can just-in-time pick the best (for example the fastest) way and therefore achieve speedup. Previous work has demonstrated the benefits of such an approach but has not addressed its inherent waste. In this work, we focus on providing a mathematically sound learning-based statistical model that can be used by a runtime to determine the optimal balance between resources used and benefits obtainable through N-way. We further describe a dynamic culling mechanism to further reduce resource waste. We present abstractions and a runtime support to cleanly encapsulate the computational-options and monitor their progress. We demonstrate a low-overhead runtime that achieves significant speedup over a range of widely used kernels. Our results demonstrate super-linear speedups in certain cases.
  @cite_2: 
summary: Without enough attention to the degree of the variance of the execution time among processors, using naively wastes computing resources. To overcome this problem, Cledat @cite_12 @cite_9 @cite_2 proposes the methods called and . The CV of WalkSAT, one of the application they adopted for evaluation, is less than one and the speedup is worse than a linear speedup. Meanwhile, the CV of another application, namely, MSL motion planning is greater than one and a superlinear speedup is achieved. These results are consistent with our result. Therefore, it is proper to claim that our results reinforce and extend their work.