Synthesis of Synchronous Programs to Parallel Software Architectures

This thesis provides a fully automatic translation from synchronous programs to parallel software for different architectures, in particular, shared memory processing (SMP) and distributed memory systems. Thereby, we exploit characteristics of the synchronous model of computation (MoC) to reduce communication and to improve available parallelism and load-balancing by out-of-order (OOO) execution and data speculation. Manual programming of parallel software requires the developers to partition a system into tasks and to add synchronization and communication. The model-based approach of development abstracts from details of the target architecture and allows to make decisions about the target architecture as late as possible. The synchronous MoC supports this approach by abstracting from time and providing implicit parallelism and synchronization. Existing compilation techniques translate synchronous programs into synchronous guarded actions (SGAs) which are an intermediate format abstracting from semantic problems in synchronous languages. Compilers for SGAs analyze causality problems, ensure logical correctness and the absence of schizophrenia problems. Hence, SGAs are a simplified and general starting point and keep the synchronous MoC at the same time. The instantaneous feedback in the synchronous MoC makes the mapping of these systems to parallel software a non-trivial task. In contrast, other MoCs such as data-flow processing networks (DPNs) directly match with parallel architectures. We translate the SGAs into DPNs,which represent a commonly used model to create parallel software. DPNs have been proposed as a programming model for distributed parallel systems that have communication paths with unpredictable latencies. The purely data-driven execution of DPNs does not require a global coordination and therefore DPNs can be easily mapped to parallel software for architectures with distributed memory. The generation of efficient parallel code from DPNs challenges compiler design with two issues: To perfectly utilize a parallel system, the communication and synchronization has to be kept low, and the utilization of the computational units has to be balanced. The variety of hardware architectures and dynamic execution techniques in processing units of these systems make a statically balanced distributed execution impossible. The synchronous MoC is still reflected in our generated DPNs, which exhibits characteristics that allow optimizations concerning the previously mentioned issues. In particular, we apply a general communication reduction and OOO execution to achieve a dynamically balanced execution which is inspired from hardware design.Diese Arbeit behandelt die vollautomatische Übersetzung von synchronen Programmen in parallele Software für verschiedene Architekturen, genauer gesagt für Systeme mit gemeinsam genutztem Speicher und Systeme mit verteiltem Speicher. Dabei nutzen wir Eigenschaften des synchronen Berechnungsmodells (englisch: model of computation (MoC)) zur Reduzierung von Kommunikation und Out-of-Order Ausführung und Datenspekulation zur Erhöhung von Parallelität und zum dynamischen Ausgleich der Rechenauslast. Die manuelle Programmierung paralleler Systeme erfordert von Entwicklern die Partitionierung eines Systems in Teilprozesse und das Hinzufügen von Synchronisation und Kommunikation. Der modellbasierte Ansatz der Entwicklung abstrahiert von Details der Zielarchitektur und erlaubt späte Entscheidungen über die Zielarchitektur. Das synchrone MoC unterstützt diesen Ansatz indem es von der Zeit abstrahiert und implizite Parallelität und Synchronisation erlaubt. Existierende Kompilierungsverfahren übersetzen synchrone Programme in synchrone bedingte Aktionen (englisch: synchronous guarded actions (SGAs)) - ein Zwischenformat dass von semantischen Problemen der synchronen Sprachen abstrahiert. Compiler für SGAs analysieren Kausalitätsprobleme und stellen logische Korrektheit und die Abwesenheit von Schizophrenieproblemen sicher. SGAs bieten daher einen einfachen und allgemeinen Startpunkt und behalten das synchrone MoC bei. Das unmittelbare Feedback im synchronen MoC macht die Übersetzung dieser Systeme in parallele Software nicht-trivial. Andere MoCs wie die Datenfluss-Netzwerke (englisch: data-flow processing networks (DPNs)) passen dagegen direkt mit parallelen Architekturen zusammen. Wir übersetzen die SGAs in DPNs, welche ein geläufiges Modell zur Erstellung paralleler Software darstellen. Die rein datengesteuerte Ausführung von DPNs benötigt keine globale Koordinierung, so dass DPNs einfach in parallele Software für Architekturen mit verteiltem Speicher übersetzt werden können. Die Erzeugung von parallelem Code aus DPNs fordert Compiler mit zwei Problemen heraus: Um ein paralleles System perfekt auszunutzen muss die Kommunikation und Synchronisation gering und die Auslastung der Recheneinheiten gleichmäßig sein. Die Vielfalt an Hardwarearchitekturen und dynamische Ausführungstechniken in deren Recheneinheiten macht eine statisch ausbalancierte verteilte Ausführung unmöglich. Das synchrone MoC spiegelt sich in denen von uns generierten DPNs wieder und erlaubt aufgrund bestimmter Eigenschaften Optimierungen bezüglich der zuvor genannten Probleme. Wir wenden eine allgemeine Kommunikationreduzierung und Out-of-Order Ausführung aus dem Hardware Design an, um die Rechenauslast dynamisch auszugleichen