FG Programmiersprachen und Compilerbau
Refine
Document Type
- Doctoral thesis (3)
- Bachelor thesis (1)
Has Fulltext
- yes (4)
Is part of the Bibliography
- no (4)
Language
- German (4) (remove)
Keywords
- Auswertung (1)
- CSP (1)
- Constraint Satisfaction-Problem (1)
- Constraint satisfaction problem (1)
- Constraint-Erfüllung (1)
- Decision making processes (1)
- Design-Space-Exploration (1)
- Design-space-exploration (1)
- Detailed scheduling (1)
- Disponent (1)
Mit Hilfe der Constraint-Programmierung können komplexe, häufig NP-vollständige Probleme, wie zum Beispiel Graphfärbungs-, Optimierungs-, Konfigurations- sowie Schichtplanungs-, Raum- und Zeitplanungsprobleme modelliert und gelöst werden. Im Vordergrund der Constraint-Programmierung steht dabei die deklarative Modellierung, also eine Beschreibung des eigentlichen Problems und nicht dessen Lösungsvorgangs. Während es Aufgabe des Entwicklers ist, das Problem zu modellieren, wird die Lösung einem separat implementierten Solver (Löser) überlassen. Im Idealfall löst dieser Solver das Problem, unabhängig von der konkreten Modellierung, immer schnellstmö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ösungsgeschwindigkeit. Bisher bestehende Remodellierungsverfahren transformieren entweder Constraint-Probleme im Ganzen (zum Beispiel beim Umwandeln in SAT- oder binäre Constraint-Probleme) oder erfordern eine präzise Angabe und Steuerung seitens des Nutzers der Constraint-Programmierung (zum Beispiel bei der Tabularisierung). Während die erste Variante in der Regel nur bei sehr speziellen Problemen zu einer Beschleunigung des Lösungsvorganges führt, benötigt die zweite Variante vom Constraint-Modellierer zusätzliches Expertenwissen über das Lösungsverfahren des verwendeten Solvers. Die bisherigen Verfahren erlauben somit keine (voll)-automatisierte Transformation von Constraint-Problemen, bei der Transformationen nur durchgeführt werden, wenn diese auch zu einer Beschleunigung führen.
Für das dieser Arbeit übergeordnete Ziel der automatisierten Optimierung von Constraint-Problemen mittels Remodellierung, ohne dass dafür zusätzliches Expertenwissen notwendig ist, werden ausreichend viele verschiedene, gute und gut untersuchte Remodellierungen benötigt. In dieser Arbeit werden daher sowohl bestehende Verfahren für die Transformation von Constraint-Problemen weiterentwickelt, als auch völlig neue entworfen und deren Korrektheit nachgewiesen. Die in dieser Arbeit entwickelten Transformationen werden bezü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über gezogen, wann welche Substituierungen besonders vielversprechend sind.
Gestaltung der Mensch-Computer-Interaktion zur Entscheidungsunterstützung in Planungssystemen
(2018)
Mit Hilfe von modernen Feinplanungssystemen kann die Produktions-, Flotten- oder Personaleinsatzplanung nahezu vollständig automatisiert werden. Für den Disponenten wird dadurch der Planungsaufwand erheblich reduziert. Gleichzeitig bieten diese Systeme dem Disponenten jedoch häufig nur unzureichende Interaktionsmöglichkeiten, um sein eigenes Expertenwissen in die Planerstellung einfließen zu lassen. Das Finden und Umsetzen von passenden Planungsentscheidungen ist häufig ein aufwändiger und fehleranfälliger Prozess, der vom Computer nicht unterstützt wird. Dieser Mangel kann die Brauchbarkeit der Pläne und damit den Nutzen des Planungssystems erheblich beeinträchtigen.
In dieser Arbeit wird ein Konzept für die Gestaltung der Mensch-Computer-Interaktion in Feinplanungssystemen entwickelt, mit dem eine effektive Einbeziehung des Disponenten abgesichert werden kann. Im Gegensatz zu herkömmlichen Interaktionskonzepten baut es auf wissenschaftlichen Erkenntnissen über menschliche Entscheidungs- und Entwurfsprozesse auf. Dadurch ist es möglich, eine Computerunterstützung sowohl für die Ermittlung als auch fü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ät in einem Anwendertest nachgewiesen wird.
Die zentrale Aufgabe dieser Arbeit besteht in der deskriptiven Auswertung eines von der AOK-Sachsen-Anhalt zur Verfügung gestellten Datenbestandes unter Anwendung unterschiedlicher Methoden und Analysen.
Dabei liegt der Schwerpunkt der Untersuchungen in der Identifizierung statistischer Auffälligkeiten, deren Entstehungsgründe in ihren geografischen Lagen zu suchen sind.
Das Datenmaterial enthält für das Bundesland Sachsen-Anhalt pseudonymisierte personenbezogene Informationen von ca. 600.000 AOK-Versicherten sowie zusätzliche Angaben über ihre ambulanten Behandlungen und verordneten Medikationen aus dem Jahr 2012.
Die Auswertung der mehreren Millionen Datensä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ü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ü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.
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üllt werden können. Zugleich sind bereits vor Beginn des Entwurfs solcher Systeme die von ihnen besonders effizient abzuarbeitenden zeitkritischen Algorithmen fest vorgegeben. Eine Hardwarelösung für jeden Algorithmus bietet daher im Allgemeinen die höchste Ausführungsgeschwindigkeit, ist aber unflexibel und sehr zeitintensiv in der Realisierung. Das steht im Widerspruch zu den geforderten kurzen Entwicklungszeiten. Zudem sind bei einer Hardwarelösung kleinere Modifikationen an den Algorithmen in einer späteren Entwurfsphase des Systems kaum noch möglich. Anwendungsspezifische Prozessoren (ASPs) bieten in dieser Hinsicht einen guten Kompromiss zwischen Flexibilität und Ausführungsgeschwindigkeit, da sie durch eine Anpassung an die zeitkritischen Algorithmen diese sehr effizient abarbeiten kö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ür benötigten Techniken vorgestellt, so dass für ein fest vorgegebenes Spektrum an Algorithmen und zugehörigen Zeitschranken die Anpassung der Parameter eines konfigurierbaren ASPs vollständig automatisiert durchgefü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ährend der Design-Space-Exploration (DSE) insbesondere die verfügbare Parallelitä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ät des Verbindungsnetzwerkes zwischen den Clustern. Bereits bekannte Verfahren zur DSE weisen eine hohe Komplexität bei der Anpassung dieser Parameter auf, da die gegebene Anwendung mit einem Compiler für eine Architektur mit festen Parametern übersetzt wird. Die Parameter der Architektur sowie der Compiler werden bei diesen Ansä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 übersetzt, jedoch ohne dass die genauen Parameter der Zielarchitektur bekannt sind. Aus dem so erzeugten Zielcode, der hinsichtlich des Platz- und Stromverbrauchs der fü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ür die lokale Optimierungsphase wurden zeitbeschränkte heuristische Planungstechniken aus der High-Level-Synthese modifiziert, um optimierte geclusterte Ablaufpläne unterschiedlicher Länge für dieselben Basisblöcke zu erzeugen. Dabei wird die Kombination verschiedener Operatoren in derselben FU bereits berücksichtigt. Das trägt neben der Clusterung zur Reduzierung der erforderlichen Parallelitä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ücksichtigen sowie vollständig automatisch eine geeignete Clusteranzahl zu bestimmen. Aus den verschiedenen geclusterten Ablaufplänen, die zu einem Basisblock erzeugt wurden, wird in der globalen Optimierungsphase jeweils ein Ablaufplan für jeden Basisblock ausgewählt, so dass die ausgewählten Ablaufpläne ähnliche Anforderungen an den Prozessor stellen und dieser in der Lage ist, die zuvor festgelegten Zeitschranken bei der Abarbeitung einzuhalten. Für die Auswahl werden Informationen aus der lokalen Optimierungsphase genutzt. Es wird berücksichtigt, dass mit steigender Parallelität in den Clustern die maximal mögliche Taktfrequenz des Prozessors sinkt. Mit den vorgestellten Verfahren zur lokalen Optimierung wurden Architekturen für verschiedene Benchmarkprogramme erzeugt und mit den Ergebnissen aus der Dissertation von Victor Lapinskii hinsichtlich der erforderlichen Parallelität verglichen. Es zeigte sich, dass bei gleicher Abarbeitungsgeschwindigkeit mit dem DESCOMP-Ansatz im Durchschnitt ca. 20 Prozent weniger Parallelität in den Architekturen erforderlich ist, was zu einer deutlichen Verringerung des Platz- bzw. Stromverbrauchs führt und gleichzeitig eine höhere Taktfrequenz zulässt. Die Anwendbarkeit der globalen Optimierungsstrategie wurde anhand der Kombination kleinerer Signalverarbeitungsalgorithmen demonstriert.