Value prediction in many-core systems

Modern many-core-on-a-chip designs will demand programs with extremely high degrees of parallelism. Our study of the PARSEC and the SPLASH-2 benchmark suites has shown that application programs may not have sufficient inherent parallelism. However, two fundamental factors contribute to program speedup: intrinsic parallelism, which can be exploited by fine-grained synchronization, and inherent data redundancy, which can be exploited by value prediction. In this work, we first present a theoretical framework to characterize the predictability of data values and the feasibilities of value predictor designs. The results are encouraging: our theoretical analysis shows that the average value prediction accuracy can reach 70% on the PARSEC and the SPLASH-2 benchmarks. This demonstrates the immense potential of value prediction in enhancing the performance of many-core architectures.;Also, we explore the possibility of using the many-core GPU architectures for speculative execution: we implement software value prediction techniques to accelerate programs with limited parallelism, and software speculation techniques to accelerate programs that contain runtime parallelism, which are hard to parallelize statically. Our experiment results show that due to the relatively high overhead, mapping software value prediction techniques on existing GPUs may not bring any immediate performance gain. On the other hand, although software speculation techniques introduce some overhead as well, mapping these techniques to existing GPUs can already bring some performance gain over CPU. Furthermore, we explore the hardware implementation of speculative execution operations on GPU architectures. The results indicate that the hardware extensions result in almost 10-fold reduction of the control divergent sequential operations with only moderate hardware and power consumption overheads.;In addition, communication problems have become a major performance bottleneck in many-core architectures and in large-scale scientific simulations. We use LQCD simulations as a case study to study how value prediction techniques can reduce the communication overheads. We first implement a software value predictor on LQCD simulations: 22.15% of the predictions result in performance gain and only 2.65% of the predictions lead to rollbacks. Then we explore the hardware value predictor design, which results in a 6-fold reduction of the prediction latency. Moreover, based on the observation that the full range of floating point accuracy may not be always needed, we propose and implement an initial design of the tolerance value predictor: as the tolerance range increases, the prediction accuracy also increases dramatically.