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.
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.
18485412
Gemini: An Optical Interconnection Network for Parallel Processing
The Gemini interconnect is a dual technology (optical and electrical) interconnection network designed for use in tightly-coupled multicomputer systems. It consists of a circuit-switched optical data path in parallel with a packet-switched electrical control/data path. The optical path is used for transmission of long data messages and the electrical path is used for switch control and transmission of short data messages. The paper describes the architecture of the interconnection network and related communications protocols. Fairness issues associated with network operation are addressed and a discrete-event simulation model of the entire system is described. Network performance characteristics derived from the simulation model are presented. The results show significant performance benefits when using virtual output queuing and quantify the tradeoffs between throughput and fairness in the system.
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.
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.
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.
59766135
Improving Responsiveness for Wide-Area Data Access
Improving Resp onsiveness for WideArea Data AccessLaurent AmsalegPhilipp e BonnetMichael J FranklinINRIABullUniversity of MarylandAnthonyTomasicTolga UrhanINRIAUniversity of MarylandAbstractIn a widearea environment the time rquird to obtain data from remote sources can varyunpredictably due to network congestion link failure or other problems Traditional techniquesfor query optimization and query execution do not cope wel l with such unpredictabilityThestatic nature of those techniques prevents them from adapting to remote access delays that ariseat runtime In this paper we describe two separate but relatedtechniques aimed at tackling thisproblem The rst technique cal led Query Scrambling hides relatively short intermittent delaysby dynamical ly adjusting query execution plans onthey The second technique addresses thelongerterm unavailability of data sources by al lowing the return of partial query answers whensome of the data needed to ful ly answer a query are missingIntro ductionThe continued dramatic growth in global interconnectivity via the Internet has made aroundtheclo ckondemand access to widelydistribu ted data a common exp ectation for many computer users Advances in resource discoery heterogeneous data management and semistructured data managementare providingsemanticto ols to enable the access and correlation of data from diverse widelydistributedsources A limiting factor of suchwork however is the diculty of providing resp onsive data access tousers due to the highly varying resp onsetime and availabilitycharacteristics of remote data sources ina widearea environment Data access over widearea networks inolves a large numb er of data sourcesintermediate sites and communications links all of which are vulnerable to congestion and failuresSuch problems can intro duce signicant and unpredictabledelaysin the access of information fromremote sourcesCurrent distributed query pro cessing approaches p erform p o orly in the widearea environmentThey p ermit unexp ected delays to directly increase the query resp onse time allowing query executionCopyright IEEE Personal use of this material is permitted However permission to reprintrepublish this material for advertising or promotional purposes or for creating new col lective works for resale or rdistribution to serversor lists or to reuse any copyrightedcomponent of this work in other works must be obtainedfrom the IEEEBulletin of the IEEE Computer So cietyTechnical Committee on Data EngineeringThis work was partially supp orted by the NSF under Grant IRI by Bellcore and by an IBM SharedUniversity Researchaward Laurent Amsaleg did this work while he was at the Univy of Maryland and was supp ortedin part by an INRIA Fellowship Philipp e Bonnet and AnthonyTomasic p erformed this work in the context of Dyadean RD jointventure b etween Bull and INRIA
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.
5309390
Uniform Object Management
Most real-world applications require a capability for both general-purpose programming and database transactions on persistent data. Unfortunately, the implementation techniques for these capabilities are notoriously incompatible. Programming languages stress memory-resident transient data with a rich collection of data types, while database systems stress disk-resident persistent data with a limited collection of data types. Even in object-oriented database systems, combining these capabilities is traditionally done using a two-level storage model in which storage formats are quite different. This approach suffers from the performance overhead required to translate data between these two levels.
2276483
Semantic Data Caching and Replacement
We propose a semantic model for client-side caching and replacement in a client-server database system and compare this approach to page caching and tuple caching strategies. Our caching model is based on, and derives its advantages from, three key ideas. First, the client maintains a semantic description of the data in its cache,which allows for a compact specification, as a remainder query, of the tuples needed to answer a query that are not available in the cache. Second, usage information for replacement policies is maintained in an adaptive fashion for semantic regions, which are associated with collections of tuples. This avoids the high overheads of tuple caching and, unlike page caching, is insensitive to bad clustering. Third, maintaining a semantic description of cached data enables the use of sophisticated value functions that incorporate semantic notions of locality, not just LRU or MRU, for cache replacement. We validate these ideas with a detailed performance study that includes traditional workloads as well as a workload motivated by a mobile navigation application.
2567437
Dynamic Query Operator Scheduling for Wide-Area Remote Access
Distributed databases operating over wide-area networks such as the Internet, must deal with the unpredictable nature of the performance of communication. The response times of accessing remote sources can vary widely due to network congestion, link failure, and other problems. In such an unpredictable environment, the traditional iterator-based query execution model performs poorly. We have developed a class of methods, called query scrambling, for dealing explicitly with the problem of unpredictable response times. Query scrambling dynamically modifies query execution plans on-the-fly in reaction to unexpected delays in data access. In this paper we focus on the dynamic scheduling of query operators in the context of query scrambling. We explore various choices for dynamic scheduling and examine, through a detailed simulation, the effects of these choices. Our experimental environment considers pipelined and non-pipelined join processing in a client with multiple remote data sources and delayed or possibly bursty arrivals of data. Our performance results show that scrambling rescheduling is effective in hiding the impact of delays on query response time for a number of different delay scenarios.