Narrow Results

The polyhedral model for loop parallelization has proved to be an effective tool for advanced optimization and automatic parallelization of programs in higher-level languages. Yet, to integrate such optimizations seamlessly into production compilers, they must be performed on the compiler's internal, low-level, intermediate representation (IR). With Polly, we present an infrastructure for polyhedral optimizations on such an IR. We describe the detection of program parts amenable to a polyhedral optimization (so-called static control parts), their translation to a Z-polyhedral representation, optimizations on this representation and the generation of optimized IR code. Furthermore, we define an interface for connecting external optimizers and present a novel way of using the parallelism they introduce to generate SIMD and OpenMP code. To evaluate Polly, we compile the PolyBench 2.0 benchmarks fully automatically with PLuTo as external optimizer and parallelizer. We can report on significant speedups.

Iterative stencil computations are important in scientific computing and more also in the embedded and mobile domain. Recent publications have shown that tiling schemes that ensure concurrent start provide efficient ways to execute these kernels. Diamond tiling and hybrid-hexagonal tiling are two tiling schemes that enable concurrent start. Both have different advantages: diamond tiling has been integrated in a general purpose optimization framework and uses a cost function to choose among tiling hyperplanes, whereas the greater flexibility with tile sizes for hybrid-hexagonal tiling has been exploited for effective generation of GPU code.

In this paper we undertake a comparative study of these two tiling approaches and propose a hybrid approach that combines them. We analyze the effects of tile size and wavefront choices on tile-level parallelism, and formulate constraints for optimal diamond tile shapes. We then extend, for the case of two dimensions, the diamond tiling formulation into a hexagonal tiling one, which offers both the flexibility of hexagonal tiling and the generality of the original diamond tiling implementation. We also show how to compute tile sizes that maximize the compute-to-communication ratio, and apply this result to compare the best achievable ratio and the associated synchronization overhead for diamond and hexagonal tiling.

The Siromoney matrix model is a simple and elegant model for describing two-dimensional digital picture languages. The notion of attaching indices to nonterminals in a generative grammar, introduced and investigated by Aho. is considered in the vertical phase of a Siromoney matrix grammar (SMG). The advantage of this study is that the new model retains the simplicity and elegance of SMG but increases the generative power and enables us to describe pictures not generable by SMG. Besides certain closure properties and hierarchy results. applications of these two-dimensional grammars to describe tilings, polyominoes, distorted patterns and parquet deformations are studied.

One-dimensional cellular automata are known to be able to present complex behaviors. In some cases, their evolution may be understood as movings, collisions, or creations of particles. In the case of the special Wolfram's rule 54, Boccara has previously pointed out basic particles. In this paper, we introduce a group which allows the formal study of interactions between these particles. Coming back to the complexity of rule 54 and using the new algebraic classification of Rapaport, we prove that rule 54 is not simple.

This paper is a follow-up Irigoin and Triolet's earlier work and our recent work on tiling. In this paper, tiling is discussed in terms of its effects on the dependences between tiles, the dependences within a tile and the required dependence test for legality. A necessary and sufficient condition is given for enforcing the data dependences of the program, while Irigion and Triolet's atomic tile constraint is only sufficient. A condition is identified under which both Irigoin and Triolet's and our constraints are equivalent. The results of this paper are discussed in terms of their impact on dependence abstractions suitable for legality test and on tiling to optimise a certain given goal.

The emptiness problem for non-overlapping Basic puzzle grammars is shown to be decidable. An alternate proof of the decidability of the non-overlapping feature for basic puzzle grammars is given. Hierarchy among the various classes of puzzle languages is also established.

Interpolating a piecewise-linear triangulated surface between two polygons lying in parallel planes has attracted a lot of attention in the literature over the past three decades. This problem is the simplest variant of interpolation between parallel slices, which may contain multiple polygons with unrestricted geometries and/or topologies. Its solution has important applications to medical imaging, digitization of objects, geographical information systems, and more. Practically all currently-known methods for surface reconstruction from parallel slices assume a priori the existence of a non-self-intersecting triangulated surface defined over the vertices of the two polygons, which connects them. Gitlin et al. were the first to specify a nonmatable pair of polygons. In this paper we provide proof of the nonmatability of a “simpler” pair of polygons, which is less complex than the example given by Gitlin et al. Furthermore, we provide a family of polygon pairs with unbounded complexity, which we believe to be nonmatable. We also give a few sufficient conditions for polygon matability.

A set of natural numbers tiles the plane if a square-tiling of the plane exists using exactly one square of sidelength n for every n in the set. From Ref. 8 we know that ℕ itself tiles the plane. From that and Ref. 9 we know that the set of even numbers tiles the plane while the set of odd numbers doesn't. In this paper we explore the nature of this property. We show, for example, that neither tiling nor non-tiling is preserved by superset. We show that a set with one or three odd numbers may tile the plane—but a set with two odd numbers can't.

We find examples of both tiling and non-tiling sets that can be partitioned into tiling sets, non-tiling sets or a combination. We show that any set growing faster than the Fibonacci numbers cannot tile the plane.

There exists a linear algorithm to decide whether a polyomino tessellates the plane by translation only. On the other hand, the problem of deciding whether a set of $11$ or more polyominoes can tile the plane by translation is undecidable. We narrow the gap between decidable and undecidable by showing that it remains undecidable for a set of $10$ polyominoes, which partially solves a conjecture posed by Ollinger.

Not much is known about the topological structure of a connected self-similar tile whose interior is disconnected, and even less is understood if the interior consists of infinitely many components. We introduce a technique to show that for a large class of self-similar tiles in ℝ², the closure of each component of the interior is homeomorphic to a disk. This allows us to prove such a result for the Eisenstein set, the fundamental domain of a well-known quadratic canonical number system, and some other well-known fractal tiles.

In this paper, we present an idea of creating fractals by using the geometric arc as the basic element. This approach of generating fractals, through the tuning of just three parameters, gives a universal way to obtain many novel fractals including the classic ones. Although this arc-fractal system shares similar features with the well-known Lindenmayer system, such as the same set of invariant points and the ability to tile the space, they do have different properties. One of which is the generation of pseudo-random number, which is not available in the Lindenmayer system. Furthermore, by assuming that coastline formation is based purely on the processes of erosion and deposition, the arc-fractal system can also serve as a dynamical model of coastal morphology, with each level of its construction corresponds to the time evolution of the shape of the coastal features. Remarkably, our results indicate that the arc-fractal system can provide an explanation on the origin of fractality in real coastline.

The object under study is a particular closed and simple curve on the square lattice ℤ² related with the Fibonacci sequence F_n. It belongs to a class of curves whose length is 4F_3n+1, and whose interiors tile the plane by translation. The limit object, when conveniently normalized, is a fractal line for which we compute first the fractal dimension, and then give a complexity measure.

A fractal tiling is a tiling which possesses self-similarity and the boundary of which is a fractal. In this paper, we investigate the boundary dimension of $s_n$- and $u_n$-tilings. We first derive an explicit recursion formula for the boundary edges of $s_n$- and $u_n$-tilings. Then we present an analytical expression for their fractal boundary dimensions using matrix methods. Results indicate that, as $n$ increases, the boundaries of $s_n$- and $u_n$-tilings will degenerate into general Euclidean curves. The method proposed in this paper can be extended to compute the boundary dimensions of other kinds of fractal tilings.

A fractal tiling or $f$-tiling is a tiling which possesses self-similarity and the boundary of which is a fractal. By substitution rule of tilings, this short paper presents a very simple strategy to create a great number of $f$-tilings. The substitution tiling Equithirds is demonstrated to show how to achieve it in detail. The method can be generalized to every tiling that can be constructed by substitution rule.

The emptiness problem for non-overlapping Basic puzzle grammars is shown to be decidable. An alternate proof of the decidability of the non-overlapping feature for basic puzzle grammars is given. Hierarchy among the various classes of puzzle languages is also established.

The Siromoney matrix model is a simple and elegant model for describing two-dimensional digital picture languages. The notion of attaching indices to nonterminals in a generative grammar, introduced and investigated by Aho, is considered in the vertical phase of a Siromoney matrix grammar (SMG). The advantage of this study is that the new model retains the simplicity and elegance of SMG but increases the generative power and enables us to describe pictures not generable by SMG. Besides certain closure properties and hierarchy results, applications of these two-dimensional grammars to describe tilings, polyominoes, distorted patterns and parquet deformations are studied.