1844352
Supporting aggregate queries over ad-hoc wireless sensor networks
We show how the database community's notion of a generic query interface for data aggregation can be applied to ad-hoc networks of sensor devices. As has been noted in the sensor network literature, aggregation is important as a data reduction tool; networking approaches, however, have focused on application specific solutions, whereas our in-network aggregation approach is driven by a general purpose, SQL-style interface that can execute queries over any type of sensor data while providing opportunities for significant optimization. We present a variety of techniques to improve the reliability and performance of our solution. We also show how grouped aggregates can be efficiently computed and offer a comparison to related systems and database projects.
2815522
Efficient Filtering of XML Documents for Selective Dissemination of Information
Information Dissemination applications are gaining increasing popularity due to dramatic improvements in communications bandwidth and ubiquity. The sheer volume of data available necessitates the use of selective approaches to dissemination in order to avoid overwhelming users with unnecessaryinformation. Existing mechanisms for selective dissemination typically rely on simple keyword matching or “bag of words” information retrieval techniques. The advent of XML as a standard for information exchangeand the development of query languages for XML data enables the development of more sophisticated filtering mechanisms that take structure information into account. We have developed several index organizations and search algorithms for performing efficient filtering of XML documents for large-scale information dissemination systems. In this paper we describe these techniques and examine their performance across a range of document, workload, and scale scenarios.
1006062
The design of an acquisitional query processor for sensor networks
We discuss the design of an acquisitional query processor for data collection in sensor networks. Acquisitional issues are those that pertain to where, when, and how often data is physically acquired (sampled) and delivered to query processing operators. By focusing on the locations and costs of acquiring data, we are able to significantly reduce power consumption over traditional passive systems that assume the a priori existence of data. We discuss simple extensions to SQL for controlling data acquisition, and show how acquisitional issues influence query optimization, dissemination, and execution. We evaluate these issues in the context of TinyDB, a distributed query processor for smart sensor devices, and show how acquisitional techniques can provide significant reductions in power consumption on our sensor devices.
2033914
Data Staging for On-Demand Broadcast
:A>@<b_DCGAdPBEG>R<:c\A8:Q@L]J.A8<0H(L[MOz:CTL0PBc:zbP[<bc4EGADCG ? >@_DA8EHGbP[HP[CTA>@<::ADCTAD<.HTQRJz:CTL0PBcb_DPBEwHw_DPBbP[zbQRA bP0EqPBc\A>Uc\ADPBCGAdP$c:P]HFP z:CGL.PBc:_8PBEwHP[<P]HGHGCFPB_ HG>@?BA4c:P]HFP c\A8QR>@?BA8CGJ P[QRHGA8CG<kP]HG>@?BA2MSLBCQ@PBCG0A&_Q@>RA8<.H  LB:a:QUP]HT>RL0<bE8`v:ADCTAbP0Evz ADAD<Ew>@B<:>Rk_8P[<.HvyL0CGZ HGL]P[CFc:EOc\A8?BA8QRL0:>R<b$LB<\QR>@<:Az:CTL0P0c:_DP0EKHET_F:Adc\a:QR >@<:P[Q@BLBCT>RHG:E MSLBCEGJ\EKHTADE :ADCTA!P[Q@Q c:P]HFP >RHGADEOPBCGAyCGAdPBc\>@QRJPY?]PB>RQUP[z:Q@A>@<¡HG:AEGADCT?BADCd¢ E6P[>@< ADLBCTJB` :A8EGA£EwHGabc:>RAdE(>@B<bLBCTA HG:Ac:P]HFP2P[<: P[0ADAD<.H>UETEwa:AdEOHTbP]HP[CT>@EGA:A8<HG:A c:P[HTP HTL£z A z:CTL0P0c:_DP0EKH£akEKH&z A L0z\HTPB>R<bA8c MSCGL0¤EGA8_DLB<bcbP[CTJ EwHGLBCFP[0A LBC,CTADL[HTA Q@L\_DP]HT>RL0<bE8`¥<¦HT:>@E4bPBkA8C8V  A§:CTLB L0EGA HG:CTADA_LB:Q@ADA8<0HFP[CTJ ̈EGLBQ@a\HG>@LB<kE HGL EGab_F ̈©Ba[«a ¬­«aD®B ̄±°.®_L0<b_A8CG<kED2§L0: LBCGHGa:<:>UEw HG>U_ ET_F:A8c:a:QR>@<:kVEGADCT?BA8C2_DP0_F:>R<bbVP[<bc bCGADMSAHT_F: >@<:b`&bA8EGAHGA8_Fb<:>@3.a:AdE$A ́\:Q@LB>RH:>@<.HTE$:CTL]? >@c:A8c z J,HG:AET_F:A8c\abQR>@<:,P[Q@BLBCT>RHG:,`$μ¶c:AHTPB>RQ@A8c kA8Cw MSLBCTP[<b_DA AD?]P[Q@abP]HT>RL0< akEw>@<:P[<·¥K ̧o1 a:QRHG>U_DPBEwHw zbP0EwAdc HGAdEKHTzkAdc EG:L]vE$HTbP]HHG:AdEwA4c:P]HFP EwHTPBB>@<: HGAd_F:<:>U3.a:A8Ev_8P[< c\CFP[P]HT>@_8P[Q@QRJA8<:bPB<b_A HT:A$kA8Cw MSLBCTP[<b_DA L[M£P Q@PBCG0AEG_8P[Q@A,LB<\c\ADPB<bcz:CTL0P0c  _DP0EKHvEGJ\EKHTAD,`
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.
17986347
Data caching tradeoffs in client-server DBMS architectures
In this paper, we examine the performance tradeoffs that are raised by caching data in the client workstations of a client-server DBMS. We begin by presenting a range of lock-based cache consistency algorithms that arise by viewing cache consistency as a v~iant of the well-understood problem of replicated data management. We then use a detailed simulation model to study the performance of these algorithm over a wide range of workloads end system resource configurations. The results illustrate the key performance tradeoffs related to clientserver cache consistency, and should be of use to designers of next-generation DBMS prototypes and products.
210844
Predictive scheduling of network processors
To provide flexibility in deploying new protocols and services, general-purpose processing engines are being placed in the datapath of routers. Such network processors (NPs) are typically simple RISC multiprocessors that perform forwarding and custom application processing of packets. The inherent unpredictability of execution time of arbitrary instruction code poses a significant challenge in providing service guarantees for data flows that compete for such processing resources in the network. However, we show that network processing workloads are highly regular and predictable, which can be exploited for scheduling purposes. We present two such predictive processor scheduling algorithms that aim at providing service guarantees as well as improving the performance of the NP by increasing the instruction data locality. Simulation results show that these algorithms provide significantly better performance than processor scheduling algorithms that do not take packet processing times into consideration.
37466607
Analysis of parallel mixed-mode simulation algorithms
This paper presents a performance analysis of several parallel algorithms for the mixed-mode simulation of digital systems. The performance model is an architectural simulation of the parallel algorithms running on a hypercube multiprocessor. Workload data is collected from a uniprocessor-based mixed-mode simulator on several benchmark circuits, and two distinct circuit partitioning algorithms are considered. The results indicate that the performance of the parallel simulations is highly circuit dependent, in some cases performing worse than a uniprocessor and in others approaching optimal performance.<<ETX>>
20626063
One-dimensional optimization on multiprocessor systems
This paper presents a straightforward approach to determining how best to utilize an MIMD multiprocessor in the solution of one-dimensional optimization problems involving continuous unimodal functions and nongradient search techniques. A methodology is presented which allows one to consider a variety of speedup functions which may occur in parallel function and systems evaluation. It is shown how the best of two parallel optimization strategies can be determined for a given accuracy, number of processors, and speedup function.
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.
17384542
A general compiler framework for speculative multithreaded processors
Speculative multithreading (SpMT) promises to be an effective mechanism for parallelizing nonnumeric programs, which tend to have irregular and pointer-intensive data structures and complex flows of control. Proper thread formation is crucial for obtaining good speedup in an SpMT system. This paper presents a compiler framework for partitioning a sequential program into multiple threads for parallel execution in an SpMT system. This framework is very general and supports speculative threads, nonspeculative threads, loop-centric threads, and out-of-order thread spawning. It is therefore useful for compiling for a wide variety of SpMT architectures. For effective partitioning of programs, the compiler uses profiling, interprocedural pointer analysis, data dependence information, and control dependence information. The compiler is implemented on the SUIF-MachSUIF platform. A simulation-based evaluation of the generated threads shows that the use of nonspeculative threads and nonloop speculative threads provides a significant increase in speedup for nonnumeric programs.