This paper argues for explicit consideration of data fidelity during development of context-aware systems. Increasing the amount of data captured, stored, and distributed does not always translate into into increased fidelity, and we can leverage this to avoid unnecessary energy overhead and increase device battery life. We introduce Context-Awareness Fidelity Expression (CAFE) as a framework for deliberately specifying application data fidelity adaptation with the aim of using context-awareness to reduce energy consumption.

Wireless sensor networks generate a vast amount of data. This data, however, must be sparingly extracted to conserve energy, usually the most precious resource in battery-powered sensors. When approximation is acceptable, a model-driven approach to query processing is effective in saving energy by avoiding contacting nodes whose values can be predicted or are unlikely to be in the result set. To optimize queries such as top-k, however, reasoning directly with models of joint probability distributions can be prohibitively expensive. Instead of using models explicitly, we propose to use samples of past sensor readings. Not only are such samples simple to maintain, but they are also computationally efficient to use in query optimization. With these samples, we can formulate the problem of optimizing approximate top-k queries under an energy constraint as a linear program. We demonstrate the power and flexibility of our sampling-based approach by developing a series of topk query planning algorithms with linear programming, which are capable of efficiently producing plans with better performance and novel features. We show that our approach is both theoretically sound and practically effective on simulated and real-world datasets.

No abstract available.

The increasing functionality that handheld devices have come to incorporate at lower prices make them powerful candidates for various kinds of location-aware systems and services. In this work, we describe the innards of Uhuru, an RF based in-building location tracking system that we have developed and deployed on a mobile device. Our work seeks to build upon and extend previous work in this field, providing proof of concept for location information on multiple floors in a building. We outline a history monitoring algorithm that we have devised to improve the accuracy of the system and introduce a new metric of 'Survivability', which measures the ability of history-based location tracking schemes to be able to display location information consistently. We also discuss details of a heuristic that can be used for the placement of wireless base stations to improve the delivered accuracy.

No abstract available.

Energy consumption has recently been widely recognized as a major challenge of computer systems design. This paper explores how to support energy as a first-class operating system resource. Energy, because of its global system nature, presents challenges beyond those of conventional resource management. To meet these challenges we propose the Currentcy Model that unifies energy accounting over diverse hardware components and enables fair allocation of available energy among applications. Our particular goal is to extend battery lifetime by limiting the average discharge rate and to share this limited resource among competing task according to user preferences. To demonstrate how our framework supports explicit control over the battery resource we implemented ECOSystem, a modified Linux, that incorporates our currentcy model. Experimental results show that ECOSystem accurately accounts for the energy consumed by asynchronous device operation, can achieve a target battery lifetime, and proportionally shares the limited energy resource among competing tasks.

The increasing importance of energy e ciency has produced amultitude of hardware devices with various power management features. This paper investigates memory controller policies for manipulating DRAM power states in cache-based systems. We develop an analytic model that approximates the idle time of DRAM chips using an exponential distribution, and validate our model against trace-driven simulations. Our results show that, for our benchmarks, the simple policy of immediately transitioning a DRAM chip to a lower power state when it becomes idle is superior to more sophisticated policies that try to predict DRAM chip idle time. 1.

The ability of a Web service to provide low-latency access to its contents is constrained by available network bandwidth. It is important for the service to manage available bandwidth wisely. While providing differentiated quality of service (QoS) is typically enforced through network mechanisms, in this paper we introduce a robust mechanism for managing network resources at the application level. We use transcoding to allow Web servers to customize the size of objects constituting a Web page, and hence the bandwidth consumed by that page, by dynamically varying the size of multimedia objects on a per-client basis. We leverage earlier work on characterizing quality versus size tradeoffs in transcoding JPEG images to dynamically determine the quality and size of the object to transmit. We evaluate the performance benefits of incorporating this information in a series of bandwidth management policies. We develop metrics to measure the performance of our system. We use realistic workloads and access scenarios to drive our system. The principal contribution of this work is the demonstration that it is possible to use informed transcoding techniques to provide differentiated service and to dynamically allocate available bandwidth among different client classes, while delivering a high degree of information content (quality factor) for all clients.

The ability of a Web service to provide low-latency access to its content is constrained by available network bandwidth. While providing differentiated quality of service (QoS) is typically enforced through network mechanisms, in this paper we introduce a robust mechanism for managing network resources using application-specific characteristics of Web services. We use transcoding to allow Web servers to customize the size of objects constituting a Web page, and hence the bandwidth consumed by that page, by dynamically varying the size of multimedia objects on a per-client basis. We leverage our earlier work on characterizing quality versus size tradeoffs in transcoding JPEG images to supply more information for determining the quality and size of the object to transmit. We evaluate the performance benefits of incorporating this information in a series of bandwidth management policies using realistic workloads and access scenarios to drive our system. The principal contribution of this paper is the demonstration that it is possible to use informed transcoding techniques to provide differentiated service and to dynamically allocate available bandwidth among different client classes, while delivering good quality of information content for all clients. We also show that it is possible to customize multimedia objects to the highly variable network conditions experienced by mobile clients in order to provide acceptable quality and latency depending on the networks used in accessing the service. We show that policies that aggressively transcode the larger images can produce images with quality factor values that closely follow the untranscoded base case while still saving as much as 150 kB. A transcoding policy that has knowledge of the characteristics of the link to the client can avoid as many as 40% of (unnecessary) transcodings.

Phenomenal improvements in the computational performance of multiprocessors have not been matched by comparable gains in I/O system performance. This imbalance has resulted in I/O becoming a significant bottleneck for many scientific applications. One key to overcoming this bottleneck is improving the performance of multiprocessor file systems. The design of a high-performance multiprocessor file system requires a comprehensive understanding of the expected workload. Unfortunately, until recently, no general workload studies of multiprocessor file systems have been conducted. The goal of the CHARISMA project was to remedy this problem by characterizing the behavior of several production workloads, on different machines, at the level of individual reads and writes. The first set of results from the CHARISMA project describe the workloads observed on an Intel iPSC/860 and a Thinking Machines CM-5. This paper is intended to compare and contrast these two workloads for an understanding of their essential similarities and differences, isolating common trends and platform-dependent variances. Using this comparison, we are able to gain more insight into the general principles that should guide multiprocessor file-system design.

The class of NUMA (nonuniform memory access time) shared memory architectures is becoming increasingly important with the desire for larger scale multiprocessors. In such machines, the placement and movement of code and data are crucial to performance. The operating system can play a role in managing placement through the policies and mechanisms of the virtual memory subsystem. In this paper, we develop an analytic model of memory system performance of a Local/Remote NUMA architecture based on approximate mean-value analysis techniques. The model assumes that a simple workload model based on a few parameters can often provide insight into the general behavior of real applications. The model is validated against experimental data obtained with the DUnX operating system kernel for the BBN GP1000 while running a synthetic workload. The results of this validation show that in general, model predictions are quite good, though in some cases the model fails to include the effect of unexpected behaviors in the implementation. Experiments investigate the effectiveness of dynamic multiple-copy page placement. We investigate the cost of incorrect policy decisions by introducing different percentages of policy error and measuring their effect on performance.

For given input the global trace generated by a parallel program in a shared memory multiprocessing environment may change as the memory architecture, and management policies change. A method is proposed for ensuring that a correct global trace is generated in the new environment. This method involves a new characterization of a parallel program that identifies its address change points and address affecting points. An extension of traditional process traces, called the intrinsic trace of each process, is developed. The intrinsic traces maximize the decoupling of program execution from simulation by describing the address flow graph and path expressions of each process program. At each point where an address is issued, the trace-driven simulator uses the intrinsic traces and the sequence of loads and stores before the current cycle, to determine the next address. The mapping between load and store sequences and next addresses to issue, sometimes, requires partial program reexecution. Programs that do not require partial program reexecution are called graph-traceable.>

Dynamic page placement policies for NUMA (nonuniform memory access time) shared-memory architectures are explored using two approaches that complement each other in important ways. The authors measure the performance of parallel programs running on the experimental DUnX operating system kernel for the BBN GP1000, which supports a highly parameterized dynamic page placement policy. They also develop and apply an analytic model of memory system performance of a local/remote NUMA architecture based on approximate mean-value analysis techniques. The model is validated against experimental data obtained with DUnX while running a synthetic workload. The results of this validation show that, in general, model predictions are quite good. Experiments investigating the effectiveness of dynamic page-placement and, in particular, dynamic multiple-copy page placement the cost of replication/coherency fault errors, and the cost of errors in deciding whether a page should move or be remotely referenced are described.>

Shared memory multiprocessors are attractive because they are programmed in a manner similar to uniprocessors. The UMA class of shared memory multiprocessors is the most attractive, from the programmer's point of view, since the programmer need not be concerned with the placement of code and data in the physical memory hierarchy. Scalable shared memory multiprocessors, on the other hand, tend to present at least some degree of non-uniformity of memory access to the programmer, making the NUMA class an important one to consider. In this paper, we investigate the role that DUnX, an operating system supporting dynamic page placement on a BBN GP1000, might play in simplifying the memory model presented to the applications programmer. We consider a case study of psolu, a real scientific application originally targeted for a NUMA architecture. We find that dynamic page placement can dramatically improve the performance of a simpler implementation of psolu targeted for an UMA memory architec...

The study of operating systems level memory management policies for nonuniform memory access time (NUMA) shared memory multiprocessors is an area of active research. Previous results have suggested that the best policy choice often depends on the application under consideration, while others have reported that the best policy depends on the particular architecture. Since both observations have merit, we explore the concept of policy tuning on an application/architecture basis.We introduce a highly tunable dynamic page placement policy for NUMA multiprocessors, and address issues related to the tuning of that policy to different architectures and applications. Experimental data acquired from our DUnX operating system running on two different NUMA multiprocessors are used to evaluate the usefulness, importance, and ease of policy tuning.Our results indicate that while varying some of the parameters can have dramatic effects on performance, it is easy to select a set of default parameter settings that result in good performance for each of our test applications on both architectures. This apparent robustness of our parameterized policy raises the possibility of machine-independent memory management for NUMA-class machines.

Nonuniformity of memory accessis an almost inevitable feature of the memory architecture in shared memory multiprocessor designs that can scale to large numbers of processors.One implication of NUMA architectures is that the placement and movement of code and data are crucial to performance.As memory architectures become more complex and the nonuniformity becomes less well hidden, system software must assume a larger role in providing memory management support for the programmer.This paper investigates the role of the operating system.We take an experimental approach to evaluating a wide-range of memory management policies.The target NUMA environment is BBN's GP-1OOOmultiprocessor.Extensive local modifications have been made to the memory management subsystem of BBN's nX operating system to support multiple policy implementations.Policy comparisons are based on the measured performance of real parallel applications.Our results show that there are memory management policies implemented in our system that can improve the performance of programs written using the simpler uniform memory access (UMA) programming model.While achieving the level of performance of a highly tuned NUMA program is still a difficult problem, some examples come close.There appears to be no single policy that can be considered the best over our set of test applications.Investigations into the contributions made by individual policy features toward overall behavior of the workload provide some insight into the design of a set of effective policies.

The question of whether prefetching blocks on the file into the block cache can effectively reduce overall execution time of a parallel computation, even under favorable assumptions, is considered. Experiments have been conducted with an interleaved file system testbed on the Butterfly Plus multiprocessor. Results of these experiments suggest that (1) the hit ratio, the accepted measure in traditional caching studies, may not be an adequate measure of performance when the workload consists of parallel computations and parallel file access patterns, (2) caching with prefetching can significantly improve the hit ratio and the average time to perform an I/O (input/output) operation, and (3) an improvement in overall execution time has been observed in most cases. In spite of these gains, prefetching sometimes results in increased execution times (a negative result, given the optimistic nature of the study). The authors explore why it is not trivial to translate savings on individual I/O requests into consistently better overall performance and identify the key problems that need to be addressed in order to improve the potential of prefetching techniques in the environment.>

Performance considerations affecting the design of a mechanism that preserves locality and avoids high-latency remote references called the concurrent pools data structure are explored. The effectiveness of three different implementations of concurrent pools is evaluated. Experiments performed on a BBN Butterfly multiprocessor under a variety of workloads shown that the three implementations perform similarly well for light workloads, but that with stressful workloads it appears that a simple algorithm can provide better performance than a complex algorithm, designed to keep remote accesses to a minimum. Implementations can benefit by taking into account information on the nature of the operations performed by each process to help balance the elements among processes that need them.>

The authors present a brief description of data on directory reference patterns collected from a 4.2BSD UNIX system. These data are used to examine the importance of the name lookup overhead involved in opening and using files. The analysis shows that paths in the environment are relatively long and that, in the absence of caching, name resolution overhead accounts for over 70% of the disk blocks referenced to open and use files. These results confirm recent conjectures on the high level of directory activity in UNIX file systems. Directory references exhibit strong locality, though, making caches an effective way to decrease directory overhead. Simulations of a least recently used (IRU) whole directory cache show that a cache holding just ten nodes achieves an 85% hit ratio. The implications of these results on the design of both local and distributed file systems are discussed.>

A parallel file system called Bridge that distributes each file across multiple storage devices and processors has been designed and prototyped. The approach is based on the notion of an interleaved file, in which consecutive logical blocks are assigned to different physical nodes. Naive programs are able to access files just as they would with a conventional file system, while more sophisticated programs can export pieces of their code to the processors managing the data, for optimum performance. Early analytical and experimental results indicate that Bridge will deliver good parallel speedup for configurations in excess of 32 nodes with disks. High performance is achieved by exporting the I/O-related portions of an application into the processors closest to the data. A pair of applications that illustrate this technology is presented. General issues in the design of algorithms for Bridge are discussed.>

Concurrent access to complex shared data structures, particularly structures useful as database indices, has long been of interest in the database community. In dynamic databases, tree structures such as B-trees have been used as indices because of their ability to handle growth; whereas hashing has been used for fast access in relatively static databases. Recently, a number of techniques for dynamic hashing have appeared. They address the major deficiency of traditional hashing when applied to databases that experience significant change in the amount of data being stored. This paper presents a solution that allows concurrency in one of these dynamic hashing data structures, namely linear hash files. The solution is based on locking protocols and minor modifications in the data structures.

AbstmctHashing has long been recognized as a fast method for accessing records by key in large relatively static databases.However.when the amount of data is likely to grow significantly, traditional hashing suffers from performance degradation and may eventually require rehashing all the records into a larger space.Recently, a number of techniques for dynamic hashing have appeared.In this paper, we present a solution to allow for concurrency in linear hash tiles that is based .onlocking protocols and minor modifications in the data structure.The problem .ofadapting this technique for use in a distributed system is also addressed.

The extendible hash file is a dynamic data structure that is an alternative to B-trees for use as a database index. While there have been many algorithms proposed to allow concurrent access to B trees similar solutions for extendible hash files have not appeared. In this paper, we present solutions to allow for concurrency that are based on locking protocols and minor modifications in the data structure.Another question that deserves consideration is whether these indexing structures can be adapted for use in a distributed database. Among the motivations for distributing data are increased availability and ease of growth, however, unless data structures in the access path are designed to support those goals, they may not be realized. We describe some first attempts at adapting extendible hash files for distributed data.

This paper describes programming constructs and system support functions that are intended to facilitate the programming of reliable distributed systems. The systems considered include very different kinds of computers communicating through a network. Such a heterogeneous network offers a number of advantages to designers of applications software. Different machines emphasize different capabilities and many problems naturally break down into subproblems that are best solved with specialized resources. There is clearly a need for programming tools that will allow users to exploit this kind of environment.

This paper addresses the problem of concurrent access to dynamically balanced binary search trees. Specifically, two solutions for concurrent search and insertion in AVL trees are developed. The first solution is relatively simple and is intended to allow several readers to share nodes with a writer process. The second solution uses the first as a starting point and introduces additional concurrency among writers by applying various parallelization techniques. Simulation results used to evaluate the parallel performance of these algorithms with regard to the amount of concurrency achieved and the parallel overhead incurred are summarized.

The problem of designing compilers for a multiprocessing environment is approached. We show that by modeling an existing sequential compiler, we gain an understanding of the modifications necessary to transform the sequential structure into a pipeline of processes. The pipelined compiler is then evaluated through measurements and simulation. Properties of the model, a generalized Petri Net, are also discussed.