bluuebunny/crossref_metadata_2025 huggingface dataset:
Asynchronous and clocked control structures for VLSI based interconnection networks
Authors: Franklin Mark A. , Wann Donald F.
Published: November 2005

A central issue in the design of multiprocessor systems is the interconnection network which provides communications paths between the processors. For large systems, high bandwidth interconnection networks will require numerous 'network chips' with each chip implementing some subnetwork of the original larger network. Modularity and growth are important properties for such networks since multiprocessor systems may vary in size. This paper is concerned with the question of timing control of such networks. Two approaches, asynchronous and clocked, are used in the design of a basic network switching module. The modules and the approaches are then modelled and equations for network time delay are developed. These equations form the basis for a comparison between the two approaches. The importance of clock distribution strategies and clock skew is quantified, and a network clock distribution scheme which guarantees equal length clock paths is presented.
A control processor for a reconfigurable array computer
Authors: Jenevein R. M. , Browne J. C.
Published: November 2005

The problems of resource allocation, configuration and reconfiguration and network control must be solved before reconfigurable array computers can be effectively utilized. The interconnection networks proposed for these systems vary so that there has been no common or optimal solution proposed to these problems. This paper defines and describes the objectives, design, implementation and use of a network controller for a reconfigurable array computer, the Texas Reconfigurable Array Computer (TRAC). The objectives for the network controller are defined by management of the system state, the requirements of the operating system for functionality and the interface the network presents to the operating system. These objectives may be expected to have at least some commonality across most reconfigurable network architectures. The structure of the network controller given herein may offer guidance for development of controllers for other reconfigurable network architectures.
A general class of processor interconnection strategies
Authors: Bhuyan Laxmi N. , Agrawal Dharma P.
Published: November 2005

A new class of general topologies is proposed in this paper for interconnecting a large network of computers in parallel and distributed environment. These structures have been shown to possess small internode distances, fairly low number of links per node, easy message routing and large number of alternate paths that can be used in case of faults in the system. The interconnection is based on a mixed radix number system, presented in this paper. The technique results in a variety of structures for a given number of processors N, depending on the required diameter in the network.

A bus oriented structure is also introduced here, based on the same mathematical framework. These structures possess only two I/O ports per processor and are also shown to have small internode distances.
Instruction set design issues relating to a static dataflow computer
Authors: Burkowski F. J.
Published: November 2005

In an effort to minimize traffic in the distribution network of a static dataflow machine the design of the system includes alternate data paths so that data movement may take place over “shorter” paths when it is permissible to do so. The main emphasis of this approach is to allow rapid transfer of data in sequential code segments residing in single memory blocks. This decreases crowding in the more expensive distribution network utilized by data that fans out to two or more blocks as required when more concurrent activity is to be initiated during the execution of the program. The objective of data movement minimization has also influenced the design of the instruction set. In this case, composite, that is, “multi-actor” instructions have been proposed as an effective strategy. This has been done without compromizing the utility of the instructions or overly increasing the time and space requirements of their execution. In the paper, these principles are illustrated by defining controlled instructions that are especially useful in the management of loops.
Decoupled access/execute computer architectures
Authors: Smith James E.
Published: November 2005

An architecture for improving computer performance is presented and discussed. The main feature of the architecture is a high degree of decoupling between operand access and execution. This results in an implementation which has two separate instruction streams that communicate via queues. A similar architecture has been previously proposed for array processors, but in that context the software is called on to do most of the coordination and synchronization between the instruction streams. This paper emphasizes implementation features that remove this burden from the programmer. Performance comparisons with a conventional scalar architecture are given, and these show that considerable performance gains are possible.

Single instruction stream versions, both physical and conceptual, are discussed with the primary goal of minimizing the differences with conventional architectures. This would allow known compilation and programming techniques to be used. Finally, the problem of deadlock in such a system is discussed, and one possible solution is given.
A data flow architecture with a paged memory system
Authors: Caluwaerts L. J. , Debacker J. , Peperstraete J. A.
Published: November 2005

During the last ten years, data flow has become an exciting research area and several architectures have been proposed and built. They differ mostly in the way they handle data structures and how they provide mechanisms for token labeling or colouring in order to make data flow graphs reentrant.

The paper presents a data flow architecture with a paged memory system to hold both data flow programs and data structures. The token labeling mechanism is coupled with the memory management system in order to provide for each token a unique memory location.

The instruction format allows instructions with multiple operands and multiple destinations for each result.

Data structures are held in memory while pointers to the structures are circulating as tokens.

The proposed architecture is able to execute data flow programs at the level of single instructions or at a higher level.
Sentry
Authors: Barton Gene C.
Published: November 2005

A hardware protection mechanism called the Sentry is introduced which requires minimal overhead to be invoked and no overhead when providing protection. It is fail-safe, fault tolerant, and can be added to most existing architectures. It provides a convenient low level service suitable as the underlying primitive around which more sophisticated mechanisms can be established.
A logic simulation machine
Authors: Abramovici M. , Levendel Y. H. , Menon P. R.
Published: November 2005

Special-purpose CAD hardware is increasingly being considered as a means to meet the challenge posed to conventional (software-based) CAD tools by the growing complexity of VLSI circuits. In this paper we describe the architecture of a logic simulation machine employing distributed and parallel processing. Our architecture can accommodate different levels of modeling ranging from simple gates to complex functions, and support timing analysis. We estimate that simulation implemented by the proposed special-purpose hardware will be between 10 and 60 times faster than currently used software algorithms running on general-purpose computers. With the available technology, a throughput of 1,000,000 gate evaluations/second can be achieved.
Rollback propagation detection and performance evaluation of FTMR
2
M—a fault-tolerant multiprocessor
Authors: Lee Yann-Hang , Shin Kang G.
Published: November 2005

In this paper we consider the rollback propagation and the performance of a fault-tolerant multiprocessor with a rollback recovery mechanism (FTMR
2
M)[1], which was designed to be tolerant of hardware failure with minimum time overhead. Rollback propagation between cooperating processes is usually required to ensure correct recovery from failure. To minimize the waste of processor time and storage overhead required for handling sophisticated rollback propagations, the FTMR
2
M always keeps one recoverable state. Approaches for evaluating the recovery overhead and analyzing the performance of FTMR
2
M are presented. Two methods for detecting rollback propagations and multi-step rollbacks between cooperating processes are also proposed.
Design of a 2 × 2 fault-tolerant switching element
Authors: Lin Woei , Wu Chuan-lin
Published: November 2005

This paper describes the architecture of a 2 × 2 fault-tolerant switching element which can be used to modularly construct interconnection networks for multi-processing and local computer networking. The switching element uses distributed control and circuit switching. Its good gate-to-pin ratio can facilitate VLSI implementation.
Fault-tolerant wafer-scale architectures for VLSI
Authors: Fussell Donald , Varman Peter
Published: November 2005

The basic problem which limits both yields and chip sizes is the fact that circuits created using current design techniques will not function correctly in the presence of even a single flaw of sufficient size anywhere on the chip. In this work we examine the problem of constructing chips up to the size of a wafer which operate correctly despite the presence of such flaws. This can be accomplished by building on the wafer a nearest-neighbor network of small, independent, asynchronously communicating modules. A specific algorithm to be performed by the wafer is then mapped onto a fault-free subgraph of the network. We are interested in algorithms which map naturally onto a linear array of identical processors. Construction of fault-tolerant implementations of these algorithms is addressed in two contexts. First we consider the general problem of finding a fault-free subgraph of the host network which is isomorphic to the linear array required to solve a problem. We then examine ways to tailor a specific, known algorithm to the fault-tolerant context.
A recursive computer architecture for VLSI
Authors: Treleaven Philip C. , Hopkins Richard P.
Published: November 2005

We present a general-purpose computer architecture based on the concept of recursion, suitable for VLSI computer systems built from replicated (LEGO-like) computing elements. The recursive computer architecture is defined by presenting a program organisation, a machine organisation and an experimental machine implementation oriented to VLSI. The program organisation, called recursive control flow, attempts a synthesis of the concepts underlying traditional control flow, data flow and reduction, to exploit the individual strengths of each organisation. The machine organisation is based on replicated general-purpose computing elements, as well as special-purpose computing elements that allow the function of individual computer systems to be specialised. These elements are interconnected to form a larger computer system and cooperate in the concurrent execution of a program. The experimental implementation is being restricted to simple, identical microcomputers each containing a memory, a processor and a communications capability. This future generation of LEGO-like computer systems are termed fifth generation computers [1] by the Japanese.
A multiple processor system for real time control tasks
Authors: Markenscoff Pauline
Published: November 2005

The performance of a special purpose multiple processor system with a shared bus for the transmission of output data is studied. A finite population queueing model with Poisson arrivals and services is developed and analyzed. The number of states is found to increase factorially with the number of customers. In the special case of equal arrival and service rates, the model reduces to a simpler one, whose solution is obtained by a recursive technique that reduces significantly the computation time. Under certain conditions, the simplified model provides a good approximation to the throughput predicted by the general model.
Effects of cache coherency in multiprocessors
Authors: Dubois Michel , Briggs Fayė A.
Published: November 2005

In many commercial multiprocessor systems, each processor accesses the memory through a private cache. One problem that could limit the extensibility of the system and its performance is the enforcement of cache coherence. A mechanism must exist which prevents the existence of several different copies of the same data block in different private caches. In this paper, we present an indepth analysis of the effect of cache coherency in multiprocessors. A novel analytical model for the program behavior of a multitasked system is introduced. The model includes the behavior of each process and the interactions between processes with regard to the sharing of data blocks. An approximation is developed to derive the main effects of the cache coherency contributing to degradations in system performance.
Finding an extremum in a network
Authors: Levitan Steven P. , Foster Caxton C.
Published: November 2005

We propose a method for implementing “the election process” - finding an extrema of values computed in a multiprocessor network. It operates in an average time less than Log2(N), for a network of size N. It requires a single register, memory cell, or global buss into which all the processors can attempt to write, with the success of one guaranteed; and from which they may all read, in parallel. A second method is given which guarantees termination in O(Log2(MAX)) steps.
Size, power, and speed (Keynote Address)
Authors: Wilkes Maurice V.
Published: November 2005

The author discusses the roles of power and size in determining the speed of a computer.
Research on synthesis of concurrent computing systems (Extended Abstract)
Authors: King Richard M.
Published: November 2005

The object of our research is the codification of programming knowledge for the synthesis of concurrent programs. We present sample rules and techniques that we show can be used to derive two concurrent algorithms: dynamic programming (for the class of problems that run in polynomial time on sequential machines) and array multiplication. For both derived concurrent versions the code runs in linear time. The concurrent versions are significant and complex algorithms, though they are not new and already have been reported in the literature. The synthesis knowledge for these derivations is embodied in seven synthesis rules. We expect these rules to generalize to other classes of algorithms.

We have also discovered a pair of techniques called
virtualization
and
aggregation.
This pair of techniques (plus the seven rules) is shown to be powerful enough to synthesize Kung's systolic array architecture [Kung-76] from a specification of matrix multiplication.
Implementing streams on a data flow computer system with paged memory
Authors: Caluwaerts L. J. , Debacker J. , Peperstraete J. A.
Published: November 2005

In several data flow architectures, “
streams
” are proposed as special data structures able to improve parallel execution in functional programs by providing a pipelining effect between different program parts.

This paper describes how streams are implemented on a data flow computer system based on a paged memory. This memory holds both the data flow programs and data structures such as streams.

Streams are stored in the memory as a linked list of pages while pointers to the streams are flowing as data tokens. A reference count is used to prevent for excessive copying of data and to control the allocation and recovery of pages.

Input/output is treated as a special application of streams.
The Piecewise Data Flow architecture control flow and register management
Authors: Requa Joseph E.
Published: November 2005

This paper presents the hardware register management and instruction block control flow sequencing provided by the PDF block processing section of the Piecewise Data Flow machine, a proposed high performance computer architecture. Combined, these capabilities provide the maximum allowed execution overlap of instruction blocks with minimum hardware contention and high hardware utilization.
On the working set concept for data-flow machines
Authors: Tokoro Mario , Jagannathan J. R. , Sunahara Hideki
Published: November 2005

This paper discusses the concept of the working set for data-flow machines in order to establish one of the criteria for the realization of cost effective data-flow machines. The characteristics of program execution in conventional machines and data-flow machines are compared. Then, a definition of the working set for data-flow machines is proposed, based on the
simultaneity of execution
and the
principle of locality
. Several segmentation, fetch, and removal policies are described. Evaluation is made in terms of feasibility, efficiency, and performance, through computer simulations.
A data driven system based on a microprogrammed processor module
Authors: Marczyński R. W. , Milewski J.
Published: November 2005

A hardware approach to the design of data driven computers using a microprogrammed processor as a building block is proposed. The data driven computer is a network of processors virtually implementing the data flow program graph. The flexibility of microprogramming provides a wide variety of possible implementations for the fixed data driven network structure. Due to the proposed organization of communication the network is deadlock-free.
A user-microprogrammable, local host computer with low-level parallelism
Authors: Tomita Shinji , Shibayama Kiyoshi , Kitamura Toshiaki , Nakata Toshiyuki , Hagiwara Hiroshi
Published: November 2005

This paper describes the architecture of a dynamically microprogrammable computer with low-level parallelism, called QA-2, which is designed as a high-performance, local host computer for laboratory use. The architectural principle of the QA-2 is the marriage of high-speed, parallel processing capability offered by four powerful Arithmetic and Logic Units (ALUs) with architectural flexibility provided by large scale, dynamic user-microprogramming. By changing its writable control storage dynamically, the QA-2 can be tailored to a wide spectrum of research-oriented applications covering high-level language processing and real-time processing.

The QA-2 employs four identical ALUs which are independently controlled by the different fields of a 256-bit microinstruction. Sharing one uniform register file (6-kBytes), the ALUs can perform mutually independent/dependent operations on four sets of variable length operands (max. 4-Bytes × 4). In main memory accessing, four sets of variable length data (max. 4-Bytes × 4) can be simultaneously read from or written into different/continuous locations. In addition, structured microprogramming is possible because the QA-2 supports natural control structures such as an IF f(logic variables) THEN (CALL, GOTO or RETURN) ELSE (CALL,GOTO or RETURN) statement. All these features combine to yield an extensive microprogramming capability with which the user can tailor the QA-2 to his problems at hand.
Resource allocation in rectangular CC-banyans
Authors: Opper Eli , Malek Miroslaw , Lipovski G. Jack
Published: November 2005

A resource allocation problem in a reconfigurable multicomputer architecture based on rectangular CC-banyan multistage interconnection network with arbitrary fanout and arbitrary number of levels is studied. Four commonly used problem structures such as ring, pipeline, broadcast and macropipeline are introduced and the mapping problem of these structures on the system model which is camparable to the resource allocation problem, is discussed. Analytic solutions to several mapping questions are presented and a new fault diagnosis method based on the solution to the problem of mapping the ring structure is given.
An experimental system for Computer Science instruction
Authors: Krishnan R. Kalyana , Rajasekar A. K. , Moghe C. S.
Published: November 2005

A number of educational institutions of the world offer academic programs in Computer Science for undergraduate and graduate students. Many of these programs have used a medium sized to large computer system as a facility for the students. There is a need for a system in which the students have full access to the machine in terms of hardware and software details. Most commercial systems do not normally provide this information. In this paper we describe an experimental system designed and built at I.I.T., Madras, which is used for illustrating several concepts in Machine Organization, Computer Architecture, Operating Systems Distributed Computing etc.. present use of the system for Computer Science instruction is identified and proposed applications are indicated.
A retrospective on the Dorado, a high-performance personal computer
Authors: Pier Kenneth A.
Published: November 2005

In late 1975, members of the Xerox Palo Alto Research Center embarked on the specification of a high-performance successor to the Alto personal minicomputer, in use since 1973. After four years, the resulting machine, called the Dorado, was in use within the research community at PARC. This paper begins with an overview of the design goals, architecture, and implementation of the Dorado and then provides a retrospective view and critique of the Dorado project as a whole. The major machine architectural features are evaluated, other project aspects such as design automation and management structures are explained, a chronological history with milestones is included, and a variety of accomplishments, red herrings, and shortfalls is discussed. The paper concludes with some speculations on what the project might have done differently and what might be done differently today instead of in the late 1970s.

Although more than a dozen scientists and technicians contributed to the project, the evaluative and speculative parts of this paper are the sole responsibility of the author.
System/370 extended architecture
Authors: Dugan Robert J.
Published: November 2005

The 370-XA channel-subsystem architecture represents an evolutionary and significant extension of the System/370 channel architecture. This paper examines the programming-machine interface of the 370-XA channel subsystem and how it was designed to meet the requirements called for by the evolution of IBM's large-scale systems. In particular, emphasis has been placed upon meeting the needs of multiprocessing, maintaining availability, and supporting large I/O configurations while at the same time preserving compatibility for running System/370 channel programs.
Switching strategies in a class of packet switching networks
Authors: Kumar Manoj , Dias Daniel M. , Jump J. R.
Published: November 2005

This paper investigates some methods for improving the performance of Single Stage Shuffle Exchange Networks (SENs) and Multistage Interconnection Networks (MINs). The three new switching strategies proposed use extra buffers to enhance performance. Approximate analysis and simulation results indicate significant improvement in performance for both SENs and MINs. An intuitive method for determining the applicability of the approximate analysis is discussed and some performance measures, which should be useful in evaluating the performance of networks are defined.
Concurrent error detection in VLSI interconnection networks
Authors: Fuchs W. Kent , Abraham Jacob A. , Huang Kuang-Hua
Published: November 2005

Comprehensive VLSI fault models are proposed for three broad classes of interconnection networks between multiple processors and multiple memory modules. System-level algorithms are given for concurrent detection of errors produced by these faults during the normal use of the networks. The proposed algorithms are shown to be applicable to the three classes of interconnection networks with minimal changes in their classical design. The algorithms are appropriate for the broad classes of permanent and transient faults predominant in dense VLSI and wafer-scale integration with a minimal amount of network redundancy required for implementation.
The new generation of computer architecture
Authors: Treleaven Philip C.
Published: November 2005

Four major areas of research are involved in attempting to identify the fifth generation of computers (cir. 1990). The investigation of: knowledge processing systems, data and demand driven computers, integrating communications and computers, and VLSI processor architectures. From these four areas, two approaches for the fifth generation are emerging: one “revolutionary” - a parallel logic machine supporting knowledge processing applications, and the other “evolutionary” - a decentralised control flow system consisting of a network of heterogeneous processors. This paper describes the above four areas of research and discusses how their computing technologies are converging to produce fifth generation computers. It then contrasts the revolutionary logic machine approach adopted by Japan's Fifth Generation Project, and favoured by the artificial intelligence community, with the evolutionary control flow computer approach favoured by the data communications and microelectronics communities.
A critique of multiprocessing von Neumann style
Authors: Arvind  , Iannucci Robert A.
Published: November 2005

In recent years, there have been many attempts to construct multiple-processor computer systems. The majority of these systems are based on von Neumann style uniprocessors. To exploit the parallelism in algorithms, any high performance multiprocessor system must, however, address two very basic issues-the ability to tolerate long latencies for memory requests and the ability to achieve unconstrained, yet synchronized, access to shared data. In this paper, we define these two problems, and examine the ways in which they are addressed by some of the current and past von Neumann multiprocessor projects. We then proceed to hypothesize that the problems
cannot
be solved in a von Neumann context. We offer the data flow model as one possible alternative, and we describe our research in this area.
The problem of synthetically generating IP traffic matrices
Authors: Nucci Antonio , Sridharan Ashwin , Taft Nina
Published: November 2005

There exist a wide variety of network design problems that require a traffic matrix as input in order to carry out performance evaluation. The research community has not had at its disposal any information about how to construct realistic traffic matrices. We introduce here the two basic problems that need to be addressed to construct such matrices. The first is that of synthetically generating traffic volume levels that obey spatial and temporal patterns as observed in realistic traffic matrices. The second is that of assigning a set of numbers (representing traffic levels) to particular node pairs in a given topology. This paper provides an in-depth discussion of the many issues that arise when addressing these problems. Our approach to the first problem is to extract statistical characteristics for such traffic from real data collected inside two large IP backbones. We dispel the myth that uniform distributions can be used to randomly generate numbers for populating a traffic matrix. Instead, we show that the lognormal distribution is better for this purpose as it describes well the mean rates of origin-destination flows. We provide estimates for the mean and variance properties of the traffic matrix flows from our datasets. We explain the second problem and discuss the notion of a traffic matrix being well-matched to a topology. We provide two initial solutions to this problem, one using an ILP formulation that incorporates simple and well formed constraints. Our second solution is a heuristic one that incorporates more challenging constraints coming from carrier practices used to design and evolve topologies.
On the robustness of router-based denial-of-service (DoS) defense systems
Authors: Xu Ying , Guérin Roch
Published: November 2005

This paper focuses on "router-based" defense mechanisms, and whether they can provide effective solutions to network Denial-of-Service (DoS) attacks. Router-based defenses operate either on traffic aggregates or on individual flows, and have been shown, either alone or in combination with other schemes, e.g., traceback, to be reasonably effective against certain types of basic attacks. Those attacks are, however, relatively brute-force, and usually accompanied by either significant increases in congestion, and/or traffic patterns that are easily identified. It is, therefore, unclear if router-based solutions are viable in the presence of more diverse or sophisticated attacks. As a result, even if incorporating defense mechanisms in the routers themselves has obvious advantages, such schemes have not seen wide deployments. Our ultimate goal is to determine whether it is possible to build router-based defense mechanisms that are effective against a wide range of attacks. This paper describes a first phase of this effort aimed at identifying weaknesses in existing systems. In particular, the paper demonstrates that aggregate defense systems can be readily circumvented, even by a single attacker, through minor modifications of its flooding patterns. Flow-based defenses fare slightly better, but can still be easily fooled by a small number of attackers generating transient flooding patterns. The findings of the paper provide insight into possible approaches for designing better and more robust router-based defense systems.
Dagstuhl seminar on disruption tolerant networking
Authors: Brunner Marcus , Eggert Lars , Fall Kevin , Ott Jörg , Wolf Lars
Published: November 2005

Disruption Tolerant Networking (DTN) is a new area of research to improve network communication when connectivity is periodic, intermittent, and/or prone to disruptions. A seminar on DTN was held at at Schloß Dagstuhl, Germany, from 3 to 6 April 2005. Researchers from different fields discussed their approaches to dealing with delays, intermittent connectivity, and the potential non-existence of an end-to-end path in a number of different environments. The two major areas identified were: (1) dealing with delay and disruption in the present Internet in the context of wireless, mobile, and nomadic communications, supporting existing applications and (2) addressing new applications with a focus on exploiting discontinuous connectivity and opportunistic contacts for asynchronous communications. This article briefly reviews the seminar presentations and discussions.
Part I
Authors: Wischik Damon , McKeown Nick
Published: November 2005

In this article we describe recent work on buffer sizing for core Internet routers. This work suggests that the widely-used rule of thumb leads to buffers which are much larger than they need to be. For example, the buffer in a backbone router could be reduced from 1,000,000 packets to 10,000 without loss in performance. It could be reduced even further, perhaps to 10-20 packets, at the cost of a small amount of bandwidth utilization. This tradeoff is worth considering, for example for a possible future all-optical router.
Making the world (of communications) a different place
Authors: Clark David D. , Partridge Craig , Braden Robert T. , Davie Bruce , Floyd Sally , Jacobson Van , Katabi Dina , Minshall Greg , Ramakrishnan K. K. , Roscoe Timothy , Stoica Ion , Wroclawski John , Zhang Lixia
Published: November 2005

How might the computing and communications world be materially different in 10 to 15 years, and how might we define a research agenda that would get us to that world?
Skinning mesh animations
Authors: James Doug L. , Twigg Christopher D.
Published: November 2005

We extend approaches for skinning characters to the general setting of skinning deformable mesh animations. We provide an automatic algorithm for generating progressive skinning approximations, that is particularly efficient for pseudo-articulated motions. Our contributions include the use of nonparametric mean shift clustering of high-dimensional mesh rotation sequences to automatically identify statistically relevant bones, and robust least squares methods to determine bone transformations, bone-vertex influence sets, and vertex weight values. We use a low-rank data reduction model defined in the undeformed mesh configuration to provide progressive convergence with a fixed number of bones. We show that the resulting skinned animations enable efficient hardware rendering, rest pose editing, and deformable collision detection. Finally, we present numerous examples where skins were automatically generated using a single set of parameter values.
Face transfer with multilinear models
Authors: Vlasic Daniel , Brand Matthew , Pfister Hanspeter , Popović Jovan
Published: November 2005

Face Transfer is a method for mapping videorecorded performances of one individual to facial animations of another. It extracts visemes (speech-related mouth articulations), expressions, and three-dimensional (3D) pose from monocular video or film footage. These parameters are then used to generate and drive a detailed 3D textured face mesh for a target identity, which can be seamlessly rendered back into target footage. The underlying face model automatically adjusts for how the target performs facial expressions and visemes. The performance data can be easily edited to change the visemes, expressions, pose, or even the identity of the target---the attributes are separably controllable. This supports a wide variety of video rewrite and puppetry applications.Face Transfer is based on a multilinear model of 3D face meshes that separably parameterizes the space of geometric variations due to different attributes (e.g., identity, expression, and viseme). Separability means that each of these attributes can be independently varied. A multilinear model can be estimated from a Cartesian product of examples (identities × expressions × visemes) with techniques from statistical analysis, but only after careful preprocessing of the geometric data set to secure one-to-one correspondence, to minimize cross-coupling artifacts, and to fill in any missing examples. Face Transfer offers new solutions to these problems and links the estimated model with a face-tracking algorithm to extract pose, expression, and viseme parameters.
RPU
Authors: Woop Sven , Schmittler Jörg , Slusallek Philipp
Published: November 2005

Recursive ray tracing is a simple yet powerful and general approach for accurately computing global light transport and rendering high quality images. While recent algorithmic improvements and optimized parallel software implementations have increased ray tracing performance to realtime levels, no compact and programmable hardware solution has been available yet.This paper describes the architecture and a prototype implementation of a single chip, fully programmable Ray Processing Unit (RPU). It combines the flexibility of general purpose CPUs with the efficiency of current GPUs for data parallel computations. This design allows for realtime ray tracing of dynamic scenes with programmable material, geometry, and illumination shaders.Although, running at only 66 MHz the prototype FPGA implementation already renders images at up to 20 frames per second, which in many cases beats the performance of highly optimized software running on multi-GHz desktop CPUs. The performance and efficiency of the proposed architecture is analyzed using a variety of benchmark scenes.
Linear rotation-invariant coordinates for meshes
Authors: Lipman Yaron , Sorkine Olga , Levin David , Cohen-Or Daniel
Published: November 2005

We introduce a rigid motion invariant mesh representation based on discrete forms defined on the mesh. The reconstruction of mesh geometry from this representation requires solving two sparse linear systems that arise from the discrete forms: the first system defines the relationship between local frames on the mesh, and the second encodes the position of the vertices via the local frames. The reconstructed geometry is unique up to a rigid transformation of the mesh. We define surface editing operations by placing user-defined constraints on the local frames and the vertex positions. These constraints are incorporated in the two linear reconstruction systems, and their solution produces a deformed surface geometry that preserves the local differential properties in the least-squares sense. Linear combination of shapes expressed with our representation enables linear shape interpolation that correctly handles rotations. We demonstrate the effectiveness of the new representation with various detail-preserving editing operators and shape morphing.
Mesh-based inverse kinematics
Authors: Sumner Robert W. , Zwicker Matthias , Gotsman Craig , Popović Jovan
Published: November 2005

The ability to position a small subset of mesh vertices and produce a
meaningful
overall deformation of the entire mesh is a fundamental task in mesh editing and animation. However, the class of meaningful deformations varies from mesh to mesh and depends on mesh kinematics, which prescribes valid mesh configurations, and a selection mechanism for choosing among them. Drawing an analogy to the traditional use of skeleton-based inverse kinematics for posing skeletons. we define
mesh-based inverse kinematics
as the problem of finding meaningful mesh deformations that meet specified vertex constraints.Our solution relies on example meshes to indicate the class of meaningful deformations. Each example is represented with a feature vector of deformation gradients that capture the affine transformations which individual triangles undergo relative to a reference pose. To pose a mesh, our algorithm efficiently searches among all meshes with specified vertex positions to find the one that is closest to some pose in a nonlinear span of the example feature vectors. Since the search is not restricted to the span of example shapes, this produces compelling deformations even when the constraints require poses that are different from those observed in the examples. Furthermore, because the span is formed by a nonlinear blend of the example feature vectors, the blending component of our system may also be used independently to pose meshes by specifying blending weights or to compute multi-way morph sequences.
Large mesh deformation using the volumetric graph Laplacian
Authors: Zhou Kun , Huang Jin , Snyder John , Liu Xinguo , Bao Hujun , Guo Baining , Shum Heung-Yeung
Published: November 2005

We present a novel technique for large deformations on 3D meshes using the volumetric graph Laplacian. We first construct a graph representing the volume inside the input mesh. The graph need not form a solid meshing of the input mesh's interior; its edges simply connect nearby points in the volume. This graph's Laplacian encodes volumetric details as the difference between each point in the graph and the average of its neighbors. Preserving these volumetric details during deformation imposes a volumetric constraint that prevents unnatural changes in volume. We also include in the graph points a short distance outside the mesh to avoid local self-intersections. Volumetric detail preservation is represented by a quadric energy function. Minimizing it preserves details in a least-squares sense, distributing error uniformly over the whole deformed mesh. It can also be combined with conventional constraints involving surface positions, details or smoothness, and efficiently minimized by solving a sparse linear system.We apply this technique in a 2D curve-based deformation system allowing novice users to create pleasing deformations with little effort. A novel application of this system is to apply nonrigid and exaggerated deformations of 2D cartoon characters to 3D meshes. We demonstrate our system's potential with several examples.
Robust moving least-squares fitting with sharp features
Authors: Fleishman Shachar , Cohen-Or Daniel , Silva Cláudio T.
Published: November 2005

We introduce a robust moving least-squares technique for reconstructing a piecewise smooth surface from a potentially noisy point cloud. We use techniques from robust statistics to guide the creation of the neighborhoods used by the moving least squares (MLS) computation. This leads to a conceptually simple approach that provides a unified framework for not only dealing with noise, but also for enabling the modeling of surfaces with sharp features.Our technique is based on a new robust statistics method for outlier detection: the forward-search paradigm. Using this powerful technique, we locally classify regions of a point-set to multiple outlier-free smooth regions. This classification allows us to project points on a locally smooth region rather than a surface that is smooth everywhere, thus defining a piecewise smooth surface and increasing the numerical stability of the projection operator. Furthermore, by treating the points across the discontinuities as outliers, we are able to define sharp features. One of the nice features of our approach is that it automatically disregards outliers during the surface-fitting phase.
Fast exact and approximate geodesics on meshes
Authors: Surazhsky Vitaly , Surazhsky Tatiana , Kirsanov Danil , Gortler Steven J. , Hoppe Hugues
Published: November 2005

The computation of geodesic paths and distances on triangle meshes is a common operation in many computer graphics applications. We present several practical algorithms for computing such geodesics from a source point to one or all other points efficiently. First, we describe an implementation of the exact "single source, all destination" algorithm presented by Mitchell, Mount, and Papadimitriou (MMP). We show that the algorithm runs much faster in practice than suggested by worst case analysis. Next, we extend the algorithm with a merging operation to obtain computationally efficient and accurate approximations with bounded error. Finally, to compute the shortest path between two given points, we use a lower-bound property of our approximate geodesic algorithm to efficiently prune the frontier of the MMP algorithm. thereby obtaining an exact solution even more quickly.
Interactive video cutout
Authors: Wang Jue , Bhat Pravin , Colburn R. Alex , Agrawala Maneesh , Cohen Michael F.
Published: November 2005

We present an interactive system for efficiently extracting foreground objects from a video. We extend previous min-cut based image segmentation techniques to the domain of video with four new contributions. We provide a novel painting-based user interface that allows users to easily indicate the foreground object across space and time. We introduce a hierarchical mean-shift preprocess in order to minimize the number of nodes that min-cut must operate on. Within the min-cut we also define new local cost functions to augment the global costs defined in earlier work. Finally, we extend 2D alpha matting methods designed for images to work with 3D video volumes. We demonstrate that our matting approach preserves smoothness across both space and time. Our interactive video cutout system allows users to quickly extract foreground objects from video sequences for use in a variety of applications including compositing onto new backgrounds and NPR cartoon style rendering.
Shell maps
Authors: Porumbescu Serban D. , Budge Brian , Feng Louis , Joy Kenneth I.
Published: November 2005

A shell map is a bijective mapping between shell space and texture space that can be used to generate small-scale features on surfaces using a variety of modeling techniques. The method is based upon the generation of an offset surface and the construction of a tetrahedral mesh that fills the space between the base surface and its offset. By identifying a corresponding tetrahedral mesh in texture space, the shell map can be implemented through a straightforward barycentric-coordinate map between corresponding tetrahedra. The generality of shell maps allows texture space to contain geometric objects, procedural volume textures, scalar fields, or other shell-mapped objects.
Color2Gray
Authors: Gooch Amy A. , Olsen Sven C. , Tumblin Jack , Gooch Bruce
Published: November 2005

Visually important image features often disappear when color images are converted to grayscale. The algorithm introduced here reduces such losses by attempting to preserve the salient features of the color image. The
Color2Gray
algorithm is a 3-step process: 1) convert RGB inputs to a perceptually uniform CIE
L*a*b*
color space, 2) use chrominance and luminance differences to create grayscale target differences between nearby image pixels, and 3) solve an optimization problem designed to selectively modulate the grayscale representation as a function of the chroma variation of the source image. The
Color2Gray
results offer viewers salient information missing from previous grayscale image creation methods.
A photon accurate model of the human eye
Authors: Deering Michael F.
Published: November 2005

A photon accurate model of individual cones in the human eye perceiving images on digital display devices is presented. Playback of streams of pixel video data is modeled as individual photon emission events from within the physical substructure of each display pixel. The thus generated electromagnetic wavefronts are refracted through a four surface model of the human cornea and lens, and diffracted at the pupil. The position, size, shape, and orientation of each of the five million photoreceptor cones in the retina are individually modeled by a new synthetic retina model. Photon absorption events map the collapsing wavefront to photon detection events in a particular cone, resulting in images of the photon counts in the retinal cone array. The custom rendering systems used to generate sequences of these images takes a number of optical and physical properties of the image formation into account, including wavelength dependent absorption in the tissues of the eye, and the motion blur caused by slight movement of the eye during a frame of viewing. The creation of this new model is part of a larger framework for understanding how changes to computer graphics rendering algorithms and changes in image display devices are related to artifacts visible to human viewers.
Action synopsis
Authors: Assa Jackie , Caspi Yaron , Cohen-Or Daniel
Published: November 2005

Illustrating motion in still imagery for the purpose of summary, abstraction and motion description is important for a diverse spectrum of fields, ranging from arts to sciences. In this paper, we introduce a method that produces an action synopsis for presenting motion in still images. The method carefully selects key poses based on an analysis of a skeletal animation sequence, to facilitate expressing complex motions in a single image or a small number of concise views. Our approach is to embed the high-dimensional motion curve in a low-dimensional Euclidean space, where the main characteristics of the skeletal action are kept. The lower complexity of the embedded motion curve allows a simple iterative method which analyzes the curve and locates significant points, associated with the key poses of the original motion. We present methods for illustrating the selected poses in an image as a means to convey the action. We applied our methods to a variety of motions of human actions given either as 3D animation sequences or as video clips, and generated images that depict their synopsis.