Search

In real-time theory, there exist two approaches for computing the response time of tasks: the classical response time analysis (RTA) approach and the modular performance analysis with the Real-Time Calculus (MPA-RTC). The classical RTA techniques are based on the busy window methods and the response time equation needs to be adapted every time a new scheduling policy or a new event activation pattern is considered in the system model. MPA-RTC has its roots in Network Calculus (NC). MPA-RTC offers more powerful abstraction and exibility than the RTA based techniques, because of its ability to model resource availability and arbitrary incoming activations with the help of expressive service curves and arrival curves respectively. MPA-RTC models scheduling policy with the help of service curves and can handle hierarchical scheduling better than RTA based techniques. In this paper, we propose a generalized approach to model offset dependencies using MPA-RTC based technique to compute tight worst-case response times of tasks., acceptedVersion

Embedded systems are becoming increasingly connected in time-heterogeneous networks. Communicating with non-real-time systems without changing or deleting the often time-critical requirements. New is here the mix up of real-time and non-real-time requirements within one network. The time-critical requirements are then propagated across the network to other nodes. That is, passed while communication is done at runtime between real-time and non-real-time systems. However, if non-real-time systems do not meet the propagated requirements, the connected real-time systems can no longer guarantee that their specific main function is correctly executed. A methodology is needed that enables a structured evaluation and adaptation of non-real-time systems, in the case that the main function of the real-time systems is not jeopardized. The presented work deals with the software of such network nodes, which time-critical requirements are propagated on the one hand; where on the other hand, the requirements were not taken into account in the original design of the systems. Methods for the evaluation and adaptation of the software of these systems are presented, which aim to increase the fulfilment of the corresponding network nodes with the propagated time-critical requirements. These methods can also be used iteratively in agile development processes in an automated way, which are also being established today in the development of embedded systems. The evaluation is carried out on existing software or software freshly implemented. The multistep approach to this involves conformance-based validation of signals and path coverage with metrics based on software lifecycles. The subsequent adaptation should take into account the evaluation results and is supported via five design patterns on software in this thesis. Three of these design patterns have been developed mainly for node-to-node communication, the other two design patterns for use within network nodes. The evaluation and adaptation of the software can be carried out repeatedly. If the software under adaptation achieves a certain quality, for example a signal conformity to a certain reference signal, corresponding network nodes can be installed with real-time systems or on real-time platforms after completion of the adaptation in such a way that the specific main function of the connected real-time systems is executed correctly in time-critical terms. Also, use cases and time-sensitive requirements are catalogued in aspects of scheduling, memory management, and software platform timers. The thesis shows how test cases can be generated as the basis of an evaluation from these catalogues, and also provides metrics to assess the runtime results of the software. Case studies and collaborative projects with industry have examined the developed methods and software prototypes to demonstrate the applicability of them within established development processes.

Medizinische cyberphysikalische Systeme erfordern einerseits die Adaption an patientenindividuelle Parameter während einer Behandlung und andererseits den Nachweis eines sicheren Systemverhaltens. Wir schlagen vor, Nachweisbarkeit mittels Online Model-Checking und Nachvollziehbarkeit durch Anwendung von regelbasierten Transformationen zu verbinden.

Recent technological advancements have enabled the miniaturization of electronics to a degree that powerful mobile computers and versatile sensor arrays can be integrated in phones, watches or even glasses. This dissertation looks at how such devices, in particular smartphones, smart watches and smart glasses, can be used to help users participating in social interactions improve the quality of their behaviour, and thus better the outcome of the interaction. To this end, the concept of social augmentation is introduced. Social augmentation makes use of behavioural feedback loops to analyse the behaviour of the user in realtime and, based on the outcome of this analysis, provide live feedback to the user on how to improve their behaviour. The concept is positioned as an evolution of classical social skills training methods, capable of augmenting the social skills of the users in realtime during actual social interactions. It is targeted at users who wish to perform better during critical social interactions, such as job interview or speaking in public. However, social augmentation can also help persons who suffer from various disabilities better regulate their behaviour to avoid misunderstandings and generally increase their functional independence. The main challenge of this approach lies in designing the augmentation to function alongside social interactions without disrupting them. To address this, the thesis introduces a conceptual framework for social augmentation, which has been informed by empirical and theoretical findings from the fields of cognitive psychology, human-computer interaction and digital signal processing. With the help of three user studies spanning two scenarios (public speaking and group discussions), the social augmentation concept has been tested for effectiveness in improving social behaviour without disrupting the social interaction. To foster further research in this area, the SSJ open source software framework for social augmentation has been implemented. Through a combination of state-of-the-art behaviour analysis and live feedback techniques, SSJ supports the behavioural feedback loop in its entirety. First, it allows the processing and classification of social signals extracted from various sensors locally on mobile devices and in realtime. Using the results of the behaviour analysis, SSJ can deliver unobtrusive, multimodal live feedback using various output devices including head-mounted displays, vibro-actuators and headphones. Thus, SSJ enables the creation of powerful and versatile social augmentation systems. Moreover, thanks to a modular and flexible design, the augmentation is not restricted to any particular scenario, but can be targeted at manifold social situations.

The present thesis addresses the topic of 3D range imaging in a twofold way: new methods in the field of range data simulation as well as the accumulation of range images into a consistent data representation, namely 3D environment models, for high quality 3D object reconstruction are proposed. Within the last years inexpensive Time-of-Flight (ToF) range imaging devices have become an alternative to traditional depth measuring approaches. ToF cameras measure full-range distance information by actively illuminating a scene and measuring the time until back-scattered light is detected. The final distance information is computed from multiple raw images. This thesis proposes a method for simulating the ToF principle in real-time along with the major sensor characteristics. The approach is motivated by physically-based illumination models and applied to the simulation of Photonic Mixing Devices, a specific type of ToF sensors. Furthermore, this thesis presents new methods of range data accumulation in real-time. While the hierarchical volumetric approach supports merging and subtraction of sub-volumes with arbitrary resolutions, the point-based fusion method accounts for spatial limitations of previous approaches and addresses high quality 3D reconstructions at extended scales. Additionally, dynamically changing scenes are supported which results in advanced camera pose estimation as well as reduced drift errors. The algorithms are evaluated using simulated data as well as real camera data from structured light and ToF devices. The algorithms presented in this thesis feature an extensive data-parallel implementation on current graphics processing units in order to ensure the online capability of the methods but without restricting the algorithms to hardware-specific features. Die vorliegende Arbeit befasst sich im Bereich der 3D Tiefen-Bildverarbeitung mit zwei unterschiedlichen Themengebieten: zum einen geht es um neue Ansätze zur Simulation von Tiefenbilddaten, zum anderen geht es um die Akkumulierung von Entfernungsbildern in eine konsistente Datenbasis - auch 3D Umgebungsmodelle genannt - für qualitativ hochwertige 3D Objektrekonstruktionen. Im Laufe der letzten Jahre haben sich kostengünstige 3D Laufzeitkamerasysteme (Time-of-Flight, ToF) zu einer ernstzunehmenden Alternative zu traditionellen Abstandsmessverfahren etabliert. ToF-Kameras erfassen Entfernungsbilder, indem die Szene aktiv beleuchtet und die Laufzeit des reflektierten Lichts bestimmt wird. Dabei werden die Tiefendaten aus mehreren Rohbildern rekonstruiert. Diese Arbeit stellt einen Ansatz zur Echtzeit-Simulation des ToF-Verfahrens vor, welcher auch die Simulation von relevanten Sensor-Charakteristiken umfasst. Der Ansatz ist physikalisch motiviert und findet seine Anwendung in der Simulation von Photomischdetektoren (Photonic Mixing Devices), welche auf dem Lichtlaufzeitverfahren basieren. Darüber hinaus werden in der vorliegenden Arbeit neue Verfahren für die Akkumulierung von Entfernungsbildern präsentiert. Der hierarchisch-volumetrische Ansatz unterstützt das Hinzufügen und Entfernen von Teil-Volumen mit unterschiedlicher Auflösung. Im Gegensatz zu bisherigen Ansätzen stellt die punkt-basierte Methode qualitativ hochwertige Rekonstruktion von großen Szenen sicher. Des Weiteren werden dynamische Szenen unterstützt. Dadurch verbessern sich die Abschätzung der Kamerapose sowie das Abdriften während der Datenfusion. Die Anwendung der Algorithmen wird unter Nutzung von Simulationsdaten und realen Kameradaten (basierend sowohl auf dem strukturierten Licht-Ansatz als auch auf dem ToF Verfahren) demonstriert. Alle präsentierten Algorithmen zeichnen sich durch eine umfangreiche daten-parallele Implementierung auf derzeit verfügbaren Grafikkarten aus, um die Echtzeitverarbeitung sicherzustellen. Die Algorithmen werden dabei nicht auf hardware-spezifische Aspekte eingeschränkt.

This work makes significant contributions in the field of sufficient schedulability tests for rate-monotonic scheduling (RMS) and their application to partitioned RMS. Goal is the maximization of possible utilization in worst or average case under a given number of processors. This scenario is more realistic than the dual case of minimizing the number of necessary processors for a given task set since the hardware is normally fixed. Sufficient schedulability tests are useful for quick estimates of task set schedulability in automatic system-synthesis tools and in online scheduling where exact schedulability tests are too slow. Especially, the approach of Accelerated Simply Periodic Task Sets (ASPTSs) and the concept of circular period similarity are cornerstones of improvements in the success ratio of such schedulability tests. To the best of the author's knowledge, this is the first application of circular statistics in real-time scheduling. Finally, the thesis discusses the use of sharp total utilization thresholds for partitioned EDF. A constant-time admission control is enabled with a controlled residual risk. Diese Arbeit liefert entscheidende Beiträge im Bereich der hinreichenden Planbarkeitstests für ratenmonotones Scheduling (RMS) und deren Anwendung auf partitioniertes RMS. Ziel ist die Maximierung der möglichen Last im Worst Case und im Average Case bei einer gegebenen Zahl von Prozessoren. Dieses Szenario ist realistischer als der duale Fall der Minimierung der Anzahl der notwendigen Prozessoren für eine gegebene Taskmenge, da die Hardware normalerweise fixiert ist. Hinreichende Planbarkeitstests sind für schnelle Schätzungen der Planbarkeit von Taskmengen in automatischen Werkzeugen zur Systemsynthese und im Online-Scheduling sinnvoll, wo exakte Einplanungstests zu langsam sind. Insbesondere der Ansatz der beschleunigten einfach-periodischen Taskmengen und das Konzept der zirkulären Periodenähnlichkeit sind Eckpfeiler für Verbesserungen in der Erfolgsrate solcher Einplanungstests. Nach bestem Wissen ist das die erste Anwendung zirkulärer Statistik im Echtzeit-Scheduling. Schließlich diskutiert die Arbeit plötzliche Phasenübergänge der Gesamtlast für partitioniertes EDF. Eine Zugangskontrolle konstanter Zeitkomplexität mit einem kontrollierten Restrisiko wird ermöglicht.

Mit der vorliegenden Arbeit wird eine durchgängige Werkzeugkette von der Modellbildung physikalischer Simulationen bis zur Entwurfsautomatisierung für FPGA-basierte Echtzeitsimulationen etabliert. Modelica wurde als vielseitige, intuitive und objektorientierte Sprache zur Modellbildung ausgewählt. Die entwickelte Werkzeugkette nutzt Methoden der High-Level-Synthese, um einen Entwurf in VHDL zu generieren. Dabei können sowohl Entwürfe in Fließkomma-, als auch Festkomma-Arithmetik erzeugt werden.

Real-time 3D map building and 3D motion estimation using only visual data are two challenging problems which have been intensively studied by the machine vision community in the past decade. In order to successfully build a 3D map, the accurate 3D motion estimation of the input sensor during the map building process is needed. Up to now, most of the attempts to improve the 3D motion estimation process have been concentrated on the software algorithms used. However, despite the use of sophisticated algorithms, accurate 3D motion information is still hindered by the limitation of the visual sensor used, e.g. a single camera with small field of view which suffers the motion ambiguity problem in the case of small movements, leading to inaccurate motion information and poor map quality. This thesis work proposes a new piece of multi-camera hardware to be used as a 3D visual sensing device for the real-time 3D motion estimation and 3D map building problems. Instead of focusing only on the software solution, this work takes an alternative approach to improve the motion estimation accuracy and robustness by means of a better hardware design. A multi-camera unit (MCU) which is aimed for high accuracy 3D motion detection is constructed. It consists of three pairs of stereo cameras which are put together as a compact, mobile hardware platform. This unique camera arrangement eliminates the motion ambiguity error found in single camera systems and so accurate motion estimation is obtained. The increased field of view by means of multiple cameras also enables a simple but accurate detection of 3D movement of the camera in real-time without any complex calculations. The accompanied algorithms which are needed for the real-time 3D motion estimation including the real-time feature detection and feature matching as well as outlier rejection schemes are also implemented for the MCU system. Moreover, the FastSLAM algorithm for real-time 3D localization and map building approach is implemented in order to maintain a consistent feature point map and the location and orientation of the MCU. As a result, the proposed 3D motion estimation and 3D map building using the MCU system gives a better performance compared to the conventional, single camera systems as confirmed by the simulation results and real world experiments. This is especially the case for 3D motion estimation performances, where the motion ambiguity error is being compensated in both rotation and translation cases. The probabilistic approach for 3D feature point map building shows a strong real-time performance and consistency with good accuracy. Finally, the proposed multi-camera hardware is used for a 3D photorealistic map building task where a high quality 3D model which correctly replicates the surrounding environment can be constructed in real-time. 3D-Kartengenerierung und 3D-Bewegungsschätzung in Echtzeit ausschließlich unter Verwendung visueller Daten sind zwei anspruchsvolle Problemstellungen, mit denen sich der Arbeitskreis zum maschinellen Sehen in den vergangenen Jahren intensiv auseinandergesetzt hat. Für die erfolgreiche Erstellung einer 3D-Karte bedarf es der genauen 3D-Bewegungsschätzung mit Hilfe eines Eingangssensors während des Kartierungsprozesses. Bisher waren die meisten Versuche zur Verbesserung der 3D-Bewegungsschätzung vor allem auf die eingesetzten Software-Algorithmen gerichtet. Doch trotz ausgeklügelter Algorithmen wird eine exakte 3D-Bewegungsschätzung weiterhin durch die Grenzen behindert, die durch den verwendeten visuellen Sensor hervorgerufen werden. Eine einzelne Kamera besitzt nur ein kleines Sichtfeld, was zum Problem der Bewegungsmehrdeutigkeit im Fall kleiner Bewegungen führt und damit zu ungenauen Bewegungsinformationen und einer schlechten Kartenqualität. Diese Doktorarbeit stellt eine neue Multikamera-Hardware vor, die als ein optisches 3D-Messgerät zur Lösung der Probleme der Echtzeit-3D-Bewegungsschätzung und -3D-Kartierung verwendet werden kann. Der Fokus liegt dabei nicht allein auf der Software-Lösung, sondern geht einen alternativen Weg zur Verbesserung der Genauigkeit und Zuverlässigkeit der Bewegungsschätzung, nämlich mit Hilfe eines besseren Hardware-Designs. Das Ergebnis dieser Herangehensweise ist eine Multikameraeinheit (MKE), die auf eine extrem genaue 3D-Bewegungsdetektion ausgelegt ist. Sie besteht aus drei Stereokamerapaaren, die zu einer kompakten, mobilen Hardwareplattform zusammengefügt werden. Die einzigartige Kameraanordnung beseitigt die Mehrdeutigkeit des Bewegungsfehlers, welche man in Einzelkamerasystemen findet, und liefert so eine präzise Bewegungsschätzung. Das erweiterte Sichtfeld dank mehrerer Kameras ermöglicht außerdem eine einfache, aber genaue Detektion der 3D-Bewegung der Kamera in Echtzeit ohne komplizierte Berechnungen. Die begleitenden Algorithmen, die für die Echtzeit-3D-Bewegungsschätzung benötigt werden, einschließlich der Detektion und des Abgleichs von Merkmalen in Echtzeit sowie Algorithmen zur Unterdrückung von Ausreißern, werden ebenfalls für die MKE implementiert. Darüber hinaus wird der FastSLAM-Algorithmus für die simultane Echtzeit-3D-Lokalisierung und Kartenerstellung implementiert, um eine einheitliche Merkmalpunktkarte und den Standort und die Ausrichtung der MKE beizubehalten. Infolge dessen erbringt das vorgestellte 3D-Bewegungsschätzungs- und 3D-Kartierungssystem mittels der MKE im Vergleich zu den herkömmlichen Einzelkamerasystemen eine höhere Leistung, was durch Simulationsergebnisse und Experimente unter realen Bedingungen bestätigt wird. Dies gilt besonders für die Leistungsfähigkeit der 3D-Bewegungsschätzung, bei der sowohl die rotatorische als auch die translatorische Mehrdeutigkeit des Bewegungsfehlers kompensiert wird. Der wahrscheinlichkeitstheoretische Ansatz für die Generierung von Merkmalpunktkarten zeigt eine hohe Echtzeit-Leistung und Konsistenz mit guter Genauigkeit. Schließlich wird die vorgestellte Multikamera-Hardware für 3D-fotorealistische Kartierungsprojekte verwendet, in denen ein hochwertiges 3D-Modell, welches die Umgebung korrekt repliziert, in Echtzeit erstellt werden kann.

Graphics hardware has in recent years become increasingly programmable, and its programming APIs use the stream processor model to expose massive parallelization to the programmer. Unfortunately, the inherent restrictions of the stream processor model, used by the GPU in order to maintain high performance, often pose a problem in porting CPU algorithms for both video and volume processing to graphics hardware. Serial data dependencies which accelerate CPU processing are counterproductive for the data-parallel GPU. This thesis demonstrates new ways for tackling well-known problems of large scale video/volume analysis. In some instances, we enable processing on the restricted hardware model by re-introducing algorithms from early computer graphics research. On other occasions, we use newly discovered, hierarchical data structures to circumvent the random-access read/fixed write restriction that had previously kept sophisticated analysis algorithms from running solely on graphics hardware. For 3D processing, we apply known game graphics concepts such as mip-maps, projective texturing, and dependent texture lookups to show how video/volume processing can benefit algorithmically from being implemented in a graphics API. The novel GPU data structures provide drastically increased processing speed, and lift processing heavy operations to real-time performance levels, paving the way for new and interactive vision/graphics applications. Graphikhardware wurde in den letzen Jahren immer weiter programmierbar. Ihre APIs verwenden das Streamprozessor-Modell, um die massive Parallelisierung auch für den Programmierer verfügbar zu machen. Leider folgen aus dem strikten Streamprozessor-Modell, welches die GPU für ihre hohe Rechenleistung benötigt, auch Hindernisse in der Portierung von CPU-Algorithmen zur Video- und Volumenverarbeitung auf die GPU. Serielle Datenabhängigkeiten beschleunigen zwar CPU-Verarbeitung, sind aber für die daten-parallele GPU kontraproduktiv . Diese Arbeit präsentiert neue Herangehensweisen für bekannte Probleme der Video- und Volumensverarbeitung. Teilweise wird die Verarbeitung mit Hilfe von modifizierten Algorithmen aus der frühen Computergraphik-Forschung an das beschränkte Hardwaremodell angepasst. Anderswo helfen neu entdeckte, hierarchische Datenstrukturen beim Umgang mit den Schreibzugriff-Restriktionen die lange die Portierung von komplexeren Bildanalyseverfahren verhindert hatten. In der 3D-Verarbeitung nutzen wir bekannte Konzepte aus der Computerspielegraphik wie Mipmaps, projektive Texturierung, oder verkettete Texturzugriffe, und zeigen auf welche Vorteile die Video- und Volumenverarbeitung aus hardwarebeschleunigter Graphik-API-Implementation ziehen kann. Die präsentierten GPU-Datenstrukturen bieten drastisch schnellere Verarbeitung und heben rechenintensive Operationen auf Echtzeit-Niveau. Damit werden neue, interaktive Bildverarbeitungs- und Graphik-Anwendungen möglich.

With increasing system complexity, there is growing interest in using formal methods in wider range of systems to improve system predictability and determine system robustness to changes, enhancements and pitfalls. This paper gives an overview over a formal approach to system level performance modelling and analysis. A methodology is presented to cover distributed multiprocessor systems as well as multiprocessor systems on chip. The abstract modelling allows early design space exploration and optimization. We investigate an example multimedia application and optimize the usage of the shared memory to reach an optimal performance.

Vernetzte Standardarbeitsplatzrechner (sog. Cluster) sind eine attraktive Umgebung zur Ausf"uhrung paralleler Programme; f"ur einige Anwendungsgebiete bestehen jedoch noch immer ungel"oste Probleme. Ein solches Problem ist die Verl"asslichkeit und Rechtzeitigkeit der Programmausf"uhrung: In vielen Anwendungen ist es wichtig, sich auf die rechtzeitige Fertigstellung eines Programms verlassen zu k"onnen. Mechanismen zur Kombination dieser Eigenschaften f"ur parallele Programme in verteilten Rechenumgebungen sind das Hauptanliegen dieser Arbeit. Zur Behandlung dieses Anliegens ist eine gemeinsame Metrik f"ur Verl"asslichkeit und Rechtzeitigkeit notwendig. Eine solche Metrik ist die Responsivit"at, die f"ur die Bed"urfnisse dieser Arbeit verfeinert wird. Als Fallstudie werden Calypso und Charlotte, zwei Systeme zur parallelen Programmierung, im Hinblick auf Responsivit"at untersucht und auf mehreren Abstraktionsebenen werden Ansatzpunkte zur Verbesserung ihrer Responsivit"at identifiziert. L"osungen f"ur diese Ansatzpunkte werden zu allgemeineren Mechanismen f"ur (parallele) responsive Dienste erweitert. Im Einzelnen handelt es sich um 1. eine Analyse der Responsivit"at von Calypsos ``eager scheduling'' (ein Verfahren zur Lastbalancierung und Fehlermaskierung), 2. die Behebung eines ``single point of failure,'' zum einen durch eine Responsivit"atsanalyse von Checkpointing, zum anderen durch ein auf Standardschnittstellen basierendes System zur Replikation bestehender Software, 3. ein Verfahren zur garantierten Ressourcenzuteilung f"ur parallele Programme und 4.die Einbeziehung semantischer Information "uber das Kommunikationsmuster eines Programms in dessen Ausf"uhrung zur Verbesserung der Leistungsf"ahigkeit. Die vorgeschlagenen Mechanismen sind kombinierbar und f"ur den Einsatz in Standardsystemen geeignet. Analyse und Experimente zeigen, dass diese Mechanismen die Responsivit"at passender Anwendungen verbessern., Clusters of standard workstations have been shown to be an attractive environment for parallel computing. However, there remain unsolved problems to make them suitable to some application scenarios. One of these problems is a dependable and timely program execution: There are many applications in which a program should be successfully completed at a predictable point of time. Mechanisms to combine the properties of both dependable and timely execution of parallel programs in distributed computing environments are the main objective of this dissertation. Addressing these properties requires a joint metric for dependability and timeliness. Responsiveness is such a metric; it is refined for the purposes of this work. As a case study, Calypso and Charlotte, two parallel programming systems, are analyzed and their shortcomings on several abstraction levels with regard to responsiveness are identified. Solutions for them are presented and generalized, resulting in widely applicable mechanisms for (parallel) responsive services. Specifically, these solutions are: 1) a responsiveness analysis of Calypso's eager scheduling (a mechanism for load balancing and fault masking), 2) ameliorating a single point of failure by a responsiveness analysis of checkpointing and by a standard interface-based system for replication of legacy software, 3) managing resources in a way suitable for parallel programs, and 4) using semantical information about the communication pattern of a program to improve its performance. All proposed mechanisms can be combined and are suitable for use in standard environments. It is shown by analysis and experiments that these mechanisms improve the responsiveness of eligible applications.