The efficiency of the time synchronization service in wireless sensor networks is tightly connected to the design of the radio, the quality of the clocking hardware, and the synchronization algorithm employed. While improvements can be made on all levels of the system, over the last few years most work has focused on the algorithmic level to minimize message exchange and in radio architectures to provide accurate time-stamping mechanisms. Surprisingly, the influences of the underlying clock system and its impact on the overall synchronization accuracy has largely been unstudied. In this work, we investigate the impact of the clocking subsystem on the time synchronization service and address, in particular, the influence of changes in environmental temperature on clock drift in highly duty-cycled wireless sensor nodes. We also develop formulas that help the system architect choose the optimal resynchronization period to achieve a given synchronization accuracy. We find that the synchronization accuracy has a two region behavior. In the first region, the synchronization accuracy is limited by quantization error, while int he second region changes in environmental temperature impact the achievable accuracy. We verify our analytic results in simulation and real hardware experiments.

The search for homologous RNA molecules---sequences of RNA that might behave simiarly due to similarity in their physical (secondary) structure---is currently a computationally intensive task. Moreover, RNA sequences are populating genome databases at a pace unmatched by gains in standard processor performance. While software tools such as Infernal can efficiently find homologies among RNA families and genome databases of modest size, the continuous advent of new RNA families and the explosive growth in volume of RNA sequences necessitate a faster approach. This work introduces two different architectures for accelerating the task of finding homologous RNA molecules in a genome database. The first architecture takes advantage of the tree-like configuration of the covariance models used to represent the consensus secondary structure of an RNA family and converts it directly into a highly-pipelined processing engine. Results for this architecture show a 24× speedup over Infernal when processing a small RNA model. It is estimated that the architecture could potentially offer several thousands of times speedup over Infernal on larger models, provided that there are sufficient hardware resources available. The second architecture is introduced to address the steep resource requirements of the first architecture. It utilizes a uniform array of processing elements and schedules all of the computations required to scan for an RNA homolog onto those processing elements. The estimated speedup for this architecture over the Infernal software package ranges from just under 20× to over 2,350×.

Time keeping and synchronization are important services for networked and embedded systems. High quality timing information allows embedded network nodes to provide accurate time-stamping, fast localization, efficient duty cycling schedules, and other basic but essential functions - all of which are required for low power operation.

This poster introduces an application-specific trace log compression mechanism targeted for execution on wireless sensor network nodes. Trace logs capture sequences of significant events executed on a node to provide visibility into the system. The application-specific compression mechanism exploits static program control flow knowledge to automate insertion of trace statements that capture trace data in a concise form. Initial evaluation reveals that these compressed trace logs, when generated, consume just over a fifth of the space required by standard trace logging techniques.

Time synchronization is an essential service in distributed computing and control systems. It is used to enable tasks such as synchronized data sampling and accurate time-of-flight estimation, which can be used to locate nodes. The deviation in nodes' knowledge of time and inter-node resynchronization rate are affected by three sources of time stamping errors: network wireless communication delays, platform hardware and software delays, and environment-dependent frequency drift characteristics of the clock source. The focus of this work is on the last source of error, the clock source, which becomes a bottleneck when either required time accuracy or available energy budget and bandwidth (and thus feasible resynchronization rate) are too stringent. Traditionally, this has required the use of expensive clock sources (such as temperature compensation using precise sensors and calibration models) that are not cost-effective in low-end wireless sensor nodes. Since the frequency of a crystal is a product of manufacturing and environmental parameters, we describe an approach that exploits the subtle manufacturing variation between a pair of inexpensive oscillators placed in close proximity to algorithmically compensate for the drift produced by the environment. The algorithm effectively uses the oscillators themselves as a sensor that can detect changes in frequency caused by a variety of environmental factors. We analyze the performance of our approach using behavioral models of crystal oscillators in our algorithm simulation. Then we apply the algorithm to an actual temperature dataset collected at the James Wildlife Reserve in Riverside County, California, and test the algorithms on a waveform generator based testbed. The result of our experiments show that the technique can effectively improve the frequency stability of an inexpensive uncompensated crystal 5 times with the potential for even higher gains in future implementations.

Most network routers and switches provide some protection against the network attacks. However, the rapidly increasing amount of damages reported over the past few years indicates the urgent need for tougher security. Deep-packet inspection is one of the solutions to capture packets that can not be identified using the traditional methods. It uses a list of signatures to scan the entire content of the packet, providing the means to filter harmful packets out of the network. Since one signature does not depend on the other, the filtering process has a high degree of parallelism. Most software and hardware deep-packet filters that are in use today execute the tasks under Von Neuman architecture. Such architecture can not fully take advantage of the parallelism. For instance, one of the most widely used network intrusion-detection systems, Snort, configured with 845 patterns, running on a dual 1-GHz Pentium III system, can sustain a throughput of only 50 Mbps. The poor performance is because of the fact that the processor is programmed to execute several tasks sequentially instead of simultaneously. We designed scalable deep-packet filters on field-programmable gate arrays (FPGAs) to search for all data-independent patterns simultaneously. With FPGAs, we have the ability to reprogram the filter when there are any changes to the signature set. The smallest full-pattern matcher implementation for the latest Snort NIDS fits in a single 400k Xilinx FPGA (Spartan 3-XC3S400) with a sustained throughput of 1.6 Gbps. Given a larger FPGA, the design can scale linearly to support a greater number of patterns, as well as higher data throughput.

This article presents a dense logic design for matching multiple regular expressions with a field programmable gate array (FPGA) at 10+ Gbps. It leverages on the design techniques that enforce the shortest critical path on most FPGA architectures while optimizing the circuit size. The architecture is capable of supporting a maximum throughput of 12.90 Gbps on a Xilinx Virtex 4 LX200 and its performance is linearly scalable with size. Additionally, this article presents techniques for parsing data streams to provide semantic information for patterns found within a data stream. We illustrate how a content-based router can be implemented with our parsing techniques using an XML parser as an example. The content-based router presented was designed, implemented, and tested in a Xilinx Virtex XCV2000E FPGA on the FPX platform. It is capable of processing 32-bits of data per clock cycle and runs at 100 MHz. This allows the system to process and route XML messages at 3.2 Gbps.

A growing number of embedded computing systems are used outside of environmentally controlled locations. In locations such as remote parts of deserts, deep ocean floors, and outer space, it is not only difficult to predict environmental effects on a system, they also allow very limited accessibility once a system is deployed. Therefore, it is often necessary for system parameters to be over provisioned to guarantee correct functionality under worst case environmental conditions. This often leads to an end system that is suboptimal for typical conditions.

A biological organism's ability to sense and adapt to its environment is essential to its survival. Likewise, environmentally aware computing systems avail themselves to a longer operational life and a wider range of applications than traditional systems. In this paper, we propose a novel circuit design methodology that allows parameterizable hardware to self-regulate its temperature. We apply this methodology to an image recognition system on an Xilinx Virtex 4 FX100 field programmable gate array (FPGA). The image recognition system sustains a safe operational temperature by automatically adjusting its frequency and output quality. The circuit sacrifices output performance and quality to lower its internal temperature as the ambient temperature increases, and can leverage cooler temperatures by increasing output performance and quality. Furthermore, the circuit will shutdown if the ambient temperature becomes too hot for the device to function properly. A performance evaluation of our adaptive circuit under various thermal conditions shows up to a 4× factor increase in performance and a 2× factor increase in quality over a system without dynamic thermal control.

Currently available genome databases are growing exponentially in size, making it difficult for software analysis tools to keep up. A number of hardware accelerators utilizing special purpose VLSI (Blas, et al., 2005) or reconfigurable hardware (Hoang, 1993) have been proposed. However, they are inflexible; support for new applications usually requires a laborious redesign. None of these accelerators can be easily adapted to other applications that require differing hardware resources. The design philosophy of the softcore vector processor is based on two important goals: adaptability and performance. Instruction based execution allows programmable support for a large number of algorithms. The fact that different classes of applications require different subsets of hardware resources, argues for a customizable hardware design built from primitives. The second goal was to achieve programmability without sacrificing performance. The SVP was designed to perform competitively with full custom solutions available in the market

In this paper, the authors present a reconfigurable hardware architecture for searching for regular expression patterns in streaming data. This new architecture is created by combining two popular pattern matching techniques: a pipelined character grid architecture (Baker, 2004), and a regular expression NFA architecture (Cho, 2006). The resulting hybrid architecture can scale the number of input characters while still maintaining the ability to scan for regular expression patterns

Non-hierarchical k-means algorithms have been implemented in hardware, most frequently for image clustering. Here, we focus on hierarchical clustering of text documents based on document similarity. To our knowledge, this is the first work to present a hierarchical clustering algorithm designed for hardware implementation and ours is the first hardware-accelerated implementation

We present a high performance reconfigurable hardware architecture for detecting patterns as well as their contextual meaning. By analyzing for both semantic content and structure, the accuracy of content-level processing systems can be improved. Our system is built using semantics defined by context-free-grammar (CFG) to tag the streaming data. Unlike the traditional table look up and stack based engines used in CFG parsers, we explore a new method that maps the grammar structure on to the Field Programmable Gate Arrays (FPGA) hardware. The structure is a direct translation of the grammar which enables the meaning of the patterns to be determined based on the location of its detection. The parallel pattern detection engines are instantiated using FPGA resources. Our implementation scans for the regular expression patterns and determines their semantics as defined by a grammar. This highly parallel and fine grained pipelined engine with 8 bit input bus can operate in bandwidth above 2 Gbps. For a simple XML grammar example, our engine can detect and tag the patterns at 1.57 Gbps on Xilinx VirtexE FPGA and 4.26 Gbps on the new Virtex 4 devices.

High-performance document clustering systems enable similar documents to be automatically organized into groups. In the past, the large amount of computational time needed to cluster documents prevented practical use of such systems with a large number of documents. A full hardware implementation of the K-means clustering algorithm has been designed and implemented in reconfigurable hardware that clusters 512k documents rapidly. This implementation, uses four parallel cosine distance metrics to cluster document vectors that each have 4000 dimensions. The synthesized hardware runs on the field programmable port extender (FPX) platform at a clock rate of 80 MHz. Although the clock rate on the Xilinx VirtexE 2000 is slower than a CPU, the implementation runs 26 times faster than an algorithmically equivalent software algorithm running on an Intel 3.60 GHz Xeon. The same architecture was used to synthesize a faster and larger design for the Xilinx Virtex4 LX200. This larger implementation can contain up to 25 parallel cosine distance metrics. The implementation synthesized with a clock rate of 250 MHz and outperforms the equivalent software by a factor of 328

Given large circuit sizes, high clock frequencies, and possibly extreme operating environments, Field Programmable Gate Arrays (FPGAs) are capable of heating beyond their designed thermal limits. As new circuits are developed for FPGAs and deployed remotely, engineers are challenged to determine in advance if the device will operate within recommended thermal ranges. The amount of power consumed by the circuit depends on how an algorithm is compiled into hardware, how the circuit is placed and routed, and the patterns of data that pass through the system. The amount of heat that can be dissipated depends on the thermal transfer characteristics of the package, the air flow that passes over the package, and the ambient temperature of the remote systems. Rather than designing a system to handle unreasonable worst-case situations, we have implemented a thermal management system that continuously monitors the temperature of the FPGA and reprograms the device if the temperate approaches the outer limits of safe operating conditions. Our system measures the junction temperature of a Xilinx Virtex FPGA using a built-in thermal diode. Using the temperature monitoring mechanism, we have studied the steady-state and transient conditions of multiple benchmark circuits implemented in an FPGA logic on the Field-programmable Port Extender (FPX) development platform. We observed properties of these benchmark circuits that enable us to predict power and thermal characteristics for real applications. We propose a Dynamic Thermal Management (DTM) strategy for FPGAs based on temperature feedback.

This paper presents an implementation of a high-performance network application layer parser in FPGAs. At the core of the architecture resides a pattern matcher and a parser. The pattern matcher scans for patterns in high-speed streaming TCP data streams. The parser core augments each pattern found with semantic information determined from the patterns location within the data stream. The packet payload parser can provide a higher level of understanding of a data stream for many network applications. Such applications include high performance XML parsers, content-based/aware routers, and others. Additionally, a TCP processor allows stateful packet payload parsing of up to 8 million simultaneous TCP flows. The payload parser has been implemented in a Xilinx Virtex E 2000 FPGA on the Field-Programmable Port Extender platform. The parsing module runs at 200 MHz and parse raw data at 6.4 Gbps. The payload parser, integrated with the TCP processor, runs at 100 MHz for a throughput of 3.2 Gbps

Reconfigurable circuits running in field programmable gate arrays (FPGAs) can be dynamically optimized for power based on computational requirements and thermal conditions of the environment. In the past, FPGA circuits were typically small and operated at a low frequency. Few users were concerned about high-power consumption and the heat generated by FPGA devices. The current generation of FPGAs, however, use extensive pipelining techniques to achieve high data processing rates and dense layouts that can generate significant amounts of heat. FPGA circuits can be synthesized that can generate more heat than the package can dissipate. For FPGAs that operate in controlled environments, heatsinks and fans can be mounted to the device to extract heat from the device. When FPGA devices do not operate in a controlled environment, however, changes to ambient temperature due to factors such as the failure of a fan or a reconfiguration of bitfile running on the device can drastically change the operating conditions. A protection mechanism is needed to ensure the proper operation of the FPGA circuits when such a change occurs. To address these issues, we have devised a reconfigurable temperature monitoring system that gives feedback to the FPGA circuit using the measured junction temperature of the device. Using this feedback, we designed a novel dual frequency switching system that allows the FPGA circuits to maintain the highest level of performance for a given maximum junction temperature. Our working system has been implemented and deployed on the field programmable port extender (FPX) platform at Washington University in St. Louis. Our experimental results with a scalable image correlation circuit show up to a 2.4times factor increase in performance as compared to a system without thermal feedback. Our circuit ensures that the device performs the maximum required computation while always operating within a safe temperature range

This paper presents an architecture for context-free grammar (CFG) based data processing hardware for re-configurable devices. Our system leverages on CFGs to tokenize and parse data streams into a sequence of words with corresponding semantics. Such a tokenizing and parsing engine is sufficient for processing grammatically correct input data. However, most pattern recognition applications must consider data sets that do not always conform to the predefined grammar. Therefore, we augment our system to detect and recover from grammatical errors while extracting useful information. Unlike the table look up method used in traditional CFG parsers, we map the structure of the grammar rules directly onto the field programmable gate array (FPGA). Since every part of the grammar is mapped onto independent logic, the resulting design is an efficient parallel data processing engine. To evaluate our design, we implement several XML parsers in an FPGA. Our XML parsers are able to process the full content of the packets up to 3.59 Gbps on Xilinx Virtex 4 devices

It has been estimated that computer network worms and virus caused the loss of over $55B in 2003. Network security system use techniques such as deep packet inspection to detect the harmful packets. While software intrusion detection system running on general purpose processors can be updated in response to new attacks. They lack the processing power to monitor gigabit networks. We present a high performance pattern matching co-processor architecture that can be used to monitor and identify a large number of intrusion signature. The design consists of a bank of pattern matchers that are used to implement a highly concurrent filter. The pattern matchers can be programmed to match multiple patterns of various lengths, and are able to leverage the existing databases of threat signatures. We have been able to program the filters to match all the payload patterns defined in the widely used Snort network intrusion detection system at a rate above 7 Gbps, with memory space left to accommodate threat signatures that become available in the future.

Due to increasing number of network worms and virus, many computer network users are vulnerable to attacks. Unless network security systems use more advanced methods of content filtering such as deep packet inspection, the problem get worse. However, searching for patterns at multiple offsets in entire content of network packet requires more processing power than most general purpose processor can provide. Thus, researchers have developed high performance parallel deep packet filters for reconfigurable devices. Although some reconfigurable systems can be generated automatically from pattern database, obtaining high performance result from each subsequent reconfiguration can be a time consuming process. We present a novel architecture for programmable parallel pattern matching coprocessor. By combining a scalable coprocessor with the compact reconfigurable filter, we produce a hybrid system that is able to update the rules immediate during the time the new filter is being compiled. We mapped our hybrid filter for the latest Snort rule set on January 13, 2005, containing 2,044 unique patterns byte make up 32,384 bytes, onto a single Xilinx Virtex 4LX-XC4VLX15 FPGA with a filtering rate of 2 Gbps.

Searching for multiple string patterns in a stream of data is a computationally expensive task. The speed of the search pattern module determines the overall performance of deep packet inspection firewalls, intrusion detection systems (IDS), and intrusion prevention systems (IPS). For example, one open source IDS configured for 845 patterns, can sustain a throughput of only 50 Mbps running on a dual 1-GHz Pentium III system. Using such systems would not be practical for filtering high speed networks with over 1 Gbps traffic. Some of these systems are implemented with field programmable gate arrays (FPGA) so that they are fast and programmable. However, such FPGA filters tend to be too large to be mapped on to a single FPGA. By sharing the common sublogic in the design, we can effectively shrink the footprint of the filter. Then, for a large subset of the patterns, the logic area can be further reduced by using a memory based architecture. These design methods allow our filter for 2064 attack patterns to map onto a single Xilinx Spartan 3-XC3S2000 FPGA with a filtering rate of over 3 Gbps of network traffic.