Bibliographic Metadata

Title
Parallelizing the commutation property for functions over small domains / von Markus Scherer
Additional Titles
Parallelisierung der Kommutationseigenschaft für Funktionen über kleinen Wertebereichen
AuthorScherer, Markus
CensorSalzer, Gernot
PublishedWien, 2016
Descriptionxv, 51 Seiten : Diagramme
Institutional NoteTechnische Universität Wien, Diplomarbeit, 2016
Annotation
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers
Zusammenfassung in deutscher Sprache
LanguageEnglish
Document typeThesis (Diplom)
Keywords (DE)Erfüllungsproblem / Zentralisatorklon / Kommutationseigenschaft
Keywords (EN)Constraint Satisfaction Problems / centralizer clones / commutation property
URNurn:nbn:at:at-ubtuw:1-4018 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Parallelizing the commutation property for functions over small domains [0.69 mb]
Links
Reference
Classification
Abstract (German)

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.

Abstract (English)

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.

Stats
The PDF-Document has been downloaded 50 times.