bluuebunny/crossref_metadata_2025 huggingface dataset:
Precomputed shadow fields for dynamic scenes
Authors: Zhou Kun , Hu Yaohua , Lin Stephen , Guo Baining , Shum Heung-Yeung
Published: November 2005

We present a soft shadow technique for dynamic scenes with moving objects under the combined illumination of moving local light sources and dynamic environment maps. The main idea of our technique is to precompute for each scene entity a
shadow field
that describes the shadowing effects of the entity at points around it. The shadow field for a light source, called a
source radiance field
(SRF), records radiance from an illuminant as cube maps at sampled points in its surrounding space. For an occluder, an
object occlusion field
(OOF) conversely represents in a similar manner the occlusion of radiance by an object. A fundamental difference between shadow fields and previous shadow computation concepts is that shadow fields can be precomputed independent of scene configuration. This is critical for dynamic scenes because, at any given instant, the shadow information at any receiver point can be rapidly computed as a simple combination of SRFs and OOFs according to the current scene configuration. Applications that particularly benefit from this technique include large dynamic scenes in which many instances of an entity can share a single shadow field. Our technique enables low-frequency shadowing effects in dynamic scenes in real-time and all-frequency shadows at interactive rates.
All-frequency interactive relighting of translucent objects with single and multiple scattering
Authors: Wang Rui , Tran John , Luebke David
Published: November 2005

We present a technique, based on precomputed light transport, for interactive rendering of translucent objects under all-frequency environment maps. We consider the complete BSSRDF model proposed by Jensen et al. [2001]. which includes both single and diffuse multiple scattering components. The challenge is how to efficiently precompute all-frequency light transport functions due to subsurface scattering. We apply the two-pass hierarchical technique by Jensen et al. [2002] in the space of non-linearly approximated transport vectors, which allows us to efficiently evaluate transport vectors due to diffuse multiple scattering. We then include an approximated single scattering term in the precomputation, which previous interactive systems have ignored. For an isotropic phase function, this approximation produces a diffuse transport vector per vertex, and is combined with the multiple scattering component. For a general phase function, we introduce a technique from BRDF rendering to factor the phase function using a separable decomposition to allow for view-dependent rendering. We show that our rendering results qualitatively match the appearance of translucent objects, achieving a high level of realism at interactive rates.
A model for characterizing the scalability of distributed systems
Authors: Srinivas A Vijay , Janakiram D.
Published: November 2005

Scalability is an important issue in the construction of distributed systems. A number of theoretical and experimental studies have been made on scalability of distributed systems. However, they have been either studies on specific technologies or have studied scalability in isolation. The main conjecture of our work is that scalability must be perceived along with the related issues of availability, synchronization and consistency. In this context, we propose a scalability model which characterizes scalability as being dependent on these factors as well as the workload and faultload. The model is generic and can be used to compare scalability of similar systems. We illustrate this by a comparison between NFS and AFS, two well known distributed file systems. The model is also useful in identifying scalability bottlenecks in distributed systems. We have applied the model to optimize Virat, a wide-area shared object space that we have built.
User-level checkpoint and recovery for LAM/MPI
Authors: Zhang Youhui , Wong Dongsheng , Zheng Weimin
Published: November 2005

As high-performance clusters continue to grow in size and popularity, issues of fault tolerance and reliability are becoming limiting factors on application scalability. We integrated one user-level checkpointing and rollback recovery (CRR) library to LAM/MPI, a high performance implementation of the Message Passing Interface (MPI), to improve its availability. Compared with the current CRR implementation of LAM/MPI, our work supports file checkpointing and own higher portability, which can run on more platforms including IA32 and IA64 Linux. In addition, the test shows that less than 15% performance overhead is introduced by the CRR mechanism of our implementation.
The bounds of faulty components on consensus with dual failure modes
Authors: Yan Kuo-Qin , Wang Shu-Ching
Published: November 2005

The consensus is an important topic in the reliable distributed system because the system can cope with the influences from faulty components when the agreement is achieved. Siu, Chin and Yang have indicated that the bound on the number of allowable faulty processors in Meyer and Pradhan's scheme is an overestimated one, and they have given a new fixed bound to the allowable faulty processors. However, we find out that the new bound for the allowable faulty processors by Siu et al. still seems to give the scheme too much credit. In this study, we shall give a more accurate estimation to the bound of the allowable faulty processors.
Enhancement of digital signature with message recovery using self-certified public keys and its variants
Authors: Chen Yi-Hwa , Jan Jinn-Ke
Published: November 2005

In 2003, Tseng et al. proposed a self-certified public key signature with message recovery, which gives two advantages: one is that the signer's public key can simultaneously be authenticated in verifying the signature and the other one is that only the specified verifier can recover the message. Lately, Xie and YU proposed an attack to the Tseng et al.'s scheme under the cases: the specified verifier substitutes his secret key or two or more specified verifiers cooperatively forge the signer's signature. About the same time, Shao also proposed another insider forgery attack to break the Tseng et al.'s scheme. In addition, he claimed the Tseng et al.'s scheme without the properties of non-repudiation and forward security. Therefore, he proposed an improved scheme to overcome the weakness. In this paper, we will show that the Shao's improved scheme is still insecure against the insider forgery attack. A specified verifier can forge many different valid signatures with the same message to the other verifiers who cooperatively provide their secret keys. Furthermore, we give a small modification to overcome this weakness.
Interview with Ken Goldstein
Authors: Lee Newton , Goldstein Ken
Published: November 2005

Ken Goldstein is executive vice president and managing director of Disney Online (http://corporate.disney.go.com/wdig/bios/ken_goldstein.html). Prior to joining Disney in November 1998, Ken served as Broderbund Software's vice president of entertainment and founding general manager of the company's Red Orb Entertainment division. In the video interview, you will hear what Ken says about:1. Can you tell us about the multiplayer online game, Toontown Online, and the new game, Pirates of the Caribbean Online?2. Do children play multiplayer online games differently than adults?3. What are the challenges for the children's games market as opposed to the traditional gamers market?4. How will multiplayer online games reach beyond the traditional gamers?5. What is the future of "edutainment," combining gaming and education for children?6. Combining video games and physical fitness is a form of "exergaming". What other types of gaming do you envision we will have in the future?7. What will take computer games to the next new level?8. With online games, videos on demand, and IPTV, what is the future of the Internet for entertainment use?
GameFlow
Authors: Sweetser Penelope , Wyeth Peta
Published: November 2005

Although player enjoyment is central to computer games, there is currently no accepted model of player enjoyment in games. There are many heuristics in the literature, based on elements such as the game interface, mechanics, gameplay, and narrative. However, there is a need to integrate these heuristics into a validated model that can be used to design, evaluate, and understand enjoyment in games. We have drawn together the various heuristics into a concise model of enjoyment in games that is structured by flow. Flow, a widely accepted model of enjoyment, includes eight elements that, we found, encompass the various heuristics from the literature. Our new model, GameFlow, consists of eight elements -- concentration, challenge, skills, control, clear goals, feedback, immersion, and social interaction. Each element includes a set of criteria for achieving enjoyment in games. An initial investigation and validation of the GameFlow model was carried out by conducting expert reviews of two real-time strategy games, one high-rating and one low-rating, using the GameFlow criteria. The result was a deeper understanding of enjoyment in real-time strategy games and the identification of the strengths and weaknesses of the GameFlow model as an evaluation tool. The GameFlow criteria were able to successfully distinguish between the high-rated and low-rated games and identify why one succeeded and the other failed. We concluded that the GameFlow model can be used in its current form to review games; further work will provide tools for designing and evaluating enjoyment in games.
Creating entertainment applications for cellular phones
Authors: Coulton Paul , Rashid Omer , Edwards Reuben , Thompson Robert
Published: November 2005

Cellular phones offer a whole range of interesting and exciting possibilities for entertainment systems coupled with a very resource-constrained environment. In this article we consider the possibilities currently achievable through the example of a networked sports service. Applications that keep users up-to-date with sports results and playing fantasy team games, based on the results of actual events, are well established on the Internet; they attract millions of subscribers world-wide. As yet, the sports results services on cellular phones, even within countries that offer 3G services, are by and large SMS or WAP-based, and there are no dedicated fantasy team game services for cellular phones. In this article we present a novel application using GPRS that not only keeps users up-to-date, wherever they are, with the events of the English Premier Football League, but also provides the opportunity of playing a real-time fantasy football game as these events transpire. As we are seeing moves by cellular phone manufacturers to adopt standardized operating systems, we compare application development in Symbian, Brew, and J2ME. Although J2ME is not an operating system, it has, up until recently, been the only means of cross-platform application development for cellular phonesThis application not only takes advantage of the "nature" of the cellular network, rather than porting existing services off the Internet, but radically improves currently available services in terms of cost and efficiency. It also highlights the fact that resource constraints on a cellular phone are not a bar to creating compelling content. This technique could be applied to a whole range of sports from Formula 1 to baseball.
Preventing bots from playing online games
Authors: Golle Philippe , Ducheneaut Nicolas
Published: November 2005

As multiplayer online gaming gains in economic and social importance, an increasingly large number of players is beginning to rely on bots (automated player agents) to gain unfair advantages in games. In this article we study the problem of restricting participation in online games to human players so they can enjoy the game without interference from the bots. We propose two broad approaches to prevent bots from playing online games. The first consists of seamlessly integrating software-based tests (known as reverse Turing tests or CAPTCHA tests) into online games to tell humans and computers apart. Our second contribution is to propose hardware instantiations of CAPTCHA tests. Our techniques are applicable in a wide variety of online games, from poker to "shoot'em ups." They are cost-effective, immune to cheating, and preserve the human players' enjoyment of each game. We conclude with a discussion of how approaches to
deter
the use of bots may complement our techniques to
detect
bots.
Pervasive games
Authors: Magerkurth Carsten , Cheok Adrian David , Mandryk Regan L. , Nilsen Trond
Published: November 2005

This article gives an introduction and overview of the field of pervasive gaming, an emerging genre in which traditional, real-world games are augmented with computing functionality, or, depending on the perspective, purely virtual computer entertainment is brought back to the real world.The field of pervasive games is diverse in the approaches and technologies used to create new and exciting gaming experiences that profit by the blend of real and virtual game elements. We explicitly look at the pervasive gaming sub-genres of smart toys, affective games, tabletop games, location-aware games, and augmented reality games, and discuss them in terms of their benefits and critical issues, as well as the relevant technology base.
Atomic actions -- molecular experience
Authors: Walther Bo Kampmann
Published: November 2005

In this article we attempt to describe and analyze the formalisms of pervasive games and pervasive gaming (PG). As the title indicates, PG consists of atomic entities that nevertheless merge into a molecular structure that exhibits emergent features during the actual game-play. The article introduces four axes of PG (mobility, distribution, persistence, and transmediality). Further, it describes and analyses three key units of PG (rules, entities, and mechanics) as well as discusses the role of space in PG by differentiating between tangible space, information-embedded space, and accessibility space. The article is generally concerned with classifying the indispensable components of pervasive games and, in addition, it lists the invariant features of pervasive game-play, meaning the epistemology that is tied to this new kind of gaming situated on the borderline between corporeal and immaterial space. Of particular interest are game rules in pervasive gaming, since they seem to touch upon both the underlying, formal structure of the game (i.e., the ontology of PG) and the actual play vis-à-vis physical and/or virtual constraints (i.e., the PG epistemology).
SeRLoc
Authors: Lazos Loukas , Poovendran Radha
Published: November 2005

Many distributed monitoring applications of Wireless Sensor Networks (WSNs) require the location information of a sensor node. In this article, we address the problem of enabling nodes of Wireless Sensor Networks to determine their location in an untrusted environment, known as the
secure localization problem.
We propose a novel range-independent localization algorithm called SeRLoc that is well suited to a resource constrained environment such as a WSN. SeRLoc is a distributed algorithm based on a two-tier network architecture that allows sensors to passively determine their location without interacting with other sensors. We show that SeRLoc is robust against known attacks on a WSNs such as the
wormhole attack
, the
Sybil attack
, and
compromise of network entities
and analytically compute the probability of success for each attack. We also compare the performance of SeRLoc with state-of-the-art range-independent localization schemes and show that SeRLoc has better performance.
Visual cues can be sufficient for triggering automatic, reflexlike spatial updating
Authors: Riecke Bernhard E. , Heyde Markus Von Der , Bülthoff Heinrich H.
Published: November 2005

“Spatial updating” refers to the process that automatically updates our egocentric mental representation of our immediate surround during self-motions, which is essential for quick and robust spatial orientation. To investigate the relative contribution of visual and vestibular cues to spatial updating, two experiments were performed in a high-end Virtual Reality system. Participants were seated on a motion platform and saw either the surrounding room or a photorealistic virtual model presented via head-mounted display or projection screen. After upright rotations, participants had to point “as accurately and quickly as possibl ” to previously learned targets that were outside of the current field of view (FOV). Spatial updating performance, quantified as response time, configuration error, and pointing error, was comparable in the real and virtual reality conditions when the FOV was matched. Two further results challenge the prevailing basic assumptions about spatial updating: First, automatic, reflexlike spatial updating occurred without any physical motion, i.e., visual information from a known scene alone
can
, indeed, be sufficient, especially for large FOVs. Second, continuous-motion information is not, in fact, mandatory for spatial updating---merely presenting static images of new orientations proved sufficient, which motivated our distinction between
continuous
and
instant-based
spatial updating.
Distance perception in real and virtual environments
Authors: Plumert Jodie M. , Kearney Joseph K. , Cremer James F. , Recker Kara
Published: November 2005

We conducted three experiments to compare distance perception in real and virtual environments. In Experiment 1, adults estimated how long it would take to walk to targets in real and virtual environments by starting and stopping a stopwatch while looking at a target person standing between 20 and 120 ft away. The real environment was a large grassy lawn in front of a university building. We replicated this scene in our virtual environment using a nonstereoscopic, large-screen immersive display system. We found that people underestimated time to walk in both environments for distances of 40 to 60 ft and beyond. However, time-to-walk estimates were virtually identical across the two environments, particularly when people made real environment estimates first. In Experiment 2, 10- and 12-year-old children and adults estimated time to walk in real and virtual environments both with and without vision. Adults underestimated time to walk in both environments for distances of 60 to 80 ft and beyond. Again, their estimates were virtually identical in the real and virtual environment both with and without vision. Twelve-year-olds' time-to-walk estimates were also very similar across the two environments under both viewing conditions, but 10-year-olds exhibited greater underestimation in the virtual than in the real environment. A third experiment showed that adults' time-to-walk estimates were virtually identical to walking without vision. We conclude that distance perception may be better in virtual environments involving large-screen immersive displays than in those involving head-mounted displays (HMDS).
Manipulating Video Sequences to Determine the Components of Conversational Facial Expressions
Authors: Cunningham Douglas W. , Kleiner Mario , Wallraven Christian , Bülthoff Heinrich H.
Published: November 2005

Communication plays a central role in everday life. During an average conversation, information is exchanged in a variety of ways, including through facial motion. Here, we employ a custom, model-based image manipulation technique to selectively “freez ” portions of a face in video recordings in order to determine the areas that are sufficient for proper recognition of nine conversational expressions. The results show that most expressions rely primarily on a single facial area to convey meaning with different expressions using different areas. The results also show that the combination of rigid head, eye, eyebrow, and mouth motions is sufficient to produce expressions that are as easy to recognize as the original, unmanipulated recordings. Finally, the results show that the manipulation technique introduced few perceptible artifacts into the altered video sequences. This fusion of psychophysics and computer graphics techniques provides not only fundamental insights into human perception and cognition, but also yields the basis for a systematic description of what needs to move in order to produce realistic, recognizable conversational facial animations.
Predicting and Evaluating Saliency for Simplified Polygonal Models
Authors: Howlett Sarah , Hamill John , O'Sullivan Carol
Published: November 2005

In this paper, we consider the problem of determining feature saliency for three-dimensional (3D) objects and describe a series of experiments that examined if salient features exist and can be predicted in advance. We attempt to determine salient features by using an eye-tracking device to capture human gaze data and then investigate if the visual fidelity of simplified polygonal models can be improved by emphasizing the detail of salient features identified in this way. To try to evaluate the visual fidelity of the simplified models, a set of naming time, matching time, and forced-choice preference experiments were carried out. We found that perceptually weighted simplification led to a significant increase in visual fidelity for the lower levels of detail (LOD) of the natural objects, but that for the man-made artifacts the opposite was true. We, therefore, conclude that visually prominent features may be predicted in this way for natural objects, but our results show that saliency prediction for synthetic objects is more difficult, perhaps because it is more strongly affected by task. As a further step we carried out some confirmation experiments to examine if the prominent features found during the saliency experiment were actually the features focused upon during the naming, matching, and forced-choice preference tasks. Results demonstrated that the heads of natural objects received a significant amount of attention, especially during the naming task. We hope that our results will lead to new insights into the nature of saliency in 3D graphics.
Low-Level Image Cues in the Perception of Translucent Materials
Authors: Fleming Roland W. , Bülthoff Heinrich H.
Published: November 2005

When light strikes a translucent material (such as wax, milk or fruit flesh), it enters the body of the object, scatters and reemerges from the surface. The diffusion of light through translucent materials gives them a characteristic visual softness and glow. What image properties underlie this distinctive appearance? What cues allow us to tell whether a surface is translucent or opaque? Previous work on the perception of semitransparent materials was based on a very restricted physical model of thin filters [Metelli 1970; 1974a,b]. However, recent advances in computer graphics [Jensen et al. 2001; Jensen and Buhler 2002] allow us to efficiently simulate the complex subsurface light transport effects that occur in real translucent objects. Here we use this model to study the perception of translucency, using a combination of psychophysics and image statistics. We find that many of the cues that were traditionally thought to be important for semitransparent filters (e.g., X-junctions) are not relevant for solid translucent objects. We discuss the role of highlights, color, object size, contrast, blur, and lighting direction in the perception of translucency. We argue that the physics of translucency are too complex for the visual system to estimate intrinsic physical parameters by inverse optics. Instead, we suggest that we identify translucent materials by parsing them into key regions and by gathering image statistics from these regions.
A maiden analysis of longest wait first
Authors: Edmonds Jeff , Pruhs Kirk
Published: November 2005

We consider server scheduling strategies to minimize average flow time in a multicast pull system where data items have uniform size. The algorithm Longest Wait First (LWF) always services the page where the aggregate waiting times of the outstanding requests for that page is maximized. We provide the first non-trivial analysis of the worst case performance of LWF. On the negative side, we show that LWF is nots-speedO(1)-competitive fors< 1+√5/2. On the positive side, we show that LWF is 6-speedO(1)-competitive.
Fixed-parameter algorithms for (
k
,
r
)-center in planar graphs and map graphs
Authors: Demaine Erik D. , Fomin Fedor V. , Hajiaghayi Mohammadtaghi , Thilikos Dimitrios M.
Published: November 2005

The

(
k
,
r
)-center problem

asks whether an input graph
G
has ≤
k
vertices (called
centers
) such that every vertex of
G
is within distance ≤
r
from some center. In this article, we prove that the (
k
,
r
)-center problem, parameterized by
k
and
R
, is fixed-parameter tractable (FPT) on planar graphs, i.e., it admits an algorithm of complexity
f
(
k
,
r
)
n

O
(1)

where the function
f
is independent of
n
. In particular, we show that
f
(
k,r
) = 2

O
(
r
log
r
) √k

, where the exponent of the exponential term grows sublinearly in the number of centers. Moreover, we prove that the same type of FPT algorithms can be designed for the more general class of
map graphs
introduced by Chen, Grigni, and Papadimitriou. Our results combine dynamic-programming algorithms for graphs of small branchwidth and a graph-theoretic result bounding this parameter in terms of
k
and
r
. Finally, a byproduct of our algorithm is the existence of a PTAS for the
r
-domination problem in both planar graphs and map graphs.Our approach builds on the seminal results of Robertson and Seymour on Graph Minors, and as a result is much more powerful than the previous machinery of Alber et al. for exponential speedup on planar graphs. To demonstrate the versatility of our results, we show how our algorithms can be extended to general parameters that are “large” on grids. In addition, our use of branchwidth instead of the usual treewidth allows us to obtain much faster algorithms, and requires more complicated dynamic programming than the standard leaf/introduce/forget/join structure of nice tree decompositions. Our results are also unique in that they apply to classes of graphs that are not minor-closed, namely, constant powers of planar graphs and map graphs.
Pricing multicasting in more flexible network models
Authors: Adler Micah , Rubenstein Dan
Published: November 2005

The problem of designing efficient algorithms for sharing the cost of multicasting has recently received considerable attention. In this article, we examine the effect on the complexity of pricing when two flexibility-enhancing mechanisms are incorporated into the network model. In particular, we study a model where the session is offered at a number of different rates of transmission, and where there is a cost for enabling multicasting at each node of the network. We consider two techniques that have been used in practice to provide multiple rates: using a layered transmission scheme (called the
layered paradigm
) and using different multicast groups for each possible rate (called the
split session paradigm
). We demonstrate that the difference between these two paradigms has a significant impact on the complexity of pricing multicasting.For the layered paradigm, we provide a distributed algorithm for computing pricing efficiently in terms of local computation and message complexity. For the split session paradigm, on the other hand, we demonstrate that this problem can be solved in polynomial time if the number of possible rates is fixed, but if the number of rates is part of the input, then the problem becomes NP-Hard even to approximate. We also examine the effect of delivering the transmissions for the various rates from different locations within the network. We show that, in this case, the pricing problem becomes NP-Hard for the split session paradigm even for a fixed constant number of possible rates but if layering is used, then it can be solved in polynomial time by formulating the problem as a totally unimodular integer program.
On network design problems: fixed cost flows and the covering steiner problem
Authors: Even Guy , Kortsarz Guy , Slany Wolfgang
Published: November 2005

Network design problems, such as generalizations of the Steiner Tree Problem, can be cast as edge-cost-flow problems. An edge-cost flow problem is a min-cost flow problem in which the cost of the flow equals the sum of the costs of the edges carrying positive flow.We prove a hardness result for the Minimum Edge Cost Flow Problem (MECF). Using the one-round two-prover scenario, we prove that MECF does not admit a 2

log
1-ε
n

-ratio approximation, for every constant ε > 0, unless
NP
⊆
DTIME
(
n
polylogn
).A restricted version of MECF, called Infinite Capacity MECF (ICF), is defined. The ICF problem is defined as follows: (i) all edges have infinite capacity, (ii) there are multiple sources and sinks, where flow can be delivered from every source to every sink, (iii) each source and sink has a supply amount and demand amount, respectively, and (iv) the required total flow is given as part of the input. The goal is to find a minimum edge-cost flow that meets the required total flow while obeying the demands of the sinks and the supplies of the sources. This problem naturally arises in practical scheduling applications, and is equivalent to the special case of single source MECF, with all edges not touching the source or the sink having infinite capacity.The directed ICF generalizes the Covering Steiner Problem in directed and undirected graphs. The undirected version of ICF generalizes several network design problems, such as: Steiner Tree Problem,
k
-MST, Point-to-point Connection Problem, and the generalized Steiner Tree Problem.An
O
(log
x
)-approximation algorithm for undirected ICF is presented. We also present a bi-criteria approximation algorithm for directed ICF. The algorithm for directed ICF finds a flow that delivers half the required flow at a cost that is at most
O
(
n
ε
/ε
4
) times bigger than the cost of an optimal flow. The running time of the algorithm is
O
(
x
2/ε
ċ
n
1+1/ε
), where
x
denotes the required total flow.Randomized approximation algorithms for the Covering Steiner Problem in directed and undirected graphs are presented. The algorithms are based on a randomized reduction to a problem called 1/2-Group Steiner. In undirected graphs, the approximation ratio matches the approximation ratio of Konjevod et al. [2002]. However, our algorithm is much simpler. In directed graphs, the algorithm is the first nontrivial approximation algorithm for the Covering Steiner Problem. Deterministic algorithms are obtained by derandomization.
On a generalization of the stable roommates problem
Authors: Cechlárová Katarína , Fleiner Tamás
Published: November 2005

We consider two generalizations of the stable roommates problem: a) we allow parallel edges in the underlying graph, and b) we study a problem with multiple partners. We reduce both problems to the classical stable roommates problem and describe an extension of Irving's algorithm that solves the generalized problem efficiently. We give a direct proof of a recent result on the structure of stable many-to-many matchings (so called stable
b
-matchings) as a by-product of the justification of the algorithm.
High-level modeling and simulation of single-chip programmable heterogeneous multiprocessors
Authors: Paul Joann M. , Thomas Donald E. , Cassidy Andrew S.
Published: November 2005

Heterogeneous multiprocessing is the future of chip design with the potential for tens to hundreds of programmable elements on single chips within the next several years. These chips will have heterogeneous, programmable hardware elements that lead to different execution times for the same software executing on different resources as well as a mix of desktop-style and embedded-style software. They will also have a layer of programming across multiple programmable elements forming the basis of a new kind of programmable system which we refer to as a Programmable Heterogeneous Multiprocessor (PHM). Current modeling approaches use instruction set simulation for performance modeling, but this will become far too prohibitive in terms of simulation time for these larger designs. The fundamental question is what the next higher level of design will be. The high-level modeling, simulation and design required for these programmable systems poses unique challenges, representing a break from traditional hardware design. Programmable systems, including layered concurrent software executing via schedulers on concurrent hardware, are not characterizable with traditional component-based hierarchical composition approaches, including discrete event simulation. We describe the foundations of our layered approach to modeling and performance simulation of PHMs, showing an example design space of a network processor explored using our simulation approach.
A framework for systematic validation and debugging of pipeline simulators
Authors: Roy Arnab , Panda S. K. , Kumar Rajeev , Chakrabarti P. P.
Published: November 2005

Microprocessor pipeline simulation at the system level is an extremely important activity in the architecture exploration process. In this article, we address the problem of validating and debugging a pipeline simulator from the specific perspective of instruction scheduling. We propose a general framework for a systematic validation process and show that the assumptions made are justified for most standard pipeline models. The framework does not need any formal specification of the pipeline logic and hence can be readily integrated into the simulation and iteration-based architectural design space exploration process. We propose a concept of semantic equivalence between two simulations called
D* equivalence
which effectively captures the dataflow between instructions through registers. We then proceed to propose an algorithm which decides this equivalence in time polynomial in the number of instructions executed and the number of registers. We implement the algorithm and demonstrate how the framework facilitates debugging.
The open family of temporal logics
Authors: Banerjee Ansuman , Dasgupta Pallab
Published: November 2005

Assume-guarantee style verification of modules relies on the appropriate modeling of the interaction of the module with its environment. Popular temporal logics such as Computation Tree Logic (CTL) and Linear Temporal Logic (LTL) that were originally defined for closed systems (Kripke structures) do not make any syntactic discrimination between input and output variables. As a result, these logics and their recent derivatives (such as System Verilog, Sugar, Forspec, etc) permit the specification of properties that have some semantic problems when interpreted over open systems or modules. These semantic problems are quite common in practice, but are computationally hard to detect within a given specification. In this article, we propose a new style for writing temporal specifications of open systems that helps the designer to avoid most of these problems. In the proposed style, the basic temporal operators (such asnextanduntil) are annotated withassumeconstraints over the input variables. We formalize this style through an extension of LTL, namely Open-LTL and an extension of CTL with fairness, called Open-CTL. We show that this simple syntactic separation between theassumeand theguaranteeachieves the desired results. We show that the proposed style can be integrated with traditional symbolic model-checking techniques and present a complete tool for the verification of Verilog RTL modules in isolation.
An algorithm for integrated pin assignment and buffer planning
Authors: Xiang Hua , Tang Xiaoping , Wong Martin D. F.
Published: November 2005

The
buffer block
methodology has become increasingly popular as more and more buffers are needed in deep-submicron design, and it leads to many challenging problems in physical design. In this article, we present a polynomial-time exact algorithm for integrated pin assignment and buffer planning for all two-pin nets from one macro block (source block) to all other blocks of a given buffer block plan, while minimizing the total cost α ˙
W
+ β ˙
R
for any positive α and β where
W
is the total wirelength, and
R
is the number of buffers. By applying this algorithm iteratively (each time, pick one block as the source block), it provides a polynomial-time algorithm for pin assignment and buffer planning for nets among multiple macro blocks. Experimental results demonstrate its efficiency and effectiveness.
A novel document retrieval method using the discrete wavelet transform
Authors: Park Laurence A. F. , Ramamohanarao Kotagiri , Palaniswami Marimuthu
Published: November 2005

Current information retrieval methods either ignore the term positions or deal with exact term positions; the former can be seen as coarse document resolution, the latter as fine document resolution. We propose a new spectral-based information retrieval method that is able to utilize many different levels of document resolution by examining the term patterns that occur in the documents. To do this, we take advantage of the multiresolution analysis properties of the wavelet transform. We show that we are able to achieve higher precision when compared to vector space and proximity retrieval methods, while producing fast query times and using a compact index.
From the chair
Authors: Sipior Janice C. , Lending Diane , Amoroso Donald L. , Vowels Susan
Published: November 2005

I am excited to have been reelected to serve as Chair of SIGMIS for July 1, 2005 - June 30, 2007! I look forward to serving the members of SIGMIS in the best way that I can. I would like to thank all of you for your support.Before announcing our newly elected officers, I wish to thank our two departing officers for their past service: Laurie Schatzberg, University of New Mexico, served as the Vice Chair since July 1, 2001. As Conrad Shayo, CPR'06 Conference Chair, said so well, "Laurie is so kind, she nudges me along saying nicely: 'you better ha...'" I wholeheartedly agree. Laurie has a gentle way of keeping things on track. She is an invaluable source of inspiration, ideas, and follow-through in her service to SIGMIS. I know I will miss her dearly as she pursues greater responsibilities at the University of New Mexico.Dorothy Leidner, Texas Christian University, served as Secretary/Treasurer since July 1, 2001. I am happy that she will continue as a Co-Editor of Data Base with Wynne Chin, University of Houston. Her outstanding dedication and service to SIGMIS is greatly appreciated.I would like to welcome our new officers, whom I look forward to working with:

Diane Lending, James Madison University, ACM-SIGMIS Vice Chair

Don Amoroso, Appalachian State University, ACM-SIGMIS Secretary/Treasurer

To be announced, ACM-SIGMIS CPR (Computer Personnel Research) Committee Chair Susan Vowels, Washington College, ACM-SIGMIS Information DirectorAnd now, on to our upcoming activities. Please consider sending a submission to the SIGMIS Computer Personnel Research 2006 Conference: When & Where: April 13-15, 2006, Claremont, California, USATheme:"Forty Four Years of Computer Personnel Research: Achievements, Challenges and the Future". The submission deadline is October 15, 2005. Your participation is encouraged! For more information, please contact the SIGMIS CPR Conference Committee:

Conference Chair:
Conrad Shayo, California State University, San Bernardino

Program Co-Chairs:
Kate M. Kaiser, Marquette University & Terry Ryan, Claremont Graduate University

Local Arrangements:
Seta Whitby, University of La Verne

Treasurer:
Laurie Schatzberg, University of New Mexico

Publicity:
Tony Coulson, California State University, San Bernardino

Doctoral Consortium Co-Chairs:
Andrea Tapia & Lynette Kvasny, Penn State University

Or, check our website at: http://www.acm.org/sigmisPlease help make the SIGMIS CPR Conference a continuing success. Consider hosting a future SIGMIS CPR Conference!Finally, please mark your calendar now for the Fifth Annual ACM-SIGMIS Reception:

Where:
International Conference on Information Systems (ICIS2005) The Venetian Hotel, Casanova Room 606, Las Vegas, NV USA

When:
Saturday, December 10, 2005, 5:30 to 7:00 pm

Who:
All ACM-SIGMIS members and their invited guests are welcome!

On behalf of all of the new officers, thank you for your continued support of SIGMIS. Please feel free to contact any one of us with suggestions or ideas.
A new twist on an old method
Authors: Wade Michael R. , Tingling Peter
Published: November 2005

A review of the Information Systems literature reveals that experiments are employed infrequently by IS researchers. Further, there is some evidence that the use of experiments is not increasing and may, in fact, be declining. A relatively new approach, the Web experiment, is introduced as a tool for Information Systems researchers to take advantage of the benefits of experimental methods, while avoiding some of the costs. A Web experiment resides on a Web site and can be accessed online through a browser. The experiment includes one or more independent variables that are dynamically manipulated through the Web. Subjects are typically remote from the experimenter and are free to complete the experiment at a time and place of their choosing. The strengths and weaknesses of Web experiments are explored.
Trustworthiness in B2C e-commerce
Authors: Serva Mark A. , Benamati John "Skip" , Fuller Mark A.
Published: November 2005

Advancing research on trust requires clarifying the different conceptualizations of trust and trust-related constructs. The purpose of this study is to advance the theoretical conceptualization of trustworthiness by synthesizing previous research and testing three alternative conceptualizations within the e-commerce context. Data collected from multiple studies involving over 700 participants were used to examine the relative merits of trustworthiness as a one-dimensional construct, a grouping of three first-order constructs, and a second-order construct. Our results indicate that a one-dimensional view may be too simplistic, given the variety of factors that online consumers must weigh. Instead, the study suggests that trustworthiness is multidimensional and that both first- and second-order conceptualizations have a place in e-commerce trust research. Trust researchers should be guided by the research question, hypotheses, and research design in deciding which conceptualization to use.
Continuous Optimization
Authors: Fahs Brian , Rafacz Todd , Patel Sanjay J. , Lumetta Steven S.
Published: November 2005

This paper presents a hardware-based dynamic optimizer that continuously optimizes an applicationýs instruction stream. In continuous optimization, dataflow optimizations are performed using simple, table-based hardware placed in the rename stage of the processor pipeline. The continuous optimizer reduces dataflow height by performing constant propagation, reassociation, redundant load elimination, store forwarding, and silent store removal. To enhance the impact of the optimizations, the optimizer integrates values generated by the execution units back into the optimization process. Continuous optimization allows instructions with input values known at optimization time to be executed in the optimizer, leaving less work for the out-of-order portion of the pipeline. Continuous optimization can detect branch mispredictions earlier and thus reduce the misprediction penalty. In this paper, we present a detailed description of a hardware optimizer and evaluate it in the context of a contemporary microarchitecture running current workloads. Our analysis of SPECint, SPECfp, and mediabench workloads reveals that a hardware optimizer can directly execute 33% of instructions, resolve 29% of mispredicted branches, and generate addresses for 76% of memory operations. These positive effects combine to provide speed ups in the range 0.99 to 1.27.
Architecture for Protecting Critical Secrets in Microprocessors
Authors: Lee Ruby B. , Kwan Peter C. S. , McGregor John P. , Dwoskin Jeffrey , Wang Zhenghong
Published: November 2005

We propose “secret-protected (SP)” architecture to enable secure and convenient protection of critical secrets for a given user in an on-line environment. Keys are examples of critical secrets, and key protection and management is a fundamental problem - often assumed but not solved - underlying the use of cryptographic protection of sensitive files, messages, data and programs. SP-processors contain a minimalist set of architectural features that can be built into a general-purpose microprocessor to provide protection of critical secrets and their computations, without expensive or inconvenient auxiliary hardware. SP-architecture also requires a trusted software module, a few modifications to the operating system, a secure I/O path to the user, and a secure installation process. Unique aspects of our architecture include: decoupling of user secrets from the devices, enabling users to securely access their keys from different networked computing devices; the use of symmetric master keys rather than more costly public-private key pairs; and the avoidance of any permanent or factory-installed device secrets.
Disk Drive Roadmap from the Thermal Perspective
Authors: Gurumurthi Sudhanva , Sivasubramaniam Anand , Natarajan Vivek K.
Published: November 2005

The importance of pushing the performance envelope of disk drives continues to grow, not just in the server market but also in numerous consumer electronics products. One of the most fundamental factors impacting disk drive design is the heat dissipation and its effect on drive reliability, since high temperatures can cause off-track errors, or even head crashes. Until now, drive manufacturers have continued to meet the 40% annual growth target of the internal data rates (IDR) by increasing RPMs, and shrinking platter sizes, both of which have counter-acting effects on the heat dissipation within a drive. As this paper will show, we are getting to a point where it is becoming very difficult to stay on this roadmap. This paper presents an integrated disk drive model that captures the close relationships between capacity, performance and thermal characteristics over time. Using this model, we quantify the drop off in IDR growth rates over the next decade if we are to adhere to the thermal envelope of drive design.We present two mechanisms for buying back some of this IDR loss with Dynamic Thermal Management (DTM). The first DTM technique exploits any available thermal slack, between what the drive was intended to support and the currently lower operating temperature, to ramp up the RPM. The second DTM technique assumes that the drive is only designed for average case behavior, thus allowing higher RPMs than the thermal envelope, and employs dynamic throttling of disk drive activities to remain within this envelope.
Direct Cache Access for High Bandwidth Network I/O
Authors: Huggahalli Ram , Iyer Ravi , Tetrick Scott
Published: November 2005

Recent I/O technologies such as PCI-Express and 10Gb Ethernet enable unprecedented levels of I/O bandwidths in mainstream platforms. However, in traditional architectures, memory latency alone can limit processors from matching 10 Gb inbound network I/O traffic. We propose a platform-wide method called Direct Cache Access (DCA) to deliver inbound I/O data directly into processor caches. We demonstrate that DCA provides a significant reduction in memory latency and memory bandwidth for receive intensive network I/O applications. Analysis of benchmarks such as SPECWeb9, TPC-W and TPC-C shows that overall benefit depends on the relative volume of I/O to memory traffic as well as the spatial and temporal relationship between processor and I/O memory accesses. A system level perspective for the efficient implementation of DCA is presented.