---

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".

Value Prediction Championships

The first Championship Value Prediction (CVP-1) (Old website) was held in colocation with ACM/IEEE ISCA'18. To leverage the interest shown at the workshop, we chose to keep CVP-1 alive online, with the objective of gathering new ideas to potentially impact industry design decisions, while providing contestants a way to publish their work on the CVP website and present it at a latter instance of the in-person or virtual CVP workshops. The leaderboard of CVP-1 and CVP-1 Online can be found here.

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. CVP includes :

• A trace-based simulator courtesy of Vinesh Srinivasan and Eric Rotenberg from NCSU. Note : Different workshops use different releases of the framework, be sure to use the correct one if you wish to participate !
• Currently unavailable, work in progress to rehost, 135 small traces (30M insts.) and 2013 large traces (100M insts. for sampled worloads, 20-600M insts. for entire workloads) courtesy of Qualcomm Datacenter Technologies (Cheers to Daniel Jiménez for hosting those until September 2022) (Temporary backup for small traces, expiring 3/20/21). Those traces comprise both compute- and memory-intensive workloads, as well as a large number of server-class traces. Be sure to check out the README file first
• Currently unavailable, work in progress to rehost, A trace reader for anyone to experiment with the traces. Currently the trace reader depends on boost to stream from compressed files, but one can work around it (by using gzstream for instance). The underlying trace format is open and explicited in the trace reader file should you want to build your own.

Link to Old CVPs

• CVP-1 Online
• CVP-1 (Old website)

---

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.