No description available.

No description available.

No description available.

In computations over many-sorted algebras, one typically encounters error cases, caused by attempting to evaluate an operation outside its domain (e.g. division by the integer 0; taking the square root of a negative integer; popping an empty stack). We present a method for systematically dealing with such error cases, namely the construction of an "error algebra" based on the original algebra. As an application of this method, we show that it provides a good semantics for (possibly improper) function tables. / Thesis / Master of Science (MSc)

Given two sets of points $A$ and $B$ ($|A| = m$, $|B| = n$), we seek to find a minimum-weight many-to-many matching which seeks to match each point in $A$ to at least one point in $B$ and vice versa. Each matched pair (an edge) has a weight. The goal is to find the matching that minimizes the total weight. We study two kinds of problems depending on the edge weight used. The first edge weight is the Euclidean distance, $d_1$. The second is edge weight is the square of the Euclidean distance, $d_2$. There already exists an $O(k\log k)$ algorithm for $d_1$, where $k=m+n$. We provide an $O(mn)$ algorithm for the $d_2$ problem. We also solve the problem of finding the minimum-weight matching when the sets $A$ and $B$ are allowed to be translated on the real line. We present an $O(mnk \log k)$ algorithm for the $d_1$ problem and an $O(3^{mn})$ algorithm for the $d_2$. Furthermore, we also deal with the special case where $A$ and $B$ lie on a circle of a specific circumference. We present an $O(k^2 \log k)$ algorithm and $O(kmn)$ algorithm for solving the minimum-weight matching for the $d_1$, and $d_2$ weights respectively. Much like the problem on the real line, we extend this problem to allow the sets $A$ and $B$ to be rotated on the circle. We try to find the minimum-weight many-to-many matching when rotations are allowed. For $d_1$ we present an $O(k^2mn \log k)$ algorithm and a $O(3^{mn})$ algorithm for $d_2$. / Thesis (Master, Computing) -- Queen's University, 2010-11-08 20:48:18.968

Doctor of Philosophy / Department of Mathematics / Alexander G. Ramm / In this thesis, the author presents several numerical methods for solving scalar and electromagnetic wave scattering problems. These methods are taken from the papers of Professor Alexander Ramm and the author, see [1] and [2]. In Chapter 1, scalar wave scattering by many small particles of arbitrary shapes with impedance boundary condition is studied. The problem is solved asymptotically and numerically under the assumptions a << d << λ, where k = 2π/λ is the wave number, λ is the wave length, a is the characteristic size of the particles, and d is the smallest distance between neighboring particles. A fast algorithm for solving this wave scattering problem by billions of particles is presented. The algorithm comprises the derivation of the (ORI) linear system and makes use of Conjugate Orthogonal Conjugate Gradient method and Fast Fourier Transform. Numerical solutions of the scalar wave scattering problem with 1, 4, 7, and 10 billions of small impedance particles are achieved for the first time. In these numerical examples, the problem of creating a material with negative refraction coefficient is also described and a recipe for creating materials with a desired refraction coefficient is tested. In Chapter 2, electromagnetic (EM) wave scattering problem by one and many small perfectly conducting bodies is studied. A numerical method for solving this problem is presented. For the case of one body, the problem is solved for a body of arbitrary shape, using the corresponding boundary integral equation. For the case of many bodies, the problem is solved asymptotically under the physical assumptions a << d << λ, where a is the characteristic size of the bodies, d is the minimal distance between neighboring bodies, λ = 2π/k is the wave length and k is the wave number. Numerical results for the cases of one and many small bodies are presented. Error analysis for the numerical method are also provided.

Training structures have been defined as the order and arrangement of baseline conditional discriminations within stimulus equivalence training. The three training structures most often used are, linear (trains A:B and B:C discrimination), many-to-one (trains B:A and C:A discriminations) , and one-to-many (trains A:B and A:C discriminations). Each training structure trains a different set of simultaneous and successive discriminations that are then needed in the test for derived relations (symmetry, reflexivity, transitivity, and symmetrical transitivity). The present experiment seeks to extend the research on stimulus equivalence training structures by using a within-subject design and adult human subjects. Three sets of 9 arbitrary stimuli were trained concurrently each with a different training structure. From the beginning, training and testing trials were intermixed. The likelihood of producing stimulus equivalence formation was equal across structures.

Il y a un intérêt croissant pour le développement d'applications sur les plates-formes multiprocesseurs homo- et hétérogènes en raison de l'extension de leur champ d'application et de l'apparition des puces many-core, telles que Kalray MPPA-256 (256 cœurs) ou TEGRA X1 de NVIDIA (256 GPU et 8 cœurs 64 bits CPU). Étant donné l'ampleur de ces nouveaux systèmes massivement parallèles, la mise en œuvre des applications sur ces plates-formes est difficile à cause de leur complexité, qui tend à augmenter, et de leurs exigences strictes à la fois qualitatives (robustesse, fiabilité) et quantitatives (débit, consommation d’énergie). Dans ce contexte, les Modèles de Calcul (MdC) flot de données ont été développés pour faciliter la conception de ces applications. Ces MdC sont par définition composées de filtres qui échangent des flux de données via des liens de communication. Ces modèles fournissent une représentation intuitive des applications flot de données, tout en exposant le parallélisme de tâches de l’application. En outre, ils fournissent des capacités d'analyse statique pour la vivacité et l’exécution en mémoire bornée. Cependant, de nouvelles applications de signalisation et de traitement des médias complexes présentent souvent plusieurs défis majeurs qui ne correspondent pas aux restrictions des modèles flot de données statiques classiques: 1) Comment fournir des services garantis contre des interférences inévitables qui peuvent affecter des performances temps réel ?, et 2) Comment ces langages flot de données qui sont souvent trop statiques pourraient répondre aux besoins des applications embarquées émergentes, qui nécessitent une exécution plus dynamique et plus dépendante du contexte ? Pour faire face au premier défi, nous proposons un ordonnancement hybride, nommé Self-Timed Periodic (STP), qui relie des MdC flot de données classiques et des modèles de tâches temps réel. Cet ordonnancement peut aussi être considéré comme un modèle d'exécution combinant l'ordonnancement classique dirigé seulement par les contraintes de dépendance d'exécution appelé Self-Timed Scheduling (STS), évalué comme le plus approprié pour des applications modélisées sous forme de graphes flot de données, avec l'ordonnancement périodique: STS améliore les indicateurs de performance des programmes, tandis que le modèle périodique capture les aspects de synchronisation. Nous avons évalué la performance de notre ordonnancement sur un ensemble de 10 applications et nous avons constaté que dans la plupart des cas, notre approche donne une amélioration significative de la latence par rapport à un ordonnancement purement périodique ou Strictly Periodic Scheduling (SPS), et rivalise bien avec STS. Les expériences montrent également que, pour presque tous les cas de test, STP donne un débit optimal. Sur la base de ces résultats, nous avons évalué la latence entre le temps d'initiation de tous les deux acteurs dépendants, et nous avons introduit une approche basée sur la latence pour le traitement des flux à tolérance de pannes modélisée comme un graphe Cyclo-Static Dataflow (CSDF), dans le but d'aborder des problèmes de défaillance de nœud ou de réseau… / There is an increasing interest in developing applications on homo- and heterogeneous multiprocessor platforms due to their broad availability and the appearance of many-core chips, such as the MPPA-256 chip from Kalray (256 cores) or TEGRA X1 from NVIDIA (256 GPU and 8 64-bit CPU cores). Given the scale of these new massively parallel systems, programming languages based on the dataflow model of computation have strong assets in the race for productivity and scalability, meeting the requirements in terms of parallelism, functional determinism, temporal and spatial data reuse in these systems. However, new complex signal and media processing applications often display several major challenges that do not fit the classical static restrictions: 1) How to provide guaranteed services against unavoidable interferences which can affect real-time performance?, and 2) How these streaming languages which are often too static could meet the needs of emerging embedded applications, such as context- and data-dependent dynamic adaptation? To tackle the first challenge, we propose and evaluate an analytical scheduling framework that bridges classical dataflow MoCs and real-time task models. In this framework, we introduce a new scheduling policy noted Self-Timed Periodic (STP), which is an execution model combining Self-Timed scheduling (STS), considered as the most appropriate for streaming applications modeled as data-flow graphs, with periodic scheduling: STS improves the performance metrics of the programs, while the periodic model captures the timing aspects. We evaluate the performance of our scheduling policy for a set of 10 real-life streaming applications and find that in most of the cases, our approach gives a significant improvement in latency compared to the Strictly Periodic Schedule (SPS), and competes well with STS. The experiments also show that, for more than 90% of the benchmarks, STP scheduling results in optimal throughput. Based on these results, we evaluate the latency between initiation times of any two dependent actors, and we introduce a latency-based approach for fault-tolerant stream processing modeled as a Cyclo-Static Dataflow (CSDF) graph, addressing the problem of node or network failures. For the second challenge, we introduce a new dynamic Model of Computation (MoC), called Transaction Parameterized Dataflow (TPDF), extending CSDF with parametric rates and a new type of control actor, channel and port to express dynamic changes of the graph topology and time-triggered semantics. TPDF is designed to be statically analyzable regarding the essential deadlock and boundedness properties, while avoiding the aforementioned restrictions of decidable dataflow models. Moreover, we demonstrate that TPDF can be used to accurately model task timing requirements in a great variety of situations and introduce a static scheduling heuristic to map TPDF to massively parallel embedded platforms. We validate the model and associated methods using a set of realistic applications and random graphs, demonstrating significant buffer size and performance improvements (e.g., throughput) compared to state of the art models including Cyclo-Static Dataflow (CSDF) and Scenario-Aware Dataflow (SADF).

Based on the works [R1] - [R10], this thesis tackles various aspects of the dynamics of interacting quantum many-body systems. Particular emphasis is given to the understanding of transport and thermalization phenomena in isolated (quasi) one-dimensional quantum spin models. Employing a variety of methods, these phenomena are studied both, close to equilibrium where linear response theory (LRT) is valid, as well as in far-from-equilibrium situations where LRT is supposed to break down. The main results of this thesis can be summarized as follows. First, it is shown that conventional hydrodynamic transport, i.e., diffusion, occurs in a number of (integrable and nonintegrable) quantum models and can be detected by looking at different signatures in position and momentum space as well as in the time and the frequency domain. Furthermore, the out-of-equilibrium dynamics resulting from a realistic class of initial states is explored. These states are thermal states of the model in the presence of an additional static force, but become nonequilibrium states when this force is eventually removed. Remarkably, it is shown that in some cases, the full time-dependent relaxation process can become independent of whether the initial state is prepared close to or far away from equilibrium. In this context, a new connection between the eigenstate thermalization hypothesis and linear response theory is unveiled. Finally, this thesis also reports progress on the development and improvement of numerical and (semi-)analytical techniques to access the dynamics of quantum many-body systems. Specifically, a novel combination of dynamical quantum typicality and numerical linked cluster expansions is employed to study current-current correlation functions in chain and ladder geometries in the thermodynamic limit.

La multiplication du nombre de cœurs de calcul présents sur une même puce va depair avec une augmentation des besoins en communication. De plus, la variété des applications s’exécutant sur la puce provoque une hétérogénéité spatiale et temporelle des communications. C’est pour répondre à ces problématiques que nous pré-sentons dans ce manuscrit un réseau d’interconnexion sur puce dynamiquement reconfigurable utilisant la Radio Fréquence (RF). L’utilisation de la RF permet de disposer d’une bande passante plus importante tout en minimisant la latence. La possibilité de reconfigurer dynamiquement le réseau permet d’adapter cette puce many-cœur à la variabilité des applications et des communications. Nous présentons les raisons du choix de la RF par rapport aux autres nouvelles technologies du domaine que sont l’optique et la 3D, l’architecture détaillée de ce réseau et d’une puce le mettant en œuvre ainsi que l’évaluation de sa faisabilité et de ses performances. Durant la phase d’évaluation nous avons pu montrer que pour un Chip Multiprocessor (CMP) de 1 024 tuiles, notre solution permettait un gain en performance de 13 %. Un des avantages de ce réseau d’interconnexion RF est la possibilité de faire du broadcast sans surcoût par rapport aux communications point-à-point,ouvrant ainsi de nouvelles perspectives en termes de gestion de la cohérence mémoire notamment. / The growing number of cores in a single chip goes along with an increase in com-munications. The variety of applications running on the chip causes spatial andtemporal heterogeneity of communications. To address these issues, we presentin this thesis a dynamically reconfigurable interconnect based on Radio Frequency(RF) for intra chip communications. The use of RF allows to increase the bandwidthwhile minimizing the latency. Dynamic reconfiguration of the interconnect allowsto handle the heterogeneity of communications. We present the rationale for choos-ing RF over optics and 3D, the detailed architecture of the network and the chipimplementing it, the evaluation of its feasibility and its performances. During theevaluation phase we were able to show that for a CMP of 1 024 tiles, our solutionallowed a performance gain of 13 %. One advantage of this RF interconnect is theability to broadcast without additional cost compared to point-to-point communi-cations, opening new perspectives in terms of cache coherence.