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.
5272318
On Designing Interconnection Networks for Multiprocessors
This paper considers various physical constraints which influence the design of interconnection networks used in multiprocessor systems. Design expressions are presented for implementing an N log N packet passing interconnection network composed for circuit switched crossbar chip modules. Expressions reflecting chip level and board level pin and area constraints are derived and used to determine the network delay expected at a given clock frequency. Logic and memory delay, signal path delay, clock skew and clock tree delay parameters are defined and used to determine the maximum frequency which can be obtained with a given design. An example 2048x2048 network... Read complete abstract on page 2.
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
27473158
Interconnection Networks: Physical Design and Performance Analysis
This paper considers various physical constraints which influence the design of interconnection networks used in multiprocessor systems. Design expressions are presented for implementing an N log N packet passing interconnection network composed of circuit switched crossbar chip modules. Expressions reflecting chip level and board level pin and area constraints are derived and used to determine the network delay expected at a given clock frequency. Logic and memory delay, signal path delay, clock skew, and clock distribution delay parameters are defined and used to determine the maximum frequency which can be obtained with a given design. An example 2048 × 2048 network design is considered. This example indicates that using aggressive packaging and MOS technology, a clock frequency of about 40 Mhz is achievable. However, even at this frequency, this network would result in a one-way delay (ignoring blocking and hot spot delays) of about 1 μsec. A read operation from memory requiring a round trip would thus require about 2 μsec. This represents considerable slowdown when compared with accessing strictly local memory and appears to be a major problem in the design of network centered multiprocessor architectures.
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.
4909660
Declarative Support for Sensor Data Cleaning
Pervasive applications rely on data captured from the physical world through sensor devices. Data provided by these devices, however, tend to be unreliable. The data must, therefore, be cleaned before an application can make use of them, leading to additional complexity for application development and deployment. Here we present Extensible Sensor stream Processing (ESP), a framework for building sensor data cleaning infrastructures for use in pervasive applications. ESP is designed as a pipeline using declarative cleaning mechanisms based on spatial and temporal characteristics of sensor data. We demonstrate ESP's effectiveness and ease of use through three real-world scenarios.
2701585
“Data in your face”: push technology in perspective
Push technology has recently generated a tremendous amount of media attention, commercial activity, and contro versy. The wide range of opinions on push is understandable given that it represents a major departure from the way distributed information systems have traditionally been b Adding to the noise, however, is confusion about the basic principles of push and where it fits in to the world of data delivery. For example, many discussions on the topic blur the distinction between push and broadcast. We argue that this confusion stems from two fundamental causes: First, push is just one dimension of a larger design space of data delivery mechanisms. Second, networked information systems can employ different data delivery options between different s ets of information producers and consumers. In this short paper we characterize the design space for dissemination-based i nformation systems and applications, and show how current “push” solutions fit into this space. We then use this framework highlight how the implementation of current Internetbased push solutions differs from the appearance that they present to users.
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.
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.
2596226
Towards an Internet-Scale XML Dissemination Service
Publish/subscribe systems have demonstrated the ability to scale to large numbers of users and high data rates when providing content-based data dissemination services on the Internet. However, their services are limited by the data semantics and query expressiveness that they support. On the other hand, the recent work on selective dissemination of XML data has made significant progress in moving from XML filtering to the richer functionality of transformation for result customization, but in general has ignored the challenges of deploying such XML-based services on an Internet-scale. In this paper, we address these challenges in the context of incorporating the rich functionality of XML data dissemination in a highly scalable system. We present the architectural design of ONYX, a system based on an overlay network. We identify the salient technical challenges in supporting XML filtering and transformation in this environment and propose techniques for solving them.