Les algorithmes d'evaluation parallele des expressions et des circuits arithmetiques peuvent etre vus comme des extracteurs du parallelisme intrinseque contenu dans les programmes sequentiels, parallelisme qui depasse celui qui peut etre lu sur le graphe de precedence et qui tient a la semantique des operateurs utilises. La connaissance des proprietes algebriques, comme l'associativite ou la distributivite, permet une reorganisation des calculs qui n'affecte pas les resultats. Plus la structure algebrique utilisee sera riche en proprietes, plus il sera possible d'en tirer parti pour ameliorer les algorithmes d'evaluation. Generalisant les algorithmes concus pour les semi-anneaux, nous proposons un algorithme qui ameliore les majorations precedemment connues pour la contraction de circuits arithmetiques dans un treillis. Des simulations de cet algorithme ont permis de mettre en evidence ses qualites de << predicteur automatique de complexite >>. Reorganiser explicitement les calculs a l'aide de ces algorithmes, c'est-a-dire realiser un compilateur complet, permet de comparer la realite des algorithmes paralleles sur machines a memoire distribuee et la puissance des algorithmes theoriques. Un prototype a ete realise, base sur une simplification/extension du langage C. Enfin, l'interet de ces techniques dans le domaine de la parallelisation des nids de boucles, pour guider la recherche de reductions cachees dans ces nids, semble prometteuse, parce qu'elle est peu couteuse a mettre en oeuvre et fournit des informations de qualite. En cela, les recherches en algorithmique parallele theorique rejoignent les preoccupations de la parallelisation effective.

Recent technological advances are causing an explosion in the production of sequential data. Biological sequences, web logs and time series are represented as strings. Currently, strings are stored, managed and queried in an ad-hoc fashion because they lack a standardized data model and query language. String queries are computationally demanding, especially when strings are long and numerous. Existing approaches cannot handle the growing number of strings produced by environmental, healthcare, bioinformatic, and space applications. There is a trade- off between performing analytics efficiently and scaling to thousands of cores to finish in reasonable times. In this thesis, we introduce a data model that unifies the input and output representations of core string operations. We define a declarative query language for strings where operators can be pipelined to form complex queries. A rich set of core string operators is described to support string analytics. We then demonstrate a database system for string analytics based on our model and query language. In particular, we propose the use of a novel data structure augmented by efficient parallel computation to strike a balance between preprocessing overheads and query execution times. Next, we delve into repeated motifs extraction as a core string operation for large-scale string analytics. Motifs are frequent patterns used, for example, to identify biological functionality, periodic trends, or malicious activities. Statistical approaches are fast but inexact while combinatorial methods are sound but slow. We introduce ACME, a combinatorial repeated motifs extractor. We study the spatial and temporal locality of motif extraction and devise a cache-aware search space traversal technique. ACME is the only method that scales to gigabyte- long strings, handles large alphabets, and supports interesting motif types with minimal overhead. While ACME is cache-efficient, it is limited by being serial. We devise a lightweight parallel space traversal technique, called FAST, that enables ACME to scale to thousands of cores. High degree of concurrency is achieved by partition- ing the search space horizontally and balancing the workload among cores with minimal communication overhead. Consequently, complex queries are solved in minutes instead of days. ACME is a versatile system that runs on workstations, clusters, and supercomputers. It is the first to utilize a supercomputer and scale to 16 thousand CPUs. Merely using more cores does not guarantee efficiency, because of the related overheads. To this end, we introduce an automatic tuning mechanism that suggests the appropriate number of cores to meet user constraints in terms of runtime while minimizing the financial cost of cloud resources. Particularly, we study workload frequency distributions then build a model that finds the best problem decomposition and estimates serial and parallel runtimes. Finally, we generalize our automatic tuning method as a general method, called APlug. APlug can be used in other applications and we integrate it with systems for molecular docking and multiple sequence alignment.

The complexity of SPARQL queries and RDF applications poses great challenges on distributed RDF management systems. SPARQL workloads are dynamic and con- sist of queries with variable complexities. Hence, systems that use static partitioning su↵er from communication overhead for workloads that generate excessive communi- cation. Concurrently, RDF applications are becoming more sophisticated, mandating analytical operations that extend beyond SPARQL queries. Being primarily designed and optimized to execute SPARQL queries, which lack procedural capabilities, exist- ing systems are not suitable for rich RDF analytics. This dissertation tackles the problem of accelerating SPARQL queries and RDF analytics on distributed shared-nothing RDF systems. First, a distributed RDF en- gine, coined AdPart, is introduced. AdPart uses lightweight hash partitioning for sharding triples using their subject values; rendering its startup overhead very low. The locality-aware query optimizer of AdPart takes full advantage of the partition- ing to (i) support the fully parallel processing of join patterns on subjects and (ii) minimize data communication for general queries by applying hash distribution of intermediate results instead of broadcasting, wherever possible. By exploiting hash- based locality, AdPart achieves better or comparable performance to systems that employ sophisticated partitioning schemes. To cope with workloads dynamism, AdPart is extended to dynamically adapt to workload changes. AdPart monitors the data access patterns and dynamically redis- tributes and replicates the instances of the most frequent patterns among workers.Consequently, the communication cost for future queries is drastically reduced or even eliminated. Experiments with synthetic and real data verify that AdPart starts faster than all existing systems and gracefully adapts to the query load. Finally, to support and accelerate rich RDF analytical tasks, a vertex-centric RDF analytics framework is proposed. The framework, named SPARTex, bridges the gap between RDF and graph processing. To do so, SPARTex: (i) implements a generic SPARQL operator as a vertex-centric program. The operator is coupled with an optimizer that generates e cient execution plans. (ii) It allows SPARQL to invoke vertex-centric programs as stored procedures. Finally, (iii) it provides a unified in- memory data store that allows the persistence of intermediate results. Consequently, SPARTex can e ciently support RDF analytical tasks consisting of complex pipeline of operators.

Hereditäre Kardiomyopathien sind durch klinische und genetische Heterogenität gekennzeichnet, welche die Kardiogenetik vor Herausforderungen stellt. In dieser Arbeit wurden manche dieser Herausforderungen angegangen, indem anhand einer Kohorte von 61 Patienten mit Kardiomyopathie bzw. primärer Arrhythmie eine Exom-Diagnostik mit anschließender stufenweiser Datenanalyse vorgenommen wurde. Ein Ziel der Arbeit war, die aktuellen diagnostischen Detektionsraten zu prüfen sowie zu bewerten, ob eine erweiterte Exom-Diagnostik im Vergleich zur üblichen Genpanel-Analyse einen diagnostischen Zugewinn bringt. Zudem sollten potenzielle Krankheitsgene sowie komplexe Genotypen identifiziert werden. Die Ergebnisse zeigten, dass bei insgesamt 64% der Patienten eine Variante von Interesse gefunden wurde. Hervorzuheben ist die hohe Detektionsrate in der größten Subkohorte, die aus Patienten mit dilatativer bzw. linksventrikulärer Non-Compaction Kardiomyopathie bestand: 69% und damit höher im Vergleich zur in der Literatur berichteten Detektionsrate von bis zu 50%. Im Rahmen der stufenweisen Daten-Auswertung zeigte sich zwar, dass die meisten kausalen Varianten in den phänotypspezifischen Panels zu finden waren, die Analyse eines erweiterten Panels mit 79 Genen sowie der Gesamtexom-Daten aber zu einer zusätzlichen Aufklärungsquote von 13% bzw. 5% führte. Durch die Erweiterung der Diagnostik konnten interessante, teilweise neue Assoziationen zwischen Genotyp und Phänotyp sowie neue Kandidatengene identifiziert werden. Das beste Beispiel dafür ist eine trunkierende Variante im STK38-Gen, das an der Phosphorylierung eines Regulators der Expression kardialer Gene beteiligt ist. Zusammenfassend konnte gezeigt werden, dass, obwohl die Detektionsrate von Genpanels für die Routine-Diagnostik akzeptabel ist, die Anwendung von Exom-Diagnostik einen diagnostischen Zugewinn, die Entdeckung von interessanten Genotyp-Phänotyp-Korrelationen sowie die Identifizierung von Kandidatengenen ermöglicht. / Hereditary cardiomyopathies are characterized by clinical and genetic heterogeneity, which poses challenges to genetic diagnostics in cardiogenetics. In this study, some of these challenges were addressed on the basis of the genetic analysis of 61 cardiomyopathy and arrhythmia patients using exome sequencing with subsequent stepwise analysis of the genetic data. One objective of the study was to examine the current diagnostic yield of genetic analysis as well as to assess the diagnostic benefit of an extended exome analysis vs. targeted gene panel analysis. Another aim was to identify novel candidate genes and describe new genotype-phenotype correlations. Regarding the results, a variant of interest could be detected in 64% of the patients. Of note is the high detection rate in the main subcohort of patients with dilated cardiomyopathy and/or left ventricular noncompaction cardiomyopathy: 69% vs. the reported detection rate of max. 50% in the literature. To evaluate the additional diagnostic benefit of extensive exome testing, a stepwise analysis of the exome data was performed. It was shown here that most of the variants of interest were detected in the phenotype-specific core gene panels; however, the analysis of an extended gene set with 79 genes and subsequently of the complete exome data led to an additional diagnostic yield of 13% and 5% respectively. Through the expansion of the genetic analysis, interesting or new genotype-phenotype correlations could be documented and candidate genes could be identified. The best candidate was a truncating variant in STK38, a gene coding for a kinase that phosphorylates a transcription regulator of genes encoding for cardiac sarcomere proteins. In conclusion, although the detection rate of gene panels is acceptable for the clinical routine, the use of exome analysis enables the highest possible diagnostic yield, the detection of interesting genotype-phenotype correlations as well as the identification of new candidate genes.

Durch die parallele Programmierung wird ermöglicht, dass Programme nebenläufig auf mehreren CPU-Kernen oder CPUs ausgeführt werden können. Um das parallele Programmieren zu erleichtern, wurden diverse Sprachen (z.B. Erlang) und Bibliotheken (z.B. OpenMP) aufbauend auf parallele Programmiermodelle (z.B. Parallel Random Access Machine) entwickelt. Möchte z.B. ein Softwarearchitekt sich in einem Projekt für ein Programmiermodell entscheiden, muss er dabei auf mehrere wichtige Kriterien (z.B. Abhängigkeiten zur Hardware) achten. erleichternd für diese Suche sind Übersichten, die die Programmiermodelle in diesen Kriterien unterscheiden und ordnen. Werden existierenden Übersichten jedoch betrachtet, finden sich Unterschiede in der Klassifizierung, den verwendeten Begriffen und den aufgeführten Programmiermodellen. Diese Arbeit begleicht dieses Defizit, indem zuerst durch ein Systematic Literature Review die existierenden Taxonomien gesammelt und analysiert werden. Darauf aufbauend wird eine einheitliche Taxonomie erstellt. Mit dieser Taxonomie kann eine Übersicht über die parallelen Programmiermodelle erstellt werden. Diese Übersicht wird zusätzlich durch Informationen zu den jeweiligen Abhängigkeiten der Programmiermodelle zu der Hardware-Architektur erweitert werden. Der Softwarearchitekt (oder Projektleiter, Softwareentwickler,...) kann damit eine informierte Entscheidung treffen und ist nicht gezwungen alle Programmiermodelle einzeln zu analysieren.

Vorgestellt wird ein Ansatz zur mathematischen Beschreibung der Erregungsausbreitung in einer Neuronenpopulation. Beschrieben werden im Detail die Einzugsgebiete der Erregungsausbreitung und die Intensität von Wechselwirkungen innerhalb solcher Einzugsgebiete. Als schwierig erweist sich dabei die Trennung von Ursache und Reaktion. In einer natürlichen Neuronenpopulationen sind Transmittermoleküle, die Botenstoffe zwischen den Neuronen, sowohl Erregung als auch Reaktion. Sie verursachen, angelagert auf der Membranoberfläche eines Neurons, dessen Erregung in Form einer Depolarisation; sie sind gleichermaßen aber auch Reaktion eines Neurons auf eine stattgefundene Erregung, wenn sie aus den Vesikeln des synaptischen Endknopfes in den synaptischen Spalt ausgeschüttet werden. Zur Überwindung dieser Dualität wird der Begriff Wirkstoff definiert. Ein Wirkstoff bewirkt etwas, er besitzt unter diesem Gesichtspunkt ein bestimmtes Potential. Die Ausbreitung von Wirkstoffen, nämlich die Wirkungsübertragung, ereignet sich extrazellulär in Raum und Zeit. Im Detail wird dargelegt, wie aus dem punktuellen Ausbreitungsverhaltens einer Erregung über das unvollständig globale Ausbreitungsverhalten auf das vollständig globale Ausbreitungsverhalten einer Erregung in einer Neuronenpopulation geschlußfolgert werden kann. Das Ziel besteht darin, einen Ansatz zur analytischen Beschreibung der Erregungsausbreitung in natürlichen Neuronenpopulationen vorzubereiten und in seiner Sinnfälligkeit zu plausibilisieren. Sinnfällig erscheinen solche Betrachtungen im Hinblick auf den Entwurf STOCHASTISCH MASSIV PARALLELER SYSTEME. Darunter werden technische Systeme verstanden, die sowohl in ihrem technischen Konzept als auch in ihrer Wirkungsweise Korrespondenzen zu natürlichen Neuronenpopulationen aufweisen. Ausgehend von der Struktur und dem Erregungsmechanismus eines Neurons soll in der Perspektive ein analytisches Entwurfswerkzeug für STOCHASTISCH MASSIV PARALLELE SYSTEME entwickelt werden.

The limited capacity of working memory forces people to update its contents continuously. Two aspects of the updating process were investigated in the present experimental series. The first series concerned the question if it is possible to update several representations in parallel. Similar results were obtained for the updating of object features as well as for the updating of whole objects, participants were able to update representations in parallel. The second experimental series addressed the question if working memory representations which were replaced in an updating disappear directly or interfere with the new representations. Evidence for the existence of old representations was found under working memory conditions and under conditions exceeding working memory capacity. These results contradict the hypothesis that working memory contents are protected from proactive interference of long-term memory contents. / Aufgrund der begrenzten Kapazität des Arbeitsgedächtnisses müssen seine Inhalte ständig aktualisiert werden. Zwei Aspekte des Aktualisierungsprozesses wurden in Experimentalserien untersucht. Die erste Serie betraf die Frage, ob es möglich ist, mehrere Repräsentationen gleichzeitig zu aktualisieren. Ähnliche Ergebnisse ergaben sich sowohl für das Aktualisieren von Objektmerkmalen als auch für das Aktualisieren von ganzen Objekten, die Versuchsteilnehmer konnten Repräsentationen gleichzeitig aktualisieren. In der zweiten Experimentalserie wurde die Frage untersucht, ob Arbeitsgedächtnisrepräsentationen, die bei einer Aktualisierung ersetzt worden sind, sofort verschwinden oder mit den neuen Repräsentationen interferieren. Evidenz für das Vorhandensein alter Repräsentationen wurde unter Arbeitsgedächtnisbedingungen und unter Bedingungen, bei denen die Arbeitsgedächtniskapazität überschritten wird, gefunden. Diese Ergebnisse widersprechen der Hypothese, dass Arbeitsgedächtnisinhalte vor proaktiver Interferenz aus dem Langzeitgedächtnis geschützt sind.

Die Common Object Request Broker Architecture (CORBA) der Object Management Group (OMG) bietet die Chance, nicht nur eine Plattform fuer neue verteilte Anwendungen zu sein, sondern erlaubt es auch, bestehende Anwendungen und Altsoftware hersteller- und systemuebergreifend zu integrieren. Diese Eigenschaft hebt CORBA von anderen Programmierplattformen ab und gibt CORBA das Potential, eine aussichtsreiche Basis fuer kuenftige Anwendungssysteme zu sein. Das Ziel dieser Studienarbeit besteht darin, die Umsetzbarkeit verschiedener Interaktionsarten in CORBA zu untersuchen und an Beispielen praktisch auszuprobieren. Moegliche Ablaufformen aus der Literatur, aus den Systemen DCE und MPI und anhand eigener Ueberlegungen werden im ersten Teil dieser Arbeit systematisch zusammengefasst. Danach folgt eine ausfuerliche Behandlung der Architektur von CORBA und der hier moeglichen Ablaufformen und Interaktionsszenarien. Abschliessend werden acht verschiedene Versionen eines einfachen verteilten Woerterbuches vorgestellt, um einige der in CORBA realisierten Konzepte am praktischen Beispiel zu verdeutlichen. Als CORBA-Plattform stand Orbix-MT 2.0.1 (multi-threaded) der Firma IONA Technologies Ltd. unter Solaris 2.x zur Verfuegung.

This work considers black-box Bayesian inference over high-dimensional parameter spaces. The well-known and widely respected adaptive Metropolis (AM) algorithm is extended herein to asymptotically scale uniformly with respect to the underlying parameter dimension, by respecting the variance, for Gaussian targets. The result- ing algorithm, referred to as the dimension-independent adaptive Metropolis (DIAM) algorithm, also shows improved performance with respect to adaptive Metropolis on non-Gaussian targets. This algorithm is further improved, and the possibility of probing high-dimensional targets is enabled, via GPU-accelerated numerical libraries and periodically synchronized concurrent chains (justified a posteriori). Asymptoti- cally in dimension, this massively parallel dimension-independent adaptive Metropolis (MPDIAM) GPU implementation exhibits a factor of four improvement versus the CPU-based Intel MKL version alone, which is itself already a factor of three improve- ment versus the serial version. The scaling to multiple CPUs and GPUs exhibits a form of strong scaling in terms of the time necessary to reach a certain convergence criterion, through a combination of longer time per sample batch (weak scaling) and yet fewer necessary samples to convergence. This is illustrated by e ciently sampling from several Gaussian and non-Gaussian targets for dimension d 1000.

This thesis presents a contribution to the field of performance analysis for Input/Output (I/O) related problems, focusing on the area of High Performance Computing (HPC). Beside the compute nodes, High Performance Computing systems need a large amount of supporting components that add their individual behavior to the overall performance characteristic of the whole system. Especially file systems in such environments have their own infrastructure. File operations are typically initiated at the compute nodes and proceed through a deep software stack until the file content arrives at the physical medium. There is a handful of shortcomings that characterize the current state of the art for performance analyses in this area. This includes a system wide data collection, a comprehensive analysis approach for all collected data, an adjusted trace event analysis for I/O related problems, and methods to compare current with archived performance data. This thesis proposes to instrument all soft- and hardware layers to enhance the performance analysis for file operations. The additional information can be used to investigate performance characteristics of parallel file systems. To perform I/O analyses on HPC systems, a comprehensive approach is needed to gather related performance events, examine the collected data and, if necessary, to replay relevant parts on different systems. One larger part of this thesis is dedicated to algorithms that reduce the amount of information that are found in trace files to the level that is needed for an I/O analysis. This reduction is based on the assumption that for this type of analysis all I/O events, but only a subset of all synchronization events of a parallel program trace have to be considered. To extract an I/O pattern from an event trace, only these synchronization points are needed that describe dependencies among different I/O requests. Two algorithms are developed to remove negligible events from the event trace. Considering the related work for the analysis of a parallel file systems, the inclusion of counter data from external sources, e.g. the infrastructure of a parallel file system, has been identified as a major milestone towards a holistic analysis approach. This infrastructure contains a large amount of valuable information that are essential to describe performance effects observed in applications. This thesis presents an approach to collect and subsequently process and store the data. Certain ways how to correctly merge the collected values with application traces are discussed. Here, a revised definition of the term "performance counter" is the first step followed by a tree based approach to combine raw values into secondary values. A visualization approach for I/O patterns closes another gap in the analysis process. Replaying I/O related performance events or event patterns can be done by a flexible I/O benchmark. The constraints for the development of such a benchmark are identified as well as the overall architecture for a prototype implementation. Finally, different examples demonstrate the usage of the developed methods and show their potential. All examples are real use cases and are situated on the HRSK research complex and the 100GBit Testbed at TU Dresden. The I/O related parts of a Bioinformatics and a CFD application have been analyzed in depth and enhancements for both are proposed. An instance of a Lustre file system was deployed and tuned on the 100GBit Testbed by the extensive use of external performance counters.