Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/16097
Title: Επιτάχυνση Της Εύρεσης Της Κυκλικής Αναπαράστασης Συνόλων Μερικής Διάταξης «poset» Με Χρήση Gpu.
Authors: Νεοκλής Χατζηγεωργίου
Κοζύρης Νεκτάριος
Keywords: εικασία ssu
κυκλική διάταξη
σύνολα μερικής διάταξης
poset
εύρεση poset διάστασης 1 και 2
εύρεση μη συνεκτικών poset
κατηγοριοποίηση poset
επιταχυντές γραφικών
gpu
cuda
conjecture ssu
circle order
partially ordered set
check poset dimension 1 or 2
classification of posets
graphic accelerator
Issue Date: 29-Jul-2011
Abstract: Στη διπλωματική μας μελετούμε την εικασία Sydney, Sydney και Urrutia περί κυκλικής αναπαράστασης των συνόλων μερικής διάταξης. Πιο συγκεκριμένα, ακολουθούμε την μεθοδολογία Bayon, Lygeros και Sereni, οι οποίοι απέδειξαν ότι όλα τα σύνολα μερικής διάταξης τάξης 10, έχουν κυκλική αναπαράσταση. Το αποτέλεσμα αυτό επιτεύχθηκε με γενετικό αλγόριθμο. Στην εργασία μας παραλληλίσαμε τον αλγόριθμό τους μέσω χρήσης καρτών γραφικών GPGPU με το προγραμματιστικό μοντέλο CUDA με στόχο να λειτουργεί με τις κάρτες TESLA με αρχιτεκτονική FERMI. Η υλοποίησή μας εφαρμόστηκε στα σύνολα μερικής διάταξης τάξης 11 και βρίσκεται σε εξέλιξη όσον αφορά στην υπολογιστική επίλυση των κυκλικών αναπαραστάσεων.In our work, we study Sidney, Sidney and Urrutia Conjecture on circle representation of partially ordered set. More specifically, we follow the methodology of Bayon, Lygeros and Sereni, who proved that all the posets of order 10, have circle representation. This result was achieved by genetic algorithm. In our work, we parallelized the algorithm through the use of graphics cards with GPGPU CUDA programming model designed to work with the cards TESLA architecture FERMI. The implementation was applied to posets of order 11 and is ongoing in terms of computational resolution of circle representations.
URI: http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/16097
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File Description SizeFormat 
DT2011-0198.doc8.27 MBMicrosoft WordView/Open
DT2011-0198.pdf3.81 MBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.