Τα γραφικά στην σημερινή κοινωνία της «Πληροφορίας» παίζουν σημαντικό ρόλο και είναι από τους τομείς που δαπανούνται υπέρογκα ποσά για τη βελτίωση τους. Για να καταλάβουμε τη σημαντικότητα του ρόλου τους αρκεί να αναφέρουμε τους τομείς στους οποίους βρίσκουν εφαρμογή: -Αλληλεπίδραση με το χρήστη -Σχεδιασμός στις επιχειρήσεις, στην επιστήμη και στην τεχνολογία -Αυτοματισμοί γραφείου και ηλεκτρονικές εκδόσεις -Ο υπολογιστής σαν βοήθημα στη σχεδίαση -Εξομοίωση και “animation” για επιστημονικές απεικονίσεις και διασκέδαση -Τέχνη και εμπόριο -Διεξαγωγή ελέγχου -Βοήθημα για εκμάθηση -Χαρτογραφία -Διασκέδαση Ένα από τα στάδια λειτουργίας μιας μηχανής παραγωγής 3D γραφικών, το Rendering, που είναι ένα από τα πιο απαιτητικά σε ισχύ στάδια της, μπορεί και γεμίζει με χρώμα κάθε Pixel της οθόνης ανάλογα με τη 3D εικόνα που θέλουμε να παρουσιάσουμε στην οθόνη του υπολογιστή. Το στάδιο αυτό απαιτεί εκατοντάδες χιλιάδες υπολογισμούς και προσπελάσεις μνήμης το δευτερόλεπτο -για rendering πραγματικού χρόνου- συνεπώς απαιτεί σημαντική ποσότητα ισχύος. Η εφαρμογή της παραγωγής γραφικών 3D σε συσκευές που απαιτούν χαμηλή κατανάλωση ισχύος, όπως PDA, κινητά τηλέφωνα και άλλες φορητές συσκευές, έχει δημιουργήσει την ανάγκη για μείωση της κατανάλωσης ισχύος. Το Clipping αποτελεί ένα από τα πέντε στάδια του Geometry Stage για την παραγωγή γραφικών. Το στάδιο αυτό το εφαρμόζεται για να καθοριστεί το μέρος της εικόνας το οποίο θα είναι ορατό μέσα σε μια δεδομένη περιοχή -το ορατό παράθυρο- γνωστή και ως viewing frustum ή viewport και να αποκοπούν εκείνα τα αντικείμενα που βρίσκονται έξω από αυτή. Αυτό που επιτυγχάνεται επομένως είναι να γίνεται rasterization μόνο στην ορατή περιοχή και αυτό είναι το βασικό πλεονέκτημα της χρήσης του Clipping. Επιτυγχάνεται καλύτερη απόδοση καθώς το στάδιο του rasterization είναι ιδιαίτερα απαιτητικό και μέσω του clipping βοηθάμε στην μείωση των αντικειμένων που θα απεικονισθούν άρα και στους μελλοντικούς υπολογισμούς και στην κατανάλωση ενέργειας. Ο αλγόριθμος N-L-N είναι ένας από τους βασικούς αλγορίθμους που χρησιμοποιούνται ευρέως στον τομέα των 2D γραφικών καθώς αποφεύγει τις εξωτερικές τομές (τομές μεταξύ του ΑΒ και των προεκτάσεων των πλευρών του παραθύρου) διαιρώντας το χώρο σε περισσότερες από τον C-S (Cohen-Sutherland) περιοχές, έχει τις λιγότερες διαιρέσεις και τις λιγότερες συγκρίσεις (1/3 από τον C-S και 1/2 από τον L-B (Liang-Barsky) [2] ) άρα είναι ο πιο ταχύς και αποδοτικός και συνεπώς ο πιο επιθυμητός σε 2D περιβάλλοντα. Όμως πολύ μικρό ποσοστό των γραμμών υπόκεινται Clipping -μόλις το 6% κατά μέσο όρο [1]- έτσι για τη βελτίωση του αλγορίθμου επικεντρωθήκαμε στα προηγούμενα στάδια (μέχρι την απόφαση να κάνουμε Clip).Πιο συγκεκριμένα στο [1] υποστηρίζεται ότι τα 8/9 των γραμμών αυτών υπόκεινται “Reject” αφού είναι εξ’ολοκλήρου εκτός του ορατού παραθύρου και μόνο το 1/9 “Accept” ή “Clip”. Για το λόγο αυτό δημιουργήθηκε ο QuickClip, ένας αλγόριθμος που στοχεύει στο πολύ γρήγορο reject ενός μεγάλου αριθμού γραμμών, όχι όμως όλων όσων πρέπει να υποστούν reject. Σκοπός λοιπόν του προτεινόμενου αλγορίθμου είναι να επιτευχθεί “Full Reject” (δηλαδή απόρριψη όλων των γραμμών που δεν είναι εξ’ ολοκλήρου ορατές) με όσο το δυνατόν λιγότερες πράξεις. Ο Quick Clip στη χειρότερη περίπτωση, μπορεί να κάνει έως και 3 άσκοπα Clipping, πριν αποφασίσει να αποκλείσει τη γραμμή. Αυτές οι άσκοπες πράξεις είναι κάτι ανεπιθύμητο, που προσπαθήσαμε να ελαχιστοποιήσουμε στον αλγόριθμό μας. Η οπτική γωνία από την οποία ο N-L-N αλγόριθμος αντιμετωπίζει το Clipping και o μηχανισμός των κλίσεων που χρησιμοποιεί μας βοήθησε στην δική μας υλοποίηση. Αφού μελετήσαμε και κατανοήσαμε την οπτική γωνία και τον τρόπο σκέψης των αλγορίθμων των οποίων η χρήση έχει επικρατήσει στη διαδικασία του Polygon και Line Clipping, διαπιστώσαμε ότι οι περισσότεροι έχουν διαφορετικές φιλοσοφίες και παρουσιάζουν μειονεκτήματα και πλεονεκτήματα. Το αποτέλεσμα ήταν η προσπάθεια σχεδίασης ενός αλγορίθμου, που εκμεταλλεύεται τα θετικά στοιχεία, προσπαθώντας παράλληλα να λύσει τα αρνητικά. Σύμφωνα με τις μετρήσεις της υπολογιστικής πολυπλοκότητας παρατηρούμε ότι κάνει λιγότερες πράξεις κυρίως στις περιπτώσεις απόρριψης των γραμμών (¨Full Reject¨), αλλά και αποδοχής (¨Full Accept¨) από τους κυρίαρχους αλγορίθμους. Επίσης σε συνολικό επίπεδο, ακόμα και στην χειρότερη περίπτωση (¨Worst case¨) όπου απαιτούνται οι περισσότερες πράξεις είναι ανταγωνιστικός με τους αλγόριθμους N-L-N και Quickclip. Σε συνδυασμό με τις μετρήσεις που έχουν προηγηθεί μεταξύ των αλγορίθμων που έχουν επικρατήσει ως τώρα στο Clipping ([1],[2],[3],[4],[5],[7]) μπορούμε να ισχυριστούμε ότι ο προτεινόμενος είναι ένας αλγόριθμος που θα είναι αποδοτικός λόγω των λιγότερων πράξεων του σε Low Power κατασκευές. Συμπερασματικά λοιπόν αναφέρουμε ότι συγκριτικά με τους αλγορίθμους N-L-N και Quickclip μειώθηκαν οι απαραίτητοι υπολογισμοί και ειδικά στην περίπτωση των εξ’ολοκλήρου απορρίψεων (“Full Reject”) όπου δόθηκε ιδιαίτερη έμφαση. Αυτό προήλθε από την παρατήρηση ότι τα 8/9 των γραμμών υπόκεινται “Reject” αφού είναι εξ’ολοκλήρου εκτός του ορατού παραθύρου και μόνο το 1/9 “Accept” ή “Clip”. Έτσι η πολυπλοκότητα της διαδικασίας αυτής μειώνεται, κάτι χρήσιμο σε αυτό το πρώιμο στάδιο των γραφικών. Ο προτεινόμενος αλγόριθμός μπορεί να φανεί χρήσιμος σε συσκευές που έχουν ανάγκη από χαμηλή κατανάλωση ενέργειας και μικρή επιφάνεια. Ο σχεδιασμός του αλγορίθμου έχει γίνει για δισδιάστατο περιβάλλον (2D), χωρίς όμως να αποκλείεται και τρισδιάστατη (3D) επέκτασή του. Με την κατάλληλη Low power και Low area υλοποίηση σε VLSI θα δώσει ένα αποτέλεσμα χαμηλής κατανάλωσης ενέργειας αλλά και μικρής επιφάνειας, στοιχεία που είναι καίρια για mobile συσκευές. Οι αλγόριθμοι του point clipping υλοποιήθηκαν σε γλώσσα προγραμματισμού C με την προσθήκη μιας εφαρμογής που αναπαριστά γραφικά τις γραμμές πριν και μετά το στάδιο του clipping. Κατόπιν έγινε καταγραφή σε VHDL μιας ενδεικτικής αρχιτεκτονικής του προτεινόμενου αλγορίθμου ώστε να δειχθεί ότι είναι υλοποιήσιμος σε VLSI. / Graphics in the society of "Information" play an important role, as they are one of the sectors where great sums of money are consumed for their improvement. In order to understand the importance of their role it is enough to mention the sectors in which they are applied: - Interaction with the user - Planning in enterprises, science and technology - Office automations and electronic publications - The computer as an aid in designing - Simulation and "animation" for scientific representations and entertainment - Art and trade - Conduct of control - Aid in learning - Cartography - Entertainment One of the stages of a 3D graphics production machine, Rendering, which is one of the most demanding in power, fills with color each Pixel of the screen depending on the 3D picture that we want to present in the screen of the computer. This stage requires hundreds of thousands calculations and memory accesses per second - for real time rendering -, so it requires an important quantity of power. The implementation of 3D graphics production at devices that require low consumption of power, as PDAs, mobile phones and other portable devices, has created the need of reducing the power consumption. The Clipping stage is one of the five stages of Geometry Stage in the graphics production. This stage is applied in order to determine the part of the picture that will be visible in a given region - called the visible window -also known as viewing frustum or viewport and cut away those objects that are detected outside this region. Consequently what is achieved is applying rasterization only in the visible region which is the main advantage of using Clipping. Better performance is achieved as the rasterization stage is too demanding and clipping helps the reduction of objects that will be drawn, hence the reduction of the future calculations and the consumption of energy. Algorithm N-L-N is one of the basic algorithms that are used widely in the section of 2D graphics as it avoids the exterior traces (traces between the AB line segment and the extensions of the sides of the window) dividing the space in more regions than the C-S (Cohen-Sutherland), it has the less divisions and less comparisons (1/3 of C-S and 1/2 of the L-B (Liang-Barsky) [ 2 ]) hence is quicker and more efficient so consequently the most desirable in 2D environments. However a very small percentage of lines is being Clipped - just the 6% in average [ 1 ] - so for the improvement of the algorithm we are focused in the previous stages (up to the decision of making Clipping). Specifically in [ 1 ] is mentioned that the 8/9 of this lines are being "Rejected" as being wholly outside the visible window and only the 1/9 are being "Accepted" or "Clipped". For this reason the QuickClip algorithm was created, a algorithm that aims in the very fast rejection of a large amount of lines, no however all of which should go through rejection. Aim of the proposed algorithm is to achieve "Full Reject" (that is to say reject of all lines that is not entirely visible) with as less operations as possible. The QuickClip algorithm at the worst case, will make up to 3 unnecessary Clippings, before deciding to exclude the line. These pointless operations are undesirable, that we tried to minimize in the proposed algorithm. The way which the N-L-N algorithm faces Clipping and the mechanism of slopes that it uses helped us in our implementation. After we studied and comprehended the ideas and the ways of the algorithms of which the use has dominated in the process of Polygon and Line Clipping, we realized that most have different philosophies and have disadvantages and advantages. The result was the effort of designing an algorithm that takes advantage of the positive elements, trying at the same time to reduce the negatives. According to the measurements of calculating complexity we observe that it mainly makes less operations in the cases of rejecting lines (¨Full Reject¨), but also acceptance (¨Full Accept¨) from the dominant algorithms. Also in a overall level, even in the worst case (¨Worst case¨) where the most operations are required is competitive with the algorithms N-L-N and QuickClip. In combination with the measurements that have preceded between the algorithms that have dominated until now in Clipping ([1], [2], [3], [4], [5], [7 ]) we can claim that the proposed algorithm will be efficient in Low Power devices because of the less operations. Deductively therefore we report that comparatively with the algorithms N-L-N and QuickClip the necessary calculations were decreased and specifically in the case of wholly rejected lines ("Full Reject") where proper emphasis was given. This came from the observation that the 8/9 of lines that go through "Reject" while they are wholly outside the visible window and only the 1/9 go through "Accept" or "Clip". Thus the complexity of this process is decreased, something useful in this early stage of graphics' pipeline. The proposed algorithm can be useful in devices that have the need of low consumption of energy and small surface. The planning of the algorithm has become for two-dimensions environment (2D), without however excluding the three-dimensions (3D) extension. With the suitable Low power and Low area implementation in VLSI it will give a result of low consumption of energy but also small surface, elements that are vital for mobile devices. The algorithms of point clipping were written in C Code with the addition of an application that represent graphically the lines before and afterwards the stage of clipping. Then a suggestive architecture of the proposed algorithm was designed in VHDL so as to show that it can be implemented in VLSI.

Στην παρούσα διπλωματική, κύριος στόχος ήταν η παραλληλοποίηση ενός αλγορίθμου σχεδιασμού κίνησης για κάρτες γραφικών. Για το σκοπό αυτό, χρησιμοποιήθηκε ο Probabilistic Road Map (PRM), ένας αλγόριθμος που προσφέρει μεγάλο βαθμό παραλληλισμού και, συνεπώς, προτείνεται για υλοποίηση σε πολυπύρηνους επεξεργαστές. Το πλαίσιο εργασίας που χρησιμοποιήθηκε για τον προγραμματισμό στην κάρτα γραφικών ήταν το OpenCL επειδή προσφέρει ένα αφαιρετικό επίπεδο προγραμματισμού ανεξαρτήτως υλικού και μπορεί να μεταφερθεί σε κάρτες γραφικών από διαφορετικούς κατασκευαστές. Ο αλγόριθμος αποσυντέθηκε στα δομικά του μέρη και καθένα από αυτά μελετήθηκε ξεχωριστά, ώστε να παραλληλοποιηθεί. Κατά τη διαδικασία αυτή, λοιπόν, υλοποιήθηκαν οι εξής αλγόριθμοι: • Ταξινόμηση • Αναζήτηση Γράφου κατά Πλάτος • Κατακερματισμός • Αναζήτηση Κοντινότερων Γειτόνων Οι παραπάνω αλγόριθμοι έχουν γραφτεί με τέτοιο τρόπο ώστε να μπορούν να χρησιμοποιηθούν αυτόνομα, ως ξεχωριστά κομμάτια. / In this thesis work, the main objective was the parallelization of a motion planning algorithm for graphics card units. For this purpose, the Probabilistic Road Map (PRM) was chosen, an algorithm that offers a high degree of parallelism and, consequently, is suggested for implementation in many core processing units. The framework used for GPU programming was OpenCL because it provides an abstraction programming layer independent of hardware and is portable among GPUs. The algorithm was decomposed in its structural components and each one of them was processed indepedently with the purpose of massive parallelization. During this process, the following algorithms were implemented: • Sorting • Breadth First Traversal • Hashing • Nearest Neighbours Search The above algorithms have been written in such a way so that they can be used as separate parts.

Στην παρούσα διπλωματική εκπονείται μία μελέτη για την απόδοση των αλγορίθμων αναζήτησης μοτίβων όταν αυτοί τροποποιηθούν κατάλληλα ώστε να εκμεταλλεύονται την αρχιτεκτονική του Υλικού των καρτών γραφικών. Για τον σκοπό αυτό στην παρούσα διπλωματική παρουσιάζεται στην αρχή το πρόβλημα της αναζήτησης ώστε να γίνει κατανοητό γιατί είναι επιτακτική η ανάγκη βελτιστοποίησης της απόδοσης των υπαρχόντων αλγορίθμων. Επίσης παρουσιάζονται οι κυριότεροι αλγόριθμοι αναζήτησης μοτίβων που χρησιμοποιούνται σήμερα και εξηγείται γιατί επιλέγεται ένας από αυτούς τους αλγόριθμους που στην συνέχεια θα τροποποιηθεί ώστε να εκμεταλλεύεται την ιδιαίτερη αρχιτεκτονική μιας κάρτας γραφικών. Έπειτα εξάγονται συμπεράσματα για την απόδοση που μας προσφέρει αυτή η νέα υλοποίηση του αλγορίθμου σε λογισμικό σε σχέση με την απλή υλοποίηση του αλγορίθμου και για διαφορετικά μεγέθη εισόδων / Conversion of Aho-Corasick algorithm in order to execute in an Nvidia graphic card using CUDA technology. Comparison of speed between the parallel and the classic version of the algorithm.

Μια γρήγορη επίλυση του Delaunay Τριγωνισμός (DT) πρόβληματος αποτελεί ένα από τα βασικά συστατικά σε πολλές θεωριτικές και πρακτικές εφαρμογές. Οι υπάρχουσες μονάδες επεξεργασίας γραφικών (GPU), με βάση τις εφαρμογές των αλγορίθμων DT πάσχουν από δύο σοβαρά μειονεκτήματα. Το πρώτο σχετίζεται με την εξάρτηση του αλγορίθμου καθοδήγηση της GPU από την CPU για τους υπολογισμούς. Το δεύτερο πιο σοβαρό μειονέκτημα είναι η εξάρτησή τους από τη διανομή του σημειοσύνολου εισόδου. Οι περισσότεροι αλγορίθμοι για GPU έχουν καλή απόδοση μόνο με ομοιόμορφες κατανομές σημειοσύνολον. Προτείνουμε ένα καινούριο αλγόριθμο που δεν πάσχουν από τα παραπάνω προβλήματα. / A Fast solver of Delaunay Triangulation (DT) problem constitutes one of the basic ingredients in many practical and sientific applications. Existing Graphics Processing Units (GPU) based implementations of DT algorithms suffer from two serious drawbacks. The first is related to the dependency of the CPU guidance algorithm on GPU calculations. Albeit the modern GPUs have high computational throughput, if the feedback from CPU is necessary for the algorithmic evolution, the overhead caused by CPU-GPU communication can seriously degrade the performance. The second most serious drawback is their dependency on the distribution of the given point-set. Most of the GPU-based implementations can optimally run only on uniformly distributed point-sets, however, in many practical applications this is not the case.

Οι προγραμματιζόμενοι επεξεργαστές γραφικών (Graphics Processing Units - GPUs), είναι πανίσχυροι παράλληλοι επεξεργαστές και πλέον υπάρχουν σε κάθε σύγχρονο προσωπικό υπολογιστή (PC). Οι GPUs αναλαμβάνουν κι επιταχύνουν την σχεδίαση δισδιάστατων και τρισδιάστατων γραφικών στην οθόνη του υπολογιστή. Η εξέλιξή τους είναι τόσο ραγδαία τα τελευταία χρόνια, που πλέον ξεπερνούν σε πολυπλοκότητα τις σύγχρονες κεντρικές μονάδες επεξεργασίας (CPUs), ενώ είναι ικανές να επιταχύνουν εκτός από γραφικά κι άλλες απαιτητικές σε επεξεργαστική ισχύ εφαρμογές, όπως είναι η τεχνητή νοημοσύνη και η προσομοίωση φυσικών αλληλεπιδράσεων μεταξύ αντικειμένων (συγκρούσεις, εκρήξεις, προσομοίωση κίνησης υγρών) κ.α. Σκοπός της συγκεκριμένης εργασίας είναι η δημιουργία, η μελέτη και η βελτιστοποίηση αλγορίθμων σκίασης με χρήση GPUs. Ο όρος σκίαση (shading) αναφέρεται στην αλληλεπίδραση του φωτός με τα αντικείμενα ενός εικονικού περιβάλλοντος. Παρουσιάζονται τα εργαλεία (APIs) και οι γλώσσες προγραμματισμού των GPUs καθώς και τρόποι βελτιστοποίησης της εκτέλεσης των σκιάσεων που είναι ένα θέμα μείζονος σημασίας σε προσομοιώσεις πραγματικού χρόνου. / Graphics processing units (GPUs), are powerful parallel processors and today are found in every modern Personal Computer (PC). The GPUs accelerate the drawing of two and three dimensional graphics on the monitor of the PCs. The evolution of this hardware is very rapid the last decade and today these circuits are more complex than CPUs. They are capable of accelerating many demanding applications except graphics, like Artificial Intelligence and Physics Simulation. The purpose of this thesis is to implement, study and optimize the execution of shading algorithms that run on GPUs in real time. The term shading refers to the interactions between light and the material of every object in a virtual three dimensional environment. In this thesis we present the tools, the programming languages and techniques for optimizing the execution of the shaders which is a matter of major importance in real time simulations.