Scheduling dynamic dataflow graphs with model checking

With the shift towards many-core computer architectures, dataflow programming has been proposed as one potential solution for producing software that scales to a varying number of processor cores. Programming for parallel architectures is considered difficult as the current popular programming languages are inherently sequential and introducing parallelism is typically up to the programmer. Dataflow, however, is inherently parallel, describing an application as a directed graph, where nodes represent calculations and edges represent a data dependency in form of a queue. These queues are the only allowed communication between the nodes, making the dependencies between the nodes explicit and thereby also the parallelism. Once a node have the su cient inputs available, the node can, independently of any other node, perform calculations, consume inputs, and produce outputs. Data ow models have existed for several decades and have become popular for describing signal processing applications as the graph representation is a very natural representation within this eld. Digital lters are typically described with boxes and arrows also in textbooks. Data ow is also becoming more interesting in other domains, and in principle, any application working on an information stream ts the dataflow paradigm. Such applications are, among others, network protocols, cryptography, and multimedia applications. As an example, the MPEG group standardized a dataflow language called RVC-CAL to be use within reconfigurable video coding. Describing a video coder as a data ow network instead of with conventional programming languages, makes the coder more readable as it describes how the video dataflows through the different coding tools. While dataflow provides an intuitive representation for many applications, it also introduces some new problems that need to be solved in order for data ow to be more widely used. The explicit parallelism of a dataflow program is descriptive and enables an improved utilization of available processing units, however, the independent nodes also implies that some kind of scheduling is required. The need for efficient scheduling becomes even more evident when the number of nodes is larger than the number of processing units and several nodes are running concurrently on one processor core. There exist several data ow models of computation, with different trade-offs between expressiveness and analyzability. These vary from rather restricted but statically schedulable, with minimal scheduling overhead, to dynamic where each ring requires a ring rule to evaluated. The model used in this work, namely RVC-CAL, is a very expressive language, and in the general case it requires dynamic scheduling, however, the strong encapsulation of dataflow nodes enables analysis and the scheduling overhead can be reduced by using quasi-static, or piecewise static, scheduling techniques. The scheduling problem is concerned with nding the few scheduling decisions that must be run-time, while most decisions are pre-calculated. The result is then an, as small as possible, set of static schedules that are dynamically scheduled. To identify these dynamic decisions and to find the concrete schedules, this thesis shows how quasi-static scheduling can be represented as a model checking problem. This involves identifying the relevant information to generate a minimal but complete model to be used for model checking. The model must describe everything that may affect scheduling of the application while omitting everything else in order to avoid state space explosion. This kind of simplification is necessary to make the state space analysis feasible. For the model checker to nd the actual schedules, a set of scheduling strategies are de ned which are able to produce quasi-static schedulers for a wide range of applications. The results of this work show that actor composition with quasi-static scheduling can be used to transform data ow programs to t many different computer architecture with different type and number of cores. This in turn, enables dataflow to provide a more platform independent representation as one application can be fitted to a specific processor architecture without changing the actual program representation. Instead, the program representation is in the context of design space exploration optimized by the development tools to fit the target platform. This work focuses on representing the dataflow scheduling problem as a model checking problem and is implemented as part of a compiler infrastructure. The thesis also presents experimental results as evidence of the usefulness of the approach.

Tautomerism and Fragmentation of Biologically Active Hetero Atom (O, N)-Containing Acyclic and Cyclic Compounds Under Electron Ionization

In this thesis a total of 86 compounds containing the hetero atoms oxygen and nitrogen were studied under electron ionization mass spectrometry (EIMS). These compounds are biologically active and were synthesized by various research groups. The main attention of this study was paid on the fragmentations related to different tautomeric forms of 2- phenacylpyridines, 2-phenacylquinolines, 8-aryl-3,4-dioxo-2H,8H-6,7-dihydroimidazo- [2,1-c][1,2,4]triazines and aryl- and benzyl-substituted 2,3-dihydroimidazo[1,2-a]pyrimidine-5,7-(1H,6H)-diones. Also regio/stereospecific effects on fragmentations of pyrrolo- and isoindoloquinazolinones and naphthoxazine, naphthpyrrolo-oxazinone and naphthoxazino-benzoxazine derivatives were screened. Results were compared with NMR data, when available. The first part of thesis consists of theory and literature review of different types of tautomerism and fragmentation mechanisms in EIMS. The effects of tautomerism in biological systems are also briefly reviewed. In the second part of the thesis the own results of the author, based on six publications,are discussed. For 2-phenacylpyridines and 2-phenacylquinolines the correlation of different Hammett substituent constants to the relative abundances (RA) or total ion currents (% TIC) of selected ions were investigated. Although it was not possible to assign most of the ions formed unambiguously to the different tautomers, the linear fits of their RAs and % TICs can be related to changing contributions of different tautomeric forms. For dioxoimidazotriazines and imidazopyrimidinediones the effects of substituents were rather weak. The fragmentations were also found useful for obtaining structural information. Some stereoisomeric pairs of pyrrolo- and isoindoloquinazolines and regiomeric pairs of naphtoxazine derivatives showed clear differences in thir mass spectra. Some mechanisms are suggested for their fragmentations.

Methods of genetic diversity creation and functional display for directed evolution experiments

Protein engineering aims to improve the properties of enzymes and affinity reagents by genetic changes. Typical engineered properties are affinity, specificity, stability, expression, and solubility. Because proteins are complex biomolecules, the effects of specific genetic changes are seldom predictable. Consequently, a popular strategy in protein engineering is to create a library of genetic variants of the target molecule, and render the population in a selection process to sort the variants by the desired property. This technique, called directed evolution, is a central tool for trimming protein-based products used in a wide range of applications from laundry detergents to anti-cancer drugs. New methods are continuously needed to generate larger gene repertoires and compatible selection platforms to shorten the development timeline for new biochemicals. In the first study of this thesis, primer extension mutagenesis was revisited to establish higher quality gene variant libraries in Escherichia coli cells. In the second study, recombination was explored as a method to expand the number of screenable enzyme variants. A selection platform was developed to improve antigen binding fragment (Fab) display on filamentous phages in the third article and, in the fourth study, novel design concepts were tested by two differentially randomized recombinant antibody libraries. Finally, in the last study, the performance of the same antibody repertoire was compared in phage display selections as a genetic fusion to different phage capsid proteins and in different antibody formats, Fab vs. single chain variable fragment (ScFv), in order to find out the most suitable display platform for the library at hand. As a result of the studies, a novel gene library construction method, termed selective rolling circle amplification (sRCA), was developed. The method increases mutagenesis frequency close to 100% in the final library and the number of transformants over 100-fold compared to traditional primer extension mutagenesis. In the second study, Cre/loxP recombination was found to be an appropriate tool to resolve the DNA concatemer resulting from error-prone RCA (epRCA) mutagenesis into monomeric circular DNA units for higher efficiency transformation into E. coli. Library selections against antigens of various size in the fourth study demonstrated that diversity placed closer to the antigen binding site of antibodies supports generation of antibodies against haptens and peptides, whereas diversity at more peripheral locations is better suited for targeting proteins. The conclusion from a comparison of the display formats was that truncated capsid protein three (p3Δ) of filamentous phage was superior to the full-length p3 and protein nine (p9) in obtaining a high number of uniquely specific clones. Especially for digoxigenin, a difficult hapten target, the antibody repertoire as ScFv-p3Δ provided the clones with the highest affinity for binding. This thesis on the construction, design, and selection of gene variant libraries contributes to the practical know-how in directed evolution and contains useful information for scientists in the field to support their undertakings.

Computational models for and from biology : simple gene assembly and reaction systems

The advancement of science and technology makes it clear that no single perspective is any longer sufficient to describe the true nature of any phenomenon. That is why the interdisciplinary research is gaining more attention overtime. An excellent example of this type of research is natural computing which stands on the borderline between biology and computer science. The contribution of research done in natural computing is twofold: on one hand, it sheds light into how nature works and how it processes information and, on the other hand, it provides some guidelines on how to design bio-inspired technologies. The first direction in this thesis focuses on a nature-inspired process called gene assembly in ciliates. The second one studies reaction systems, as a modeling framework with its rationale built upon the biochemical interactions happening within a cell. The process of gene assembly in ciliates has attracted a lot of attention as a research topic in the past 15 years. Two main modelling frameworks have been initially proposed in the end of 1990s to capture ciliates’ gene assembly process, namely the intermolecular model and the intramolecular model. They were followed by other model proposals such as templatebased assembly and DNA rearrangement pathways recombination models. In this thesis we are interested in a variation of the intramolecular model called simple gene assembly model, which focuses on the simplest possible folds in the assembly process. We propose a new framework called directed overlap-inclusion (DOI) graphs to overcome the limitations that previously introduced models faced in capturing all the combinatorial details of the simple gene assembly process. We investigate a number of combinatorial properties of these graphs, including a necessary property in terms of forbidden induced subgraphs. We also introduce DOI graph-based rewriting rules that capture all the operations of the simple gene assembly model and prove that they are equivalent to the string-based formalization of the model. Reaction systems (RS) is another nature-inspired modeling framework that is studied in this thesis. Reaction systems’ rationale is based upon two main regulation mechanisms, facilitation and inhibition, which control the interactions between biochemical reactions. Reaction systems is a complementary modeling framework to traditional quantitative frameworks, focusing on explicit cause-effect relationships between reactions. The explicit formulation of facilitation and inhibition mechanisms behind reactions, as well as the focus on interactions between reactions (rather than dynamics of concentrations) makes their applicability potentially wide and useful beyond biological case studies. In this thesis, we construct a reaction system model corresponding to the heat shock response mechanism based on a novel concept of dominance graph that captures the competition on resources in the ODE model. We also introduce for RS various concepts inspired by biology, e.g., mass conservation, steady state, periodicity, etc., to do model checking of the reaction systems based models. We prove that the complexity of the decision problems related to these properties varies from P to NP- and coNP-complete to PSPACE-complete. We further focus on the mass conservation relation in an RS and introduce the conservation dependency graph to capture the relation between the species and also propose an algorithm to list the conserved sets of a given reaction system.

Monitoring Directed Energy Deposition Processes in Additive Manufacturing

The purpose of this study is to find out how laser based Directed Energy Deposition processes can benefit from different types of monitoring. DED is a type of additive manufacturing process, where parts are manufactured in layers by using metallic powder or metallic wire. DED processes can be used to manufacture parts that are not possible to manufacture with conventional manufacturing processes, when adding new geometries to existing parts or when wanting to minimize the scrap material that would result from machining the part. The aim of this study is to find out why laser based DED-processes are monitored, how they are monitored and what devices are used for monitoring. This study has been done in the form of a literature review. During the manufacturing process, the DED-process is highly sensitive to different disturbances such as fluctuations in laser absorption, powder feed rate, temperature, humidity or the reflectivity of the melt pool. These fluctuations can cause fluctuations in the size of the melt pool or its temperature. The variations in the size of the melt pool have an effect on the thickness of individual layers, which have a direct impact on the final surface quality and dimensional accuracy of the parts. By collecting data from these fluctuations and adjusting the laser power in real-time, the size of the melt pool and its temperature can be kept within a specified range that leads to significant improvements in the manufacturing quality. The main areas of monitoring can be divided into the monitoring of the powder feed rate, the temperature of the melt pool, the height of the melt pool and the geometry of the melt pool. Monitoring the powder feed rate is important when depositing different material compositions. Monitoring the temperature of the melt pool can give information about the microstructure and mechanical properties of the part. Monitoring the height and the geometry of the melt pool is an important factor in achieving the desired dimensional accuracy of the part. By combining multiple different monitoring devices, the amount of fluctuations that can be controlled will be increased. In addition, by combining additive manufacturing with machining, the benefits of both processes could be utilized.