Optimization Method on Programs Using Dependency Analysis and Loop Peeling Transformations

Assya Sellak, Dr. Clèment Aubert, School of Computer and Cyber Sciences, Augusta University, 1120 15th St, Augusta, GA 30912

Computer programs are written using high-level languages that are unable to be directly executed by computers. Therefore, the program must be translated into machine-code using compilers. Compilers perform a series of program transformation and optimizations to improve memory usage and reduce the run time of the program execution. Programs consist of commands and statements such as conditionals and loops. Loops are a powerful tool for programmers used to repeatedly run a sequence of commands until a specified condition is met. However, when used carelessly, loops can lead to never-halting or extremely slow programs. Loops can contain commands that perform unneeded residual operations instead of only being executed when necessary. This excessive performance results in an avoidable increase in runtime which may arise either because of the programmer or other automatic transformations. Detecting which operations could have been performed fewer times than the loop requires is complex, but some optimizations try to detect this and extract portions of code that only needed to run once and successively move commands that need to run more than once, but not as times as the loop runs. Thanks to quasi-interpretation (Rubiano & Moyen, Loop Quasi-Invariant Chunk Motion 2017) coming from Implicit Computational Complexity, new ways of detecting invariant sequences of commands inside loops have been developed. We extend this work along two axes: 1.We allow for more structures, including for, do...while, loops with break, to be transformed. 2. By analyzing the dependencies within the loop, we hope to allow for some parallel optimization. This allows to consider more programs and potentially significantly speed-up programs that are distributed, i.e., executed in parallel on multiple computers. In addition, we guarantee that the transformation preserves the program behavior by proving the  optimized program is functionally equivalent to the original.

Additional Abstract Information

Presenter: Assya Sellak

Institution: Augusta University

Type: Oral

Subject: Computer Science

Status: Approved

Time and Location

Session: Oral 3
Date/Time: Mon 4:30pm-5:30pm
Session Number: 345
List other presenters in this same room and session