14211318
An architecture for fast processing of large unstructured data sets
This paper presents a general system architecture tailored to perform searching, filtering, compression, encryption, and other operations on unstructured data streaming from a disk system. The system achieves high performance on such applications by providing for parallelism, hardware-application specialization and reconfiguration, and hardware placement near the disk systems. A limited prototype of a single compute node has been implemented and is described. The prototype is tailored to applications involving complex searching and its performance is compared to a pure software implementation having the same search capabilities. Performance is considered in terms of data set size, query string hit rate and query complexity. Performance results as a function of these parameters are presented and the results indicate that, for data set sizes above 1.4 MB, the prototype compute node is between one and two orders of magnitude faster than a pure software implementation. At high data set sizes, on an individual node, speedups of about 200 and a sustained throughput of 300 MB/sec have been achieved.
18311613
Fair scheduling in an optical interconnection network
Existing fair scheduling schemes have focused primarily on scheduling multiple flows to a single output. The limited work that has focused on scheduling multiple flows to multiple outputs has assumed a non-blocking, slotted-time, cell-based network with a centralized controller. This paper presents a fair scheduler suitable for use in bufferless circuit-switched blocking networks operating with distributed, asynchronous controllers and variable length messages. We begin by describing the potential for starvation in the Gemini interconnect network, an optical, circuit-switched network. A proposed distributed fair scheduler is presented and shown to solve this problem. The tradeoffs and limitations of performing many-to-many fair scheduling in general, and that of our fair scheduler in particular, are discussed.
583321
Performance models for network processor design
To provide a variety of new and advanced communications services, computer networks are required to perform increasingly complex packet processing. This processing typically takes place on network routers and their associated components. An increasingly central component in router design is a chip-multiprocessor (CMP) referred to as "network processor" or NP. In addition to multiple processors, NPs have multiple forms of on-chip memory, various network and off-chip memory interfaces, and other specialized logic components such as CAMs (content addressable memories). The design space for NPs (e.g., number of processors, caches, cache sizes, etc.) is large due to the diverse workload, application requirements, and system characteristics. System design constraints relate to the maximum chip area and the power consumption that are permissible while achieving defined line rates and executing required packet functions. In this paper, an analytic performance model that captures the processing performance, chip area, and power consumption for a prototypical NP is developed and used to provide quantitative insights into system design trade offs. The model, parameterized with a networking application benchmark, provides the basis for the design of a scalable, high-performance network processor and presents insights into how best to configure the numerous design elements associated with NPs
33759482
Working Set and Page Fault Frequency Paging Algorithms: A Performance Comparison
Performance of a paged virtual memory computer system operating under working set (WS) and page fault frequency (PFF) paging algorithms is analyzed analytically. Performance sensitivity to program reference behavior and paging algorithm parameter is studied for the two paging algorithms. The results indicate that when performance with the two algorithms is compared, the WS algorithm is generally less sensitive to changes in program behavior. Results are also provided relating to performance sensitivity to algorithm parameter selection.
18934348
Anomalies with variable partition paging algorithms
Five types of anomalous behaviour which may occur in paged virtual memory operating systems are defined. One type of anomaly, for example, concerns the fact that, with certain reference strings and paging algorithms, an increase in mean memory allocation may result in an increase in fault rate. Two paging algorithms, the page fault frequency and working set algorithms, are examined in terms of their anomaly potential, and reference string examples of various anomalies are presented. Two paging algorithm properties, the inclusion property and the generalized inclusion property, are discussed and the anomaly implications of these properties presented.
206622431
Pin Limitations and Partitioning of VLSI Interconnection Networks
Multiple processor interconnection networks can be characterized as having N' inputs and N' outputs, each being B' bits wide. A major implementation constraint of large networks in the VLSI environment is the number of pins available on a chip, Np. Construction of large networks requires partitioning of the N' * N' * B' network into a collection of N * N switch modules with each input and output port being B (B ≤ B') bits wide. If each module corresponds to a single chip, then a large network can be implemented by interconnecting the chips in a particular manner. This correspondence presents a methodology for selecting the optimum values of N and B given values of N', B', Np, and the number of control lines per port. Models for both banyan and crossbar networks are developed and arrangements yielding minimum: 1) number of chips, 2) average delay through the network, and 3) product of number of chips and delay, are presented.
6221317
Client-Server Caching Revisited
The caching of data and/or locks at client workstations is an eeective technique for improving the performance of a client-server database system. This paper extends an earlier performance study of client-server caching in several ways. The rst is a re-examination of heuristics for deciding dynamically between propagating changes or invalidating remote copies of data pages in order to maintain cache consistency. The second is a study of the \Callback Locking" family of caching algorithms. These algorithms are of interest because they provide an alternative to the optimistic techniques used in the earlier study and because they have recently begun to nd use in commercial systems. In addition, the performance of the caching algorithms is examined in light of current trends in processor and network speeds and in the presence of data contention.
31246040
Global Memory Management in Client-Server Database Architectures
Earlier performance studies of client-server database systems have investigated algorithms for caching locks and data at client worhxtations to reafuce latency and offload the server. These studies have been restricted to algorithms in which d&abase pages that were not in the local client buffer pool or the server buffer pool were read in from disk. In this paper we investigate a technique that allows client page requests to be serviced by other clients, thus treating the entire system as a single memory hierarchy. We also present techniques for efficiently exploiting this global memory hierarchy by reducing the replication of pages between client and server buffer pools. Global memory management algorithms that employ various combinalions of these techniques are then described, and the performance tradeoffs among the algorithms we investigated under a range of workloads and system conjiguratio~ using a simulation model.
14137960
Scheduling for large-scale on-demand data broadcasting
Advances in telecommunications have enabled the deployment of broadcast-based wide-area information services that provide on-demand data access to very large client populations. In order to effectively utilize a broadcast medium for such a service, it is necessary to have efficient, on-line scheduling algorithms that can balance individual and overall performance and can scale in terms of data set sizes, client populations, and broadcast bandwidth. In this study we introduce a parameterized algorithm that provides good performance across all of these criteria and can be tuned to emphasize either average or worst case waiting time. Unlike previous work on low overhead scheduling, the algorithm is not based on estimates of the access probabilities of items, but rather, it makes scheduling decisions based on the current queue state, allowing it to easily adapt to changes in the intensity and distribution of the workload. We examine the performance of the algorithm using a simulation model.
236978
Streaming Queries over Streaming Data
Recent work on querying data streams has focused on systems where newly arriving data is processed and continuously streamed to the user in real-time. In many emerging applications, however, ad hoc queries and/or intermittent connectivity also require the processing of data that arrives prior to query submission or during a period of disconnection. For such applications, we have developed PSoup, a system that combines the processing of ad-hoc and continuous queries by treating data and queries symmetrically, allowing new queries to be applied to old data and new data to be applied to old queries. PSoup also supports intermittent connectivity by separating the computation of query results from the delivery of those results. PSoup builds on adaptive query processing techniques developed in the Telegraph project at UC Berkeley. In this paper, we describe PSoup and present experiments that demonstrate the effectiveness of our approach.
7889988
Crash recovery in client-server EXODUS
In this paper, we address the correctness and performance issues that arise when implementing logging and crash recovery in a page-server environment. The issues result from two characteristics of page-server systems: 1) the fact that data is modified and cached in client database buffers that are not accessible by the server, and 2) the performance and cost trade-offs that are inherent in a client-server environment. We describe a recovery system that we have implemented for the client-server version of the EXODUS storage manager. The implementation supports efficient buffer management policies, allows flexibility in the interaction between clients and the server, and reduces the server load by generating log records at clients. We also present a preliminary performance analysis of the implementation.