University of Patras
Παράλληλοι αλγόριθμοι και εφαρμογές σε πολυπύρηνες μονάδες επεξεργασίας γραφικών
Abstract
dc:descriptionIn this thesis, parallel algorithms and applications in manycore graphics processing units are presented. More specifically, we examine methods of designing a parallel algorithm for solving both simple and common problems such as sorting, and computationally demanding problems, so as to fully exploit the enormous computing power of modern graphics processing units (GPUs). First problem considered is sorting, which is one of the most common problems in computer science. It exists as an internal problem in many applications. Therefore, sorting faster, results in better performance in general. Chapter 3 describes all design options for the implementation of a sorting algorithm for integers, count sort, on a graphics processing unit. The elimination of thread synchronization in the last step of the algorithm had a significant effect on the performance. Chapter 4 addresses the examination timetabling problem for Universities, which is a combinatorial optimization problem. A hybrid evolutionary algorithm, which runs entirely on GPU, was used to solve the problem. The tremendous computing power of GPU and parallel programming enable the use of large populations in order to explore better the solution space and get better quality results. In the next chapter, the problem of motion planning for underwater vehicle manipulator systems is examined. In the gross motion planning problem, it is important to achieve a good solution with high accuracy. The parallel algorithm used for the representation of the working environment in a Bump-surface is a step towards this direction. In the local motion planning problem, which is a real-time problem, the time needed to find the next configuration of the vehicle is crucial. Parallel programming and the GPU greatly assist in this online problem. Last application considered is the atomistic Monte Carlo simulation of semifluorinated alkanes. The parallelization of part of the algorithm, the most time-consuming, enabled the study of a much larger system in an acceptable execution time. In general, it becomes obvious that parallel programming and new novel manycore architectures, such as graphics processing units, give new capabilities for solving every-day problems, real time and combinatorial optimization problems.
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 2014
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Kolonias, Vasileios
- Κολώνιας, Βασίλειος
Subjects
dc:subject × 20- Παράλληλος προγραμματισμός
- Πολυπύρηνα συστήματα υπολογιστών
- Μονάδες επεξεργασίας γραφικών
- Count sort
- Χρονοπρογραμματισμός εξετάσεων πανεπιστημίων
- Εξελικτικοί αλγόριθμοι
- Σχεδιασμός κίνησης
- Μοριακή προσομοίωση
- Monte Carlo
- Parallel programming
- Μanycore architectures
- Graphics processing units (GPUs)
- Examination timetabling problem
- Evolutionary algorithms
- Motion planning
- Molecular simulation
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/35234