Titelaufnahme

Titel
Parallelizing the commutation property for functions over small domains / von Markus Scherer
Weitere Titel
Parallelisierung der Kommutationseigenschaft für Funktionen über kleinen Wertebereichen
VerfasserScherer, Markus
Begutachter / BegutachterinSalzer, Gernot
ErschienenWien, 2016
Umfangxv, 51 Seiten : Diagramme
HochschulschriftTechnische Universität Wien, Univ., Diplomarbeit, 2016
Anmerkung
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers
Zusammenfassung in deutscher Sprache
SpracheEnglisch
DokumenttypDiplomarbeit
Schlagwörter (DE)Erfüllungsproblem / Zentralisatorklon / Kommutationseigenschaft
Schlagwörter (EN)Constraint Satisfaction Problems / centralizer clones / commutation property
URNurn:nbn:at:at-ubtuw:1-4018 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Parallelizing the commutation property for functions over small domains [0.69 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Funktionale und relationale Klone, das heißt Mengen von Funktionen oder Relationen, die unter einer Form von Komposition abgeschlossen sind, sind ein wichtiges Werkzeug zur Untersuchung von Eigenschaften von Algebren. Ein Verständnis von Klonen und den Beziehungen zwischen ihnen ist beispielsweise hilfreich für das Beweisen komplexitätstheoretischer Resultate für das Constraint-Satisfaction-Problem. Eine spezielle Form von Klonen sind sogenannte primitiv-positive Klone, von denen es über jedem Wertebereich nur eine endliche Anzahl gibt. Diese Klone sind theoretisch berechenbar, in der Realität ist der Suchraum allerdings in den meisten Fällen zu groß. Das Ziel dieser Diplomarbeit ist es zu untersuchen, in welchem Ausmaß Parallelisierung die Grenzen dessen, was als praktisch berechenbar gilt, erweitern kann Wir werden daher unterschiedliche Ansätze zur Berechnung von primitiv-positiven Klonen entwickeln und sie gegeneinander evaluieren. Bei den untersuchten Ansätzen handelt es sich um Parallelismus auf der Anweisungsebene, klassische Nebenläufigkeit und Grafikkartenprogrammierung. Resultat der Diplomarbeit wird, neben der Auswertung der verschiedenen Ansätze, außerdem ein Programm sein, das für Experimente im Bereich der Klontheorie genutzt werden kann.

Zusammenfassung (Englisch)

Functional and relational clones, that is sets of functions or relations closed under some form of composition, are an important tool for investigating properties of algebras. Understanding clones and the relation between them can for example help us to prove complexity-theoretic results for Constraint Satisfaction Problems. A special form of clones are so-called primitive positive clones, of which there are only finitely many over each domain. These clones are computable in principle, but in reality the search space too huge in most cases. The aim of this thesis is to investigate to what extent parallelization can push the boundaries of what is thought to be practically computable. We will therefore develop different parallel approaches to calculate primitive positive clones - using instruction level parallelism, classical multithreading and GPU programming - and evaluate them against each other. Result of this thesis will be, in addition to the evaluation of the different approaches, a program which can be used for experiments in the context of clone theory.