We consider a class of algorithms related to Lempel-Ziv that incorporate restrictions on the manner in which the data can be parsed with the goal of introducing new tradeoffs between implementation complexity and data compression ratios. Our main motivation lies within the field of compressed memory computer systems. Here requirements include extremely fast decompression and compression speeds, adequate compression performance on small data block lengths, and minimal hardware area and energy requirements. We describe the approach and provide experimental data concerning its compression performance with respect to known alternatives. We show that for a variety of data sets stored in a typical main memory, this direction yields results close to those of earlier techniques, but with significantly lower energy consumption at comparable or better area requirements. The technique thus may be of eventual interest for a number of applications requiring high compression bandwidths and efficient hardware implementation.

We consider a number of cache/memory hierarchy design issues in systems with compressed random access memories (C-RAMs) In which compression and decompression occur automatically to and from main memory. Using a C-RAM as main memory, the bulk of main memory contents are stored in a compressed format and dynamically decompressed to handle cache misses at the next higher level of memory. This is the general approach adopted in IBM's memory expansion technology (MXT). The design of the main memory directory structures and storage allocation methods in such systems is described elsewhere; here, we focus on issues related to cache-memory interfaces. In particular, if the cache line size (of the cache or caches to which main memory data is transferred) is different than the size of the unit of compression in main memory, bandwidth and latency problems can occur. Another issue is that of guaranteed forward progress, that is, ensuring that modified lines can be written to the compressed main memory so that the system can continue operation even if overall compression deteriorates. We study several approaches for solving these problems, using trace-driven analysis to evaluate alternatives.

This paper considers issues relevant to Operating System control of systems with compressed main memory.The notion of "allocated but unused storage" is introduced.This represents storage which has been recently allocated by the Operating System, but which does not yet occupy physical memory because the lines have not yet been cast out of the cache.We propose that control policies incorporate estimates of allocated but unused storage , as such storage represents a major way in which compressibility can dramatically change.The paper addresses the estimation of allocated but unused storage and analyzes its accuracy on system traces.

In a common form of a RAID 5 architecture, data is organized on a disk array consisting of N+1 disks into stripes of N data blocks and one parity block (with parity block locations staggered so as to balance the number of parity blocks on each disk). This allows data to be recovered in the event of a single disk failure. Here we consider an extension to this architecture in which parity information applies to arbitrary subsets of the data blocks in each stripe. Using several simplifying assumptions, we present simulation and analytic results that provide estimates of the improvement using this approach, in terms of total I/O operations, as compared to 1) conventional RAID 5 under a random single-block write workload, and 2) the use of a log-structured file system in which data is written out in stripes. Results on the reduction of disk recovery costs are also presented.

It is often desirable to compress or decompress relatively small blocks of data at high bandwidth and low latency (for example, for data fetches across a high speed network). Sequential compression may not satisfy the speed requirement, while simply splitting the block into smaller subblocks for parallel compression yields poor compression performance due to small dictionary sizes. We consider an intermediate approach, where multiple compressors jointly construct a dictionary. The result is parallel speedup, with compression performance similar to the sequential case.

We describe a method of controlling a three-stage Clos nonblocking switch where "speculative" self-routing over the Clos fabric is augmented with reservations over a control network that connects controllers in the input and output stages of the switch. The effect is that most connections succeed over the speculative path while those subject to contention are processed over the control network. We present simulation result which indicate that the inclusion of a control network yields significant benefits under heavily nonuniform traffic conditions.

In a log-structured file system (LFS), in general each block written to disk causes another disk block to become invalid data, resulting in one block of free space. Over time free disk space becomes highly fragmented, and a high level of dynamic reorganization may be required to coalesce free blocks into physically contiguous areas that subsequently can be used for logs. By consuming available disk bandwidth, this reorganization can degrade system performance. In a segmented disk LFS organization, the copy-and-compact reorganization method reads entire segments and then writes back all valid blocks. Other methods, suggested by earlier work on reduction of storage fragmentation for non-LFS disks, may access far fewer blocks (at the cost of increased CPU time). An analytic model is used to evaluate the effects on available disk bandwidth of dynamic reorganization, as a function of the read/write ratio, storage utilization, and degree of data movement required by dynamic reorganization for steady-state operation. It is shown that decreasing reorganization overhead can have dramatic effects on available disk bandwidth.>

The performance of high-volume transaction processing systems for business applications is determined by the degree of contention for hardware resources as well as for data. Hardware resource requirements may be met cost-effectively with a data-partitioned or shared-nothing architecture. However, the two-phase locking (2PL) concurrency control method may restrict the performance of a shared-nothing system more severely than that of a centralized system due to increased lock holding times. Deadlock detection and resolution are an added complicating factor in shared-nothing systems. The authors describe distributed Wait-Depth Limited (WDL) concurrency control (CC), a locking-based distributed CC method that limits the wait-depth of blocked transactions to one, thus preventing the occurrence of deadlocks. Several implementations of distributed WDL which vary in the number of messages and the amount of information available for decision making are discussed. The performance of a generic implementation of distributed WDL is compared with distributed 2PL (with general-waiting policy) and the Wound-Wait CC method through a detailed simulation. It is shown that distributed WDL behaves similarly to 2PL for low lock contention levels, but for substantial lock contention levels (caused by higher degrees of transaction concurrency), distributed WDL outperforms the other methods to a significant degree.>

Distributed wait-depth-limited (DWDL) concurrency control, a locking-based method that limits the wait-depth of blocked transactions to one, which assures that deadlocks are resolved as part of regular transaction processing is described. The performance of DWDL is compared with that of distributed two-phase locking (2PL) and the wound-wait concurrency control method through a detailed simulated. Results show that DWDL behaves similarly to 2PL for low data contention levels, but at high lock contention levels, DWDL outperforms the other methods to a significant degree.>

Future transaction processing systems may have substantially higher levels of concurrency due to reasons which include: (1) increasing disparity between processor speeds and data access latencies, (2) large numbers of processors, and (3) distributed databases. Another influence is the trend towards longer or more complex transactions. A possible consequence is substantially more data contention, which could limit total achievable throughput. In particular, it is known that the usual locking method of concurrency control is not well suited to environments where data contention is a significant factor. Here we consider a number of concurrency control concepts and transaction scheduling techniques that are applicable to high contention environments, and that do not rely on database semantics to reduce contention. These include access invariance and its application to prefetching of data, approximations to essential blocking such as wait depth limited scheduling, and phase dependent control. The performance of various concurrency control methods based on these concepts are studied using detailed simulation models. The results indicate that the new techniques can offer substantial benefits for systems with high levels of data contention.

A new class of wait depth limited (WDL) concurrency control (CC) methods is described. The WDL policy is shown by simulations to be effective both in systems with proportionately large I/O latencies as well as in systems with large numbers of processors. WDL is also attractive in terms of implementation. In many applications little or no system modification may be required other than the CC code. Since it is a lock-based method, unlike optimistic methods, there is no need for private copies of modified data for each transaction, nor is there any need for snapshot, timestamp, or versioning mechanisms to guarantee that transactions are always provided with a fully consistent database image.>

Various factors suggest that data contention may be of increasing significance in transaction processing systems. One approach to this problem is to run transactions twice, the first time without making any changes to the database. Benefits may result either from data prefetching during the first execution or from determining the locks required for purposes of scheduling. Consideration is given to various concurrency control methods based on this notion, and properties required for these methods to be useful are formalized. Performance results based on detailed simulation models suggest that such policies offer potential benefits for some system configurations.>

Given the pairwise probability of conflict p among transactions in a transaction processing system, together with the total number of concurrent transactions n, the effective level of concurrency E(n,p) is defined as the expected number of the n transactions that can run concurrently and actually do useful work. Using a random graph model of concurrency, we show for three general classes of concurrency control methods, examples of which are (1) standard locking, (2) strict priority scheduling, and (3) optimistic methods, that (1) E(n, p) ⩽ n(1 - p/2) n-1 , (2) E(n, p) ⩽ (1 - (1 - p) n )/p, and (3) 1 + ((1 - p)/p)ln(p(n - 1) + 1) ⩽ E(n, p) ⩽ 1 + (1/p)ln(p(n - 1) + 1). Thus, for fixed p, as n ↣ ∞), (1) E ↣ 0 for standard locking methods, (2) E ⩽ 1/p for strict priority scheduling methods, and (3) E ↣ ∞ for optimistic methods. Also found are bounds on E in the case where conflicts are analyzed so as to maximize E. The predictions of the random graph model are confirmed by simulations of an abstract transaction processing system. In practice, though, there is a price to pay for the increased effective level of concurrency of methods (2) and (3): using these methods there is more wasted work (i.e., more steps executed by transactions that are later aborted). In response to this problem, three new concurrency control methods suggested by the random graph model analysis are developed. Two of these, called (a) running priority and (b) older or running priority, are shown by the simulation results to perform better than the previously known methods (l)-(3) for relatively large n or large p, in terms of achieving a high effective level of concurrency at a comparatively small cost in wasted work.

In paged storage systems, page replacement policies generally depend on a use bit for each page frame. The use bit is automatically turned on when the resident page is referenced. Typically, a page is considered eligible for replacement if its use bit has been scanned and found to be off on µ consecutive occasions, where µ is a parameter of the algorithm. This investigation focuses on the dependence of the number of bit-scanning operations on the value of µ and on properties of the string of page references. The number of such operations is a measure of the system overhead incurred while making replacement decisions. In particular, for several algorithms, the number of scans per reference is shown to be approximately proportional to µ However, empirical results from single-program traces show that the value of µ has little effect on the miss ratio. Although the miss ratios for the bit-scanning algorithms are close to those of least recently used (LRU), it is pointed out that increasing the value of µ need not bring the bit-scanning policies closer to LRU management.

The topic of this paper is a probabilistic analysis of demand paging algorithms for storage hierarchies. Two aspects of algorithm performance are studied under the assumption that the sequence of page requests is statistically independent: the page fault probability for a fixed memory size and the variation of performance with memory. Performance bounds are obtained which are independent of the page request probabilities. It is shown that simple algorithms exist which yield fault probabilities close to optimal with only a modest increase in memory.

A study is described of delta modulators where the quantizing parameter\Deltais a function of a finite number of previously emitted bits. Sufficient conditions are obtained for bounding the steady-state quantization error by the current value of\Deltaunder the assumption that input signals are limited both in amplitude and frequency. The nonlinear problem associated with determining a bounding rule is partitioned into a set of problems amenable to linear programming techniques. Results of the analysis are compared with those obtained from a stochastic approximation program.

This paper is devoted to a special class of linear time-varying filters, members of which are commonly employed in practice. It is shown that some of these filters share a number of desirable properties with linear stationary systems, the most important of which is the preservation of wide sense stationarity of stochastic inputs. An application to the problem of transmitting a continuous signal over a sampled data channel is included. Some results coincide with those for a multichannel system with simultaneous optimum stationary presampling and postsampling filters.