bluuebunny/crossref_metadata_2025 huggingface dataset:
Towards passive 6D reflectance field displays
Authors: Fuchs Martin , Raskar Ramesh , Seidel Hans-Peter , Lensch Hendrik P. A.
Published: August 2008

Traditional flat screen displays present 2D images. 3D and 4D displays have been proposed making use of lenslet arrays to shape a fixed outgoing light field for horizontal or bidirectional parallax. In this article, we present different designs of multi-dimensional displays which passively react to the light of the environment behind. The prototypes physically implement a reflectance field and generate different light fields depending on the incident illumination, for example light falling through a window. We discretize the incident light field using an optical system, and modulate it with a 2D pattern, creating a flat display which is view
and
illumination-dependent. It is free from electronic components. For distant light and a fixed observer position, we demonstrate a passive optical configuration which directly renders a 4D reflectance field in the real-world illumination behind it. We further propose an optical setup that allows for projecting out different angular distributions depending on the incident light direction. Combining multiple of these devices we build a display that renders a 6D experience, where the incident 2D illumination influences the outgoing light field, both in the spatial and in the angular domain. Possible applications of this technology are time-dependent displays driven by sunlight, object virtualization and programmable light benders / ray blockers without moving parts.
Simulating knitted cloth at the yarn level
Authors: Kaldor Jonathan M. , James Doug L. , Marschner Steve
Published: August 2008

Knitted fabric is widely used in clothing because of its unique and stretchy behavior, which is fundamentally different from the behavior of woven cloth. The properties of knits come from the nonlinear, three-dimensional kinematics of long, inter-looping yarns, and despite significant advances in cloth animation we still do not know how to simulate knitted fabric faithfully. Existing cloth simulators mainly adopt elastic-sheet mechanical models inspired by woven materials, focusing less on the model itself than on important simulation challenges such as efficiency, stability, and robustness. We define a new computational model for knits in terms of the motion of yarns, rather than the motion of a sheet. Each yarn is modeled as an inextensible, yet otherwise flexible, B-spline tube. To simulate complex knitted garments, we propose an implicit-explicit integrator, with yarn inextensibility constraints imposed using efficient projections. Friction among yarns is approximated using rigid-body velocity filters, and key yarn-yarn interactions are mediated by stiff penalty forces. Our results show that this simple model predicts the key mechanical properties of different knits, as demonstrated by qualitative comparisons to observed deformations of actual samples in the laboratory, and that the simulator can scale up to substantial animations with complex dynamic motion.
Motion-invariant photography
Authors: Levin Anat , Sand Peter , Cho Taeg Sang , Durand Frédo , Freeman William T.
Published: August 2008

Object motion during camera exposure often leads to noticeable blurring artifacts. Proper elimination of this blur is challenging because the blur kernel is unknown, varies over the image as a function of object velocity, and destroys high frequencies. In the case of motions along a 1D direction (e.g. horizontal) we show that these challenges can be addressed using a camera that moves during the exposure. Through the analysis of motion blur as space-time integration, we show that a parabolic integration (corresponding to constant sensor acceleration) leads to motion blur that is invariant to object velocity. Thus, a single deconvolution kernel can be used to remove blur and create sharp images of scenes with objects moving at different speeds, without requiring any segmentation and without knowledge of the object speeds. Apart from motion invariance, we prove that the derived parabolic motion preserves image frequency content nearly optimally. That is, while static objects are degraded relative to their image from a static camera, a reliable reconstruction of all moving objects within a given velocities range is made possible. We have built a prototype camera and present successful deblurring results over a wide variety of human motions.
Curved folding
Authors: Kilian Martin , Flöry Simon , Chen Zhonggui , Mitra Niloy J. , Sheffer Alla , Pottmann Helmut
Published: August 2008

Fascinating and elegant shapes may be folded from a single planar sheet of material without stretching, tearing or cutting, if one incorporates curved folds into the design. We present an optimization-based computational framework for design and digital reconstruction of surfaces which can be produced by curved folding. Our work not only contributes to applications in architecture and industrial design, but it also provides a new way to study the complex and largely unexplored phenomena arising in curved folding.
Freeform surfaces from single curved panels
Authors: Pottmann Helmut , Schiftner Alexander , Bo Pengbo , Schmiedhofer Heinz , Wang Wenping , Baldassini Niccolo , Wallner Johannes
Published: August 2008

Motivated by applications in architecture and manufacturing, we discuss the problem of covering a freeform surface by single curved panels. This leads to the new concept of semi-discrete surface representation, which constitutes a link between smooth and discrete surfaces. The basic entity we are working with is the developable strip model. It is the semi-discrete equivalent of a quad mesh with planar faces, or a conjugate parametrization of a smooth surface. We present a B-spline based optimization framework for efficient computing with D-strip models. In particular we study conical and circular models, which semi-discretize the network of principal curvature lines, and which enjoy elegant geometric properties. Together with geodesic models and cylindrical models they offer a rich source of solutions for surface panelization problems.
Green Coordinates
Authors: Lipman Yaron , Levin David , Cohen-Or Daniel
Published: August 2008

We introduce Green Coordinates for closed polyhedral cages. The coordinates are motivated by Green's third integral identity and respect both the vertices position and faces orientation of the cage. We show that Green Coordinates lead to space deformations with a shape-preserving property. In particular, in 2D they induce conformal mappings, and extend naturally to quasi-conformal mappings in 3D. In both cases we derive closed-form expressions for the coordinates, yielding a simple and fast algorithm for cage-based space deformation. We compare the performance of Green Coordinates with those of Mean Value Coordinates and Harmonic Coordinates and show that the advantage of the shape-preserving property is not achieved at the expense of speed or simplicity. We also show that the new coordinates extend the mapping in a natural analytic manner to the exterior of the cage, allowing the employment of partial cages.
Continuation methods for adapting simulated skills
Authors: Yin KangKang , Coros Stelian , Beaudoin Philippe , van de Panne Michiel
Published: August 2008

Modeling the large space of possible human motions requires scalable techniques. Generalizing from example motions or example controllers is one way to provide the required scalability. We present techniques for generalizing a controller for physics-based walking to significantly different tasks, such as climbing a large step up, or pushing a heavy object. Continuation methods solve such problems using a progressive sequence of problems that trace a path from an existing solved problem to the final desired-but-unsolved problem. Each step in the continuation sequence makes progress towards the target problem while further adapting the solution. We describe and evaluate a number of choices in applying continuation methods to adapting walking gaits for tasks involving interaction with the environment. The methods have been successfully applied to automatically adapt a regular cyclic walk to climbing a 65
cm
step, stepping over a 55
cm
sill, pushing heavy furniture, walking up steep inclines, and walking on ice. The continuation path further provides parameterized solutions to these problems.
A system for high-volume acquisition and matching of fresco fragments
Authors: Brown Benedict J. , Toler-Franklin Corey , Nehab Diego , Burns Michael , Dobkin David , Vlachopoulos Andreas , Doumas Christos , Rusinkiewicz Szymon , Weyrich Tim
Published: August 2008

Although mature technologies exist for acquiring images, geometry, and normals of small objects, they remain cumbersome and time-consuming for non-experts to employ on a large scale. In an archaeological setting, a practical acquisition system for routine use on
every
artifact and fragment would open new possibilities for archiving, analysis, and dissemination. We present an inexpensive system for acquiring all three types of information, and associated metadata, for small objects such as fragments of wall paintings. The acquisition system requires minimal supervision, so that a single, non-expert user can scan at least 10 fragments per hour. To achieve this performance, we introduce new algorithms to robustly and automatically align range scans, register 2-D scans to 3-D geometry, and compute normals from 2-D scans. As an illustrative application, we present a novel 3-D matching algorithm that efficiently searches for matching fragments using the scanned geometry.
3D-modeling by ortho-image generation from image sequences
Authors: Thormählen Thorsten , Seidel Hans-Peter
Published: August 2008

A semi-automatic approach is presented that enables the generation of a high-quality 3D model of a static object from an image sequence that was taken by a moving, uncalibrated consumer camera. A bounding box is placed around the object, and orthographic projections onto the sides of the bounding box are automatically generated out of the image sequence. These ortho-images can be imported as background maps in the orthographic views (e.g., the top, side, and front view) of any modeling package. Modelers can now use these ortho-images to guide their modeling by tracing the shape of the object over the ortho-images. This greatly improves the accuracy and efficiency of the manual modeling process. An additional advantage over existing semi-automatic systems is that modelers can use the modeling package that they are trained in and can thereby increase their productivity by applying the advanced modeling features the package offers. The results presented show that accurate 3D models can even be generated for translucent or specular surfaces, and the approach is therefore still applicable in cases where today's fully automatic image-based approaches or laser scanners would fail.
Where do people draw lines?
Authors: Cole Forrester , Golovinskiy Aleksey , Limpaecher Alex , Barros Heather Stoddart , Finkelstein Adam , Funkhouser Thomas , Rusinkiewicz Szymon
Published: August 2008

This paper presents the results of a study in which artists made line drawings intended to convey specific 3D shapes. The study was designed so that drawings could be registered with rendered images of 3D models, supporting an analysis of how well the locations of the artists' lines correlate with other artists', with current computer graphics line definitions, and with the underlying differential properties of the 3D surface. Lines drawn by artists in this study largely overlapped one another (75% are within 1mm of another line), particularly along the occluding contours of the object. Most lines that do not overlap contours overlap large gradients of the image intensity, and correlate strongly with predictions made by recent line drawing algorithms in computer graphics. 14% were not well described by any of the local properties considered in this study. The result of our work is a publicly available data set of aligned drawings, an analysis of where lines appear in that data set based on local properties of 3D models, and algorithms to predict where artists will draw lines for new scenes.
Real-time gradient-domain painting
Authors: McCann James , Pollard Nancy S.
Published: August 2008

We present an image editing program which allows artists to paint in the gradient domain with real-time feedback on megapixel-sized images. Along with a pedestrian, though powerful, gradient-painting brush and gradient-clone tool, we introduce an
edge brush
designed for edge selection and replay. These brushes, coupled with special blending modes, allow users to accomplish global lighting and contrast adjustments using only local image manipulations --- e.g. strengthening a given edge or removing a shadow boundary. Such operations would be tedious in a conventional intensity-based paint program and hard for users to get right in the gradient domain without real-time feedback. The core of our paint program is a simple-to-implement GPU multigrid method which allows integration of megapixel-sized full-color gradient fields at over 20 frames per second on modest hardware. By way of evaluation, we present example images produced with our program and characterize the iteration time and convergence rate of our integration method.
Markerless garment capture
Authors: Bradley Derek , Popa Tiberiu , Sheffer Alla , Heidrich Wolfgang , Boubekeur Tamy
Published: August 2008

A lot of research has recently focused on the problem of capturing the geometry and motion of garments. Such work usually relies on special markers printed on the fabric to establish temporally coherent correspondences between points on the garment's surface at different times. Unfortunately, this approach is tedious and prevents the capture of off-the-shelf clothing made from interesting fabrics.

In this paper, we describe a marker-free approach to capturing garment motion that avoids these downsides. We establish temporally coherent parameterizations between incomplete geometries that we extract at each timestep with a multiview stereo algorithm. We then fill holes in the geometry using a template. This approach, for the first time, allows us to capture the geometry and motion of unpatterned, off-the-shelf garments made from a range of different fabrics.
Automated generation of interactive 3D exploded view diagrams
Authors: Li Wilmot , Agrawala Maneesh , Curless Brian , Salesin David
Published: August 2008

We present a system for creating and viewing interactive exploded views of complex 3D models. In our approach, a 3D input model is organized into an
explosion graph
that encodes how parts explode with respect to each other. We present an automatic method for computing explosion graphs that takes into account part hierarchies in the input models and handles common classes of interlocking parts. Our system also includes an interface that allows users to interactively explore our exploded views using both direct controls and higher-level interaction modes.
Interactive visual editing of grammars for procedural architecture
Authors: Lipp Markus , Wonka Peter , Wimmer Michael
Published: August 2008

We introduce a real-time interactive visual editing paradigm for shape grammars, allowing the creation of rulebases from scratch without text file editing. In previous work, shape-grammar based procedural techniques were successfully applied to the creation of architectural models. However, those methods are text based, and may therefore be difficult to use for artists with little computer science background. Therefore the goal was to enable a visual work-flow combining the power of shape grammars with traditional modeling techniques. We extend previous shape grammar approaches by providing direct and persistent local control over the generated instances, avoiding the combinatorial explosion of grammar rules for modifications that should not affect all instances. The resulting visual editor is flexible: All elements of a complex state-of-the-art grammar can be created and modified visually.
Interview with David Harris, MTV New Media
Authors: Lee Newton , Harris David
Published: August 2008

David Harris was born in Puerto Rico, raised in Texas, and received his undergraduate degree in Film, Animation, and Video from the Rhode Island School of Design. He worked as the creative director for Love Advertising, producer for ADV Films, Inc. (one of America's leading animé companies), and lived in Paris for a year in between. In 2003, he relocated to Los Angeles to pursue his MFA from UCLA in Film, TV and Digital Media. His thesis project, HOWDOISAYTHIS.COM, was sponsored by mtvU and Cisco and won the 2007 SXSW Web Award for Best Student Site. Since launching HOWDOISAYTHIS.COM, Harris worked in the development think tank at Fox Television Studios before taking his current position at MTV New Media, where he is working on the Players project, Jackass World, and a number of interactive projects that are as exciting as they are secret. In the video interview, you will hear David's answers to the following questions:

1. You call yourself the "MacGyver" at MTV New Media. Could you elaborate on your role at MTV?

2. How does MTV New Media compete with MySpace and YouTube in reaching the MTV audience on the Internet?

3. What is your experience in working with the AFI Digital Content Lab?

4. What suggestions do you have that would make the Digital Content Lab more innovative, useful, and rewarding?

5. What is the innovation of the "Players" project that you are working on at the Digital Content Lab?

6. If you can do anything you want at MTV, what will you do?
People, places, and play
Authors: De Kort Yvonne A. W. , Ijsselsteijn Wijnand A.
Published: August 2008

Digital games frequently give rise to engaging and meaningful social interactions, both over the internet and in the real and tangible world of the gamer. This is the focus of the present paper, which explores digital gaming as a situated experience, shaped by socio-spatial contingencies. In particular we discuss how co-players, audience, and their spatial organization shape play and player experience and review supporting evidence for this. We present a framework describing social processes underlying situated social play experience and how these are shaped by the player the game's socio-spatial and media context. The core of this framework describes various 'sociality characteristics', and discusses these both in terms of co-located and mediated social game settings.
An architecture to easily produce adventure and movie games for the mobile scenario
Authors: Furini Marco
Published: August 2008

Simple and easy-to-play casual games are flooding the mobile gaming market and are best-sellers on the mobile game charts of several cellphone network operators. Most of the titles are mobile versions of videogames developed in the '80s and '90s, which were also very simple and easy-to-play. In this article we focus on adventure and movie games, a genre simple, easy-to-play, and very popular in the past. We propose a software architecture to easily produce full-motion adventure games for the mobile scenario, and thus potentially transform any modern cellphone into an adventure game console. The games are portable and protected against un-authorized usage. The feasibility of our approach is shown through a prototype player and an evaluation that shows the suitability of the proposed approach for the mobile scenario. The simplicity of our approach along with the ubiquity of modern cell-phones may bring new life to adventure games, which can also become an exciting genre for the current mobile gaming scenario.
Checking type safety of foreign function calls
Authors: Furr Michael , Foster Jeffrey S.
Published: August 2008

Foreign function interfaces (FFIs) allow components in different languages to communicate directly with each other. While FFIs are useful, they often require writing tricky low-level code and include little or no static safety checking, thus providing a rich source of hard-to-find programming errors. In this article, we study the problem of enforcing type safety across the OCaml-to-C FFI and the Java Native Interface (JNI). We present O-Saffire and J-Saffire, a pair of multilingual type inference systems that ensure C code that uses these FFIs accesses high-level data safely. Our inference systems userepresentational typesto model C's low-level view of OCaml and Java values, and singleton types to track integers, strings, memory offsets, and type tags through C. J-Saffire, our Java system, uses a polymorphic flow-insensitive, unification-based analysis. Polymorphism is important because it allows us to precisely model user-defined wrapper functions and the more than 200 JNI functions. O-Saffire, our OCaml system, uses a monomorphic flow-sensitive analysis because, while polymorphism is much less important for the OCaml FFI flow-sensitivity is critical to track conditional branches, which are used when pattern matching OCaml data in C. O-Saffire also tracks garbage collection information to ensure that local C pointers to the OCaml heap are registered properly, which is not necessary for the JNI. We have applied O-Saffire and J-Saffire to a set of benchmarks and found many bugs and questionable coding practices. These results suggest that static checking of FFIs can be a valuable tool in writing correct multilingual software.
Relations as an abstraction for BDD-based program analysis
Authors: Lhoták Ondřej , Hendren Laurie
Published: August 2008

In this article we present Jedd, a language extension to Java that supports a convenient way of programming with Binary Decision Diagrams (BDDs). The Jedd language abstracts BDDs as database-style relations and operations on relations, and provides static type rules to ensure that relational operations are used correctly.

The article provides a description of the Jedd language and reports on the design and implementation of the Jedd translator and associated runtime system. Of particular interest is the approach to assigning attributes from the high-level relations to physical domains in the underlying BDDs, which is done by expressing the constraints as a SAT problem and using a modern SAT solver to compute the solution. Further, a runtime system is defined that handles memory management issues and supports a browsable profiling tool for tuning the key BDD operations.

The motivation for designing Jedd was to support the development of interrelated whole program analyses based on BDDs. We have successfully used Jedd to build Paddle, a framework of context-sensitive program analyses, including points-to analysis and call graph construction, as well as several client analyses.
Beyond separation of duty
Authors: Li Ninghui , Wang Qihua
Published: August 2008

The process of introducing security controls into a sensitive task, which we call
secure task design
in this article, consists of two steps: high-level security policy design and low-level enforcement scheme design. A high-level security policy states an overall requirement for a sensitive task. One example of a high-level security policy is a separation of duty policy, which requires a task to be performed by a team of at least
k
users. Unlike low-level enforcement schemes such as security constraints in workflows, a separation of duty policy states a high-level requirement about the task without referring to individual steps in the task. While extremely important and widely used, separation of duty policies state only requirements on the number of users involved in the task and do not capture the requirements on these users' attributes. In this article, we introduce a novel algebra that enables the formal specification of high-level policies that combine requirements on users' attributes with requirements on the number of users motivated by separation of duty considerations. We give the syntax and semantics of the algebra and study algebraic properties of its operators. After that, we study potential mechanisms to enforce high-level policies specified in the algebra and a number of computational problems related to policy analysis and enforcement.
Matching algorithmic bounds for finding a Brouwer fixed point
Authors: Chen Xi , Deng Xiaotie
Published: August 2008

We prove a new discrete fixed point theorem for direction-preserving functions defined on integer points, based on a novel characterization of boundary conditions for the existence of fixed points. The theorem allows us to derive an improved algorithm for finding such a fixed point. We also develop a new lower bound proof technique. Together, they allow us to derive an asymptotic matching bound for the problem of finding a fixed point in a hypercube of any constantly bounded finite dimension.

Exploring a linkage with the approximation version of the continuous fixed point problem, we obtain asymptotic matching bounds for the complexity of the approximate Brouwer fixed point problem in the continuous case for Lipschitz functions. It settles a fifteen-years-old open problem of Hirsch, Papadimitriou, and Vavasis by improving both the upper and lower bounds.

Our characterization for the existence of a fixed point is also applicable to functions defined on nonconvex domains, which makes it a potentially useful tool for the design and analysis of algorithms for fixed points in general domains.
Computing correlated equilibria in multi-player games
Authors: Papadimitriou Christos H. , Roughgarden Tim
Published: August 2008

We develop polynomial-time algorithms for finding correlated equilibria—a well-studied notion of rationality that generalizes the Nash equilibrium—in a broad class of succinctly representable multiplayer games, encompassing graphical games, anonymous games, polymatrix games, congestion games, scheduling games, local effect games, as well as several generalizations. Our algorithm is based on a variant of the existence proof due to Hart and Schmeidler, and employs linear programming duality, the ellipsoid algorithm, Markov chain steady state computations, as well as application-specific methods for computing multivariate expectations over product distributions.

For anonymous games and graphical games of bounded tree-width, we provide a different polynomial-time algorithm for optimizing an arbitrary linear function over the set of correlated equilibria of the game. In contrast to our sweeping positive results for computing an arbitrary correlated equilibrium, we prove that optimizing over correlated equilibria is NP-hard in all of the other classes of games that we consider.
Characterization and Improvement of Time-Memory Trade-Off Based on Perfect Tables
Authors: Avoine Gildas , Junod Pascal , Oechslin Philippe
Published: August 2008

Cryptanalytic time-memory trade-offs have been studied for 25 years and have benefited from several improvements since the original work of Hellman. The ensuing variants definitely improve the original trade-off but their real impact has never been evaluated in practice. We fill this lack by analyzing the
perfect
form of classic tables, distinguished point-based tables, and rainbow tables. We especially provide a thorough analysis of the latter variant, whose performances have never been formally calculated yet. Our analysis leads to the concept of a
characteristic
that enables to measure the intrinsic quality of a trade-off. We finally introduce a new technique based on
checkpoints
that still reduces the cryptanalysis time by ruling out false alarms probabilistically. Our analysis yields the exact gain of this approach and establishes its efficiency when applied on rainbow tables.
Overview of the INEX 2007 Book Search track
Authors: Kazai Gabriella , Doucet Antoine
Published: August 2008

This paper provides an overview of the newly launched Book Search Track at INEX 2007 (BookSearch '07), its participants, tasks, book corpus, test topics and relevance assessments, as well as some results.
30
th
European Conference in Information Retrieval (ECIR 2008)
Authors: Ounis Iadh , Ruthven Ian , Plachouras Vassilis
Published: August 2008

The 30th European Conference on Information Retrieval Research (ECIR '08) took place in Glasgow, Scotland, on 30
th
March -- 3
rd
April, 2008 and was organised by the Department of Computing Science, University of Glasgow.
Some(what) grand challenges for information retrieval
Authors: Belkin Nicholas J.
Published: August 2008

Although we see the positive results of information retrieval research embodied throughout the Internet, on our computer desktops, and in many other aspects of daily life, at the same time we notice that people still have a wide variety of difficulties in finding information that is useful in resolving their problematic situations. This suggests that there still remain substantial challenges for research in IR. Already in 1988, on the occasion of receiving the ACM SIGIR Gerard Salton Award, Karen Spärck Jones suggested that substantial progress in information retrieval was likely only to come through addressing issues associated with users (actual or potential) of IR systems, rather than continuing IR research's almost exclusive focus on document representation and matching and ranking techniques. In recent years it appears that her message has begun to be heard, yet we still have relatively few substantive results that respond to it. In this paper, I identify and discuss a few challenges for IR research which fall within the scope of association with users, and which I believe, if properly addressed, are likely to lead to substantial increases in the usefulness, usability and pleasurability of information retrieval.
Exploiting semantic annotations in information retrieval
Authors: Alonso Omar , Zaragoza Hugo
Published: August 2008

The following report summarizes the highlights of the first workshop on exploiting semantic annotations in information retrieval (ESAIR '08). The workshop format included paper and demo presentations as well as breakout sessions and a panel discussion.
ECIR 2008 Workshop on Efficiency Issues on Information Retrieval
Authors: Blanco Roi , Silvestri Fabrizio
Published: August 2008

The goal of EIIR 2008, the first Workshop on Efficiency Issues in Information Retrieval, was to shed light on efficiency-related issues of modern high-scale information retrieval (IR), e.g., Web, distributed technologies, peer to peer architectures and also new IR environments such as desktop search, enterprise/expert search, mobile devices, etc. In addition, the workshop aimed at fostering collaboration between different research groups in this area.
Adversarial Information Retrieval on the Web (AIRWeb 2007)
Authors: Castillo Carlos , Chellapilla Kumar , Davison Brian D.
Published: August 2008

The ubiquitous use of search engines to discover and access Web content shows clearly the success of information retrieval algorithms. However, unlike controlled collections, the vast majority of Web pages lack an authority asserting their quality. This openness of the Web has been the key to its rapid growth and success, but this openness is also a major source of new adversarial challenges for information retrieval methods.
Cooperative cross layer MAC protocols for directional antenna ad hoc networks
Authors: Munari Andrea , Rossetto Francesco , Zorzi Michele
Published: August 2008

This paper deals with some of the main problems that affect directional antenna ad hoc networks, especially deafness and collisions. By means of a thorough study of the possibilities offered by an antenna array, we propose cooperation as a novel technique for deafness suppression, together with a low complexity multiuser detector and a collision avoidance algorithm tailored for this type of networks. Building on these ideas, a new family of protocols (called Cooperative MAC) is designed. A lower and an upper bound on its performance are compared with the Circular RTS/CTS protocol (CRCM), a known benchmark in this field. We are able to achieve interesting improvements.
A system for secure verification of location claims
Authors: Graham Michelle
Published: August 2008

Location information is playing a larger and larger part within services in today's world and for this reason, users require some way of providing their location which can be trusted by third parties. Until recently, GPS has been accepted as an adequate solution but with user privacy and information security becoming more sensitive issues, a new method of gathering trustworthy location information must be developed. We believe that enlisting the aid of neighbouring devices, while employing proper security measures, provides the basis of such a method, and propose one such method of our own, based upon distance-bounding protected by security protocols.
Report on the First MobiSys ACM workshop on mobile opportunistic networking (MobiOpp'07)
Authors: Conti Marco , Gerla Mario , Passarella Andrea , Pau Giovanni
Published: August 2008

The aim of the MobiOpp workshop series is to bring together the (increasing) community of researchers working in the area of Mobile Opportunistic Networking. The first workshop in this series, MobiOpp'07, was held on June 11, 2007 in San Juan, Puerto Rico (USA) in conjunction with MobiSys 2007. MobiOpp'07 was sponsored by ACM SIGMOBILE and jointly organized by the IIT Institute of the Italian National Research Council (CNR) and by the UCLA Network Research Laboratory.
The internet diary
Authors: Vogt Christian , Perkins Charles E.
Published: August 2008

This is the first in a new series of reports on selected activities from the Internet Engineering and Research Task Forces, IETF and IRTF. This issue focuses on IP mobility, routing in mobile ad-hoc networks, routing scalability, and transition from IP version 4 to version 6. Principal in IP mobility is the impending publication of the NETLMM working group's Proxy Mobile IPv6 protocol, as well as the creation of the new MEXT working group for maintenance and extension of (non-proxy) Mobile-IPv6-based protocols. Two second-generation routing protocols for ad-hoc networks are being completed in the MANET working group. Engineering of IP auto-configuration mechanisms for ad-hoc networks has stalled in the Autoconf working group due to the inappropriateness of the subnet-oriented IP addressing model in less structured mobile ad-hoc networks. Routing scalability is the main focus of the Routing research group from IRTF. The group is set to develop a recommendation on how to mitigate the critical growth in routing table size and update frequency. The v6ops working group is redesigning its IPv4/IPv6 protocol translator to provide operators with an urgently needed tool for interworking between IP versions.
Technology-Driven, Highly-Scalable Dragonfly Topology
Authors: Kim John , Dally Wiliam J. , Scott Steve , Abts Dennis
Published: August 2008

Evolving technology and increasing pin-bandwidth motivate the use of high-radix routers to reduce the diameter, latency, and cost of interconnection networks. High-radix networks, however, require longer cables than their low-radix counterparts. Because cables dominate network cost, the number of cables, and particularly the number of long, global cables should be minimized to realize an efficient network. In this paper, we introduce the dragonfly topology which uses a group of high-radix routers as a virtual router to increase the effective radix of the network. With this organization, each minimally routed packet traverses at most one global channel. By reducing global channels, a dragonfly reduces cost by 20% compared to a flattened butterfly and by 52% compared to a folded Clos network in configurations with ≥ 16K nodes.We also introduce two new variants of global adaptive routing that enable load-balanced routing in the dragonfly. Each router in a dragonfly must make an adaptive routing decision based on the state of a global channel connected to a different router. Because of the indirect nature of this routing decision, conventional adaptive routing algorithms give degraded performance. We introduce the use of selective virtual-channel discrimination and the use of credit round-trip latency to both sense and signal channel congestion. The combination of these two methods gives throughput and latency that approaches that of an ideal adaptive routing algorithm.
Globally-Synchronized Frames for Guaranteed Quality-of-Service in On-Chip Networks
Authors: Lee Jae W. , Ng Man Cheuk , Asanovic Krste
Published: August 2008

Future chip multiprocessors (CMPs) may have hundreds to thousands of threads competing to access shared resources, and will require quality-of-service (QoS) support to improve system utilization. Although there has been significant work in QoS support within resources such as caches and memory controllers, there has been less attention paid to QoS support in the multi-hop on-chip networks that will form an important component in future systems. In this paper we introduce Globally-Synchronized Frames (GSF), a framework for providing guaranteed QoS in on-chip networks in terms of minimum bandwidth and a maximum delay bound. The GSF framework can be easily integrated in a conventional virtual channel (VC) router without significantly increasing the hardware complexity. We rely on a fast barrier network, which is feasible in an on-chip environment, to efficiently implement GSF. Performance guarantees are verified by both analysis and simulation. According to our simulations, all concurrent flows receive their guaranteed minimum share of bandwidth in compliance with a given bandwidth allocation. The average throughput degradation of GSF on a 8x8 mesh network is within 10% compared to the conventional best-effort VC router in most cases.
Using Hardware Memory Protection to Build a High-Performance, Strongly-Atomic Hybrid Transactional Memory
Authors: Baugh Lee , Neelakantam Naveen , Zilles Craig
Published: August 2008

We demonstrate how fine-grained memory protection can be used in support of transactional memory systems: first showing how a software transactional memory system (STM) can be made strongly atomic by using memory protection on transactionally-held state, then showing how such a strongly-atomic STM can be used with a bounded hardware TM system to build a hybrid TM system in which zero-overhead hardware transactions may safely run concurrently with potentially-conflicting software transactions. We experimentally demonstrate how this hybrid TM organization avoids the common-case overheads associated with previous hybrid TM proposals, achieving performance rivaling an unbounded HTM system without the hardware complexity of ensuring completion of arbitrary transactions in hardware. As part of our findings, we identify key policies regarding contention management within and across the hardware and software TM components that are key to achieving robust performance with a hybrid TM.
Flexible Decoupled Transactional Memory Support
Authors: Shriraman Arrvindh , Dwarkadas Sandhya , Scott Michael L.
Published: August 2008

A high-concurrency transactional memory (TM) implementation needs to track concurrent accesses, buffer speculative updates, and manage conflicts. We present a system, FlexTM (FLEXible Transactional Memory), that coordinates four decoupled hardware mechanisms: read and write signatures, which summarize per-thread access sets; per-thread conflict summary tables (CSTs), which identify the threads with which conflicts have occurred; Programmable Data Isolation, which maintains speculative updates in the local cache and employs a thread-private buffer (in virtual memory) in the rare event of overflow; and Alert-On-Update, which selectively notifies threads about coherence events. All mechanisms are software-accessible, to enable virtualization and to support transactions of arbitrary length. FlexTM allows software to determine when to manage conflicts (either eagerly or lazily), and to employ a variety of conflict management and commit protocols. We describe an STM-inspired protocol thatuses CSTs to manage conflicts in a distributed manner (no global arbitration) and allows parallel commits. In experiments with a prototype on Simics/GEMS, FlexTM exhibits 5x speedup over high-quality software TM, with no loss in policy flexibility. Its distributed commit protocol is also more efficient than a central hardware manager. Our results highlight the importance of flexibility in determining when to manage conflicts: lazy maximizes concurrency and helps to ensure forward progress while eager provides better overall utilization in a multi-programmed system.
Corona
Authors: Vantrease Dana , Schreiber Robert , Monchiero Matteo , McLaren Moray , Jouppi Norman P. , Fiorentino Marco , Davis Al , Binkert Nathan , Beausoleil Raymond G. , Ahn Jung Ho
Published: August 2008

We expect that many-core microprocessors will push performance per chip from the 10 gigaflop to the 10 teraflop range in the coming decade. To support this increased performance, memory and inter-core bandwidths will also have to scale by orders of magnitude. Pin limitations, the energy cost of electrical signaling, and the non-scalability of chip-length global wires are significant bandwidth impediments. Recent developments in silicon nanophotonic technology have the potential to meet these off- and on-stack bandwidth requirements at acceptable power levels. Corona is a 3D many-core architecture that uses nanophotonic communication for both inter-core communication and off-stack communication to memory or I/O devices. Its peak floating-point performance is 10 teraflops. Dense wavelength division multiplexed optically connected memory modules provide 10 terabyte per second memory bandwidth. A photonic crossbar fully interconnects its 256 low-power multithreaded cores at 20 terabyte per second bandwidth. We have simulated a 1024 thread Corona system running synthetic benchmarks and scaled versions of the SPLASH-2 benchmark suite. We believe that in comparison with an electrically-connected many-core alternative that uses the same on-stack interconnect power, Corona can provide 2 to 6 times more performance on many memory intensive workloads, while simultaneously reducing power.
Trading off Cache Capacity for Reliability to Enable Low Voltage Operation
Authors: Wilkerson Chris , Gao Hongliang , Alameldeen Alaa R. , Chishti Zeshan , Khellah Muhammad , Lu Shih-Lien
Published: August 2008

One of the most effective techniques to reduce a processor’s power consumption is to reduce supply voltage. However, reducing voltage in the context of manufacturing-induced parameter variations cancause many types of memory circuits to fail. As a result, voltage scaling is limited by a minimum voltage, often called Vccmin, beyond which circuits may not operate reliably. Large memory structures (e.g., caches) typically set Vccmin for the whole processor. In this paper, we propose two architectural techniques that enable microprocessor caches (L1and L2), to operate at low voltages despite very high memory cell failure rates. The Word-disable scheme combines two consecutive cache lines, to form a single cache line where only non-failing words are used. The Bit-fix scheme uses a quarter of the ways in a cache set to store positions and fix bits for failing bits in other ways of the set. During high voltage operation, both schemes allow use of the entire cache. During low voltage operation, they sacrifice cache capacity by 50% and 25%, respectively, to reduce Vccmin below 500mV. Compared to current designs with a Vccmin of 825mV, our schemes enable a 40% voltage reduction, which reduces power by 85% and energy per instruction (EPI) by 53%
Virtual Circuit Tree Multicasting
Authors: Jerger Natalie Enright , Peh Li-Shiuan , Lipasti Mikko
Published: August 2008

Current state-of-the-art on-chip networks provide efficiency, high throughput, and low latency for one-to-one (unicast) traffic. The presence of one-to-many (multicast) or one-to-all (broadcast) traffic can significantly degrade the performance of these designs, since they rely on multiple unicasts to provide one-to-many communication. This results in a burst of packets from a single source and is a very inefficient way of performing multicast and broadcast communication. This inefficiency is compounded by the proliferation of architectures and coherence protocols that require multicast and broadcast communication. In this paper, we characterize a wide array of on-chip communication scenarios that benefit from hardware multicast support. We propose Virtual Circuit Tree Multicasting (VCTM) and present a detailed multicast router design that improves network performance by up to 90\% while reducing network activity (hence power) by up to 53%.Our VCTM router is flexible enough to improve interconnect performance for a broad spectrum of multicasting scenarios,and achieves these benefits with straightforward and inexpensive extensions to a state-of-the-art packet-switched router.
Rerun
Authors: Hower Derek R. , Hill Mark D.
Published: August 2008

Multiprocessor deterministic replay has many potential uses in the era of multicore computing, including enhanced debugging, fault tolerance, and intrusion detection. While sources of nondeterminism in a uniprocessor can be recorded efficiently in software, it seems likely that hardware support will be needed in a multiprocessor environment where the outcome of memory races must also be recorded.We develop a memory race recording mechanism, called Rerun, that uses small hardware state (~166 bytes/core), writes a small race log (~4 bytes/kilo- instruction), and operates well as the number of cores per system scales (e.g., to16cores). Rerun exploits the dual of conventional wisdom in race recording: Rather than record information about individual memory accesses that conflict, we record how long a thread executes without conflicting with other threads. In particular, Rerun passively creates atomic episodes. Each episode is a dynamic instruction sequence that a thread happens to execute without interacting with other threads. Rerun uses Lamport Clocks to order episodes and enable replay of an equivalent execution.
DeLorean
Authors: Montesinos Pablo , Ceze Luis , Torrellas Josep
Published: August 2008

Support for deterministic replay of multithreaded execution can greatly help in finding concurrency bugs. For highest effectiveness, replay schemes should (i) record at production-run speed, (ii) keep their logging requirements minute, and (iii) replay at a speed similar to that of the initial execution. In this paper, we propose a new substrate for deterministic replay that provides substantial advances along these axes. In our proposal, processors execute blocks of instructions atomically, as in transactional memory or speculative multithreading, and the system only needs to record the commit order of these blocks. We call our scheme DeLorean. Our results show that DeLorean records execution at a speed similar to that of Release Consistency (RC) execution and replays at about 82% of its speed. In contrast, most current schemes only record at the speed of Sequential Consistency (SC) execution. Moreover, DeLorean only needs 7.5% of the log size needed by a state-of-the-art scheme. Finally, DeLorean can be configured to need only 0.6% of the log size of the state-of-the-art scheme at the cost of recording at 86% of RC’s execution speed — still faster than SC. In this configuration, the log of an 8-processor 5-GHz machine is estimated to be only about 20GB per day.