bluuebunny/crossref_metadata_2025 huggingface dataset:
Handle-aware isolines for scalable shape editing
Authors: Au Oscar Kin-Chung , Fu Hongbo , Tai Chiew-Lan , Cohen-Or Daniel
Published: September 2007

Handle-based mesh deformation is essentially a nonlinear problem. To allow scalability, the original deformation problem can be approximately represented by a compact set of control variables. We show the direct relation between the locations of handles on the mesh and the local rigidity under deformation, and introduce the notion of
handle-aware rigidity
. Then, we present a reduced model whose control variables are intelligently distributed across the surface, respecting the rigidity information and the geometry. Specifically, for each handle, the control variables are the transformations of the isolines of a harmonic scalar field representing the deformation propagation from that handle. The isolines constitute a virtual skeletal structure similar to the bones in skinning deformation, thus correctly capturing the low-frequency shape deformation. To interpolate the transformations from the isolines to the original mesh, we design a method which is local, linear and geometry-dependent. This novel interpolation scheme and the transformation-based reduced domain allow each iteration of the nonlinear solver to be fully computed over the reduced domain. This makes the per-iteration cost dependent on only the number of isolines and enables compelling deformation of highly detailed shapes at interactive rates. In addition, we show how the handle-driven isolines provide an efficient means for deformation transfer without full shape correspondence.
Image-based procedural modeling of facades
Authors: Müller Pascal , Zeng Gang , Wonka Peter , Van Gool Luc
Published: September 2007

This paper describes algorithms to automatically derive 3D models of high visual quality from single facade images of arbitrary resolutions. We combine the procedural modeling pipeline of shape grammars with image analysis to derive a meaningful hierarchical facade subdivision. Our system gives rise to three exciting applications: urban reconstruction based on low resolution oblique aerial imagery, reconstruction of facades based on higher resolution ground-based imagery, and the automatic derivation of shape grammar rules from facade images to build a rule base for procedural modeling technology.
VideoTrace
Authors: van den Hengel Anton , Dick Anthony , Thormählen Thorsten , Ward Ben , Torr Philip H. S.
Published: September 2007

VideoTrace is a system for interactively generating realistic 3D models of objects from video---models that might be inserted into a video game, a simulation environment, or another video sequence. The user interacts with VideoTrace by tracing the shape of the object to be modelled over one or more frames of the video. By interpreting the sketch drawn by the user in light of 3D information obtained from computer vision techniques, a small number of simple 2D interactions can be used to generate a realistic 3D model. Each of the sketching operations in VideoTrace provides an intuitive and powerful means of modelling shape from video, and executes quickly enough to be used interactively. Immediate feedback allows the user to model rapidly those parts of the scene which are of interest and to the level of detail required. The combination of automated and manual reconstruction allows VideoTrace to model parts of the scene not visible, and to succeed in cases where purely automated approaches would fail.
Direct manipulation of subdivision surfaces on GPUs
Authors: Zhou Kun , Huang Xin , Xu Weiwei , Guo Baining , Shum Heung-Yeung
Published: September 2007

We present an algorithm for interactive deformation of subdivision surfaces, including displaced subdivision surfaces and subdivision surfaces with geometric textures. Our system lets the user directly manipulate the surface using freely-selected surface points as handles. During deformation the control mesh vertices are automatically adjusted such that the deforming surface satisfies the handle position constraints while preserving the original surface shape and details. To best preserve surface details, we develop a gradient domain technique that incorporates the handle position constraints and detail preserving objectives into the deformation energy. For displaced subdivision surfaces and surfaces with geometric textures, the deformation energy is highly nonlinear and cannot be handled with existing iterative solvers. To address this issue, we introduce a shell deformation solver, which replaces each numerically unstable iteration step with two stable mesh deformation operations. Our deformation algorithm only uses local operations and is thus suitable for GPU implementation. The result is a real-time deformation system running orders of magnitude faster than the state-of-the-art multigrid mesh deformation solver. We demonstrate our technique with a variety of examples, including examples of creating visually pleasing character animations in real-time by driving a subdivision surface with motion capture data.
Capturing and viewing gigapixel images
Authors: Kopf Johannes , Uyttendaele Matt , Deussen Oliver , Cohen Michael F.
Published: September 2007

We present a system to capture and view "Gigapixel images": very high resolution, high dynamic range, and wide angle imagery consisting of several billion pixels each. A specialized camera mount, in combination with an automated pipeline for alignment, exposure compensation, and stitching, provide the means to acquire Gigapixel images with a standard camera and lens. More importantly, our novel viewer enables exploration of such images at interactive rates over a network, while dynamically and smoothly interpolating the projection between perspective and curved projections, and simultaneously modifying the tone-mapping to ensure an optimal view of the portion of the scene being viewed.
Image upsampling via imposed edge statistics
Authors: Fattal Raanan
Published: September 2007

In this paper we propose a new method for upsampling images which is capable of generating sharp edges with reduced input-resolution grid-related artifacts. The method is based on a statistical edge dependency relating certain edge features of two different resolutions, which is generically exhibited by real-world images. While other solutions assume some form of smoothness, we rely on this distinctive edge dependency as our prior knowledge in order to increase image resolution. In addition to this relation we require that intensities are conserved; the output image must be identical to the input image when downsampled to the original resolution. Altogether the method consists of solving a constrained optimization problem, attempting to impose the correct edge relation and conserve local intensities with respect to the low-resolution input image. Results demonstrate the visual importance of having such edge features properly matched, and the method's capability to produce images in which sharp edges are successfully reconstructed.
Joint bilateral upsampling
Authors: Kopf Johannes , Cohen Michael F. , Lischinski Dani , Uyttendaele Matt
Published: September 2007

Image analysis and enhancement tasks such as tone mapping, colorization, stereo depth, and photomontage, often require computing a solution (e.g., for exposure, chromaticity, disparity, labels) over the pixel grid. Computational and memory costs often require that a smaller solution be run over a downsampled image. Although general purpose upsampling methods can be used to interpolate the low resolution solution to the full resolution, these methods generally assume a smoothness prior for the interpolation.

We demonstrate that in cases, such as those above, the available high resolution input image may be leveraged as a prior in the context of a joint bilateral upsampling procedure to produce a better high resolution solution. We show results for each of the applications above and compare them to traditional upsampling methods.
Bubbling and frothing liquids
Authors: Cleary Paul W. , Pyo Soon Hyoung , Prakash Mahesh , Koo Bon Ki
Published: September 2007

We present a discrete particle based method capable of creating very realistic animations of bubbles in fluids. It allows for the generation (nucleation) of bubbles from gas dissolved in the fluid, the motion of the discrete bubbles including bubble collisions and drag interactions with the liquid which could be undergoing complex free surface motion, the formation and motion of coupled foams and the final dissipation of bubbles. This allows comprehensive simulations of dynamic bubble behavior. The underlying fluid simulation is based on the mesh-free Smoothed Particle Hydrodynamics method. Each particle representing the liquid contains an amount of dissolved gas. Gas is transferred from the continuum fluid model to the discrete bubble model at nucleation sites on the surface of solid bodies. The rate of gas transport to the nucleation sites controls the rate of bubble generation, producing very natural time variations in bubble numbers. Rising bubbles also grow by gathering more gas from the surrounding liquid as they move. This model contains significant bubble scale physics and allows, in principle, the capturing of many important processes that cannot be directly modeled by traditional methods. The method is used here to realistically animate the pouring of a glass of beer, starting with a stream of fresh beer entering the glass, the formation of a dense cloud of bubbles, which rise to create a good head as the beer reaches the top of the glass.
Simulation of bubbles in foam with the volume control method
Authors: Kim Byungmoon , Liu Yingjie , Llamas Ignacio , Jiao Xiangmin , Rossignac Jarek
Published: September 2007

Liquid and gas interactions often produce bubbles that stay for a long time without bursting on the surface, making a dry foam structure. Such long lasting bubbles simulated by the level set method can suffer from a small but steady volume error that accumulates to a visible amount of volume change. We propose to address this problem by using the volume control method. We track the volume change of each connected region, and apply a carefully computed divergence that compensates undesired volume changes. To compute the divergence, we construct a mathematical model of the volume change, choose control strategies that regulate the modeled volume error, and establish methods to compute the control gains that provide robust and fast reduction of the volume error, and (if desired) the control of how the volume changes over time.
A fast variational framework for accurate solid-fluid coupling
Authors: Batty Christopher , Bertails Florence , Bridson Robert
Published: September 2007

Physical simulation has emerged as a compelling animation technique, yet current approaches to coupling simulations of fluids and solids with irregular boundary geometry are inefficient or cannot handle some relevant scenarios robustly. We propose a new variational approach which allows robust and accurate solution on relatively coarse Cartesian grids, allowing possibly orders of magnitude faster simulation. By rephrasing the classical pressure projection step as a kinetic energy minimization, broadly similar to modern approaches to rigid body contact, we permit a robust coupling between fluid and arbitrary solid simulations that always gives a well-posed symmetric positive semi-definite linear system. We provide several examples of efficient fluid-solid interaction and rigid body coupling with sub-grid cell flow. In addition, we extend the framework with a new boundary condition for free-surface flow, allowing fluid to separate naturally from solids.
Computational time-lapse video
Authors: Bennett Eric P. , McMillan Leonard
Published: September 2007

We present methods for generating novel time-lapse videos that address the inherent sampling issues that arise with traditional photographic techniques. Starting with video-rate footage as input, our post-process downsamples the source material into a time-lapse video and provides user controls for retaining, removing, and resampling events. We employ two techniques for selecting and combining source frames to form the output. First, we present a non-uniform sampling method, based on dynamic programming, which optimizes the sampling of the input video to match the user's desired duration and visual objectives. We present multiple error metrics for this optimization, each resulting in different sampling characteristics. To complement the non-uniform sampling, we present the
virtual shutter
, a non-linear filtering technique that synthetically extends the exposure time of time-lapse frames.
Real-time edge-aware image processing with the bilateral grid
Authors: Chen Jiawen , Paris Sylvain , Durand Frédo
Published: September 2007

We present a new data structure---the
bilateral grid
, that enables fast edge-aware image processing. By working in the bilateral grid, algorithms such as bilateral filtering, edge-aware painting, and local histogram equalization become simple manipulations that are both local and independent. We parallelize our algorithms on modern GPUs to achieve real-time frame rates on high-definition video. We demonstrate our method on a variety of applications such as image editing, transfer of photographic look, and contrast enhancement of medical images.
Construction and optimal search of interpolated motion graphs
Authors: Safonova Alla , Hodgins Jessica K.
Published: September 2007

Many compelling applications would become feasible if novice users had the ability to synthesize high quality human motion based only on a simple sketch and a few easily specified constraints. We approach this problem by representing the desired motion as an interpolation of two time-scaled paths through a motion graph. The graph is constructed to support interpolation and pruned for efficient search. We use an anytime version of
A*
search to find a globally optimal solution in this graph that satisfies the user's specification. Our approach retains the natural transitions of motion graphs and the ability to synthesize physically realistic variations provided by interpolation. We demonstrate the power of this approach by synthesizing optimal or near optimal motions that include a variety of behaviors in a single motion.
Simulating biped behaviors from human motion data
Authors: Sok Kwang Won , Kim Manmyung , Lee Jehee
Published: September 2007

Physically based simulation of human motions is an important issue in the context of computer animation, robotics and biomechanics. We present a new technique for allowing our physically-simulated planar biped characters to imitate human behaviors. Our contribution is twofold. We developed an optimization method that transforms any (either motion-captured or kinematically synthesized) biped motion into a physically-feasible, balance-maintaining simulated motion. Our optimization method allows us to collect a rich set of training data that contains stylistic, personality-rich human behaviors. Our controller learning algorithm facilitates the creation and composition of robust dynamic controllers that are learned from training data. We demonstrate a planar articulated character that is dynamically simulated in real time, equipped with an integrated repertoire of motor skills, and controlled interactively to perform desired motions.
Efficient symbolic differentiation for graphics applications
Authors: Guenter Brian
Published: September 2007

Functions with densely interconnected expression graphs, which arise in computer graphics applications such as dynamics, space-time optimization, and PRT, can be difficult to efficiently differentiate using existing symbolic or automatic differentiation techniques. Our new algorithm,
D*
, computes efficient symbolic derivatives for these functions by symbolically executing the expression graph at compile time to eliminate common subexpressions and by exploiting the special nature of the graph that represents the derivative of a function. This graph has a sum of products form; the new algorithm computes a factorization of this derivative graph along with an efficient grouping of product terms into subexpressions. For the problems in our test suite
D*
generates symbolic derivatives which are up to 4.6 x 10
3
times faster than those computed by the symbolic math program Mathematica and up to 2.2x10
5
times faster than the non-symbolic automatic differentiation program CppAD. In some cases the
D*
derivatives rival the best manually derived solutions.
The axiomatic translation principle for modal logic
Authors: Schmidt Renate A. , Hustadt Ullrich
Published: September 2007

In this paper we present a translation principle, called the
axiomatic translation
, for reducing propositional modal logics with background theories, including triangular properties such as transitivity, Euclideanness and functionality, to decidable fragments of first-order logic. The goal of the axiomatic translation principle is to find simplified theories, which capture the inference problems in the original theory, but in a way that can be readily automated and is easier to deal with by existing (first-order) theorem provers than the standard translation. The principle of the axiomatic translation is conceptually very simple and can be almost completely automated. Soundness is automatic under reasonable assumptions, general decidability results can be stated and termination of ordered resolution is easily achieved. The non-trivial part of the approach is proving completeness. We prove results of completeness, decidability, model generation, the small model property and the interpolation property for a number of common and less common modal logics. We also present results of experiments with a number of first-order logic theorem provers which are very encouraging.
Probabilistic abstraction for model checking
Authors: Laplante Sophie , Lassaigne Richard , Magniez Frédéric , Peyronnet Sylvain , de Rougemont Michel
Published: September 2007

The goal of model checking is to verify the correctness of a given program, on all its inputs. The main obstacle, in many cases, is the intractably large size of the program's transition system. Property testing is a randomized method to verify whether some fixed property holds on individual inputs, by looking at a small random part of that input. We join the strengths of both approaches by introducing a new notion of probabilistic abstraction, and by extending the framework of model checking to include the use of these abstractions.

Our abstractions map transition systems associated with large graphs to small transition systems associated with small random subgraphs. This reduces the original transition system to a family of small, even constant-size, transition systems. We prove that with high probability, “sufficiently” incorrect programs will be rejected (ε-robustness). We also prove that under a certain condition (exactness), correct programs will never be rejected (soundness).

Our work applies to programs for graph properties such as bipartiteness,
k
-colorability, or any ∃∀ first order graph properties. Our main contribution is to show how to apply the ideas of property testing to syntactic programs for such properties. We give a concrete example of an abstraction for a program for bipartiteness. Finally, we show that the relaxation of the test alone does not yield transition systems small enough to use the standard model checking method. More specifically, we prove, using methods from communication complexity, that the OBDD size remains exponential for approximate bipartiteness.
First-order queries on structures of bounded degree are computable with constant delay
Authors: Durand Arnaud , Grandjean Etienne
Published: September 2007

A relational structure is
d
-degree-bounded, for some integer
d
, if each element of the domain belongs to at most
d
tuples. In this paper, we revisit the complexity of the evaluation problem of not necessarily Boolean first-order (
FO
) queries over
d
-degree-bounded structures. Query evaluation is considered here as a dynamical process. We prove that any
FO
query on
d
-degree-bounded structures belongs to the complexity class constant-Delay

lin

, that is, can be computed by an algorithm that has two separate parts: it has a precomputation step of time linear in the size of the structure and then, it outputs all solutions (i.e., tuples that satisfy the formula) one by one with a constant delay (i.e., depending on the size of the formula only) between each. Seen as a global process, this implies that queries on
d
-degree-bounded structures can be evaluated in total time
f
(|φ|).(|
S
| + |φ(
S
)|) and space
g
(|φ|).|
S
| where
S
is the structure, φ is the formula, φ(
S
) is the result of the query and
f
,
g
are some fixed functions.

Among other things, our results generalize a result of Seese on the data complexity of the model-checking problem for
d
-degree-bounded structures. Besides, the originality of our approach compared to related results is that it does not rely on the Hanf's model-theoretic technique and is simple and informative since it essentially rests on a quantifier elimination method.
A sequent calculus and a theorem prover for standard conditional logics
Authors: Olivetti Nicola , Pozzato Gian Luca , Schwind Camilla B.
Published: September 2007

In this paper we present a cut-free sequent calculus, called SeqS, for some standard conditional logics. The calculus uses labels and transition formulas and can be used to prove decidability and space complexity bounds for the respective logics. We also show that these calculi can be the base for uniform proof systems. Moreover, we present CondLean, a theorem prover in Prolog for these calculi.
Probabilistic interval XML
Authors: Hung Edward , Getoor Lise , Subrahmanian V. S.
Published: September 2007

Interest in XML databases has been expanding rapidly over the last few years. In this paper, we study the problem of incorporating probabilistic information into XML databases. We propose the Probabilistic Interval XML (

PIXML

for short) data model in this paper. Using this data model, users can express probabilistic information within XML markups. In addition, we provide two alternative formal model-theoretic semantics for

PIXML

data. The first semantics is a “global” semantics which is relatively intuitive, but is not directly amenable to computation. The second semantics is a “local” semantics which supports efficient computation. We prove several correspondence results between the two semantics. To our knowledge, this is the first formal model theoretic semantics for probabilistic interval XML. We then provide an operational semantics that may be used to compute answers to queries and that is correct for a large class of probabilistic instances.
Privacy-enhanced personalization
Authors: Kobsa Alfred
Published: September 2007

Multi-pronged strategies are needed to reconcile the tension between personalization and privacy.
Dealing with change
Authors: Elfatatry Ahmed
Published: September 2007

Understanding the philosophy behind components and services is necessary before choosing a solution to deal with change in software design.
Involving top management in IT projects
Authors: Simonsen Jesper
Published: September 2007

Aligning business needs and IT solutions with the problem-mapping technique.
A classification of product comparison agents
Authors: Wan Yun , Menon Satya , Ramaprasad Arkalgud
Published: September 2007

Using the ecological food chain as an analogy for agent classification.
Testing object-oriented industrial software without precise oracles or results
Authors: Tse T. H. , Lau Francis C. M. , Chan W. K. , Liu Peter C. K. , Luk Colin K. F.
Published: September 2007

TACCLE tests an automated assembly system in which the expected outcomes cannot be precisely defined and the actual results cannot be directly observed.
Dynamic decision support through instantiation of UEML representations
Authors: Sen Sagnika , Demirkan Haluk , Goul Michael
Published: September 2007

The resulting system inherits (on demand) from representations developed and maintained by partners engaged in business alliances.
Better-than-nothing security practices
Authors: Berghel Hal
Published: September 2007

Security for general audiences.
Software copyright and role models
Authors: Bruckman Amy S.
Published: September 2007

Our words, ideas, and behavior profoundly influence our children and students to do good and not so good when using technology.
A deja-vu look at software engineering researchers who care about practice
Authors: Glass Robert L.
Published: September 2007

Reflections on institutes performing practice-relevant research.
Online social support for older people
Authors: Pfeil Ulrike
Published: September 2007

Until a few years ago, the main activities of internet users were all about accessing information and data. These days, the internet is increasingly used for social interaction and communication purposes. This topic becomes ever more important with the growing popularity of virtual environments, social networking websites and their likes. The fact that more and more people use online communities for social interaction opens new challenges for inclusive design researchers and practitioners. In addition to making information accessible to people with special needs, it is also necessary to ensure that everybody has access to the social aspects of online activities.
Effective requirements gathering for older adults
Authors: Rice Mark , Carmichael Alex
Published: September 2007

Eliciting appropriate requirements from users is an important part of the software design process. However, increasing evidence suggests that for many groups of older people lacking the experience and familiarity with many aspects of new technology, this can be a particularly difficult issue to address. Further, this issue is critical in regards to novel and emerging applications that break away from the 'traditional' desktop/workplace interface domain, and reside more in the domestic/entertainment/leisure domain. Thus the challenge is to address user-requirements before they are implemented, and in doing so create more meaningful dialogue with potential older users about applications and devices that do not actually exist yet.
Understanding frameworks and reviews
Authors: Schwarz Andrew , Mehta Manjari , Johnson Norman , Chin Wynne W.
Published: September 2007

Review and framework articles, which are commonly used to synthesize the research literature on a topic area can be important tools for advancing the state of knowledge in a field of inquiry. However, the appraisal of, and the distinction between, survey review and framework articles are often difficult because of the common focus on analyzing a substantial volume of literature. As more review and framework articles are produced with the concomitant increase in outlets for publication, such as MISQ Review and JAIS, it seems this is an opportune time for a reflexive pause regarding what are appropriate criteria for authors and reviewers to have in assessing such articles and recognizing their salient features. By assessing a representative sample of North American journals and IS researchers currently working in U.S. institutions, we present a set of criteria for the assessment of survey review and framework articles and identify the most salient features of these types of articles. Our findings suggest that, among other things, a "good" framework article should offer a clear guideline (indicating possible problems that can be examined within the stated framework), consist of a parsimonious set of elements, and have a clearly defined boundary. On the other hand, a good review article should advance the field as a result of consolidating prior research, identify and propose testable hypotheses, and focus on simplifying past results. We also found that both framework and review articles can be characterized according to their stated objective, comprehensiveness, relationship to research boundaries, temporal focus, and content focus. As our effort focuses primarily on our colleagues working in U.S. institutions, we invite our colleagues from other regions and academic traditions to make similar assessments of work from their perspectives.
Introduction
Authors: Hohmuth Michael
Published: September 2007

Since the early microkernel hype of the 1980s and some spectacular failures in the 1990s, the field of small-kernelbased systems has enjoyed renewed interest mostly because of contemporary challenges for computer security: Modern hypervisors and microkernels allow removing buggy and untrusted standard operating systems from a system's trusted computing base. At the same time, these kernels are small enough to make them (and indeed all of a system's trusted software) attainable for security auditing, formal methods, and even formal verification.

In this Special Topic Issue of Operating Systems Review, we explore this field in many dimensions: In addition to current research, we present both retrospective and forward-looking work; we look at both overall system structure as well as the mechanics of building small-kernel-based systems; and we present work from both the hypervisor and the microkernel factions of the small-kernel community.
Towards trustworthy computing systems
Authors: Heiser Gernot , Elphinstone Kevin , Kuz Ihor , Klein Gerwin , Petters Stefan M.
Published: September 2007

As computer systems become increasingly mission-critical, used in life-critical situations, and relied upon to protect intellectual property, operating-system reliability is becoming an ever growing concern. In the past, mission- and life-critical embedded systems consisted of simple microcontrollers running a small amount of software that could be validated using traditional and informal techniques. However, with the growth of software complexity, traditional techniques for ensuring software reliability have not been able to keep up, leading to an overall degradation of reliability. This paper argues that microkernels are the best approach for delivering truly trustworthy computer systems in the foreseeable future. It presents the NICTA operating-systems research vision, centred around the L4 microkernel and based on four core projects. The
seL4
project is designing an improved API for a secure microkernel,
L4, verified
will produce a full formal verification of the microkernel, Potoroo combines execution-time measurements with static analysis to determine the worst case execution profiles of the kernel, and
CAmkES
provides a component architecture for building systems that use the microkernel. Through close collaboration with
Open Kernel Labs
(a NICTA spinoff) the research output of these projects will make its way into products over the next few years.
A critique of the GNU hurd multi-server operating system
Authors: Walfield Neal H. , Brinkmann Marcus
Published: September 2007

The GNU Hurd's design was motivated by a desire to rectify a number of observed shortcomings in Unix. Foremost among these is that many policies that limit users exist simply as remnants of the design of the system's mechanisms and their implementation. To increase extensibility and integration, the Hurd adopts an object-based architecture and defines interfaces, in particular those for the composition of and access to name spaces, that are virtualizable.

This paper is first a presentation of the Hurd's design goals and a characterization of its architecture primarily as it represents a departure from Unix's. We then critique the architecture and assess it in terms of the user environment of today focusing on security. Then follows an evaluation of Mach, the microkernel on which the Hurd is built, emphasizing the design constraints which Mach imposes as well as a number of deficiencies its design presents for multi-server like systems. Finally, we reflect on the properties such a system appears to require.
A case study on the cost and benefit of dynamic RPC marshalling for low-level system components
Authors: Feske Norman
Published: September 2007

Interface definition languages are omnipresent in microkernel-based operating systems for providing a time-tested solution for realizing communication between user-level components. Driven by advancing kernels and application demands, IDL compilers and the generated communication-stub code have become significant contributors to the tool-chain complexity and the size of the trusted-computing base of such systems. This paper examines the performance and the engineering costs of an alternative technique for RFC communication between microkernel servers. Initially intended as an interim solution, the presented approach turned out to be low complex, yet very flexible and fast. These overly positive results turned our interim solution into a proposal for realizing inter-component communication in future microkernel-based operating systems.
Towards effective user-controlled scheduling for microkernel-based systems
Authors: Stoess Jan
Published: September 2007

With μ-kernel based systems becoming more and more prevalent, the demand for extensible resource management raises - and with it the demand for flexible thread scheduling. In this paper, we investigate the benefits and costs of a μ-kernel that exports scheduling from the kernel to user level. A key idea of our approach is to involve the user level whenever the μ-kernel encounters a situation that is ambiguous with respect to scheduling, and to permit the kernel to resolve the ambiguity based on user decisions. A further key aspect is that we rely on a generic, protection domain neutral interface between kernel and applications.

For evaluation, we have developed a hierarchical user level scheduling architecture for the L4 μ-kernel, and a virtualization environment running on its top. Our environment supports Linux 2.6.9 guest operating systems on IA-32 processors. Experiments indicate an application overhead between 0 and 10 percent compared to a pure in-kernel scheduler solution, but also demonstrate that our architecture enables effective and accurate user-directed scheduling.
L4oprof
Authors: Kim Dohun , Eom Jugwan , Park Chanik
Published: September 2007

These days, the L4 microkernel is expanding its domain towards embedded systems since it is showing a comparable performance with traditional monolithic kernels. The L4 microkernel shows a greatly different execution behavior of user applications from that in a traditional monolithic environment because most operating-system services are run as user-level applications. Therefore, we need a profiling framework to obtain a better understanding of performance bottlenecks for software optimization. However, current L4 profiling tools provide only higher-level information, such as the number of function calls, IPCs, and context switches. In this paper, we present a software profiling framework which gathers system-wide statistical information in the L4 microkernel environment. In order to support profiling lower-level information such as clock cycles, cache misses, and TLB misses, our profiling framework uses the hardware performance counters of the PMU (Performance Monitoring Unit) which most CPUs support. In this paper, we show that our profiling framework incurs less than 3% overhead below 15000 interrupts per second compared to the existing Linux profiling tool. Moreover, as a case study, we show the main cause of performance loss in L4Linux applications compared with Linux applications.
Opportunities and challenges of storage grid enabled by grid service
Authors: Deng Yuhui , Wang Frank
Published: September 2007

The explosive growth of data generated worldwide by information digitization has been identified as the key driver of storage system evolution. In this paper, we discuss the existing storage system architectures and pose the challenges they are facing. Drawing inspiration from Grid computing community, we propose to design a storage Grid enabled by Grid service which can solve the scalability and heterogeneity problems. However, the challenging Internet involved in the storage Grid incurs some emerging problems including the limited network performance, the unstable network environment, and etc. The Grid service involved in the storage Grid introduces much larger overhead which may result in low performance and inefficient utilization of storage resources. Because Grid service is designed for loosely coupled systems, we argue that the storage Grid can employ Grid service as a glue to manage, monitor and locate the Internet-scale storage resources which are transparent to users, while still adopting binary code to transfer data to maintain the performance. Some other solutions which may alleviate the performance pressure of Grid service and increase the efficiency of storage resource utilization are discussed as well.
Security of ultra-lightweight RFID authentication protocols and its improvements
Authors: Chien Hung-Yu , Huang Chen-Wei
Published: September 2007

The design of ultra-lightweight authentication protocols is imperative to the pervasive deployment of low-cost RFIDs. This paper examines the security of two well known ultra-lightweight authentication protocols (LMAP and M2AP) and the improved scheme. We demonstrate our efficient attacks on the protocols, and highlight the key weaknesses of the designs.
Design and automation
Authors: Radke C. E.
Published: September 2007

At the recent ACM 70 Conference, Bob Hitchcock chaired the SIGDA meeting. There were four of us in attendance: Bob (IBM), John Hanne (Texas Instruments), Murray Freeman (Philco), and myself (IBM). Later we caught a passer-by, Bob Brover (UCLA student). Although Bob was not acquainted with SIGDA or its purposes, at our insistence he did come up with a definition of Design Automation (DA). His on-the-spot definition was:

DESIGN -- An iterative, decision-making process that seeks to optimize the value of society's resources.

AUTOMATION -- Selecting of procedures for doing work with less effort.
Computer-aided preliminary layout of customized MOS arrays
Authors: Larsen R. P.
Published: September 2007

One of the most perplexing problems confronting device designers utilizing MOS technology is the development of an effective layout design methodology. This paper describes a versatile layout design scheme for customized digital-type MOS arrays utilizing four-phase clocking schemes (ratioless logic). The analytical characterization of this layout design scheme is defined through the introduction of p-order and m-order indices. The p-order indices are assigned to members of the Boolean equation set that define the relative placement of their mechanization areas (p-diffusion structures) on the MOS array. The m-order indices are assigned to members of the term set that define their relative placements within parallel metalization channels on the MOS array. The underlying variables influencing the algorithmic derivation of quasi-optimal p-order and m-order assignments are also discussed.

This preliminary layout design methodology is then related to the computer-aided design environment. Two computer programs, named P-ORDER and M-ORDER, that comprise the computer-aided design environment are briefly described. A simple example is also presented to illustrate the complementary relationships that exist between the device designer and computer within the computer-aided design environment. Computer inputs and outputs for this simple problem are presented to stress the minimal input requirements and the pictorial characterizations of computer-synthesized solutions, which are essential ingredients to cost effective computer-aided design applications.
Graphics abstraction model for SEICAD
Authors: Matsuo Masanobu , Kondo Ikuo , Tsunoda Shinji
Published: September 2007

The data abstraction approach to design of a Graphics Abstraction Model (GAM) for 3D solid objects and 2D picture views is described. The main idea is to represent graphical objects including instances of certain views by abstraction data types and data abstraction models using functional dependencies, which basically use the algebraic approach.

Compound objects constructed by several ACTION operations (ASSEMBLE, UNION, etc.) on primitive 3D entities can be handled as compound entities. Points, lines, and faces are defined as data abstractions. General drawing facilities such as points, lines and faces also can be used by commands under 3D coordinates data.
Implications of educational innovations
Authors: Dorn William S.
Published: September 2007

One must always keep in mind that education is the reason for the existence of a university. Of course, it is generally accepted that a strong and vigorous research program is essential to a university's survival. The argument for such a university research programs is that only through research programs can qualified faculty be attracted to the university, and only through continued research can the faculty remain qualified in their respective disciplines. Even if one accepts these arguments, the fact still remains that research activities are only justified in a university on the basis of their contributions to the caliber of the education. Without students a university is reduced to a research laboratory.
The position of the computer center director in the administrative heirarchies of U. S. higher education June 30, 1967
Authors: Hamblen John W.
Published: September 2007

As estimated 980 of the 2477 institutions of higher education had at least one computer by June 30, 1967. (see Tables 1, 2, and 3) By June 30, 1969, 1255 of the then 2537 institutions were expected to have access to at least one computer.
The computer in the university
Authors: Lykos Peter G.
Published: September 2007

Payroll and student records have been with us as long as the professor and the classroom. The technology which evolved out of Hollerith's invention of the punched card came to be used by those concerned with payroll and student records many years ago and the "unit record" became part of the life style of those concerned with university management activity. The invention of the electronic digital computer provided a natural and important complement to an already wide spread and highly diffused information handling technology based on the punched card. With the interfacing of the computer (now better designated the information processing machine) to the communication network, we are experiencing another large leap forward in the level of sophistication of information handling.
A different perspective on financing university computing centers
Authors: Uretsky Myron
Published: September 2007

During the past two years there has been increasing attention placed upon the problems associated with financing University Academic Computer Centers. This concern has been directly related to the great decrease in general funding from organizations such as the National Science Foundations. At the same time it is not clearly independent of the much broader picture relating to the financial conditions surrounding the University as a whole.
Contracting for computer use
Authors: Freed Roy N.
Published: September 2007

Until recently, the procurement of computers and their use was characterized by poor contracting practices. Suppliers presented form contracts that all too frequently failed to reflect the transactions involved. And customers, usually failed to tap their considerable bargaining power to get types of commitments and forms of written agreements to which they were entitled. The result was bedlam. Unsatisfactory procurement resulted. For a considerable time, customers suffered in silence, first considering the difficulties to be normal for the technology and later being too embarrassed to let others know. Finally, some resorted to litigation, unleashing a veritable avalanche. The unsatisfactory nature of dealings in that industry was dramatized by the volume of litigation and the massive verdicts sought. One judgment of $500,000 was awarded, although it was reduced to $250,000 two years later on appeal.
Vendor evaluation
Authors: Reeves Roy F.
Published: September 2007

In August 1970 we sent a letter to a number of vendors that manufacture large scale computer systems which might be suitable for use in the academic computer center at Ohio State University. In this letter we informed them that we intended to replace three separate computers by a single computer system in approximately two years. The three computer systems were an IBM 360/75 and an IBM 7094, both of which were used for batch processing, as well as a 360/50 which was used for time sharing.
Some reflections on computer technology and higher education
Authors: Sherman Gordon R.
Published: September 2007

It is consistent with our times and the many troubled aspects of it that there is so much uncertainty over modern computer technology and its current and future effect on the general quality of human life. There is also, at least in the United States, much uncertainty concerning higher education and its future role in society's efforts to better things. The combination of these two major and important areas of activity, to my mind, makes a most vital subject for study and reflection by concerned persons.
Legal constraints on computer data banks
Authors: Hoffman Lance J.
Published: September 2007

The intent of this paper is to give an overview of the existing laws and pending legislation related to the regulation of computer data banks. Many computer systems dealing with personal information are now legally required to take into consideration effects on personal privacy, access rights of subjects, and safeguards against unauthorized access.
The university as a systems development center for state government
Authors: Peck John C.
Published: September 2007

During the past few year, I have attended several professional meetings which have included panel discussions between representatives from industry and academia concerning computer science education. Industry usually claims that students graduate with few practical skills --- many can't even write a program as simple as a master file update. They further complain that such major issues as documentation, programming style, and team programming are neglected, while the abilities for written expression and oral presentation are often totally lacking. The programming languages which are common in industry (COBOL, FORTRAN) are often not introduced, and actual experience in the use of data base and data communications software just doesn't exist. In summary, universities are not interested in preparing a student for an industrial career.
Right to know ...need to learn
Authors: Berlo David K.
Published: September 2007

Managers and professional staff voice two complaints with high frequency when i visit with them. The first---"I'm snowed...overloaded with information. Look at this desk, look at my calendar. Too many meetings, too many interviews, too many reports and printouts. I'm inundated with information." The second---"I don't feel I'm a part of this outfit any more. They don't communicate with me. The organization is cold and impersonal. I don't know what's going on, don't feel I have a stake in the organization, don't believe it cares about me. I'm alienated ... or getting that way."
A framework for the response time analysis of fixed-priority tasks with stochastic inter-arrival times
Authors: Cucu Liliana , Tovar Eduardo
Published: September 2007

Real-time scheduling usually considers worst-case values for the parameters of task (or message stream) sets, in order to provide safe schedulability tests for hard real-time systems. However, worst-case conditions introduce a level of pessimism that is often inadequate for a certain class of (soft) real-time systems. In this paper we provide an approach for computing the stochastic response time of tasks where tasks have inter-arrival times described by discrete probabilistic distribution functions, instead of minimum inter-arrival (MIT) values.