18921221
RAPID-Cache-a reliable and inexpensive write cache for disk I/O systems
This paper presents a new cache architecture called RAPID-Cache for Redundant, Asymmetrically Parallel, and Inexpensive Disk Cache. A typical RAPID-Cache consists of two redundant write buffers on top of a disk system. One of the buffers is a primary cache made of RAM or NVRAM and the other is a backup cache containing a two level hierarchy: a small NVRAM buffer on top of a log disk. The backup cache has nearly equivalent write performance as the primary RAM cache, while the read performance of the backup cache is not as critical because normal read operations are performed through the primary RAM cache and reads from the backup cache happen only during error recovery periods. The RAPID-Cache presents an asymmetric architecture with a fast-write-fast-read RAM being a primary cache and a fast-write-slow-read NVRAM-disk hierarchy being a backup cache. The asymmetric cache architecture allows cost-effective designs for very large write caches for high-end disk I/O systems that would otherwise have to use dual-copy, costly NVRAM caches. It also makes it possible to implement reliable write caching for low-end disk I/O systems since the RAPID-Cache makes use of inexpensive disks to perform reliable caching. Our analysis and trace-driven simulation results show that the RAPID-Cache has significant reliability/cost advantages over conventional single NVRAM write caches and has great cost advantages over dual-copy NVRAM caches. The RAPID-Cache architecture opens a new dimension for disk system designers to exercise trade-offs among performance, reliability and cost.
36641724
A new and efficient FFT algorithm for distributed memory systems
This paper presents a new and optimal parallel implementation of multidimensional fast Fourier transform algorithm on distributed memory multiprocessors. Its optimality is obtained by minimizing the number of message passings necessary, at the cost of increase in message length. This distinctive feature of the new algorithm effectively utilizes the important architectural property of most of today's distributed memory multiprocessors-wormhole routing for interprocessor communications. By using the algebra of stride permutations and tenser products as a mathematical tool, we are able to derive and formulate an efficient data partition and communication scheme that reduces communication cost from O(N/sup 2/) required for the best known FFT to O(N) on an N/sup 2/-processor machine. Our data partition scheme is natural and efficient for solving discretized boundary value problems such as partial differential equations and finite element analysis. To evaluate the actual performance of our new algorithm in comparison with other existing parallel FFT algorithms, we have carried out implementation experiments on the Intel's Touchstone Delta machine.
78709
STICS: SCSI-to-IP cache for storage area networks
Abstract Data storage plays an essential role in today's fast-growing data-intensive network services. New standards and products emerge very rapidly for networked data storage. Given the mature Internet infrastructure, the overwhelming preference among the IT community recently is using IP for storage networking because of economy and convenience. iSCSI is one of the most recent standards that allow SCSI protocols to be carried out over IP networks. However, there are many disparities between SCSI and IP in terms of protocols, speeds, bandwidths, data unit sizes, and design considerations that prevent fast and efficient deployment of storage area network (SAN) over IP. This paper introduces SCSI-to-IP cache storage (STICS), a novel storage architecture that couples reliable and high-speed data caching with low-overhead conversion between SCSI and IP protocols. A STICS block consists of one or several storage devices and an intelligent processing unit with CPU and RAM. The storage devices are used to cache and store data while the intelligent processing unit carries out the caching algorithm, protocol conversion, and self-management functions. Through the efficient caching algorithm and localization of certain unnecessary protocol overheads, STICS can significantly improve performance, reliability, and scalability over current iSCSI systems. Furthermore, STICS can be used as a basic plug-and-play building block for data storage over IP. Analogous to “cache memory” invented several decades ago for bridging the speed gap between CPU and memory, STICS is the first-ever “cache storage” for bridging the gap between SCSI and IP making it possible to build an efficient SAN over IP. We have implemented software STICS prototype on Linux operating system. Numerical results using popular benchmarks such as vxbench, IOzone, PostMark, and EMC's trace have shown a dramatic performance gain over the current iSCSI implementation.
229042
Introducing a New Cache Design into Vector Computers
Introduces an innovative cache design for vector computers, called prime-mapped cache. By utilizing the special properties of a Mersenne prime, the new design does not increase the critical path length of a processor, nor does it increase the cache access time as compared to existing cache organizations. The prime-mapped cache minimizes cache miss ratio caused by line interferences that have been shown to be critical for numerical applications by previous investigators. With negligibly additional hardware cost, significant performance gains are obtained by adding the proposed cache memory to an existing vector computer. The performance of the design is studied analytically, using a generic vector computation model. The analytical model is validated through extensive simulation experiments. A performance analysis for various vector access patterns shows that the prime-mapped cache performs significantly better than conventional cache organizations in the vector processing environment. The performance gain will increase with the increase of the speed gap between processors and memories. >
8600912
Performance Evaluation of Distributed Web Server Architectures under E-Commerce Workloads
One of the central and key components to make the ECommerce a success is high performance and highly reliable web server architectures. Extensive research has been sparked aiming at improving web server performance. Fundamental to the goal of improving web server performance is a solid understanding of behavior and performance of web servers. However, very little research is found on evaluating web server performance based on realistic workload representing E-Commerce applications which are usually exemplified by a large amount of CGI (Common Gateway Interface), ASP (Active Server Page), or Servlet (Java Server-side interface) calls. This paper presents a performance study under the workload with a mixture of static web page requests, CGI requests, Servlet requests, and database queries. System throughputs and user response times are measured for five different server architectures consisting of PCs that run both a web server program and a database. We observed that performance behaviors of the web server architectures considered under this mixed workload are quite different from that under static page workload and sometimes counter-intuitive. Our performance results suggest that there is a large room for potential performance improvement for web servers.
11786279
Effects of Arbitration Protocols on the Performance of Multiple-Bus Multiprocessors
15776610
Delaying Variable Binding Commitments in Planning
One of the problems with many partial-order planners is their eager commitment to variable bindings. This is contrary to their control decision in delayed-commitment of operator orderings. In this paper we present an extension to the classical partial-order planners by associating every variable with a finite domain of values. The extended planner applies constraint satisfaction routines to check for the consistency of variable bindings. With the extended planner, we perform a set of experiments to show that it is able to reduce the amount of backtracking in domains where few variable instantiations can lead to final solutions. We also investigate the frequency of CSP application to determine how often should constraint checking be performed in order to yield the best performance.
7514161
An Incremental Subspace Learning Algorithm to Categorize Large Scale Text Data
The dramatic growth in the number and size of on-line information sources has fueled increasing research interest in the incremental subspace learning problem. In this paper, we propose an incremental supervised subspace learning algorithm, called Incremental Inter-class Scatter (IIS) algorithm. Unlike traditional batch learners, IIS learns from a stream of training data, not a set. IIS overcomes the inherent problem of some other incremental operations such as Incremental Principal Component Analysis (PCA) and Incremental Linear Discriminant Analysis (LDA). The experimental results on the synthetic datasets show that IIS performs as well as LDA and is more robust against noise. In addition, the experiments on the Reuters Corpus Volume 1 (RCV1) dataset show that IIS outperforms state-of-the-art Incremental Principal Component Analysis (IPCA) algorithm, a related algorithm, and Information Gain in efficiency and effectiveness respectively.
42167729
Computation of chain queries in distributed database systems
13194241
BUCS - a bottom-up cache structure for networked storage servers
This paper introduces a new caching structure to improve server performance by minimizing data traffic over the system bus. The idea is to form a bottom-up caching hierarchy in a networked storage server. The bottom level cache is located on an embedded controller that is a combination of a network interface card (NIC) and a storage host bus adapter (HBA). Storage data coming from or going to a network are cached at this bottom level cache and meta-data related to these data are passed to the host for processing. When cached data exceed the capacity of the bottom level cache, some data are moved to the host RAM that is usually larger than the bottom level cache. This new cache hierarchy is referred to as bottom-up cache structure (BUGS) in contrast to a traditional CPU-centric top-down cache where the top-level cache is the smallest and fastest, and the lower in the hierarchy the larger and slower the cache. Such data caching at the controller level dramatically reduces bus traffic and leads to great performance improvement for networked storages. We have implemented a proof-of-concept prototype using Intel's IQ80310 reference board and Linux network block device. Through performance measurements on the prototype implementation, we observed up to 3 times performance improvement of BUCS over traditional systems in terms of response time and system throughput.
219267
Planning with Primary Effects: Experiments and Analysis
The use of primary effects in planning is an effective approach to reducing search. The underlying idea of this approach is to select certain "important" effects among the effects of each operator and to use an operator only for achieving its important effects. In the past, there has been little analysis of planning with primary effects and few experimental results We provide empirical and analytical results on the use of primary effects First, we experimentally demonstrate that the use of primary effects may lead to an exponential reduction of the planning time. Second, we analytically ex plain the experimental results and identify the factors that influence the efficiency of planning with primary effects. Third we describe an application of our analysis to predicting the performance of a planner for a given selection of primary effects.