Timing Analysable Synchronisation Techniques for Parallel Programs on Embedded Multi-Cores

The thesis on hand provides hardware-software co-design of timing analysable synchronisation techniques in embedded shared-memory multi-core processors. In hardware, an augmented memory controller including the logic to support consistent and atomic Read-Modify-Write (RMW) primitives for a predictable shared-memory multi-core processor has been developed. The techniques introduced with the augmented memory controller are also applicable to further (future) shared-memory multi-core platforms. On top of these RMW primitives, timing analysable software synchronisation techniques are provided. On the one hand, hard real-time (HRT) capable, worst-case efficient, lock-based synchronisation techniques employing busy-waiting (spinning) and blocking (suspending) are introduced. On the other hand, worst-case efficient barrier implementations for progress coordination of HRT threads are presented. The implemented hardware and software techniques are analysed in detail with an open-source static worst-case execution time (WCET) analysis tool, which supports the analysis of multithreaded parallel programs on shared-memory multi-cores. The static timing analysis includes worst-case memory latencies for the concurrent access of threads to a shared global memory, and allows for analysing multithreaded programs by introducing worst-case waiting times at synchronisation points. Furthermore, two benchmarking parallel programs, a parallel matrix multiplication and an Integer Fast Fourier Transformation, have been implemented and analysed using the proposed synchronisation techniques. The analyses have shown that busy-waiting spin locks are preferable over locking techniques with suspension for multithreaded parallel programs on shared-memory multi-core processors. Also, the static timing analyses indicate that pessimism in the WCET estimates could be further reduced by providing a technique that prioritises frequent normal load and store operations over infrequent RMW operations on synchronisation variables. The optimisation technique, the split-phase synchronisation technique, has been implemented in the augmented memory controller, and allows for splitting RMW operations into a load and modification phase and a store phase while maintaining atomicity and data consistency under a weak consistency model. The WCET analyses of parallel benchmark programs with the split-phase synchronisation technique applied shows an additional improvement of WCET guarantees. The remainder of this thesis introduces an approach towards a novel parallelisation method for HRT programs using parallel design patterns. The pattern-based parallelisation process integrates the developed HRT capable synchronisation techniques as synchronisation idioms. The proposed parallelisation approach is envisioned to be further evolved and integrated in a software engineering approach that limits the possible variability in the parallelisation process to well-known, timing analysable structures by embracing programmer and timing analyser knowledge in forms of design patterns, algorithmic skeletons, and idioms.Die vorliegende Dissertation behandelt Hardware-Software-Co-Design von zeitlich vorhersagbaren Synchronisierungstechniken für eingebettete Mehrkernprozessoren mit gemeinsamem Speicher. Dazu wurde der Speicher-Controller eines echtzeitfähigen eingebetteten Mehrkernprozessors um die Hardware-Logik zur Behandlung von atomaren und konsistenten Read-Modify-Write (RMW) Primitiven erweitert. Die entwickelten Techniken lassen sich auch in weiteren (zukünftigen) Mehrkernprozessoren verwenden. Darauf aufbauend werden zeitlich analysierbare, worst-case effiziente Software-Synchronisationstechniken bereitgestellt. Einerseits werden Synchronisationstechniken mit Busy-Waiting (Spinning) und Sperren (Aussetzung) und andererseits Barrieren zur Fortschrittskoordination von HRT (harte Echtzeit) Kontrollfäden vorgestellt. Die implementierten Hardware- und Software-Techniken werden im Detail mit einem open-source, statischen worst-case execution time (WCET) Analyse-Tool, das die Analyse von mehrfädigen parallelen Programmen auf Mehrkernprozessoren mit gemeinsamen Speicher unterstützt, evaluiert. Das benutzte WCET Analyse-Tool verwendet worst-case Speicherlatenzen zur Behandlung von konkurrierenden Zugriffen mehrerer Programmfäden auf einen gemeinsamen Hauptspeicher. Es ermöglicht die Analyse von mehrfädigen Programmen durch die Einführung von worst-case Wartezeiten an Synchronisationspunkten. Außerdem wurden zwei parallele Benchmark-Programme, eine parallele Matrixmultiplikation und eine mehrfädige (Ganzzahl) Fast Fourier Transformation, entwickelt und unter Verwendung der vorgeschlagenen Synchronisationstechniken evaluiert. Die Evaluierungen ergeben, dass für die echtzeitfähige Ausführung von mehrfädigen Programmen auf Mehrkernprozessoren mit gemeinsamen Speicher Busy-Waiting Spinlocks gegenüber den Synchronisationstechniken, die einen aktiven Kontrollfaden aussetzen, vorzuziehen sind. Außerdem zeigen die vorgenommenen Echtzeitanalysen, dass der Pessimismus in den WCET Abschätzungen weiter reduziert werden kann, wenn eine Technik eingesetzt wird, die sehr häufige normale Lade- und Schreibzugriffe gegenüber selteneren RMW Operationen auf Synchronisationsvariablen priorisiert. Die Optimierungstechnik ist im erweiterten Speichercontroller implementiert und erlaubt das Aufspalten von RMW Operationen unter Aufrechterhaltung der Atomarität und Datenkonsistenz unter einem schwachen Konsistenz-Modell. Die erzielten Ergebnisse mit der Optimierungstechnik zeigen eine weitere Verbesserung der WCET Garantien. Am Schluß dieser Dissertation wird ein Ansatz für eine neuartige Methode zur Parallelisierung von HRT-Programmen mit parallelem Entwurfsmuster vorgestellt. Dieses Parallelisierungsverfahren beinhaltet die entwickelten HRT-fähigen Synchronisierungstechniken als Synchronisations-Idiome. Das vorgeschlagene Parallelisierungsverfahren wird zukünftig weiterentwickelt, um die mögliche Variabilität des Parallelisierungsprozesses noch weiter auf bekannte, zeitlich analysierbare Strukturen zu begrenzen. Dazu wird Wissen von Software-Entwicklern und Echtzeit-Analysten in Form von Entwurfsmustern, algorithmischen Programmskeletten und Idiomen gesammelt und aufgeführt