bluuebunny/crossref_metadata_2025 huggingface dataset:
IOSONO
Authors: Lee Newton
Published: August 2005

IOSONO breakthrough spatial audio technology for the projection of recorded or amplified sound. IOSONO has the potential to revolutionize the way motion pictures, themed attractions, and live events are experienced. For the first time ever all areas of a listening area can be filled with completely natural, realistic three-dimensional sound. IOSONO innovation is that it recreates natural sound waves while traditional audio systems merely amplify sound.

IOSONO is based on the principle that sound waves can be reproduced using secondary sources at the perimeter of the original sound field. The result of over 15 years of research and development, this process is called Wave Field Synthesis (WFS). Speaker arrays ring the listening space and operate in a coordinated, phased fashion to re-create each individual sound wave.

For example, a helicopter can slowly approach the audience, fly through the middle of the theatre, and disappear off into the distance. The audience hears the sound waves the helicopter would generate if it were actually flying this path.
The Third International Conference on Active Media Technology
Authors: Lee Newton
Published: August 2005

In the great digital era, we are witnessing many rapid scientific and technological developments in human-centered, seamless computing environments, interfaces, devices, and systems with applications ranging from business and communication to entertainment and learning. These developments are collectively best characterized as Active Media Technology (AMT), a new area of information technology and computer science that emphasizes the proactive, seamless roles of interfaces and systems as well as new media in all aspects of digital life.

The first international conference on Active Media Technology (AMT01) was held in Hong Kong in 2001, and the second International Conference on Active Media Technology (AMT03) was held in Chongqing of China in May 29-31 of 2004. Following the success of AMT01 and AMT03, the third International Conference on Active Media Technology (AMT05) will be held in Kagawa, Japan in 2005.
Coming soon
Authors: Lee Newton
Published: August 2005

Technology Induced Change in Film/Television Distribution

High Performance Data Recording Architecture and High Definition Video

Mobile Digital Rights Management for Multimedia

Why We Play Games: Gaming Beyond Games

Computer Game Flow Design

How Autonomous Characters Change The Process And Product Of Animating

Design vs. Content: A Survey of Ten Popular Web Sites That Made Emotional Connections with the User

Jabber Server Extensions for Multiplayer Games

Massive Multi-Player Java Game Server

and more...
Augmenting the virtual domain with physical and social elements
Authors: Magerkurth Carsten , Engelke Timo , Memisoglu Maral
Published: August 2005

In this paper, means of enriching computer entertainment experiences by emphasizing physical and social game elements are discussed. A conceptual framework in which the relations between the virtual, the physical, and the social domains are modeled is presented. Interfaces that mediate between the domains are discussed along with a complementary software architecture that helps developing hybrid computer games. Finally, sample games that follow the approach of physical and social augmentation are presented.
Audio media for public spaces
Authors: Krause Bernard L.
Published: August 2005

Audio media is one of the most important, yet least considered and valued elements of exhibit design for public spaces. The historical and cultural roots of this oversight are considered in this document, along with ways to mitigate the problems through the implementation of powerful new delivery technologies and conceptual design.
Pruning-based, energy-optimal, deterministic I/O device scheduling for hard real-time systems
Authors: Swaminathan Vishnu , Chakrabarty Krishnendu
Published: August 2005

Software-controlled (or dynamic) power management (DPM) in embedded systems has emerged as an attractive alternative to inflexible hardware solutions. However, DPM via I/O device scheduling for hard real-time systems has received relatively little attention. In this paper, we present an offline I/O device scheduling algorithm called energy-optimal device scheduler (EDS). For a given set of jobs, it determines the start time of each job such that the energy consumption of the I/O devices is minimized. EDS also ensures that no real-time constraint is violated. The device schedules are provably energy optimal under hard real-time job deadlines. Temporal and energy-based pruning are used to reduce the search space significantly. Since the I/O device scheduling problem is NP-complete, we also describe a heuristic called maximum device overlap (MDO) to generate near-optimal solutions in polynomial time. We present experimental results to show that EDS and MDO reduce the energy consumption of I/O devices significantly for hard real-time systems.
Optimal voltage allocation techniques for dynamically variable voltage processors
Authors: Kwon Woo-Cheol , Kim Taewhan
Published: August 2005

This paper presents important, new results of a study on the problem of task scheduling and voltage allocation in dynamically variable voltage processors, the purpose of which was minimization of processor energy consumption. The contributions are twofold: (1) For given multiple
discrete
supply voltages and tasks with arbitrary arrival-time/deadline constraints, we propose a voltage allocation technique that produces a feasible task schedule with
optimal
processor energy consumption. (2) We then extend the problem to include the case in which tasks have
nonuniform loads
(i.e.; switched) capacitances and solve it
optimally
. The proposed technique, called Alloc-vt, in (1) is based on the prior results in [Yao, Demers and Shenker. 1995. In
Proceedings of IEEE Symposium on Foundations of Computer Science
. 374--382] (which is optimal for dynamically continuously variable voltages, but not for discrete ones) and [Ishihara and Yasuura. 1998. In
Proceedings of International Symposium on Low Power Electronics and Design
. 197--202] (which is optimal for a single task, but not for multiple tasks), whereas the proposed technique, called Alloc-vt
cap
, in (2) is based on an efficient linear programming (LP) formulation. Both techniques solve the allocation problems optimally in polynomial time.
Energy macromodeling of embedded operating systems
Authors: Tan T. K. , Raghunathan A. , Jha N. K.
Published: August 2005

As embedded systems get more complex, deployment of embedded operating systems (OSs) as software run-time engines has become common. In particular, this trend is true even for battery-powered embedded systems, where maximizing battery life is a primary concern. In such OS-driven embedded software, the overall energy consumption depends very much on which OS is used and how the OS is used. Therefore, the energy effects of the OS need to be studied in order to design low-energy systems effectively.In this paper, we discuss the motivation for performing OS energy characterization and propose a methodology to perform the characterization systematically. The methodology consists of two parts. The first part is
analysis
, which is concerned with identifying a set of components that can be used to characterize the OS energy consumption, called
energy characteristics
. The second part is
macromodeling
, which is concerned with obtaining quantitative macromodels for the energy characteristics. It involves the process of experiment design, data collection, and macromodel fitting. The OS energy macromodels can be used conveniently as OS energy estimators in high-level or architectural optimization of embedded systems for low-energy consumption.As far as we know, this work is the first attempt to systematically tackle energy macromodeling of an embedded OS. To demonstrate our approach, we present experimental results for two well-known embedded OSs, namely, μC/OS and embedded Linux OS.
Interview with Elisabeth and Eric Freeman
Authors: Lee Newton , Freeman Elisabeth , Freeman Eric
Published: August 2005

Elisabeth Freeman is a software developer and digital artist. A strong advocate for women in computing, Elisabeth co-founded The Ada Project (TAP) - an award-winning website for resources for women in computing. In 1995, TAP became an official volunteer project of the ACM Committee on the Status of Women (http://women.acm.org/). Elisabeth led the R&D efforts in digital media at the Walt Disney Internet Group, where she co-invented Motion, a content system that delivers terabytes of video every day to Disney, ESPN, ABC, FamilyFun, and Movies.com users. She holds graduate degrees in computer science from Yale University and Indiana University. Eric Freeman is a computer scientist with a passion for media and software architectures. He directed the Internet broadband and wireless efforts at the Walt Disney Internet Group for four years. He studied computer science with David Gelernter at Yale University and received his Ph.D. in 1997. Eric implemented tuple-space systems on Thinking Machine CM-5s and created some of the first Internet information systems for NASA in the late 80s. Eric and Elisabeth are the coauthors of the new book
Head First Design Patterns
(O'Reilly, 2004).
Stand up and take your place
Authors: Mallon Bride , Webb Brian
Published: August 2005

This article reports results from a series of empirical studies exploring narrative dimensions of adventure and role-play in computer-game design. It identifies aspects of narrative employed in such games, considers the significance of narrative structures and devices in increasing user-engagement, and reflects on game-design implications.Because not all approaches identified in traditional narrative theory can be applied to the new, interactive media, a phenomenological, reader-response methodology was used in the studies to identify narrative considerations appropriate to game-players' experiences. In two model focus-group studies, evaluative responses to games played in a controlled environment were analyzed. From the factors identified as affecting engagement, those with narrative aspects were isolated and their significance assessed. Among the factors identified are characterization, identification, agency, motivation, plot, linearity, and authorial control. Also considered is the disruption of primal narrative features of narrative--causality, temporality, and linearity--within a hyper-structure, and a number of design techniques and strategies to resolve such tensions and promote user engagement are suggested.
A Word from the Editor
Authors: Lee Newton
Published: August 2005

Welcome to ACM Computers in Entertainment, a unique magazine featuring video interviews with leading professionals and interesting articles on entertainment technology and its applications.The Interviews column features video interviews with two of our distinguished advisory board members, Kimberly Till and Rick Mandler.
Interview with Kimberly Till
Authors: Lee Newton , Till Kimberly
Published: August 2005

Interview with Kimberly Till (April 18, 2005)

Kimberly Till is vice president of Microsofts Worldwide Media & Entertainment Group (http://www.microsoft.com/presspass/exec/till/default.asp). In the video interview, Kimberly was accompanied by David Alstadter (Senior Director of Marketing, Partners, and Solutions), John Canning (Technical Evangelist of Microsoft Windows eHome Division), and Jon Weisner (Solution Specialist). You will hear what they have to say about:

What does the Worldwide Media & Entertainment Group do?
Video 1 - Kimberly Till

What are the challenges and solutions for digital asset management?
Video 2 - David Alstadter

How does the Microsoft technology benefit the entertainment industry?
Video 3 - David Alstadter and Jon Weisner

There are interactive TV programs and other special software designed to run on the Windows XP Media Center Edition PC. What are the future plans for the Media Center PC?
Video 4 - John Canning
Interview with Rick Mandler
Authors: Lee Newton , Mandler Rick
Published: August 2005

Interview with Rick Mandler (April 18, 2005)

Rick Mandler is vice president and general manager of Walt Disney Internet Group and ABCs Enhanced TV (http://corporate.disney.go.com/wdig/bios/rick_mandler.html). He and his teams have won two Emmys for their interactive TV programs. In the video interview, you will hear Ricks answers to the following questions:

What are the two Emmy award winning Interactive TV applications?
Video 1

Are there more interactive TV programs planned to run on the Windows XP Media Center Edition PC platform?
Video 2

How do you see the future of 2-screen applications vs. single-screen applications?
Video 3

I would imagine that it is easier to add interactivity to a sporting event than to a sitcom. How do you determine which television programs lend themselves to interactivity?
Video 4

How important is interactive television to ABC?
Video 5
A RIO-like technique for interactivity loss-avoidance in fast-paced multiplayer online games
Authors: Palazzi Claudio E. , Ferretti Stefano , Cacciaguerra Stefano , Roccetti Marco
Published: August 2005

The astonishing increase in the spread of the Internet has given rise to a globally connected community proficient at deploying online games for a large number of participants geographically located very far from each other. However, online games are characterized by more stringent requirements than traditional distributed applications deployed over the Internet can fulfill. Indeed, one of the key factors in determining the success of an online game is its ability to rapidly deliver events to the various game servers that maintain the state of the game over the network. We have already demonstrated [Palazzi et al. 2004] that in this context adapting RED (random early detection) techniques, borrowed from queuing management, can improve the global responsiveness of a game. However, this solution may not be sufficient for a specific class of online games. We deem that fast-paced multiplayer online games (such as shoot 'em ups, for example) in which participants have to behave frenetically, must guarantee a very high degree of interactivity, even at the cost of partially sacrificing the consistency of the game state. In this case having only a partially consistent view of the game state will not affect a player's amusement as much as delaying action-processing activity will. Hence we explore the possibility of applying a RIO-based (RED with in and out) algorithm to manage game delivery to the various game servers, in order to improve the degree of interactivity for fast-paced online games. Preliminary experimental results confirm the viability of our approach.
PLTL-partitioned model checking for reactive systems under fairness assumptions
Authors: Chouali S. , Julliand J. , Masson P.-A. , Bellegarde F.
Published: August 2005

We are interested in verifying dynamic properties of finite state reactive systems under fairness assumptions by model checking. The systems we want to verify are specified through a top-down refinement process.In order to deal with the state explosion problem, we have proposed in previous works to partition the reachability graph and to perform the verification on each part separately. Moreover, we have defined a class, called B

mod

, of dynamic properties that are
verifiable by parts
, whatever the partition. We decide if a property
P
belongs to B

mod

by looking at the form of the Büchi automaton that accepts ¬
P
. However, when a property
P
belongs to B

mod

, the property
f
⇒
P
, where
f
is a fairness assumption, does not necessarily belong to B

mod

.In this paper, we propose to use the refinement process in order to build the parts on which the verification has to be performed. We then show that with such a partition, if a property
P
is verifiable by parts and if
f
is the expression of the fairness assumptions on a system, then the property
f
⇒
P
is still verifiable by parts.This approach is illustrated by its application to the chip card protocol T = 1 using the
B
engineering design language.
Algorithmic aspects in speech recognition
Authors: Buchsbaum Adam L. , Giancarlo Raffaele
Published: August 2005

Speech recognition is an area with a considerable literature, but there is little discussion of the topic within the computer science algorithms literature. Many computer scientists, however, are interested in the computational problems of speech recognition. This paper presents the field of speech recognition and describes some of its major open problems from an algorithmic viewpoint. Our goal is to stimulate the interest of algorithm designers and experimenters to investigate the algorithmic problems of effective automatic speech recognition.
An experimental study of the basis for graph drawing algorithms
Authors: Purchase H. C. , Cohen R. F. , James M. I.
Published: August 2005

Designers of graph drawing algorithms and systems claim to illuminate application data by producing layouts that optimise measurable aesthetic qualities. Examples of these aesthetics include
symmetry
(where possible, a symmetrical view of the graph should be displayed),
minimise arc crossing
(the number of arc crossings in the display should be minimised), and
minimise bends
(the total number of bends in polyline arcs should be minimised).

The aim of this paper is to describe our work to validate these claims by performing empirical studies of human understanding of graphs drawn using various layout aesthetics. This work is important since it helps indicate to algorithm and system designers what are the aesthetic qualities most important to aid understanding, and consequently to build more effective systems.
Weight-biased leftist trees and modified skip lists
Authors: Cho Seonghun , Sahni Sartaj
Published: August 2005

We propose the weight biased leftist tree as an alternative to traditional leftist trees [CRAN72] for the representation of mergeable priority queues. A modified version of skip lists [PUGH90] that uses fixed size nodes is also proposed. Experimental results show our modified skip list structure is faster than the original skip list structure for the representation of dictionaries. Experimental results comparing weight biased leftist trees and competing priority queue structures are presented.
Lock bypassing
Authors: Yan Yong , Zhang Xiaodong
Published: August 2005

The heap representation of priority queues is one of the most widely used data structures in the design of parallel algorithms. Efficiently exploiting the parallelism of a priority heap has significant influence on the efficiency of a wide range of applications and parallel algorithms. In this paper, we propose an aggressive priority heap operating algorithm, called the lock bypassing algorithm (LB) on shared memory systems. This algorithm minimizes interference of concurrent enqueue and dequeue operations on priority heaps while keeping the strict priority property: a dequeue always returns the minimum of a heap. The unique idea that distinguishes the LB algorithm from previous concurrent algorithms on priority heaps is the use of locking-on-demand and lock-bypassing techniques to minimize locking granularity and to maximize parallelism. The LB algorithm allows an enqueue operation to bypass the locks along its insertion path until it reaches a possible place where it can perform the insertion. Meanwhile a dequeue operation also makes its locking range and locking period as small as possible by carefully tuning its execution procedure. The LB algorithm is shown to be correct in terms of deadlock freedom and heap consistency. The performance of the LB algorithm was evaluated analytically and experimentally in comparison with previous algorithms. Analytical results show that the LB algorithm reduces by half the number of locks waited for in the worst case by previous algorithms. The experimental results show that the LB algorithm outperforms previously designed algorithms by up to a factor of 2 in hold time.
At the heart of information ecologies
Authors: Ranney Frances J.
Published: August 2005

The ecological metaphor for technological systems provides a useful supplement to others dealing with the question of human control over technologies. However, it fails to develop adequately its own reliance on communication as the means whereby human values may be embedded in technologies, or to recognize the role of professional communicators
in that process.
Readability and computer documentation
Authors: Hargis Gretchen
Published: August 2005

Traditional readability concerns are alive and well, but subsumed within several more recent documentation quality efforts. For example, concerns with interestingness and translatability for global markets, with audience analysis and task sufficiency, and with reader appropriateness of technical text all involve readability, but often in ways not easily measured by any formula.
Readability formulas have even more limitations than Klare discusses
Authors: Redish Janice
Published: August 2005

A literature review reveals many technical weaknesses of readability formulas (when compared to direct usability testing with typical readers): they were developed for children s school books, not adult technical documentation;they ignore between-reader differences and the effects of content, layout, and retrieval aids on text usefulness; they emphasize
countable features at the expense of more subtle contributors to text comprehension.
Design and implementation of move-based heuristics for VLSI hypergraph partitioning
Authors: Caldwell Andrew E. , Kahng Andrew B. , Markov Igor L.
Published: August 2005

We summarize the techniques of implementing move-based hypergraph partitioning heuristics and evaluating their performance in the context of VLSI design applications. Our first contribution is a detailed software architecture, consisting of seven reusable components, that allows flexible, efficient and accurate assessment of the practical implications of new move-based algorithms and partitioning formulations. Our second contribution is an assessment of the modern context for hypergraph partitioning research for VLSI design applications. In particular, we discuss the current level of sophistication in implementation know-how and experimental evaluation, and we note how requirements for real-world partitioners - if used as motivation for research - should affect the evaluation of prospective contributions. Two "implicit decisions" in the implementation of the Fiduccia-Mattheyses heuristic are used to illustrate the difficulty of achieving meaningful experimental evaluation of new algorithmic ideas.
Finding minimum congestion spanning trees
Authors: Werneck Renato , Setubal João , da Conceicão Arlindo
Published: August 2005

Given a weighted graph G = (V, E), a positive integer k, and a penalty function wp, we want to find k spanning trees on G, not necessarily disjoint, of minimum total weight, such that the weight of each edge is subject to a penalty given by wp if it belongs to more than one tree. The objective function to be minimized is Σe∈EWe(ie), where ie is the number of times edge e appears in the solution and We(ie) = iewp(e, ie) is the aggregate cost of using edge e ie times. For the case when We is weakly convex, which should have wide application in congestion problems, we present a polynomial time algorithm; the algorithm's complexity is quadratic in k. We also present two heuristics with complexity linear in k. In an experimental study we show that these heuristics are much faster than the exact algorithm also in practice. These experiments present a diverse combination of input families (four), varying k (up to 1000), and penalty functions (two). In most inputs tested the solutions given by the heuristics were within 1% of optimal or much better, especially for large k. The worst quality observed was 3.2% of optimal.
Rapid software prototyping in molecular modeling using the biochemical algorithms library (BALL)
Authors: Boghossian N. P. , Kohlbacher O. , Lenhof H. P.
Published: August 2005

In the next century, virtual laboratories will play a key role in biotechnology. Computer experiments will not only replace some of the time-consuming and expensive real-world experiments, but they will also provide insights that cannot be obtained using "wet" experiments. The field that deals with the modeling of atoms, molecules, and their reactions is called Molecular Modeling. The advent of Life Sciences gave rise to numerous new developments in this area. However, the implementation of new simulation tools is extremely time-consuming. This is mainly due to the large amount of supporting code that is required in addition to the code necessary to implement the new idea. The only way to reduce the development time is to reuse reliable code, preferably using object-oriented approaches. We have designed and implemented BALL, the first object-oriented application framework for rapid prototyping in Molecular Modeling. By the use of the composite design pattern and polymorphism we were able to model the multitude of complex biochemical concepts in a well-structured and comprehensible class hierarchy, the BALL kernel classes. The isomorphism between the biochemical structures and the kernel classes leads to an intuitive interface. Since BALL was designed for rapid software prototyping, ease of use, extensibility, and robustness were our principal design goals. Besides the kernel classes, BALL provides fundamental components for import/export of data in various file formats, Molecular Mechanics simulations, three-dimensional visualization, and more complex ones like a numerical solver for the Poisson-Boltzmann equation.
An experimental study of priority queues in external memory
Authors: Brengel Klaus , Crauser Andreas , Ferragina Paolo , Meyer Ulrich
Published: August 2005

In this paper we compare the performance of eight different priority queue implementations: four of them are explicitly designed to work in an external-memory setting, the others are standard internal-memory queues available in the LEDA library [Mehlhorn and Näher 1999]. Two of the external-memory priority queues are obtained by engineering known internal-memory priority queues with the aim of achieving effective performance on external storage devices (i.e., Radix heaps [Ahuja et al. 1990] and array heaps [Thorup 1996]). Our experimental framework includes some simple tests, like random sequences of insert or delete-minimum operations, as well as more advanced tests consisting of intermixed sequences of update operations and "application driven" update sequences originated by simulations of Dijkstra's algorithm on large graph instances. Our variegate spectrum of experimental results gives a good picture of the features of these priority queues, thus being helpful to anyone interested in the use of such data structures on very large data sets.
A conversation and commentary on from Millwrights to Shipwrights
Authors: Jobst Jack
Published: August 2005

Through their mutual dialog, the authors answer and explore seven
questions about the audience,goals, assumptions, impact, and educational
value of R.John Brockmann s 1998 history of technical communication in the United States.
An optimal memory allocation scheme for scratch-pad-based embedded systems
Authors: Avissar Oren , Barua Rajeev , Stewart Dave
Published: August 2005

This article presents a technique for the efficient compiler management of software-exposed heterogeneous memory. In many lower-end embedded chips, often used in microcontrollers and DSP processors, heterogeneous memory units such as scratch-pad SRAM, internal DRAM, external DRAM, and ROM are visible directly to the software, without automatic management by a hardware caching mechanism. Instead, the memory units are mapped to different portions of the address space. Caches are avoided due to their cost and power consumption, and because they make it difficult to guarantee real-time performance. For this important class of embedded chips, the allocation of data to different memory units to maximize performance is the responsibility of the software.Current practice typically leaves it to the programmer to partition the data among different memory units. We present a compiler strategy that automatically partitions the data among the memory units. We show that this strategy is optimal, relative to the profile run, among all static partitions for global and stack data. For the first time, our allocation scheme for stacks distributes the stack among multiple memory units. For global and stack data, the scheme is provably equal to or better than any other compiler scheme or set of programmer annotations. Results from our benchmarks show a 44.2% reduction in runtime from using our distributed stack strategy vs. using a unified stack, and a further 11.8% reduction in runtime from using a linear optimization strategy for allocation vs. a simpler greedy strategy; both in the case of the SRAM size being 20% of the total data size. For some programs, less than 5% of data in SRAM achieves a similar speedup.
Application-adaptive intelligent cache memory system
Authors: Lee Jung-Hoon , Kim Shin-Dug , Weems Charles
Published: August 2005

This article presents the design of a simple hardware-controlled, high performance cache system. The design supports fast access time, optimal utilization of temporal and spatial localities adaptive to given applications, and a simple dynamic fetching mechanism with different fetch sizes. Support for dynamically varying the fetch size makes the cache equally effective for general-purpose as well as multimedia applications. Our cache organization and operational mechanism are especially designed to maximize temporal locality and spatial locality, selectively and adaptively. Simulation shows that the average memory access time of the proposed cache is equal to that of a conventional direct-mapped cache with eight times as much space. In addition, the simulations show that our cache achieves better performance than a 2-way or 4-way set associative cache with twice as much space. The average miss ratio, compared with the victim cache with 32-byte block size, is improved by about 41% or 60% for general applications and multimedia applications, respectively. It is also shown that power consumption of the proposed cache is around 10% to 60% lower than other cache systems that we examine. Our cache system thus offers high performance with low power consumption and low hardware cost.
Our little help machines and their invisibilities
Authors: Farkas David K.
Published: August 2005

This paper examines the four kinds of invisibility Johnson-Eilola associates with minimalist help systems: fast information access that reduces user reflection and questioning, impersonal writing style that assumes the Shannon-Weaver communication model, narrow scope that leads to training but not teaching, and interface designs that oversimplify user tasks. For each of the four, the paper questions Johnson-Eilola's conclusions. Ultimately, the problems with truncated online help systems may disappear, as help systems are increasingly linking to the web, where adequate conceptual information is often supplied and opportunities for a social context for help are available.
Data remapping for design space optimization of embedded memory systems
Authors: Rabbah Rodric M. , Palem Krishna V.
Published: August 2005

In this article, we present a novel linear time algorithm for
data remapping
, that is, (i) lightweight; (ii) fully automated; and (iii) applicable in the context of pointer-centric programming languages with dynamic memory allocation support. All previous work in this area lacks one or more of these features. We proceed to demonstrate a
novel application of this algorithm as a key step in optimizing the design of an embedded memory system.
Specifically, we show that by virtue of locality enhancements via data remapping, we may reduce the memory subsystem needs of an application by 50%, and hence concomitantly reduce the associated costs in terms of size, power, and dollar-investment (61%). Such a reduction overcomes key hurdles in designing high-performance embedded computing solutions. Namely, memory subsystems are very desirable from a performance standpoint, but their costs have often limited their use in embedded systems. Thus, our innovative approach offers the intriguing possibility of compilers playing a significant role in exploring and optimizing the design space of a memory subsystem for an embedded design. To this end and in order to properly leverage the improvements afforded by a compiler optimization,
we identify a range of measures for quantifying the cost-impact of popular notions of locality, prefetching, regularity of memory access, and others
. The proposed methodology will become increasingly important, especially as the needs for application specific embedded architectures become prevalent. In addition, we demonstrate the wide applicability of data remapping using several existing microprocessors, such as the Pentium and UltraSparc. Namely, we show that remapping can achieve a performance improvement of 20% on the average. Similarly, for a parametric research HPL-PD microprocessor, which characterizes the new Itanium machines, we achieve a performance improvement of 28% on average. All of our results are achieved using applications from the DIS, Olden and SPEC2000 suites of integer and floating point benchmarks.
Adaptive mode control
Authors: Zhou Huiyang , Toburen Mark C. , Rotenberg Eric , Conte Thomas M.
Published: August 2005

Lower threshold voltages in deep submicron technologies cause more leakage current, increasing static power dissipation. This trend, combined with the trend of larger/more cache memories dominating die area, has prompted circuit designers to develop SRAM cells with low-leakage operating modes (e.g., sleep mode). Sleep mode reduces static power dissipation, but data stored in a sleeping cell is unreliable or lost. So, at the architecture level, there is interest in exploiting sleep mode to reduce static power dissipation while maintaining high performance.Current approaches dynamically control the operating mode of large groups of cache lines or even individual cache lines. However, the performance monitoring mechanism that controls the percentage of sleep-mode lines, and identifies particular lines for sleep mode, is somewhat arbitrary. There is no way to know what the performance could be with all cache lines active, so arbitrary miss rate targets are set (perhaps on a per-benchmark basis using profile information), and the control mechanism tracks these targets. We propose applying sleep mode only to the data store and not the tag store. By keeping the entire tag store active the hardware knows what the hypothetical miss rate would be if all data lines were active, and the actual miss rate can be made to precisely track it. Simulations show that an average of 73% of I-cache lines and 54% of D-cache lines are put in sleep mode with an average IPC impact of only 1.7%, for 64 KB caches.
On energy-optimal voltage scheduling for fixed-priority hard real-time systems
Authors: Yun Han-Saem , Kim Jihong
Published: August 2005

We address the problem of energy-optimal voltage scheduling for fixed-priority hard real-time systems, on which we present a complete treatment both theoretically and practically. Although most practical real-time systems are based on fixed-priority scheduling, there have been few research results known on the energy-optimal fixed-priority scheduling problem. First, we prove that the problem is NP-hard. Then, we present a fully polynomial time approximation scheme (FPTAS) for the problem. For any ε > 0, the proposed approximation scheme computes a voltage schedule whose energy consumption is at most (1 + ε) times that of the optimal voltage schedule. Furthermore, the running time of the proposed approximation scheme is bounded by a polynomial function of the number of input jobs and 1/ε. Given the NP-hardness of the problem, the proposed approximation scheme is practically the best solution because it can compute a near-optimal voltage schedule (i.e., provably arbitrarily close to the optimal schedule) in polynomial time. Experimental results show that the approximation scheme finds more efficient (almost optimal) voltage schedules faster than the best existing heuristic.
Planning and information foraging theories
Authors: Jack Jordynn
Published: August 2005

Information foraging theory and strategic planning theory can help technical communicators think about effective research methods. A broader understanding of social theory can complement Gattis's approach by adding considerations related to underlying ideological assumptions and to how research practices are situated in the larger contexts of organizations, communities, and cultures.
Parallelizing local search for CNF satisfiability using vectorization and PVM
Authors: Iwama Kazuo , Kawai Daisuke , Miyazaki Shuichi , Okabe Yasuo , Umemoto Jun
Published: August 2005

The purpose of this paper is to speed up the local search algorithm for the CNF Satisfiability problem. Our basic strategy is to run some 10
5
independent search paths simultaneously using PVM on a vector supercomputer VPP800, which consists of 40 vector processors. Using the above parallelization and vectorization together with some improvement of data structure, we obtained 600-times speedup in terms of the number of flips the local search can make per second, compared to the original GSAT by Selman and Kautz. We ran our parallel GSAT for benchmark instances and compared the running time with those of existing SAT programs. We could observe an apparent benefit of parallelization: Especially, we were able to solve two instances that have never been solved before this paper. We also tested parallel local search for the SAT encoding of the class scheduling problem. Again we were able to get almost the best answer in reasonable time.
Implementing
HEAPSORT
with (
n
log
n
- 0.9
n
) and
QUICKSORT
with (
n
log
n
+ 0.2
n
) comparisons
Authors: Edelkamp Stefan , Stiegeler Patrick
Published: August 2005

With refinements to the
WEAK-HEAPSORT
algorithm we establish the general and practical relevant sequential sorting algorithm
INDEX-WEAK-HEAPSORT
with exactly
n
⌈log
n
⌉ - 2

⌈log
n
⌉

+ 1 ≤
n
log
n
-0.9
n
comparisons and at most
n
log
n
+ 0.1
n
transpositions on any given input. It comprises an integer array of size
n
and is best used to generate an index for the data set. With
RELAXED-WEAK-HEAPSORT
and
GREEDY-WEAK-HEAPSORT
we discuss modifications for a smaller set of pending element transpositions.If extra space to create an index is not available, with
QUICK-WEAK-HEAPSORT
we propose an efficient
QUICKSORT
variant with
n
log
n
+ 0.2
n
+
o(n)
comparisons on the average. Furthermore, we present data showing that
WEAK-HEAPSORT, INDEX-WEAK-HEAPSORT
and
QUICK-WEAK-HEAPSORT
compete with other performant
QUICKSORT
and
HEAPSORT
variants.
Efficient sorting using registers and caches
Authors: Wickremesinghe Rajiv , Arge Lars , Chase Jeffrey S. , Vitter Jeffrey Scott
Published: August 2005

Modern computer systems have increasingly complex memory systems. Common machine models for algorithm analysis do not reflect many of the features of these systems, e.g., large register sets, lockup-free caches, cache hierarchies, associativity, cache line fetching, and streaming behavior. Inadequate models lead to poor algorithmic choices and an incomplete understanding of algorithm behavior on real machines.A key step toward developing better models is to quantify the performance effects of features not reflected in the models. This paper explores the effect of memory system features on sorting performance. We introduce a new cache-conscious sorting algorithm, R-MERGE, which achieves better performance in practice over algorithms that are superior in the theoretical models. R-MERGE is designed to minimize memory stall cycles rather than cache misses by considering features common to many system designs.
Breaking cycles for minimizing crossings
Authors: Demestrescu Camil , Finocchi Irene
Published: August 2005

We consider the one-sided crossing minimization problem (CP):
given a bipartite graph
G
and a permutation

x
0

of the vertices on a layer, find a perumuation

x
1

of the vertices on the other layer which
minimizes the number of edge crossings in any straightline drawing
of
G
where vertices are placed on two parallel lines and
sorted according to

x
0

and

x
1

.
Solving CP represents a fundamental step in the construction of
aesthetically pleasing layouts of heirarchies and directed graphs,
but unfortunately this problem has been proved to be
NP-complete.

In this paper we address the strong relation between CP and the
problem of computing minimum feedback arc sets in directed graphs
and we devise a enw approximation algorithm for CP, called PM, that
exploits this dependency. We experimantally and visually compare
the performance of PM with the performance of well-known algorithms
and of recent attractive strategies. Experiments are carried out on
different families of randomly generated graphs, on pathological
instances, and on real test sets. Performance indicators include
both number of edge crossings and running time, as well as
structural measures of the problem instances. We found CP to be a
very interesting and rich problem from a combinatorial point of
view. Our results clearly separate the behavior of the algorithms,
proving the effectiveness of PM on most test sets and showing
tradeoffs between quality of the solutions and running time.
However, if the visual complexity of the drawings is considered, we
found no clear winner. This confirms the importance of optimizing
also other aesthetic criteria such as symmetry, edge length, and
angular resolution.
A Network-Flow-Based Scheduler: Design, Performance History, and Experimental Analysis
Authors: Gabow Harold , Kohno Tadayoshi
Published: August 2005

We describe a program that schedules physician attending teams
at Denver Health Medical Center. The program uses network flow
techniques to prune an exponentially sized search space. We
describe the program design, its performance history at the
hospital, and experiments on a simplified version of the
program.
An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms
Authors: Iyer Raj , Karger David , Rahul Hariharan , Thorup Mikkel
Published: August 2005

We present an experimental study of different variants of the
amortized
O
(log
2
n
)-time fully-dynamic
connectivity algorithm of Holm, de Lichtenberg, and Thorup
(STOC'98). The experiments build upon experiments provided by
Alberts, Cattaneo, and Italiano (SODA'96) on the randomized
amortized
O
(log
3
n
) fully-dynamic
connectivity algorithm of Henzinger and King (STOC'95). Our
experiments shed light upon similarities and differences between
the two algorithms. We also present a slightly modified version of
the Henzinger-King algorithm that runs in
O
(log
2
n
) time, which resulted from our experiments.
Coming soon
Authors: Lee Newton
Published: August 2005

RoBallet: Creativity Can Be Hard Fun

Learning by Doing and Learning through Play: An Exploration of
Interactivity in Virtual Environments for Children

Tools for Children to Create Physical Interactive
StoryRooms

A Friendly Face in Robotics: Sony's AIBO Entertainment Robot as
an Educational Tool

Think science! Entertainment Education in Interactive
Theaters

When Children Reflect on their Own Playing Style: Experiments
with Continuator and and Children

Edutainment: A Case Study of Interactive CD-ROM Playsets

Development and Utilization of Asobiuta KARAOKE for Elementary
Music Education Available on the Internet

and more...
Call for papers
Authors: Lee Newton
Published: August 2005

About the MagazineThe ACM Computers in Entertainment magazine (http://www.acm.org/pubs/cie.html) covers a wide range of theoretical and practical computer applications in the field of entertainment such as online games, CGI movies, interactive TV, virtual reality, and animatronics. It publishes high-quality papers on the latest development in software, hardware, and business policies that improve existing mainstream entertainment and that create new genres of entertainment. Upcoming special issues will be devoted to "Educating Children Through Entertainment," "Merging Virtual Reality and Live Performances," "Music Informatics," "Interactive Television," and "Entertainment Robots." The magazine welcomes submissions of articles from scholars and professionals involved in all aspects of entertainment technology.GUIDELINE FOR AUTHORSPapers should be submitted to the editor-in-chief via email, preferably in MS Word or RTF format. Rich media such as QuickTime and Flash movies are also acceptable. Manuscripts should contain no more than 10,000 words. Submissions should include the paper title, abstract, keywords, classification (www.acm.org/class/1998/overview.html), name of authors, their affiliation, email address, and postal address.
Breaking into the universe
Authors: Wilson Leslie
Published: August 2005

High quality interactive entertainment is educational and beneficial for children. It transports our children through fantasy to understanding, inspires them and helps them survive in a world of growing complexity.Creativity is one of the most important skills a child can learn. Just like math, language arts, and science, creativity is teachable and essential to a well-rounded personality and tolerant view of the world. More creative thinking in every sphere will go a long way towards improving our lives. So let's design games that teach creativity and computer science bound together in that unique new art form called "interactive entertainment."
Entering the education arcade
Authors: Jenkins Henry , Klopfer Eric , Squire Kurt , Tan Philip
Published: August 2005

Responding to social, economic, and technological trends which make games the most powerful medium for reaching young learners, The Education Arcade project, based in the MIT Comparative Media Studies Program, seeks to prototype games that teach, develop curricular materials which support existing commercial titles, and help prepare teachers to use games in the classroom. This article reports on the first three prototypes that are producing -- Supercharged! (electromagnetism), Environmental Detectives (environmental science) and Revolution (American History).
Self-configuring localization systems
Authors: Bulusu Nirupama , Heidemann John , Estrin Deborah , Tran Tommy
Published: August 2005

Embedded networked sensors promise to revolutionize the way we interact with our physical environment and require scalable, ad hoc deployable and energy-efficient node localization/positioning.This paper describes the motivation, design, implementation, and experimental evaluation (on sharply resource-constrained devices) of a
self-configuring
localization system using radio beacons. We identify beacon
density
as an important parameter in determining localization quality, which saturates at a transition density. We develop algorithms to improve localization quality by (i) automating placement of new beacons at low densities (HEAP) and (ii) rotating functionality among redundant beacons while increasing system lifetime at high densities (STROBE).