Value Prediction in a Nutshell

Value Prediction (VP) is a microarchitectural technique that speculatively breaks true data dependency to increase instruction level parallelism in out-of-order processor cores. Think of it as "branch prediction but for values"™. It was proposed in the 90's by four independent groups :

  • AMD (Nexgen): L. Widigen and E. Sowadsky, patent filed March 1996, inv. March 1995
  • Technion: F. Gabbay and A. Mendelson, inv. sometime 1995, TR 11/96, US patent Sep 1997 [1]
  • Carnegie Mellon University: M. Lipasti, C. Wilkerson, J. Shen, inv. Oct. 1995, ASPLOS paper submitted March 1996, MICRO June 1996 [2,3]
  • University of Wisconsin: Y. Sazeides, J. Smith, Summer 1996 [4]

So far, VP has not - officially - been implemented in products. However, VP has recently regained interest [5,6,7] as a way to increase IPC in an era where Moore's Law is fading and Dennard Scaling is gone. One of the initial VP papers by Lipasti and Shen was also awarded a MICRO Test-of-time award in 2017. The award "recognizes the most influential papers published in prior sessions of the International Symposium on Microarchitecture, each of whom have had significant impact in the field".

VP Championships

After a succesful first championship workshop held in colocation with ACM/IEEE ISCA'18, it appeared to us that an all-year round championship would be a good way to move Value Prediction forward. The objective is to gather news ideas to potentially impact industry design decisions, while providing contestants a way to publish their work on the CVP website and present it at the CVP workshop that we will organize regularly (contingent on the number of new submissions).

CVP also provides a good framework for CS and ECE BS/MS students looking for an interesting project that may potentially have real-world implications should key industry players decide to implement VP.

CVP Provides :

Link to Old CVPs


To participate, please take a look at the Rules & Downloads section.

And register with the cvp-1 google group for kit & leaderboard updates !




References

[1] Gabbay, F & Mendelson, A. Speculative Execution Based on Value Prediction. Technion TR-1080, 1996.

[2] Lipasti, M. H., & Shen, J. P. Exceeding the dataflow limit via value prediction. In Proceedings of the annual International Symposium on Microarchitecture (MICRO), 1996.

[3] Lipasti, M. H., Wilkerson, C. B. & Shen, J. P.Value Locality and Load Value Prediction. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 1996.

[4] Sazeides, Y., & Smith, J. E. The predictability of data values. In Proceedings of the International Symposium on Microarchitecture (MICRO), 1997.

[5] Perais, A., & Seznec, A. Practical data value speculation for future high-end processors. In Proceedings of the International Symposium on High-Performance Computer Architecture (HPCA), 2014.

[6] Perais, A., & Seznec, A. EOLE: Paving the Way for an Effective Implementation of Value Prediction.. In Proceedings of the International Symposium on Computer Architecture (ISCA), 2014.

[7] Sheikh, R., Cain, H. W. & Damodaran, R. Load Value Prediction via Path-based Address Prediction: Avoiding Mispredictions Due to Conflicting Stores. In Proceedings of the International Symposium on Microarchitecture (MICRO), 2017.


Other References (no specific order)

Gabbay, F & Mendelson, A. Using value prediction to increase the power of speculative execution hardware. ACM Transactions on Computer Systems (TOCS), 1998.

Gabbay, F & Mendelson, A. The effect of instruction fetch bandwidth on value prediction. In Proceedings of the International Conference on Computer Architecture (ISCA), 1998.

Burstcher, M & Zorn, B. G. Exploring last-n value prediction. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques (PACT), 1999.

Burstcher, M & Zorn, B. G. Hybridizing and coalescing load value predictors. In Proceedings of the International Conference on Computer Design (ICCD), 2000.

Calder, B., Reinman, G. & Tullsen, D. M. Selective value prediction. In Proceedings of the International Symposium on Computer Architecture (ISCA), 1999.

González, J. & González A. The potential of data value speculation to boost ILP. In Proceedings of the International Conference on Supercomputing (ICS), 1998.

Goeman, B., Vandierendonck, H. & De Bosschere, K. Differential FCM: Increasing value prediction accuracy by improving table usage efficiency. In Proceedings of the International Symposium on High Performance Architecture (HPCA), 2001.

Loh, G. Width prediction for reducing value predictor size and power. In First Value Prediction Workshop, held in conjunction with the International Symposium on Computer Architecture (ISCA), 2003.

Lee, S-J. & Yew, P-C. On table bandwidth and its update delay for value prediction on wide-issue ILP processors. IEEE Transactions on Computers (TC), 2001.

Nakra, T., Gupta, R. & Soffa, M. L. Global context-based value prediction. In Proceedings of the International Symposium on High Performance Architecture (HPCA), 1999.

Rychlik, B., Faistl, J. W., Krug, B. & Shen, J. P. Efficacy and performance impact of value prediction. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques (PACT), 1998.

Sazeides, Y. & Smith, J. E. Implementations of context based value predictors. Technical report, University of Wisconsin at Madison, 1998.

Thomas, R. & Franklin, M. Using dataflow based context for accurate value prediction. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques (PACT), 2001.

Wang, K. & Franklin, M. Highly accurate data value prediction us-ing hybrid predictors. In Proceedings of the International Symposium on Microarchitecture (MICRO), 1997.

Zhou, H., Flanagan, J. & Conte, T. M. Detecting global stride locality value streams. In Proceedings of the International Symposium on Computer Architecture (ISCA), 2003.

Perais, A. & Seznec, A. BeBoP: A cost effective predictor infrastructure for superscalar value prediction. In Proceedings of the International Symposium on High Performance Computer Architecture (HPCA), 2015.