<div class="csl-bib-body">
<div class="csl-entry">Scherer, M. (2016). <i>Parallelizing the commutation property for functions over small domains</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2016.36321</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2016.36321
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/6596
-
dc.description
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers
-
dc.description
Zusammenfassung in deutscher Sprache
-
dc.description.abstract
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.
de
dc.description.abstract
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.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Erfüllungsproblem
de
dc.subject
Zentralisatorklon
de
dc.subject
Kommutationseigenschaft
de
dc.subject
Constraint Satisfaction Problems
en
dc.subject
centralizer clones
en
dc.subject
commutation property
en
dc.title
Parallelizing the commutation property for functions over small domains
en
dc.title.alternative
Parallelisierung der Kommutationseigenschaft für Funktionen über kleinen Wertebereichen