No description available.

The natural capacity of DNA for molecular self-assembly has already been exploited to create DNA based tiles which can self-assemble into nano-scale arrays and carry out nano-scale computation. Thus far, however, all such self-assembly has been passive, in the sense that the binding capacities of a tile are never altered throughout the assembly. The idea of active tiles, tiles that can send signals to each other and activate latent binding sites, has been proposed but never incorporated into a formal model. Here, I present an extension of the existent abstract tile assembly model by defining an active tile assembly and give a detailed example of an aperiodic set of active tiles which hierarchically produces a self-similar L-shape tiling. This yields a technique utilizing active tiles for the assembly of aperiodic self-similar shapes.

Malgré des décennies de recherche sur l’optimisation de boucle auxhaut niveau et leur intégration réussie dans les compilateurs C/C++et FORTRAN, la plupart des systèmes de transformation de bouclene traitent que partiellement les défis posé par la complexité croissanteet la diversité du matériel d’aujourd’hui. L’exploitation de laconnaissance dédiée a un domaine d’application pour obtenir le codeoptimal pour cibles complexes, tels que des accélérateurs ou des microprocessorsmulti-coeur, pose des problèmes pour les formalismeset outils d’optimisation de boucle existants. En conséquence, de nouveauxschémas d’optimisation qui exploitent la connaissance dédiéea un domaine sont développées indépendamment sans profiter dela technologie d’optimisation de boucle existante. Cela conduit à despossiblités d’optimisation raté et ainsi qu’à une faible portabilité deces schémas d’optimisation entre des compilateurs différents. Un domainepour lequel on voit la nécessité d’améliorer les optimisationsest le calcul de pochoir itératifs, un probléme de calcul important quiest réguliérement optimisé par les compilateurs dédiées, mais pourlequel générer code efficace est difficile.Dans ce travail, nous présentons des nouvelles stratégies pour l’optimisationdédiée qui permettent la génération de code GPU haute performancepour des calculs de pochoir. À la différence de la façon dontla plupart des compilateurs existants sont mis en oeuvre, nous découplonsla stratégie d’optimisation de haut niveau de l’optimisationde bas niveau et la spécialisation nécessaire pour obtenir la performanceoptimale. Comme schéma d’optimisation de haut niveau, nousprésentons une nouvelle formulation de “split tiling”, une techniquequi permet la réutilisation de données dans la dimension du tempsainsi que le parallélisme équilibré à gros grain sans la nécessité derecourir à des calculs redondants. Avec le “split tiling”, nous montronscomment intégrer une optimisation dédiée dans un traducteurgénérique source-à-source, C vers CUDA, une approche qui nouspermet de réutiliser des optimisations existants non-dédiées. Nousprésentons ensuite notre technique appelée “hybrid hexagonal / parallelogramtiling", un schéma qui nous permet de générer du codeque cible directement les préoccupations spécifiques aux GPUs. Pourconclure notre travail sur le "loop tiling", nous étudions la rapport entre“diamond tiling” et “hexagonal tiling”. À partir d’une analyse de“diamond tiling” détailée, qui comprend les exigences qu’elle posesur la taille de tuile et les coefficients de front d’onde, nous fournissonsune formulation unifiée de l’“hexagonal tiling” et du “diamondtiling” qui nous permet de réaliser un “hexagonal tiling” pourvdes problèmes avec deux dimensions (un temps, un espace) dans lecadre d’un usage dans un optimiseur générique, comme “Pluto”. Enfin,nous utilisons cette formulation pour évaluer l’“hexagonal tiling”et le “diamond tiling” en terme de rapport de calcul-à-communicationet calcul-à-synchronisation.Dans la deuxième partie de ce travail, nous discutons nos contributionsaux composants de l’infrastructure les plus important, nos“building blocks”, qui nous permettent de découpler notre optimisationde haut niveau tant des optimisations nécessaires dàns la générationde code que de l’infrastructure de compilation générique. Nouscommençons par présenter le nouveau “polyhedral extractor” (pet),qui obtient une représentation polyédrique d’un morceau de code C.pet utilise l’arithmétique de Presburger en sa généralité pour élargirle fragment de code C supporté et porter une attention particulièreà la modélisation de la sémantique des langages même en présencede dépassement de capacité des entiers. / Despite decades of research on high-level loop optimizations and theirsuccessful integration in production C/C++/FORTRAN com- pilers, most compilerinternal loop transformation systems only partially address the challengesposed by the increased complexity and diversity of today’s hardware. Especiallywhen exploiting domain specific knowledge to obtain optimal code for complextargets such as accelerators or many-cores processors, many existing loopoptimization frameworks have difficulties exploiting this hardware. As aresult, new domain specific optimization schemes are developed independentlywithout taking advantage of existing loop optimization technology. This resultsboth in missed optimization opportunities as well as low portability of theseoptimization schemes to different compilers. One area where we see the need forbetter optimizations are iterative stencil computations, an importantcomputational problem that is regularly optimized by specialized, domainspecific compilers, but where generating efficient code is difficult.In this work we present new domain specific optimization strategies that enablethe generation of high-performance GPU code for stencil computations. Differentto how most existing domain specific compilers are implemented, we decouple thehigh-level optimization strategy from the low-level optimization andspecialization necessary to yield optimal performance. As high-leveloptimization scheme we present a new formulation of split tiling, a tilingtechnique that ensures reuse along the time dimension as well as balancedcoarse grained parallelism without the need for redundant computations. Usingsplit tiling we show how to integrate a domain specific optimization into ageneral purpose C-to-CUDA translator, an approach that allows us to reuseexisting non-domain specific optimizations. We then evolve split tiling into ahybrid hexagonal/parallelogram tiling scheme that allows us to generate codethat even better addresses GPU specific concerns. To conclude our work ontiling schemes we investigate the relation between diamond and hexagonaltiling. Starting with a detailed analysis of diamond tiling including therequirements it poses on tile sizes and wavefront coefficients, we provide aunified formulation of hexagonal and diamond tiling which enables us to performhexagonal tiling for two dimensional problems (one time, one space) in thecontext of a general purpose optimizer such as Pluto. Finally, we use thisformulation to evaluate hexagonal and diamond tiling in terms ofcompute-to-communication and compute-to-synchronization ratios.In the second part of this work, we discuss our contributions to importantinfrastructure components, our building blocks, that enviable us to decoupleour high-level optimizations from both the necessary code generationoptimizations as well as the compiler infrastructure we apply the optimizationto. We start with presenting a new polyhedral extractor that obtains apolyhedral representation from a piece of C code, widening the supported C codeto exploit the full generality of Presburger arithmetic and taking special careof modeling language semantics even in the presence of defined integerwrapping. As a next step, we present a new polyhedral AST generation approach,which extends AST generation beyond classical control flow generation byallowing the generation of user provided mappings. Providing a fine-grainedoption mechanism, we give the user fine grained control about AST generatordecisions and add extensive support for specialization e.g., with a newgeneralized form of polyhedral unrolling. To facilitate the implementation ofpolyhedral transformations, we present a new schedule representation, scheduletrees, which proposes to make the inherent tree structure of schedules explicitto simplify the work with complex polyhedral schedules.The last part of this work takes a look at our contributions to low-levelcompilers.

No description available.

A Cuntz-Pimsner algebra is a quotient of a generalized Toeplitz algebra. It is completely determined by a C*-correspondence, which consists of a right Hilbert A- module, E, and a *-homomorphism from the C*-algebra A into L(E), the adjointable operators on E. Some familiar examples of C*-algebras which can be recognized as Cuntz-Pimsner algebras include the Cuntz algebras, Cuntz-Krieger algebras, and crossed products of a C*-algebra by an action of the integers by automorphisms. In this dissertation, we construct a Cuntz-Pimsner Algebra associated to a dynam- ical system of a substitution tiling, which provides an alternate construction to the groupoid approach found in [3], and has the advantage of yielding a method for com- puting the K-Theory. / Graduate

Etant donnée une substitution de dimension 1, notée $\sigma$, nous pouvons définir l'enveloppe $\Omega_\sigma$ formant un système dynamique $(\Omega_\sigma, \R)$ où l'action de $\R$ sur les pavages est donnée par les translations. Si la substitution est primitive alors nous pouvons construire un pavage $P$ du demi-plan de Poincaré $\mathbb H_2 $ muni de sa métrique $\frac{\mathrm d x + \mathrm d y}{y^2}$. De manière analogue nous pouvons construire des enveloppes pour les actions de $N= \{ \mathbb{H}_2 \to \mathbb{H}_2, z \mapsto z +t, t\in \R\}$ et $G = \{ \mathbb{H}_2 \to \mathbb{H}_2, z \mapsto a z +b,(a,b) \in \R_+ ^* \times \R\}$ que l'on notera respectivement $X_P ^N$ et $X_{P(c)}^G$ (où $P(c)$ est le pavage colorié ligne à ligne pour rendre l'action de $G$ libre).\par En utilisant la notion de $C^* $-algèbre de groupoïde ainsi que les résultats obtenus dans l'article de Ian Putnam et Jared Anderson et via l'isomorphisme issu de l'équivalence Morita entre $C((\Xi \times \R)/\As)$ et $C(\Xi) \rtimes \Z$, nous pouvons donner la description de la $C^*$-algèbre de l'enveloppe du pavage hyperbolique en termes de générateurs et relations. Nous terminons par la description des générateurs de la $K$-théorie de $C(X_{P(c)}^G) \rtimes G.$ pour les substitutions de Fibonacci, Thue-Morse et Tribonacci / Given a one dimensional substitution $\sigma$, one can define the continuous hull $\Omega_\sigma$ for the $\R$-action given by translations and so we obtain a dynamical system $(\Omega_\sigma,\sigma)$. If the substitution we choose is primitive, then we can construct an hyperbolic tiling on Poincaré's half-plane equiped with its standard metric $\frac{\mathrm d x +\mathrm d y}{y^2}$. By analogy of the standard case, we can define two continuous hulls, denoted $X_P ^ N $ and $X_{P(c)}^G$, where $P(c)$ is a colored tiling (in such fashion that the action of $G$ is free), and the groups are denoted respectively $N= \{ \mathbb{H}_2 \to \mathbb{H}_2, z \mapsto z +t, t\in \R\}$ and $G = \{ \mathbb{H}_2 \to \mathbb{H}_2, z \mapsto a z +b,(a,b) \in \R_+ ^* \times \R\}$.\par Using Jean Renault's construction of the reduced $C^*$-algebra of a groupoid , the results of Ian Putnam and Jared Anderson and the Morita equivalence between $C((\Xi\times \R)/\As)$ and $C(\Xi) \rtimes \Z$, we describe the $C^*$-algebra of the hyperbolic tiling using generators and relations. Finally we obtain for the Fibonacci, Thue-Morse and Tribonacci substitutions the full description of the generators of $K_* (C(X_{P(c)}^G ) \rtimes G)$

abstract: Extremal graph theory results often provide minimum degree conditions which guarantee a copy of one graph exists within another. A perfect $F$-tiling of a graph $G$ is a collection $\mathcal{F}$ of subgraphs of $G$ such that every element of $\mathcal{F}$ is isomorphic to $F$ and such that every vertex in $G$ is in exactly one element of $\mathcal{F}$. Let $C^{3}_{t}$ denote the loose cycle on $t = 2s$ vertices, the $3$-uniform hypergraph obtained by replacing the edges $e = \{u, v\}$ of a graph cycle $C$ on $s$ vertices with edge triples $\{u, x_e, v\}$, where $x_e$ is uniquely assigned to $e$. This dissertation proves for even $t \geq 6$, that any sufficiently large $3$-uniform hypergraph $H$ on $n \in t \mathbb{Z}$ vertices with minimum $1$-degree $\delta^1(H) \geq {n - 1 \choose 2} - {\Bsize \choose 2} + c(t,n) + 1$, where $c(t,n) \in \{0, 1, 3\}$, contains a perfect $C^{3}_{t}$-tiling. The result is tight, generalizing previous results on $C^3_4$ by Han and Zhao. For an edge colored graph $G$, let the minimum color degree $\delta^c(G)$ be the minimum number of distinctly colored edges incident to a vertex. Call $G$ rainbow if every edge has a unique color. For $\ell \geq 5$, this dissertation proves that any sufficiently large edge colored graph $G$ on $n$ vertices with $\delta^c(G) \geq \frac{n + 1}{2}$ contains a rainbow cycle on $\ell$ vertices. The result is tight for odd $\ell$ and extends previous results for $\ell = 3$. In addition, for even $\ell \geq 4$, this dissertation proves that any sufficiently large edge colored graph $G$ on $n$ vertices with $\delta^c(G) \geq \frac{n + c(\ell)}{3}$, where $c(\ell) \in \{5, 7\}$, contains a rainbow cycle on $\ell$ vertices. The result is tight when $6 \nmid \ell$. As a related result, this dissertation proves for all $\ell \geq 4$, that any sufficiently large oriented graph $D$ on $n$ vertices with $\delta^+(D) \geq \frac{n + 1}{3}$ contains a directed cycle on $\ell$ vertices. This partially generalizes a result by Kelly, K\"uhn, and Osthus that uses minimum semidegree rather than minimum out degree. / Dissertation/Thesis / Doctoral Dissertation Mathematics 2019

Minimum Cost Polygon Overlay (MCPO) is a unique two-dimensional optimization problem that involves the task of covering a polygon shaped area with a series of rectangular shaped panels. The challenges in solving MCPO problems are related to the interdependencies that exist among the parameters and constraints that may be applied to the solution.This thesis examines the MCPO problem to construct a model that captures essential parameters to be solved using optimization algorithms. The purpose of the model is to make it possible that a solution for an MCPO problem can be generated automatically. A software application has been developed to provide a framework for validating the model.The development of the software has uncovered a host of geometric operations that are required to enable optimization to take place. Many of these operations are non-trivial, demanding novel, well-constructed algorithms based on careful appreciation of the nature of the problem.For the actual optimization task, three algorithms have been implemented: a greedy search, a Monte Carlo method, and a Genetic Algorithm. The behavior of the completed software is observed through its application on a series of test data. The results are presented to show the effectiveness of the software under various settings. This is followed by critical analysis of various findings of the research.Conclusions are drawn to summarize lessons learned from the research. Important issues about which no satisfactory explanation exists are given as material to be studied by future research.

We consider tiling problems for graphs and hypergraphs. For two graphs and , an -tiling of is a subgraph of consisting of only vertex disjoint copies of . By using the absorbing method, we give a short proof that in a balanced tripartite graph , if every vertex is adjacent to of the vertices in each of the other vertex partitions, then has a -tiling. Previously, Magyar and Martin [11] proved the same result (without ) by using the Regularity Lemma. In a 3-uniform hypergraph , let denote the minimum number of edges that contain for all pairs of vertices. We show that if , there exists a -tiling that misses at most vertices of . On the other hand, we show that there exist hypergraphs such that and does not have a perfect -tiling. These extend the results of Pikhurko [12] on -tilings.

C*-algebras from tilings are of particular interest. In 1998 J. Anderson and I. Putnam introduced a C*-algebra obtained from a substitution tiling that is viewed today as a standard invariant for this tilings. In this thesis we introduce another C*-algebra associated to a substitution tiling. We expect this C*-algebra to be in some sense a dual C*-algebra to the one introduced by Anderson and Putnam. but we were not able to make a precise statement. In our effort to characterize this new C*-algebras we prove that they are simple and can be constructed as an inductive limit of recursive subhomogenous algebras. We finish with K-theory computations for a number of examples.