Message Passing Interface (MPI) is a standard library interface for writing parallel programs. The MPI specification is broadly used for solving engineering and scientific problems on parallel computers, and MPICH2 is a popular MPI implementation developed at Argonne National Laboratory. The scalability of MPI implementations is very important for building high performance parallel computing applications. The initial TCP (Transmission Control Protocol) network module developed for Nemesis communication sub-system in the MPICH2 library, however, was not scalable in how it established connections: pairwise connections between all of an application's processes were established during the initialization of the application (the library call to MPI_Init), regardless of whether the connections were eventually needed or not. In this work, we have developed a new TCP network module for Nemesis that establishes connections on-demand. The on-demand connection establishment scheme is designed to improve the scalability of the TCP network module in MPICH2 library, aiming to reduce the initialization time and the use of operating system resources of MPI applications. Our performance benchmark results show that MPI_Init in the on-demand connection establishment scheme becomes a fast constant time operation, and the additional cost of establishing connections later is negligible. The on-demand connection establishment between two processes, especially when two processes attempt to connect to each other simultaneously, is a complex task due to race-conditions and thus prone to hard-to-reproduce defects. To assure ourselves of the correctness of the TCP network module, we modeled its design using the SPIN model checker, and verified safety and liveness properties stated as Linear Temporal Logic claims.

L'objectif du présent texte est de tenter de construire un modèle de l'acquisition des concepts mathématiques sans l'aide du langage en s'inspirant des thèses intuitionnistes de L.E.J. Brouwer et en les appliquant à des théories plus modernes de l'acquisition et de la représentation des concepts mathématiques, notamment, la théorie du sens des nombres de Stanislas Dehaene. Pour ce faire, nous initierons le lecteur à la pensée de Brouwer dans les deux premiers chapitres et développerons dans le troisième chapitre une nouvelle analyse de l'Intuition Primordiale de Brouwer dans laquelle il est possible d'identifier chaque élément impliqué dans l'acquisition des concepts mathématiques chez Brouwer et le rôle joué par chacun. Le chapitre quatre exposera la théorie de Dehaene selon laquelle nos capacités mathématiques sont le résultat de deux systèmes cognitifs de base, soit le système de répertoire d'objets et le système de représentation approximative de la numérosité. Nous tenterons ainsi d'améliorer le modèle de l'ontogenèse de Dehaene ainsi que les interprétations de Suzanne Carey, celles-ci soulignant le besoin de faire appel à d'autres systèmes de base incluant un système de représentation de l'ordre linéaire ainsi que le langage. Nous présenterons une hypothèse alternative en remarquant qu'une représentation approximative de la numérosité peut implicitement contenir une forme d'ordre et de relation de successeur capable de justifier une partie de l'apprentissage des listes de numéros chez les enfants. Aussi, nous tenterons d'expliquer le développement de concepts mathématiques plus avancés en nous basant sur la théorie de l'abstraction de Lawrence Barsalou, selon laquelle l'abstraction est une interprétation dynamique faite par des systèmes de symboles perceptuels. Nous pourrons alors expliquer la manière dont le système de répertoire d'objets réussit à développer une composante numérique en venant interpréter les représentations du système approximatif. Nous suggérerons enfin l'hypothèse que les concepts mathématiques puissent être aptes à se développer à mesure que ce système de répertoire d'objets produit des représentations structurées dans lesquelles les numérosités se voient regroupées de manière analogue au développement des nombres par l'IP de Brouwer. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Intuitionnisme, Abstraction, Concepts mathématiques, Fondements des mathématiques.

With the plateauing of processor frequencies and increase in energy consumption in computing, application developers are seeking new sources of performance acceleration. Heterogeneous platforms with multiple processor architectures offer one possible avenue to address these challenges. However, modern heterogeneous programming models tend to be either so low-level as to severely hinder programmer productivity, or so high-level as to limit optimization opportunities. The novel systems presented in this thesis strike a better balance between abstraction and transparency, enabling programmers to be productive and produce high-performance applications on heterogeneous platforms. This thesis starts by summarizing the strengths, weaknesses, and features of existing heterogeneous programming models. It then introduces and evaluates four novel heterogeneous programming models and runtime systems: JCUDA, CnC-CUDA, DyGR, and HadoopCL. We'll conclude by positioning the key contributions of each piece in this thesis relative to the state-of-the-art, and outline possible directions for future work.

Reinforcement learning is the problem faced by an agent that must learn behavior through trial-and-error interactions with a dynamic environment. Generally, the problem to be solved contains subtasks that repeat at different regions of the state space. Without any guidance an agent has to learn the solutions of all subtask instances independently, which degrades the learning performance. In this thesis, we propose two approaches to build connections between different regions of the search space leading to better utilization of gained experience and accelerate learning is proposed. In the first approach, we first extend existing work of McGovern and propose the formalization of stochastic conditionally terminating sequences with higher representational power. Then, we describe how to efficiently discover and employ useful abstractions during learning based on such sequences. The method constructs a tree structure to keep track of frequently used action sequences together with visited states. This tree is then used to select actions to be executed at each step. In the second approach, we propose a novel method to identify states with similar sub-policies, and show how they can be integrated into reinforcement learning framework to improve the learning performance. The method uses an efficient data structure to find common action sequences started from observed states and defines a similarity function between states based on the number of such sequences. Using this similarity function, updates on the action-value function of a state are reflected to all similar states. This, consequently, allows experience acquired during learning be applied to a broader context. Effectiveness of both approaches is demonstrated empirically by conducting extensive experiments on various domains.

Business process models are used within a range of organizational initiatives, where every stakeholder has a unique perspective on a process and demands the respective model. As a consequence, multiple process models capturing the very same business process coexist. Keeping such models in sync is a challenge within an ever changing business environment: once a process is changed, all its models have to be updated. Due to a large number of models and their complex relations, model maintenance becomes error-prone and expensive. Against this background, business process model abstraction emerged as an operation reducing the number of stored process models and facilitating model management. Business process model abstraction is an operation preserving essential process properties and leaving out insignificant details in order to retain information relevant for a particular purpose. Process model abstraction has been addressed by several researchers. The focus of their studies has been on particular use cases and model transformations supporting these use cases. This thesis systematically approaches the problem of business process model abstraction shaping the outcome into a framework. We investigate the current industry demand in abstraction summarizing it in a catalog of business process model abstraction use cases. The thesis focuses on one prominent use case where the user demands a model with coarse-grained activities and overall process ordering constraints. We develop model transformations that support this use case starting with the transformations based on process model structure analysis. Further, abstraction methods considering the semantics of process model elements are investigated. First, we suggest how semantically related activities can be discovered in process models-a barely researched challenge. The thesis validates the designed abstraction methods against sets of industrial process models and discusses the method implementation aspects. Second, we develop a novel model transformation, which combined with the related activity discovery allows flexible non-hierarchical abstraction. In this way this thesis advocates novel model transformations that facilitate business process model management and provides the foundations for innovative tool support. / Geschäftsprozessmodelle werden in einer Fülle organisatorischer Initiativen eingesetzt, wobei verschiedene Stakeholder individuelle Ansprüche an die Sicht auf den jeweiligen Prozess haben. Dies führt dazu, dass zu einem Geschäftsprozess eine Vielzahl unterschiedlicher Modelle existiert. In einer sich ständig verändernden Geschäftsumgebung ist es daher schwierig, diese Vielzahl von Modellen konsistent zu halten: Ändert sich sich ein Prozess, müssen alle Modelle, die ihn beschreiben, aktualisiert werden. Aufgrund der schieren Menge an Prozessmodellen und ihrer komplexen Beziehungen zueinander, erhöhen sich Aufwand und Kosten zur Pflege aller Modelle enorm. Vor diesem Hintergrund ermöglicht die Abstraktion von Geschäftsprozessmodellen, die Menge der Modelle zu reduzieren und damit ihre Verwaltung zu vereinfachen. Abstraktion von Geschäftsprozessmodellen bezeichnet eine Transformation eines Prozessmodells, so dass es für einen bestimmten Zweck besonders geeignet ist. Bei der Abstraktion von Geschäftsprozessen bleiben essentielle Eigenschaften eines Modells erhalten, während irrelevante Eigenschaften verworfen werden. Mehrere Studien stellen Prozessmodellabstraktion in den Fokus und konzentrieren sich auf konkrete Anwendungsfälle, für die sie geeignete Transformationen entwickelt haben. Diese Dissertation untersucht das Problem der Prozessmodellabstraktion und systematisiert die Lösung in einem Framework. Aktuelle Anforderungen der Industrie an die Abstraktion von Prozessmodellen wurden recherchiert und in einem Katalog von Anwendungsfällen zusammengefasst, von denen ein besonderer für die weiteren Untersuchungen ausgewählt wurde. In diesem Fall erwartet der Nutzer ein Modell niedrigeren Detailgrades, in welchem die Kontrollflussbeziehungen des Ursprungsmodells erhalten bleiben. Beginnend bei Modelltransformationen, die auf der Analyse der Prozessmodellstruktur aufbauen, entwickeln wir neuartige Abstraktionsoperationen zur Unterstützung dieses Anwendungsfalles. Darüber hinaus untersuchen wir Abstraktionsmethoden, welche die Semantik von Prozessmodellelementen berücksichtigen. Zum einen zeigen wir, wie Aktivitäten ermittelt werden können, die miteinander in semantischer Beziehung stehen - ein Problem, das bisher nur unzureichend betrachtet wurde. Die vorgeschlagenen Methoden werden mithilfe industrieller Prozessmodellsammlungen validiert und deren Umsetzung diskutiert. Zum anderen schlagen wir eine innovative Modelltransformation zur nicht-hierarchischen Abstraktion von Prozessmodellen vor. Dieser liegt die Ermittlung in Beziehung stehender Aktivitäten zugrunde. Demzufolge präsentiert diese Arbeit eine originäre Methode zur Prozessmodellabstraktion, die die Verwaltung von Geschäftsprozessmodellen vereinfacht und den Grundstein für innovative Softwarewerkzeuge legt.

Finding an efficient data reduction method for large-scale problems is an imperative task. In this paper, we propose a similarity-based self-constructing fuzzy clustering algorithm to do the sampling of instances for the classification task. Instances that are similar to each other are grouped into the same cluster. When all the instances have been fed in, a number of clusters are formed automatically. Then the statistical mean for each cluster will be regarded as representing all the instances covered in the cluster. This approach has two advantages. One is that it can be faster and uses less storage memory. The other is that the number of new representative instances need not be specified in advance by the user. Experiments on real-world datasets show that our method can run faster and obtain better reduction rate than other methods.

<p>As a result of Web 2.0 technologies such as Asynchronous JavaScript and XML (Ajax) web-based applications with rich contents are evolving to be more and more like normal applications in aspects, such as interactivity, functionality, and usability. This evolvement makes it possible to create web-based services, providing maps for users to search and browse geographic information. This thesis is an evaluation of functionality, usability and accuracy for the four web-based map APIs: Google Maps, Microsoft Virtual Earth, Multimap and ViaMichelin.</p><p>The thesis explains how web-based mapping works, common functionality provided, and evaluates the functionality provided by each map service provider as well as the offered usability. In addition to this, it also includes the results of several tests, illustrating the APIs’ browser compatibility, performance and accuracy.</p><p>After testing and evaluation of the four APIs, the conclusion is that none of them can be appointed as the winner. They all have benefits and drawbacks; differences in terms of functionality, compatibility, usability, geocoding and development support, and the choice of API is consequently dependent of the type of application. As a result of this, and the fact that the APIs are constantly changing in terms of functionality and coverage, it is important to create applications independent of the map service provider. This was successfully done during the internship at Amadeus by creating a map abstraction layer in-between the applications and the maps, creating the possibility to switch API, or map service provider, without changed the code.</p>

<p>It is often beneficial for an autonomous agent that operates in a complex environment to make use of different types of mathematical models to keep track of unobservable parts of the world or to perform prediction, planning and other types of reasoning. Since a model is always a simplification of something else, there always exists a tradeoff between the model’s accuracy and feasibility when it is used within a certain application due to the limited available computational resources. Currently, this tradeoff is to a large extent balanced by humans for model construction in general and for autonomous agents in particular. This thesis investigates different solutions where such agents are more responsible for balancing the tradeoff for models themselves in the context of interleaved task planning and plan execution. The necessary components for an autonomous agent that performs its abstractions and constructs planning models dynamically during task planning and execution are investigated and a method called DARE is developed that is a template for handling the possible situations that can occur such as the rise of unsuitable abstractions and need for dynamic construction of abstraction levels. Implementations of DARE are presented in two case studies where both a fully and partially observable stochastic domain are used, motivated by research with Unmanned Aircraft Systems. The case studies also demonstrate possible ways to perform dynamic abstraction and problem model construction in practice.</p> / Report code: LiU-Tek-Lic-2008:21.

Ce mémoire propose des représentations formelles pour contrôleurs logiques industriels qui visent à améliorer le passage à l'échelle des techniques de model-checking. Ces vérifications, focalisées sur les propriétés extrinsèques, permettent d'améliorer la sûreté et aident à la certification de ces contrôleurs. Premièrement, la représentation de contrôleurs ne comprend que les états qui sont pertinents pour la preuve de propriétés et minimise le nombre de variables qui caractérisent chaque état. Puis une représentation de chaque bloc fonctionnel, décrit dans un nouveau langage formel adapté à nos besoins, est incluse dans la représentation du contrôleur. Ces représentations permettent la vérification formelle du contrôleur, même avec des programmes de grande taille. La comparaison avec de précédentes représentations, ainsi que leur utilisation dans un contexte industriel, valide nos représentations et quantifie leur efficacité.

Model checking is the most effective means of verifying the correctness of asynchronous designs, and state space exploration is central to model checking. Although model checking can achieve very high verification coverage, the high degree of concurrency in asynchronous designs often leads to state explosion during state space exploration. To inhibit this explosion, our approach builds on the ideas of compositional verification. In our approach, a design modeled in a high level description is partitioned into a set of parallel components. Before state space exploration, each component is paired with an over-approximated environment to decouple it from the rest of the design. Then, a global state transition graph is constructed by reducing and incrementally composing component state transition graphs. We take great care during reduction and composition to preserve all failures found during the initial state space exploration of each component. To further reduce complexity, interface constraints are automatically derived for the over-approximated environment of each component. We prove that our approach is conservative in that false positive results are never produced. The effectiveness of our approach is demonstrated by the experimental results of several case studies showing that our approach can verify designs that cannot be handled by traditional at approaches. The experiments also show that constraints can reduce the size of the global state transition graph and prevent some false failures.