@phdthesis{Loeffler2022, author = {L{\"o}ffler, Sven}, title = {Optimierung und Regularisierung von Constraint Satisfaction-Problemen (CSPs)}, doi = {10.26127/BTUOpen-6149}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-61490}, school = {BTU Cottbus - Senftenberg}, year = {2022}, abstract = {Mit Hilfe der Constraint-Programmierung k{\"o}nnen komplexe, h{\"a}ufig NP-vollst{\"a}ndige Probleme, wie zum Beispiel Graphf{\"a}rbungs-, Optimierungs-, Konfigurations- sowie Schichtplanungs-, Raum- und Zeitplanungsprobleme modelliert und gel{\"o}st werden. Im Vordergrund der Constraint-Programmierung steht dabei die deklarative Modellierung, also eine Beschreibung des eigentlichen Problems und nicht dessen L{\"o}sungsvorgangs. W{\"a}hrend es Aufgabe des Entwicklers ist, das Problem zu modellieren, wird die L{\"o}sung einem separat implementierten Solver (L{\"o}ser) {\"u}berlassen. Im Idealfall l{\"o}st dieser Solver das Problem, unabh{\"a}ngig von der konkreten Modellierung, immer schnellstm{\"o}glich. In der Praxis kann von diesem Idealfall in der Regel nicht ausgegangen werden und somit hat die Art und Weise der Modellierung ein und desselben Problems und dessen Remodellierung teilweise einen erheblichen Einfluss auf die L{\"o}sungsgeschwindigkeit. Bisher bestehende Remodellierungsverfahren transformieren entweder Constraint-Probleme im Ganzen (zum Beispiel beim Umwandeln in SAT- oder bin{\"a}re Constraint-Probleme) oder erfordern eine pr{\"a}zise Angabe und Steuerung seitens des Nutzers der Constraint-Programmierung (zum Beispiel bei der Tabularisierung). W{\"a}hrend die erste Variante in der Regel nur bei sehr speziellen Problemen zu einer Beschleunigung des L{\"o}sungsvorganges f{\"u}hrt, ben{\"o}tigt die zweite Variante vom Constraint-Modellierer zus{\"a}tzliches Expertenwissen {\"u}ber das L{\"o}sungsverfahren des verwendeten Solvers. Die bisherigen Verfahren erlauben somit keine (voll)-automatisierte Transformation von Constraint-Problemen, bei der Transformationen nur durchgef{\"u}hrt werden, wenn diese auch zu einer Beschleunigung f{\"u}hren. F{\"u}r das dieser Arbeit {\"u}bergeordnete Ziel der automatisierten Optimierung von Constraint-Problemen mittels Remodellierung, ohne dass daf{\"u}r zus{\"a}tzliches Expertenwissen notwendig ist, werden ausreichend viele verschiedene, gute und gut untersuchte Remodellierungen ben{\"o}tigt. In dieser Arbeit werden daher sowohl bestehende Verfahren f{\"u}r die Transformation von Constraint-Problemen weiterentwickelt, als auch v{\"o}llig neue entworfen und deren Korrektheit nachgewiesen. Die in dieser Arbeit entwickelten Transformationen werden bez{\"u}glich ihrer beschleunigenden Wirkung auf Constraint-Probleme untersucht. Anhand von generierten und von realen Praxisbeispielen wird die Wirksamkeit der Transformationen evaluiert und es werden Schlussfolgerungen dar{\"u}ber gezogen, wann welche Substituierungen besonders vielversprechend sind.}, subject = {Constraint Satisfaction-Problem; Constraint satisfaction problem; Optimierung; Optimization; Regularisierung; Regularization; CSP; SAT; Constraint-Erf{\"u}llung; Regularisierung; Optimierung}, language = {de} } @phdthesis{Liu2021, author = {Liu, Ke}, title = {Parallel constraint solving for combinatorial problems}, doi = {10.26127/BTUOpen-5437}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-54375}, school = {BTU Cottbus - Senftenberg}, year = {2021}, abstract = {With parallelism becoming the standard in computer design, research on parallel constraint solving technique is of vital importance for enhancing the performance of constraint solving. In this dissertation, we reviewed the literature on exploiting parallelism in constraint solving to help gain insight into the rationale of different types of parallel constraint solving approaches. On this basis, we analyzed the effectiveness of parallel constraint solving, with the focus on obtaining a first solution when solving computationally hard combinatorial problems. We have shown that a well-designed search space splitting method and constraint programming model can enable the embarrassingly parallel search (EPS) to solve some open instances of the social golfer problem that have not been solved by a sequential algorithm. We also observed superlinear speedups when solving these instances, which confirms our theoretical analysis. Besides, we examined two practical constraint optimization problems, including the traveling tournament problem with predefined venues and the talent scheduling problem. Our proposed constraint models outperformed the existing models on the same instances, and the EPS approach could always attain better feasible solutions in terms of the optimal objective value by using more parallel processors. To explore the use of massively parallel processing, we proposed the parallel stochastic portfolio search, which is a simple and non-intrusive way to parallelize different incarnations of a sequential solver. When comparing the existing portfolio to our portfolio approach by solving the same constraint satisfaction problems using the same constraint models, our technique could solve harder and larger instances. The successes of our new parallel approaches are attributed to early diversity; i.e., some diversity early in the search introduced by parallelism can offset early mistakes caused by weak heuristic choices. Unlike the other techniques (e.g., limited discrepancy search) used to overcome early mistakes, the studied two parallel constraint solving approaches not only can explore more nodes simultaneously but also does not sacrifice the guarantee of completeness. We also presented a hypertree decomposition method that builds a degenerate decomposition tree for a given constraint network, in which each node of the decomposition tree possesses and executes a subset of constraints of the given constraint network. The usefulness of our proposed parallel techniquedepends on whether we can find an efficient way to join the results of each node.}, subject = {Parallel constraint solving; Parallel computing; Constraint programing; Constraint-Programmierung; L{\"o}sen von Zwangsbedingungen; Paralleles Rechnen; SGP; Constraint-Programmierung; Parallelverarbeitung}, language = {en} } @phdthesis{Liu2021, author = {Liu, Ke}, title = {Parallel constraint solving for combinatorial problems}, doi = {10.26127/BTUOpen-5399}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-53999}, school = {BTU Cottbus - Senftenberg}, year = {2021}, abstract = {With parallelism becoming the standard in computer design, research on parallel constraint solving technique is of vital importance for enhancing the performance of constraint solving. In this dissertation, we reviewed the literature on exploiting parallelism in constraint solving to help gain insight into the rationale of different types of parallel constraint solving approaches. On this basis, we analyzed the effectiveness of parallel constraint solving, with the focus on obtaining a first solution when solving computationally hard combinatorial problems. We have shown that a well-designed search space splitting method and constraint programming model can enable the embarrassingly parallel search (EPS) to solve some open instances of the social golfer problem that have not been solved by a sequential algorithm. We also observed superlinear speedups when solving these instances, which confirms our theoretical analysis. Besides, we examined two practical constraint optimization problems, including the traveling tournament problem with predefined venues and the talent scheduling problem. Our proposed constraint models outperformed the existing models on the same instances, and the EPS approach could always attain better feasible solutions in terms of the optimal objective value by using more parallel processors. To explore the use of massively parallel processing, we proposed the parallel stochastic portfolio search, which is a simple and non-intrusive way to parallelize different incarnations of a sequential solver. When comparing the existing portfolio to our portfolio approach by solving the same constraint satisfaction problems using the same constraint models, our technique could solve harder and larger instances. The successes of our new parallel approaches are attributed to early diversity; i.e., some diversity early in the search introduced by parallelism can offset early mistakes caused by weak heuristic choices. Unlike the other techniques (e.g., limited discrepancy search) used to overcome early mistakes, the studied two parallel constraint solving approaches not only can explore more nodes simultaneously but also does not sacrifice the guarantee of completeness. We also presented a hypertree decomposition method that builds a degenerate decomposition tree for a given constraint network, in which each node of the decomposition tree possesses and executes a subset of constraints of the given constraint network. The usefulness of our proposed parallel techniquedepends on whether we can find an efficient way to join the results of each node.}, subject = {Parallel constraint solving; Parallel computing; Constraint programing; Constraint-Programmierung; L{\"o}sen von Zwangsbedingungen; Paralleles Rechnen; SGP; Constraint-Programmierung; Parallelverarbeitung}, language = {en} } @phdthesis{Prenzel2018, author = {Prenzel, Anna}, title = {Gestaltung der Mensch-Computer-Interaktion zur Entscheidungsunterst{\"u}tzung in Planungssystemen}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-45278}, school = {BTU Cottbus - Senftenberg}, year = {2018}, abstract = {Mit Hilfe von modernen Feinplanungssystemen kann die Produktions-, Flotten- oder Personaleinsatzplanung nahezu vollst{\"a}ndig automatisiert werden. F{\"u}r den Disponenten wird dadurch der Planungsaufwand erheblich reduziert. Gleichzeitig bieten diese Systeme dem Disponenten jedoch h{\"a}ufig nur unzureichende Interaktionsm{\"o}glichkeiten, um sein eigenes Expertenwissen in die Planerstellung einfließen zu lassen. Das Finden und Umsetzen von passenden Planungsentscheidungen ist h{\"a}ufig ein aufw{\"a}ndiger und fehleranf{\"a}lliger Prozess, der vom Computer nicht unterst{\"u}tzt wird. Dieser Mangel kann die Brauchbarkeit der Pl{\"a}ne und damit den Nutzen des Planungssystems erheblich beeintr{\"a}chtigen. In dieser Arbeit wird ein Konzept f{\"u}r die Gestaltung der Mensch-Computer-Interaktion in Feinplanungssystemen entwickelt, mit dem eine effektive Einbeziehung des Disponenten abgesichert werden kann. Im Gegensatz zu herk{\"o}mmlichen Interaktionskonzepten baut es auf wissenschaftlichen Erkenntnissen {\"u}ber menschliche Entscheidungs- und Entwurfsprozesse auf. Dadurch ist es m{\"o}glich, eine Computerunterst{\"u}tzung sowohl f{\"u}r die Ermittlung als auch f{\"u}r die Umsetzung von Planungsentscheidungen durch den Disponenten zu definieren. Zudem ist das Konzept auf beliebige Feinplanungsprobleme anwendbar. Es setzt sich aus 9 Interaktionsrichtlinien zusammen, deren Effektivit{\"a}t in einem Anwendertest nachgewiesen wird.}, subject = {Mensch-Computer-Interaktion; Feinplanung; Planungssysteme; Disponent; Entscheidungsprozesse; Human-computer-interaction; Detailed scheduling; Scheduling systems; Scheduler; Decision making processes; Mensch-Maschine-Kommunikation; Planungssystem; Planungsmodell}, language = {de} } @phdthesis{Voertler2017, author = {V{\"o}rtler, Thilo}, title = {Verification of software for Contiki-based low-power embedded systems using software model checking}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-44080}, school = {BTU Cottbus - Senftenberg}, year = {2017}, abstract = {The main building blocks for the internet of things are connected embedded systems. Often these systems are also used in safety critical applications. Therefore, it is particularly important that these devices work according to their specification i.e. they behave as intended. Nowadays, even for simple devices embedded operating systems as Contiki are used to simplify application development and to increase portability between different hardware platforms. The main objective of this thesis is to present a methodology for the verification of software applications written for the operation system Contiki, taking the system hardware into account. Therefore, software model checking and especially bounded model checking [BCC⁺03] is used as a technique, which allows to formally verify software for embedded systems. For verifying the software against its specification, it is also necessary to build a model of the system hardware. Thereby, the difficulty is to create a model which is detailed enough to capture the hardware behavior so that the software performs correctly, while keeping the computation effort for the verification process manageable. In this work, the drivers which communicate with the hardware are therefore replaced with abstract models during the verification process. This enables the verification based on an abstract hardware platform independent of specific hardware. A special role within embedded systems play interrupts. Interrupts are used to save power and can also be used to react on external events. Current methods for verification of interrupt driven software are based on the interleaving model and partial order reduction to reduce the size of the verification problem. This thesis argues that this method is not sufficient for software, whose behavior relies on periodically occurring interrupts. Therefore, in this thesis, a new approach called periodic interrupt modeling is introduced. This approach can be applied automatically and reduces the number of incorrect verification results due to inaccurate modeling. In addition, properties can be proven that depend on the number of occurring interrupts. Using applications for the Contiki operating system, and based on a verification flow, the approaches toward interrupt modeling are compared.}, subject = {Embedded Systems; Interrupts; Model Checking; Contiki; Software; Contiki; Eingebettete Systeme; Unterbrechungen; Modellpr{\"u}fung; Software; Eingebettetes System; Interrupt ; Bounded Model Checking; Software}, language = {en} } @masterthesis{Hoech2015, type = {Bachelor Thesis}, author = {H{\"o}ch, Florian}, title = {Statistische Analyse pseudonymisierter Krankenkassenpatientendaten nach geografischen Gesichtspunkten}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-40454}, school = {BTU Cottbus - Senftenberg}, year = {2015}, abstract = {Die zentrale Aufgabe dieser Arbeit besteht in der deskriptiven Auswertung eines von der AOK-Sachsen-Anhalt zur Verf{\"u}gung gestellten Datenbestandes unter Anwendung unterschiedlicher Methoden und Analysen. Dabei liegt der Schwerpunkt der Untersuchungen in der Identifizierung statistischer Auff{\"a}lligkeiten, deren Entstehungsgr{\"u}nde in ihren geografischen Lagen zu suchen sind. Das Datenmaterial enth{\"a}lt f{\"u}r das Bundesland Sachsen-Anhalt pseudonymisierte personenbezogene Informationen von ca. 600.000 AOK-Versicherten sowie zus{\"a}tzliche Angaben {\"u}ber ihre ambulanten Behandlungen und verordneten Medikationen aus dem Jahr 2012. Die Auswertung der mehreren Millionen Datens{\"a}tze wird mit Hilfe der freien Statistik-Software R realisiert. Die Programmiersprache R zeichnet sich durch eine Vielzahl an vordefinierten statistischen und grafischen Funktionen, sowie durch die effiziente Verarbeitung von Massendaten f{\"u}r die visuelle Aufbereitung aus. Zu Beginn werden innerhalb der Einleitung einzelne Fragestellungen formuliert, deren Beantwortung das Hauptziel dieser Arbeit darstellt. Des Weiteren werden in den nachfolgenden Kapiteln einfache statistische Grundlagen vermittelt, sowie eine Einf{\"u}hrung in die wichtigsten Befehle und Datenstrukturen der Programmiersprache R gegeben. Anschließend folgt eine detaillierte Beschreibung und Voranalyse des Datenmaterials, bevor mit den auswertenden und explorativen Studien begonnen wird.}, subject = {Statistische Analyse; Krankenkassenpatientendaten; Auswertung; Statistiksoftware R; Statistical analysis; Healthy insurance data; Geographical aspects; Sachsen-Anhalt; Statistische Analyse; Krankenkasse; Krankenunterlagen; R }, language = {de} } @phdthesis{Jeltsch2011, author = {Jeltsch, Wolfgang}, title = {Strongly typed and efficient functional reactive programming}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus-24369}, school = {BTU Cottbus - Senftenberg}, year = {2011}, abstract = {Functional Reactive Programming (FRP) is a declarative approach to programming reactive and interactive systems. We develop a common interface and a common semantics for FRP and discuss existing implementation approaches. Afterwards, we develop a technique for ensuring start time consistency as well as an efficient implementation of discrete signals. Finally, we present a novel record system, which makes FRP more usable in practice. Our system offers generic record combinators that are statically typed.}, subject = {Haskell; Funktionale Programmierung; Funktionale Reaktive Programmierung; funktionale Programmierung; Haskell; Records; Kind-System; Functional reactive programming; Functional programming; Haskell; Records; Kind system}, language = {en} } @phdthesis{ELssaedi2008, author = {ELssaedi, Mosbah Mohamed}, title = {A new approach to Event-Driven Programming}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus-4574}, school = {BTU Cottbus - Senftenberg}, year = {2008}, abstract = {In many applications, like embedded systems or systems with a strong user interaction, the program is mainly controlled by events. An event handler waits for any event to occur, and then processes that event by ignoring it or calling a corresponding action, a procedure declared in the program. In this way, events are coupled with actions and can influence the global state of the whole program. In order to design a well structured program, event handling and corresponding actions should be clearly separated. However, this aim is not always ensured. In this thesis, an approach is introduced, which enforces to design event-driven systems into two main parts: - An event-handling part, also called specification part, and - An action part, also called hand-built program part (hbp). The specification part is defined as a declarative specification of the event-handling in a special language. It is separated from the hand-built program part. Every event can only influence the state of this part, which contains the implementation of control functions, which calls the several actions defined in the hand-built program part and so connects both parts together. The prototype of a framework was implemented which allows to specify the eventhandling part by means of a special editor and generates from it some classes and templates. In order to complete the implementation, the programmer has to fill into the templates program code by hand (therefore called hand-built program part), which describe the actions.}, subject = {Ereignisgesteuerte Programmierung; Event-Driven Programming; Spezifizierung; Event-Driven Programming; Specification}, language = {en} } @phdthesis{Schoelzel2006, author = {Sch{\"o}lzel, Mario}, title = {Automatisierter Entwurf anwendungsspezifischer VLIW-Prozessoren}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus-397}, school = {BTU Cottbus - Senftenberg}, year = {2006}, abstract = {In einigen Einsatzbereichen digitaler Systeme sind die Anforderungen an die Verarbeitungsgeschwindigkeit bei gleichzeitig niedrigem Platz- und Stromverbrauch so hoch, dass sie nur durch die Verwendung spezialisierter Hardware erf{\"u}llt werden k{\"o}nnen. Zugleich sind bereits vor Beginn des Entwurfs solcher Systeme die von ihnen besonders effizient abzuarbeitenden zeitkritischen Algorithmen fest vorgegeben. Eine Hardwarel{\"o}sung f{\"u}r jeden Algorithmus bietet daher im Allgemeinen die h{\"o}chste Ausf{\"u}hrungsgeschwindigkeit, ist aber unflexibel und sehr zeitintensiv in der Realisierung. Das steht im Widerspruch zu den geforderten kurzen Entwicklungszeiten. Zudem sind bei einer Hardwarel{\"o}sung kleinere Modifikationen an den Algorithmen in einer sp{\"a}teren Entwurfsphase des Systems kaum noch m{\"o}glich. Anwendungsspezifische Prozessoren (ASPs) bieten in dieser Hinsicht einen guten Kompromiss zwischen Flexibilit{\"a}t und Ausf{\"u}hrungsgeschwindigkeit, da sie durch eine Anpassung an die zeitkritischen Algorithmen diese sehr effizient abarbeiten k{\"o}nnen und gleichzeitig in der Lage sind, leicht modifizierte Varianten und andere zeitunkritische Teile der Anwendung abzuarbeiten. In dieser Arbeit wird ein methodisches Vorgehen (DESCOMP - Design By Compilation) und die daf{\"u}r ben{\"o}tigten Techniken vorgestellt, so dass f{\"u}r ein fest vorgegebenes Spektrum an Algorithmen und zugeh{\"o}rigen Zeitschranken die Anpassung der Parameter eines konfigurierbaren ASPs vollst{\"a}ndig automatisiert durchgef{\"u}hrt werden kann und der angepasste Prozessor die Algorithmen innerhalb der Zeitschranken abarbeiten kann. Dabei wird der Platz- und Stromverbrauch des Prozessors minimiert. Schwerpunkt bildet die Anpassung an datenflussdominierte Algorithmen. Daher wird w{\"a}hrend der Design-Space-Exploration (DSE) insbesondere die verf{\"u}gbare Parallelit{\"a}t auf Instruktionsebene optimiert. Als Basisarchitektur dient ein heterogener geclusterter VLIW-Prozessor. Dessen anzupassende Parameter umfassen die Clusteranzahl, die Art und Anzahl der funktionalen Einheiten (FUs) in jedem Cluster sowie die Kapazit{\"a}t des Verbindungsnetzwerkes zwischen den Clustern. Bereits bekannte Verfahren zur DSE weisen eine hohe Komplexit{\"a}t bei der Anpassung dieser Parameter auf, da die gegebene Anwendung mit einem Compiler f{\"u}r eine Architektur mit festen Parametern {\"u}bersetzt wird. Die Parameter der Architektur sowie der Compiler werden bei diesen Ans{\"a}tzen in einem iterativen Prozess modifiziert, weswegen eine große Anzahl von Konfigurationen zu untersuchen ist. Bei DESCOMP dagegen, werden die Algorithmen wie mit einem Compiler {\"u}bersetzt, jedoch ohne dass die genauen Parameter der Zielarchitektur bekannt sind. Aus dem so erzeugten Zielcode, der hinsichtlich des Platz- und Stromverbrauchs der f{\"u}r seine Abarbeitung erforderlichen Hardware optimiert wurde, werden dann die Parameter des ASPs abgeleitet. Grundlage von DESCOMP bildet die Einteilung der DSE in eine lokale und globale Optimierungsphase. F{\"u}r die lokale Optimierungsphase wurden zeitbeschr{\"a}nkte heuristische Planungstechniken aus der High-Level-Synthese modifiziert, um optimierte geclusterte Ablaufpl{\"a}ne unterschiedlicher L{\"a}nge f{\"u}r dieselben Basisbl{\"o}cke zu erzeugen. Dabei wird die Kombination verschiedener Operatoren in derselben FU bereits ber{\"u}cksichtigt. Das tr{\"a}gt neben der Clusterung zur Reduzierung der erforderlichen Parallelit{\"a}t in den Clustern bei. Ein neu entwickelter Clusterungsalgorithmus, der mit der Planung gekoppelt ist, erlaubt es, in einem iterativen Vorgehen die gegenseitigen Wechselwirkungen von Clusterung und Ablaufplanung zu ber{\"u}cksichtigen sowie vollst{\"a}ndig automatisch eine geeignete Clusteranzahl zu bestimmen. Aus den verschiedenen geclusterten Ablaufpl{\"a}nen, die zu einem Basisblock erzeugt wurden, wird in der globalen Optimierungsphase jeweils ein Ablaufplan f{\"u}r jeden Basisblock ausgew{\"a}hlt, so dass die ausgew{\"a}hlten Ablaufpl{\"a}ne {\"a}hnliche Anforderungen an den Prozessor stellen und dieser in der Lage ist, die zuvor festgelegten Zeitschranken bei der Abarbeitung einzuhalten. F{\"u}r die Auswahl werden Informationen aus der lokalen Optimierungsphase genutzt. Es wird ber{\"u}cksichtigt, dass mit steigender Parallelit{\"a}t in den Clustern die maximal m{\"o}gliche Taktfrequenz des Prozessors sinkt. Mit den vorgestellten Verfahren zur lokalen Optimierung wurden Architekturen f{\"u}r verschiedene Benchmarkprogramme erzeugt und mit den Ergebnissen aus der Dissertation von Victor Lapinskii hinsichtlich der erforderlichen Parallelit{\"a}t verglichen. Es zeigte sich, dass bei gleicher Abarbeitungsgeschwindigkeit mit dem DESCOMP-Ansatz im Durchschnitt ca. 20 Prozent weniger Parallelit{\"a}t in den Architekturen erforderlich ist, was zu einer deutlichen Verringerung des Platz- bzw. Stromverbrauchs f{\"u}hrt und gleichzeitig eine h{\"o}here Taktfrequenz zul{\"a}sst. Die Anwendbarkeit der globalen Optimierungsstrategie wurde anhand der Kombination kleinerer Signalverarbeitungsalgorithmen demonstriert.}, subject = {Entwurfsautomation; Hardwareentwurf; VLIW-Architektur; Design-Space-Exploration; VLIW; Prozessorentwurf; Design-space-exploration; VLIW; Processor design}, language = {de} }