University of Patras
Μεθοδολογία ανάπτυξης μεταγλωττιστών με εκμετάλλευση της δομής του λογισμικού και του μοντέλου του υλικού
Abstract
dc:descriptionThe existing state of the art (SOA) compilers, have 3 major disadvantages. Firstly, the back-end compilerphases - subproblems (e.g. transformations, scheduling, register allocation) are optimized separately;these subproblems depend on each other and they should be optimized together as one problem and notseparately. Secondly, the existing SOA compilers do not effectively utilize the software characteristics(e.g. algorithm structure, data reuse). Thirdly, they do not effectively utilize the hardware parameters.In this PhD dissertation, new methodologies have been developed speeding up software kernels,by solving the sub-problems of finding the schedules with the minimum numbers of i) L1 data cacheaccesses, ii) L2 data cache accesses, iii) main memory accesses and iv) addressing instructions, as oneproblem and not separately. This is achieved by fully exploiting the software information and the memoryhierarchy parameters. This is the first time a methodology optimizes the above sub-problems in this way.The proposed methodologies fully utilize the software characteristics. The algorithm structure (e.g.FFT data flow graph consists of butterfly operations while the gauss blur algorithm consists of array maskoperations), the algorithm individual characteristics (e.g. symmetry of Toeplitz matrix), the data patterns(e.g. matrix elements are multiplied by a mask), data reuse, production-consumption of intermediateresults and algorithm's parallelism, are utilized as one problem and not separately.The proposed methodologies fully utilize the major architecture parameters. The memory architecture(e.g. shared L2/L3 cache), the size of the register file, the number of the levels of data cachehierarchy, the data cache sizes, the data cache associativities, the data cache line sizes, the number ofthe function units, the number of the function units can run in parallel and the number of the CPU coresare utilized as one problem and not separately. By utilizing the hardware and software constraints theexploration space is orders of magnitude decreased.In this PhD dissertation, new speeding-up methodologies are developed for i) Matrix Matrix Multiplication(MMM) algorithm, ii) Matrix Vector Multiplication (MVM) algorithm, iii) Fast Fourier Transform(FFT), iv) Canny algorithm and Hough Transform. Also, a new compilation methodology whichfully exploits the memory architecture and the software characteristics, is developed. This methodologycan be applied in software kernels whose i) execution paths are known at compile time and thus they donot depend on the data, ii) all array subscripts are linear equations of the iterators (which in most casesdo). The above methodologies refer to both embedded and general purpose processors (usage of theSIMD technology). The summary of the above methodologies is given below.A Methodology for speeding-up Matrix Matrix Multiplication (MMM) algorithm: A new methodologyfor Matrix Matrix Multiplication using SIMD (Single Instruction Multiple Data) unit and not, at oneand more cores having a shared cache, is presented. The proposed methodology partitions the MMMmatrices into smaller sub-matrices fitting in the data cache memories and into register file according tothe memory hierarchy architecture parameters. This is the first time for MMM algorithm that equationscontaining the data cache associativity values, are given. To fully utilize the memory hierarchy, a newthe data array layout is proposed. The proposed methodology is from 1.1 up to 3.5 times faster than oneof the SOA software libraries for linear algebra, ATLAS.A Fast Fourier Transform (FFT) speeding-up methodology: A new Fast Fourier Transform methodology is presented which fully utilizes the individual algorithm characteristics and the memory hierarchyarchitecture parameters. FFT data flow graph (DFG) is partitioned into patterns and into sub-FFTs. Eachpattern consists of butterflies according to the number of the registers. The selection of the exact butterflieseach pattern contains, has been made by maximizing the production-consumption of the butterfliesintermediate results. Also, the patterns are executed in that order, minimizing the data reuse of the FFTtwiddle factors. The FFT data flow graph is partitioned into sub-FFTs according to the number of thelevels and the sizes of data cache. The proposed methodology is faster from 1.1 up to 1.8 times in contrastto the SOA FFT library, FFTW. This is the first time that an FFT methodology fully utilizes thememory hierarchy architecture parameters.A methodology for speeding-up Matrix Vector Multiplication (MVM) algorithm for regular, Toeplitzand Bisymmetric Toeplitz matrices: A new methodology for MVM including different types of matrices,is presented. The above matrices have a special structure, a small number of different elements and largedata reuse. The proposed methodology partitions the MVM matrices into smaller sub-matrices fitting inthe data cache memories and into register file according to the memory hierarchy architecture parameters.To fully utilize the memory hierarchy, a new data array layout is proposed. The proposed methodologyuses the standard algorithm for matrix vector multiplication, i.e. each row of A is multiplied by X.However, for Bisymmetric Toeplitz (BT) and Toeplitz (T) matrices, MVM can also be implemented byusing FFT; although in this paper we use the standard MVM algorithm, we show that for large inputsizes, the MVM using FFT performs much better. The proposed methodology achieves speedup from1.2 up to 4.4 over the SOA libraries, ATLAS.A Methodology for Speeding Up Edge and Line Detection Algorithms: A new Methodology forSpeeding Up Edge and Line Detection Algorithms focusing on memory architecture utilization is presented.This methodology achieves i) a smaller number of load/store and arithmetic instructions, ii) asmaller number of data cache accesses and data cache misses in memory hierarchy and iii) a smalleralgorithm memory size, in contrast to the SOA library of OpenCV. This is achieved by: i) utilizing theproduction-consumption of intermediate results - merging all Canny kernels to one and pipelining thekernels to comply with the data dependences, ii) reducing the number and the size of the arrays, iii)writing the data into the new reduced size arrays in a circular way, iv) applying loop tiling for the registerfile and data cache, according to the size of the memories and associativity and v) finding the data arrayslayout according to the data cache associativity. The proposed methodology achieves speedup from 1.27up to 2.2 over the OpenCV SOA library.Compilation methodology: A new compilation methodology which fully exploits the memory architectureand the software characteristics is presented. This is the first time that a methodology optimizesthe subproblems explained above as one problem and not separately, for a loop-kernel. The proposedmethodology takes as input C-code kernels and it produces new software kernels with a new iterationspace, which may not be given by applying existing compiler transformations to original code. Firstly, theexploration space is found according to the s/w characteristics; it is described by mathematical equationsand inequalities that are derived from the array subscripts, the combination of common array references,loop iterators, loop bounds and data dependences. Then, the exploration space is orders of magnitudedecreased by applying constraint propagation of the h/w and s/w parameters. The register file and the data cache sizes are fully exploited by producing register file and data cache inequalities which containi) the tiles sizes of each array, ii) the shape of each array tile. Also, new data array layouts are found,according to the data cache associativity. The final schedule is found by choosing the best combinationof the number of i) L1 data cache accesses, ii) L2 data cache accesses, iii) main memory data accessesand iv) addressing instructions. The proposed methodology is evaluated to five well-known algorithmsand speedups from 2 up to 18 over the target gcc compiler are obtained.
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 2013
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Kelefouras, Vasilios
- Κελεφούρας, Βασίλειος
Subjects
dc:subject × 20- Επαναχρησιμοποίηση δεδομένων
- Διαχείριση μνήμης
- Κρυφή μνήμη δεδομένων
- Πολυεπεξεργαστές
- Μεταγλωττιστές
- Απόδοση
- Μετασχηματισμοί
- Συσχετικότητα κρυφής μνήμης
- Data reuse
- Memory management
- Data cache memory
- Multi core
- Compilers
- Performance
- Trasformations
- Data cache associativity
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/28963