short-paper

Towards automatic restrictification of CUDA kernel arguments

Author:

Rokiatou DiarraAuthors Info & Claims

ASE '18: Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering

Pages 928 - 931

https://doi.org/10.1145/3238147.3241533

Published: 03 September 2018 Publication History

Abstract

Many procedural languages, such as C and C++, have pointers. Pointers are powerful and convenient, but pointer aliasing still hinders compiler optimizations, despite several years of research on pointer aliasing analysis. Because alias analysis is a difficult task and results are not always accurate, the ISO C standard 99 has added a keyword, named restrict to allow the programmer to specify non−aliasing as an aid to the compiler′s optimizer and to thereby possibly improve performance. The task of annotating pointers with the restrict keyword is still left to the programmer. This task is, in general, tedious and prone to errors especially since the C does not perform any verification to ensure that restrict keyword is not misplaced. In this paper we present a static analysis tool that (i) finds CUDA kernels call sites in which actual parameters do not alias; (ii) clones the kernels called at such sites; (iii) after performing an alias analysis in these kernels, adds the restrict keyword to their arguments; and (iv) replaces the original kernel call by a call to the optimized clone whenever possible.

References

[1]

E. Helal Ahmed, Feng Wu-chun, Jung Changhee, and Y. Hanafy Yasser. 2017. AutoMatch: An automated framework for relative performance estimation and workload distribution on heterogeneous HPC systems. In IEEE International Symposium on Workload Characterization (IISWC), 2017. IEEE.

[2]

Péricles Alves, Fabian Gruber, Johannes Doerfert, Alexandros Lamprineas, Tobias Grosser, Fabrice Rastello, and Fernando Magno Quintão Pereira. 2015. Runtime Pointer Disambiguation. SIGPLAN Not. 50, 10 (Oct. 2015), 589–606.

Digital Library

[3]

Lars Ole Andersen. 1994. Program Analysis and Specialization for the C Programming Language. Ph.D. Dissertation. DIKU, University of Copenhagen.

[4]

George Balatsouras and Yannis Smaragdakis. 2016. Structure-Sensitive Points-To Analysis for C and C++. Rival X. (Eds) Static Analysis. SAS 2016 (2016).

[5]

https://link.springer.com/chapter/10.1007/978-3-662-53413-7_5

[6]

Ethel Bardsley, Adam Betts, Nathan Chong, Peter Collingbourne, Pantazis Deligiannis, Alastair F. Donaldson, Jeroen Ketema, Daniel Liew, and Shaz Qadeer. 2014.

[7]

Engineering a Static Verification Tool for GPU Kernels. In Proceedings of the 16th International Conference on Computer Aided Verification - Volume 8559. Springer-Verlag, Berlin, Heidelberg, 226–242. 15

Digital Library

[8]

Ben Hardekopf and Calvin Lin. 2011. Flow-sensitive Pointer Analysis for Millions of Lines of Code. In Proceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO ’11). IEEE Computer Society, Washington, DC, USA, 289–298. http://dl.acm.org/citation.cfm?id=2190025.

Digital Library

[9]

2190075

[10]

Michael Hind. 2001. Pointer analysis: havenâĂŹt we solved this problem yet?. In Proceedings of Workshop on Program Analysis For Software Tools and Engineering. ACM, 54–61.

Digital Library

[11]

Michael Hind and Anthony Pioli. 2000. Which Pointer Analysis Should I Use? SIGSOFT Softw. Eng. Notes 25, 5 (Aug. 2000), 113–123. 347636.348916

Digital Library

[12]

Andrew Kerr, Gregory Diamos, and Sudhakar Yalamanchili. 2009. A Characterization and Analysis of PTX Kernels. In Proceedings of the 2009 IEEE International Symposium on Workload Characterization (IISWC) (IISWC ’09). IEEE Computer Society, Washington, DC, USA, 3–12.

Digital Library

[13]

Peng Li, Guodong Li, and Ganesh Gopalakrishnan. 2014. Practical Symbolic Race Checking of GPU Programs. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’14). IEEE Press, Piscataway, NJ, USA, 179–190.

Digital Library

[14]

Robert V. Lim, Boyana Norris, and Allen D. Malony. 2017. Autotuning GPU Kernels via Static and Predictive Analysis. CoRR abs/1701.08547 (2017).

[15]

arXiv:1701.08547 http://arxiv.org/abs/1701.08547

[16]

Maroua Maalej, Vitor Paisante, Fernando Magno Quinto Pereira, and Laure Gonnord. 2018. Combining Range and Inequality Information for Pointer Disambiguation. Sci. Comput. Program. 152, C (Jan. 2018), 161–184.

Digital Library

[17]

Maroua Maalej, Vitor Paisante, Pedro Ramos, Laure Gonnord, and Fernando Magno Quintão Pereira. 2017. Pointer Disambiguation via Strict Inequalities. In Proceedings of the 2017 International Symposium on Code Generation and Optimization (CGO ’17). IEEE Press, Piscataway, NJ, USA, 134–147. http: //dl.acm.org/citation.cfm?id=3049832.3049848

[18]

Reena Panda, Xinnian Zheng, Jiajun Wang, Andreas Gerstlauer, and Lizy K. John. 2017. Statistical Pattern Based Modeling of GPU Memory Access Streams. In Proceedings of the 54th Annual Design Automation Conference 2017 (DAC ’17). ACM, New York, NY, USA, Article 81, 6 pages.

Digital Library

[19]

3062320

[20]

Marc Shapiro and Susan Horwitz. 1997. Fast and Accurate Flow-insensitive Points-to Analysis. In Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’97). ACM, New York, NY, USA, 1–14.

Digital Library

[21]

Victor Hugo Sperle Campos, Péricles Rafael Alves, Henrique Nazaré Santos, and Fernando Magno Quintão Pereira. 2016. Restrictification of Function Arguments. In Proceedings of the 25th International Conference on Compiler Construction (CC 2016). ACM, New York, NY, USA, 163–173.

Digital Library

[22]

2892225

Cited By

Leong MLee KKwan BNg YLiu ZNavab NLuk WKwok K(2021)Performance-aware programming for intraoperative intensity-based image registration on graphics processing unitsInternational Journal of Computer Assisted Radiology and Surgery10.1007/s11548-020-02303-y16:3(375-386)Online publication date: 23-Jan-2021
https://doi.org/10.1007/s11548-020-02303-y

Index Terms

Towards automatic restrictification of CUDA kernel arguments
1. Computing methodologies
  1. Computer graphics
    1. Graphics systems and interfaces
      1. Graphics processors
  2. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Source code generation
  2. Software organization and properties
    1. Software functional properties
      1. Formal methods
        Automated static analysis
        Software verification

Recommendations

Restrictification of function arguments
CC '16: Proceedings of the 25th International Conference on Compiler Construction

Pointer aliasing still hinders compiler optimizations, in spite of years of research on pointer disambiguation. Because the automatic disambiguation of pointers is a difficult endeavor, several programming languages offer programmers mechanisms to ...
Dynamic points-to sets: a comparison with static analyses and potential applications in program understanding and optimization
PASTE '01: Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering

In this paper, we compare the behavior of pointers in C programs, as approximated by static pointer analysis algorithms, with the actual behavior of pointers when these programs are run. In order to perform this comparison, we have implemented several ...
Context-, flow-, and field-sensitive data-flow analysis using synchronized Pushdown systems

Precise static analyses are context-, field- and flow-sensitive. Context- and field-sensitivity are both expressible as context-free language (CFL) reachability problems. Solving both CFL problems along the same data-flow path is undecidable, which is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASE '18: Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering

September 2018

955 pages

ISBN:9781450359375

DOI:10.1145/3238147

General Chair:
Marianne Huchard
University of Montpellier, France
,
Program Chairs:
Christian Kästner
Carnegie Mellon University, USA
,
Gordon Fraser
University of Passau, Germany

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAI: ACM Special Interest Group on Artificial Intelligence
CNRS: Centre National De La Rechercue Scientifique
SIGSOFT: ACM Special Interest Group on Software Engineering
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 September 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Conference

ASE '18

Sponsor:

SIGAI
CNRS
SIGSOFT
IEEE-CS

ASE '18: 33rd ACM/IEEE International Conference on Automated Software Engineering

September 3 - 7, 2018

Montpellier, France

Acceptance Rates

Overall Acceptance Rate 82 of 337 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
168
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Leong MLee KKwan BNg YLiu ZNavab NLuk WKwok K(2021)Performance-aware programming for intraoperative intensity-based image registration on graphics processing unitsInternational Journal of Computer Assisted Radiology and Surgery10.1007/s11548-020-02303-y16:3(375-386)Online publication date: 23-Jan-2021
https://doi.org/10.1007/s11548-020-02303-y

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents