LS Praktische Informatik / Programmiersprachen und Compilerbau
Refine
Document Type
- Doctoral thesis (3)
Has Fulltext
- yes (3)
Is part of the Bibliography
- no (3)
Keywords
- Design-Space-Exploration (1)
- Design-space-exploration (1)
- Entwurfsautomation (1)
- Ereignisgesteuerte Programmierung (1)
- Event-Driven Programming (1)
- Functional programming (1)
- Functional reactive programming (1)
- Funktionale Programmierung (1)
- Funktionale Reaktive Programmierung (1)
- Hardwareentwurf (1)
Institute
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.
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.
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.