SmartNICs are increasingly deployed in datacenters to offload tasks from server CPUs, improving the efficiency and flexibility of datacenter security, networking and storage. Optimizing cloud server efficiency in this way is critically important to ensure that virtually all server resources are available to paying customers. Userspace system software, specifically, decision-making tasks performed by various operating system subsystems, is particularly well suited for execution on mid-tier SmartNIC ARM cores. To this end, we introduce Wave, a framework for offloading userspace system software to processes/agents running on the SmartNIC. Wave uses Linux userspace systems to better align system functionality with SmartNIC capabilities. It also introduces a new host-SmartNIC communication API that enables offloading of even μs-scale system software. To evaluate Wave, we offloaded preexisting userspace system software including kernel thread scheduling, memory management, and an RPC stack to SmartNIC ARM cores, which showed a performance degradation of 1.1%-7.4% in an apples-to-apples comparison with on-host implementations. Wave recovered host resources consumed by on-host system software for memory management (saving 16 host cores), RPCs (saving 8 host cores), and virtual machines (an 11.2% performance improvement). Wave highlights the potential for rethinking system software placement in modern datacenters, unlocking new opportunities for efficiency and scalability.

Cycle-level simulators such as gem5 are widely used in microarchitecture design, but they are prohibitively slow for large-scale design space explorations.We present Concorde, a new methodology for learning fast and accurate performance models of microarchitectures.Unlike existing simulators and learning approaches that emulate each instruction, Concorde predicts the behavior of a program based on compact performance distributions that capture the impact of different microarchitectural components.It derives these performance distributions using simple analytical models that estimate bounds on performance induced by each microarchitectural component, providing a simple yet rich representation of a program's performance characteristics across a large space of microarchitectural parameters.Experiments show that Concorde is more than five orders of magnitude faster than a reference cycle-level simulator, with about 2% average Cycles-Per-Instruction (CPI) prediction error across a range of SPEC, open-source, and proprietary benchmarks.This enables rapid design-space exploration and performance sensitivity analyses that are currently infeasible, e.g., in about an hour, we conducted a first-of-its-kind fine-grained performance attribution to different microarchitectural components across a diverse set of programs, requiring nearly 150 million CPI evaluations.

The discovery of the *lazy neuron phenomenon* (Li et al., 2022), where fewer than 10% of the feedforward networks (FFN) parameters in trained Transformers are activated per token, has spurred significant interests in *activation sparsity* for enhancing large model efficiency. While notable progress has been made in translating such sparsity to wall-time benefits across CPUs, GPUs, and TPUs, modern Transformers have moved away from the ReLU activation function crucial to this phenomenon. Existing efforts on re-introducing activation sparsity, e.g., by reverting to ReLU or applying top-k masking, often degrade model quality, increase parameter count, or complicate training. Sparse attention, the application of sparse activation to the attention mechanism, often face similar challenges. This paper introduces the Spark Transformer, a novel architecture that achieves high activation sparsity in both FFN and the attention mechanism while maintaining model quality, parameter count, and standard training procedures. Our method realizes sparsity via top-$k$ masking for explicit control over sparsity level. Crucially, we introduce *statistical top-k*, a hardware-accelerator-friendly, linear-time approximate algorithm that avoids costly sorting and mitigates significant training slowdown from standard top-k operators. Furthermore, Spark Transformer reallocates existing FFN parameters and attention key embeddings to form a low-cost predictor for identifying activated entries. This design not only mitigates quality loss from enforced sparsity, but also enhances wall-time benefit. Pretrained with the Gemma-2 recipe, Spark Transformer demonstrates competitive performance on standard benchmarks while exhibiting significant sparsity: only 8\% of FFN neurons are activated, and each token attends to a maximum of 256 tokens. This translates to a 2.5x reduction in FLOPs, leading to decoding wall-time speedups of up to 1.79x on CPU and 1.40xon GPU.

Large language models (LLMs) have excelled in various applications, yet serving them at scale is challenging due to their substantial resource demands and high latency. Our real-world studies reveal that over 70% of user requests to LLMs have semantically similar counterparts, suggesting the potential for knowledge transfer among requests. However, naively caching and reusing past responses leads to a big quality drop.

Emerging interconnects make peripherals, such as the network interface controller (NIC), accessible through the processor's cache hierarchy, allowing these devices to participate in the CPU cache coherence protocol. This is a fundamental change from the separate I/O data paths and read-write transaction primitives of today's PCIe NICs. Our experiments show that the I/O data path characteristics cause NICs to prioritize CPU efficiency at the expense of inflated latency, an issue that can be mitigated by the emerging low-latency coherent interconnects. But, the coherence abstraction is not suited to current host-NIC access patterns. Applying existing signaling mechanisms and data structure layouts in a cache-coherent setting results in extraneous communication and cache retention, limiting performance. Redesigning the interface is necessary to minimize overheads and benefit from the new interactions coherence enables. This work contributes CC-NIC, a host-NIC interface design for coherent interconnects. We model CC-NIC using Intel's Ice Lake and Sapphire Rapids UPI interconnects, demonstrating the potential of optimizing for coherence. Our results show a maximum packet rate of 1.5Gpps and 980Gbps packet throughput. CC-NIC has 77% lower minimum latency, and 88% lower at 80% load, than today's PCIe NICs. We also demonstrate application-level core savings. Finally, we show that CC-NIC's benefits hold across a range of interconnect performance characteristics.

Fast DRAM increasingly dominates infrastructure spend in large scale computing environments and this trend will likely worsen without an architectural shift. The cost of deployed memory can be reduced by replacing part of the conventional DRAM with lower cost albeit slower memory media, thus creating a tiered memory system where both tiers are directly addressable and cached. But, this poses numerous challenges in a highly multi-tenant warehouse-scale computing setting. The diversity and scale of its applications motivates an application-transparent solution in the general case, adaptable to specific workload demands.

The global scale and challenging requirements of modern cloud applications have led to the development of complex, widely distributed, service-oriented applications. One enabler of such applications is the remote procedure call (RPC), which provides location-independent communication and hides the myriad of cloud communication complexities and requirements within the RPC stack. Understanding RPCs is thus one key to understanding the behavior of cloud applications. While there have been numerous studies of RPCs in distributed systems, as well as attempts to optimize RPC overheads with both software and hardware, there is still a lack of knowledge about the characteristics of RPCs "in the wild" in the modern cloud environment.

We present evidence and characterization of host congestion in production clusters: adoption of high-bandwidth access links leading to emergence of bottlenecks within the host interconnect (NIC-to-CPU data path). We demonstrate that contention on existing IO memory management units and/or the memory subsystem can significantly reduce the available NIC-to-CPU bandwidth, resulting in hundreds of microseconds of queueing delays and eventual packet drops at hosts (even when running a state-of-the-art congestion control protocol that accounts for CPU-induced host congestion). We also discuss implications of host interconnect congestion to design of future host architecture, network stacks and network protocols.

We are accustomed to thinking of computers as fail-stop, especially the cores that execute instructions, and most system software implicitly relies on that assumption. During most of the VLSI era, processors that passed manufacturing tests and were operated within specifications have insulated us from this fiction. As fabrication pushes towards smaller feature sizes and more elaborate computational structures, and as increasingly specialized instruction-silicon pairings are introduced to improve performance, we have observed ephemeral computational errors that were not detected during manufacturing tests. These defects cannot always be mitigated by techniques such as microcode updates, and may be correlated to specific components within the processor, allowing small code changes to effect large shifts in reliability. Worse, these failures are often "silent" - the only symptom is an erroneous computation.

Access to large amounts of real-world data has long been a barrier to the development and evaluation of analytics applications for the built environment. Open datasets exist, but they are limited in their span (how much data is available) and context (what kind of data is available and how it is described). Evaluation of such analytics is also limited by how the analytics themselves are implemented, often using hard-coded names of building components, points and locations, or unique input data formats. To advance the methodology for how such analytics are implemented and evaluated, we present Mortar: an open testbed for portable building analytics, currently spanning 90 buildings and containing over 9.1 billion data points. All buildings in the testbed are described using Brick, a recently developed metadata schema, providing rich functional descriptions of building assets and subsystems. We also propose a simple architecture for writing portable analytics applications that are robust to the diversity of buildings and can configure themselves based on context. We demonstrate the utility of Mortar by implementing 11 applications from the literature.

We present PC-RPL , a transmission power-controlled IPv6 routing protocol for low-power and lossy wireless networks that significantly improves the end-to-end packet delivery performance under heavy traffic compared to the standard RPL. We show through actual design, implementation, and experiments that a multihop wireless network can achieve better throughput and routing stability when transmission power and routing topology are “jointly and adaptively” controlled. Our experiments show that the predominant “fixed and uniform” transmission power strategy with “link quality and hop distance”–based routing topology construction (i.e., RPL) loses significant bandwidth due to hidden terminal and load imbalance problems. We design an adaptive and distributed control mechanism for transmission power and routing topology, named PC-RPL , on top of the standard RPL routing protocol for hidden terminal mitigation and load balancing. We implement PC-RPL on real embedded devices and evaluate its performance on a 49-node multihop testbed. PC-RPL reduces total end-to-end packet losses by approximately sevenfold without increasing hop distance compared to RPL with the highest transmission power, resulting in 17% improvement in aggregate bandwidth and 64% improvement for the worst-case node by successfully alleviating both hidden terminal and load imbalance problems.

This paper presents MARVEL, a mobile augmented reality (MAR) system which provides a notation display service with imperceptible latency (<100 ms) and low energy consumption on regular mobile devices. In contrast to conventional MAR systems, which recognize objects using image-based computations performed in the cloud, MARVEL mainly utilizes a mobile device's local inertial sensors for recognizing and tracking multiple objects, while computing local optical flow and offloading images only when necessary. We propose a system architecture which uses local inertial tracking, local optical flow, and visual tracking in the cloud synergistically. On top of that, we investigate how to minimize the overhead for image computation and offloading. We have implemented and deployed a holistic prototype system in a commercial building and evaluate MARVEL's performance. The efficient use of a mobile device's capabilities lowers latency and energy consumption without sacrificing accuracy.

The emergence of low-power 32-bit Systems-on-Chip (SoCs), which integrate a 32-bit MCU, radio, and flash, presents an opportunity to re-examine design points and trade-offs at all levels of the system architecture of networked sensors. To this end, we develop a post-SoC/32-bit design point called Hamilton, showing that using integrated components enables a ~$7 core and shifts hardware modularity to design time. We study the interaction between hardware and embedded operating systems, identifying that (1) post-SoC motes provide lower idle current (5.9 μA) than traditional 16-bit motes, (2) 32-bit MCUs are a major energy consumer (e.g., tick increases idle current >50 times), comparable to radios, and (3) thread-based concurrency is viable, requiring only 8.3 μs of context switch time. We design a system architecture, based on a tickless multithreading operating system, with cooperative/adaptive clocking, advanced sensor abstraction, and preemptive packet processing. Its efficient MCU control improves concurrency with ~30% less energy consumption. Together, these developments set the system architecture for networked sensors in a new direction.

Although TCP has widespread adoption in the Internet, wireless sensor networks (WSNs) generally use simpler UDP-based protocols. The few existing TCP implementations for sensor network operating systems do not support all of the features of TCP. We present a full-scale TCP implementation for sensor networks, called TCPlp, based on the TCP protocol logic of the FreeBSD Operating System. Our implementation demonstrates that full-scale TCP can run within the resource constraints of a modern WSN platform, and serves as a vehicle to explore the benefits of using a full TCP stack in the WSN setting. We showcase TCPlp via three applications of TCP: (1) reliable data collection in the context of an application, (2) an interactive configuration/debug shell, and (3) a mote-based web server.

No abstract available.

Operating systems and applications in the built environment have relied upon central authorization and management mechanisms that restrict their scalability, especially with respect to administrative overhead. We propose a new set of primitives encompassing syndication, security, and service execution that unifies the management of applications and services across the built environment, while enabling participants to individually delegate privilege across multiple administrative domains with no loss of security or manageability. We show how to leverage a decentralized authorization syndication platform to extend the design of building operating systems beyond the single administrative domain of a building. The authorization system leveraged is based on blockchain smart contracts to permit decentralized and democratized delegation of authorization without central trust. Upon this, a publish/subscribe syndication tier and a containerized service execution environment are constructed. Combined, these mechanisms solve problems of delegation, federation, device protection and service execution that arise throughout the built environment. We leverage a high-fidelity city-scale emulation to verify the scalability of the authorization tier, and briefly describe a prototypical democratized operating system for the built environment using this foundation. This is an extension of work presented in Ref. [3].

Brick is a recently proposed metadata schema and ontology for describing building components and the relationships between them. It represents buildings as directed labeled graphs using the RDF data model. Using the SPARQL query language, building-agnostic applications query a Brick graph to discover the set of resources and relationships they require to operate. Latency-sensitive applications, such as user interfaces, demand response, and model-predictive control, require fast queries—conventionally less than 100ms. We benchmark a set of popular open source and commercial SPARQL databases against three real Brick models using seven application queries and find that none of them meet this performance target. This lack of performance can be attributed to design decisions that optimize for queries over large graphs consisting of billions of triples but give poor spatial locality and join performance on the small dense graphs typical of Brick. We present the design and evaluation of HodDB, a RDF/SPARQL database for Brick built over a node-based index structure. HodDB performs Brick queries 3--700× faster than leading SPARQL databases and consistently meets the 100ms threshold, enabling the portability of important latency-sensitive building applications. This article is an extension of a previously published work [16].

We show that a multihop wireless network can achieve better bandwidth and routing stability when transmission power and routing topology are jointly and adaptively controlled. Our experiments show that the predominant 'fixed and uniform' transmission power strategy with 'link quality and hop distance'-based routing topology construction loses significant bandwidth due to hidden terminal and load imbalance problems. We design an adaptive and distributed control mechanism for transmission power and routing topology, PCRPL, within the standard RPL routing protocol. We implement PC-RPL on real embedded devices and evaluate its performance on a 49-node multihop testbed. PC-RPL reduces total end-to-end packet losses ~7-fold without increasing hop distance compared to RPL with the highest transmission power, resulting in 17% improvement in aggregate bandwidth and 64% for the worst-case node.

Modern IoT prototyping platforms fall short in terms of energy efficiency, connectivity and software programming practices. We present the design of a new hardware and software platform that addresses these shortcomings by bringing together Mobile, Wearable, Maker and Wireless Sensor Network technologies to enable rapid prototyping with a high degree of synergy and energy efficiency. This is achieved in part by leveraging the Memory Protection Unit on modern microcontrollers along with a novel syscall interface to provide kernel / user isolation and a clean concurrency model. Such a design allows a wide range of languages to be used for application development without significant adaptation. We demonstrate how careful choice of application language allows the naturally asynchronous nature of embedded programming to be expressed cleanly and powerfully. Finally we evaluate the platform in several integrated use cases, providing examples of the capabilities introduced by Synergy.

The study of Operating Systems and Systems Programming provides invaluable software engineering experience and crucial conceptual understanding that make it an essential component of an undergraduate computer science curriculum. It is also imperative that classroom course material and infrastructure keep pace with rapidly evolving technology. A "modern" course will provide an accurate software engineering experience and prevent the study of outdated concepts. With the recent increase in size and popularity of computer science courses, all course material must also be appropriately scalable. In order to create such a "modern" systems course, we redesigned UC Berkeley's CS 162, a 300 student Introduction to Operating Systems & Systems Programming course. In this paper we detail our unique curriculum layout, our advanced infrastructure support for students, and future work on extending our infrastructure for other large computer science courses

Rust, a new systems programming language, provides compile-time memory safety checks to help eliminate runtime bugs that manifest from improper memory management. This feature is advantageous for operating system development, and especially for embedded OS development, where recovery and debugging are particularly challenging. However, embedded platforms are highly event-based, and Rust's memory safety mechanisms largely presume threads. In our experience developing an operating system for embedded systems in Rust, we have found that Rust's ownership model prevents otherwise safe resource sharing common in the embedded domain, conflicts with the reality of hardware resources, and hinders using closures for programming asynchronously. We describe these experiences and how they relate to memory safety as well as illustrate our workarounds that preserve the safety guarantees to the largest extent possible. In addition, we draw from our experience to propose a new language extension to Rust that would enable it to provide better memory safety tools for event-driven platforms.

Sensor network research has facilitated advancements in various domains, such as industrial monitoring, environmental sensing, etc., and research challenges have shifted from creating infrastructure to utilizing it. Extracting meaningful information from sensor data, or control applications using the data, depends on the metadata available to interpret it, whether provided by novel networks or legacy instrumentation. Commercial buildings provide a valuable setting for investigating automated metadata acquisition and augmentation, as they typically comprise large sensor networks, but have limited, obscure metadata that are often meaningful only to the facility managers. Moreover, this primitive metadata is imprecise and varies across vendors and deployments.

In this demonstration, we present a novel system of building control and simulation focused on the integration of the physical and virtual worlds. Actuations and schedules can be manifested either in a physical space or in a virtualization of that space, allowing for more natural interactions with simulations and easier transferring of schedules and configurations from the simulated virtual environment to a real-world deployment. We provide an implementation using a widely used game engine (Unity 3D) and sMAP (Simple Measurement and Actuation Profile), a developed time series database and metadata store.

For the last fifteen years, research explored the hardware, software, sensing, communication abstractions, languages, and protocols that could make networks of small, embedded devices---motes---sample and report data for long periods of time unattended. Today, the application and technological landscapes have shifted, introducing new requirements and new capabilities. Hardware has evolved past 8 and 16 bit microcontrollers: there are now 32 bit processors with lower energy budgets and greater computing capability. New wireless link layers have emerged, creating protocols that support rapid and efficient setup and teardown but introduce novel limitations that systems must consider. The time has come to look beyond optimizing networks of motes. We look towards new technologies such as Bluetooth Low Energy, Cortex M processors, and capable energy harvesting, with new application spaces such as personal area networks, and new capabilities and requirements in security and privacy to inform contemporary hardware and software platforms. It is time for a new, open experimental platform in this post-mote era.

There has been a recent industrial effort to develop multi-resource hierarchical schedulers. However, the existing implementations have some shortcomings in that they might leave resources unallocated or starve certain jobs. This is because the multi-resource setting introduces new challenges for hierarchical scheduling policies. We provide an algorithm, which we implement in Hadoop, that generalizes the most commonly used multi-resource scheduler, DRF [1], to support hierarchies. Our evaluation shows that our proposed algorithm, H-DRF, avoids the starvation and resource inefficiencies of the existing open-source schedulers and outperforms slot scheduling.

A typical large building contains thousands of sensors, monitoring the HVAC system, lighting, and other operational sub-systems. With the increased push for operational efficiency, operators are relying more on historical data processing to uncover opportunities for energy-savings. However, they are overwhelmed with the deluge of data and seek more efficient ways to identify potential problems. In this paper, we present a new approach called the Strip, Bind and Search (SBS); a method for uncovering abnormal equipment behavior and in-concert usage patterns. SBS uncovers relationships between devices and constructs a model for their usage pattern relative to other devices. It then flags deviations from the model. We run SBS on a set of building sensor traces; each containing hundred sensors reporting data flows over 18 weeks from two separate buildings with fundamentally different infrastructures. We demonstrate that, in many cases, SBS uncovers misbehavior corresponding to inefficient device usage that leads to energy waste. The average waste uncovered is as high as 2500~kWh per device.

Over the past 15 years we have created a robust base of embedded networking technology to enable the `macroscope' - the ability to observe complex interactions of physical systems over a substantial extent of space and time. Created to understand the ecophysiology of natural systems, this technology is finding many natural applications in the quest to improve the sustainability of the built environment. In this talk we explore the role of pervasive computing and communications in buildings - where, in the US, we spend 90% of our time, over 70% of our electrical energy, and nearly 50% of our GHG emissions. We examine how pervasive monitoring serves to identify waste and opportunities for energy efficiency; how diverse sources of physical information can be homogenized to enable an innovative application ecosystem; and how a building operating system and services can provide a foundation for advanced control techniques that operate in concert with external factors, such as energy availability and weather, and for personalized environmental conditioning. To be quaint, ”there's a building app for that".

The system is environment monitoring service based on Wireless Sensor Networks (WSN). Users can know temperature, humidity, light, and CO2 level in real time. Excessive electricity consumption by lighting in the office can be saved and the quality of the office environment can become better by controlling lighting and CO2 level.

We present insights obtained from conducting a year-long, 455 meter deployment of wireless plug-load electric meters in a large commercial building. We develop a stratified sampling methodology for surveying the energy use of Miscellaneous Electric Loads (MELs) in commercial buildings, and apply it to our study building. Over the deployment period, we collected over nine hundred million individual readings. Among our findings, we document the need for a dynamic, scalable IPv6 routing protocol which supports point-to-point routing and multiple points of egress. Although the meters are static physically, we find that the set of links they use is dynamic; not using such a dynamic set results in paths that are twice as long. Finally, we conduct a detailed survey of the accuracy possible with inexpensive AC metering hardware. Based on a 21-point automated calibration of a population of 500 devices, we find that it is possible to produce nearly utility-grade metering data.

Buildings are some of the largest energy consumers in the world and yet occupants are regularly dissatisfied with the interior environment in large part due to thermal discomfort [7]. Studies show that given personal control over their environment, occupants are comfortable in a much larger range of ambient temperatures [2]. We present a personalized control smartphone application designed with the dual goals of increasing occupant comfort and achieving building-wide energy savings.

It is often highly valuable for organizations to have their data analyzed by external agents. However, any program that computes on potentially sensitive data risks leaking information through its output. Differential privacy provides a theoretical framework for processing data while protecting the privacy of individual records in a dataset. Unfortunately, it has seen limited adoption because of the loss in output accuracy, the difficulty in making programs differentially private, lack of mechanisms to describe the privacy budget in a programmer's utilitarian terms, and the challenging requirement that data owners and data analysts manually distribute the limited privacy budget between queries.

Heating, ventilation, and air conditioning (HVAC) systems are an important target for efficiency improvements through new equipment and retrofitting because of their large energy footprint. One type of equipment that is common in homes and some offices is an electrical, single-stage heat pump air conditioner (AC). To study this setup, we have built the Berkeley Retrofitted and Inexpensive HVAC Testbed for Energy Efficiency (BRITE) platform. This platform allows us to actuate an AC unit that controls the room temperature of a computer laboratory on the Berkeley campus that is actively used by students, while sensors record room temperature and AC energy consumption. We build a mathematical model of the temperature dynamics of the room, and combining this model with statistical methods allows us to compute the heating load due to occupants and equipment using only a single temperature sensor. Next, we implement a control strategy that uses learning-based model-predictive control (MPC) to learn and compensate for the amount of heating due to occupancy as it varies throughout the day and year. Experiments on BRITE show that our techniques result in a 30%-70% reduction in energy consumption as compared to two-position control, while still maintaining a comfortable room temperature. The energy savings are due to our control scheme compensating for varying occupancy, while considering the transient and steady state electrical consumption of the AC. Our techniques can likely be generalized to other HVAC systems while still maintaining these energy saving features.

Micro-solar power system design is challenging because it must address long-term system behavior under highly variable solar energy conditions and consider a large space of design options. Several micro-solar power systems and models have been made, validating particular points in the whole design space. We provide a general architecture of micro-solar power systems---comprising key components and interconnections among the components---and formalize each component in an analytical or empirical model of its behavior. To model the variability of solar energy, we provide three solar radiation models, depending on the degree of information available: an astronomical model for ideal conditions, an obstructed astronomical model for estimating solar radiation under the presence of shadows and obstructions, and a weather-effect model for estimating solar radiation under weather variation. Our solar radiation models are validated with a concrete design, the HydroWatch node, thus achieving small deviation from the long-term measurement. They can be used in combination with other micro-solar system models to improve the utility of the load and estimate the behavior of micro-solar power systems more accurately. Thus, our solar radiation models provide more accurate estimations of solar radiation and close the loop for micro-solar power system modeling.

Building a micro-solar power system is challenging because it must address long-term system behavior under highly variable solar energy and consider a large design space. We develop a practical theory of micro-solar power systems that is materialized in a simulation suite that models component and system behavior over a long time scale and in an external environment that depends on time, location, weather, and local variations. This simulation provides sufficient accuracy to guide specific design choices in a large design space. Unlike the many macro-solar calculators, this design tool models detailed behavior of milliwatt systems in the worst conditions, rather than typical behavior of kilowatt systems in the best conditions. Our simulation suite is validated with a concrete design of micro-solar power systems, the HydroWatch node. With our simulation suite, micro-solar power systems can be designed in a systematic fashion. Putting the model and empirical vehicle together, the design choices in each component of a micro-solar power system are studied to reach a deployable candidate. The deployment is evaluated by analyzing the effects of different solar profiles across the network. The analysis from the deployment can be used to refine the next system-design iteration.

Interoperability is essential for the commercial adoption of wireless sensor networks. However, existing sensor network architectures have been developed in isolation and thus interoperability has not been a concern. Recently, IP has been proposed as a solution to the interoperability problem of low-power and lossy networks (LLNs), considering its open and standards-based architecture at the network, transport, and application layers. We present two complete and interoperable implementations of the IPv6 protocol stack for LLNs, one for Contiki and one for TinyOS, and show that the cost of interoperability is low: their performance and overhead is on par with state-of-the-art protocol stacks custom built for the two platforms. At the same time, extensive testbed results show that the ensemble performance of a mixed network with nodes running the two interoperable stacks depends heavily on implementation decisions and parameters set at multiple protocol layers. In turn, these results argue that the current industry practice of interoperability testing does not cover the crucial topic of the performance and motivate the need for generic techniques that quantify the performance of such networks and configure their run-time behavior.

Interoperability is key to widespread adoption of sensor network technology, but interoperable systems have traditionally been difficult to develop and test. We demonstrate an interoperable system development and performance diagnosis environment in which different systems, different software, and different hardware can be simulated in a single network configuration. This allows both development, verification, and performance diagnosis of interoperable systems. Estimating the performance is important since even when systems interoperate, the performance can be sub-optimal, as shown in our companion paper that has been conditionally accepted for SenSys 2011.

In distribution and embedded systems, data compression is often used to reduce the size of flash RAM and transmission data, while a rapid decompression speed enables faster rebooting of the compressed program code. We have developed a new data compression algorithm with a high decompression speed and a good compression rate that is equivalent to zlib, the standard technology in use today. We created a LZSS-based algorithm by optimizing the parsing of data strings. LZSS is known as a high decompression speed algorithm useful for embedded systems, and optimal parsing is well known as a method for improving compression rates [1]. Previously, this combination had not been implemented because statistical code length varies during optimal parsing [1]. Our algorithm overcomes this problem by calculating the probability of the literal or the code ( distance and length ) solving the shortest path problem first. It then constructs a simple code set that enables fast decompression using those probabilities and solves the shortest path problem again. Experiments on the standard evaluation data and wireless sensor network program [2] demonstrated that we can achieve a high compression rate equivalent to zlib and a decompression speed that is twice as fast.

We present the architecture, specification, and implementations of a simple monitoring and action profile (sMAP), optimized for sensors, meters, and actuators in building environments. Our architecture is built on HTTP/REST and uses JSON as the object format for interoperability. We implement sMAP on a variety of resource monitors and actuators inside a commercial building, including mote-based wireless sensors and meters running IPv6/6LowPAN, Modbus based panel meters, and external data sources. We show that sMAP is widely implementable and efficient, and our API and schema definitions are expressive and concise. We demonstrate that our architecture is well suited for resource constrained devices using compressed JSON and proxies.

We study the utility of dynamic frequency agility in real-world wireless sensor networks. Many view such agility as essential to obtaining adequate reliability in industrial environments. We quantify the actual utility by identifying the two facets of connectivity graphs that yield potential benefits called Multichannel Links (MCLs) and Multichannel Triangles (MCTs), study how frequently these occur empirically and determine whether multihop provides a comparable solution without the complexity of switching channels. We examine connectivity graphs of live networks over each 802.15.4 channel and find that MCLs and MCTs are extremely rare in practice. Almost no MCLs are found in any connectivity graph while MCTs occur between 0-200 parts per million (ppm). Furthermore, we show that MCLs are rarely important for routing while each MCT has a singlechannel routing solution. We also find that there are channels that are always good for connectivity and offer comparable routing costs, with respect to transmission count, in comparison to multichannel communication. Thus, the justification for channel agility in industrial environments applies in the absence but not in the presence of multihop routing.

As more and more physical information becomes available, a critical problem is enabling the simple and efficient exchange of this data. We present our design for a simple RESTful web service called the Simple Measuring and Actuation Profile (sMAP) which allows instruments and other producers of physical information to directly publish their data. In our design study, we consider what information should be represented, and how it fits into the RESTful paradigm. To evaluate sMAP, we implement a large number of data sources using this profile, and consider how easy it is to use to build new applications. We also design and evaluate a set of adaptations made at each layer of the protocol stack which allow sMAP to run on constrained devices.

With deeply embedded wireless sensors, a new tier of the Internet is emerging that will extend into the physical world. These wireless sensor nodes are expected to vastly outnumber conventional computer hosts as we see them today, but their strict resource constraints are unlike other technologies already common to the Internet. As wireless sensor network research took off, many in the field eschewed the use of IP as inadequate and in contradiction to the needs of wireless sensor networking. Since then, the field has matured and IP has evolved. In this paper, we show that the convergence of Internet Protocol Version 6 (IPv6) and low-power multihop wireless networking is possible, pragmatic, and efficient-especially in regard to the metrics that matter most for embedded applications, low memory footprint, high reliability, and low energy usage. Using real commercial deployments, we show that it is possible to simultaneously achieve an average duty cycle of99.9%, and average per-hop latency of <; 125 ms over 12 months in different environments.

We describe the design, deployment, and experience with a wireless sensor network for high-fidelity monitoring of electrical usage in buildings. A network of 38 mote-class AC meters, 6 light sensors, and 1 vibration sensor is used to determine and audit the energy envelope of an active laboratory. Classic WSN issues of coverage, aggregation, sampling, and inference are shown to appear in a novel form in this context. The fundamental structuring principle is the underlying load tree, and a variety of techniques are described to disambiguate loads within this structure. Utilizing contextual metadata, this information is recomposed in terms of its spatial, functional, and individual projections. This suggests a path to broad use of WSN technology in energy and environmental domains.

We present Epic, an open mote platform for application-driven design. Sensornet platforms, like most embedded systems, are tightly coupled to their applications. This coupling can make it difficult for general-purpose platforms to address application-specific needs, forcing platform designers to repeatedly reimplement functionality. Inspired by the hierarchical nature of software and integrated circuit design, we propose sensornet platforms be composed hierarchically from a family of modular components. This approach makes platform development accessible to a much wider community; developers do not need to be analog, sensor, or radio frequency experts, and can instead reuse components that encapsulate the needed functionality.

We present Disco, an asynchronous neighbor discovery and rendezvous protocol that allows two or more nodes operating their radios at low duty cycles (e.g. 1%) to discover and communicate with each other during opportunistic encounters and without any prior synchronization information.

We present iCount, a new energy meter design. For many systems that have a built-in switching regulator, adding a single wire between the regulator and the microcontroller enables real-time energy metering. iCount measures energy usage by counting the switching cycles of the regulator. We show that the relationship between load current and switching frequency is quite linear and demonstrate that this simple design can be applied to a variety of regulators. Our particular implementation exhibits a maximum error of less than plusmn20% over five decades of current draw, a resolution exceeding 1 muJ, a read latency of 15 mus, and a power overhead that ranges from 1% when the node is in standby to 0.01 % when the node is active, for a typical workload. The basic iCount design requires only a pulse frequency modulated switching regulator and a microcontroller with an externally-clocked counter.

This paper describes a systematic approach to building micro-solar power subsystems for wireless sensor network nodes. Our approach composes models of the basic pieces - solar panels, regulators, energy storage elements, and application loads - to appropriately select and size the components. We demonstrate our approach in the context of a microclimate monitoring project through the design of the node, micro-solar subsystem, and network, which is deployed in a challenging, deep forest setting. We evaluate our deployment by analyzing the effects of the range of solar profiles experienced across the network.

We present Disco, an asynchronous neighbor discovery and rendezvous protocol that allows two or more nodes to operate their radios at low duty cycles (e.g. 1%) and yet still discover and communicate with one another during infrequent, opportunistic encounters without requiring any prior synchronization information. The key challenge is to operate the radio at a low duty cycle but still ensure that discovery is fast, reliable, and predictable over a range of operating conditions. Disco nodes pick a pair of prime numbers such that the sum of their reciprocals is equal to the desired radio duty cycle. Each node increments a local counter with a globallyfixed period. If a node's local counter value is divisible by either of its primes, then the node turns on its radio for one period. This protocol ensures that two nodes will have some overlapping radio on-time within a bounded number of periods, even if nodes independently set their own duty cycle. Once a neighbor is discovered, and its wakeup schedule known, rendezvous is just a matter of being awake during the neighbor's next wakeup period,for synchronous rendezvous, or during an overlapping wake period, for asynchronous rendezvous.

We present a building block approach to hardware platform design based on a decade of collective experience in this area, arriving at an architecture in which general-purpose modules that require expertise to de sign and incorporate commonly-used functionality are integrated with application-specific carriers that satisfy the unique sensing, power supply, and mechanical constraints of an application. Of course, modules are widespread, but our focus is far less on the performance of any individual module and far more on an overall architecture that supports the prototype, pilot, and production stages of design, and preserves the artifacts and learnings accumulated along the way.

A decade ago as wireless sensor network research took off many researchers in the field denounced the use of IP as inadequate and in contradiction to the needs of wireless sensor networking. Since then the field has matured, standard links have emerged, and IP has evolved. In this paper, we present the design of a complete IPv6-based network architecture for wireless sensor networks. We validate the architecture with a production-quality implementation that incorporates many techniques pioneered in the sensor network community, including duty-cycled link protocols, header compression, hop-by-hop forwarding, and efficient routing with effective link estimation. In addition to providing interoperability with existing IP devices, this implementation was able to achieve an average duty-cycle of 0.65%, average per-hop latency of 62ms, and a data reception rate of 99.98% over a period of 4 weeks in a real-world home-monitoring application where each node generates one application packet per minute. Our results outperform existing systems that do not adhere to any particular standard or architecture. In light of this demonstration of full IPv6 capability, we review the central arguments that led the field away from IP. We believe that the presence of an architecture, specifically an IPv6-based one, provides a strong foundation for wireless sensor networks going forward.

A home where every major appliance can be monitored for energy consumption and individually controlled wirelessly has long been a dream of gadgeteers and the green-conscious alike. Research has shown that real-time, per-appliance electricity usage feedback can induce behavior changes that lead to 10% to 20% reduction in usage [2].

As the number of wireless devices increase, the frequency spectrum becomes further congested. Deployments of wireless devices in harsh radio environments (i.e. an industrial plant) also motivates the study of alternate communication protocols that offer enough diversity to overcome interference. This work explores the use of frequency diversity to address this problem and examines its effectiveness in various environmental settings. We also examine the interplay between frequency agility at the MAC layer and route diversity in the network layer and look to understand the cost-tradeoffs in the diversity of choices offered by each layer.

We present SPOT, a scalable power observation tool that enables in situ measurement of nodal power and energy over a dynamic range exceeding four decades or a temporal resolution of microseconds. Using SPOT, every node in a sensor network can now be instrumented, providing unparalleled visibility into the dynamic power profile of applications and system software. Power metering at every node enables previously impossible empirical evaluation of low power designs at scale. The SPOT architecture and design meet challenges unique to wireless sensor networks and other low power systems, such as orders of magnitude difference in current draws between sleep and active states, short-duration power spikes during periods of brief activity, and the need for minimum perturbation of the system under observation.

A Wireless Sensor Network (WSN) for Structural Health Monitoring (SHM) is designed, implemented, deployed and tested on the 4200ft long main span and the south tower of the Golden Gate Bridge (GGB). Ambient structural vibrations are reliably measured at a low cost and without interfering with the operation of the bridge. Requirements that SHM imposes on WSN are identified and new solutions to meet these requirements are proposed and implemented. In the GGB deployment, 64 nodes are distributed over the main span and the tower, collecting ambient vibrations synchronously at 1kHz rate, with less than 10μs jitter, and with an accuracy of 30μG. The sampled data is collected reliably over a 46-hop network, with a bandwidth of 441B/s at the 46th hop. The collected data agrees with theoretical models and previous studies of the bridge. The deployment is the largest WSN for SHM.

We present Flush, a reliable, high goodput bulk data transport protocol for wireless sensor networks. Flush provides end-to-end reliability, reduces transfer time, and adapts to time-varying network conditions. It achieves these properties using end-to-end acknowledgments, implicit snooping of control information, and a rate-control algorithm that operates at each hop along a flow. Using several real network topologies, we show that Flush closely tracks or exceeds the maximum goodput achievable by a hand-tuned but fixed rate for each hop over a wide range of path lengths and varying network conditions. Flush is scalable; its effective bandwidth over a 48-hop wireless network is approximately one-third of the rate achievable over one hop. The design of Flush is simplified by assuming that different flows do not interfere with each other, a reasonable restriction for many sensornet applications that collect bulk data in a coordinated fashion, like structural health monitoring, volcanic activity monitoring, or protocol evaluation. We collected all of the performance data presented in this paper using Flush itself.

Energy management is a critical concern in wireless sensornets. Despite its importance, sensor network operating systems today provide minimal energy management support, requiring applications to explicitly manage system power states. To address this problem, we present ICEM, a device driver architecture that enables simple, energy efficient wireless sensornet applications. The key insight behind ICEM is that the most valuable information an application can give the OS for energy management is its concurrency. Using ICEM, a low-rate sensing application requires only a single line of energy management code and has an efficiency within 1.6 % of a hand-tuned implementation. ICEM’s effectiveness questions the assumption that sensornet applications must be responsible for all power management and sensornets cannot have a standardized OS with a simple API.

We present design patterns used by software components in the TinyOS sensor network operating system. They differ significantly from traditional software design patterns because of the constraints of sensor networks and to TinyOS's focus on static allocation and whole-program composition. We describe how nesC has evolved to support these design patterns by including a few simple language primitives and optimizations.

A number of multi-hop, wireless, network programming systems have emerged for sensor network retasking but none of these systems support a cryptographically-strong, public-key-based system for source authentication and integrity verification. The traditional technique for authenticating a program binary, namely a digital signature of the program hash, is poorly suited to resource-contrained sensor nodes. Our solution to the secure programming problem leverages authenticated streams, is consistent with the limited resources of a typical sensor node, and can be used to secure existing network programming systems. Under our scheme, a program binary consists of several code and data segments that are mapped to a series of messages for transmission over the network. An advertisement, consisting of the program name, version number, and a hash of the very first message, is digitally signed and transmitted first. The advertisement authenticates the first message, which in turn contains a hash of the second message. Similarly, the second message contains a hash of the third message, and so on, binding each message to the one logically preceding it in the series through the hash chain. We augmented the Deluge network programming system with our protocol and evaluated the resulting system performance.

We present the philosophy, design, and initial evaluation of the Trio Testbed, a new outdoor sensor network deployment that consists of 557 solar-powered motes, seven gateway nodes, and a root server. The testbed covers an area of approximately 50,000 square meters and was in continuous operation during the last four months of 2005. This new testbed in one of the largest solar-powered outdoor sensor networks ever constructed and it offers a unique platform on which both systems and application software can be tested safely at scale. The testbed is based on Trio, a new mote platform that provides sustainable operation, enables efficient in situ interaction, and supports fail-safe programming. The motivation behind this testbed was to evaluate robust multi-target tracking algorithms at scale. However, using the testbed has stressed the system software, networking protocols, and management tools in ways that have exposed subtle but serious weaknesses that were never discovered using indoor testbeds or smaller deployments. We have been iteratively improving our support software, with the eventual aim of creating a stable hardware-software platform for sustainable, scalable, and flexible testbed deployments.

In this study, we implement six ranging-based localization algorithms from the literature and evaluate them in simulations that employ real-world ultrasound ranging data. We find that small variations in the ranging model can lead to large variations in localization error. We analyze each algorithm to identify how implicit assumptions may be violated by empirical ranging data and why this changes the behavior of the algorithm.

A main challenge with developing applications for wireless embedded systems is the lack of visibility and control during execution of an application. In this paper, we present a tool suite called Marionette that provides the ability to call functions and to read or write variables on pre-compiled, embedded programs at run-time, without requiring the programmer to add any special code to the application. This rich interface facilitates interactive development and debugging at minimal cost to the node.

No abstract available.

The operation of wireless sensor networks is fundamentally constrained by available energy sources. The underlying hardware determines the power draw of each possible mode of operation. System software attempts maximize the use of the lowest possible modes of each of the subsystems. This tutorial paper describes the system software techniques used at several levels. At the application sensing level, this includes duty-cycling, sensor hierarchy, and aggregation. At the communication level, it includes low-power listening, communication scheduling, piggybacking, post-hoc synchronization, and power-aware routing. At the node OS level, it includes event driven execution with split-phase operation and cooperative power management interfaces. At the lowest level, it includes management of primary and secondary energy storage devices coupled with intelligent charge transfer scheduling. All of these aspects must be integrated in a systematic software framework.

Summary form only given. Networks of intelligent sensors that are distributed through the physical world will revolutionize practices in the life sciences, civil engineering, manufacturing, security, agriculture, ubiquitous computing, and many other areas. They also present an opportunity and a need to explore distributed algorithms that are wedded to the noisy, localized, time varying physical world. Bandwidth, storage, and energy limitations make in-network processing essential - within the node and among collections of nodes. The algorithms should be resource efficient, but also deal with noise, uncertainty and dynamically changing connectivity. A broad research community has been exploring these issues in the context of TinyOS and the Berkeley motes. This talk will highlight novel distributed algorithms coming out of these efforts and discuss issues in making such networks robust and programmable

We present the design of the extreme scale mote, a new sensor network platform for reliably detecting and classifying, and quickly reporting, rare, random, and ephemeral events in a large-scale, long-lived, and ret askable manner. This new mote was designed for the ExScal project which seeks to demonstrate a 10,000 node network capable of discriminating civilians, soldiers and vehicles, spread out over a 10 km/sup 2/ area, with node lifetimes approaching 1,000 hours of continuous operation on two AA alkaline batteries. This application posed unique functional, usability, scalability, and robustness requirements which could not be met with existing hardware, and therefore motivated the design of a new platform. The detection and classification requirements are met using infrared, magnetic, and acoustic sensors. The infrared and acoustic sensors are designed for low-power continuous operation and include asynchronous processor wakeup circuitry. The usability and scalability requirements are met by minimizing the frequency and cost of human-in-the-loop operations during node deployment, activation, and verification through improvements in the user interface, packaging, and configurability of the platform. Recoverable retasking is addressed by using a grenade timer that periodically forces a system reset. The key contributions of this work are a specific design point and general design methods for building sensor network platforms to detect exceptional events.

Environmental energy is an attractive power source for low power wireless sensor networks. We present Prometheus, a system that intelligently manages energy transfer for perpetual operation without human intervention or servicing. Combining positive attributes of different energy storage elements and leveraging the intelligence of the microprocessor, we introduce an efficient multi-stage energy transfer system that reduces the common limitations of single energy storage systems to achieve near perpetual operation. We present our design choices, tradeoffs, circuit evaluations, performance analysis, and models. We discuss the relationships between system components and identify optimal hardware choices to meet an application's needs. Finally we present our implementation of a real system that uses solar energy to power Berkeley's Telos Mote. Our analysis predicts the system will operate for 43 years under 1% load, 4 years under 10% load, and 1 year under 100% load. Our implementation uses a two stage storage system consisting of supercapacitors (primary buffer) and a lithium rechargeable battery (secondary buffer). The mote has full knowledge of power levels and intelligently manages energy transfer to maximize lifetime.

We present Telos, an ultra low power wireless sensor module ("mote") for research and experimentation. Telos is the latest in a line of motes developed by UC Berkeley to enable wireless sensor network (WSN) research. It is a new mote design built from scratch based on experiences with previous mote generations. Telos' new design consists of three major goals to enable experimentation: minimal power consumption, easy to use, and increased software and hardware robustness. We discuss how hardware components are selected and integrated in order to achieve these goals. Using a Texas Instruments MSP430 microcontroller, Chipcon IEEE 802.15.4-compliant radio, and USB, Telos' power profile is almost one-tenth the consumption of previous mote platforms while providing greater performance and throughput. It eliminates programming and support boards, while enabling experimentation with WSNs in both lab, testbed, and deployment settings.

This paper presents a study of how empirical ranging characteristics affect multihop localization in wireless sensor networks. We use an objective metric to evaluate a well-established parametric model of ranging called Noisy Disk: if the model accurately predicts the results of a real-world deployment, it sufficiently captures ranging characteristics. When the model does not predict accurately, we systematically replace components of the model with empirical ranging characteristics to identify which components contribute to the discrepancy. We reveal that both the connectivity and noise components of Noisy Disk fail to accurately represent real-world ranging characteristics and show that these shortcomings affect localization in different ways under different circumstances.

We present design patterns used by software components in the TinyOS operating system. They differ significantly from traditional software design patterns due to TinyOS's focus on static allocation and whole-program composition. We describe how nesC has evolved to support design patterns by including a few simple language primitives

The Macroscope is a conceptual instrument for perceiving complex interactions, such as what occurs is ecosystems, social systems, and large-scale industrial settings. Sensor networks are a significant step toward such an instrument, because of the fidelity they offer in monitoring large regions of space and large collections of things. This talk describes our experiences in developing and deploying a large sensor network for microclimate monitoring of coastal redwood forests as a basis for studies in redwood ecophysiology. It summarizes the architecture, its implementation, and the many lessons and surprises encountered along the way. The effort produced unprecedented recordings of the microclimate dynamics indicating how these huge organisms interact with their environment.

Project ExScal (for extreme scale) fielded a 1000+ node wireless sensor network and a 200+ node peer-to-peer ad hoc network of 802.11 devices in a 13km by 300m remote area in Florida, USA during December 2004. In comparison with previous deployments, the ExScal application is relatively complex and its networks are the largest ones of either type fielded to date. In this paper, we overview the key requirements of ExScal, the corresponding design of the hardware/software platform and application, and some results of our experiments.

Recent technological advances and the continuing quest for greater efficiency have led to an explosion of link and network protocols for wireless sensor networks. These protocols embody very different assumptions about network stack composition and, as such, have limited interoperability. It has been suggested [3] that, in principle, wireless sensor networks would benefit from a unifying abstraction (or "narrow waist" in architectural terms), and that this abstraction should be closer to the link level than the network level. This paper takes that vague principle and turns it into practice, by proposing a specific unifying sensornet protocol (SP) that provides shared neighbor management and a message pool.The two goals of a unifying abstraction are generality and efficiency: it should be capable of running over a broad range of link-layer technologies and supporting a wide variety of network protocols, and doing so should not lead to a significant loss of efficiency. To investigate the extent to which SP meets these goals, we implemented SP (in TinyOS) on top of two very different radio technologies: B-MAC on mica2 and IEEE 802.15.4 on Telos. We also built a variety of network protocols on SP, including examples of collection routing [53], dissemination [26], and aggregation [33]. Measurements show that these protocols do not sacrifice performance through the use of our SP abstraction.

The wireless sensor network "macroscope" offers the potential to advance science by enabling dense temporal and spatial monitoring of large physical volumes. This paper presents a case study of a wireless sensor network that recorded 44 days in the life of a 70-meter tall redwood tree, at a density of every 5 minutes in time and every 2 meters in space. Each node measured air temperature, relative humidity, and photosynthetically active solar radiation. The network captured a detailed picture of the complex spatial variation and temporal dynamics of the microclimate surrounding a coastal redwood tree. This paper describes the deployed network and then employs a multi-dimensional analysis methodology to reveal trends and gradients in this large and previously-unobtainable dataset. An analysis of system performance data is then performed, suggesting lessons for future deployments.

We study four distributed techniques for computing the area of a region in a sensor network. Area calculation is a fundamental sensor network primitive, and distributed, in-network approaches prove more scalable than centralized collection in terms of energy consumption. The four techniques - Delaunay triangulations, Voronoi diagrams, and two new, simpler algorithms, inverse neighborhood and inverse neighborhood with location - vary in computational complexity, communication cost, and information required from the sensor network. We conclude that when sensors know their physical locations, our simple and efficient inverse-neighborhood approach performs comparably to more systematic, but more expensive, computational geometry algorithms. We also analyze the effects of radio range and deployment density on accuracy, and show that topologies derived from real testbeds behave quite differently from commonly seen random topologies with unit disk connectivity.

This paper proposes a neighborhood programming abstraction for sensor networks, wherein a node can identify a subset of nodes around it by a variety of criteria and share state with those nodes. This abstraction allows developers to design distributed algorithms in terms of the neighborhood abstraction itself, instead of decomposing them into component parts such as messaging protocols, data caches, and neighbor lists. In those applications that are already neighborhood-based, this abstraction is shown to facilitate good application design and to reduce algorithmic complexity, inter-component coupling, and total lines of code. The abstraction as defined here has been successfully used to implement several complex applications and is shown to capture the essence of many more existing distributed sensor network algorithms.

We present an incremental network programming mechanism which re programs wireless sensors quickly by transmitting the incremental changes for the new program version. Using the Rsync algorithm we generate the difference of the two program images, which allows us to distribute just the key changes of the program. Unlike previous approaches, our design does not assume any prior knowledge of the program code structure and can be applied to any hardware platform. To meet the resource constraints of wireless sensors we tuned the Rsync algorithm which was originally made for updating binary files among computationally powerful machines. In our design, the sensor node processes the delivery and the decoding of the difference script in separate steps. This makes it easy to extend for multi-hop network programming. We are able to achieve the speedup of 9.1 for changing a constant and 2.1 to 2.5 for changing a few lines in the source code over the non-incremental delivery.

Many applications in wireless sensor networks, including structure monitoring, require collecting all data without loss from the nodes. End-to-end retransmission, which is used in the Internet for reliable transport, becomes very inefficient in wireless sensor networks, since wireless communication, and constrained resources pose new challenges. We look at factors affecting reliability, and search for efficient combinations of the possible options. Information redundancy like retransmission, and erasure codes, can be used. Route fix, which tries alternative next hop after some failures, also reduces packet loss. We implemented and evaluated these options on a real test bed of Berkeley Mica2Dot motes. Our experimental results show that each option overcomes different kinds of failures. Link-level retransmission is efficient but limited in achieving reliability. Erasure code enables very high reliability by tolerating packet losses. Route fix responds to link failures quickly. Previous work had found it difficult to increase reliability past a certain threshold. We show that the right combination of primitives can yield more than 99% reliability with low overhead, providing a viable alternative to end-to-end retransmission over multiple hops.

To support network programming, we present Deluge, a reliable data dissemination protocol for propagating large data objects from one or more source nodes to many other nodes over a multihop, wireless sensor network. Deluge builds from prior work in density-aware, epidemic maintenance protocols. Using both a real-world deployment and simulation, we show that Deluge can reliably disseminate data to all nodes and characterize its overall performance. On Mica2-dot nodes, Deluge can push nearly 90 bytes/second, one-ninth the maximum transmission rate of the radio supported under TinyOS. Control messages are limited to 18% of all transmissions. At scale, the protocol exposes interesting propagation dynamics only hinted at by previous dissemination work. A simple model is also derived which describes the limits of data propagation in wireless networks. Finally, we argue that the rates obtained for dissemination are inherently lower than that for single path propagation. It appears very hard to significantly improve upon the rate obtained by Deluge and we identify establishing a tight lower bound as an open problem.

We propose B-MAC, a carrier sense media access protocol for wireless sensor networks that provides a flexible interface to obtain ultra low power operation, effective collision avoidance, and high channel utilization. To achieve low power operation, B-MAC employs an adaptive preamble sampling scheme to reduce duty cycle and minimize idle listening. B-MAC supports on-the-fly reconfiguration and provides bidirectional interfaces for system services to optimize performance, whether it be for throughput, latency, or power conservation. We build an analytical model of a class of sensor network applications. We use the model to show the effect of changing B-MAC's parameters and predict the behavior of sensor network applications. By comparing B-MAC to conventional 802.11-inspired protocols, specifically SMAC, we develop an experimental characterization of B-MAC over a wide range of network conditions. We show that B-MAC's flexibility results in better packet delivery rates, throughput, latency, and energy consumption than S-MAC. By deploying a real world monitoring application with multihop networking, we validate our protocol design and model. Our results illustrate the need for flexible protocols to effectively realize energy efficient sensor network applications.

Habitat and environmental monitoring is a driving application for wireless sensor networks. We present an analysis of data from a second generation sensor networks deployed during the summer and autumn of 2003. During a 4 month deployment, these networks, consisting of 150 devices, produced unique datasets for both systems and biological analysis. This paper focuses on nodal and network performance, with an emphasis on lifetime, reliability, and the the static and dynamic aspects of single and multi-hop networks. We compare the results collected to expectations set during the design phase: we were able to accurately predict lifetime of the single-hop network, but we underestimated the impact of multi-hop traffic overhearing and the nuances of power source selection. While initial packet loss data was commensurate with lab experiments, over the duration of the deployment, reliability of the backend infrastructure and the transit network had a dominant impact on overall network performance. Finally, we evaluate the physical design of the sensor node based on deployment experience and a post mortem analysis. The results shed light on a number of design issues from network deployment, through selection of power sources to optimizations of routing decisions.

In this paper, we present a structure for monitoring a large set of computational clusters. We illustrate methods for scaling a monitor network comprised of many clusters while keeping processing requirements low. A design for presenting high-level Web-based summaries of the monitor network is provided, along with a generalization to a distributed, multiple-resolution monitoring tree. Emphasis is placed on scalability, fast query response, fault tolerance, and grid compatibility. Experimental evidence is presented that demonstrates the performance of our design.

We present nesC, a programming language for networked embedded systems that represent a new design space for application developers. An example of a networked embedded system is a sensor network, which consists of (potentially) thousands of tiny, low-power "motes," each of which execute concurrent, reactive programs that must operate with severe memory and power constraints.nesC's contribution is to support the special needs of this domain by exposing a programming model that incorporates event-driven execution, a flexible concurrency model, and component-oriented application design. Restrictions on the programming model allow the nesC compiler to perform whole-program analyses, including data-race detection (which improves reliability) and aggressive function inlining (which reduces resource consumption).nesC has been used to implement TinyOS, a small operating system for sensor networks, as well as several significant sensor applications. nesC and TinyOS have been adopted by a large number of sensor network research groups, and our experience and evaluation of the language shows that it is effective at supporting the complex, concurrent programming style demanded by this new class of deeply networked systems.

Accurate and scalable simulation has historically been a key enabling factor for systems research. We present TOSSIM, a simulator for TinyOS wireless sensor networks. By exploiting the sensor network domain and TinyOS's design, TOSSIM can capture network behavior at a high fidelity while scaling to thousands of nodes. By using a probabilistic bit error model for the network, TOSSIM remains simple and efficient, but expressive enough to capture a wide range of network interactions. Using TOSSIM, we have discovered several bugs in TinyOS, ranging from network bit-level MAC interactions to queue overflows in an ad-hoc routing protocol. Through these and other evaluations, we show that detailed, scalable sensor network simulation is possible.

The dynamic and lossy nature of wireless communication poses major challenges to reliable, self-organizing multihop networks. These non-ideal characteristics are more problematic with the primitive, low-power radio transceivers found in sensor networks, and raise new issues that routing protocols must address. Link connectivity statistics should be captured dynamically through an efficient yet adaptive link estimator and routing decisions should exploit such connectivity statistics to achieve reliability. Link status and routing information must be maintained in a neighborhood table with constant space regardless of cell density. We study and evaluate link estimator, neighborhood table management, and reliable routing protocol techniques. We focus on a many-to-one, periodic data collection workload. We narrow the design space through evaluations on large-scale, high-level simulations to 50-node, in-depth empirical experiments. The most effective solution uses a simple time averaged EWMA estimator, frequency based table management, and cost-based routing.

Composed of tens of thousands of tiny devices with very limited resources ("motes"), sensor networks are subject to novel systems problems and constraints. The large number of motes in a sensor network means that there will often be some failing nodes; networks must be easy to repopulate. Often there is no feasible method to recharge motes, so energy is a precious resource. Once deployed, a network must be reprogrammable although physically unreachable, and this reprogramming can be a significant energy cost.We present Maté, a tiny communication-centric virtual machine designed for sensor networks. Maté's high-level interface allows complex programs to be very short (under 100 bytes), reducing the energy cost of transmitting new programs. Code is broken up into small capsules of 24 instructions, which can self-replicate through the network. Packet sending and reception capsules enable the deployment of ad-hoc routing and data aggregation algorithms. Maté's concise, high-level program representation simplifies programming and allows large networks to be frequently reprogrammed in an energy-efficient manner; in addition, its safe execution environment suggests a use of virtual machines to provide the user/kernel boundary on motes that have no hardware protection mechanisms.

This paper presents a performance analysis of market-based batch schedulers for clusters of workstations. In contrast to previous work, we use user-centric performance metrics as the basis for system evaluation. Each user is modeled as having a utility function for each job which measures value delivered to the user as function of execution time. Summing over all utility functions in the workload, we use aggregate utility as a measure of overall value delivered to users. With aggregate utility as the performance metric, simulations are used to quantify the performance of both market-based and traditional batch scheduling algorithms under a variety of synthetic work-loads. Results show that an auction-based batch scheduling algorithm improves performance by a factor of up to 2-5x for sequential workloads and up to 14x for highly parallel workloads compared to traditional scheduling algorithms.

We propose a SAN architecture called Queue Pair IP (QPIP) that combines the interface from industry proposals for low overhead, high bandwidth networks, e.g. Infiniband, with the well established inter-network protocol suite. We evaluate how effectively the queue pair abstraction enables inter-network protocol offload We develop a prototype QPIP system that implements basic queue pair operations over a subset of TCP, UDP and IPv6 protocols using a programmable network adapter. We assess this prototype in terms of basic application performance, underlying processing costs, and a network storage application. With modest hardware support, QPIP can perform as well as traditional inter-network protocol implementations at a fraction of the host CPU overhead. With hardware support equivalent to Infiniband, QPIP would achieve similar performance targets.

Abstract We present the results of a detailed study of the Virtual Interface (VI) paradigm as a communication foundation for a distributed computing environment. Using Active Messages and the Split‐C global memory model, we analyze the inherent costs of using VI primitives to implement these high‐level communication abstractions. We demonstrate a minimum mapping cost (i.e. the host processing required to map one abstraction to a lower abstraction) of 5.4 μs for both Active Messages and Split‐C using four‐way 550 MHz Pentium III SMPs and the Myrinet network. We break down this cost to the use of individual VI primitives in supporting flow control, buffer management and event processing and identify the completion queue as the source of the highest overhead. Bulk transfer performance plateaus at 44 Mbytes/s for both implementations are due to the addition of fragmentation requirements. Based on this analysis, we present the implications for the VI successor, Infiniband. Copyright © 2002 John Wiley & Sons, Ltd.

We argue that existing OS designs are ill-suited for the needs of Internet service applications. These applications demand massive concurrency (supporting a large number of requests per second) and must be well-conditioned to load (avoiding degradation of performance and predictability when demand exceeds capacity). The transparency and virtualization provided by existing operating systems leads to limited concurrency and lack of control over resource usage. We claim that Internet services would be far better supported by operating systems by reconsidering the role of resource virtualization. We propose a new design for server applications, the staged event-driven architecture (SEDA). In SEDA, applications are constructed as a set of event driven stages separated by queues. We present the SEDA architecture and its consequences for operating system design.

As sensor networks edge closer towards wide-spread deployment, security issues become a central concern. So far, much research has focused on making sensor networks feasible and useful, and has not concentrated on security.

We study the problem of media access control in the novel regime of sensor networks, where unique application behavior and tight constraints in computation power, storage, energy resources, and radio technology have shaped this design space to be very different from that found in traditional mobile computing regime. Media access control in sensor networks must not only be energy efficient but should also allow fair bandwidth allocation to the infrastructure for all nodes in a multihop network. We propose an adaptive rate control mechanism aiming to support these two goals and find that such a scheme is most effective in achieving our fairness goal while being energy efficient for both low and high duty cycle of network traffic.

We propose a new design for highly concurrent Internet services, which we call the staged event-driven architecture (SEDA). SEDA is intended to support massive concurrency demands and simplify the construction of well-conditioned services. In SEDA, applications consist of a network of event-driven stages connected by explicit queues. This architecture allows services to be well-conditioned to load, preventing resources from being overcommitted when demand exceeds service capacity. SEDA makes use of a set of dynamic resource controllers to keep stages within their operating regime despite large fluctuations in load. We describe several control mechanisms for automatic tuning and load conditioning, including thread pool sizing, event batching, and adaptive load shedding. We present the SEDA design and an implementation of an Internet services platform based on this architecture. We evaluate the use of SEDA through two applications: a high-performance HTTP server and a packet router for the Gnutella peer-to-peer file sharing network. These results show that SEDA applications exhibit higher performance than traditional service designs, and are robust to huge variations in load.

Dependable network computing is becoming a key part of our daily economic and social life. Every day, millions of users and businesses are utilizing the Internet infrastructure for real-time electronic commerce transactions, scheduling important events, and building relationships. While network traffic and the number of users are rapidly growing, the mean-time between failures (MTTF) is surprisingly short; according to recent studies, in the majority of Internet backbone paths, the MTTF is 28 days. This leads to a strong requirement for highly dependable networks, servers, and software systems. The challenge is to build interconnected systems, based on available technology, that are inexpensive, accessible, scalable, and dependable. This special section provides insights into a number of these exciting challenges.

Implementing efficient communication and I/O mechanisms in Java requires both fast access to low-level system resources (such as network and raw disk interfaces) and direct manipulation of memory regions external to the Java heap (such as communication and I/O buffers). Java native methods are too expensive to perform these operations and raise serious protection concerns. We present Jaguar, a new mechanism that provides Java applications with efficient access to system resources while retaining the protection of the Java environment. This is accomplished through compile-time translation of certain Java bytecodes to inlined machine code segments. We demonstrate the use of Jaguar through a Java interface to the VIA fast communications layer, which achieves nearly identical performance to that of C, and Pre-Serialized Objects, a mechanism which greatly reduces the cost of Java object serialization. Copyright © 2000 John Wiley & Sons, Ltd.

Virtual networks provide applications with the illusion of having their own dedicated, high-performance networks, although network interfaces posses limited, shared resources. We present the design of a large-scale virtual network system and examine the integration of communication programming interface, system resource management, and network interface operation. Our implementation on a cluster of 100 workstations quantifies the impact of virtualization on small message latencies and throughputs, shows full hardware performance is delivered to dedicated applications and time-shared workloads, and shows robust performance under demanding workloads that overcommit interface resources.

We present a study of the architectural requirements and scalability of the NAS Parallel Benchmarks.Through direct measurements and simulations, we identify the factors which affect the scalability of benchmark codes on two relevant and distinct platforms; a cluster of workstations and a ccNUMA SGI Origin 2000.We find that the benefit of increased global cache size is pronounced in certain applications and often offsets the communication cost.By constructing the working set profile of the benchmarks, we are able to visualize the improvement of computational efficiency under constant-problem-size scaling.We also find that, while the Origin MPI has better point-to-point performance, the cluster MPI layer is more scalable with communication load.However, communication performance within the applications is often much lower than what would be achieved by microbenchmarks.We show that the communication protocols used by MPI runtime library are influential to the communication performance in applications, and that the benchmark codes have a wide spectrum of communication requirements.

This paper examines NFS sensitivity to performance characteristics of emerging networks.We adopt an unusual method of inserting controlled delays into live systems to measure sensitivity to basic network parameters.We develop a simple queuing model of an NFS server and show that it reasonably characterizes our two live systems running the SPECsfs benchmark.Using the techniques in this work, we can infer the structure of servers from published SPEC results.Our results show that NFS servers are most sensitive to processor overhead; it can be the limiting factor with even a modest number of disks.Continued reductions in processor overhead will be necessary to realize performance gains from future multigigabit networks.NFS can tolerate network latency in the regime of newer LANs and IP switches.Due to NFS's historic high mix of small metadata operations, NFS is quite insensitive to network bandwidth.Finally, we find that the protocol enhancements in NFS version 3 tolerate high latencies better than version 2 of the protocol.

We investigate resource usage while performing streaming I/O by contrasting three architectures, a single workstation, a cluster, and an SMP, under various I/O benchmarks. We derive analytical and empirically-based models of resource usage during data transfer, examining the I/O bus, memory bus, network, and processor of each system. By investigating each resource in detail, we assess what comprises a well-balanced system for these workloads. We find that the architectures we study are not well balanced for streaming I/O applications. Across the platforms, the main limitation to attaining peak performance is the CPU, due to lack of data locality. Increasing processor performance (especially with improved block operation performance) will be of great aid for these workloads in the future. For a cluster workstation, the I/O bus is a major system bottleneck, because of the increased load placed on it from network communication. A well-balanced cluster workstation should have copious I/O bus bandwidth, perhaps via multiple I/O busses. The SMP suffers from poor memory-system performance; even when there is true parallelism in the benchmark, contention in the shared-memory system leads to reduced performance. As a result, the clustered workstations provide higher absolute performance for streaming I/O workloads.

Demonstrates the power of providing a common set of operating system services to wide-area applications, including mechanisms for naming, persistent storage, remote process execution, resource management, authentication and security. On a single machine, application developers can rely on the local operating system to provide these abstractions. In the wide area, however, application developers are forced to build these abstractions themselves or to do without. This ad-hoc approach often results in individual programmers implementing non-optimal solutions, wasting both programmer effort and system resources. To address these problems, we are building a system, WebOS, that provides the basic operating systems services needed to build applications that are geographically distributed, highly available, incrementally scalable and dynamically reconfigurable. Experience with a number of applications developed under WebOS indicates that it simplifies system development and improves resource utilization. In particular, we use WebOS to implement Rent-A-Server to provide dynamic replication of overloaded Web services across the wide area in response to client demands.

No abstract available.

Rapid developments in networking technology and a rise in clustered computing have driven research studies in high performance communication architectures. In an effort to standardize the work in this area, industry leaders have developed the Virtual Interface Architecture (VIA) specification. This architecture seeks to provide an operating system-independent infrastructure for high-performance user-level networking in a generic environment. This paper evaluates the inherent costs and performance potential of the Virtual Interface Architecture through a prototype implementation over Myrinet. The VIA prototype is compared against established research user-level networks using simple communication benchmarks on the same hardware. We consider extensions to the VI Architecture that improve its performance for certain types of communication traffic and outline further research areas in the VIA design space that merit investigation.

Implicit coscheduling is a distributed algorithm for time-sharing communicating processes in a cluster of workstations. By observing and reacting to implicit information, local schedulers in the system make independent decisions that dynamically coordinate the scheduling of communicating processes. The principal mechanism involved is two-phase spin-blocking: a process waiting for a message response spins for some amount of time, and then relinquishes the processor if the response does not arrive.In this paper, we describe our experience implementing implicit coscheduling on a cluster of 16 UltraSPARC I workstations; this has led to contributions in three main areas. First, we more rigorously analyze the two-phase spin-block algorithm and show that spin time should be increased when a process is receiving messages. Second, we present performance measurements for a wide range of synthetic benchmarks and for seven Split-C parallel applications. Finally, we show how implicit coscheduling behaves under different job layouts and scaling, and discuss preliminary results for achieving fairness.

In this paper, we study how to minimize the latency of a message through a network that consists of a number of store-and-forward stages. This research is especially relevant for today's low overhead communication systems that employ dedicated processing elements for protocol processing. We develop an abstract pipeline model that reveals a crucial performance tradeoff involving the effects of the overhead of the bottleneck stage and the bandwidth of the remaining stages. We exploit this tradeoff to develop a suite of fragmentation algorithms designed to minimize message latency. We also provide an experimental methodology that enables the construction of customized pipeline algorithms that can adapt to the specific system characteristics and application workloads. By applying this methodology to the Myrinet-GAM system, we have improved its latency by up to 51%. Our theoretical framework is also applicable to pipelined systems beyond the context of high speed networks.

No abstract available.

This work provides a systematic study of the impact of communication performance on parallel applications in a high performance network of workstations. We develop an experimental system in which the communication latency, overhead, and bandwidth can be independently varied to observe the effects on a wide range of applications. Our results indicate that current efforts to improve cluster communication performance to that of tightly integrated parallel machines results in significantly improved application performance. We show that applications demonstrate strong sensitivity to overhead, slowing down by a factor of 60 on 32 processors when overhead is increased from 3 to 103 µs. Applications in this study are also sensitive to per-message bandwidth, but are surprisingly tolerant of increased latency and lower per-byte bandwidth. Finally, most applications demonstrate a highly linear dependence to both overhead and per-message bandwidth, indicating that further improvements in communication performance will continue to improve application performance.

Clusters of multiprocessors, or Clumps, promise to be the supercomputers of the future, but obtaining high performance on these architectures requires an understanding of interactions between the multiple levels of interconnection. In this paper, we present the first multi-protocol implementation of a lightweight message layer---a version of Active Messages-II running on a cluster of Sun Enterprise 5000 servers connected with Myrinet. This research brings together several pieces of high-performance interconnection technology: bus backplanes for symmetric multiprocessors, low-latency networks for connections between machines, and simple, user-level primitives for communication. The paper describes the shared memory message-passing protocol and analyzes the multi-protocol implementation with both microbenchmarks and Split-C applications. Three aspects of the communication layer are critical to performance: the overhead of cache-coherence mechanisms, the method of managing concurrent access, and the cost of accessing state with the slower protocol. Through the use of an adaptive polling strategy, the multi-protocol implementation limits performance interactions between the protocols, delivering up to 160 MB/s of bandwidth with 3.6 microsecond end-to-end latency. Applications within an SMP benefit from this fast communication, running up to 75% faster than on a network of uniprocessor workstations. Applications running on the entire Clump are limited by the balance of NIC's to processors in our system, and are typically slower than on the NOW. These results illustrate several potential pitfalls for the Clumps architecture.

We report the performance of NOW-Sort, a collection of sorting implementations on a Network of Workstations (NOW). We find that parallel sorting on a NOW is competitive to sorting on the large-scale SMPs that have traditionally held the performance records. On a 64-node cluster, we sort 6.0 GB in just under one minute, while a 32-node cluster finishes the Datamation benchmark in 2.41 seconds.

Large-scale parallel machines are incorporating increasingly sophisticated architectural support for user-level messaging and global memory access. We provide a systematic evaluation of a broad spectrum of current design alternatives based on our implementations of a global address language on the Thinking Machines CM-5, Intel Paragon, Meiko CS-2, Cray T3D, and Berkeley NOW. This evaluation includes a range of compilation strategies that make varying use of the network processor; each is optimized for the target architecture and the particular strategy. We analyze a family of interacting issues that determine the performance trade-offs in each implementation, quantify the resulting latency, overhead, and bandwidth of the global access operations, and demonstrate the effects on application performance.

We present a distributed algorithm for time-sharing parallel workloads that is competitive with coscheduling. Implicit scheduling allows each local scheduler in the system to make independent decisions that dynamically coordinate the scheduling of cooperating processes across processors. Of particular importance is the blocking algorithm which decides the action of a process waiting for a communication or synchronization event to complete. Through simulation of bulk-synchronous parallel applications, we find that a simple two-phase fixed-spin blocking algorithm performs well; a two-phase adaptive algorithm that gathers run-time data on barrier wait-times performs slightly better. Our results hold for a range of machine parameters and parallel program characteristics. These findings are in direct contrast to the literature that states explicit coscheduling is necessary for fine-grained programs. We show that the choice of the local scheduler is crucial, with a priority-based scheduler performing two to three times better than a round-robin scheduler. Overall, we find that the performance of implicit scheduling is near that of coscheduling (+/- 35%), without the requirement of explicit, global coordination.

In this paper, we analyze four parallel sorting algorithms (bitonic, column, radix, and sample sort) with the LogP model. LogP characterizes the performance of modern parallel machines with a small set of parameters: the communication latency (L), overhead (o), bandwidth (g), and the number of processors (P). We develop implementations of these algorithms in Split-C, a parallel extension to C, and compare the performance predicted by LogP to actual performance on a CM-5 of 32 to 512 processors for a range of problem sizes. We evaluate the robustness of the algorithms by varying the distribution and ordering of the key values. We also briefly examine the sensitivity of the algorithms to the communication parameters. We show that the LogP model is a valuable guide in the development of parallel algorithms and a good predictor of implementation performance. The model encourages the use of data layouts which minimize communication and balanced communication schedules which avoid contention. With an empirical model of local processor performance, LogP predictions closely match observed execution times on uniformly distributed keys across a broad range of problem and machine sizes. We find that communication performance is oblivious to the distribution of the key values, whereas the local processor performance is not; some communication phases are sensitive to the ordering of keys due to contention. Finally, our analysis shows that overhead is the most critical communication parameter in the sorting algorithms.

Most recent MPP systems employ a fast microprocessor surrounded by a shell of communication and synchronization logic. The CRAY-T3D provides an elaborate shell to support global-memory access, prefetch, atomic operations, barriers, and block transfers. We provide a detailed empirical performance characterization of these primitives using micro-benchmarks and evaluate their utility in compiling for a parallel language. We have found that the raw performance of the machine is quite impressive and the most effective forms of communication are prefetch and write. Other shell provisions, such as the bulk transfer engine and the external Annex register set, are cumbersome and of little use. By evaluating the system in the context of a language implementation, we shed light on important trade-offs and pitfalls in the machine architecture.

No abstract available.

In this paper we present substantially improved thread partitioning algorithms for modern implicitly parallel languages. We present a new block partitioning algorithm, separation constraint partitioning, which is both more powerful and more flexible than previous algorithms. Our algorithm is guaranteed to derive maximal threads. We present a theoretical framework for proving the correctness of our partitioning approach, and we show how separation constraint partitioning makes interprocedural partitioning viable.

: We present and analyze a portable, high-performance algorithm for finding connected components on modern distributed memory multiprocessors. The algorithm is a hybrid of the classic DFS on the subgraph local to each processor and a variant of the Shiloach-Vishkin PRAM algorithm on the global collection of subgraphs. We implement the algorithm in Split-C and measure performance on the the Cray T3D, the Meiko CS-2, and the Thinking Machines CM-5 using a class of graphs derived from cluster dynamics methods in computational physics. On a 256 processor Cray T3D, the implementation outperforms all previous solutions by an order of magnitude. A characterization of graph parameters allows us to select graphs that highlight key performance features. We study the effects of these parameters and machine characteristics on the balance of time between the local and global phases of the algorithm and find that edge density, surface-to-volume ratio, and relative communication cost dominate perform...

This paper uses an abstract machine approach to compare the mechanisms of two parallel machines: the J-Machine and the CM-5. High-level parallel programs are translated by a single optimizing compiler to a fine-grained abstract parallel machine, TAM. A final compilation step is unique to each machine and optimizes for specifics of the architecture. By determining the cost of the primitives and weighting them by their dynamic frequency in parallel programs, we quantify the effectiveness of the following mechanisms individually and in combination. Efficient processor/network coupling proves valuable. Message dispatch is found to be less valuable without atomic operations that allow the scheduling levels to cooperate. Multiple hardware contexts are of small value when the contexts cooperate and the compiler can partition the register set. Tagged memory provides little gain. Finally, the performance of the overall system is strongly influenced by the performance of the memory system and the frequency of control operations.

A vast body of theoretical research has focused either on overly simplistic models of parallel computation, notably the PRAM, or overly specific models that have few representatives in the real world. Both kinds of models encourage exploitation of formal loopholes, rather than rewarding development of techniques that yield performance across a range of current and future parallel machines. This paper offers a new parallel machine model, called LogP, that reflects the critical technology trends underlying parallel computers. it is intended to serve as a basis for developing fast, portable parallel algorithms and to offer guidelines to machine designers. Such a model must strike a balance between detail and simplicity in order to reveal important bottlenecks without making analysis of interesting problems intractable. The model is based on four parameters that specify abstractly the computing bandwidth, the communication bandwidth, the communication delay, and the efficiency of coupling communication and computation. Portable parallel algorithms typically adapt to the machine configuration, in terms of these parameters. The utility of the model is demonstrated through examples that are implemented on the CM-5.

No abstract available.

For MPP's to solve new and interesting problems, they must support ihe development of sophisticated algorithms on very large data sets.Successful development depends strongly on the speed of the execute-fix cycle.Sequential machines cannot provide suflciently fast execution of large problems, but many programming systems available on MPP's ;!s date appear, and w+iceis given that copying is by permission of the Asmciation for Compuing Macbkuxy.To copy &envise, or to repubhsb, quires a fee sndor specific prmiskm.

We examine multithreading to improve uniprocessor cost/performance on multiple processes. Processor utilization and cache behavior are studied analytically and under simulation by interleaving reference traces to model timesharing and multithreading. Multithreading a small number of threads is superior with large on-chip caches and significant memory latency. The switch need not be extremely fast. Surprisingly, miss ratios under multithreading may be lower than under timesharing, because switch-on-miss multithreading favors processes with better cache behavior.

The design challenge for large-scale multiprocessors is (1) to minimize communication overhead, (2) allow communication to overlap computation, and (3) coordinate the two without sacrificing processor cost/performance. We show that existing message passing multiprocessors have unnecessarily high communication costs. Research prototypes of message driven machines demonstrate low communication overhead, but poor processor cost/performance. We introduce a simple communication mechanism, Active Messages, show that it is intrinsic to both architectures, allows cost effective use of the hardware, and offers tremendous flexibility. Implementations on nCUBE/2 and CM-5 are described and evaluated using a split-phase shared-memory extension to C, Split-C. We further show that active messages are sufficient to implement the dynamically scheduled languages for which message driven machines were designed. With this mechanism, latency tolerance becomes a programming/compiling concern. Hardware support for active messages is desirable and we outline a range of enhancements to mainstream processors.

article Free Access Share on Fine-grain parallelism with minimal hardware support: a compiler-controlled threaded abstract machine Authors: David E. Culler View Profile , Anurag Sah View Profile , Klaus E. Schauser View Profile , Thorsten von Eicken View Profile , John Wawrzynek View Profile Authors Info & Claims ACM SIGOPS Operating Systems ReviewVolume 25Issue Special IssueApr. 1991pp 164–175https://doi.org/10.1145/106974.106990Published:01 April 1991Publication History 229citation1,379DownloadsMetricsTotal Citations229Total Downloads1,379Last 12 Months108Last 6 weeks19 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Dataflow architectures tolerate long unpredictable communication delays and support generation and coordination of parallel activities directly in hardware, rather than assuming that program mapping will cause these issues to disappear. However, the proposed mechanisms are complex and introduce new mapping complications. This paper presents a greatly simplified approach to dataflow execution, called the explicit token store (ETS) architecture, and its current realization in Monsoon. The essence of dynamic dataflow execution is captured by a simple transition on state bits associated with storage local to a processor. Low-level storage management is performed by the compiler in assigning nodes to slots in an activation frame, rather than dynamically in hardware. The processor is simple, highly pipelined, and quite general. It may be viewed as a generalization of a fairly primitive von Neumann architecture. Although the addressing capability is restrictive, there is exactly one instruction executed for each action on the dataflow graph. Thus, the machine oriented ETS model provides new understanding of the merits and the real cost of direct execution of dataflow graphs.

Multithreading has been proposed as an architectural strategy for tolerating latency in multiprocessors and, through limited empirical studies, shown to offer promise.This paper develops an analytical model of multithreaded processor behavior based on a small set of architectural and program parameters.The model gives rise to a large Markov chain, which is solved to obtain a formula for processor efficiency in terms of the number of threads per processor, the remote reference rate, the latency, and the cost of switching between threads.It is shown that a multithreaded processor exhibits three operating regimes: linear (efficiency is proportional to the number of threads), transition, and saturation (efficiency depends only on the remote reference rate and switch cost).Formulae for regime boundaries are derived.The model is embellished to reflect cache degradation due to multithreading, using an analytical model of cache behavior, demonstrating that retums diminish as the number threads becomes large.predictions from the embellished model correlate well with published empirical measurements.prescriptive use of the model under various scenarios indicates that multithreading is effective, but the Ilumber of useful threads per processor is fairly small.

Parallel execution of programs requires more resources and more complex resource management than sequential execution. If concurrent tasks can be spawned dynamically, programs may require an inordinate amount of resources when the potential parallelism in the program is much greater than the amount of parallelism the machine can utilize. Loop bounding, a technique for dynamically controlling the amount of parallelism exposed in dataflow programs, is described. The effectiveness of the technique in reducing token storage requirements is supported by experimental data in the form of parallelism profiles and waiting-token profiles. Comparisons are made throughout with more conventional approaches to parallel computing. It is shown that limiting the maximum number of coherent iterations of loops is effective in reducing the resource requirements of typical scientific programs without sacrificing performance. The implementation of this idea is based on compiling loops into dataflow graphs with a loop-bounding parameter than can be set at run time according to some policy.>

A method for assessing the benefits of fine-grain parallelism in actual programs is presented. The method is based on parallelism profiles and speedup curves derived by executing dataflow graphs on an interpreter under progressively more realistic assumptions about processor resources and communication costs. It is shown that programs, even using traditional algorithms, exhibit ample parallelism when parallelism is exposed at all levels. Since only dataflow graphs compiled from the high-level language Id are considered, the bias introduced by the language and the compiler is examined. A method of estimating speedup through analysis of the ideal parallelism profile is developed, avoiding repeated execution of programs. It is shown that the fine-grain parallelism can be used to mask large, unpredictable memory latency and synchronization waits in architectures using dataflow instruction execution mechanisms. The effects of grouping portions of dataflow programs, such as function invocations or loop iterations, and requiring that the operators in a group execute on a single processor, are explored.>