University of Peloponesse
Ανάλυση της απόστασης επαναχρησιμοποίησης δεδομένων σε επίπεδο πηγαίου κώδικα για την βελτιστοποίηση της τοπικότητας αναφοράς σε αλγορίθμους όπου κυριαρχούν βρόχοι επανάληψης
Abstract
dc:descriptionThis Ph.D. dissertation discusses a software profiling and optimization tool that infers source code optimizations for algorithms implemented in high level languages like C and MATLAB. Reuse distance analysis forms the main part of the optimization process. C has already been extensively used as the input specification on most similar systems. MATLAB is a high level array programming language used broadly for prototyping algorithms in scientific and engineering settings. Reuse distance analysis is the process of calculating the number of distinct data elements accessed between two consecutive uses of the same memory element during program execution. The notion of reuse distance is equivalent to temporal data reuse but in a machine independent manner. Reuse distance analysis provides quantitative measures of program locality that can be used to drive locality optimization. The optimizations proposed by the tool are mainly loop transformations which target the reduction of reuse distances and thus the improvement of temporal locality, the reduction of data cache misses and the improvement of the execution speed of a specific program. A framework for the efficient development of code analysis software has also been developed. This framework includes a tool for automatically generating the front end of analysis tools for a given language grammar expressed in the BNF notation. It also provides a domain specific language to concisely express queries on the internal representation generated by the front end. This language tackles the problem of writing complex code in a general purpose programming language in order to retrieve information from the internal representation. Both tools of this framework have been developed and used primarily for the construction of the proposed optimization tool. The required reuse distance analysis is always performed at C code level. To support MATLAB input sources, a MATLAB-to-C compiler has been developed. This compiler can relate the input MATLAB variables with output C code. Then reuse distance analysis is performed on the C code and the relevant optimization proposals are mapped back to the input MATLAB code. A thorough performance evaluation (in terms of execution time and cache performance) has been performed on six different algorithms that were optimized using the proposed tool. Measurements have been carried out on four different processors with ARM, MIPS and x86 ISAs and different memory hierarchies but also using a memory simulator. The results show that a reduction of memory accesses up to 42% has been achieved, leading to a speedup up to 3x for locality related optimizations and up to 68x for optimizations regarding the reduction of recomputations. Furthermore, the C code generated from the optimized MATLAB code, using MathWorks MATLAB Coder, is also optimized compared to the code that is generated from the original MATLAB code.
Degree
thesis:*- Grantor dc:publisher
- University of Peloponesse
- Year dc:date
- 2018
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Lezos, Christakis
- Λέζος, Χρηστάκης
Subjects
dc:subject × 14- Απόσταση επαναχρησιμοποιήσης δεδομένων
- Βελτιστοποίηση τοπικότητας αναφοράς δεδομένων
- Μετασχηματισμοί βρόχων επανάληψης
- Μεταγλωττιστές
- Αυτόματη παραγωγή κώδικα
- Reuse distance analysis
- Data locality optimization
- Source-to-source optimizing transformations
- Compiler generators
- source code analysis
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/45200