On tiling under tomographic constraints

Given a tiling of a 2D grid with several types of tiles, we can count for every row and column how many tiles of each type it intersects. These numbers are called the projections. We are interested in the problem of reconstructing a tiling which has given projections. Some simple variants of this problem, involving tiles that are 1×1 or 1×2 rectangles, have been studied in the past, and were proved to be either solvable in polynomial time or -complete. In this note, we make progress toward a comprehensive classification of various tiling reconstruction problems, by proving -completeness results for several sets of tiles.     

Stratified Markov Chain Monte Carlo Light Transport

Markov chain Monte Carlo (MCMC) sampling is a powerful approach to generate samples from an arbitrary distribution. The application to light transport simulation allows us to efficiently handle complex light transport such as highly occluded scenes. Since light transport paths in MCMC methods are sampled according to the path contributions over the sampling domain covering the whole image, bright pixels receive more samples than dark pixels to represent differences in the brightness. This variation in the number of samples per pixel is a fundamental property of MCMC methods. This property often leads to uneven convergence over the image, which is a notorious and fundamental issue of any MCMC method to date. We present a novel stratification method of MCMC light transport methods. Our stratification method, for the first time, breaks the fundamental limitation that the number of samples per pixel is uncontrollable. Our method guarantees that every pixel receives a specified number of samples by running a single Markov chain per pixel. We rely on the fact that different MCMC processes should converge to the same result when the sampling domain and the integrand are the same. We thus subdivide an image into multiple overlapping tiles associated with each pixel, run an independent MCMC process in each of them, and then align all of the tiles such that overlapping regions match. This can be formulated as an optimization problem similar to the reconstruction step for gradient-domain rendering. Further, our method can exploit the coherency of integrands among neighboring pixels via coherent Markov chains and replica exchange. Images rendered with our method exhibit much more predictable convergence compared to existing MCMC methods.     

Activatable tiles for compact robust programmable molecular assembly and other applications

Algorithmic DNA self-assembly is capable of forming complex patterns and shapes, that have been shown theoretically, and experimentally. Its experimental demonstrations, although improving over recent years, have been limited by significant assembly errors. Since 2003 there have been several designs of error-resilient tile sets but all of these existing error-resilient tile systems assumed directional growth of the tiling assembly. This is a very strong assumption because experiments show that tile self-assembly does not necessarily behave in such a fashion, since they may also grow in the reverse of the intended direction. The assumption of directional growth of the tiling assembly also underlies the growth model in theoretical assembly models such as the TAM. What is needed is a means for enforce this directionality constraint, which will allow us to reduce assembly errors. In this paper we describe a protection/deprotection strategy to strictly enforce the direction of tiling assembly growth so that the assembly process is robust against errors. Initially, we start with (1) a single “activated” tile with output pads that can bind with other tiles, along with (2) a set of “deactivated” tiles, meaning that the tile’s output pads are protected and cannot bind with other tiles. After other tiles bind to a “deactivated” tile’s input pads, the tile transitions to an active state and its output pads are exposed, allowing further growth. When these are activated in a desired order, we can enforce a directional assembly at the same scale as the original one. Such a system can be built with minimal modifications of existing DNA tile nanostructures. We propose a new type of tiles called activatable tiles and its role in compact proofreading. Activatable tiles can be thought of as a particular case of the more recent signal tile assembly model, where signals transmit binding/unbinding instructions across tiles on binding to one or more input sites. We describe abstract and kinetic models of activatable tile assembly and show that the error rate can be decreased significantly with respect to Winfree’s original kinetic tile assembly model without considerable decrease in assembly growth speed. We prove that an activatable tile set is an instance of a compact, error-resilient and self-healing tile-set. We describe a DNA design of activatable tiles and a mechanism of deprotection using DNA polymerization and strand displacement. We also perform detailed stepwise simulations using a DNA Tile simulator Xgrow, and show that the activatable tiles mechanism can reduce error rates in self assembly. We conclude with a brief discussion on some applications of activatable tiles beyond computational tiling, both as (1) a novel system for concentration of molecules, and (2) a catalyst in sequentially triggered chemical reactions.     

On the parallel execution time of tiled loops

Many computationally-intensive programs, such as those for differential equations, spatial interpolation, and dynamic programming, spend a large portion of their execution time in multiply-nested loops that have a regular stencil of data dependences. Tiling is a well-known compiler optimization that improves performance on such loops, particularly for computers with a multilevel hierarchy of parallelism and memory. Most previous work on tiling is limited in at least one of the following ways: they only handle nested loops of depth two, orthogonal tiling, or rectangular tiles. In our work, we tile loop nests of arbitrary depth using polyhedral tiles. We derive a prediction formula for the execution time of such tiled loops, which can be used by a compiler to automatically determine the tiling parameters that minimizes the execution time. We also explain the notion of rise, a measure of the relationship between the shape of the tiles and the shape of the iteration space generated by the loop nest. The rise is a powerful tool in predicting the execution time of a tiled loop. It allows us to reason about how the tiling affects the length of the longest path of dependent tiles, which is a measure of the execution time of a tiling. We use a model of the tiled iteration space that allows us to determine the length of the longest path of dependent tiles using linear programming. Using the rise, we derive a simple formula for the length of the longest path of dependent tiles in rectilinear iteration spaces, a subclass of the convex iteration spaces, and show how to choose the optimal tile shape.     

A pipelined schedule to minimize completion time for loop tiling with computation and communication overlapping

This paper proposes a new method for the problem of minimizing the execution time of nested for-loops using a tiling transformation. In our approach, we are interested not only in tile size and shape according to the required communication to computation ratio, but also in overall completion time. We select a time hyperplane to execute different tiles much more efficiently by exploiting the inherent overlapping between communication and computation phases among successive, atomic tile executions. We assign tiles to processors according to the tile space boundaries, thus considering the iteration space bounds. Our schedule considerably reduces overall completion time under the assumption that some part from every communication phase can be efficiently overlapped with atomic, pure tile computations. The overall schedule resembles a pipelined datapath where computations are not anymore interleaved with sends and receives to nonlocal processors. We survey the application of our schedule to modern communication architectures. We performed two sets of experimental results, one using MPI primitives over FastEthernet and one using the SISCI API over an SCI network. In both cases, the total completion time is significantly reduced.     

Dual Poisson-Disk Tiling: an efficient method for distributing features on arbitrary surfaces

This paper introduces a novel surface-modeling method to stochastically distribute features on arbitrary topological surfaces. The generated distribution of features follows the Poisson disk distribution, so we can have a minimum separation guarantee between features and avoid feature overlap. With the proposed method, we not only can interactively adjust and edit features with the help of the proposed Poisson disk map, but can also efficiently re-distribute features on object surfaces. The underlying mechanism is our dual tiling scheme, known as the Dual Poisson-Disk Tiling. First, we compute the dual of a given surface parameterization, and tile the dual surface by our specially-designed dual tiles; during the pre-processing, the Poisson disk distribution has been pre-generated on these tiles. By dual tiling, we can nicely avoid the problem of corner heterogeneity when tiling arbitrary parameterized surfaces, and can also reduce the tile set complexity. Furthermore, the dual tiling scheme is non-periodic, and we can also maintain a manageable tile set. To demonstrate the applicability of this technique, we explore a number of surface-modeling applications: pattern and shape distribution, bump-mapping, illustrative rendering, mold simulation, the modeling of separable features in texture and BTF, and the distribution of geometric textures in shell space.     

COMPILE TIME PARTITIONING OF NESTED LOOP ITERATION SPACES WITH NON-UNIFORM DEPENDENCES*

In this paper we address the problem of partitioning nested loops with non-uniform (irregular) dependence vectors. Parallelizing and partitioning of nested loops requires efficient inter-iteration dependence analysis. Although many methods exist for nested loop partitioning, most of these perform poorly when parallelizing nested loops with irregular dependences. Unlike the case of nested loops with uniform dependences these will have a complicated dependence pattern which forms a non-uniform dependence vector set. We apply the results of classical convex theory and principles of linear programming to iteration spaces and show the correspondence between minimum dependence distance computation and iteration space tiling. Cross-iteration dependences are analyzed by forming an Integer Dependence Convex Hull (IDCH). Every integer point in this IDCH corresponds to a dependence vector in the iteration space of the nested loops. A simple way to compute minimum dependence distances from the dependence distance vectors of the extreme points of the IDCH is presented. Using these minimum dependence distances the iteration space can be tiled. Iterations within a tile can be executed in parallel and the different tiles can then be executed with proper synchronization. We demonstrate that our technique gives much better speedup and extracts more parallelism than the existing techniques.     

Texture Stationarization: Turning Photos into Tileable Textures

Texture synthesis has grown into a mature field in computer graphics, allowing the synthesis of naturalistic textures and images from photographic exemplars. Surprisingly little work, however, has been dedicated to synthesizing tileable textures, that is, textures that when laid out in a regular grid of tiles form a homogeneous appearance suitable for use in memory‐sensitive real‐time graphics applications. One of the key challenges in doing so is that most natural input exemplars exhibit uneven spatial variations that, when tiled, show as repetitive patterns. We propose an approach to synthesize tileable textures while enforcing stationarity properties that effectively mask repetitions while maintaining the unique characteristics of the exemplar. We explore a number of alternative measures for texture stationarity and show how each measure can be integrated into a standard texture synthesis method (PatchMatch) to enforce stationarity at user‐controlled scales. We demonstrate the efficacy of our approach using a database of 118 exemplar images, both from publicly available sources as well as new ones captured under uncontrolled conditions, and we quantitatively analyze alternative stationarity measures for their robustness across many test runs using different random seeds. In conclusion, we suggest a novel synthesis approach that employs local histogram matching to reliably turn input photographs of natural surfaces into tiles well suited for artifact‐free tiling.     

A unifying approach to picture grammars

Several old and recent classes of picture grammars, that variously extend context-free string grammars in two dimensions, are based on rules that rewrite arrays of pixels. Such grammars can be unified and extended using an approach, whereby the right part of a rule is formalized by means of a finite set of permitted tiles. We focus on a simple type of tiling, named regional, and define the corresponding regional tile grammars. They include both Siromoney?s (or Matz?s) Kolam grammars and their generalization by Pr?ša, as well as Drewes?s grid grammars. Regionally defined pictures can be recognized with polynomial-time complexity by an algorithm extending the CKY one for strings. Regional tile grammars and languages are strictly included into our previous tile grammars and languages, and are incomparable with Giammarresi-Restivo tiling systems (or Wang systems).     

Spatially referenced methods of processing raster and vector data

The authors consider a general method of constructing addressing and arithmetic systems for two-dimensional image data using the hierarchy of ‘molecular’ tilings based on an original isohedral ‘atomic’ tiling. (Each molecular title at level k is formed from a constant number of tiles at level k−1; this is termed the ‘aperture’ property of the hierarchy.) In addition they present 11 objective criteria (which are of significance in cartographic image processing), by which these hierarchies and tilings may be described and compared.

Of the 11 topologically distinct types of isohedral tiling, three ([3⁶], [4⁴] and [6³]) are composed of regular polygons, and two of these ([3⁶] and[4⁴]) satisfy the condition that all tiles have the same ‘orientation’. In general, although each level in a hierarchy is topologically equivalent, the tiles may differ in shape at different levels and only [6³], [4⁴], [4.8²] and [4.6.12] are capable of giving rise to hierarchies in which the tiles at all levels are the same shape. The possible apertures of hierarchies obeying this condition are n² (for any n > 1)in the cases of [6³] and [4⁴]; n² or 2n² in the case of [4.8²]; and n² or 3n² in the case of [4.6.12].

In contrast the only tiling exhibiting the uniform ‘adjacency’ criterion is[3⁶]. However, hierarchies based on this atomic tiling generate molecular tiles with different shapes at every level. If these disadvantages are accepted, hierarchies based on first-level molecular tiles referred to as the 4-shape, 4′-shape, 7-shape and 9-shape are generated. Of these the 4-shape and the 9-shape appear to satisfy many of the cartographically desirable properties in addition to having an atomic tiling which exhibits uniform adjacency.

In recent years the generalized balanced ternary addressing system has been developed to exploit the image processing power of the 7-shape. The authors have generalized and extended this system as ‘tesseral addressing and arithmetic’, showing how it can be used to render a 4-shape into a spatially correct linear quadtree.     

Optimal tiling of heterogeneous images

A novel information theoretical approach has been developed, implemented and tested to approximate large, heterogeneous images with maps of varying spatial resolution and predefinedcomplexity. The goal of the approximation is the derivation of units in the spatial domain rather than determining classes in the attribute (spectral) domain. The proposed procedure is a regular, hierarchical tiling. The value of each tile is the local mean and the parti tion leads to a map represented by a region quadtree with minimum Kullback-divergence from the original image. Kullback-divergence is a non-parametric measure of dissimilarity of two spatial distributions and is applied here because of several advantageous properties. This tiling procedure can be also viewed as data compression, and it optimizes information loss under constraint on the spatial arrangement and number of tiles. The methodology is illustrated by the sampling design of an environmental soil mapping project of the salt-affected rangeland in Hortobagy, north-east Hungary.     

Procedural Generation of Rock Piles using Aperiodic Tiling

In this paper, we present a tiling method for generating piles of rocks without any computationally demanding physically‐based simulation. Previous techniques rely on a periodic tiling of rocks and generate unrealistic repetitive patterns. In contrast, our approach relies on a modified corner cube algorithm to generate a set of aperiodic tiles. We generalize the construction method so that the geometry of rocks should straddle corner cubes with a view to avoiding unrealistic gaps in the arrangement of rocks. Moreover, we propose an original technique to control the shape of rocks into contact by computing the Voronoï cells using a parameterized anisotropic distance. Our method has been successfully used to generate landscapes and stone huts and walls with thousands of rocks piled together.     

Optimal semi-oblique tiling

For 2D iteration space tiling, we address the problem of determining the tile parameters that minimize the total execution time on a parallel machine. We consider uniform dependency computations tiled so that (at least) one of the tile boundaries is parallel to the domain boundaries. We determine the optimal tile size as a closed form solution. In addition, we determine the optimal number of processors and also the optimal slope of the oblique tile boundary. Our results are based on the BSP model, which assures the portability of the results. Our predictions are justified on a sequence global alignment problem specialized to similar sequences using Fickett's k-band algorithm, for which our optimal semi-oblique tiling yields an improvement of a factor of 2.5 over orthogonal tiling. Our optimal solution requires a block-cyclic distribution of tiles to processors. The best one can obtain with only block distribution (as many authors require) is three times slower. Furthermore, our best running time is within 10 percent of the "predicted theoretical peak" performance of the machine!.     

An efficient code generation technique for tiled iteration spaces

This paper presents a novel approach for the problem of generating tiled code for nested for-loops, transformed by a tiling transformation. Tiling or supernode transformation has been widely used to improve locality in multilevel memory hierarchies, as well as to efficiently execute loops onto parallel architectures. However, automatic code generation for tiled loops can be a very complex compiler work, especially when nonrectangular tile shapes and iteration space bounds are concerned. Our method considerably enhances previous work on rewriting tiled loops, by considering parallelepiped tiles and arbitrary iteration space shapes. In order to generate tiled code, we first enumerate all tiles containing points within the iteration space and, second, sweep all points within each tile. For the first subproblem, we refine upon previous results concerning the computation of new loop bounds of an iteration space that has been transformed by a nonunimodular transformation. For the second subproblem, we transform the initial parallelepiped tile into a rectangular one, in order to generate efficient code with the aid of a nonunimodular transformation matrix and its Hermite Normal Form (HNF). Experimental results show that the proposed method significantly accelerates the compilation process and generates much more efficient code.     

一类基于迭代空间条块的并行有限差分Stencil 算法

高效的并行有限差分Stencil 算法对于求解大型线性方程组是十分重要的.针对并行有限差分Stencil 算法中数据局部性差、同步和通信开销大的问题.首先改进传统有限差分Stencil 算法,提出了多层对称遍历有限差分Stencil 算法.然后给出了以迭代空间条块序作为执行序的串行算法,通过沿时间轴对迭代空间进行时滞划分,在不改变迭代算法性质的同时,对迭代空间条块内部多次迭代计算,提高算法的数据局部性.最后提出一种基于迭代空间条块的并行算法,该算法利用改进的多面体模型对迭代空间网格划分,并通过网格条块重排序减少了Cache 缺失率、通信启动和同步次数.理论分析和实验结果表明,该并行模型比传统的区域分解方法和红黑排序并行算法具有更好的数据局部性,并行效率和可扩展性.     

迭代空间交错条块并行Gauss-Seidel算法

针对并行GS(Gauss-Seidel)迭代算法中数据局部性差、同步和通信开销大的问题,首先改进传统GS迭代,提出了多层对称GS迭代算法.然后给出了以迭代空间条块序作为执行序的串行执行模型.该模型通过对迭代空间进行"时滞"划分,对迭代空间条块内部多次迭代计算,提高算法的数据局部性.最后提出一种基于迭代空间条块的并行执行模型.该模型改进了迭代空间网格划分,并通过网格条块重排序减少了cache缺失率、通信启动和同步次数.实验结果表明,迭代空间交错条块并行算法比传统的区域分解方法和红黑排序并行算法具有更好的并行效率和可扩展性.     

Re-using digital narrative content in interactive games

This paper presents a model, called Scene-Driver, for the re-use of film and television material. We begin by exploring general issues surrounding the ways in which content can be sub-divided into meaningful units for re-use and how criteria might then be applied to the selection and ordering of these units. We also identify and discuss the different means by which a user might interact with the content to create novel and engaging experiences. The Scene-Driver model has been instantiated using content from an animated children's television series called Tiny Planets, which is aimed at children of 5–7-year old. This type of material, being story-based itself, lends itself particularly well to the application of narrative constraints to scene reordering, to provide coherence to the experience of interacting with the content.We propose an interactive narrative-driven game architecture, in which a user generates novel narratives from existing content by placing “domino” like tiles. These tiles act as “glue” between scenes and each tile choice dictates certain properties of the next scene to be shown within a game. There are three different game-types, based on three different ways in which tiles can be matched to scenes. We introduce algorithms for generating legal tile-sets for each of these three game-types, which can be extended to include narrative constraints. This ensures that all novel orderings adhere to a minimum narrative plan, which has been identified based on analysis of the Tiny Planets series and on narrative theories. We also suggest ways in which basic narratives can be enhanced by the inclusion of directorial techniques and by the use of more complex plot structures. In our evaluation studies with children in the target age-range, our game compared favourably with other games that the children enjoyed playing.     

Some Notes on Graph Automata, TilingSystems and Partition Logic

Introduce heuristically the newly definition(W.Thomas)for graph automata-using “tiles”to simulate the extension(over dag‘s) of the classical notions of transition moves;propose a sufficient condition for when graph automata can be reduced to (simpler)tiling systems,which is a generalization of a Thomas‘ result;and finally study the logic sepcification of tiling systems (particularly,over picture languages)by (existential)monadic partition logic,instead of the ususal and stronger framework(E)MSO.     

Tileable BTF

This paper presents a modular framework to efficiently apply the bidirectional texture functions (BTF) onto object surfaces. The basic building blocks are the BTF tiles. By constructing one set of BTF tiles, a wide variety of objects can be textured seamlessly without resynthesizing the BTF. The proposed framework nicely decouples the surface appearance from the geometry. With this appearance-geometry decoupling, one can build a library of BTF tile sets to instantaneously dress and render various objects under variable lighting and viewing conditions. The core of our framework is a novel method for synthesizing seamless high-dimensional BTF tiles, which are difficult for existing synthesis techniques. Its key is to shorten the cutting paths and broaden the choices of samples so as to increase the chance of synthesizing seamless BTF tiles. To tackle the enormous data, the tile synthesis process is performed in a compressed domain. This not only allows the handling of large BTF data during the synthesis, but also facilitates the compact storage of the BTF in a GPU memory during the rendering.