A data-driven VLSI array for arbitrary algorithms

The design of specialized processing array architectures, capable of executing any given arbitrary algorithm, is proposed. An approach is adopted in which the algorithm is first represented in the form of a dataflow graph and then mapped onto the specialized processor array. The processors in this array execute the operations included in the corresponding nodes (or subsets of nodes) of the dataflow graph, while regular interconnections of these elements serve as edges of the graph. To speed up the execution, the proposed array allows the generation of computation fronts and their cancellation at a later time, depending on the arriving data operands; thus it is called a data-driven array. The structure of the basic cell and its programming are examined. Some design details are presented for two selected blocks, the instruction memory and the flag array. A scheme for mapping a dataflow graph (program) onto a hexagonally connected array is described and analyzed. Two distinct performance measures-mapping efficiency and array utilization-and some performance results are discussed     

Minimum-diameter cyclic arrangements in mapping data-flow graphs onto VLSI arrays

Regular arrays of processing elements in VLSI have proved to be suitable for high-speed execution of many matrix operations. To execute an arbitrary computational algorithm on such processing arrays, it has been suggested mapping the given algorithm directly onto a regular array. The computational algorithm is represented by a data-flow graph whose nodes are to be mapped onto processors in the VLSI array. This study examines the complexity of mapping data-flow graphs onto square and hexagonal arrays of processors. We specifically consider the problem of routing data from processors in a given (source) sequence to another (target) sequence. We show that under certain conditions, the above problem is equivalent to the one of finding a minimum-diameter cyclic arrangement. The complexity of the latter problem is analyzed and upper and lower bounds on the number of intermediate rows of processors (between the source and target rows) are derived.     

面向SIMD机器的全局自动数据分割

提出了一种面向ＳＩＭＤ机器的全局数据自动分割算法,该算法能处理多个非紧嵌折循环嵌套,并且数组下标存取为循环变量的线性式,首先通过数据与迭代映射抽象了计算中的通信方式,然事提出识别规则模式通信模式的形式比条件,接着建立包含对准信息和相应通信开销的数据迭代图,并在数据迭代图的基础上提出了一个启发式算法来计算较优的数据分布和迭代分布,以优化处理单元之间的通信开销,通过发析多个循环嵌套所涉及的多个数组映和     

On mapping systolic algorithms onto the hypercube

Consideration is given to the problem of mapping systolic array algorithms into efficient algorithms for a fixed-size hypercube architecture. The authors describe in detail several optimal implementations of algorithms given for one-way one- and two-dimensional systolic arrays. Since interprocessor communication is many times slower than local computation in parallel computers built to date, the problem of efficient communication is specifically addressed for these mappings. In order to validate the technique experimentally, five systolic algorithms were mapped in various ways onto a 64-node NCUBE/7 MIMD hypercube machine. The algorithms are for the following problems: the shuffle scheduling problem, finite impulse response filtering, linear context-free language recognition, matrix multiplication, and computing the Boolean transitive closure. Experimental evidence indicates that good performance is obtained for the mappings     

保测地曲率的曲面曲线设计

给出一种在给定光滑曲面上进行曲线设计的算法．由于曲面上曲线的曲率向量可分解为测地曲率向量与法曲率向量的和,故可以通过设计平面源曲线,并将这条源曲线保测地曲率对应到给定曲面上,得到一条测地曲率和平面源曲线的曲率相同的目标曲线．取给定曲面上一点为初始点,逐次迭代跟踪得到整条目标曲线．该算法既可以用来进行曲面上的图案设计,也可用于求解光滑曲面上的测地线。     

A Generic Framework for Efficient 2-D and 3-D Facial Expression Analogy

Facial expression analogy provides computer animation professionals with a tool to map expressions of an arbitrary source face onto an arbitrary target face. In the recent past, several algorithms have been presented in the literature that aim at putting the expression analogy paradigm into practice. Some of these methods exclusively handle expression mapping between 3-D face models, while others enable the transfer of expressions between images of faces only. None of them, however, represents a more general framework that can be applied to either of these two face representations. In this paper, we describe a novel generic method for analogy-based facial animation that employs the same efficient framework to transfer facial expressions between arbitrary 3-D face models, as well as between images of performer's faces. We propose a novel geometry encoding for triangle meshes, vertex-tent-coordinates, that enables us to formulate expression transfer in the 2-D and the 3-D case as a solution to a simple system of linear equations. Our experiments show that our method outperforms many previous analogy-based animation approaches in terms of achieved animation quality, computation time and generality.     

基于波场模型的宽带相干源方位估计优化方法

阵列流形内插方法（AMI）是一种基于波场模型的宽带聚焦方法。它无须角度预估, 可以应用于任意已知结构的阵列, 但其采样矩阵的截断点数通常选取较大, 尤其在均匀线阵列下大大增加了运算量。针对这个问题, 提出了一种采样矩阵优化方法, 该方法利用贝塞尔函数的性质, 重新构造了采样矩阵, 使得新的采样矩阵在不损失信号信息的前提下, 最大限度地降低运算量, 从而有效缩短了运算时间。计算机仿真实验结果表明了该方法只需和阵元个数相同的截断点数就可以有效地实现方位估计, 并获得与阵列流形内插方法相当的方位估计性能。     

Texture mapping using surface flattening via multidimensionalscaling

Presents a novel technique for texture mapping on arbitrary surfaces with minimal distortion by preserving the local and global structure of the texture. The recent introduction of the fast marching method on triangulated surfaces has made it possible to compute a geodesic distance map from a given surface point in O(n lg n) operations, where n is the number of triangles that represent the surface. We use this method to design a surface flattening approach based on multi-dimensional scaling (MDS). MDS is a family of methods that map a set of points into a finite-dimensional flat (Euclidean) domain, where the only data given is the corresponding distance between every pair of points. The MDS mapping yields minimal changes of the distances between the corresponding points. We then solve an "inverse" problem and map a flat texture patch onto a curved surface while preserving the structure of the texture     

The efficient computation of ownership sets in HPF

Ownership sets are fundamental to the partitioning of program computations across processors by the owner-computes rule. These sets arise due to the mapping of arrays onto processors. In this paper, we focus on how ownership sets can be efficiently determined in the context of the HPF language and show how the structure of these sets can be symbolically characterized in the presence of arbitrary array alignment and array distribution directives. Our starting point is a system of equalities and inequalities due to Ancourt et al. (1995) that captures the array mapping problem in HPF. We arrive at a refined system that enables us to efficiently solve for the ownership set using the Fourier-Motzkin Elimination technique and that requires the course vector as the only auxiliary vector. The formulation makes it possible to enumerate the elements of the ownership set exactly once, a feature that is very beneficial when such sets are applied to handle DO loops qualified by HPF's INDEPENDENT directive. We develop important and general properties pertaining to HPF alignments and distributions and show how they can be used to eliminate redundant communication due to array replication. Polynomial-time schemes that determine whether the ownership set of a particular processor, with respect to some array, is the empty set or whether the ownership set of every processor, with respect to some array, is the empty set, are presented. We show how distribution directives with unspecified processor meshes can be efficiently handled at compile time. We also show how to avoid the generation of communication code when pairs of array references are ultimately mapped onto the same processors. Experimental data demonstrating the improved code performance that the latter optimization enables is presented and discussed     

The Role of Observers in Computations

John Searle raised the question whether all computation is observer-relative. Indeed, all of the common views of computation, be they semantical, functional or causal rely on mapping something onto the states of a physical or abstract process. In order to effectively execute such a mapping, this process would have to be observed in some way. Thus a probably syntactical analysis by an observer seems to be essential for judging whether a given process implements some computation or not. In order to be able to explore the nature of these observers in a more formal way, we look at the Computing by Observing paradigm, a theoretical model of computation that includes an observer. We argue that the observers used there, monadic transducers, are good candidates for formalizing the way in which the syntax of a process must be analysed in order to judge whether it is computational.     

二叉树平面坐标网及其应用

二叉树平面坐标网、平面坐标网二叉树的定义及其基本定理在本文给出。利用该平面坐标网二叉树，把平面中的网络点一一映射到一个整数集合上，从而可以把平面中的任意点近似地映射为一个整数，而且可以任意精确，对任意平面图形图象的处理、储存和传输起着极其重要的作用。本文给出的应用例子是二维实体的近似表示、储存、处理和打打印。     

The convergence of functions to fixedpoints of recursive definitions

The classical method for constructing the least fixedpoint of a recursive definition is to generate a sequence of functions whose initial element is the totally undefined function and which converges to the desired least fixedpoint. This method, due to Kleene, cannot be generalized to allow the construction of other fixedpoints. In this paper we present an alternate definition of convergence and a new fixedpoint access method of generating sequences of functions for a given recursive definition. The initial function of the sequence can be an arbitrary function, and the sequence will always converge to a fixedpoint that is “close” to the initial function. This defines a monotonic mapping from the set of partial functions onto the set of all fixedpoints of the given recursive definition.     

带不失真纹理映射的三维Morphing动画研究及实现

介绍了三维Morphing，编程实现了相同顶点数和拓扑结构的物体之间的Morphing，并采用一种带不失真纹理映射的船形曲面造型法，有效地消除了形变曲面的纹理映射的图像失真问题，最后给出了基于任意拓扑结构的物体间Morphing的方法。     

医学图象体数据场的剖切显示方法

为了给医生提供一些全面、直观和准确的诊断信息 ,讨论了一种对医学图象体数据场进行二维和三维剖切显示的方法 ,其中对于二维剖切显示 ,可首先由用户通过人机交互的方式来给出对体数据场进行任意剖切显示的路径 ;然后运用反求工程的求解思路沿切割路径进行量化和采样来得到沿切割路径上每个采样点在对应图象坐标空间中的位置 ,并由此获得剖切平面上所有采样点的空间位置坐标 ;最后通过对体数据场进行重采样和插值操作来实现对空间体数据场的二维任意剖切显示 .对于三维剖切显示 ,可首先采用与二维剖切操作类似的图象采样和插值操作来获得纹理数据阵列 ,然后结合纹理映射技术 ,将纹理数据映射到三维坐标空间中 ,以实现数据场的三维空间剖切显示     

Texture Mapping Real‐World Objects with Hydrographics

In the digital world, assigning arbitrary colors to an object is a simple operation thanks to texture mapping. However, in the real world, the same basic function of applying colors onto an object is far from trivial. One can specify colors during the fabrication process using a color 3D printer, but this does not apply to already existing objects. Paint and decals can be used during post‐fabrication, but they are challenging to apply on complex shapes. In this paper, we develop a method to enable texture mapping of physical objects, that is, we allow one to map an arbitrary color image onto a three‐dimensional object. Our approach builds upon hydrographics, a technique to transfer pigments printed on a sheet of polymer onto curved surfaces. We first describe a setup that makes the traditional water transfer printing process more accurate and consistent across prints. We then simulate the transfer process using a specialized parameterization to estimate the mapping between the planar color map and the object surface. We demonstrate that our approach enables the application of detailed color maps onto complex shapes such as 3D models of faces and anatomical casts.     

A BSP Bareiss Algorithm for Toeplitz Systems

In this paper, a BSP (bulk synchronous parallel) Bareiss algorithm for Toeplitz system is described. We investigate various data distribution and scheduling strategies for mapping a typical class of systolic array algorithms onto BSP machines. Load balance, both in communication and computation, as well as linear speedup have been achieved for the Toeplitz system solver and at the same time the minimum memory requirement is achieved. An implementation has been tested on Sun workstations, an SGI Power Challenge, and an IBM SP2, using the Oxford BSPlib (Hillet al., 1997).     

Spacetime representations of computational structures

A general theory for characterizing and then realizing algorithms in hardware is given. The physical process of computation is interpreted in terms of a graph in physical space and time, and then an embedding into this graph of another graph which characterizes data flow in particular algorithms is given. The types of the special class of computational structures called systolic arrays which can occur physically are completely described, and a technique is developed for mapping the graph of a particular systolic algorithm into a physical array. Examples illustrate the methodology.     

虚平面映射:深度图像内部视点的绘制技术

首先推导与归纳了图像三维变换中像素深度场的变换规律,同时提出了基于深度场和极线原则的像素可见性别方法,根据上述理论和方法,提出一种基于深度图像的建模与绘制(image-based modeling and rendering,简称IBMR)技术,称为虚平面映射.该技术可以基于图像空间内任意视点对场景进行绘制.绘制时,先在场景中根据视线建立若干虚拟平面,将源深度图像中的像素转换到虚平面上,然后通过对虚平面上像素的中间变换,将虚平面转换成平面纹理,再利用虚平面的相互拼接,将视点的成像以平面纹理映射的方式完成.新方法还能在深度图像内侧,基于当前视点快速获得该视点的全景图,从而实现视点的实时漫游.新方法视点运动空间大、存储需求小,且可以发挥图形硬件的纹理映射功能,并能表现物体表面的三维凹凸细节和成像视差效果,克服了此前类似算法的局限和不足.