Abstract
dc:descriptionThis thesis offers some insight into the automatic parallelization of loops by introducing and describing a source-to-source parallelizing compiler developed from scratch called C2μTC/SL. Once basic notions and ideas on the field of automatic parallelization have been introduced, the SVP system is described in great detail. It is a novel proposal on multi-core architectures and is what C2μTC/SL targets as output. The SVP is a novel design for a multi-threaded processor that can be bundled together with an OS-on-chip as part of the chip's ISA (Instruction Set Architecture). Several of those SVP cores together form a microgrid. The programming paradigm followed by the microgrid is that of a family of threads. Each family executes independently and all the threads belonging in such a family run in parallel. A thread can create more ad-hoc families so a whole hierarchy of families can exist at any given time. Synchronization is achieved by a series of synchronizing channels that can carry information from one thread in the family to its neighbors. The whole system can revert back to complete sequential execution once all resources are taken. Two programming languages were created for the high level programming / abstraction layer of the SVP: μTC and SL. Both are explained later in the text however they both are extensions of the basic C language. They extend the language with a series of directives for the creation and execution of families of threads.The C2μTC/SL source-to-source compiler is described afterwards: its purpose is to take as input any legacy C code and transform it into a parallel SL program. Originally its output was the μTC language but with the advent of SL it changed to that, hence the name C to μTC / SL (C2μTC/SL). The compiler’s main target constructs are loops since a loop is where most of the execution time of an application takes place. Since SVP works with families of threads that resemble single-dimentional loops, transforming any kind of loop into a meaningful construct for the SVP is an important step. For that reason, loops are divided into single-dimensional and multi-dimensional ones with each category requiring a different transformation method.Single-dimentional loops are further categorized by the number of the so-called loop carried dependencies that they have and are treated accordingly. Loops with no dependencies are just translated simply into parallel families. Loops with dependencies utilize the SVP’s synchronizing channels to transfer data from one thread to the next in a dataflow manner. This action alleviates the weight of each thread having to access the global memory for a particular piece of data since whatever it needs is simply transferred over via the synchronizing / shared channel. Once each thread finishes computation it pushes all relevant data back to the shared channel for use by the next thread. The combination of parallel executing independent data-flows (data-chains) and the synchronizing channel to reduce accesses to the main global memory brings tremendous increases in speedup and efficiency.Multi-dimensional loops are also subcategorized into two groups. The first group is the one that contains no dependencies. Again each loop of the loop nesting is simply transformed to a fully parallel family and it is up to the SVP to run the code effectively. The second and most interesting group contains the perfect loop nestings with a static dependency vector. Lamport’s hyperplane idea is applied in this case however there is a novelty: Instead of precomputing any loop transformation, it is up to the run-time environment to intuitively follow the dependency vector over the index space and discover the different hyperplanes per cycle. This novel idea gave birth to our first run-time algorithm: The fixed-size algorithm. It has the ability to apply the hyperplane idea, discovered while running the actual computation code, into the various tiles of a fixed size which divide the innermost dimension of the loop. The fixed size algorithm proved to work properly, however for optimal or even good results the size of the tile was needed to be known beforehand, effectively making the whole algorithm not particularly useful except as a stepping stone and also a great tool for comparisons.This glaring weakness of the Fixed-Size algorithm was covered by its evolutionary “descendant”: the Self-Adaptive algorithm. Working on the same principles as the Fixed-Size one, it can, at run-time, determine the optimal tile size to use at any given computation cycle by reducing it or increasing it according to the current needs.Experimental results indicate that not only the Self-Adaptive algorithm fares very well with near-optimal results when compared with the Fixed-Size one, it is also shown that for that particular type of parallelism (run-time execution of parallel families discovered on the spot) the results obtained are the best possible results that can be obtained. The algorithms were also compared with a standard compile-time method (the hyperplane method) and it was found that their speedup is relatively close to each other. This combined with the versatility offered by a run-time system (like dealing with irregular index spaces) makes the Self-Adaptive algorithm especially appealing.
Degree
thesis:*- Grantor dc:publisher
- University of Ioannina
- Year dc:date
- 2014
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Saougkos, Dimitrios
- Σαούγκος, Δημήτριος
Subjects
dc:subject × 16- Αυτόματος παραλληλισμός
- Βρόχοι
- Μεταφραστές
- Παράλληλη επεξεργασία
- Automatic parallelization
- Loops
- Compilers
- Parallel processing
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Natural Sciences
- Computer and Information Sciences
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/39700