17338631
DCD—disk caching disk: a new approach for boosting I/O performance
This paper presents a novel disk storage architecture called DCD, Disk Caching Disk, for the purpose of optimizing I/O performance. The main idea of the DCD is to use a small log disk, referred to as cache-disk, as a secondary disk cache to optimize write performance. While the cache-disk and the normal data disk have the same physical properties, the access speed of the former differs dramatically from the latter because of different data units and different ways in which data are accessed. Our objective is to exploit this speed difference by using the log disk as a cache to build a reliable and smooth disk hierarchy. A small RAM buffer is used to collect small write requests to form a log which is transferred onto the cache-disk whenever the cache-disk is idle. Because of the temporal locality that exists in office/engineering work-load environments, the DCD system shows write performance close to the same size RAM (i.e. solid-state disk) for the cost of a disk. Moreover, the cache-disk can also be implemented as a logical disk in which case a small portion of the normal data disk is used as the log disk. Trace-driven simulation experiments are carried out to evaluate the performance of the proposed disk architecture. Under the office/engineering work-load environment, the DCD shows superb disk performance for writes as compared to existing disk systems. Performance improvements of up to two orders of magnitude are observed in terms of average response time for write operations. Furthermore, DCD is very reliable and works at the device or device driver level. As a result, it can be applied directly to current file systems without the need of changing the operating system.
11786279
Effects of Arbitration Protocols on the Performance of Multiple-Bus Multiprocessors
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. >
2566279
PRINS: Optimizing Performance of Reliable Internet Storages
Distributed storage systems employ replicas or erasure code to ensure high reliability and availability of data. Such replicas create great amount of network traffic that negatively impacts storage performance, particularly for distributed storage systems that are geographically dispersed over a wide area network (WAN). This paper presents a performance study of our new data replication methodology that minimizes network traffic for data replications. The idea is to replicate the parity of a data block upon each write operation instead of the data block itself. The data block will be recomputed back at the replica storage site upon receiving the parity. We name the new methodology PRINS (Parity Replication in IP-Network Storages). PRINS trades off highspeed computation for communication that is costly and more likely to be the performance bottleneck for distributed storages. By leveraging the parity computation that exists in common storage systems (RAID), our PRINS does not introduce additional overhead but dramatically reduces network traffic. We have implemented PRINS using iSCSI protocol over a TCP/IP network interconnecting a cluster of PCs as storage nodes. We carried out performance measurements on Oracle database, Postgres database, MySQL database, and Ext2 file system using TPC-C, TPC-W, and Micro benchmarks. Performance measurements show up to 2 orders of magnitudes bandwidth savings of PRINS compared to traditional replicas. A queueing network model is developed to further study network performance for large networks. It is shown that PRINS reduces response time of the distributed storage systems dramatically.
2114893
The Downward Refinement Property
Using abstraction in planning does not guarantee an improvement in search efficiency; it is possible for an abstract planner to display worse performance than one that does not use abstraction. Analysis and experiments have shown that good abstraction hierarchies have, or are close to having, the downward refinement property, whereby, given that a concrete-level solution exists, every abstract solution can be refined to a concrete-level solution without backtracking across abstract levels. Working within a semantics for ABSTRIPS-style abstraction we provide a characterization of the downward refinement property. After discussing its effect on search efficiency, we develop a semantic condition sufficient for guaranteeing its presence in an abstraction hierarchy. Using the semantic condition, we then provide a set of sufficient and polynomial-time checkable syntactic conditions that can be used for checking a hierarchy for the downward refinement property.
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.
15404000
Relating the performance of partial-order planning algorithms to domain features
The AI planning field has a long history of introducing yet another search algorithm that is believed to be the best in all domains. Some recent examples are NONLIN, TWEAK and SNLP. In this paper we show, by directly comparing the above three planners, that the quest for an overall winner is doomed to fail. We first argue that these three planners differ in a variety of ways, including methods for termination check, causal-link protection, and subgoal selection. These differences entail different search behaviors in terms of factors such as the branching factor, the search depth and the time spent by the algorithm on each search node. Furthermore, the search behavior is closely related to the characteristics of the problem domain in which a planner is operating. In this paper we identify one such domain feature, expressed as the ratio of the number of negative threats to the number of positive threats. We present an artificial domain where we can control this ratio and show that in fact the planners show radically different performance as the ratio is varied in this domain. The implication of this result for someone implementing a planning system is that the most appropriate algorithm will depend on the types of problems to be solved by the planner.
8789759
Mining web logs for prediction models in WWW caching and prefetching
Web caching and prefetching are well known strategies for improving the performance of Internet systems. When combined with web log mining, these strategies can decide to cache and prefetch web documents with higher accuracy. In this paper, we present an application of web log mining to obtain web-document access patterns and use these patterns to extend the well-known GDSF caching policies and prefetching policies. Using real web logs, we show that this application of data mining can achieve dramatic improvement to web-access performance.
9153942
ActiveCBR: An Agent System That Integrates Case-Based Reasoning and Active Databases
Abstract. Case-based reasoning (CBR) is an artificial intelligence (AI) technique for problem solving that uses previous similar examples to solve a current problem. Despite its success, most current CBR systems are passive: they require human users to activate them manually and to provide information about the incoming problem explicitly. In this paper, we present an integrated agent system that integrates CBR systems with an active database system. Active databases, with the support of active rules, can perform event detection, condition monitoring, and event handling (action execution) in an automatic manner. The integrated ActiveCBR system consists of two layers. In the lower layer, the active database is rule-driven; in the higher layer, the result of action execution of active rules is transformed into feature–value pairs required by the CBR subsystem. The layered architecture separates CBR from sophisticated rule-based reasoning, and improves the traditional passive CBR system with the active property. The system has both real-time response and is highly exible in knowledge management as well as autonomously in response to events that a passive CBR system cannot handle. We demonstrate the system efficiency and effectiveness through empirical tests.