22695314
VLSI Performance Comparison of Banyan and Crossbar Communications Networks
The performance characteristics of banyan and crossbar communications networks are compared in a VLSI environment, where it is assumed that the entire network resides on a single VLSI chip and operates in a circuit switched mode. A high-level model of the space (area) and time (delay) requirements for these networks is developed and relative performance comparisons are made based on a space-time product measure. The results differ significantly from those obtained with more traditional analyses which are usually based on switch aggregate comparisons and SSI-based delay calculations. The analysis presented shows that the area required by both networks grows as 0(N2). Time delay grows as 0(N) for the crossbar, and approximately 0[ Na(log2N)2] for the banyan where 0 < a < 1. This contrasts with traditional results which yield 0(N log N) and 0(log N) switch and delay growth for banyan networks.
18137632
Collecting Data About Logic Simulation
Design of high-performance hardware and software-based gate-switch-level logic simulators requires knowledge about the logic simulation process itself. Unfortunately, little data is publicly available concerning key aspects of this process. An example of this is the lack of published empirical measurements relating to the time distribution of events generated by such simulators. This paper presents a gate-switch-level logic simulator lsim which is oriented towards the collection of data about the simulation process. The basic components of lsim are reviewed, and its relevant data gathering facilities are discussed. An example is presented which illustrates the use of lsim in gathering data on event distributions and on communications requirements under alternative logic circuit partitionings.
34325813
Timing Control of VLSI Based NlogN and Crossbar Networks
Two basic data flow control methods for circuit switched, pipelined networks of the general nlogn and crossbar (cb) topologies are modelled and their effects on overall data rates achievable are determined. The synchronous method uses a global clock and as network modules grow, clock skew and clock tree charge/discharge times grow resulting in lower data rates. The asynchronous method relies on local request/acknowledge signals to control data movement and hence its performance is less affected by system growth. 12 references.
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.
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.
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.
463375
Support for speculative update propagation and mobility in Deno
This paper presents the replication framework of Deno, an object replication system specifically designed for mobile and weakly-connected environments. Deno uses weighted voting for availability and pair-wise, epidemic information flow for flexibility. This combination allows the protocols to operate with less than full connectivity, to easily adapt to changes in group membership, and to make few assumptions about the underlying network topology. Deno has been implemented and runs on top of Linux and Win32 platforms. We use the Deno prototype to characterize the performance of two versions of Deno's protocol. The first version enables globally serializable execution of update transactions. The second supports a weaker consistency level that still guarantees transactionally-consistent access to replicated data. We demonstrate that the incremental cost of providing global serializability is low, and that speculative dissemination of updates can significantly improve commit performance.
10316420
Balancing push and pull for data broadcast
The increasing ability to interconnect computers through internet-working, wireless networks, high-bandwidth satellite, and cable networks has spawned a new class of information-centered applications based on data dissemination. These applications employ broadcast to deliver data to very large client populations. We have proposed the Broadcast Disks paradigm [Zdon94, Acha95b] for organizing the contents of a data broadcast program and for managing client resources in response to such a program. Our previous work on Broadcast Disks focused exclusively on the “push-based” approach, where data is sent out on the broadcast channel according to a periodic schedule, in anticipation of client requests. In this paper, we study how to augment the push-only model with a “pull-based” approach of using a backchannel to allow clients to send explicit requests for data to the server. We analyze the scalability and performance of a broadcast-based system that integrates push and pull and study the impact of this integration on both the steady state and warm-up performance of clients. Our results show that a client backchannel can provide significant performance improvement in the broadcast environment, but that unconstrained use of the backchannel can result in scalability problems due to server saturation. We propose and investigate a set of three techniques that can delay the onset of saturation and thus, enhance the performance and scalability of the system.
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.
1061791
Disseminating Updates on Broadcast Disks
Lately there has been increasing interest in the use of data dissemination as a means for delivering data from servers to clients in both wired and wireless environments. Using data dissemination, the transfer of data is initiated by servers, resulting in a reversal of the traditional relationship between clients and servers. In previous papers, we have proposed Broadcast Disks as a model for structuring the repetitive transmission of data in a broadcast medium. Broadcast Disks are intended for use in environments where, for either physical or application-dependent reasons, there is asymmetry in the communication capacity between clients and servers. Examples of such environments include wireless networks with mobile clients, cable and direct satellite broadcast, and information dispersal applications. Our initial studies of Broadcast Disks focused on the performance of the mechanism when the data being broadcast did not change. In this paper, we extend those results to incorporate the impact of updates. We first propose several alternative models for updates and examine the fundamental tradeoff that arises between the currency of data and performance. We then propose and analyze mechanisms for implementing these various models. The performance results show that, even in a model where updates must be transmitted immediately, the performance of the Broadcast Disks technique can be made quite mbust through the use of simple techniques for propagating and prefetching data items.
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.