Evolving Distributed Algorithms with Genetic Programming

Distributed systems are one of the most vital components of the economy. The most prominent example is probably the internet, a constituent element of our knowledge society. During the recent years, the number of novel network types has steadily increased. Amongst others, sensor networks, distributed systems composed of tiny computational devices with scarce resources, have emerged. The further development and heterogeneous connection of such systems imposes new requirements on the software development process. Mobile and wireless networks, for instance, have to organize themselves autonomously and must be able to react to changes in the environment and to failing nodes alike. Researching new approaches for the design of distributed algorithms may lead to methods with which these requirements can be met efficiently. In this thesis, one such method is developed, tested, and discussed in respect of its practical utility. Our new design approach for distributed algorithms is based on Genetic Programming, a member of the family of evolutionary algorithms. Evolutionary algorithms are metaheuristic optimization methods which copy principles from natural evolution. They use a population of solution candidates which they try to refine step by step in order to attain optimal values for predefined objective functions. The synthesis of an algorithm with our approach starts with an analysis step in which the wanted global behavior of the distributed system is specified. From this specification, objective functions are derived which steer a Genetic Programming process where the solution candidates are distributed programs. The objective functions rate how close these programs approximate the goal behavior in multiple randomized network simulations. The evolutionary process step by step selects the most promising solution candidates and modifies and combines them with mutation and crossover operators. This way, a description of the global behavior of a distributed system is translated automatically to programs which, if executed locally on the nodes of the system, exhibit this behavior. In our work, we test six different ways for representing distributed programs, comprising adaptations and extensions of well-known Genetic Programming methods (SGP, eSGP, and LGP), one bio-inspired approach (Fraglets), and two new program representations called Rule-based Genetic Programming (RBGP, eRBGP) designed by us. We breed programs in these representations for three well-known example problems in distributed systems: election algorithms, the distributed mutual exclusion at a critical section, and the distributed computation of the greatest common divisor of a set of numbers. Synthesizing distributed programs the evolutionary way does not necessarily lead to the envisaged results. In a detailed analysis, we discuss the problematic features which make this form of Genetic Programming particularly hard. The two Rule-based Genetic Programming approaches have been developed especially in order to mitigate these difficulties. In our experiments, at least one of them (eRBGP) turned out to be a very efficient approach and in most cases, was superior to the other representations.

Generic Finite Element Model for Mechanically Consistent Scaling of Composite Beam-to-column Joint with Welded Connection

To study the behaviour of beam-to-column composite connection more sophisticated finite element models is required, since component model has some severe limitations. In this research a generic finite element model for composite beam-to-column joint with welded connections is developed using current state of the art local modelling. Applying mechanically consistent scaling method, it can provide the constitutive relationship for a plane rectangular macro element with beam-type boundaries. Then, this defined macro element, which preserves local behaviour and allows for the transfer of five independent states between local and global models, can be implemented in high-accuracy frame analysis with the possibility of limit state checks. In order that macro element for scaling method can be used in practical manner, a generic geometry program as a new idea proposed in this study is also developed for this finite element model. With generic programming a set of global geometric variables can be input to generate a specific instance of the connection without much effort. The proposed finite element model generated by this generic programming is validated against testing results from University of Kaiserslautern. Finally, two illustrative examples for applying this macro element approach are presented. In the first example how to obtain the constitutive relationships of macro element is demonstrated. With certain assumptions for typical composite frame the constitutive relationships can be represented by bilinear laws for the macro bending and shear states that are then coupled by a two-dimensional surface law with yield and failure surfaces. In second example a scaling concept that combines sophisticated local models with a frame analysis using a macro element approach is presented as a practical application of this numerical model.

Analysen der beiden cis-regulierenden Sequenzelemente translational control element (TCE) und cytoplasmic polyadenylation element (CPE) in der Drosophila-Spermatogenese

Ein essentieller Bestandteil in dem Mechanismus der Translationskontrolle sind RNA-Pro­tein-Wechselwirkungen. Solche Interaktionen konnten in Translationssystemen an zwei unabhängigen cis-regulierenden Elementen durch in vitro-Bindungsanalysen mit individu­ellen rekombinanten Proteinen dokumentiert werden. Im Fall des translational control elements (TCE), welches ein konserviertes Sequenz-Ele­ment in der Mst(3)CGP-Genfamilie darstellt, wird eine negative Translationskontrolle durch die Bindung der Proteine CG3213, CG12470, CG1898, dFMR1, Exuperantia und Orb2 an diese Sequenz vermittelt (Stinski, 2011). Neben den in Bindungsstudien positiv getesteten Kandidaten dFMR1 und Orb2 (Stinski, 2011) wurde in der vorliegenden Dis­sertation CG3213 als weiterer direkter Bindungspartner an das TCE dokumentiert. Ein Abgleich der genomweiten Zusammenstellung von Proteininteraktionen in der Datenbank InterologFinder lieferte zwei weitere potentielle Kandidaten: CG34404 und CG3727. Al­lerdings schließen Northern-Analysen und das Proteinexpressionsmuster eine zentrale Rolle in der Drosophila-Spermatogenese für diese nahezu aus. In Kolokalisationsstudien einiger TCE-Komplex-Kandidaten mit CG3213 als Referenz konnten eindeutige Überein­stimmungen der Fluoreszenzmuster mit CG12470 in der postmeiotischen Phase be­schrieben werden, wohingegen mit Orb2 (postmeiotisch) und CG1898 (prämeiotisch) nur eine geringe Kolokalisation erkannt wurde. Punktstrukturen in den Verteilungsmustern sowohl von CG3213 als auch von CG12470 ließen sich nicht mit ER- und mitochondrien­spezifischen Markern korrelieren. Im Anschluss der Meiose konnte eine deutliche Intensitätserhöhung des CG3213-Proteins beobachtet werden, was eventuell durch eine veränderte Translationseffizienz zustande kommen könnte. Exuperantia (Exu) stellt einen bekannten Regulator für eine Reihe von translationskontrollierten mRNAs dar (Wang und Hazelrigg, 1994). Die Quantifizierungen der CG3213-mRNA in exu-mutantem Hintergrund bestätigen, dass auch die Transkript­menge der CG3213-mRNA durch Exu reguliert wird, was die obige Interpretation stützen würde. Für das zweite cis-regulierende Element, das cytoplasmic polyadenylation element (CPE), konnte eine direkte Bindung mit dem CPEB-Homolog in Drosophila (Orb2) gezeigt wer­den, welches auch eine Komponente des mst87F-RNP-Komplexes ist. Ein vermuteter Interaktionspartner dieses CPEBs ist Tob, weshalb die Verteilung beider Proteine in einem Kombinationsstamm verglichen wurde. In dem teilweise übereinstimmenden Fluoreszenz­muster ist Tob an den distalen Spermatidenenden auffallend konzentriert. Das gesamte Tob-Muster jedoch legt eine Verteilung in den Mitochondrien nahe, wie die MitoTracker®-Färbung belegt. Somit wurde erstmals ein Mitglied der Tob/BTG-Genfamilie in der Droso­phila-Spermatogenese mit Mitochondrien in Verbindung gebracht. Die Lokalisierung die­ser Proteine ist bislang unklar, jedoch konnte eine Kernlokalisation trotz der N-terminalen NLS-Sequenz mit Hilfe einer Kernfärbung ausgeschlossen werden.

Learning Commonsense Categorical Knowledge in a Thread Memory System

If we are to understand how we can build machines capable of broad purpose learning and reasoning, we must first aim to build systems that can represent, acquire, and reason about the kinds of commonsense knowledge that we humans have about the world. This endeavor suggests steps such as identifying the kinds of knowledge people commonly have about the world, constructing suitable knowledge representations, and exploring the mechanisms that people use to make judgments about the everyday world. In this work, I contribute to these goals by proposing an architecture for a system that can learn commonsense knowledge about the properties and behavior of objects in the world. The architecture described here augments previous machine learning systems in four ways: (1) it relies on a seven dimensional notion of context, built from information recently given to the system, to learn and reason about objects' properties; (2) it has multiple methods that it can use to reason about objects, so that when one method fails, it can fall back on others; (3) it illustrates the usefulness of reasoning about objects by thinking about their similarity to other, better known objects, and by inferring properties of objects from the categories that they belong to; and (4) it represents an attempt to build an autonomous learner and reasoner, that sets its own goals for learning about the world and deduces new facts by reflecting on its acquired knowledge. This thesis describes this architecture, as well as a first implementation, that can learn from sentences such as ``A blue bird flew to the tree'' and ``The small bird flew to the cage'' that birds can fly. One of the main contributions of this work lies in suggesting a further set of salient ideas about how we can build broader purpose commonsense artificial learners and reasoners.

Fast Sorting on a Distributed-Memory Architecture

We consider the often-studied problem of sorting, for a parallel computer. Given an input array distributed evenly over p processors, the task is to compute the sorted output array, also distributed over the p processors. Many existing algorithms take the approach of approximately load-balancing the output, leaving each processor with Θ(n/p) elements. However, in many cases, approximate load-balancing leads to inefficiencies in both the sorting itself and in further uses of the data after sorting. We provide a deterministic parallel sorting algorithm that uses parallel selection to produce any output distribution exactly, particularly one that is perfectly load-balanced. Furthermore, when using a comparison sort, this algorithm is 1-optimal in both computation and communication. We provide an empirical study that illustrates the efficiency of exact data splitting, and shows an improvement over two sample sort algorithms.

Memory Hierarchy Hardware-Software Co-design in Embedded Systems

The memory hierarchy is the main bottleneck in modern computer systems as the gap between the speed of the processor and the memory continues to grow larger. The situation in embedded systems is even worse. The memory hierarchy consumes a large amount of chip area and energy, which are precious resources in embedded systems. Moreover, embedded systems have multiple design objectives such as performance, energy consumption, and area, etc. Customizing the memory hierarchy for specific applications is a very important way to take full advantage of limited resources to maximize the performance. However, the traditional custom memory hierarchy design methodologies are phase-ordered. They separate the application optimization from the memory hierarchy architecture design, which tend to result in local-optimal solutions. In traditional Hardware-Software co-design methodologies, much of the work has focused on utilizing reconfigurable logic to partition the computation. However, utilizing reconfigurable logic to perform the memory hierarchy design is seldom addressed. In this paper, we propose a new framework for designing memory hierarchy for embedded systems. The framework will take advantage of the flexible reconfigurable logic to customize the memory hierarchy for specific applications. It combines the application optimization and memory hierarchy design together to obtain a global-optimal solution. Using the framework, we performed a case study to design a new software-controlled instruction memory that showed promising potential.

Memory Usage Inference for Object-Oriented Programs

We present a type-based approach to statically derive symbolic closed-form formulae that characterize the bounds of heap memory usages of programs written in object-oriented languages. Given a program with size and alias annotations, our inference system will compute the amount of memory required by the methods to execute successfully as well as the amount of memory released when methods return. The obtained analysis results are useful for networked devices with limited computational resources as well as embedded software.

Failure-Oblivious Computing and Boundless Memory Blocks

Memory errors are a common cause of incorrect software execution and security vulnerabilities. We have developed two new techniques that help software continue to execute successfully through memory errors: failure-oblivious computing and boundless memory blocks. The foundation of both techniques is a compiler that generates code that checks accesses via pointers to detect out of bounds accesses. Instead of terminating or throwing an exception, the generated code takes another action that keeps the program executing without memory corruption. Failure-oblivious code simply discards invalid writes and manufactures values to return for invalid reads, enabling the program to continue its normal execution path. Code that implements boundless memory blocks stores invalid writes away in a hash table to return as the values for corresponding out of bounds reads. he net effect is to (conceptually) give each allocated memory block unbounded size and to eliminate out of bounds accesses as a programming error. We have implemented both techniques and acquired several widely used open source servers (Apache, Sendmail, Pine, Mutt, and Midnight Commander).With standard compilers, all of these servers are vulnerable to buffer overflow attacks as documented at security tracking web sites. Both failure-oblivious computing and boundless memory blocks eliminate these security vulnerabilities (as well as other memory errors). Our results show that our compiler enables the servers to execute successfully through buffer overflow attacks to continue to correctly service user requests without security vulnerabilities.

Reforç d’un element estructural mitjançant l’adhesió de làmines de compòsits reforçats amb fibres (FRP)

Aquest treball final de carrera és un estudi del reforç d’un element estructural de formigó per mitjà de fibres FRP. Podem assimilar-lo a una guia pràctica per tal que un enginyer amb coneixements de construcció, pugui reforçar un membre que ha sofert danys produïts per aguantar càrregues, oscil·lacions, etc.per les que no havia estat dissenyat. El projecte conté teoria del FRP per tal de conèixer el material que utilitzarem pel nostre reforç, les normatives i prenormatives que s’utilitzen per fer el disseny, i un exemple pràctic de càlcul del reforç d’una biga sotmesa a flexió i el confinament d’un pilar, que són les dues opcions més utilitzades per reforçar amb FRP. El reforç d’estructures de formigó és el camp de la construcció on més ràpidament i amb major èxit s’estan aplicant els reforços amb FRP, degut a les propietats tant avantatjoses que presenten, entre altres, resistència a la corrosió i lleugeresa, que es tradueix en estalvi de transport i posada en obra

Sexual orientation and spatial memory

Resumen tomado de la publicaci??n

Attention, memory and verbal learning and their relation to schizotypal traits in unaffected parents of schizophrenic patients

The main objective of this ex post facto study is to compare the differences in cognitive functions and their relation to schizotypal personality traits between a group of unaffected parents of schizophrenic patients and a control group. A total of 52 unaffected biological parents of schizophrenic patients and 52 unaffected parents of unaffected subjects were assessed in measures of attention (Continuous Performance Test- Identical Pairs Version, CPT-IP), memory and verbal learning (California Verbal Learning Test, CVLT) as well as schizotypal personality traits (Oxford-Liverpool Inventory of Feelings and Experiences, O-LIFE). The parents of the patients with schizophrenia differ from the parents of the control group in omission errors on the Continuous Performance Test- Identical Pairs, on a measure of recall and on two contrast measures of the California Verbal Learning Test. The associations between neuropsychological variables and schizotpyal traits are of a low magnitude. There is no defined pattern of the relationship between cognitive measures and schizotypal traits

El papel de la memoria de trabajo en el cálculo mental un cuarto de siglo después de Hitch = The role of working memory in mental arithmetic a quarter of century after Hitch

Desde que Hitch (1978) publicó el primer estudio sobre el rol de la memoria de trabajo en el cálculo han ido aumentando las investigaciones en este campo. Muchos trabajos han estudiado un único subsistema, pero nuestro objetivo es identificar qué subsistema de la memoria de trabajo (bucle fonológico, agenda viso-espacial o ejecutivo central) está más implicado en el cálculo mental. Para ello hemos realizado un estudio correlacional en el que hemos administrado dos pruebas aritméticas y nueve pruebas de la “Bateria de Test de Memòria de Treball” de Pickering, Baqués y Gathercole (1999) a una muestra de 94 niños españoles de 7-8 años. Nuestros resultados indican que el bucle fonológico y sobretodo el ejecutivo central inciden de forma estadísticamente significativa en el rendimiento aritmético