bluuebunny/crossref_metadata_2025 huggingface dataset:
Reliability and security of RAID storage systems and D2D archives using SATA disk drives
Authors: Hughes Gordon F. , Murray Joseph F.
Published: August 2005

Information storage reliability and security is addressed by using personal computer disk drives in enterprise-class nearline and archival storage systems. The low cost of these serial ATA (SATA) PC drives is a tradeoff against drive reliability design and demonstration test levels, which are higher in the more expensive SCSI and Fibre Channel drives. This article discusses the tradeoff between SATA which has the advantage that fewer higher capacity drives are needed for a given system storage capacity, which further reduces cost and allows higher drive failure rates, and the use of additional storage system redundancy and drive failure prediction to maintain system data integrity using less reliable drives. RAID stripe failure probability is calculated using typical ATA and SCSI drive failure rates, for single and double parity data reconstruction failure, and failure due to drive unrecoverable block errors. Reliability improvement from drive failure prediction is also calculated, and can be significant. Today's SATA drive specifications for unrecoverable block errors appear to allow stripe reconstruction failure, and additional in-drive parity blocks are suggested as a solution. The possibility of using low cost disks data for backup and archiving is discussed, replacing higher cost magnetic tape. This requires significantly better RAID stripe failure probability, and suitable drive technology alternatives are discussed. The failure rate of nonoperating drives is estimated using failure analysis results from ≈4000 drives. Nonoperating RAID stripe failure rates are thereby estimated. User data security needs to be assured in addition to reliability, and to extend past the point where physical control of drives is lost, such as when drives are removed from systems for data vaulting, repair, sale, or discard. Today, over a third of resold drives contain unerased user data. Security is proposed via the existing SATA drive secure-erase command, or via the existing SATA drive password commands, or by data encryption. Finally, backup and archival disc storage is compared to magnetic tape, a technology with a proven reliability record over the full half-century of digital data storage. In contrast, tape archives are not vulnerable to tape transport failure modes. Only failure modes in the archived tapes and reels will make data unrecoverable.
A study of level-of-detail in haptic rendering
Authors: Payandeh Shahram , Dill John , Zhang Jian
Published: August 2005

This paper presents an initial study of an approach to reduce computational overhead in haptic rendering of physically based models. Haptic rendering refers to the notion of adding physical properties and behavior, specifically a sense of touch or force feedback, to models of objects. In this way, a user through a haptic feedback device can feel interaction forces while visually observing the objects. Physically based modeling is particularly important when representing deformable objects. In this paper, an approach based on a mass-spring damper system is used in modeling deformable objects. Deformation due to interaction forces is obtained by solving a set of differential equations, a process that is in general computationally demanding. To reduce this demand, the notion of level-of-detail in haptic rendering is introduced. Here the interplay between the graphical mesh and the haptic mesh as a function of various levels of subdivision is studied. The approach we describe is to adjust model parameters such that the user feels the same reaction force for a given deformation, regardless of the level of local subdivision.A preliminary user study with simple objects suggests there can be a local subdivision threshold such that the user cannot distinguish between global subdivision and the local subdivision introduced by the level-of-detail algorithm. This conclusion is beneficial for haptic rendering of deformable objects. Similar conclusions were obtained for haptic rendering of rigid objects. These results can be used as a guideline for other approaches to modeling deformable objects, such as finite element representations.
Memory safety without garbage collection for embedded applications
Authors: Dhurjati Dinakar , Kowshik Sumant , Adve Vikram , Lattner Chris
Published: August 2005

Traditional approaches to enforcing memory safety of programs rely heavily on run-time checks of memory accesses and on garbage collection, both of which are unattractive for embedded applications. The goal of our work is to develop advanced compiler techniques for enforcing memory safety with minimal run-time overheads. In this paper, we describe a set of compiler techniques that, together with minor semantic restrictions on C programs and no new syntax, ensure memory safety and provide most of the error-detection capabilities of type-safe languages, without using garbage collection, and with no run-time software checks, (on systems with standard hardware support for memory management). The language permits arbitrary pointer-based data structures, explicit deallocation of dynamically allocated memory, and restricted array operations. One of the key results of this paper is a compiler technique that ensures that dereferencing dangling pointers to freed memory does not violate memory safety,
without annotations, run-time checks, or garbage collection
, and works for arbitrary type-safe C programs. Furthermore, we present a new interprocedural analysis for static array bounds checking under certain assumptions. For a diverse set of embedded C programs, we show that we are able to ensure memory safety of pointer and dynamic memory usage
in all these programs
with no run-time software checks (on systems with standard hardware memory protection), requiring only minor restructuring to conform to simple type restrictions. Static array bounds checking fails for roughly half the programs we study due to complex array references, and these are the only cases where explicit run-time software checks would be needed under our language and system assumptions.
China great wall digital cultural heritage
Authors: Hylton Eldon C.
Published: August 2005

Early in 2004 the Chinese government established a foundation whose mission is to protect and preserve the Great Wall of China and to articulate the Bo Da Jing Sheng or "profound esteem" that emanates from the 3,000 years of history encompassing the Great Wall. The Great Wall is the cultural icon of China, and is directly linked to China's long history. The China Great Wall Society (CGWS) and IMC have recently executed a letter of intent that together we will utilize state-of-the-art digital technologies and apply them to the preservation and protection of the Great Wall and to the creation of content to disseminate the history and knowledge embodied in this unique cultural heritage. The Great Wall represents a time-line of Chinese history.On September 1, 2004, Xu Jia Lu of the National People's Congress and chairman of the China Great Wall Society emphasized the need to formulate a five-year plan to retrieve, protect, restore, and develop a Great Wall database that can be utilized for future research, educational purposes, and the dissemination internationally of China's cultural heritage. The Great Wall project is multi-dimensional in scope, with two complementary missions: (1) physical and virtual restoration of the Great Wall, and (2) the development of a Great Wall database. The goal of the plan is to bring knowledge of the Great Wall to the world and to leave the children of China a Great Wall that is physically preserved and its underlying cultural heritage appreciated internationally.
Interview with Bill Kinder
Authors: Lee Newton , Kinder Bill
Published: August 2005

Bill Kinder is the Director of Editorial and Postproduction at the Pixar Animation Studios. He is also the DVD Producer for Pixar movies, including the Academy award-winning films "The Incredibles (2004)" and "Finding Nemo (2003)," which earned the honor of being the fastest selling DVD and video of all time. Prior to joining Pixar in 1996, Bill was the Director of Facilities at American Zoetrope in San Francisco. There he coordinated sound and picture post production on numerous feature films (including "Jack," "Mi Familia," and "Theremin: An Electronic Odyssey"), introduced innovations in Francis Coppola's Electronic Storyboard Department, and oversaw the film-to-tape transfers of dailies. He has also directed an Emmy-nominated documentary, produced television news, and edited commercials. Bill studied film, sound, and photography at Brown University, Rhode Island School of Design, and the University of East Anglia.
Understanding entertainment
Authors: Schell Jesse
Published: August 2005

Stories and games, which historically have been considered radically different experiences with different principles of construction, actually have many underlying commonalities. Although we view stories as passive and linear, and games as active and nonlinear, during both types of experience, a participant (or guest) is mentally active, and having a linear experience. The way to gauge the quality of the guest's experience is through a system of interest curves, which measure interest over time, and interest is shown to be made of three components: inherent interest, poetry of presentation, and psychological proximity. Finally, this paper introduces the idea of indirect control, which is a method of secretly controlling the desires of a guest, allowing a designer to imbue a non-linear interactive experience with structures typically used in traditional storytelling.
Interactive tv
Authors: Loizides Lydia
Published: August 2005

Interactive television has been on the brink of taking off since the mid-1980s. Unfortunately, downward economic shifts, social resistance, and technological failure have hampered the growth of iTV. Is the current status of iTV any better? Can iTV shed its tattered image? Moreover, are there revenue-generating opportunities for content owners, distributors, aggregators, agencies, and advertisers? The answer, by all accounts, is yes.
IATAC: a smart predictor to turn-off L2 cache lines
Authors: Abella Jaume , González Antonio , Vera Xavier , O'Boyle Michael F. P.
Published: August 2005

As technology evolves, power dissipation increases and cooling systems become more complex and expensive. There are two main sources of power dissipation in a processor: dynamic power and leakage. Dynamic power has been the most significant factor, but leakage will become increasingly significant in future. It is predicted that leakage will shortly be the most significant cost as it grows at about a 5× rate per generation. Thus, reducing leakage is essential for future processor design. Since large caches occupy most of the area, they are one of the leakiest structures in the chip and hence, a main source of energy consumption for future processors.This paper introduces
IATAC
(inter-access time per access count), a new hardware technique to reduce cache leakage for L2 caches.
IATAC
dynamically adapts the cache size to the program requirements turning off cache lines whose content is not likely to be reused. Our evaluation shows that this approach outperforms all previous state-of-the-art techniques.
IATAC
turns off 65% of the cache lines across different L2 cache configurations with a very small performance degradation of around 2%.
Improving storage system availability with D-GRAID
Authors: Sivathanu Muthian , Prabhakaran Vijayan , Arpaci-Dusseau Andrea C. , Arpaci-Dusseau Remzi H.
Published: August 2005

We present the design, implementation, and evaluation of D-GRAID, a gracefully degrading and quickly recovering RAID storage array. D-GRAID ensures that most files within the file system remain available even when an unexpectedly high number of faults occur. D-GRAID achieves high availability through aggressive replication of semantically critical data, and fault-isolated placement of logically related data. D-GRAID also recovers from failures quickly, restoring only live file system data to a hot spare. Both graceful degradation and live-block recovery are implemented in a prototype SCSI-based storage system underneath unmodified file systems, demonstrating that powerful “file-system like” functionality can be implemented within a “semantically smart” disk system behind a narrow block-based interface.
Mining block correlations to improve storage performance
Authors: Li Zhenmin , Chen Zhifeng , Zhou Yuanyuan
Published: August 2005

Block correlations are common semantic patterns in storage systems. They can be exploited for improving the effectiveness of storage caching, prefetching, data layout, and disk scheduling. Unfortunately, information about block correlations is unavailable at the storage system level. Previous approaches for discovering file correlations in file systems do not scale well enough for discovering block correlations in storage systems.In this article, we propose two algorithms,
C-Miner
and
C-Miner
*, that use a data mining technique called
frequent sequence mining
to discover block correlations in storage systems. Both algorithms run reasonably fast with feasible space requirement, indicating that they are practical for dynamically inferring correlations in a storage system.
C-Miner
is a direct application of a frequent-sequence mining algorithm with a few modifications; compared with
C-Miner
,
C-Miner
* is redesigned for mining block correlations by making concessions for the specific problem of long sequences in storage system traces. Therefore,
C-Miner
* can discover 7--109% more correlation rules within 2--15 times shorter time than
C-Miner
. Moreover, we have also evaluated the benefits of block correlation-directed prefetching and data layout through experiments. Our results using real system workloads show that correlation-directed prefetching and data layout can reduce average I/O response time by 12--30% compared to the base case, and 7--25% compared to the commonly used sequential prefetching scheme for most workloads.
Adaptive data structures for IP lookups
Authors: Ioannidis Ioannis , Grama Ananth , Atallah Mikhail
Published: August 2005

The problem of efficient data structures for IP lookups has been well studied in the literature. Techniques such as LC tries and extensible hashing are commonly used. In this paper, we address the problem of generalizing LC tries, based on traces of past lookups, to provide performance guarantees for memory suboptimal structures. As a specific example, if a memory-optimal (LC) trie takes 6 MB and the total memory at the router is 8 MB, how should the trie be modified to make best use of the 2 MB of excess memory? We present a greedy algorithm for this problem and prove that, if for the optimal data structure there are
b
fewer memory accesses on average for each lookup compared with the original trie, the solution produced by the greedy algorithm will have at least 9 ×
b
/11 fewer memory accesses on average (compared to the original trie). An efficient implementation of this algorithm presents significant additional challenges. We describe an implementation with a time complexity of
O
(ξ(
d
)
n
log
n
) and a space complexity of
O
(
n
), where
n
is the number of nodes of the trie and
d
its depth. The depth of a trie is fixed for a given version of the Internet protocol and is typically
O
(log
n
). In this case, ξ(
d
) =
O
(log
2
n
). We also demonstrate experimentally the performance and scalability of the algorithm on actual routing data.
Combining supervisor synthesis and model checking
Authors: Ziller Roberto , Schneider Klaus
Published: August 2005

Model checking and supervisor synthesis have been successful in solving different design problems related to discrete systems in the last decades. In this paper, we analyze some advantages and drawbacks of these approaches and combine them for mutual improvement. We achieve this through a generalization of the supervisory control problem proposed by Ramadge and Wonham. The objective of that problem is to synthesize a supervisor which constrains a system's behavior according to a given specification, ensuring controllability and coaccessibility. By introducing a new representation of the solution using systems of μ-calculus equations, we are able to handle these two conditions separately and thus to exchange the coaccessibility requirement by any condition that could be used in model checking. Well-known results on μ-calculus model checking allow us to easily assess the computational complexity of any generalization. Moreover, the model checking approach also delivers algorithms to solve the generalized synthesis problem. We include an example in which the coaccessibility requirement is replaced by fairness constraints. The paper also contains an analysis of related work by several authors.
A reprogrammable customization framework for efficient branch resolution in embedded processors
Authors: Petrov Peter , Orailoglu Alex
Published: August 2005

We present a customization framework for embedded processors which employs the utilization of application-specific information, thus specializing the processor's microarchitecture to the application needs. The increased processor utilization leads to a low-cost system implementation with no sacrifice in performance requirements and to reduced custom hardware in a typical SOC. We illustrate these ideas through the branch resolution problem, known to impose severe performance degradation on control-dominated embedded applications. A customization approach for early branch resolution and subsequent folding is presented. The application-specific information is captured by the microarchitecture through a low-cost reprogrammable hardware, thus attaining the twin benefits of processor standardization and application-specific customization. Experimental results show that for a representative set of control-dominated applications a reduction in the range of 3--22% in processor cycles can be achieved, thus extending the scope of low-cost embedded processors in complex codesigns for control intensive systems.
The design, implementation, and evaluation of adaptive code unloading for resource-constrained devices
Authors: Zhang Lingli , Krintz Chandra
Published: August 2005

Java Virtual Machines (JVMs) for resource-constrained devices, e.g., hand-helds and cell phones, commonly employ interpretation for program translation. However, compilers are able to produce significantly better code quality, and, hence, use device resources more efficiently than interpreters, since compilers can consider large sections of code concurrently and exploit optimization opportunities. Moreover, compilation-based systems store code for reuse by future invocations obviating the redundant computation required for reinterpretation of repeatedly executed code.However, code storage required for compilation can increase the memory footprint of the virtual machine (VM) significantly. As a result, for devices with limited memory resources, this additional code storage may preclude some programs from executing, significantly increase memory management overhead, and substantially reduce the amount of memory available for use by the application.To address the limitations of native code storage, we present the design, implementation, and empirical evaluation of a compiled-code management system that can be integrated into any compilation-based JVM. The system unloads compiled code to reduce the memory footprint of the VM. It does so by dynamically identifying and unloading dead or infrequently used code; if the code is later reused, it is recompiled by the system. As such, our system adaptively trades off memory footprint and its associated memory management costs, with recompilation overhead. Our empirical evaluation shows that our code management system significantly reduces the memory requirements of a compile-only JVM, while maintaining the performance benefits enabled by compilation.We investigate a number of implementation alternatives that use dynamic program behavior and system resource availability to determine
when
to unload as well as
what
code to unload. From our empirical evaluation of these alternatives, we identify a set of strategies that enable significant reductions in the memory overhead required for application code. Our system reduces code size by 36--62%, on average, which translates into significant execution-time benefits for the benchmarks and JVM configurations that we studied.
Automatic summarization of voicemail messages using lexical and prosodic features
Authors: Koumpis Konstantinos , Renals Steve
Published: August 2005

This aticle presents trainable methods for extracting principal content words from voicemail messages. The short text summaries generated are suitable for mobile messaging applications. The system uses a set of classifiers to identify the summary words with each word described by a vector of lexical and prosodic features. We use an ROC-based algorithm, Parcel, to select input features (and classifiers). We have performed a series of objective and subjective evaluations using unseen data from two different speech recognition systems as well as human transcriptions of voicemail speech.
Towards efficient human machine speech communication
Authors: Tomko Stefanie , Harris Thomas K. , Toth Arthur , Sanders James , Rudnicky Alexander , Rosenfeld Roni
Published: August 2005

This research investigates the design and performance of the Speech Graffiti interface for spoken interaction with simple machines. Speech Graffiti is a standardized interface designed to address issues inherent in the current state-of-the-art in spoken dialog systems such as high word-error rates and the difficulty of developing natural language systems. This article describes the general characteristics of Speech Graffiti, provides examples of its use, and describes other aspects of the system such as the development toolkit. We also present results from a user study comparing Speech Graffiti with a natural language dialog system. These results show that users rated Speech Graffiti significantly better in several assessment categories. Participants completed approximately the same number of tasks with both systems, and although Speech Graffiti users often took more turns to complete tasks than natural language interface users, they completed tasks in slightly less time.
The influence of caches on the performance of heaps
Authors: LaMarca Anthony , Ladner Richard
Published: August 2005

As memory access times grow larger relative to processor cycle
times, the cache performance of algorithms has an increasingly
large impact on overall performance. Unfortunately, most commonly
used algorithms were not designed with cache performance in mind.
This paper investigates the cache performance of implicit heaps. We
present optimizations which significantly reduce the cache misses
that heaps incur and improve their overall performance. We present
an analytical model called collective analysis that allows cache
performance to be predicted as a function of both cache
configuration and algorithm configuration. As part of our
investigation, we perform an approximate analysis of the cache
performance of both traditional heaps and our improved heaps in our
model. In addition empirical data is given for five architectures
to show the impact our optimizations have on overall performance.
We also revisit a priority queue study originally performed by
Jones [25]. Due to the increases in cache miss penalties, the
relative performance results we obtain on today's machines differ
greatly from the machines of only ten years ago. We compare the
performance of implicit heaps, skew heaps and splay trees and
discuss the difference between our results and Jones's.
Irredundant intervals
Authors: Knuth Donald E.
Published: August 2005

This expository note presents simplifications of a theorem due to Győri and an algorithm due to Franzblau and Kleitman: Given a family F of m intervals on a linearly ordered set of n elements, we can construct in O(m+n)2 steps an irredundant subfamily having maximum cardinality, as well as a generating family having minimum cardinality. The algorithm is of special interest because it solves a problem analogous to finding a maximum independent set, but on a class of objects that is more general than a matroid. This note is also a complete, runnable computer program, which can be used for experiments in conjunction with the public-domain software of The Stanford GraphBase.
Predicting string search speed
Authors: Gittleman Arthur
Published: August 2005

String search is fundamental in many text processing applications. Sunday recently gave several algorithms to find the first occurrence of a pattern string as a substring of a text, providing experimental data from searches in a text of about 200K characters to support his claim that his algorithms are faster than the standard Boyer-Moore algorithm.

We present a methodology for the average-case analysis of the performance of string search algorithms---for such algorithms, a worst-case analysis does not yield much useful information, since the performance of the algorithm is directly affected by such characteristics as the size of the character set, the character frequencies, and the structure of the text. Knuth described a finite automaton which can be used to save information about character comparisons. Baeza-Yates, Gonnet, and Regnier gave a probabilistic analysis of the worst- and average-case behavior of a string search algorithm based upon such an automaton. We construct Knuth automata to model Sunday's algorithms and use the methods of Baeza-Yates et al. to obtain an average-case analysis which confirms Sunday's experimental data.
An empirical study of dynamic graph algorithms
Authors: Alberts David , Cattaneo Giuseppe , Italiano Giuseppe F.
Published: August 2005

The contributions of this paper are both of theoretical and of experimental nature. From the experimental point of view, we conduct an empirical study on some dynamic connectivity algorithms which where developed recently. In particular, the following implementations were tested and compared with simple algorithms: simple sparsification by Eppstein et al. and the recent randomized algorithm by Henzinger and King. In our experiments, we considered both random and non-random inputs. Moreover, we present a simplified variant of the algorithm by Henzinger and King, which for random inputs was always faster than the original implementation. For non-random inputs, simple sparsification was the fastest algorithm for small sequences of updates; for medium and large sequences of updates, the original algorithm by Henzinger and King was faster.

From the theoretical point of view, we analyze the average case running time of simple sparsification and prove that for dynamic random graphs its logarithmic overhead vanishes.
Implementation of dynamic trees with in-subtree operations
Authors: Radzik Tomasz
Published: August 2005

We describe an implementation of dynamic trees with "in-subtree" operations. Our implementation follows Sleator and Tarjan's framework of dynamic-tree implementations based on splay trees. We consider the following two examples of "in-subtree" operations. (a) For a given node v, find a node with the minimum key in the subtree rooted at v. (b) For a given node v, find a random node with key X in the subtree rooted at v (value X is fixed throughout the whole computation). The first operation may provide support for edge deletions in the dynamic minimum spanning tree problem. The second one may be useful in local search methods for degree-constrained minimum spanning tree problems. We conducted experiments with our dynamic-tree implementation within these two contexts, and the results suggest that this implementation may lead to considerably faster codes than straightforward approaches do.
Issues of online research repositories from the perspective of the biomedical sciences
Authors: Armbruster David L.
Published: August 2005

This commentary on Joseph Y. Halperns proposal for a computing research repository discusses difference in traditions and practices
of online publishing and repositories between computing and biomedicals ciences. Issues of accessibility and archiving are also discussed.
A memetic algorithm to schedule planned maintenance for the national grid
Authors: Burke E. K. , Smith A. J.
Published: August 2005

The combination of local search operators, problem specific information and a genetic algorithm has provided very good results in certain scheduling problems, particularly in timetabling and maintenance scheduling problems. The resulting algorithm from this hybrid approach has been termed a Memetic Algorithm. This paper investigates the use of such an algorithm for the scheduling of transmission line maintenance for a known problem that has been addressed in the literature using a combination of a genetic algorithm and greedy optimisers.This problem is concerned with the scheduling of maintenance for an electricity transmission network where every transmission line must be maintained once within a specified time period. The objective is to avoid situations where sections of the network are disconnected, and to minimise the overloading of lines which are in service.In this paper we look at scheduling maintenance for the South Wales region of the national transmission network. We present and discuss, in some detail, a memetic algorithm that incorporates local search operators including tabu search and simulated annealing. A comparison is made both with the results from previous work, and against a selection of optimising techniques.The approach presented in this paper shows a significant improvement over previously published results on previously tackled problems. We also present results on another problem which has not been tackled in the literature but which is closer to the real world maintenance scheduling problems faced by such companies as The National Grid Company plc using the South Wales region.
A computational study of routing algorithms for realistic transportation networks
Authors: Jacob R. , Marathe M. , Nagel K.
Published: August 2005

We carry out an experimental analysis of a number of shortest-path (routing) algorithms investigated in the context of the TRANSIMS (TRansportation ANalysis and SIMulation System) project. The main focus of the paper is to study how various heuristic as well as exact solutions and associated data structures affect the computational performance of the software developed for realistic transportation networks. For this purpose we have used a road network representing, with high degree of resolution, the Dallas Fort-Worth urban area.We discuss and experimentally analyze various one-to-one shortest-path algorithms. These include classical exact algorithms studied in the literature as well as heuristic solutions that are designed to take into account the geometric structure of the input instances.Computational results are provided to compare empirically the efficiency of various algorithms. Our studies indicate that a modified Dijkstra's algorithm is computationally fast and an excellent candidate for use in various transportation planning applications as well as ITS related technologies.
Implementing weighted b-matching algorithms
Authors: Müller-Hannemann M. , Schwartz A.
Published: August 2005

We present a case study on the design of an implementation of a fundamental combinatorial optimization problem: weighted b-matching. Although this problem is well-understood in theory and efficient algorithms are known, only little experience with implementations is available. This study was motivated by the practical need for an efficient b-matching solver as a subroutine in our approach to a mesh refinement problem in computer-aided design (CAD).The intent of this paper is to demonstrate the importance of flexibility and adaptability in the design of complex algorithms, but also to discuss how such goals can be achieved for matching algorithms by the use of design patterns. Starting from the basis of the famous blossom algorithm we explain how to exploit in different ways the flexibility of our software design which allows an incremental improvement of efficiency by exchanging subalgorithms and data structures.In a comparison with a code by Miller and Pekny we also demonstrate that our implementation is even without fine-tuning very competitive. Our code is significantly faster, with improvement factors ranging between 15 and 466 on TSPLIB instances.
Fast hierarchical clustering and other applications of dynamic closest pairs
Authors: Eppstein David
Published: August 2005

We develop data structures for dynamic closest pair problems with arbitrary distance functions, that do not necessarily come from any geometric structure on the objects. Based on a technique previously used by the author for Euclidean closest pairs, we show how to insert and delete objects from an n-object set, maintaining the closest pair, in O(n log2 n) time per update and O(n) space. With quadratic space, we can instead use a quadtree-like structure to achieve an optimal time bound, O(n) per update. We apply these data structures to hierarchical clustering, greedy matching, and TSP heuristics, and discuss other potential applications in machine learning, Gröbner bases, and local improvement algorithms for partition and placement problems. Experiments show our new methods to be faster in practice than previously used heuristics.
Improving memory performance of sorting algorithms
Authors: Xiao Li , Zhang Xiaodong , Kubricht Stefan A.
Published: August 2005

Memory hierarchy considerations during sorting algorithm design and implementation play an important role in significantly improving execution performance. Existing algorithms mainly attempt to reduce capacity misses on direct-mapped caches. To reduce other types of cache misses that occur in the more common set-associative caches and the TLB, we restructure the mergesort and quicksort algorithms further by integrating tiling, padding, and buffering techniques and by repartitioning the data set. Our study shows that substantial performance improvements can be obtained using our new methods.
Product, process, and profit
Authors: Mirel Barbara
Published: August 2005

In research and in practice,usability specialists commonly target the technology user-interfaces and help as the main arena for bringing about usability improvements. However, usability improvements depend on more than innovative and user-centered technical designs and implementations. Equally important for creating useful and usable software are the social and political forces that shape the development context. These forces give rise to leadership conflicts, factional disputes, renegade efforts, alliances and betrayals, all of which profoundly influence whether usability improvements will be supported and sustained within and across projects. This essay presents and analyzes a case history of a software start-up company in which usability achieved a Pyrrhic victory, triumphing only in the short run because of social and political forces.
From NoteCards to the web
Authors: Dobroth Kate
Published: August 2005

The issues that Frank Halasz describes in "Reflections on NoteCards" are relevant to both creating and browsing through hypermedia networks. In order to bring hypermedia out of research labs and into widespread use, it was necessary to first focus on issues related to browsing, specifically, in making information easy to find. It was also necessary to integrate computation with hypermedia in order to create worthwhile applications. Now that users are comfortable accomplishing basic tasks on the Web, there is increasing interest in developing more complex, collaborative applications. For this reason, the issues that involved authoring and support for collaborative work have new relevance today.
Frequent value locality and its applications
Authors: Yang Jun , Gupta Rajiv
Published: August 2005

By analyzing the behavior of a set of benchmarks, we demonstrate that a small number of distinct values tend to occur very frequently in memory. On an average, only eight of these frequent values were found to occupy 48% of memory locations for the benchmarks studied. In addition, we demonstrate that the identity of frequent values remains stable over the entire execution of the program and these values are scattered fairly uniformly across the allocated memory. We present three different algorithms for finding frequent values and experimentally demonstrate their effectiveness. Each of these algorithms is designed to suit a different application scenario. Since the contents of memory exhibit frequent value locality, it is expected that frequent values will be observed in data streams that flow across different points in the memory hierarchy. We exploit this observation for developing two low-power designs: a low-power level-one data cache and a low-power external data bus. In each of these applications a different form of encoding of frequent values is employed to obtain a low-power design. We also experimentally demonstrate the effectiveness of these designs.
We neurotic amateurs
Authors: Sauer Geoffrey
Published: August 2005

The assertion that technical communicators tend to be `amateurs'---that is, lovers of their work--- is a claim with little foundation. Arguments toward regimentation and systematization of documentation writing are not calls to professionalize a currently-immature field, but rather attempts to emulate the hierarchy we have seen implemented in microprocessor engineering in the 1970s, software development in the 1980s, and content management in the 1990s. Such `egoless' methods may offer advantages to employers, but should not necessarily be considered `progress.'
Notes toward a socially informed pedagogy for computer documentation
Authors: Selber Stuart A.
Published: August 2005

This article extends Johnson-Eilola's main argument and then, using a thought experiment, examines an extended example of its implications. The experiment follows a student who learns how to produce technical communication artifacts following the philosophy that informs most technical communication classes and that leads to production of the functional but not conceptual systems Johnson-Eilola critiques. The article concludes by recommending changes in overall curricula and in individual courses that would better educate communicators to account for the social implications of their work.
Reply to commentaries on "XML and the new design regime"
Authors: Wilkes Gilbert Vanburen
Published: August 2005

The author responds by agreeing with some of the commentator's points and by clarifying his meaning related to others. He also offers additional discussion and references to the literature concerning some of the article's ideas.
Response to the commentaries on
Producing Quality Technical Information
Authors: Dean Morris
Published: August 2005

The editor and principal writer of Producing Quality Technical Information (1983) responds to the commentaries: answering questions about the sources of PQTI; discussing what the System Information group at IBM's Santa Teresa Laboratory were doing about usability from 1979 to 1983; comparing the predecessor nine "ease-of-use factors" with the seven "qualities" of PQTI and the nine "quality characteristics" of Prentice Hall's subsequent editions of PQTI, published under the title Developing Quality Technical Information; and revealing his own motives and thought processes in working on several usability initiatives in the laboratory at that time, including the publication of PQTI.
Access pattern-based memory and connectivity architecture exploration
Authors: Grun Peter , Dutt Nikil , Nicolau Alex
Published: August 2005

Memory accesses represent a major bottleneck in embedded systems power and performance. Traditionally, designers tried to alleviate this problem by relying on a simple cache hierarchy, or a limited use of special purpose memory modules such as stream buffers. Although real-life applications contain a large number of memory references to a diverse set of data structures, a significant percentage of all memory accesses in the application are generated from a few memory instructions that exhibit predictable, well-known access patterns; this creates an opportunity for memory customization, targeting the needs of these access patterns. We present APEX, an approach that extracts, analyzes and clusters the most active access patterns in the application, and aggressively customizes the memory architecture to match the needs of the application. Moreover, though the memory modules are important, the rate at which the memory system can produce the data for the CPU is significantly impacted by the connectivity architecture between the memory subsystem and the CPU. Thus, it is critical to consider the connectivity architecture early in the design flow, in conjunction with the memory architecture. We couple the exploration of memory modules together with their connectivity, to evaluate a wide range of cost, performance, and energy connectivity architectures. We use a heuristic to prune the design space, guiding the exploration towards the most promising designs. We present experiments on a set of large real-life benchmarks, showing significant performance improvements for varied cost and power characteristics, allowing the designer to evaluate customized memory and connectivity configurations for embedded systems.
Low-energy off-chip SDRAM memory systems for embedded applications
Authors: Shim Hojun , Joo Yongsoo , Choi Yongseok , Lee Hyung Gyu , Chang Naehyuck
Published: August 2005

Memory systems are dominant energy consumers, and thus many energy reduction techniques for memory buses and devices have been proposed. For practical energy reduction practices, we have to take into account the interaction between a processor and cache memories together with application programs. Furthermore, energy characterization of memory systems must be accurate enough to justify various techniques. In this article, we build an in-house energy simulator for memory systems that is accelerated by special hardware support while maintaining accuracy. We explore energy behavior of memory systems for various values of the processor and memory clock frequencies and cache configuration. Each experiment is performed with 24M instruction steps of real application programs to guarantee accuracy.The simulator is based on precise energy characterization of memory systems including buses, bus drivers, and memory devices by a cycle-accurate energy measurement technique. We characterize energy consumption of each component by an energy state machine whose states and transitions are associated with the dynamic and static energy costs, respectively. Our approach easily characterizes the energy consumption of complex SDRAMs. We divide and quantify energy components of main memory systems for high-level reduction. The energy simulator enables us to devise practical energy reduction schemes by providing the actual amount of reduction out of the total energy consumption in main memory systems. We introduce several practical energy reduction techniques for SDRAM memory systems and demonstrate energy reduction ratio over the SDRAM memory systems with commercial SDRAM controller chipsets. We classify the SDRAM memory systems into high-performance and mid-performance classes and achieve suitable system configurations for each class. For instance, a typical high-performance 32-bit, 64 MB SDRAM memory system consumes 19.6 mJ, 33.8 mJ, 35.4 mJ, and 37.0 mJ for 24M instructions of an MP3 decoder, a JPEG compressor, a JPEG decompressor, and an MPEG4 decoder, respectively. Our reduction scheme saves 12.7 mJ, 15.1 mJ, 15.5 mJ, and 14.8 mJ, and the reduction ratios are 64.8%, 44.6%, 43.8%, and 40.1%, respectively, without compromising execution speed.
Portable list ranking
Authors: Lassous Isabelle Guérin , Gustedt Jens
Published: August 2005

We present and analyze two portable algorithms for the List Ranking Problem in the Coarse Grained Multicomputer model (CGM). We report on implementations of these algorithms and experiments that were done with these on a variety of parallel and distributed architectures, ranging from PC clusters to a mainframe parallel machine. With these experiments, we validate the chosen CGM model, and also show the possible gains and limits of such algorithms.
Solving a "Hard" problem to approximate an "Easy" one
Authors: Fekete Sándor P. , Meijer Henk , Rohe André , Tietze Walter
Published: August 2005

We consider geometric instances of the Maximum Weighted Matching Problem (MWMP) and the Maximum Traveling Salesman Problem (MTSP) with up to 3,000,000 vertices. Making use of a geometric duality relationship between MWMP, MTSP, and the Fermat-Weber-Problem (FWP), we develop a heuristic approach that yields in near-linear time solutions as well as upper bounds. Using various computational tools, we get solutions within considerably less than 1% of the optimum.An interesting feature of our approach is that, even though an FWP is hard to compute in theory and Edmonds' algorithm for maximum weighted matching yields a polynomial solution for the MWMP, the practical behavior is just the opposite, and we can solve the FWP with high accuracy in order to find a good heuristic solution for the MWMP.
Heuristics, Experimental Subjects, and Treatment Evaluation in Bigraph Crossing Minimization
Authors: Stallmann Matthias , Brglez Franc , Ghosh Debabrata
Published: August 2005

The bigraph crossing problem, embedding the two node sets of a bipartite graph along two parallel lines so that edge crossings are minimized, has applications to circuit layout and graph drawing. Experimental results for several previously known and two new heuristics suggest continued exploration of the problem, particularly sparse instances. We emphasize careful design of experimental subject classes and present novel views of the results. All source code, data, and scripts are available on-line
Acknowledgements
Authors: Lee Newton
Published: August 2005

Issue Acknowledgements

Flash homepage design
— Alex Lieu, Jonny Rodriquez, Michael Borys— 3-Pin Media

Flash animation and sound effects
— Jay Popeski, Jeffrey Blyseth— Axis Graphics

Video recording
— John Michael Ferrari, Eric Huff

Video and sound editing
— Eric Huff

Copyediting and Proofreading
— Roma Simon, Irma Strolia, Cathy Georges

Student volunteers
— Armen Aghaeian, Jessica Chavez

Producer
— Newton Lee

Also thanks to all authors, interviewees, reviewers, editorial board advisors, Mark Mandelbaum and the entire ACM staff for their support.
Squeakers
Authors: Rose Kim
Published: August 2005

What have Alan Kay and his research team been up to for the past few years? Our Spring issue of ACM Computers in Entertainment will include a report from Alan and his colleagues on their work with children and adults around the globe.In 2001 Kay founded Viewpoints Research Institute, Inc. -- a non-profit organization that serves as the umbrella for further research and development of new learning and media development systems. In 2002 Kay joined the Hewlett-Packard Company as a Sr. Fellow at HP Labs while maintaining the non-profit organization.Alan and his team have been working in their Labs and in classrooms, community-learning centers, and with universities worldwide to continue R&D of Squeak and other collaborative, online learning environments. Look for a report on their work and findings this Spring!For a sneak peek, visit http://www.squeakland.org/sqmedia/movies/html/clips.html
Java Games Technologies
Authors: Twilleager Doug
Published: August 2005

Sun Microsystems has formed a new Games Technologies Group. Playing on Sun's strengths in network and high performance computing, the Games Technologies Group is working with industry leaders to provide an end-to-end architecture and set of solutions for developing and deploying networked games. More information on the Java technology that you can use now to develop games is available at http://community.java.net/games/ We will have an in depth article detailing the work of this new group.