Universität Stuttgart
Permanent URI for this communityhttps://elib.uni-stuttgart.de/handle/11682/1
Browse
260 results
Search Results
Item Open Access Prozessbausteine(2014) Eberle, Hanna; Leymann, Frank (Prof. Dr.)Gegenwärtig existierenden Modellierungssprachen und Werkzeugen zur Umsetzung prozessbasierter Anwendungen liegt im Allgemeinen die Annahme eines zur Entwicklungszeit bekannten und in seiner Struktur vollständig ausmodellierten Prozessmodells zugrunde. Für Szenarien, in welchen eine prozessbasierte Anwendung neben stabilen, d.h. zur Modellierungszeit des Prozesses bekannten, auch durch dynamische, d.h. erst zur Anwendungslaufzeit geltende, Rahmenbedingungen beeinflusst wird, ist eine derartige statische Prozessmodellierung nur bedingt geeignet. In diesen Szenarien ist es vielmehr wünschenswert, (i) zur Entwicklungszeit bereits bekannte Prozessteile der Anwendung detailliert ausmodellieren zu können, und diese (ii) zur Laufzeit der Anwendung unter Berücksichtigung der zum Ausführungszeitpunkt geltenden dynamischen Rahmenbedingungen zum vollständigen Prozess der Anwendung zu integrieren. Das im Verlauf dieser Arbeit vorgestellte Konzept der Prozessbausteine setzt an diesem Punkt an und schafft ein Rahmenwerk für die Modellierung und Ausführung prozessbasierter Anwendungen unter Berücksichtigung sowohl stabiler als auch dynamischer Rahmenbedingungen. Kerngedanke des Konzepts ist die Abbildung stabiler Rahmenbedingungen zur Entwicklungszeit in Form teilweise unvollständiger Prozessmodelle, sogenannter Prozessbausteine. Zu einem späteren Zeitpunkt im Lebenszyklus der Anwendung werden diese Prozessbausteine dann, motiviert durch die jeweils geltenden dynamischen Rahmenbedingungen, mit weiteren Prozessbausteinen zum vollständigen Prozessmodell der Anwendung integriert. Zur vollständigen Unterstützung der Entwicklung von Anwendungen auf Grundlage dieses Konzepts umfasst die vorliegende Arbeit die Definition eines Metamodells für sowohl die Modellierung einzelner als auch die Repräsentation integrierter Prozessbausteine, die Beschreibung der Ausführung integrierter Prozessbausteine, sowie die Vorstellung einer Architektur für die Ausführung integrierter Prozessbausteine.Item Open Access Modeling the interface between morphology and syntax in data-driven dependency parsing(2016) Seeker, Wolfgang; Kuhn, Jonas (Prof. Dr.)When people formulate sentences in a language, they follow a set of rules specific to that language that defines how words must be put together in order to express the intended meaning. These rules are called the grammar of the language. Languages have essentially two ways of encoding grammatical information: word order or word form. English uses primarily word order to encode different meanings, but many other languages change the form of the words themselves to express their grammatical function in the sentence. These languages are commonly subsumed under the term morphologically rich languages. Parsing is the automatic process for predicting the grammatical structure of a sentence. Since grammatical structure guides the way we understand sentences, parsing is a key component in computer programs that try to automatically understand what people say and write. This dissertation is about parsing and specifically about parsing languages with a rich morphology, which encode grammatical information in the form of words. Today’s parsing models for automatic parsing were developed for English and achieve good results on this language. However, when applied to other languages, a significant drop in performance is usually observed. The standard model for parsing is a pipeline model that separates the parsing process into different steps, in particular it separates the morphological analysis, i.e. the analysis of word forms, from the actual parsing step. This dissertation argues that this separation is one of the reasons for the performance drop of standard parsers when applied to other languages than English. An analysis is presented that exposes the connection between the morphological system of a language and the errors of a standard parsing model. In a second series of experiments, we show that knowledge about the syntactic structure of sentence can support the prediction of morphological information. We then argue for an alternative approach that models morphological analysis and syntactic analysis jointly instead of separating them. We support this argumentation with empirical evidence by implementing two parsers that model the relationship between morphology and syntax in two different but complementary ways.Item Open Access Partnerübergreifende Geschäftsprozesse und ihre Realisierung in BPEL(2016) Kopp, Oliver; Leymann, Frank (Prof. Dr. Dr. h. c.)Diese Arbeit beschäftigt sich mit Geschäftsprozessen, die die Grenzen von Organisationen überspannen. Solche Geschäftsprozesse werden Choreographien genannt. In der Arbeit wird die CREAM-Methode vorgestellt, die zeigt, wie Choreographien modelliert werden können. Im Gegensatz zu Choreographien bezeichnen Orchestrierungen ausführbare Geschäftsprozesse einer einzelnen Organisation, die Dienste nutzen, um ein Geschäftsziel zu erreichen. Eine Variante der CREAM-Methode erlaubt, von einer Orchestrierung durch Aufteilung der Orchestrierung eine Choreographie zu erhalten. Um hierbei die impliziten orchestrierungsinternen Datenabhängigkeiten in Nachrichtenaustausche zu transformieren, wird der explizite Datenfluss der Orchestrierung benötigt. Die Web Services Business Process Execution Language (BPEL) ist eine verbreitete Sprache zur Modellierung von Geschäftsprozessen. In ihr wird der Datenfluss implizit modelliert und somit wird ein Verfahren benötigt, das den expliziten Datenfluss bestimmt. In dieser Arbeit wird ein solches Verfahren vorgestellt. Um eine Choreographie zu modellieren, wird eine Choreographiesprache benötigt. Zur Identifikation einer geeigneten Sprache werden in dieser Arbeit Kriterien zur Evaluation von Choreographiesprachen vorgestellt und damit Choreographiesprachen im Web-Service-Umfeld bewertet. Da keine der betrachteten Sprachen alle Kriterien erfüllt, wird die Sprache BPEL4Chor vorgestellt, die alle Kriterien erfüllt. Um die wohldefinierte Ausführungssemantik von BPEL wiederzuverwenden, verwendet BPEL4Chor die Sprache BPEL als Beschreibungssprache des Verhaltens jedes Teilnehmers in der Choreographie. BPEL4Chor verwendet analog zu BPEL XML als Serialisierungsformat und spezifiziert keine eigene graphische Repräsentation. Die Business Process Modeling Notation (BPMN) ist der de-facto Standard, um Geschäftsprozesse graphisch darzustellen. Deshalb wird in dieser Arbeit BPMN so erweitert, dass alle in BPEL4Chor verfügbaren Konstrukte mittels BPMN modelliert werden können.Item Open Access Process migration in a parallel environment(Stuttgart : Höchstleistungsrechenzentrum, Universität Stuttgart, 2016) Reber, Adrian; Resch, Michael (Prof. Dr.- Ing. Dr. h.c. Dr. h.c. Prof. E.h.)To satisfy the ever increasing demand for computational resources, high performance computing systems are becoming larger and larger. Unfortunately, the tools supporting system management tasks are only slowly adapting to the increase in components in computational clusters. Virtualization provides concepts which make system management tasks easier to implement by providing more flexibility for system administrators. With the help of virtual machine migration, the point in time for certain system management tasks like hardware or software upgrades no longer depends on the usage of the physical hardware. The flexibility to migrate a running virtual machine without significant interruption to the provided service makes it possible to perform system management tasks at the optimal point in time. In most high performance computing systems, however, virtualization is still not implemented. The reason for avoiding virtualization in high performance computing is that there is still an overhead accessing the CPU and I/O devices. This overhead continually decreases and there are different kind of virtualization techniques like para-virtualization and container-based virtualization which minimize this overhead further. With the CPU being one of the primary resources in high performance computing, this work proposes to migrate processes instead of virtual machines thus avoiding any overhead. Process migration can either be seen as an extension to pre-emptive multitasking over system boundaries or as a special form of checkpointing and restarting. In the scope of this work process migration is based on checkpointing and restarting as it is already an established technique in the field of fault tolerance. From the existing checkpointing and restarting implementations, the best suited implementation for process migration purposes was selected. One of the important requirements of the checkpointing and restarting implementation is transparency. Providing transparent process migration is important enable the migration of any process without prerequisites like re-compilation or running in a specially prepared environment. With process migration based on checkpointing and restarting, the next step towards providing process migration in a high performance computing environment is to support the migration of parallel processes. Using MPI is a common method of parallelizing applications and therefore process migration has to be integrated with an MPI implementation. The previously selected checkpointing and restarting implementation was integrated in an MPI implementation, and thus enabling the migration of parallel processes. With the help of different test cases the implemented process migration was analyzed, especially in regards to the time required to migrated a process and the advantages of optimizations to reduce the process’ downtime during migration.Item Open Access Automated composition of adaptive pervasive applications in heterogeneous environments(2012) Schuhmann, Stephan Andreas; Rothermel, Kurt (Prof. Dr. rer. nat. Dr. h. c.)Distributed applications for Pervasive Computing represent a research area of high interest. Configuration processes are needed before the application execution to find a composition of components that provides the required functionality. As dynamic pervasive environments and device failures may yield unavailability of arbitrary components and devices at any time, finding and maintaining such a composition represents a nontrivial task. Obviously, many degrees of decentralization and even completely centralized approaches are possible in the calculation of valid configurations, spanning a wide spectrum of possible solutions. As configuration processes produce latencies which are noticed by the application user as undesired waiting times, configurations have to be calculated as fast as possible. While completely distributed configuration is inevitable in infrastructure-less Ad Hoc scenarios, many realistic Pervasive Computing environments are located in heterogeneous environments, where additional computation power of resource-rich devices can be utilized by centralized approaches. However, in case of strongly heterogeneous pervasive environments including several resource-rich and resource-weak devices, both centralized and decentralized approaches may lead to suboptimal results concerning configuration latencies: While the resource-weak devices may be bottlenecks for decentralized configuration, the centralized approach faces the problem of not utilizing parallelism. Most of the conducted projects in Pervasive Computing only focus on one specific type of environment: Either they concentrate on heterogeneous environments, which rely on additional infrastructure devices, leading to inapplicability in infrastructure-less environments. Or they address homogeneous Ad Hoc environments and treat all involved devices as equal, which leads to suboptimal results in case of present resource-rich devices, as their additional computation power is not exploited. Therefore, in this work we propose an advanced comprehensive adaptive approach that particularly focuses on the efficient support of heterogeneous environments, but is also applicable in infrastructure-less homogeneous scenarios. We provide multiple configuration schemes with different degrees of decentralization for distributed applications, optimized for specific scenarios. Our solution is adaptive in a way that the actual scheme is chosen based on the current system environment and calculates application compositions in a resource-aware efficient manner. This ensures high efficiency even in dynamically changing environments. Beyond this, many typical pervasive environments contain a fixed set of applications and devices that are frequently used. In such scenarios, identical resources are part of subsequent configuration calculations. Thus, the involved devices undergo a quite similar configuration process whenever an application is launched. However, starting the configuration from scratch every time not only consumes a lot of time, but also increases communication overhead and energy consumption of the involved devices. Therefore, our solution integrates the results from previous configurations to reduce the severity of the configuration problem in dynamic scenarios. We prove in prototypical real-world evaluations as well as by simulation and emulation that our comprehensive approach provides efficient automated configuration in the complete spectrum of possible application scenarios. This extensive functionality has not been achieved by related projects yet. Thus, our work supplies a significant contribution towards seamless application configuration in Pervasive Computing.Item Open Access Visualization challenges in distributed heterogeneous computing environments(2015) Panagiotidis, Alexandros; Ertl, Thomas (Prof. Dr.)Large-scale computing environments are important for many aspects of modern life. They drive scientific research in biology and physics, facilitate industrial rapid prototyping, and provide information relevant to everyday life such as weather forecasts. Their computational power grows steadily to provide faster response times and to satisfy the demand for higher complexity in simulation models as well as more details and higher resolutions in visualizations. For some years now, the prevailing trend for these large systems is the utilization of additional processors, like graphics processing units. These heterogeneous systems, that employ more than one kind of processor, are becoming increasingly widespread since they provide many benefits, like higher performance or increased energy efficiency. At the same time, they are more challenging and complex to use because the various processing units differ in their architecture and programming model. This heterogeneity is often addressed by abstraction but existing approaches often entail restrictions or are not universally applicable. As these systems also grow in size and complexity, they become more prone to errors and failures. Therefore, developers and users become more interested in resilience besides traditional aspects, like performance and usability. While fault tolerance is well researched in general, it is mostly dismissed in distributed visualization or not adapted to its special requirements. Finally, analysis and tuning of these systems and their software is required to assess their status and to improve their performance. The available tools and methods to capture and evaluate the necessary information are often isolated from the context or not designed for interactive use cases. These problems are amplified in heterogeneous computing environments, since more data is available and required for the analysis. Additionally, real-time feedback is required in distributed visualization to correlate user interactions to performance characteristics and to decide on the validity and correctness of the data and its visualization. This thesis presents contributions to all of these aspects. Two approaches to abstraction are explored for general purpose computing on graphics processing units and visualization in heterogeneous computing environments. The first approach hides details of different processing units and allows using them in a unified manner. The second approach employs per-pixel linked lists as a generic framework for compositing and simplifying order-independent transparency for distributed visualization. Traditional methods for fault tolerance in high performance computing systems are discussed in the context of distributed visualization. On this basis, strategies for fault-tolerant distributed visualization are derived and organized in a taxonomy. Example implementations of these strategies, their trade-offs, and resulting implications are discussed. For analysis, local graph exploration and tuning of volume visualization are evaluated. Challenges in dense graphs like visual clutter, ambiguity, and inclusion of additional attributes are tackled in node-link diagrams using a lens metaphor as well as supplementary views. An exploratory approach for performance analysis and tuning of parallel volume visualization on a large, high-resolution display is evaluated. This thesis takes a broader look at the issues of distributed visualization on large displays and heterogeneous computing environments for the first time. While the presented approaches all solve individual challenges and are successfully employed in this context, their joint utility form a solid basis for future research in this young field. In its entirety, this thesis presents building blocks for robust distributed visualization on current and future heterogeneous visualization environments.Item Open Access Causal models for decision making via integrative inference(2017) Geiger, Philipp; Toussaint, Marc (Prof. Dr.)Understanding causes and effects is important in many parts of life, especially when decisions have to be made. The systematic inference of causal models remains a challenge though. In this thesis, we study (1) "approximative" and "integrative" inference of causal models and (2) causal models as a basis for decision making in complex systems. By "integrative" here we mean including and combining settings and knowledge beyond the outcome of perfect randomization or pure observation for causal inference, while "approximative" means that the causal model is only constrained but not uniquely identified. As a basis for the study of topics (1) and (2), which are closely related, we first introduce causal models, discuss the meaning of causation and embed the notion of causation into a broader context of other fundamental concepts. Then we begin our main investigation with a focus on topic (1): we consider the problem of causal inference from a non-experimental multivariate time series X, that is, we integrate temporal knowledge. We take the following approach: We assume that X together with some potential hidden common cause - "confounder" - Z forms a first order vector autoregressive (VAR) process with structural transition matrix A. Then we examine under which conditions the most important parts of A are identifiable or approximately identifiable from only X, in spite of the effects of Z. Essentially, sufficient conditions are (a) non-Gaussian, independent noise or (b) no influence from X to Z. We present two estimation algorithms that are tailored towards conditions (a) and (b), respectively, and evaluate them on synthetic and real-world data. We discuss how to check the model using X. Still focusing on topic (1) but already including elements of topic (2), we consider the problem of approximate inference of the causal effect of a variable X on a variable Y in i.i.d. settings "between" randomized experiments and observational studies. Our approach is to first derive approximations (upper/lower bounds) on the causal effect, in dependence on bounds on (hidden) confounding. Then we discuss several scenarios where knowledge or beliefs can be integrated that in fact imply bounds on confounding. One example is about decision making in advertisement, where knowledge on partial compliance with guidelines can be integrated. Then, concentrating on topic (2), we study decision making problems that arise in cloud computing, a computing paradigm and business model that involves complex technical and economical systems and interactions. More specifically, we consider the following two problems: debugging and control of computing systems with the help of sandbox experiments, and prediction of the cost of "spot" resources for decision making of cloud clients. We first establish two theoretical results on approximate counterfactuals and approximate integration of causal knowledge, which we then apply to the two problems in toy scenarios.Item Open Access Validierung komponentenbasierter Software für Echtzeitsysteme(2003) Fleisch, Wolfgang; Göhner, Peter (Prof. Dr.-Ing. Dr. h.c.)Der Anteil und die Bedeutung von Software bei der Entwicklung von Echtzeitsystemen wächst sehr stark. Gleichzeitig werden die Entwicklungszyklen für Software-Produkte zunehmend kürzer, was sich immer häufiger in ausgelieferter fehlerhafter Software widerspiegelt. Durch die Verwendung vorgefertigter Software-Komponenten kann nach dem Baukastenprinzip bei der Konstruktion neuer Produkte die Produktivität und die Qualität erheblich gesteigert werden. Aber auch wenn durch den Einsatz geprüfter, betriebsbewährter Software-Komponenten viele Fehler vermieden werden, muss eine aus Komponenten zusammengesetzte Software auch in Zukunft mit geeigneten Prüfverfahren validiert werden, weil beim Zusammenspiel der Komponenten weiterhin Fehler entstehen können. In der vorliegenden Arbeit wird dazu ein Prüfverfahren zur Validierung komponentenbasierter Software für Echtzeitsysteme entwickelt, das das dynamische Verhalten von komponentenbasierter Software gegenüber den Anforderungen aus Anwendersicht überprüft. Die Anforderungen werden zu Beginn der komponentenbasierten Softwareentwicklung als Anwendungsfälle spezifiziert. Mit Hilfe von erweiterten UML Sequenzdiagrammen werden die Anwendungsfälle systematisch in eine formale, automatisiert prüfbare Notation überführt, die auch die Spezifikation von Echtzeitanforderungen explizit unterstützt. Da beim Entwurf von komponentenbasierter Software bereits vollständig spezifizierte Software-Komponenten verwendet werden, kann das Verhalten schon in der frühen Entwurfsphase mit Hilfe von Simulation validiert werden. Die Verwendung von Simulation hat den Vorteil, dass auch ohne die in der Praxis meist spät verfügbaren Bestandteile des technischen Prozesses und des Automatisierungsrechnersystems eine Prüfung des simulierten Verhaltens der komponentenbasierten Software durchgeführt werden kann. Anhand festgelegter Prüfkriterien wird dann das simulierte Verhalten der komponentenbasierten Software gegenüber dem in den Anwendungsfällen spezifizierten Verhalten geprüft, um damit frühzeitig Fehler aufzudecken. Eine im Rahmen der Arbeit realisierte Validierungsumgebung unterstützt den Softwareentwickler dabei umfassend, angefangen bei der Spezifikation von prüfbaren Anwendungsfällen, bis hin zur automatisierten Prüfung des simulierten Verhaltens. Die Leistungsfähigkeit des Prüfverfahrens und der Validierungsumgebung werden abschließend am Beispiel der Entwicklung und Validierung einer komponentenbasierten Software für eine Kfz-Scheibenwischeranlage demonstriert.Item Open Access Position sharing for location privacy in non-trusted systems(2015) Skvortsov, Pavel; Rothermel, Kurt (Prof. Dr. rer. nat. Dr. h.c.)Currently, many location-aware applications are available for mobile users of location-based services. Applications such as Google Now, Trace4You or FourSquare are being widely used in various environments where privacy is a critical issue for users. A general solution for preserving location privacy for a user is to degrade the quality of his or her position information. In this work, we propose an approach that uses spatial obfuscation to secure the users’ position information. By revealing the user’s position with a certain degree of obfuscation, the first crucial issue is the tradeoff between privacy and precision. This tradeoff problem is caused by limited trust in the location service providers: higher obfuscation increases privacy but leads to lower quality of service. We overcome this problem by introducing the position sharing approach. Our main idea is that position information is distributed amongst multiple providers in the form of separate data pieces called position shares. Our approach allows for the usage of non-trusted providers and flexibly manages the user’s location privacy level based on probabilistic privacy metrics. In this work, we present the multi-provider based position sharing approach, which includes algorithms for the generation of position shares and share fusion algorithms. The second challenge that must be addressed is that the user’s environmental context can significantly decrease the level of obfuscation. For example, a plane, a boat and a car create different requirements for the obfuscated region. Therefore, it is very important to consider map-awareness in selecting the obfuscated areas. We assume that a static map is known to an adversary, which may help in deriving the user’s true position. We analyze both how map-awareness affects the generation and fusion of position shares and the difference between the map-aware position sharing approach and its open space based version. Our security analysis shows that the proposed position sharing approach provides good security guarantees for both open space and constrained space based models. The third challenge is that multiple location servers and/or their providers may have different trustworthiness from the user’s point of view. In this case, the user would prefer not to reveal an equal level (precision) of position information to every server. We propose a placement optimization approach that ensures that risk is balanced among the location servers according to their individual trust levels. Our evaluation shows significant improvement of privacy guarantees after applying the optimized share distribution, in comparison with the equal share distribution. The fourth related problem is the location update algorithm. A high number of different location servers n (corresponding to n privacy levels) may lead to significant communication overhead. Each update would require n messages from the mobile user to the location servers, especially in cases of high update rate. Therefore, we propose an optimized location update algorithm to decrease the number of messages sent without reducing the number of privacy levels and the user’s privacy.Item Open Access Visualization techniques for parallel coordinates(2013) Heinrich, Julian; Weiskopf, Daniel (Prof. Dr.)Visualization plays a key role in knowledge discovery, visual data exploration, and visual analytics. Static images are an effective tool for visual communication, summarization, and pattern extraction in large and complex datasets. Only together with human-computer-interaction techniques, visual interfaces enable an analyst to explore large information spaces and to drive the whole analytical reasoning process. Scatterplots and parallel coordinates are well-recognized visualization techniques that are commonly employed for statistics (both explorative and descriptive) and data-mining, but are also gaining importance for scientific visualization. While scatterplots are restricted to the display of at most three dimensions due to the orthogonal layout of coordinate axes, a parallel arrangement allows for the visualization of multiple attributes of a dataset. Although both techniques rely on projections of higher-dimensional geometry and are related by a point–line duality, parallel coordinates enjoy great popularity for the visualization and analysis of multivariate data. Despite their popularity, parallel coordinates are subject to a number of limitations that remain to be solved. For large datasets, the potentially high amount of overlapping lines may hinder the observer from visually extracting meaningful patterns. Encoding observations with polylines make it difficult to follow lines over all dimensions, as they lose visual continuation across the axes. Clusters cannot be represented by the geometry of lines, and the order of axes has a high impact on the patterns exhibited by parallel coordinates. This thesis presents visualization techniques for parallel coordinates that address these limitations. As a foundation, an extensive review of the state of the art of parallel coordinates will be given. Based on the point–line duality, the existing model of continuous scatterplots is adapted to parallel coordinates for the visualization of data defined on continuous domains. To speed up computation and obtain interactive frame rates, a scalable and progressive rendering algorithm is introduced that further allows for arbitrary reconstruction and interpolation schemes. A curve-bundling model for parallel coordinates is evaluated with a user study showing that bundling is effective for cluster visualization based on geometric cues while being equally capable of revealing correlations between neighboring axes. To address the axis-order problem, a graph-based approach is presented that allows for the visualization of all pairwise relations in a matrix layout without redundancy. Finally, the use of parallel coordinates is demonstrated for real datasets from computational fluid dynamics, motion capturing, bioinformatics, and systems biology.