The advent of sensor networks presents untapped opportunities for synthesis. We examine the problem of synthesis of behavioral specifications into networks of programmable sensor blocks. The particular behavioral specification we consider is an intuitive user-created network diagram of sensor blocks, each block having a pre-defined combinational or sequential behavior. We synthesize this specification to a new network that utilizes a minimum number of programmable blocks in place of the predefined blocks, thus reducing network size and hence network cost and power. We focus on the main task of this synthesis problem, namely partitioning pre-defined blocks onto a minimum number of programmable blocks, introducing the efficient but effective PareDown decomposition algorithm for the task. We describe the synthesis and simulation tools we developed. We provide results showing excellent network size reductions through such synthesis and significant speedups of our algorithm over exhaustive search while obtaining near-optimal results for 15 real network designs as well as nearly 10000 randomly generated designs.

We describe the development of a set of embedded system building blocks, known as eBlocks. An eBlock network can be viewed as a basic form of sensor network that can be developed by non-programming engineers, scientists, and others. Each eBlock has a defined function, either one of a few predefined combinational or sequential functions, a custom-programmed function defined by an automated tool, or by user with programming skills. A user creates an application simply by connecting blocks, and possibly performing simple configuration via dials and switches. We have built over 100 physical eBlock prototypes, and tested their usability with over 100 non-programming users to date. We will describe the architecture of the blocks, including design tradeoffs we considered and the benefit of an exploration tool that we developed to help optimize the power and performance of the design. We have also built a graphical eBlock simulator that users can utilize to quickly build and test systems before deployment, and that we have used in experiments with over 300 non-programming users to help us define intuitive block functions and interfaces. We will describe the simulator architecture, as well as a tool that automatically converts a user's eBlock network into a much smaller network of programmable blocks with accompanying automatically generated programs.

Building a sensor-based system typically requires some programming and electronics expertise. However, some applications require only basic logic transformations and/or state maintenance of sensor information. This paper describes a set of electronic blocks, called eBlocks, that enable non-experts to build basic small-scale sensor-based systems. Each block performs a particular sensing, logic/state, or output function. A user builds a system by connecting blocks together. Each block contains a hidden microprocessor executing a pre-determined low-power compute and communication protocol. A difference between eBlocks and widely known sensor-network nodes is that each eBlock has a specific easy-to-understand function, and thus does not require programming. Further, eBlocks are designed to be connected in particular configurations to create an end application, while traditional nodes form a wireless network that must be programmed to form an application. Our physical prototypes can last for several years or more on a 9-volt battery, or can receive power from wall outlets. We describe the domain of applications for which eBlocks are suitable, including being used to build complete systems or to interface with existing sensor-network compute nodes, and we summarize the eBlock compute/communication protocol. We describe experiments, involving hundreds of users of varying levels of expertise, that demonstrate how systems that otherwise would have taken weeks or more to build can be built by non-experts in just a few minutes using eBlocks.

We introduce a novel memory architecture that can count the occurrences of patterns on a system's bus, a task known as profiling. Such profiling can serve a variety of purposes, like detecting a microprocessor's software hot spots or frequently used data values, which can be used to optimize various aspects of the system. The memory, which we call ProMem, is based on a pipelined binary search tree structure, yielding several beneficial features, including nonintrusiveness, accurate counts, excellent size and power efficiency, very fast access times, and the use of standard memories with only simple additional logic. The main limitation is that the set of potential patterns must be preloaded into the memory. We describe the ProMem architecture, and show excellent size and performance advantages compared with content-addressable memory (CAM) based designs.

Instruction caches have traditionally been used to improve software performance. Recently, several tiny instruction cache designs, including filter caches and dynamic loop caches, have been proposed to instead reduce software power. We propose several new tiny instruction cache designs, including preloaded loop caches, and one-level and two-level hybrid dynamic/preloaded loop caches. We evaluate the existing and proposed designs on embedded system software benchmarks from both the Powerstone and MediaBench suites, on two different processor architectures, for a variety of different technologies. We show on average that filter caching achieves the best instruction fetch energy reductions of 60--80%, but at the cost of about 20% performance degradation, which could also affect overall energy savings. We show that dynamic loop caching gives good instruction fetch energy savings of about 30%, but that if a designer is able to profile a program, preloaded loop caching can more than double the savings. We describe automated methods for quickly determining the best loop cache configuration, methods useful in a core-based design flow.

Profiling an application executing on a microprocessor is part of the solution to numerous software and hardware optimization and design automation problems. Most current profiling techniques suffer from runtime overhead, inaccuracy, or slowness, and the traditional non-intrusive method of using a logic analyzer doesn't work for today's system-on-a-chip having embedded cores. We introduce a novel on-chip memory architecture that overcomes these limitations. The architecture, which we call ProMem, is based on a pipelined binary tree structure. It achieves single-cycle throughput, so it can keep up with today's fastest pipelined processors. It can also be laid out efficiently and scales very well, becoming more efficient the larger it gets. The memory can be used in a wide-variety of common profiling situations, such as instruction profiling, value profiling, and network traffic profiling, which in turn can be used to guide numerous design automation tasks.

Embedded system programs tend to spend much time in small loops. Introducing a very small loop cache into the instruction memory hierarchy has thus been shown to substantially reduce instruction fetch energy. However, loop caches come in many sizes and variations -- using the configuration best on the average may actually result in worsened energy for a specific program. We therefore introduce a loop cache exploration tool that analyzes a particular program's profile, rapidly explores the possible configurations, and generates the configuration with the greatest power savings. We introduce a simulation-based approach and show the good energy savings that a customized loop cache yields. We also introduce a fast estimation-based approach that obtains nearly the same results in seconds rather than tens of minutes or hours.