Skip to main content
Erschienen in: International Journal of Parallel Programming 1/2014

01.02.2014

Aggressive Value Prediction on a GPU

verfasst von: Enqiang Sun, David Kaeli

Erschienen in: International Journal of Parallel Programming | Ausgabe 1/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

To obtain significant execution speedups, GPUs rely heavily on the inherent data-level parallelism present in the targeted application. However, application programs may not always be able to fully utilize these parallel computing resources due to intrinsic data dependencies or complex data pointer operations. In this paper, we explore how to leverage aggressive software-based value prediction techniques on a GPU to accelerate programs that lack inherent data parallelism. This class of applications are typically difficult to map to parallel architectures due to the presence of data dependencies and complex data pointer manipulation present in these applications. Our experimental results show that, despite the overhead incurred due to software speculation and the communication overhead between the CPU and GPU, we obtain up to 6.5\(\times \) speedup on a selected set of kernels taken from the SPEC CPU2006, PARSEC and Sequoia benchmark suites.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Advanced Micro Devices, Inc: Heterogeneous Computing Open CL and the ATI Radeon HD 5870 (Evergreen) Architecture (2010) Advanced Micro Devices, Inc: Heterogeneous Computing Open CL and the ATI Radeon HD 5870 (Evergreen) Architecture (2010)
3.
Zurück zum Zitat Hammond, L., Willey, M., Olukotun, K.: Data speculation support for a chip multiprocessor. In: Proceedings of the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems Hammond, L., Willey, M., Olukotun, K.: Data speculation support for a chip multiprocessor. In: Proceedings of the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems
4.
Zurück zum Zitat Steffan, J., Mowry, T.: The potential for using thread-level data speculation to facilitate automatic parallelization. In: Proceedings of the 4th International Symposium on High-Performance Computer, Architecture, pp. 2–13 (1998) Steffan, J., Mowry, T.: The potential for using thread-level data speculation to facilitate automatic parallelization. In: Proceedings of the 4th International Symposium on High-Performance Computer, Architecture, pp. 2–13 (1998)
5.
Zurück zum Zitat Liu, S., Gaudiot, J.-L.: Potential impact of value prediction on communication in many-core architectures. IEEE Trans. Comput. 58(6), 759–769 (2009)CrossRefMathSciNet Liu, S., Gaudiot, J.-L.: Potential impact of value prediction on communication in many-core architectures. IEEE Trans. Comput. 58(6), 759–769 (2009)CrossRefMathSciNet
6.
Zurück zum Zitat Liu, S., Eisenbeis, C., Gaudiot, J.-L.: Speculative execution on GPU: An exploratory study. In: 2010 39th International Conference on Parallel Processing (ICPP), pp. 453–461 sept. (2010) Liu, S., Eisenbeis, C., Gaudiot, J.-L.: Speculative execution on GPU: An exploratory study. In: 2010 39th International Conference on Parallel Processing (ICPP), pp. 453–461 sept. (2010)
7.
Zurück zum Zitat Lipasti, M.H., Shen, J.P.: Exceeding the dataflow limit via value prediction. In: Proceedings of the 29th Annual ACM/IEEE International Symposium on Microarchitecture Lipasti, M.H., Shen, J.P.: Exceeding the dataflow limit via value prediction. In: Proceedings of the 29th Annual ACM/IEEE International Symposium on Microarchitecture
8.
Zurück zum Zitat Sazeides, Y., Vassiliadis, S., Smith, J.E.: The performance potential of data dependence speculation& collapsing. In: Proceedings of the 29th Annual ACM/IEEE International Symposium on Microarchitecture Sazeides, Y., Vassiliadis, S., Smith, J.E.: The performance potential of data dependence speculation& collapsing. In: Proceedings of the 29th Annual ACM/IEEE International Symposium on Microarchitecture
9.
Zurück zum Zitat Sazeides, Y., Smith, J.E.: The predictability of data values. In: Proceedings of the 30th annual ACM/IEEE International Symposium on Microarchitecture Sazeides, Y., Smith, J.E.: The predictability of data values. In: Proceedings of the 30th annual ACM/IEEE International Symposium on Microarchitecture
10.
Zurück zum Zitat Liu, S., Eisenbeis, C., Gaudiot, J.-L.: Value prediction and speculative execution on GPU. Int. J. Parallel Programm. 11, 1-20–20 (2010) Liu, S., Eisenbeis, C., Gaudiot, J.-L.: Value prediction and speculative execution on GPU. Int. J. Parallel Programm. 11, 1-20–20 (2010)
11.
Zurück zum Zitat Gupta, M., Nim, R.: Techniques for speculative run-time parallelization of loops. In: Proceedings of the 1998 ACM/IEEE Conference on Supercomputing Gupta, M., Nim, R.: Techniques for speculative run-time parallelization of loops. In: Proceedings of the 1998 ACM/IEEE Conference on Supercomputing
12.
Zurück zum Zitat Dang, F., Yu, H., Rauchwerger, L.: The R-LRPD test: Speculative parallelization of partially parallel loops, Technical report. College Station, TX, USA (2001) Dang, F., Yu, H., Rauchwerger, L.: The R-LRPD test: Speculative parallelization of partially parallel loops, Technical report. College Station, TX, USA (2001)
13.
Zurück zum Zitat Cintra, M., Llanos, D.R.: Toward efficient and robust software speculative parallelization on multiprocessors. In: Proceedings of the 9th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming Cintra, M., Llanos, D.R.: Toward efficient and robust software speculative parallelization on multiprocessors. In: Proceedings of the 9th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
14.
Zurück zum Zitat Marcuello, P., Tubella, J., Gonzalez, A.: Value prediction for speculative multithreaded architectures. In: Proceedings of the 32nd Annual ACM/IEEE International Symposium on Microarchitecture, pp. 230–236 (1999) Marcuello, P., Tubella, J., Gonzalez, A.: Value prediction for speculative multithreaded architectures. In: Proceedings of the 32nd Annual ACM/IEEE International Symposium on Microarchitecture, pp. 230–236 (1999)
15.
Zurück zum Zitat Oplinger, J.T., Heine, D.L., Lam, M.S.: In search of speculative thread-level parallelism. In: Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques Oplinger, J.T., Heine, D.L., Lam, M.S.: In search of speculative thread-level parallelism. In: Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques
18.
Zurück zum Zitat Owens, J., Houston, M., Luebke, D., Green, S., Stone, J., Phillips, J.: GPU computing. Proc. IEEE 96(5), 879–899 (2008)CrossRef Owens, J., Houston, M., Luebke, D., Green, S., Stone, J., Phillips, J.: GPU computing. Proc. IEEE 96(5), 879–899 (2008)CrossRef
19.
Zurück zum Zitat Jang, B., Kaeli, D., Do, S., Pien, H.: Multi GPU implementation of iterative tomographic reconstruction algorithms. In: ISBI’09: Proceedings of the Sixth IEEE International Conference on Symposium on Biomedical Imaging, pp. 185–188. IEEE Press, Piscataway, NJ, USA (2009) Jang, B., Kaeli, D., Do, S., Pien, H.: Multi GPU implementation of iterative tomographic reconstruction algorithms. In: ISBI’09: Proceedings of the Sixth IEEE International Conference on Symposium on Biomedical Imaging, pp. 185–188. IEEE Press, Piscataway, NJ, USA (2009)
23.
Zurück zum Zitat Spradling, C.D.: SPEC CPU 2006 benchmark tools. SIGARCH Comput. Archit. News 35, 130–134 (2007)CrossRef Spradling, C.D.: SPEC CPU 2006 benchmark tools. SIGARCH Comput. Archit. News 35, 130–134 (2007)CrossRef
24.
Zurück zum Zitat Bienia, C.: Benchmarking Modern Multiprocessors, Ph.D. dissertation. Princeton University, Jan. (2011) Bienia, C.: Benchmarking Modern Multiprocessors, Ph.D. dissertation. Princeton University, Jan. (2011)
27.
Zurück zum Zitat Kejariwal, A., Casçaval, C.: Parallelization spectroscopy: analysis of thread-level parallelism in hpc programs. In: Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming Kejariwal, A., Casçaval, C.: Parallelization spectroscopy: analysis of thread-level parallelism in hpc programs. In: Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
Metadaten
Titel
Aggressive Value Prediction on a GPU
verfasst von
Enqiang Sun
David Kaeli
Publikationsdatum
01.02.2014
Verlag
Springer US
Erschienen in
International Journal of Parallel Programming / Ausgabe 1/2014
Print ISSN: 0885-7458
Elektronische ISSN: 1573-7640
DOI
https://doi.org/10.1007/s10766-012-0232-7

Weitere Artikel der Ausgabe 1/2014

International Journal of Parallel Programming 1/2014 Zur Ausgabe

Premium Partner