Recent developments in non-volatile memory and networking technologies raise new challenges and opportunities for architecting storage systems. In this paper we propose Telepathy, a lightweight data access protocol for NVRAM+RDMA-based distributed storage systems. Telepathy is a fully distributed protocol whose I/O writes can be coordinated by any server node, and I/O reads can be served by any of the replicas. Telepathy guarantees strongly-consistent reads while providing high I/O concurrency. Hybrid RDMA operations are used to transmit data directly and efficiently to the NVRAM of target servers. The correctness of Telepathy is verified with a formal proof of consistency, and its performance is validated with YCSB benchmarks on the Chameleon cluster. Telepathy can achieve low I/O latencies and high throughput, with low CPU utilization.

This paper describes a new resource allocation policy for partitioning the cycles of a multiprocessor among concurrent multi-threaded jobs, together with a novel scheduler implementation in the Linux kernel. Each job consists of tasks whose execution times are drawn from some discrete distribution. Our policy shifts the established application-centric allocation to task-centric allocation by treating the server as a set of logical servers and dividing their joint resources fairly. We maximize task throughput while maintaining client fairness. We designed and developed the OPT scheduler for the Linux kernel, and obtain significant gains in resource utilization over CFS for various workloads. Our OPT scheduler adapts to dynamic workloads and can schedule multi-threaded clients efficiently to implement our resource allocation policy.

Advances in persistent memory and networking hardware are changing the architecture of storage systems and data management services in datacenters. Distributed, one-sided RDMA access to memory-resident data shows tremendous improvements in throughput, latency and server CPU utilization of storage servers. However, the silent nature of one-sided I/O simultaneously creates new challenging problems for providing QoS in such systems. In this paper, we propose Haechi, a work-conserving, token-based QoS mechanism to guarantee reservations and limits in storage systems that provide one-sided I/O services. Haechi decouples QoS enforcement into a QoS engine at the client and a QoS monitor at the data node. It leverages adaptive token dispatch, token conversion, and silent I/O reporting to guarantee the reservations of distributed clients while maintaining high server utilization. Empirical evaluations on the Chameleon cluster, with different reservation distributions and I/O access patterns, show that Haechi is successful in providing differentiated QoS with negligible overhead for token management.

Advances in storage, processing, and networking hardware are changing the structure of distributed applications. RDMA networks provide multiple communication mechanisms that enable novel hybrid protocols specialized to different data transfer requirements. In this paper, we present a distributed communication scheme that separates control and data communication channels directly at the RNIC rather than the application level. We develop a new communication artifact, a remote random access buffer, to efficiently implement this separation. Data messages are sent silently to the receiver, which is informed of the location of the data by a subsequent control message. Experiments on an RDMA-enabled cluster with micro benchmarks and two distributed applications validate the performance benefits of our approach.

Managing the trade-off between efficiency and fairness in a storage system is challenging due to high variability in workload behavior. Most workloads are made up of a mix of asymmetric operations (e.g. read/write, sequential/random, or striped/isolated I/Os) in different proportions, which places different resource demands on the storage device. The problem is to allocate device resources to the heterogeneous workloads fairly while maintaining high device throughput. In this paper, we present a new model for fair allocation of heterogeneous workloads with different ratios of asymmetric operations. We propose an adaptive scheme that chooses between two policies-the traditional Time-Balanced Allocation (TBA) and our proposed Bottleneck-Balanced Allocation (BBA)-based on workload characteristics. The fairness and throughput of these allocation policies are established through formal analysis. Our algorithms are tested with an adaptive, dynamic scheduler implemented in a simulation testbed, and the results validate the performance benefits of our approach.

Providing performance QoS (Quality-of-Service) guarantees in a distributed data center environment poses unique challenges. In a typical setting, a client must be guaranteed a minimum amount of service (its contractual reservation) aggregated over all servers on which it has demand for service. A server may receive service demands from multiple clients, which may in aggregate exceed its service capacity. The system must decide how much service to provide to each client on each server that it has demand, in order to satisfy all clients' reservations. In case there is no feasible allocation of the service, the amount of reservation that is fulfilled must be maximized. In practice, the number of clients is several orders of magnitude larger than the number of servers.

The paper addresses the problem of providing performance QoS guarantees in a clustered storage system. Multiple related storage objects are grouped into logical containers called buckets, which are distributed over the servers based on the placement policies of the storage system. QoS is provided at the level of buckets. The service credited to a bucket is the aggregate of the IOs received by its objects at all the servers. The service depends on individual time-varying demands and congestion at the servers. We present a token-based, coarse-grained approach to providing IO reservations and limits to buckets. We propose pShift, a novel token allocation algorithm that works in conjunction with token-sensitive scheduling at each server to control the aggregate IOs received by each bucket on multiple servers. pShift determines the optimal token distribution based on the estimated bucket demands and server IOPS capacities. Compared to existing approaches, pShift has far smaller overhead, and can be accelerated using parallelization and approximation. Our experimental results show that pShift provides accurate QoS among the buckets with different access patterns, and handles runtime demand changes well.

Providing latency support is an important problem for clustered storage systems. In this paper, we present Fair-EDF, a framework for latency guarantees in shared storage servers. It provides fairness control while supporting latency guarantees. Fair-EDF extends the pure earliest deadline first (EDF) scheduler by adding a controller to shape the workloads. Under overload it selects a minimal number of requests to drop and to choose the dropped requests in a fair manner. The evaluation results show Fair-EDF provides steady fairness control among a set of clients with different runtime behaviors.

We consider the problem of providing QoS guarantees in a clustered storage system whose data is distributed over multiple server nodes. Storage objects are encapsulated in a single logical bucket and QoS is provided at the level of buckets. The service that a single bucket receives is the aggregate of the service it receives at the nodes holding its constituent objects. The service depends on individual time-varying service demands and congestion at the physical servers. In this paper, we present bQueue, a coarse-grained scheduling algorithm that provides reservation and limit QoS for buckets in a distributed storage system, using tokens to control the amount of service received at individual storage servers. bQueue uses the max-flow algorithm to periodically determine the optimal token distribution based on the demands of the buckets at different servers and the QoS parameters of the buckets. Our experimental results show that bQueue provides accurate QoS among the buckets with different access patterns, and handles runtime demand changes in a reasonable way.

This paper addresses the problem of creating durable transactions in byte-addressable Non-Volatile Memory or Persistent Memory (PM) when using Hardware Transactional Memory (HTM)-based concurrency control. It shows how HTM transactions can be ordered correctly and atomically into PM by the use of a novel software protocol combined with a Persistent Memory Controller, without requiring changes to processor cache hardware or HTM protocols. In contrast, previous approaches require significant changes to existing processor microarchitectures. Our approach, evaluated using both micro-benchmarks and the STAMP suite compares well with standard (volatile) HTM transactions. It also yields significant gains in throughput and latency in comparison with persistent transactional locking.

This paper addresses the challenges of coupling byte addressable non-volatile memory (NVM) and hardware transaction memory (HTM) in high-performance transaction processing. We first show that HTM transactions can be ordered using existing processor instructions without any hardware changes. In contrast, existing solutions posit changes to HTM mechanisms in the form of special instructions or modified functionality. We exploit the ordering mechanism to design a novel persistence method that decouples HTM concurrency from back-end NVM operations. Failure atomicity is achieved using redo logging coupled with aliasing to guard against mistimed cache evictions. Our algorithm uses efficient lock-free mechanisms with bounded static memory requirements. We evaluated our approach using both micro-benchmarks, and, benchmarks in the STAMP suite, and showed that it compares well with standard (volatile) HTM transactions. We also showed that it yields significant gains in throughput and latency in comparison with persistent transactional locking.

Emerging persistent memory technologies (generically referred to as Storage Class Memory or SCM) hold tremendous promise for accelerating popular data-management applications like in-memory databases. However, programmers now need to deal with ensuring the atomicity of transactions on SCM-resident data and maintaining consistency between the persistent and in-memory execution orders of concurrent transactions. The problem is specially challenging when high-performance isolation mechanisms like Hardware Transaction Memory (HTM) are used for concurrency control.

Emerging nonvolatile RAM (NVRAM) technologies have a limit on the number of writes that can be made to any cell, similar to the erasure limits in NAND Flash. This motivates the need for wear leveling techniques to distribute the writes evenly among the cells. Unlike NAND Flash, cells in NVRAM can be rewritten without the need for erasing the entire containing block, avoiding the issues of space reclamation and garbage collection, motivating alternate approaches to the problem. In this article, we propose a hierarchical wear-leveling model called Ouroboros wear leveling. Ouroboros uses a two-level strategy whereby frequent low-cost intraregion wear leveling at small granularity is combined with interregion wear leveling at a larger time interval and granularity. Ouroboros is a hybrid migration scheme that exploits correct demand predictions in making better wear-leveling decisions while using randomization to avoid wear-leveling attacks by deterministic access patterns. We also propose a way to optimize wear-leveling parameter settings to meet a target smoothness level under limited time and space overhead constraints for different memory architectures and trace characteristics. Several experiments are performed on synthetically generated memory traces with special characteristics, two block-level storage traces, and two memory-line-level memory traces. The results show that Ouroboros wear leveling can distribute writes smoothly across the whole NVRAM with no more than 0.2% space overhead and 0.52% time overhead for a 512GB memory.

Big Data applications need to be able to access large amounts of variable data as fast as possible. Emerging Storage Class Memory (SCM) fit this need by making memory available in large capacity while making changes endure as a seamless continuation of load-store accesses through processor caches. However, when writing values into a persistent memory tier, programmers are faced with the dual problems of controlling untimely cache evictions that might commit changes prematurely, and of grouping changes and making them durable as a unit so that consistency can be guaranteed in the event of sudden failure. In this paper, we present various methods to achieve high-performance byte-addressable persistence for an in-memory data store. We chose Redis, a popular high-performance memory oriented key value database. We modified its source code to use SCM such that updates to data and structures are performed in a failure resilient manner. We evaluated the changes using both internal benchmarks and the Yahoo! Cloud Servicing Benchmark (YCSB). We found that even though Redis uses many SCM read operations, it can benefit from highly optimized persistent SCM write based approaches, especially when SCM write times are longer than DRAM write times. The paper presents an innovative Local Alias Table Batched (LATB) method, and shows that it outperforms the alternatives.

Non-volatile byte-addressable memory has the potential to revolutionize system architecture by providing instruction-grained direct access to vast amounts of persistent data. We describe a non-intrusive memory controller that uses backend operations for achieving lightweight failure atomicity. By moving synchronous persistent memory operations to the background, the performance overheads are minimized. Our solution avoids costly software intervention by decoupling isolation and concurrency-driven atomicity from failure atomicity and durability, and does not require changes to the front-end cache hierarchy. Two implementation alternatives - one using a hardware structure, and the other extending the memory controller with a firmware managed volatile space - are described. Our results show the performance is significantly better than traditional approaches.

Providing fairness and system efficiency are important, often conflicting, requirements when allocating shared resources. In a hybrid storage system the problem is complicated by the high variability in request service times, caused by speed differences between heterogeneous devices and workload-specific variations in access time within a device.

Providing QoS guarantees for hybrid storage systems made up of both solid-state drives (SSDs) and hard disks (HDs) is a challenging problem. Since HDs and SSDs have widely different IOPS capacities, it is not sensible to treat the storage system as a monolithic black box, instead a useful QoS model must necessarily differentiate the IOs made to different device types. Traditional storage resource allocation models have largely been designed to provide QoS for a single resource type, and result in poor utilization and fairness when applied to multiple coupled resources. In this paper, we present a new resource allocation model for hybrid storage systems using a multi-resource framework. The model supports reservations and shares for clients sharing the storage system. Reservations specify the minimum throughput (IOPS) that a client must receive, while shares reflect its weight relative to other clients that are bottlenecked on the same device. We present a formal multi-resource allocation model to allocate IOPS to clients, together with an IO scheduling algorithm to maximize system throughput. The model and algorithms are validated with empirical results.

In-memory computing is gaining popularity as a means of sidestepping the performance bottlenecks of block storage operations. However, the volatile nature of DRAM makes these systems vulnerable to system crashes, while the need to continuously refresh massive amounts of passive memoryresident data increases power consumption. Emerging storage-class memory (SCM) technologies combine fast DRAM-like cache-line access granularity with the persistence of storage devices like disks or SSDs, resulting in potential 10x-100x performance gains, and low passive power consumption. This unification of storage and memory into a single directly-accessible persistent tier raises significant reliability and pro-grammability challenges. In this paper, we present SoftWrAP, an open-source framework for Software based Write-Aside Persistence. SoftWrAP provides lightweight atomicity and durability for SCM storage transactions, while ensuring fast paths to data in processor caches, DRAM, and persistent memory tiers. We use our framework to evaluate both handcrafted SCM-based microbenchmarks as well as existing applications, specifically the STX B+Tree library and SQLite database, backed by emulated SCM. Our results show significant benefits of SoftWrAP over existing methods such as undo logging and shadow copying, and can match non-atomic durable writes to SCM, thereby gaining atomic consistency almost for free.

This paper describes a lightweight software library to solve the challenges [6], [3], [1], [5], [2] of programming storage class memory (SCM). It provides primitives to demarcate failure-atomic code regions. SCM loads and stores within each demarcated code region (called a “wrap”) are routed through the library, which buffers updates and transmits them to SCM locations asynchronously while allowing their speedy propagation from writers to readers through CPU caches.

Software-defined datacenters consolidate discrete hardware units into pools of abstract resource types that are dynamically allocated to the clients sharing the infrastructure. The allocation needs to be both fair to the clients and also make efficient use of the system resources. Unlike approaches that allocate individual resources independently, we propose a model for making integrated allocation decisions across multiple resource types, so as to balance fairness and system throughput in a heterogeneous-resource setting.

The paper examines the problem of fair bandwidth allocation in heterogeneous storage systems in the framework of multi-resource allocation. We first extend the Bottleneck Aware Allocation model recently proposed by the authors to directly compute the maximum allocation satisfyinglocal fairness, envy freedom and sharing incentive. Next, we broaden the solution space to all allocations that satisfy envy freedom and sharing incentive even if they do not satisfy local fairness. We present an efficient algorithm to maximize the system utilization in the more general model.

Current public cloud offerings sell capacity in the form of pre-defined virtual machine (VM) configurations to their tenants. Typically this means that tenants must purchase individual VM configurations based on the peak demands of the applications, or be restricted to only scale-out applications that can share a pool of VMs. This diminishes the value proposition of moving to a public cloud as compared to server consolidation in a private virtualized datacenter, where one gets the benefits of statistical multiplexing between VMs belonging to the same or different applications. Ideally one would like to enable a cloud tenant to buy capacity in bulk and benefit from statistical multiplexing among its workloads. This requires the purchased capacity to be dynamically and transparently allocated among the tenant's VMs that may be running on different servers, even across datacenters. In this paper, we propose two novel algorithms called BPX and DBS that are able to provide the cloud customer with the abstraction of buying bulk capacity. These algorithms dynamically allocate the bulk capacity purchased by a customer between its VMs based on their individual demands and user-set importance. Our algorithms are highly scalable and are designed to work in a large-scale distributed environment. We implemented a prototype of BPX as part of VMware's management software and showed that BPX is able to closely mimic the behavior of a centralized allocator in a distributed manner.

We present a novel QoS scheduling algorithm for multi-tiered storage servers made up of hard disks and SSDs. The work is motivated by the difference in access times for a workload as its SSD hit ratio changes. Our scheme is designed to reward clients according to their runtime behavior, while honoring their static QoS settings including shares (or weights), reservations and limits. A model based on entitlements is developed to describe the reward allocation policy (RAP). Simulation results show the advantages of RAP over conventional proportional share allocation in adapting to dynamically varying workloads. The proposed algorithm allows the client to directly reap the benefits of application performance tuning as if the client is on a dedicated system, addressing a key complaint of clients when moving to a shared infrastructure.

Speculative adders have attracted strong interest for reducing critical path delays to sub-logarithmic delays by exploiting the tradeoffs between reliability and performance. Speculative adders also find use in the design of reliable variable latency adders, which combine speculation with error correction to achieve high performance for low area overhead over traditional adders. This paper describes speculative carry select addition (SCSA), a novel function speculation technique for the design of low error-rate speculative adders and low overhead, high performance, reliable variable latency adders. We develop an analytical model for the error rate of SCSA to facilitate both design exploration and convergence. We show that for an error rate of 0.01% (0.25%), SCSA-based speculative addition is 10% faster than the DesignWare adder with up to 43% (56%) area reduction. Further, on average, variable latency addition using SCSA-based speculative adders is 10% faster than the DesignWare adder with area requirements of -19% to 16% (-17% to 29%) for unsigned random (signed Gaussian) inputs.

Supporting QoS control mechanisms in shared storage arrays is constrained by the well-justified fear of impacting the system efficiency. This motivates our study of the trade off between fairness and efficiency in shared storage systems. We propose two adaptations that can be applied to existing IO scheduling mechanisms: the concurrency bound and the batch size. Although these knobs are well known, their impact on system performance and automatic adaptation based on current workload characteristics have not been studied before. Using synthetic benchmarks and trace workloads, we show that the adaptive proportional share algorithm achieves over 90% IO efficiency while maintaining the specified QoS requirements.

The growing popularity of multi-tenant, cloud-based computing platforms is driving research into new QoS models that permit flexible sharing of the underlying infrastructure. In this paper, we re-examine the use of the commonly-used proportional-share model for resource allocation, in the context of modern heterogeneous, multi-tiered storage systems. We highlight the limitations of a conventional proportional sharing approach to resource allocation, and describe a new allocation model that provides strong isolation between clients. This improves the performance characteristics from the viewpoints of both the clients and the service provider.

Speculative adders have attracted strong interest for achieving sublogarithmic delays by exploiting the tradeoffs between correctness and performance. Speculative adders also find use in the design of error-free variable latency adders, which combine speculation with error correction to achieve high performance for low area overhead over traditional adders. This paper describes static window addition (SWA), a novel function speculation technique for the design of low overhead, high performance variable latency adders. Analytical models for the error rate of SWA-based speculative adders are developed to facilitate both design exploration and convergence. We show that on average, variable latency addition using SWA-based speculative adders is 10% faster than the fastest DesignWare adder with area requirements of -5 to 40% for different adder widths.

Cloud computing is an elastic computing model where users can lease computing and storage resources on demand from a remote infrastructure. It is gaining popularity due to its low cost, high reliability, and wide availability. With the emergence of public cloud storage platforms like Amazon, Microsoft, and Google, individual applications and enterprise storage are being deployed on Clouds. However, a serious impediment to its wider deployment is the relative lack of effective data management services. Our experiments, as well as industry reports, have shown that the performance and service-level agreement (SLA) cannot be guaranteed when the data is served over public Clouds. The relatively slow access to persistent data and large variability in cloud storage I/O performance can significantly degrade the performance of data-intensive applications. This paper addresses the issue of I/O performance fluctuation over public cloud platforms and we propose a middleware called CloudMW between the Cloud storage and clients to provide the storage services with better performance and SLA satisfaction. Some technologies, including data virtualization, data chunking, caching, and replication, are integrated into CloudMW to achieve a more stable and predictable performance, and permit flexible sharing of storage among the virtual machines (VMs). Experimental results based on Amazon Web Services (AWS) show that CloudMW is able to improve the stability and help provide better SLAs and data sharing for cloud storage.

The growing popularity of hosted storage services and shared storage infrastructure in data centers is driving the recent interest in resource management and QoS in storage systems. The bursty nature of storage workloads raises significant performance and provisioning challenges, leading to increased resource requirements, management costs, and energy consumption. We present a novel workload shaping framework to handle bursty workloads, where the arrival stream is dynamically decomposed to isolate its bursts, and then rescheduled to exploit available slack. We show how decomposition reduces the server capacity requirements and power consumption significantly, while affecting QoS guarantees minimally. We present an optimal decomposition algorithm RTT and a recombination algorithm Miser, and show the benefits of the approach by evaluating the performance of several storage workloads using both simulation and Linux implementation.

Cloud computing is an elastic computing model whereby users can lease computing and storage resources on demand from a remote infrastructure. Cloud computing is gaining popularity due to its low cost, high reliability and wide availability. However, a serious impediment to its wider deployment is the relative lack of effective data management services. The relatively slow access to persistent data and large variability in cloud storage I/O performance, can significantly degrade the performance of data-intensive applications. This paper addresses the problem of I/O performance fluctuation and proposes an automatic optimization schema for cloud storage called AOSC, which utilizes data chunking, placement, and replication to achieve more stable and predictable performance. Our experimental results based on Amazon Elastic Cloud Computing (EC2) data center show that AOSC can improve the stability and help provide better performance guarantees for cloud computing.

Data center computing is gaining popularity due to the cost efficiencies of consolidation, centralized management, and high reliability. The unpredictable bursty nature of typical workloads where the instantaneous arrival rates can significantly exceed the average long-term rate, requires the server to significantly over provision resources in order to meet response-time service level agreements (SLAs), resulting in low resource utilization and higher costs. In this paper we consider a statistical on-off model for bursty workloads to explore the relationship between burst size, frequency, capacity, and response time distribution. We analyze the performance of a workload shaping method to reduce capacity requirements by providing a graduated two-level SLA. Statistics of the request arrival to the overflow queue are characterized in terms of the underlying Markov chain passage times, and used to estimate its capacity.

The growing popularity of hosted storage services and shared storage infrastructure in data centers is driving the recent interest in resource management and QoS in storage systems. The bursty nature of storage workloads raises significant performance and provisioning challenges, leading to increased infrastructure, management, and energy costs. We present a novel dynamic workload shaping framework to handle bursty workloads, where the arrival stream is dynamically decomposed to isolate its bursts, and then rescheduled to exploit available slack. We show how decomposition reduces the server capacity requirements dramatically while affecting QoS guarantees minimally. We present an optimal decomposition algorithm RTT and a recombination algorithm Miser, and show the benefits of the approach by performance evaluation using several storage traces.

We consider the natural extension of the well-known single disk caching problem to the parallel disk I/O model (PDM) [17]. The main challenge is to achieve as much parallelism as possible and avoid I/O bottlenecks. We are given a fast memory (cache) of size M memory blocks along with a request sequence Σ =(b1,b2,...,bn) where each block bi resides on one of D disks. In each parallel I/O step, at most one block from each disk can be fetched. The task is to serve Σ in the minimum number of parallel I/Os. Thus, each I/O is analogous to a page fault. The difference here is that during each page fault, up to D blocks can be brought into memory, as long as all of the new blocks entering the memory reside on different disks. The problem has a long history [18, 12, 13, 26]. Note that this problem is non-trivial even if all requests in Σ are unique. This restricted version is called read-once. Despite the progress in the offline version [13, 15] and read-once version [12], the general online problem still remained open. Here, we provide comprehensive results with a full general solution for the problem with asymptotically tight competitive ratios.

We examine the problem of providing fair bandwidth allocation in distributed storage systems similar to the research prototypes HP FAB and IBM Intelligent Bricks. The problem poses significant new challenges beyond those encountered in network and storage QoS scheduling. Specifically, resources are heterogeneous i.e. an IO request can only be serviced by a particular server, and service is both requested and provided in a distributed manner with no centralized controller. We provide a distributed algorithm, d-Clock, that runs locally on each of the servers and provides global fairness guarantees without causing resource-specific starvation, with minimal synchronization overhead.

Storage consolidation is becoming an attractive paradigm for data organization because of the economies of sharing and the ease of centralized management. However, sharing of resources is viable only if applications can be isolated from each other. This work targets the problem of providing performance guarantees to an application irrespective of the behavior of other workloads. Application requirements are represented in terms of the average throughput, latency and maximum burst size. Most earlier schemes only do weighted bandwidth allocation; schemes that provide control of latency either cannot handle bursts or penalize applications for their own prior behavior, such as using spare capacity.

High-end shared storage systems serving multiple independent workloads must assure that concurrently executing clients will receive a fair or agreed-upon share of system I/O resources. In a parallel I/O system an application makes requests for specific disks at different steps of its computation depending on the data layout and its computational state. Different applications contend for disk access making the problem of maintaining fair allocation challenging.We propose a model for differentiated disk bandwidth allocation based on lexicographic minimization, and provide new efficient scheduling algorithms to allocate the I/O bandwidth fairly among contending applications. A major contribution of our model is its ability to handle multiple parallel disks and contention for disks among the concurrent applications. Analysis and simulation-based evaluation shows that our algorithms provide performance isolation, weighted allocation of resources, and are work conserving. The solutions are also applicable to other shared resource environments dealing with non-uniform heterogeneous servers.

We consider the natural extension of the single disk caching problem to parallel disk I/O model. We close the existing gap between lower and upper bounds and achieve optimal competitive ratio of O(√D) when lookahead is more than the memory size M. When lookahead is smaller, we derive various upper bounds and lower bounds on the competitive ratio under various adversarial models.

We investigate the problem of smoothing multiplexed network traffic when either a streaming server transmits data to multiple clients or a storage server accesses data from multiple storage devices or other servers. We introduce efficient algorithms for lexicographically optimally smoothing the aggregate bandwidth requirements over a shared network link. Possible applications include improvement in the bandwidth utilization of network links and reduction in the energy consumption of server hosts. In the data transmission problem, we consider the case in which the clients have different buffer capacities and unlimited bandwidth constraints or unlimited buffer capacities and different bandwidth constraints. For the data access problem, we handle the general case of a shared buffer capacity and individual network bandwidth constraints. Previous approaches for the data access problem handled either the case of only a single stream or did not compute the lexicographically optimal schedule. By provably minimizing the variance of the required aggregate bandwidth, lexicographically optimal smoothing makes the maximum resource requirements within the network more predictable and increases the useful resource utilization. It also improves fairness in sharing a network link among multiple users and makes new requests from future clients more likely to be successfully admitted without the need for rescheduling previously accepted traffic. With appropriate hardware and system support, data traffic smoothing can also reduce the energy consumption of the host processor and the communication links. Overall, we expect that efficient resource management at the network edges will better meet quality of service requirements without restricting the scalability of the system.

Parallel disks provide a cost effective way of speeding up I/Os in applications that work with large amounts of data. The main challenge is to achieve as much parallelism as possible, using prefetching to avoid bottlenecks in disk access. Efficient algorithms have been developed for some particular patterns of accessing the disk blocks. In this paper, we consider general request sequences. When the request sequence consists of unique block requests, the problem is called prefetching and is a well-solved problem for arbitrary request sequences. When the reference sequence can have repeated references to the same block, we need to devise an effective caching policy as well. While optimum offline algorithms have been recently designed for the problem, in the online case, no effective algorithm was previously known. Our main contribution is a deterministic online algorithm threshold-LRU which achieves O((MD/L)2/3) competitive ratio and a randomized online algorithm threshold-MARK which achieves O(√(MD/L) log (MD/L)) competitive ratio for the caching/prefetching problem on the parallel disk model (PDM), where D is the number of disks, M is the size of fast memory buffer, and M+L is the amount of lookahead available in the request sequence. The best-known lower bound on the competitive ratio is Ω(≾MD/L) for lookahead L ≥ M in both models. We also show that if the deterministic online algorithm is allowed to have twice the memory of the offline then a tight competitive ratio of Θ(≾MD/L) can be achieved. This problem generalizes the well-known paging problem on a single disk to the parallel disk model.

We investigate the problem of smoothing multiplexed network traffic, when either a streaming server transmits data to multiple clients, or a server accesses data from multiple storage devices or other servers. We introduce efficient algorithms for lexicographically optimally smoothing the aggregate bandwidth requirements over a shared network link. In the data transmission problem, we consider the case in which the clients have different buffer capacities but no bandwidth constraints, or no buffer capacities but different bandwidth constraints. For the data access problem, we handle the general case of a shared buffer capacity and individual network bandwidth constraints. Previous approaches in the literature for the data access problem handled either the case of only a single stream or did not compute the lexicographically optimal schedule.Lexicographically optimal smoothing (lexopt smoothing) has several advantages. By provably minimizing the variance of the required aggregate bandwidth, maximum resource requirements within the network become more predictable, and useful resource utilization increases. Fairness in sharing a network link by multiple users can be improved, and new requests from future clients are more likely to be successfully admitted without the need for frequently rescheduling previously accepted traffic. Efficient resource management at the network edges can better meet quality of service requirements without restricting the scalability of the system.

We address the problem of prefetching and caching in a parallel I/O system and present a new algorithm for parallel disk scheduling. Traditional buffer management algorithms that minimize the number of block misses are substantially suboptimal in a parallel I/O system where multiple I/Os can proceed simultaneously. We show that in the off line case, where a priori knowledge of all the requests is available, PC-OPT performs the minimum number of I/Os to service the given I/O requests. This is the first parallel I/O scheduling algorithm that is provably offline optimal in the parallel disk model. In the online case, we study the context of global L-block lookahead, which gives the buffer management algorithm a lookahead consisting of L distinct requests. We show that the competitive ratio of PC-OPT, with global L-block lookahead, is /spl Theta/(M - L + D), when L /spl les/ M, and /spl Theta/(MD/L), when L > M, where the number of disks is D and buffer size is M.

We address the problem of prefetching and caching in a parallel I/O system and present a new algorithm for optimal parallel-disk scheduling. Traditional buffer management algorithms that minimize the number of I/O disk accesses, are substantially suboptimal in a parallel I/O system where multiple I/Os can proceed simultaneously.

The I/O performance of applications in multiple-disk systems can be improved by overlapping disk accesses. This requires the use of appropriate prefetching and buffer management algorithms that ensure the most useful blocks are accessed and retained in the buffer. In this paper, we answer several fundamental questions on prefetching and buffer management for distributed-buffer parallel I/O systems. First, we derive and prove the optimality of an algorithm, P-min, that minimizes the number of parallel I/Os. Second, we analyze P-con, an algorithm that always matches its replacement decisions with those of the well-known demand-paged MIN algorithm. We show that P-con can become fully sequential in the worst case. Third, we investigate the behavior of on-line algorithms for multiple-disk prefetching and buffer management. We define and analyze P-Iru, a parallel version of the traditional LRU buffer management algorithm. Unexpectedly, we find that the competitive ratio of P-Iru is independent of the number of disks. Finally, we present the practical performance of these algorithms on randomly generated reference strings. These results confirm the conclusions derived from the analysis on worst case inputs.

We address the problems of prefetching and I/O scheduling for read-once reference strings in a parallel I/O system. Read-once reference strings, in which each block is accessed exactly once, arise naturally in applications like databases and video retrieval. Using the standard parallel disk model with D disks and a shared I/O buffer of size M, we present a novel algorithm, red-black prefetching (RBP), for parallel I/O scheduling. The number of parallel I/Os performed by RBP is within 0(D/sup 1/3/) of the minimum possible. Algorithm RBP is easy to implement and requires computation time linear in the length of the reference string. Through simulation experiments we validated the benefits of RBP over simple greedy prefetching.

We address the problems of I/O scheduling and buffer management for general reference strings in a parallel I/O system. Using the standard parallel disk model with D disks and a shared I/O buffer of size M, we study the performance of online algorithms that use bounded global M-block lookahead. We introduce the concept of write-back whereby blocks are dynamically relocated between disks during the course of the computation. Write-back allows the layout to be altered to suit different access patterns in different parts of the reference string. We show that any bounded-lookahead online algorithm that uses purely deterministic policies must have a competitive ratio of /spl Omega/ (D). We show how to improve the performance by using randomization, and present a novel algorithm, RAND-WB, using a randomized write-back scheme. RAND-WB has a competitive ratio of /spl theta/(/spl radic/D), which is the best achievable by any online algorithm with only global M-block lookahead. If the initial layout of data on the disks is uniformly random, RAND-WB has a competitive ratio of /spl theta/(log D).

An efficient multiversion access structure for a transaction-time database is presented. Our method requires optimal storage and query times for several important queries and logarithmic update times. Three version operations-inserts, updates, and deletes-are allowed on the current database, while queries are allowed on any version, present or past. The following query operations are performed in optimal query time: key range search, key history search, and time range view. The key-range query retrieves all records having keys in a specified key range at a specified time; the key history query retrieves all records with a given key in a specified time range; and the time range view query retrieves all records that were current during a specified time interval. Special cases of these queries include the key search query, which retrieves a particular version of a record, and the snapshot query which reconstructs the database at some past time. To the best of our knowledge no previous multiversion access structure simultaneously supports all these query and version operations within these time and space bounds. The bounds on query operations are worst case per operation, while those for storage space and version operations are (worst-case) amortized over a sequence of version operations. Simulation results show that good storage utilization and query performance is obtained.

The IBM SP1 is the first member of the IBM Scalable POWERparallel series, a distributed memory parallel computer based on RISC System/6000 processing element. In this paper, the benchmarking exercise of two message passing libraries, MPL and PVM, on the IBM SP1 for SPMD programming is described. We will discuss the benchmarks used in our experiment, and present the results we obtained. Our results indicate that to achieve performance improvement and to reduce the communication overhead, the use of the high performance switch is essential on the IBM SP1 machine.

The I/O performance of several concurrent external merge jobs sharing a parallel I/O system is studied. The placement of the runs is found to have a significant impact on performance. Placements leading to serialization among jobs were identified and analyzed, and solutions discussed. Contrary to the behavior of a single merge, increasing the buffer size in this situation may actually degrade performance.

The authors present a simulation study of multiple disk systems to improve the input/output (I/O) performance of multiway merging. With the increase in the size of main memory in computer systems, multiple disks and aggressive prefetching can be used to significantly reduce I/O time. Two prefetching strategies-intra-run and inter-run-for external merging using multiple disks were studied. Their performance was evaluated, and simple analytical expressions are derived to explain their asymptotic behavior. The results indicate that a combination of the strategies can result in a significant reduction in I/O time.>

The authors formally define a distributed-memory parallel architecture called the pipelined hypercube. A coarse-grained parallel sorting algorithm that can be mapped efficiently on such an architecture is also presented. The pipelined hypercube has a more powerful communication mechanism than the traditional binary code architecture, in that it permits communication of blocks of data between processing elements (PEs) to be performed in a pipelined manner. Certain data communication problems which would probably be serialized on the binary code architecture, can be performed optimally on the pipelined hypercube. The sorting algorithm can be mapped efficiently onto a pipelined hypercube of P PEs. It sorts N data items, initially distributed among the PEs, in time O((N log N/P)+log/sup 2/ P), thereby achieving linear speedup when P is O(N/log N).>

A fault-tolerant array for matrix multiplication that explicitly incorporates mechanisms for easy testability and reconfigurability is described. All signals in the array travel only a constant distance (independent of array size) in any clock cycle. An optimal-time algorithm, designed for multiplying matrices, is described. The algorithm is an efficient simulation of a 2-D systolic algorithm for multiplying matrices.>

This paper describes a modular, systolic design for two-dimensional convolution which is a frequent and computationally intensive operation in low-level image processing. The design consists of a one-dimensional array of homogeneous cells, each with a fixed amount of storage. The paper also presents schema by which the design consisting of a limited number of cells can be used to implement convolutions of varying kernel sizes, with optimal throughput. The design is simple and hence a good candidate for VLSI integration. Its one-dimensional organization and unidirectional data flow characteristics result in good fault-tolerance for the array.

Parallel algorithms for computing the minimum spanning tree of a weighted undirected graph, and the bridges and articulation points of an undirected graphs on a fixed-size linear array of processors are presented. For a graph of n vertices, the algorithms operate on a linear array of p processors and require O(n2/p) time for all p, 1 ≤ p ≤ n. In particular, using n processors the algorithms require O(n) time which is optimal on this model. The paper describes two approaches to limit the communication requirements for solving the problems. The first is a divide-and-conquer strategy applied to Sollin's algorithm for finding the minimum spanning tree of a graph. The second uses a novel data-reduction technique that constructs an auxiliary graph with no more than 2n − 2 edges, whose bridges and articulation points are the bridges and articulation points of the original graph.

Synthesis of a family of matrix multiplication algorithms on a linear array is described. All these algorithms are optimal in their area and time requirements. An important feature of the family of algorithms is that they are modularly extensible, that is, larger problem sizes can be handled by cascading smaller arrays consisting of processors having a fixed amount of local storage. These algorithms exhibit a tradeoff between the number of processors required and the local storage within a processor. In particular, as the local storage increases the number of processors required to multiply the two matrices decrease.

A matrix-multiplication algorithm on a linear array using an optimal number of processing elements is proposed. The local storage required by the processing elements and the I/O bandwidth required to drive the array are both constants that are independent of the sizes of the matrices being multiplied. The algorithm is therefore modular, that is, arbitrarily large matrices can be multiplied on a large array built by cascading small arrays. The array is well-suited for VLSI implementation.

A matrix multiplication algorithm on a linear array of processing elements is described. The local storage required by the processing elements and the I/O bandwidth required to drive the array are both constants that are independent of the sizes of the matrices being multiplied. The algorithm is therefore modular, that is, arbitrarily large matrices can be multiplied on a large array built by cascading smaller arrays. Each of the matrix elements is read only once from a fixed I/O port and the algorithm does not use global broadcasting. It is also shown that the proposed algorithm computes the n3 scalar products (where n is the size of the two matrices being multiplied) using an optimal number of processing elements.

Matrix multiplication algorithms have been proposed for VLSI array processors. Random defects in the silicon wafer and fabrication errors render processors and data paths in the array faulty, and may cause the algorithm to fail despite a significant number of nonfaulty processors. This correspondence presents a robust VLSI array processor for matrix multiplication. The array is driven by a host computer as a peripheral and the I/O bandwidth required to drive the array is a constant, independent of the problem size. Multiplication of two n x n matrices requires O(n) processors and has a time complexity of O(n2) cydes.

The basic problem which limits both yields and chip sizes is the fact that circuits created using current design techniques will not function correctly in the presence of even a single flaw of sufficient size anywhere on the chip. In this work we examine the problem of constructing chips up to the size of a wafer which operate correctly despite the presence of such flaws. This can be accomplished by building on the wafer a nearest-neighbor network of small, independent, asynchronously communicating modules. A specific algorithm to be performed by the wafer is then mapped onto a fault-free subgraph of the network. We are interested in algorithms which map naturally onto a linear array of identical processors. Construction of fault-tolerant implementations of these algorithms is addressed in two contexts. First we consider the general problem of finding a fault-free subgraph of the host network which is isomorphic to the linear array required to solve a problem. We then examine ways to tailor a specific, known algorithm to the fault-tolerant context.