Many telecommunications devices such as network switches contain content addressable memories (CAMs) for uses such as routing tables. CAMs, a class of associative memories, contain considerable logic for various forms of content matching and can be considered a class of reconfigurable logic engines. This paper demonstrates how a commercial ternary CAM and traditional RAM can be used with minimal additional logic to implement over 90% of the Snort 2.0 intrusion detection system (IDS) at line speeds of or exceeding 1 Gbs. In addition to simple matching techniques, sophisticated matching operations required by Snort can be implemented by levering an iterative approach that leverages a post processing action RAM. Additionally, a novel range encoding algorithm allows range matching required in the CAM for which other encodings either exceed the width provided by a CAM entry, or require excessive number of CAM entries to be scalable. The system was implemented for verification and performance evaluation in cycle accurate simulation using SystemC.

While RFID is starting to become a ubiquitious technology, the variation between different RFID systems still remains high. This paper presents several prototyping environments for different components of radio frequency identification (RFID) tags to demonstrate how many of these components can be standardized for many different purposes. We include two active tag prototypes, one based on a microprocessor and the second based on custom hardware. To program these devices we present a design automation flow that allows RFID transactions to be described in terms of primitives with behavior written in ANSI C code. To save power with active RFID devices we describe a passive transceiver switch called the “burst switch” and demonstrate how this can be used in a system with a microprocessor or custom hardware controller. Finally, we present a full RFID system prototyping environment based on real-time spectrum analysis technology currently deployed at the University of Pittsburgh RFID Center of Excellence. Using our prototyping techniques we show how transactions from multiple standards can be combined and targeted to several microprocessors include the Microchip PIC, Intel StrongARM and XScale, and AD Chips EISC as well as several hardware targets including the Altera Apex, Actel Fusion, Xilinx Coolrunner II, Spartan 3 and Virtex 2, and cell-based ASICs.

This paper presents a technique to visualize the communication pattern of a parallel application at different points during its execution. Unlike existing tools that show the communication pattern for the entire application, our tool breaks this communication pattern down into components to allow the more detailed study of application execution. These patterns are not merely snapshots or windows of the execution but rather are tied to specific code structures comprised of loops in the application. Our technique leverages our compiler, which adds instructions into the code to record where communications and code artifacts occur during execution. This information is stored into a trace format, which is read by our visualization tool. The visualization tool can graphically represent the communication pattern and message volume to allow a user to analyze and optimize the execution. As an example, we show how this information can be used to optimize the execution time and reduce the message delay of applications executed on a system enhanced with optical circuit switch interconnections.

This paper describes an ultra low power active RFID tag and its automated design flow. RFID primitives to be supported by the tag are enumerated with RFID macros and the behavior of each primitive is specified using ANSI-C within the template to automatically generate the tag controller. Two power saving components, a passive transceiver/burst switch and a smart buffer, are presented to save power and increase tag lifetime. Based on a test program, the processors required 183, 43, and 19 μ&J per transaction for StrongARM, XScale, and EISC processors, respectively. Three hardware controllers using a Fusion FPGA, Coolrunner II CPLD, and ASIC required 13 nJ, 1.3 nJ, and 0.07 nJ per transaction.

This paper describes LURU, a methodology for FPGA combinational technology mapping through the parallel search capability of Content-Addressable Memory (CAM). An overview is shown in Fig. 1. First, a circuit is partitioned into a set of subcircuits. Topologies of these subcircuits are described using textual string representations [(a) and (b) in Fig. 1]. A precomputed set of strings for the circuit topologies that can be contained in a LUT of K or fewer inputs [Fig. 1 (d)] can be matched against the circuit representation in parallel using the CAM shown in Fig. 1 (c). By using CAM, the search space is increased over traditional technology mapping algorithms. A final mapping is produced for an FPGA device consisting of a heterogeneous network of LUT's of K or fewer inputs, shown in Fig. 1 (e). Experimental results demonstrate that LURU can improve mapping quality by up to 49%, with an average of 21% improvement over traditional technology mapping techniques such as FlowMap and CutMap [9]. LURU exceeds the quality of such algorithms because LURU uses CAM to achieve a global search space. CAM's are capable of both exact and inexact matching. Using inexact matching, it is possible to match approximately 96% of subcircuits to a set of 16 basic CSE's [8].

Current radio frequency identification (RFID) systems generally have long design times and low tolerance to changes in specification. This paper describes a field programmable, low-power active RFID tag, and its associated specification and automated design flow. RFID primitives to be supported by the tag are enumerated with RFID macros, or assembly-like descriptions of the tag operations. From these, the RFID preprocessor generates templates automatically. The behavior of each RFID primitive is specified using ANSI C in the template. The resulting file is compiled by the RFID compiler. A smart buffer sits between the transceiver and the tag controller, to detect whether incoming packets are intended for the tag. By doing so, the main controller may remain powered down to reduce power consumption. Two system-on-a-chip implementation strategies are presented. First, a microprocessor based system for which a C program is automatically generated. The second includes a block of low-power FPGA logic. The user supplied RFID logic in ANSI-C is automatically converted into combinational VHDL by the RFID compiler. Based on a test program, the processors required 183, 43, and 19 muJ per transaction for StrongARM, XScale, and EISC processors, respectively. By replacing the processor with a Coolrunner II, the controller can be reduced to 1.11 nJ per transaction

Hardware acceleration using field programmable gate arrays (FPGAs) has become increasingly popular for computationally intensive digital signal processing (DSP) applications. Unfortunately, while FPGAs have a reasonably tractable computer aided design (CAD) flow and performance, they have poor power characteristics when compared to direct application specific integrated circuit (ASIC) fabrication. ASICs exhibit better performance and power than FPGAs, but require complex CAD and large non-recurring engineering (NRE) costs. A reconfigurable device that exhibits ASIC-like power characteristics and FPGA-like costs and tool support is desirable to fill this void. Several coarse-grained fabric architectures proposed during the last decade have been focused on performance and area-efficient architectural techniques. Even though power is becoming one of the critical design concerns for semiconductor industry, this issue has not been adequately addressed in the existing coarse-grained fabric architectures. In this paper, a low-power and high-performance hardware acceleration engine for DSP style applications is described. This reconfigurable fabric model is generic and parameterizable allowing design parameters to be adjusted within the architecture. The impact of varying different design parameters such as functional unit granularity, and multiplexer cardinality are studied for their implications on power and performance. The low-power fabric was designed to operate within the SuperCISC processor architecture designed at the University of Pittsburgh

This paper presents a parameterizable, coarse grained, reconfigurable fabric model that attempts to maintain field programmable gate array (FPGA)-like programmability and computer aided design (CAD), with application specific integrated circuit (ASIC)-like power characteristics for digital signal processing (DSP) style applications. Using this model, architectural design space decisions are explored in order to define an energy-efficient fabric. The impact on energy and performance due to the variation of different parameters such as data width and interconnection flexibility has been studied. The multiplexer cardinality usage has also been studied by mapping some of the signal processing applications onto the fabric. The results point to the use of power optimized 32-bit width computational elements interconnected by low cardinality multiplexers like 4:1 multiplexers.

This paper presents the design of a FPGA-based hardware co-processor, based on the SPHINX 3 speech recognition engine from CMU; capable of performing acoustic modeling (AM) for medium sized vocabularies in real-time. By creating an input-driven pipeline for performing the calculations, we were able to maximize the throughput of the system while simultaneously minimizing the number of pipeline stalls. Use advanced placement techniques enabled post place-and-route speeds even greater than those necessary for real-time operation while operating at maximum workload. Further, by using input control vectors all FSMs were removed from the design, greatly increasing the flexibility of the design. These results combined with the ability to reprogram the system for different recognition tasks serve to create a system capable of in a vast array of environments. Synthesis to both Xilinx Virtex 4 and Spartan 3 FPGAs helps to further characterize the flexibility of the architecture.

Content addressable memory (CAM) is a parallel search engine chip that has been proven to accelerate network appliance functions that are search-intensive by nature, such as routing table lookups. CAMs enable searching for a match of a single input with hundreds of thousands of entries in parallel in a single clock cycle. However, CAMs are inefficient in matching a numeric range with existing encoding methods. Two-hot, binary and Gray encodings exhibit a depth scalability problem where the CAM depth required increases with the maximum number M in the range. One-hot and Johnson encodings exhibit poor CAM width scalability O(M). We present a unique hybrid encoding scheme mixing the features of two-hot and Johnson codes to solve both scalability problems. For an arbitrary range, it uses only three CAM entries in depth regardless of M, and has a width scaling of O(/spl radic/M ). Therefore, this hybrid encoding scheme can be efficiently applied to CAM-based range matching with arbitrary ranges, while maintaining single cycle searching.

This paper presents an efficient hardware architecture for scheduling connections on a fat-tree interconnection network for parallel computing systems. Our technique utilizes global routing information to select upward routing paths so that most conflicts can be resolved. Thus, more connections can be successfully scheduled compared with a local scheduler. As a result of applying our technique to two-level, three-level and four-level fat-tree interconnection networks of various sizes in the range of 64 to 4096 nodes, we observe that the improvement of schedulability ratio averages 30% compared with greedy or random local scheduling. Our technique is also scalable and shows increased benefits for large system sizes.

The maximum matching algorithm for bipartite graphs can be used to provide optimal scheduling for crossbar based interconnection networks. Unfortunately, maximum matching requires O(N3) time for an N x N communication system, which has limited its application to real-time network scheduling. In this paper, we show how maximum matching can be reformulated in terms of Boolean operations rather than the more traditional formulations. By taking advantage of the inherent parallelism available in custom hardware design, we introduce three Maximum Matching implementations in hardware and show how we can trade design complexity for performance. Specifically, we examine a Pure Logic Scheduler with three dimensions of parallelism, a Matrix Scheduler with two dimensions of parallelism and a Vector Scheduler with one dimension of parallelism. These designs reduce the algorithmic time complexity down to O(1), O(K), and O(KN), respectively, where K is the number of optimization steps. While an optimal scheduling algorithm requires K = 2N -- 1 steps, our simulation results show that the scheduler can achieve 99% of the optimal schedule when K = 9. We examine hardware and time complexity of these architectures for crossbar sizes of up to N = 1024. Using FPGA synthesis results, we show that a greedy schedule for various sized crossbars, ranging from 8 x 8 to 256 x 256, can be optimized in less than 20 ns per optimization step. For crossbars reaching 1024 x 1024 the scheduling can be completed in approximately 10 μs with current technology and could reach under 90 ns with future technologies.

Multiprocessor Systems on Chips (MPSoCs) have become a popular architectural technique to increase performance. However, MPSoCs may lead to undesirable power consumption characteristics for computing systems that have strict power budgets, such as PDAs, mobile phones, and notebook computers. This paper presents the super-complex instruction-set computing (SuperCISC) Embedded Processor Architecture and, in particular, investigates performance and power consumption of this device compared to traditional processor architecture-based execution. SuperCISC is a heterogeneous, multicore processor architecture designed to exceed performance of traditional embedded processors while maintaining a reduced power budget compared to low-power embedded processors. At the heart of the SuperCISC processor is a multicore VLIW (Very Large Instruction Word) containing several homogeneous execution cores/functional units. In addition, complex and heterogeneous combinational hardware function cores are tightly integrated to the core VLIW engine providing an opportunity for improved performance and reduced energy consumption. Our SuperCISC processor core has been synthesized for both a 90-nm Stratix II Field Programmable Gate Aray (FPGA) and a 160-nm standard cell Application-Specific Integrated Circuit (ASIC) fabrication process from OKI, each operating at approximately 167 MHz for the VLIW core. We examine several reasons for speedup and power improvement through the SuperCISC architecture, includingpredicated control flow,cycle compression, and a reduction in arithmetic power consumption, which we callpower compression. Finally, testing our SuperCISC processor with multimedia and signal-processing benchmarks, we show how the SuperCISC processor can provide performance improvements ranging from 7X to 160X with an average of 60X, whilealsoproviding orders of magnitude of power improvements for the computational kernels. The power improvements for our benchmark kernels range from just over 40X to over 400X, with an average savings exceeding 130X. By combining these power and performance improvements, our total energy improvements all exceed 1000X. As these savings are limited to the computational kernels of the applications, which often consume approximately 90% of the execution time, we expect our savings to approach the ideal application improvement of 10X.

This paper describes an inexact string matching scheme devised to improve upon the LURU technique. The scheme uses a set of text strings called common subcircuit expressions (CSEs) to map a high percentage of the subcircuits in a netlist. The inexact matching scheme leverages the don't-care feature of ternary CAMs. Subcircuits are represented as standard-length strings that include wildcards. These strings are called homogeneous LURU strings (HLSs). LURU improves technology mapping by reducing the area requirements of LUT implementations. It also facilitates the profiling of circuits for the discovery of common subcircuits.

The capability and heterogeneity of new FPGA (Field Programmable Gate Array) devices continues to increase with each new line of devices. Efficiently programming these devices is increasing in difficulty. However, FPGAs continue to be utilized for algorithms traditionally targeted to embedded DSP microprocessors such as signal and image processing applications.This paper presents an architecture that combines VLIW (Very Large Instruction Word) processing with the capability to introduce application specific customized instructions and complex hardware functions. To support this architecture, a compilation and design automation flow are described for programs written in C.Several design tradeoffs for the architecture were examined including number of VLIW functional units and register file size. The architecture was implemented on an Altera Stratix II FPGA. The Stratix II device was selected because it offers a large number of high-speed DSP (digital signal processing) blocks that execute multiply accumulate operations.We show that our combined VLIW with hardware functions exhibit as much as 230X speedup and 63X on average for computational kernels for a set of benchmarks. This allows for an overall speedup of 30X and 12X on average for signal processing benchmarks from the MediaBench.

The interconnect plays a key role in both the cost and performance of large-scale HPC systems. The cost of future high-bandwidth electronic interconnects mushrooms due to expensive optical transceivers needed between electronic switches. We describe a potentially cheaper and more power-efficient approach to building high-performance interconnects. Through empirical analysis of HPC applications, we find that the bulk of inter-processor communication (barring collectives) is bounded in degree and changes very slowly or never. Thus we propose a two-network interconnect: An Optical Circuit Switching (OCS) network handling long-lived bulk data transfers, using optical switches; and a secondary lower-bandwidth Electronic Packet Switching (EPS) network. An OCS could be significantly cheaper, as it uses fewer optical transceivers than an electronic network. Collectives and transient communication packets traverse the electronic network. We present compiler techniques and dynamic run-time policies, using this two-network interconnect. Simulation results show that our approach provides high performance at low cost.

Summary form only given. The architecture of modern FPGAs contain over one thousand small memory banks, over five hundred 4k-bit memory banks, and over one hundred thousand logic elements. This inherent parallelism of an FPGA makes it an ideal platform for a multiprocessor architecture. In addition to embedded memory, numerous ASIC multipliers are embedded into the FPGA architecture. This paper introduces a single-instruction-multiple-data (SIMD) system comprised of 2, 4, 8, 16, 32, 64 and 88 processing elements that are built around the ASIC multipliers and controlled by a central instruction stream. In addition to the function of the ASIC multiplier, we have augmented each PE with "custom instructions" to show how the instruction set can be extended. The 88 processors SIMD design utilizes 100% of the DSP blocks available in the Altera Stratix EPS80F1508C6 device, but only 17% of the look-up table logic, which leaves 83% of the logic cells available for custom instructions.

To achieve peak performance in a multiprocessor system, processor synchronization must be accomplished with minimal overhead. Static hardware barrier synchronization has become a popular mechanism for coordinating parallel processors [1]. Dynamic hardware barrier synchronization has typically been considered to require an extensive amount of overhead as compared to static barrier hardware, and so the potential performance increase it gives has been largely ignored [2, 3]. This paper describes a hardware implementation of a dynamic barrier synchronization mechanism with minimal overhead using “cyclical cascade chains.” It is shown that this design can be synthesized into a single FPGA for an inexpensive and efficient synchronization solution for clusters and multiprocessor computers. The design is proven to be deadlock-free and can synchronize 32 processors in an average of 196 nanoseconds. Scalability is addressed for all aspects of the design relevant to its synthesis.