No one likes waiting in traffic, whether on a road or on a computer network. Stuttering audio, slow interactive feedback, and untimely pauses in video annoy everyone and cost businesses sales and productivity. An ideal network should (1) minimize latency, (2) maximize bandwidth, (3) share resources according to a desired policy, (4) enable incremental deployment, and (5) minimize administrative overhead. Many technologies have been developed, but none yet satisfactorily address all five goals. The best performing solutions developed so far require controlled environments where coordinated modification of multiple components in the network is possible, but they suffer poor performance in more complex scenarios. We present TCP Inigo, which uses independent delay-based algorithms on the sender and receiver (i.e. ambidextrously) to satisfy all five goals. In networks with single administrative domains, like those in data centers, Inigo's fairness, bandwidth, and latency indices are up to 1.3X better than the best deployable solution. When deployed in a more complex environment, such as across administrative domains, Inigo possesses latency distribution tail up to 42X better.

Migrating resources is a useful tool for balancing load in a distributed system, but it is difficult to determine when to move resources, where to move resources, and how much of them to move. We look at resource migration for file system metadata and show how CephFS's dynamic subtree partitioning approach can exploit varying degrees of locality and balance because it can partition the namespace into variable sized units. Unfortunately, the current metadata balancer is complicated and difficult to control because it struggles to address many of the general resource migration challenges inherent to the metadata management problem. To help decouple policy from mechanism, we introduce a programmable storage system that lets the designer inject custom balancing logic. We show the flexibility and transparency of this approach by replicating the strategy of a state-of-the-art metadata balancer and conclude by comparing this strategy to other custom balancers on the same system.

We describe a new algorithm, called Quasi-Partitioned Scheduling (QPS), capable of scheduling any feasible system composed of independent implicit-deadline sporadic tasks on identical processors. QPS partitions the system tasks into subsets, each of which is either scheduled by EDF on a single processor or by a set of servers on two or more processors. More precisely, QPS uses an efficient scheme to switch between partitioned EDF and global-like scheduling rules in response to system load variation, providing dynamic adaptation in the system. Extensive simulation compares QPS favorably against related work, showing that it has very low preemption and migration overheads.

The MapReduce framework is being extended for domains quite different from the web applications for which it was designed, including the processing of big structured data, e.g., scientific and financial data. Previous work using MapReduce to process scientific data ignores existing structure when assigning intermediate data and scheduling tasks. In this paper, we present a method for incorporating knowledge of the structure of scientific data and executing query into the MapReduce communication model. Built in SciHadoop, a version of the Hadoop MapReduce framework for scientific data, SIDR intelligently partitions and routes intermediate data, allowing it to: remove Hadoop's global barrier and execute Reduce tasks prior to all Map tasks completing; minimize intermediate key skew; and produce early, correct results. SIDR executes queries up to 2.5 times faster than Hadoop and 37% faster than SciHadoop; produces initial results with only 6% of the query completed; and produces dense, contiguous output.

Many storage systems are shared by multiple clients with different types of workloads and performance targets. To achieve performance targets without over-provisioning, a system must provide isolation between clients. Throughput-based reservations are challenging due to the mix of workloads and the stateful nature of disk drives, leading to low reservable throughput, while existing utilization-based solutions require specialized I/O scheduling for each device in the storage system.

In applications ranging from radio telescopes to Internet traffic monitoring, our ability to generate data has outpaced our ability to effectively capture, mine, and manage it. These ultra-high-bandwidth data streams typically contain little useful information and most of the data can be safely discarded. Periodically, however, an event of interest is observed and a large segment of the data must be preserved, including data preceding detection of the event. Doing so requires guaranteed data capture at source rates, line speed filtering to detect events and data points of interest, and TiVo-like ability to save past data once an event has been detected. We present Valmar, a system for guaranteed capture, indexing, and storage of ultra-high-bandwidth data streams. Our results show that Valmar performs at nearly full disk bandwidth, up to several orders of magnitude faster than flat file and database systems, works well with both small and large data elements, and allows concurrent read and search access without compromising data capture guarantees.

Graphics processing units (GPUs) are increasingly being used for general purpose parallel computing. They provide significant performance gains over multi-core CPU systems, and are an easily accessible alternative to supercomputers. The architecture of general purpose GPU systems(GPGPU), however, poses challenges in efficiently transferring data among the host and device(s). Although commodity many core devices such as NVIDIA GPUs provide more than one way to move data around, it is unclear which method is most effective given a particular application. This presents difficulty in supporting latency-sensitive cyber-physical systems (CPS). In this work we present a new approach to data transfer in a heterogeneous computing system that allows direct communication between GPUs and other I/O devices. In addition to adding this functionality our system also improves communication between the GPU and host. We analyze the current vendor provided data communication mechanisms and identify which methods work best for particular tasks with respect to throughput, and total time to completion. Our method allows a new class of real-time cyber-physical applications to be implemented on a GPGPU system. The results of the experiments presented here show that GPU tasks can be completed in 34 percent less time than current methods. Furthermore, effective data throughput is at least as good as the current best performers. This work is part of concurrent development of Gdev, an open-source project to provide Linux operating system support of many-core device resource management.

Real-time systems and applications are becoming increasingly complex and often comprise multiple communicating tasks. The management of the individual tasks is well-understood, but the interaction of communicating tasks with different timing characteristics is less well-understood. We discuss several representative inter-task communication flows via reserved memory buffers (possibly interconnected via a real-time network) and present RAD-Flows, a model for managing these interactions. We provide proofs and simulation results demonstrating the correctness and effectiveness of RAD-Flows, allowing system designers to determine the amount of memory required based upon the characteristics of the interacting tasks and to guarantee real-time operation of the system as a whole.

Optimal multiprocessor real-time schedulers incur significant overhead for preemptions and migrations. We present RUN, an efficient scheduler that reduces the multiprocessor problem to a series of uniprocessor problems. RUN significantly outperforms existing optimal algorithms with an upper bound of O(log m) average preemptions per job on m processors (≤ than 3 per job in all of our simulated task sets) and reduces to Partitioned EDF whenever a proper partitioning is found.

Hadoop has become the de facto platform for large-scale data analysis in commercial applications, and increasingly so in scientific applications. However, Hadoop's byte stream data model causes inefficiencies when used to process scientific data that is commonly stored in highly-structured, array-based binary file formats resulting in limited scalability of Hadoop applications in science. We introduce Sci-Hadoop, a Hadoop plugin allowing scientists to specify logical queries over array-based data models. Sci-Hadoop executes queries as map/reduce programs defined over the logical data model. We describe the implementation of a Sci-Hadoop prototype for NetCDF data sets and quantify the performance of five separate optimizations that address the following goals for several representative aggregate queries: reduce total data transfers, reduce remote reads, and reduce unnecessary reads. Two optimizations allow holistic aggregate queries to be evaluated opportunistically during the map phase; two additional optimizations intelligently partition input data to increase read locality, and one optimization avoids block scans by examining the data dependencies of an executing query to prune input partitions. Experiments involving a holistic function show run-time improvements of up to 8x, with drastic reductions of IO, both locally and over the network.

In-memory tree structured index search is a fundamental database operation. Modern processors provide tremendous computing power by integrating multiple cores, each with wide vector units. There has been much work to exploit modern processor architectures for database primitives like scan, sort, join, and aggregation. However, unlike other primitives, tree search presents significant challenges due to irregular and unpredictable data accesses in tree traversal. In this article, we present FAST, an extremely fast architecture-sensitive layout of the index tree. FAST is a binary tree logically organized to optimize for architecture features like page size, cache line size, and Single Instruction Multiple Data (SIMD) width of the underlying hardware. FAST eliminates the impact of memory latency, and exploits thread-level and data-level parallelism on both CPUs and GPUs to achieve 50 million (CPU) and 85 million (GPU) queries per second for large trees of 64M elements, with even better results on smaller trees. These are 5X (CPU) and 1.7X (GPU) faster than the best previously reported performance on the same architectures. We also evaluated FAST on the Intel$^\tiny\textregistered$ Many Integrated Core architecture (Intel$^\tiny\textregistered$ MIC), showing a speedup of 2.4X--3X over CPU and 1.8X--4.4X over GPU. FAST supports efficient bulk updates by rebuilding index trees in less than 0.1 seconds for datasets as large as 64M keys and naturally integrates compression techniques, overcoming the memory bandwidth bottleneck and achieving a 6X performance improvement over uncompressed index search for large keys on CPUs.

We consider the problem of optimal real-time scheduling of periodic and sporadic tasks for identical multiprocessors. A number of recent papers have used the notions of fluid scheduling and deadline partitioning to guarantee optimality and improve performance. In this paper, we develop a unifying theory with the DP-FAIR scheduling policy and examine how it overcomes problems faced by greedy scheduling algorithms. We then present a simple DP-FAIR scheduling algorithm, DP-WRAP, which serves as a least common ancestor to many recent algorithms. We also show how to extend DP-FAIR to the scheduling of sporadic tasks with arbitrary deadlines.

Data centers often consolidate a variety of workloads to increase storage utilization and reduce management costs. Each workload, however, has its own performance targets that need to be met, requiring isolation from the effects of other workloads sharing the system. Satisfying the global throughput and latency targets of each workload is challenging in fully distributed storage systems because workloads can have different data layouts and different requests from the same workload can be serviced by different nodes. Quality of service schemes that manage individual system resources usually rely on resource reservations, often requiring assumptions about the layout of data. On the other hand, solutions for distributed storage tend to treat the storage system as a black box, metering requests issued to the system and often under-utilizing system resources.

Large radio telescopes, cyber-security systems monitoring real-time network traffic, and others have specialized data storage needs: guaranteed capture of an ultra-high-bandwidth data stream, retention of the data long enough to determine what is “interesting,” retention of interesting data indefinitely, and concurrent read/write access to determine what data is interesting, without interrupting the ongoing capture of incoming data. Mahanaxar addresses this problem. Mahanaxar guarantees streaming real-time data capture at (nearly) the full rate of the raw device, allows concurrent read and write access to the device on a best-effort basis without interrupting the data capture, and retains data as long as possible given the available storage. It has built in mechanisms for reliability and indexing, can scale to meet arbitrary bandwidth requirements, and handles both small and large data elements equally well. Results from our prototype implementation show that Mahanaxar provides both better guarantees and better performance than traditional file systems.

In-memory tree structured index search is a fundamental database operation. Modern processors provide tremendous computing power by integrating multiple cores, each with wide vector units. There has been much work to exploit modern processor architectures for database primitives like scan, sort, join and aggregation. However, unlike other primitives, tree search presents significant challenges due to irregular and unpredictable data accesses in tree traversal.

In many application areas, including control systems, careful management of system resources is key to providing the best application performance. Traditional control systems with multiple control loops statically allocate a fixed portion of the system resources to each controller based on their average or worst-case resource requirements. However, controllers' resource needs vary depending on the jobs they perform and the state of the systems they control. A controller of a plant operating close to its equilibrium requires fewer resources than a controller of a plant operating far from its equilibrium point. The Draco dynamic rate control system exploits this fact by dynamically allocating resources to control systems based on system state. Our research demonstrates that Draco provides significantly better overall control performance with much less resources than static controllers. Our experimental evaluation shows that in the control scenarios we examined Draco provides up to 25% better control performance with 30% less resources.

Guaranteed I/O performance is needed for a variety of applications ranging from real-time data collection to desktop multimedia to large-scale scientific simulations. Reservations on throughput, the standard measure of disk performance, fail to effectively manage disk performance due to the orders of magnitude difference between best-, average-, and worst-case response times, allowing reservation of less than 0.01 % of the achievable bandwidth. We show that by reserving disk resources in terms of utilization it is possible to create a disk scheduler that supports reservation of nearly 100 % of the disk resources, provides arbitrarily hard or soft guarantees depending upon application needs, and yields efficiency as good or better than best-effort disk schedulers tuned for performance. We present the architecture of our scheduler, prove the correctness of its algorithms, and provide results demonstrating its effectiveness.

Large- and small-scale storage systems frequently serve a mixture of workloads, an increasing number of which require some form of performance guarantee. Providing guaranteed disk performance - the equivalent of a "virtual disk" - is challenging because disk requests are non-preemptible and their execution times are stateful, partially non-deterministic, and can vary by orders of magnitude. Guaranteeing throughput, the standard measure of disk performance, requires worst-case I/O time assumptions orders of magnitude greater than average I/O times, with correspondingly low performance and poor control of the resource allocation. We show that disk time utilization- analogous to CPU utilization in CPU scheduling and the only fully provisionable aspect of disk performance - yields greater control, more efficient use of disk resources, and better isolation between request streams than bandwidth or I/O rate when used as the basis for disk reservation and scheduling.

To offset the significant power demands of hard disk drives in computer systems, drives are typically powered down during idle periods. This saves power, but accelerates duty cycle consumption, leading to earlier drive failure. Hybrid disks with a small amount of non-volatile flash memory (NVCache) are coming on the market. We present four I/O subsystem enhancements that exploit the characteristics of hybrid disks to improve system performance: 1) artificial idle periods, 2) a read-miss cache, 3) anticipatory spin-up, and 4) NVCache write-throttling. These enhancements reduce power consumption, duty cycling, NVCache block-erase impact, and the observed spinup latency of a hybrid disk, resulting in lower power consumption, greater reliability, and faster I/O.

Dynamic storage tiering (DST) is the concept of grouping storage devices into tiers based on their characteristics, and relocating files dynamically to leverage on the heterogeneity of the underlying devices. An important usage of DST is activity-based file relocation, where less active files can be stored on less expensive devices without affecting the overall perceived quality of the storage system. In activity-based file relocation, improper choices on how much activity a file should have before it is relocated introduce the potential for overcommitting the performance capability of the preferred tier. We present an approach to prevent performance degradation caused by excessive skewing of loads. Our approach enables the delineation of periods when performance requirements are different. We consider the load pattern of files and limit the total amount of loads to be placed on the preferred tier during the periods when fast response time is desirable, and increase the load limit in other periods when throughput is more important. Considering the variation of performance requirements in time enables the finer attainment of QoS goals.

One of the biggest bottlenecks in desktop-based computing is the hard disk with I/O write latency being a key contributor. I/O write latency stems from the mechanical nature of hard disks, with seek and rotational delays the major components. Hybrid disk drives place a small amount of flash memory (NVCache) on the drive itself which can be leveraged by the host and has the potential to increase I/O performance and reduce hard disk power consumption. We present an I/O scheduling algorithm, "Flash-Backed I/O Requests", which leverages the on-board flash to reduce write latency. Since flash memory and rotating media have different I/O characteristics, predominantly in random access context, an I/O scheduler can decide which media will most efficiently service I/O requests. Our results show that with Flash-Backed I/O requests, overall write latency can be reduced by up to 70%.

Being one of the few mechanical components in a typical computer system, hard drives consume a significant amount of the overall power used by a computer. Spinning down a hard drive reduces its power consumption, but only works when no disk accesses occur, limiting overall effectiveness. We have designed and implemented a technique to extend disk spin-down times using a small non-volatile storage cache called NVCache, which contains a combination of caching techniques to service reads and writes while the hard disk is in low-power mode. We show that combining NVCache with an adaptive disk spin-down algorithm, a hard disk’s power consumption can be reduced by up to 90%.

The simple notion of soft real-time processing has fractured into a spectrum of diverse soft real-time types with a variety of different resource and time constraints. Schedulers have been developed for each of these types, but these are essentially point solutions in the space of soft real-time and no detailed unified definition of soft real-time has previously been provided that includes all types of soft realtime processing. We present a complete real-time taxonomy covering the spectrum of processes from best-effort to hard real-time. The taxonomy divides processes into nine classes based on their resource and timeliness requirements and includes four soft real-time classes, each of which captures a group of soft real-time applications with similar characteristics. We exploit the different features of each of the soft real-time classes to integrate all of them into a single scheduler together with hard real-time and best-effort processes and present results demonstrating their performance

Emerging large-scale distributed storage systems are faced with the task of distributing petabytes of data among tens or hundreds of thousands of storage devices. Such systems must evenly distribute data and workload to efficiently utilize available resources and maximize system performance, while facilitating system growth and managing hardware failures. We have developed CRUSH, a scalable pseudorandom data distribution function designed for distributed object-based storage systems that efficiently maps data objects to storage devices without relying on a central directory. Because large systems are inherently dynamic, CRUSH is designed to facilitate the addition and removal of storage while minimizing unnecessary data movement. The algorithm accommodates a wide variety of data replication and reliability mechanisms and distributes data in terms of user-defined policies that enforce separation of replicas across failure domains.

MEMS-based storage is an emerging nonvolatile secondary storage technology. It promises high performance, high storage density, and low power consumption. With fundamentally different architectural designs from magnetic disk, MEMS-based storage exhibits unique two-dimensional positioning behaviors and efficient power state transitions. We model these low-level, device-specific properties of MEMS-based storage and present request scheduling algorithms and power management strategies that exploit the full potential of these devices. Our simulations show that MEMS-specific device management policies can significantly improve system performance and reduce power consumption.

As an emerging nonvolatile secondary storage technology, MEMS-based storage exhibits several desirable properties including high performance, high storage volumic density, low power consumption, low entry cost, and small form factor. However, MEMS-based storage provides a limited amount of storage per device and is likely to be more expensive than magnetic disk. Systems designers will therefore need to make trade-offs to achieve well-balanced designs. We present an architecture in which MEMS devices are organized into MEMS storage enclosures with online spares. Such enclosures are proven to be highly reliable storage building bricks with no maintenance during their economic lifetimes. We also demonstrate the effectiveness of using MEMS as another layer in the storage hierarchy, bridging the cost and performance gap between MEMS storage and disk. We show that using MEMS as a disk cache can significantly improve system performance and cost-performance ratio.

Traditional file systems provide a weak and inadequate structure for meaningful representations of file interrelationships and other context-providing metadata. Existing designs, which store additional file-oriented metadata either in a database, on disk, or both are limited by the technologies upon which they depend. Moreover, they do not provide for user-defined relationships among files. To address these issues, we created the linking file system (LiFS), a file system design in which files may have both arbitrary user- or application-specified attributes, and attributed links between files. In order to assure performance when accessing links and attributes, the system is designed to store metadata in non-volatile memory. This paper discusses several use cases that take advantage of this approach and describes the user-space prototype we developed to test the concepts presented.

To determine whether a user can access a file in a hierarchical file system a traversal of the directory hierarchy is required in order to check access control for all the parent directories. This traversal can be especially expensive in a distributed system where the files may be on separate devices. We present two approaches for representing the complete access control for a file and its parent directories such that it can be stored locally with each file in order to avoid traversal. We use the well-known CNF and DNF (conjunctive and disjunctive normal form) formats to store permission and ownership information compactly for the entire path to a file. An examination of the structure of an existing large shared file system demonstrates the efficacy of our solution.

Non-volatile storage technologies such as flash memory, magnetic RAM (MRAM), and MEMS-based storage are emerging as serious alternatives to disk drives. Among these, MEMS storage is predicted to be the least expensive and highest density, and at about 1 ms access times still considerably faster than hard disk drives. Like the other emerging non-volatile storage technologies, it is highly suitable for small mobile devices but it is expensive to replace hard drives entirely. Its non-volatility, dense storage, and high performance still make it an ideal candidate for the secondary storage subsystem. We examine the use of MEMS storage in the storage hierarchy and show that using a technique called MEMS caching disk, we can achieve 30-49% of the pure MEMS storage performance by using only a small amount (3% of the disk capacity) of MEMS storage in conjunction with a standard hard drive. The resulting system is ideally suited for commercial packaging with a small MEMS device included as part of a standard disk controller or paired with a disk.

Systems that use or serve multimedia data require timely access to data on hard drives. To ensure adequate performance users must either prevent overload of disk resources, or use real-time algorithms that rely on intricate knowledge of disk internals to meet deadline requirements. We have developed Hierarchical Disk Sharing (HDS) to allow disks to be fully utilized while sustaining a bandwidth reservation, without requiring detailed knowledge of the drive internals. HDS uses a hierarchy of token bucket filters to isolate disk access among clients and groups of clients, and to allow for reclaiming of unused bandwidth. We discuss the design of HDS and present our implementation in a Linux block device driver, demonstrating the effectiveness (and limitations) of this approach.

Modern operating systems frequently support applications with a variety of timing constraints including hard real-time, soft real-time, and best-effort. To guarantee performance, critical applications typically over-reserve resources based on worst-case resource usage estimates, while others may reserve based on average-case or other estimates. When resources are fully subscribed, the performance of soft- and non-real-time applications depends upon the effective distribution of dynamic slack - reserved, but unused resources - from other tasks. Motivated by several representative examples, we derive four general principles for the effective management of slack. We have implemented these principles in four progressively better slack schedulers that demonstrate their effectiveness. BACKSLASH, which employs all four principles, misses fewer soft realtime deadlines than all of the other slack schedulers we examined

Summary form only given. Traditional real-time systems require a priori knowledge of process period and worst-case execution times in order to guarantee application and system performance. Traditional static worst-case execution time analysis has been developed to support this requirement. However, real-time systems have grown beyond static applications developed for unchanging and well-documented hardware and software architectures. They now include (perhaps predominately) a large variety of highly dynamic applications, written by a large number of developers inexperienced with traditional real-time design, and executed on widely varying hardware and software platforms in competition with greedy best-effort applications with unknown processing characteristics. In such an environment, static timing analysis or specification is useless. This sea change in application and system characteristics requires a corresponding change in the tools and techniques used to characterize the application requirements and to meet those requirements. In many instances, dynamic analysis is the only possibly solution.

Most research on QoS-aware storage has focused on the use of QoS-aware disk schedulers. However, the increasing intelligence and autonomy of modern disk drives have made fine-grained external disk scheduling difficult. As this trend continues, providing QoS-aware storage through external disk schedulers may become infeasible in the future. In this paper, we present a coarse-grained approach to storage bandwidth management that does not rely on external disk schedulers. The goal is to provide better storage access support for storage-bound soft real-time applications. Our approach gives priority to disk requests generated by soft real-time applications by controlling the rate that best-effort disk requests may be dispatched.

Demand for real-time capability in general-purpose systems is rising and as systems are retrofitted with scheduling features they become increasingly complex. To counter this trend we present the best-effort bandwidth server (BEBS), an aperiodic server for flexible and efficient support of best-effort applications in a real-time system. Recognizing that the responsiveness of a server depends on its period, and that not every best-effort task requires equal responsiveness, the algorithm adjusts its period based on run-time behavior of tasks. We created a prototype implementation of the system to demonstrate that it performs suitably as a general-purpose scheduler in comparison to Linux, and outperforms a common type of hierarchy used in existing general-purpose systems. The result is a system that integrates real-time scheduling with best-effort support, both simple and powerful enough to be used as the only scheduler in a general-purpose operating system.

In many application areas, including control systems, careful management of system resources is key to providing the best application performance. Most traditional resource management techniques for real-time systems with multiple control loops are based on open-loop strategies that statically allocate a constant CPU share to each controller, independent of their current resource needs. This provides average control performance with minimal overhead but in general fails to provide the best performance possible within the available resources. We show that by using feedback to dynamically allocate resources to controllers as a function of the current state of their controlled systems, control performance can be significantly improved. We present an optimal resource allocation policy that maximizes control performance within the available resources and provide experimental results showing that the optimal policy 1) significantly increases control performance compared to traditional control system implementations (by more than 20% in our experiments), 2) maximizes control performance over other feedback-based policies, 3) saves resources when perturbations occur infrequently, and 4) incurs negligible overhead.

In petabyte-scale distributed file systems that decouple read and write from metadata operations, behavior of the metadata server cluster will be critical to overall system performance and scalability. We present a dynamic subtree partitioning and adaptive metadata management system designed to efficiently manage hierarchical metadata workloads that evolve over time. We examine the relative merits of our approach in the context of traditional workload partitioning strategies, and demonstrate the performance, scalability and adaptability advantages in a simulation environment.

Real-time systems are growing in complexity and real-time and soft real-time applications are becoming common in general-purpose computing environments. Thus, there is a growing need for scheduling solutions that simultaneously support processes with a variety of different timeliness constraints. Toward this goal we have developed the resource allocation/dispatching (RAD) integrated scheduling model and the rate-based earliest deadline (RBED) integrated multi-class real-time scheduler based on this model. We present RAD and the RBED scheduler and formally prove the correctness of the operations that RBED employs. We then describe our implementation of RBED and present results demonstrating how RBED simultaneously and seamlessly supports hard real-time, soft real-time, and best-effort processes.

We are constructing caching policies that have 13-20% lower miss rates than the best of twelve baseline policies over a large variety of request streams. This represents an improvement of 49–63% over Least Recently Used, the most commonly implemented policy. We achieve this not by designing a specific new policy but by using on-line Machine Learning algorithms to dynamically shift between the standard policies based on their observed miss rates. A thorough experimental evaluation of our techniques is given, as well as a discussion of what makes caching an interesting on-line learning problem.

Magnetic RAM (MRAM) is a new memory technology with access and cost characteristics comparable to those of conventional dynamic RAM (DRAM) and the non-volatility of magnetic media such as disk. Simply replacing DRAM with MRAM will make main memory non-volatile, but it will not improve file system performance. However, effective use of MRAM in a file system has the potential to significantly improve performance over existing file systems. The HeRMES file system will use MRAM to dramatically improve file system performance by using it as a permanent store for both file system data and metadata. In particular, metadata operations, which make up over 50% of all file system requests [14], are nearly free in HeRMES because they do not require any disk accesses. Data requests will also be faster, both because of increased metadata request speed and because using MRAM as a non-volatile cache will allow HeRMES to better optimize data placement on disk. Though MRAM capacity is too small to replace disk entirely, HeRMES will use MRAM to provide high-speed access to relatively small units of data and metadata, leaving most file data stored on disk.

Real-time computing models that are based on benefit (also called utility and value) offer a generic paradigm that captures the spectrum from hard- to firm- to soft-realtime requirements. Furthermore, it allows robust, flexible real-time systems to be developed. Thus, it is the authors' opinion that benefit will become increasingly important in the theory and the practice of real-time computing. This paper discusses the notion of benefit in real-time systems and considers issues that must be addressed in order to fully exploit benefit-based models. It discusses how benefit is used in a variety of real-time paradigms and in example applications. It also identifies various types of benefit and presents a taxonomy that organizes the types. 1

Correct prediction of file accesses can improve system performance by mitigating the relative speed difference between CPU and disks. This paper discusses Program-based Last Successor (PLS) and presents Program- and Userbased Last Successor (PULS), file prediction algorithms that utilize information about the program and user that access the files. Our simulation results show that PLS makes 21% fewer incorrect predictions and PULS makes 24% fewer incorrect predictions than last-successor with roughly the same number of correct predictions that lastsuccessor makes. The cache space wasted on incorrect predictions can be reduced accordingly. We also show that a cache using the Least Recently Used (LRU) caching algorithm can perform better when the PULS is applied. In some cases, a cache using LRU and either PLS or PULS performs better than a cache up to 40 times larger using LRU alone.

In contemporary computers and networks of computers, various application domains are making increasing demands on the system to move data from one place to another, particularly under some form of soft real-time constraint. A brute force technique for implementing applications in this type of domain demands excessive system resources, even though the actual requirements by different parts of the application vary according to the way it is being used at the moment. A more sophisticated approach is to provide applications with the ability to dynamically adjust resource requirements according to their precise needs, as well as the availability of system resources. This paper describes a set of principles for designing systems to provide support for soft real-time applications using dynamic negotiation. Next, the execution level abstraction is introduced as a specific mechanism for implementing the principles. The utility of the principles and the execution level abstraction is then shown in the design of three resource managers that facilitate dynamic application adaptation: Gryphon, EPA/RT-PCIP, and the DQM architectures.

High bandwidth applications with time-dependent resource requirements demand certain resource level assurances in order to operate correctly. Quality of service resource management techniques are being successfully developed that allow network systems to provide such assurances. These solutions generally assume that the operating system at either end of the network is capable of handling the throughput requirements of the applications. However, real operating systems have to manage many concurrent applications with varying resource requirements. Without specialized support, the operating system cannot guarantee the resources needed for any particular application. In support of these kinds of applications we have developed a middleware agent called a dynamic QoS manager (DQM) that mediates application resource usage so as to ensure that applications get the resources they need in order to provide adequate performance. The DQM employs a variety of algorithms to determine application resource allocations. Using application QoS levels, it provides for resource availability based algorithmic variation within applications and varying application periods. It also allows for inaccurate application resource usage estimates through a technique we have developed called dynamic estimate refinement. The paper discusses new developments in the design of the DQM and presents results showing DQM performance with both real and synthetic applications.

Flexible operation of a robotic agent in an uncalibrated environment requires the ability to recover unknown or partially known parameters of the workspace through sensing. Of the sensors available to a robotic agent, visual sensors provide information that is richer and more complete than other sensors. In this paper we present robust techniques for the derivation of depth from feature points on a target's surface and for the accurate and high-speed tracking of moving targets. We use these techniques in a system that operates with little or no a priori knowledge of object- and camera-related parameters to robustly determine such object-related parameters as velocity and depth. Such determination of extrinsic environmental parameters is essential for performing higher level tasks such as inspection, exploration, tracking, grasping, and collision-free motion planning. For both applications, we use the Minnesota robotic visual tracker (MRVT) (a single visual sensor mounted on the end-effector of a robotic manipulator combined with a real-time vision system) to automatically select feature points on surfaces, to derive an estimate of the environmental parameter in question, and to supply a control vector based upon these estimates to guide the manipulator.

NULL Convention Logic (NCL) is a symbolically complete logic which expresses process completely in terms of the logic itself and inherently and conveniently expresses asynchronous digital circuits. The traditional form of Boolean logic is not symbolically complete in the sense that it requires the participation of a fundamentally different form of expression, time in the form of the clock, which has to be very carefully coordinated with the logic part of the expression to completely and effectively express a process. We introduce NULL Convention Logic in relation to Boolean logic as a four value logic, and as a three value logic and finally as two value logic quite different from traditional Boolean logic. We then show how systems can be constructed entirely in terms of NULL Convention Logic.

Flexible operation of a robotic agent in an uncalibrated environment requires the ability to recover unknown or partially known parameters of the workspace through sensing. Of the sensors available to a robotic agent, visual sensors provide information that is richer and more complete than other sensors. In this paper we present robust techniques for the derivation of depth from feature points on a target's surface and for the accurate and high-speed tracking of moving targets. We use these techniques in a system that operates with little or no a priori knowledge of the object- and camera-related parameters to robustly determine such object-related parameters as velocity and depth. Such determination of extrinsic environmental parameters is essential for performing higher level tasks such as inspection, exploration, tracking, grasping, and collision-free motion planning. For both applications, we use the Minnesota Robotic Visual Tracker (a single visual sensor mounted on the end-effector of a robotic manipulator combined with a real-time vision system) to automatically select feature points on surfaces, to derive an estimate of the environmental parameter in question, and to supply a control vector based upon these estimates to guide the manipulator.>

Flexible operation of a robotic agent in an uncalibrated environment requires the ability to recover unknown or partially known parameters of the workspace through sensing. Of the sensors available to a robotic agent, visual sensors provide information that is richer and more complete than other sensors. In this paper we present robust techniques for the derivation of depth from feature points on a target's surface and for the accurate and high-speed tracking of moving targets. We use these techniques in a system that operates with little or no a priori knowledge of the object-related parameters present in the environment. The system is designed under the controlled active vision framework and robustly determines parameters such as velocity for tracking moving objects and depth maps of objects with unknown depths and surface structure. Such determination of intrinsic environmental parameters is essential for performing higher level tasks such as inspection, exploration, tracking grasping, and collision-free motion planning. For both applications, we use the Minnesota Robotic Visual Tracker (a single visual sensor mounted on the end-effector of a robotic manipulator combined with a real-time vision system) to automatically select feature points on surfaces, to derive an estimate of the environmental parameter in question, and to apply a control vector based upon these estimates to guide the manipulator. The paper concludes with applications of these techniques to transportation problems such as vehicle tracking.>