As neural networks (NNs) are increasingly used to provide edge intelligence, there is a growing need to make the edge devices that run them robust to faults. Edge devices must mitigate the resulting hardware failures while maintaining strict constraints on power, energy, latency, throughput, memory size, and computational resources. Edge NNs require fundamental changes in model architecture, e.g., quantization and fewer, smaller layers. PrioriFI is a more informed fault injection (FI) algorithm that evaluates edge NN robustness by ranking NN bits based on their fault sensitivity. PrioriFI prioritizes finding highly fault-sensitive bits, that is, the bits most critical to an NN's correctness, first. To accomplish this, PrioriFI uses the Hessian for the initial parameter ranking. Then, during an FI campaign, PrioriFI uses the information gained from past FIs as a heuristic so that future FIs target the bits likely to be the next most sensitive. With PrioriFI, designers can quickly evaluate different NNs and better co-design fault-tolerant edge NN systems.

Transformer-based models achieve strong performance for jet tagging at the CERN LHC, but deploying them in low-latency, resource-constrained trigger systems is challenging. We present an initial implementation of a quantized, integer-only transformer for jet tagging on the AMD Versal AI Engine (AIE), mapping dense and multi-head attention (MHA) layers to AIE tiles. The main contribution is a reusable software framework that represents transformer layers as composable AIE building blocks and automatically generates the corresponding Vitis graph code from a high-level Python model description. This framework provides a foundation for future research and is released as open-source software at https://github.com/KastnerRG/particle_transformer_aie.

The scientific community increasingly relies on machine learning (ML) for near-sensor processing, leveraging its strengths in tasks such as pattern recognition, anomaly detection, and real-time decision-making. These deployments demand accelerators that combine extremely high performance with programmability, ease of integration, and straightforward verification. We present cgra4ml , an open-source, modular framework that generates parameterizable CGRA accelerators in synthesizable SystemVerilog RTL, tailored to common ML compute patterns found in scientific applications. The framework supports seamless system integration through AXI-compliant interfaces and open-source DMA components, and it includes automatic firmware generation for programming the accelerator. A comprehensive verification suite and a runtime firmware stack further support deployment across diverse SoC platforms. cgra4ml provides a modular, full-stack infrastructure, including a Python API, SystemVerilog hardware, TCL toolflows, and a C runtime, which facilitates easy integration and experimentation, allowing scientists to focus on innovation rather than dealing with the intricacies of hardware design and optimization. We demonstrate the effectiveness of cgra4ml to implement common scientific edge neural networks using ASIC and FPGA design flows.

Many verification methods have been proposed to detect microarchitectural information leakage in response to the surge of security breaches in hardware designs. These sophisticated efforts have gone a long way toward preventing attackers from breaking the system’s confidentiality. However, each approach has its own set of weaknesses: it may not be scalable enough, exhaustive enough, flexible enough to meet changing requirements or fit well into existing verification flows. We propose FastPath, a hybrid verification methodology that combines the efficiency of simulation with the exhaustive nature of formal verification. FastPath employs a structural analysis framework to automate the method further. Our experimental results compare FastPath to a state-of-the-art formal approach, showing a significant reduction in manual effort while achieving the same level of exhaustive confidence. We also discovered and contributed a fix for a previously unknown leak of internal operands in cv32e40s, a RISC-V processor intended for security applications.

Applications like high-energy physics and cybersecurity require extremely high throughput and low latency neural network (NN) inference. Lookup-table-based NNs address these constraints by implementing NNs as lookup tables (LUTs), achieving inference latency on the order of nanoseconds. Since LUTs are a fundamental FPGA building block, LUT-based NNs efficiently map to FPGAs. LogicNets (and its successors) form one class of LUT-based NNs that target FPGAs, mapping neurons directly to LUTs to meet low latency constraints with minimal resources. However, it is difficult to build larger, more performant LUT-based NNs like LogicNets because LUT usage increases exponentially with respect to neuron fan-in (i.e., number of synapses X synapse bitwidth). A large LUT-based NN quickly runs out of LUTs on an FPGA. Our work AmigoLUT addresses this issue by creating ensembles of smaller LUT-based NNs that scale linearly with respect to the number of models. AmigoLUT improves the scalability of LUT-based NNs, reaching higher throughput with up to an order of magnitude fewer LUTs than the largest LUT-based NNs.

Remote attackers can recover "FPGA pentimento" - long-removed data belonging to a prior user or proprietary design image on a cloud FPGA. Just as a pentimento of a painting can be exposed by infrared imaging, FPGA pentimentos can be exposed by signal timing sensors. The data constituting an FPGA pentimento is imprinted on the device through bias temperature instability effects on the underlying transistors. Measuring this degradation using a time-to-digital converter allows an attacker to (1) extract proprietary details or keys from an encrypted FPGA design image available on the AWS marketplace and (2) recover information from a previous user of a cloud-FPGA. These threat models are validated on AWS F1, with successful AES key recovery under one model.

The Arm Advanced eXtensible Interface (AXI) protocol is a widely used on-chip interconnect for processors, accelerators, memories, and other IPs. Any bugs in the AXI implementations pose a security risk to the chip's correctness. Buggy or non-compliant third-party IPs can use AXI implementation bugs to bypass the security mechanisms of the whole system. Identifying AXI implementation bugs is challenging because the incomplete specifications allow room for implementation-specific behavior in performant designs. EXPECT is a systematic approach for analyzing AXI implementations to detect functional and security violations. We use EXPECT to test 7 implementations of varying complexity, including the ones from AMD Xilinx and RISC-V PULP. We identified 135 property violations. We sampled 10 of them to show 7 exploits demonstrating that an attacker can use these bugs to trick victim IPs. Our exploits achieve outcomes such as using stale data, skipping reads and writes, leaking intermediate data, and reading and writing attacker-controlled data to attacker-controlled addresses. We evaluated our exploits in realistic scenarios deployed on FPGA. We show that AMD Xilinx protocol checker IPs miss 5/7 of our exploits.

Extreme data rate scientific experiments create massive amounts of data that require efficient ML edge processing. This leads to unique validation challenges for VLSI implementations of ML algorithms: enabling bit-accurate functional simulations for performance validation in experimental software frameworks, verifying those ML models are robust under extreme quantization and pruning, and enabling ultra-fine-grained model inspection for efficient fault tolerance. We discuss approaches to developing and validating reliable algorithms at the scientific edge under such strict latency, resource, power, and area requirements in extreme experimental environments. We study metrics for developing robust algorithms, present preliminary results and mitigation strategies, and conclude with an outlook of these and future directions of research towards the longer-term goal of developing autonomous scientific experimentation methods for accelerated scientific discovery.

Ensuring predictability in modern real-time Systems-on-Chip (SoCs) is an increasingly critical concern for many application domains such as automotive, robotics, and industrial automation. An effective approach involves the modeling and development of hardware components, such as interconnects and shared memory resources, to evaluate or enforce their deterministic behavior. Unfortunately, these IPs are often closed-source, and these studies are limited to the single modules that must later be integrated with third-party IPs in more complex SoCs, hindering the precision and scope of modeling and compromising the overall predictability. With the coming-of-age of open-source instruction set architectures (RISC-V) and hardware, major opportunities for changing this status quo are emerging. This study introduces an innovative methodology for modeling and analyzing State-of-the-Art (SoA) open-source SoCs for low-power cyber-physical systems. Our approach models and analyzes the entire set of open-source IPs within these SoCs and then provides a comprehensive analysis of the entire architecture. We validate this methodology on a sample heterogenous low-power RISC-V architecture through RTL simulation and FPGA implementation, minimizing pessimism in bounding the service time of transactions crossing the architecture between 28% and 1%, which is considerably lower when compared to similar SoA works.

Voltage fluctuation sensors measure minute changes in an FPGA power distribution network, allowing attackers to extract information from concurrently executing computations. Previous voltage fluctuation sensors make assumptions about the co-tenant computation and require the attacker have a priori access or system knowledge to tune the sensor parameters statically. Additionally, prior voltage fluctuation sensors make use of proprietary vendor intellectual property and do not provide guidance on sensor migration to other vendors. We present the open-source design of the Tunable Dual-Polarity Time-to-Digital Converter, which introduces three dynamically tunable parameters that optimize signal measurement, including the transition polarity, sample window, frequency, and phase. We show that a properly tuned sensor improves co-tenant classification accuracy by 2.5 \(\times\) over prior work and increases the ability to identify the co-tenant computation and its microarchitectural implementation. Across 13 varying applications, our techniques yield an 80% classification accuracy that generalizes beyond a single board. Our sensor improves the ability of a correlation power analysis attack to rank correct subkey values by 2 \(\times\) . As an extension to our prior work, we show that the voltage fluctuation sensor is portable to multiple FPGA vendors, and we demonstrate implementations on both Xilinx and Intel FPGA systems.

Deep neural networks use skip connections to improve training convergence. However, these skip connections are costly in hardware, requiring extra buffers and increasing on- and off-chip memory utilization and bandwidth requirements. In this article, we show that skip connections can be optimized for hardware when tackled with a hardware-software codesign approach. We argue that while a network’s skip connections are needed for the network to learn, they can later be removed or shortened to provide a more hardware-efficient implementation with minimal to no accuracy loss. We introduce Tailor , a codesign tool whose hardware-aware training algorithm gradually removes or shortens a fully trained network’s skip connections to lower the hardware cost. Tailor improves resource utilization by up to 34% for block random access memories (BRAMs), 13% for flip-flops (FFs), and 16% for look-up tables (LUTs) for on-chip, dataflow-style architectures. Tailor increases performance by 30% and reduces memory bandwidth by 45% for a two-dimensional processing element array architecture.

1.5 billion smartphones are sold annually, and most are decommissioned less than two years later. Most of these unwanted smartphones are neither discarded nor recycled but languish in junk drawers and storage units. This computational stockpile represents a substantial wasted potential: modern smartphones have increasingly high-performance and energy-efficient processors, extensive networking capabilities, and a reliable built-in power supply. This project studies the ability to reuse smartphones as "junkyard computers." Junkyard computers grow global computing capacity by extending device lifetimes, which supplants the manufacture of new devices. We show that the capabilities of even decade-old smartphones are within those demanded by modern cloud microservices and discuss how to combine phones to perform increasingly complex tasks. We describe how current operation-focused metrics do not capture the actual carbon costs of compute. We propose Computational Carbon Intensity---a performance metric that balances the continued service of older devices with the superlinear runtime improvements of newer machines. We use this metric to redefine device service lifetime in terms of carbon efficiency. We develop a cloudlet of reused Pixel 3A phones. We analyze the carbon benefits of deploying large, end-to-end microservice-based applications on these smartphones. Finally, we describe system architectures and associated challenges to scale to cloudlets with hundreds and thousands of smartphones.

Voltage fluctuation sensors measure minute changes in an FPGA power distribution network, allowing attackers to extract information from concurrently executing computations. Previous voltage fluctuation sensors make assumptions about the co-tenant computation and require the attacker have a priori access or system knowledge to tune the sensor parameters statically. We present the open-source design of the Tunable Dual-Polarity Time-to-Digital Converter, which introduces three dynamically tunable parameters that optimize signal measurement, including the transition polarity, sample window, frequency, and phase. We show that a properly tuned sensor improves co-tenant classification accuracy by 2.5× over prior work and increases the ability to identify the co-tenant computation and its microarchitectural implementation. Across 13 varying applications, our techniques yield an 80% classification accuracy that generalizes beyond a single board. Finally, our sensor improves the ability of a correlation power analysis attack to rank correct subkey values by 2×.

Deep neural networks employ skip connections – identity functions that combine the outputs of different layers-to improve training convergence; however, these skip connections are costly to implement in hardware. In particular, for inference accelerators on resource-limited platforms, they require extra buffers, increasing not only on- and off-chip memory utilization but also memory bandwidth requirements. Thus, a network that has skip connections costs more to deploy in hardware than one that has none. We argue that, for certain classification tasks, a network's skip connections are needed for the network to learn but not necessary for inference after convergence. We thus explore removing skip connections from a fully-trained network to mitigate their hardware cost. From this investigation, we introduce a fine-tuning/retraining method that adapts a network's skip connections – by either removing or shortening them-to make them fit better in hardware with minimal to no loss in accuracy. With these changes, we decrease resource utilization by up to 34% for BRAMs, 7% for FFs, and 12% LUTs when implemented on an FPGA.

Hardware security creates a hardware-based security foundation for secure and reliable operation of systems and applications used in our modern life. The presence of design for security, security assurance, and general security design life cycle practices in product life cycle of many large semiconductor design and manufacturing companies these days indicates that the importance of hardware security has been very well observed in industry. However, the high cost, time, and effort for building security into designs and assuring their security - due to using many manual processes - is still an important obstacle for economy of secure product development. This paper presents several promising directions for automation of design for security and security assurance practices to reduce the overall time and cost of secure product development. First, we present security verification challenges of SoCs, possible vulnerabilities that could be introduced inadvertently by tools mapping a design model in one level of abstraction to its lower level, and our solution to the problem by automatically mapping security properties from one level to its lower level incorporating techniques for extension and expansion of the properties. Then, we discuss the foundation necessary for further automation of formal security analysis of a design by incorporating threat model and common security vulnerabilities into an intermediate representation of a hardware model to be used to automatically determine if there is a chance for direct or indirect flow of information to compromise confidentiality or integrity of security assets. Finally, we discuss a pre-silicon-based framework for practical and time-and-cost effective power-side channel leakage analysis, root-causing the side-channel leakage by using the automatically generated leakage profile of circuit nodes, providing insight to mitigate the side-channel leakage by addressing the high leakage nodes, and assuring the effectiveness of the mitigation by reprofiling the leakage to prove its acceptable level of elimination. We hope that sharing these efforts and ideas with the security research community can accelerate the evolution of security-aware CAD tools targeted to design for security and security assurance to enrich the ecosystem to have tools from multiple vendors with more capabilities and higher performance.

System-on-chip (SoC) architectures are a heterogeneous mix of microprocessors, custom accelerators, memories, interfaces, peripherals, and other resources. These resources communicate using complex on-chip interconnect networks that attempt to quickly and efficiently arbitrate memory transactions whose behaviors can vary drastically depending on the current mode of operation and system operating state. Security- and safety-critical applications require access control policies that define how these resources interact to ensure that malicious and unsafe behaviors do not occur.Akeris a design and verification framework for on-chip access control. The core ofAkeris the access control wrapper (ACW)–a high-performance yet efficient hardware module that dynamically arbitrates on-chip communications.Akerdistributes ACWs across the SoC and programs them to perform local access control.Akerprovides a firmware generation tool and a property-driven security verification methodology to ensure that the ACWs are properly integrated and configured.Akersecurity verification confirms that the ACW behaves properly at IP level. It verifies the hardware root of trust firmware configures the ACW correctly. And it evaluates system-level security threats due to interactions between shared resources.Akeris experimentally validated on a Xilinx UltraScale+ programmable SoC. Additionally, anAkeraccess control system is integrated into the OpenPULP multicore archtiecture that uses OpenTitan hardware root-of-trust for firmware configuration.

Security verification is an important part of the hardware design process. Security verification teams can uncover weaknesses, vulnerabilities, and flaws. Unfortunately, the verification process involves substantial manual analysis to create the threat model, identify important security assets, articulate weaknesses, define security requirements, and specify security properties that formally describe security requirements upon the hardware. This work describes current hardware security verification practices. Many of these rely on manual analysis. We argue that the property generation process is a first step towards scalable and reproducible hardware security verification.

Modern FPGA system on chips uses complex multimanager, multisubordinate on-chip communication networks. Processor cores, hardware accelerators, DMA engines, and other manager components actively access subordinate components like off-chip DRAM, on-chip memories, caches, and I/Os. On-chip communication networks are designed for high bandwidth and low latency. They use simple, fast transactions that largely assumes the managers cooperate. For example, it does not describe default mechanisms to ensure the safe behaviors of the managers using the on-chip interconnect. This lack of specification can lead to unpredictable behaviors: a single misbehaving, misconfigured, or malicious component can cause denial of service of shared resources. Clearly, this issue is critical in systems with safety and security constraints. Cut and forward is a novel switching method for multicomponent communication architectures on FPGA systems on chips (SoCs). Cut and forward leverages the programmability of FPGA SoCs to enable safe and secure bus access and is carefully designed to minimize its impact on performance and resource usage. Experiments show that Cut and forward ensures safety and security in realistic applications deployed on a commercial FPGA SoC from Xilinx including a popular deep neural network accelerator.

Design space exploration (DSE) provides intelligent methods to tune the large number of optimization parameters present in modern FPGA high-level synthesis tools. High-level synthesis parameter tuning is a time-consuming process due to lengthy hardware compilation times—synthesizing an FPGA design can take tens of hours. DSE helps find an optimal solution faster than brute-force methods without relying on designer intuition to achieve high-quality results. Sherlock is a DSE framework that can handle multiple conflicting optimization objectives and aggressively focuses on finding Pareto-optimal solutions. Sherlock integrates a model selection process to choose the regression model that helps reach the optimal solution faster. Sherlock designs a strategy based around the multi-armed bandit problem, opting to balance exploration and exploitation based on the learned and expected results. Sherlock can decrease the importance of models that do not provide correct estimates, reaching the optimal design faster. Sherlock is capable of tailoring its choice of regression models to the problem at hand, leading to a model that best reflects the application design space. We have tested the framework on a large dataset of FPGA design problems and found that Sherlock converges toward the set of optimal designs faster than similar frameworks.

Modern data centers leverage large FPGAs to provide low latency, high throughput, and low energy computation. FPGA multi-tenancy is an attractive option to maximize utilization, yet it opens the door to new security threats. In this work, we develop a remote classification pipeline that targets the confidentiality of multi-tenant cloud FPGA environments. We utilize an in-fabric voltage sensor that measures subtle changes in the power distribution network caused by co-located computations. The sensor measurements are given to a classification pipeline that is able to deduce information about co-located applications including the type of computation and its implementation. We study the importance of the trace length and other aspects that affect classification accuracy. Our results show that we can determine if another co-tenant is present with 96% accuracy. We can classify with 98% accuracy whether a power waster circuit is operating. Furthermore, we are able to determine if a cryptographic operation is occuring, differentiate between different cryptographic algorithms (AES and PRESENT) and microarchitectural implementations (Microblaze, ORCA, and PicoRV32).

Side-channel leakage poses a major security threat in multi-tenant FPGA environments. One tenant can instantiate a voltage fluctuation sensor that measures minute changes in the power distribution network (PDN) and infer information about co-tenant computation and data. This work presents the Tunable Dual-Edged Time-to-Digital Converter (TDC) - a voltage fluctuation sensor with two unique elements: first, it has the ability to tune the sample duration, phase, and frequency to more effectively extract information about the co-located computation; second, it captures both rising and falling transitions which provides unique information about the target computation.

Modern data centers leverage large FPGAs to provide low latency, high throughput, and low energy computation. FPGA multi-tenancy is an attractive option to maximize utilization, yet it opens the door to unique security threats. In this work, we develop a remote classification pipeline that targets the confidentiality of multi-tenant cloud FPGA environments. We design a unique Dual-Edged voltage fluctuation sensor that measures subtle changes in the power distribution network caused by co-located computations. The sensor measurements are given to a classification pipeline that is able to deduce information about co-located applications including the type of computation and its implementation. We study the importance of the trace length, signal conditioning algorithms, and other aspects that affect classification accuracy. Our results show that we can determine if another co-tenant is present with 96% accuracy. We can classify with 98% accuracy whether a power waster circuit is operating. Furthermore, we are able to determine if a cryptographic operation is occurring, differentiate between different cryptographic algorithms (AES and PRESENT) and microarchitectural implementations (Microblaze, ORCA, and PicoRV32).

Spiking Neural Networks (SNNs) are the next generation of Artificial Neural Networks (ANNs) that utilize an event-based representation to perform more efficient computation. Most SNN implementations have a systolic array-based architecture and, by assuming high sparsity in spikes, significantly reduce computing in their designs. This work shows this assumption does not hold for applications with signals of large temporal dimension. We develop a streaming SNN (S2N2) architecture that can support fixed-per-layer axonal and synaptic delays for its network. Our architecture is built upon FINN and thus efficiently utilizes FPGA resources. We show how radio frequency processing matches our S2N2 computational model. By not performing tick-batching, a stream of RF samples can efficiently be processed by S2N2, improving the memory utilization by more than three orders of magnitude.

An adversary can exploit side-channel information such as power consumption, electromagnetic (EM) emanations, acoustic vibrations or the timing of encryption operations to derive the secret key from an electronic device. Signature aTtenuation Embedded CRYPTO with Low-Level metAl Routing (STELLAR) is a technique to mitigate power and EM-based attacks, however, it incurs 50% power overhead. This work presents iSTELLAR, which reduces the power overhead by operating STELLAR intermittently utilizing an intelligent scheduling algorithm. The proposed scheduling algorithm for iSTELLAR determines the optimal locations during the crypto operation to turn STELLAR ON, and thereby reduces the power overhead by$> 30\%$compared to the normal STELLAR operation, while eliminating the information leakage.

Modern systems on a chip (SoCs) utilize heterogeneous architectures where multiple IP cores have concurrent access to on-chip shared resources. In security-critical applications, IP cores have different privilege levels for accessing shared resources, which must be regulated by an access control system. Aker is a design and verification framework for SoC access control. Aker builds upon the Access Control Wrapper (ACW) - a high performance and easy-to-integrate hardware module that dynamically manages access to shared resources. To build an SoC access control system, Aker distributes the ACWs throughout the SoC, wrapping controller IP cores, and configuring the ACWs to perform local access control. To ensure the access control system is functioning correctly and securely, Aker provides a property-driven security verification using MITRE common weakness enumerations. Aker verifies the SoC access control at the IP level to ensure the absence of bugs in the functionalities of the ACW module, at the firmware level to confirm the secure operation of the ACW when integrated with a hardware root-of-trust (HRoT), and at the system level to evaluate security threats due to the interactions among shared resources. The performance, resource usage, and security of access control systems implemented through Aker is experimentally evaluated on a Xilinx UltraScale+ programmable SoC, it is integrated with the OpenTitan hardware root-of-trust, and it is used to design an access control system for the OpenPULP multicore architecture.

Training a neural network is a complicated and time-consuming task that involves adjusting and testing different combinations of hyperparameters. One of the essential hyperparameters is the learning rate, which balances the magnitude of changes at each training step. We introduce an Adaptive Scheduler for Learning Rate (ASLR) that significantly lowers the tuning effort since it only has a single hyperparameter. ASLR produces competitive results compared to the state-of-the-art for both hand-optimized learning rate schedulers and line search methods while requiring significantly less tuning effort. Our algorithm's computational cost is trivial and can be used to train various network topologies included quantized networks.

Passive acoustic monitoring (PAM) involves deploying audio recorders across a natural environment over a long period of time to collect large quantities of audio data. To parse through this data, researchers have worked with automated annotation techniques stemming from Digital Signal Processing and Machine Learning to identify key species calls and judge a region’s biodiversity. To apply and evaluate those techniques, one must acquire strongly labeled data that marks the exact temporal location of audio events in the data, as opposed to weakly labeled data which only labels the presence of an audio event across a clip.Pyrenote was designed to fit the demand for strong manual labels in PAM data. Based on Audino, an open-source, web-based, and easy-to-deploy audio annotation tool, Pyrenote displays a spectrogram for audio annotation, stores labels in a database, and optimizes the labeling process through simplifying the user interface to produce high-quality annotations in a short time frame. This paper documents Pyrenote’s functionality, how the challenge informed the design of the system, and how it compares to other labeling systems.

Although hardware security has received significant attention in the past decade or so, security design and validation engineers and researchers in industry, academia, and government have not still been equipped with a mature security-aware toolset to automatically and effectively analyze designs for various types of security vulnerabilities at different to detect and fix the security issues or build security in designs efficiently and easily. Despite such a demand, currently, there is not an ecosystem of security-aware Electronic Design Automation (EDA) or Computer-Aided Design (CAD) tools whereas the commercial design for security and validation tools are still in their infancy. However, there exist many research works that try to come up with security analysis engines and provide solutions to address different classes of security issues such as data leakage, access control violation, side-channel leakage, hardware Trojans and malicious changes, and vulnerabilities to physical attacks, fault-injection attacks, reverse engineering attacks, and chip counterfeiting or overproduction attacks. This paper presents the foundation established by several academic and industry researchers who have been supporting the realization of an ecosystem of security-aware CAD tools with their focus on hardware security coverage and fault-injection assessment for SoC designs, and security assurance standardization for electronic design integration.

Hardware security and trust have become a pressing issue during the last two decades due to the globalization of the semiconductor supply chain and ubiquitous network connection of computing devices. Computing hardware is now an attractive attack surface for launching powerful cross-layer security attacks, allowing attackers to infer secret information, hijack control flow, compromise system root-of-trust, steal intellectual property (IP), and fool machine learners. On the other hand, security practitioners have been making tremendous efforts in developing protection techniques and design tools to detect hardware vulnerabilities and fortify hardware design against various known hardware attacks. This article presents an overview of hardware security and trust from the perspectives of threats, countermeasures, and design tools. By introducing the most recent advances in hardware security research and developments, we aim to motivate hardware designers and electronic design automation tool developers to consider the new challenges and opportunities of incorporating an additional dimension of security into robust hardware design, testing, and verification.

High-level synthesis (HLS) allows hardware designers to think algorithmically and not worry about low-level, cycle-by-cycle details. This provides the ability to quickly explore the architectural design space and tradeoffs between resource utilization and performance. Unfortunately, security evaluation is not a standard part of the HLS design flow. In this article, we aim to understand the effects of memory-based HLS optimizations on power side-channel leakage. We use Xilinx Vivado HLS to develop different cryptographic cores, implement them on a Spartan-6 FPGA, and collect power traces. We evaluate the designs with respect to resource utilization, performance, and information leakage through power consumption. We have two important observations and contributions. First, the choice of resource optimization directive results in different levels of side-channel vulnerabilities. Second, the partitioning optimization directive can greatly compromise the hardware cryptographic system through power side-channel leakage due to the deployment of memory control logic. We describe an evaluation procedure for power side-channel leakage and use it to make best-effort recommendations about how to design more secure architectures in the cryptographic domain.

Simultaneous Localization And Mapping (SLAM) is an important technique used in robotics, computer vision, and virtual/augmented reality. SLAM algorithms have moved past creating sparse maps to making dense 3D reconstruction of the environment. Dense SLAM algorithms have high computational demands that require hardware acceleration to be done efficiently in real-time. FPGAs are an attractive compute platform for SLAM systems as they are low power and high performance. Unfortunately, dense SLAM algorithms are complex and FPGAs are notoriously difficult to program. In this work, we study the best techniques for accelerating 3D reconstruction on FPGA. We analyze a 3D reconstruction system, and implement modular FPGA designs for the main components of this application. We target both an FPGA SoC and a larger FPGA PCIe board, and perform a design space exploration (DSE) of our designs. We analyze the results of our DSE, characterize the design spaces to highlight important features, and we implement the best designs in an open-source and end-to-end dense SLAM system running on a FPGA SoC board. On the SoC board, using the FPGA increases the throughput of the whole application by a factor of two compared to the ARM processor, and individual algorithms are up to 38 times faster on the FPGA.

We present VeriSketch, a security-oriented program synthesis framework for developing hardware designs with formal guarantee of functional and security specifications. VeriSketch defines a synthesis language, a code instrumentation framework for specifying and inferring timing-sensitive information flow properties, and uses specialized constraint-based synthesis for generating HDL code that enforces the specifications. We show the power of VeriSketch through security-critical hardware design examples, including cache controllers, thread schedulers, and system-on-chip arbiters, with formal guarantee of security properties such as absence of timing side-channels, confidentiality, and isolation.

For many devices, power side-channel attacks are an effective means of obtaining secret keys from cryptographic algorithms. Recently, methods have been proposed to assess the vulnerability of devices to these attacks. While existing approaches effectively evaluate device vulnerability to attacks at specific points during execution, they do not consider the power measurement vectors holistically, using all time points in the measurement. This is necessary in order to accurately assess resistance to multi-target attacks. In this work, we identify characteristics of an ideal holistic side-channel security metric and develop a metric under these criteria. We demonstrate that our approach correctly ranks different FPGA implementations of AES with respect to attack difficulty.

Autoregressive convolutional neural networks (CNNs) have been widely exploited for sequence generation tasks such as audio synthesis, language modeling and neural machine translation. WaveNet is a deep autoregressive CNN composed of several stacked layers of dilated convolution that is used for sequence generation. While WaveNet produces state-of-the art audio generation results, the naive inference implementation is quite slow; it takes a few minutes to generate just one second of audio on a high-end GPU. In this work, we develop the first accelerator platform FastWave for autoregressive convolutional neural networks, and address the associated design challenges. We design the Fast-Wavenet inference model in Vivado HLS and perform a wide range of optimizations including fixed-point implementation, array partitioning and pipelining. Our model uses a fully parameterized parallel architecture for fast matrix-vector multiplication that enables per-layer customized latency fine-tuning for further throughput improvement. Our experiments comparatively assess the tradeoff between throughput and resource utilization for various optimizations. Our best WaveNet design on the Xilinx XCVU13P FPGA that uses only on-chip memory, achieves 66× faster generation speed compared to CPU implementation and 11× faster generation speed than GPU implementation.

editorial Free Access Share on Introduction to the Special Section on Security in FPGA-accelerated Cloud and Datacenters Editors: Chistophe Bobda University of Florida Russell Tessier, University of Massachusetts Amherst University of Florida Russell Tessier, University of Massachusetts AmherstView Profile , Ken Eguro Microsoft Research Ryan Kastner, University of California, San Diego Microsoft Research Ryan Kastner, University of California, San DiegoView Profile Authors Info & Claims ACM Transactions on Reconfigurable Technology and SystemsVolume 12Issue 3September 2019 Article No.: 11epp 1–3https://doi.org/10.1145/3352060Published:13 September 2019Publication History 0citation190DownloadsMetricsTotal Citations0Total Downloads190Last 12 Months44Last 6 weeks5 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 SiteView all FormatsPDF

FPGAs are a computing platform that excel in performing signal processing, control, networking, and security in a high performance and power efficient manner. This makes FPGAs attractive for unmanned aerial vehicles (UAVs) especially as they require smaller payloads and are processing multiple high data rate input sources (e.g. cameras, lidar, radar, gyroscopes, accelerometers). Unfortunately, FPGAs are notoriously difficult to program and they require significant hardware design expertise. However, there are newly released design tools aimed at making FPGAs easier to use, which drove the initial hypothesis for this paper: could three undergraduates program an FPGA to control a UAV in 10 weeks? The result of the experiment is PynqCopter - an open source control system implemented on an FPGA. We created and tested a UAV overlay which is able to run multiple computations in parallel, allowing for the ability to process high amounts of data at runtime.

High-level synthesis (HLS) allows hardware designers to think algorithmically and not have to worry about low-level, cycle-by-cycle details. This provides the ability to quickly explore the architectural design space and tradeoff between resource utilization and performance. Unfortunately, evaluating the security is not a standard part of the HLS design flow. In this work, we aim to understand the effects of HLS optimizations with respect to power side-channel leakage. We use Vivado HLS to develop different cryptographic cores, implement them on a Xilinx Spartan 6 FPGA, and collect power traces. We evaluate the designs with respect to resource utilization, performance, and side-channel leakage through power consumption. Furthermore, we analyze the first-order leakage of the HLS-based designs alongside well-known register transfer level (RTL) cryptographic cores. We describe an evaluation procedure for hardware designers and use it to make insightful recommendations on how to design the best architecture in cryptographic domain.

Non-rigid 3D registration is a technique for matching 3D scans of a scene involving deformable objects. Augmented reality, gesture recognition, medical imaging, and many other computer vision and graphics applications require real-time registration to model deformable or articulated objects. Unfortunately, non-rigid registration is a computationally intensive problem that requires careful optimization to maximize throughput and latency. We present a FPGA+CPU accelerator for real-time non-rigid 3D registration based on Tree Reweighted Message Passing (TRW-S). We overcome memory bound issues and scheduling limitations of conventional TRW-S by dynamically generating the Markov Random Fields. This, along with a bevy of other architectural optimizations, allows us to almost saturate 1024 multipliers in a Arria 10 at 100MHz. We achieve a 600x speed up over baseline TRW-S and our registration architecture has up to 81x energy reduction over a software implementation of our algorithm. We demonstrate the performance of our system by performing real-time (20 scan per second) registration on a complicated surgical scene.

The RISC-V specification is a highly flexible specification for low-cost processors. The RISC-V ISA is royalty free, vendor agnostic, easily portable between development environments, and highly flexible to match the demands of an application. These characteristics make RISC-V a natural ISA choice for an FPGA soft processor and this has led to widespread adoption in academia and industry. However, the sheer number of RISC-V projects can be daunting for potential users. This paper describes a tool for exploring RISC-V projects. Our tool provides a web-interface for executing C/C++ code, tests, and benchmarks. Our tool is packaged with interactive tutorials for extending, modifying, and reproducing our work.

Hardware information flow analysis detects security vulnerabilities resulting from unintended design flaws, timing channels, and hardware Trojans. These information flow models are typically generated in a general way, which includes a significant amount of redundancy that is irrelevant to the specified security properties. In this work, we propose a property specific approach for information flow security. We create information flow models tailored to the properties to be verified by performing a property specific search to identify security critical paths. This helps find suspicious signals that require closer inspection and quickly eliminates portions of the design that are free of security violations. Our property specific trimming technique reduces the complexity of the security model; this accelerates security verification and restricts potential security violations to a smaller region which helps quickly pinpoint hardware security vulnerabilities.

As demonstrated by numerous practical attacks, the physical act of computation emits unintended and damaging information through infinitesimal variations in timing, power, and resource contention. While there are many techniques for preventing the leakage of information through power channels for specific cryptographic units, they are typically either built directly into the hardware logic or exploit intricate mathematical properties of the algorithm itself. However, such leaks are not uniform in time but, as we show, rather occur in specific bursts. Exploiting this observation we propose a set of software-controlled techniques allowing for the seamless disconnection and reconnection of general purpose programmable components in a system-on-chip. Such a system is capable of providing brief moments of electrical isolation during which the most critical computations can be performed free from both timing and power measurement. Of course, disconnection comes at a cost. To balance the resulting trade-off between overhead and security effectively, we describe a new analysis technique to uncover the "leakiest" intervals of time, we provide an algorithm to co-optimize the covering of these intervals and the performance/energy costs under a set of architecture imposed constraints, and explore the architectural and software ramifications of such intermittent disconnection. In the end we find that by hiding only between 15% and 30% of the trace, at a performance cost of between 15% and 50%, we are able to reduce the mutual information between the leakage model and key bits by 75% on average, and to nearly zero in specific cases.

Cryptographic cores are known to leak information about their private key due to runtime variations, and there are many well-known attacks that can exploit this timing channel. In this paper, we study how information theoretic measures can quantify the amount of key leakage that can be exacted from runtime measurements. We develop and analyze 22 Rivest-Shamir-Adleman (RSA) hardware designs-each with unique performance optimizations, timing channel mitigation techniques, or discretization/randomization countermeasures. We demonstrate the effectiveness of information theoretic measures for quantifying timing leakage through correlation analysis of information theoretic measurements and attack results. Experimental results show that mutual information is a promising technique for quantifying timing leakage for RSA, advanced encryption standard, and elliptic curve cryptography ciphers, i.e., the mutual information correlates to being able to successfully guess the value of the private key. This is an important step toward a hardware security metric which allows designers to reason about security alongside traditional hardware design metrics like area, performance, and power.

State-of-the-art C/C++ synthesis tools lack abstractions and conveniences that are pervasive in modern software languages. Higher-order functions are particularly important as they increase productivity by concisely representing common design patterns. Providing these in hardware design environments would improve the accessibility of hardware tools for software engineers by providing familiar interfaces and abstractions. We have created an open-source library of higher-order functions synthesizable in C/C++ hardware development tools. We implement six common algorithms on a PYNQ board and conclude that our library produces results that are generally statistically indistinguishable from nonrecursive techniques.

The 28thIEEE International Conference on Application-specific Systems, Architectures, and Processors returns to the United States, this time in Seattle, Washington. We welcome everyone to the Pacific Northwest's largest and most culturally-diverse city. Although the Seattle area is certainly a technology hub, we also hope that you will have a chance to enjoy the natural beauty and specialty cuisine of the area, from Puget Sound to the Cascade Mountains and beyond.

Learning cumulative distribution functions (CDFs) is a widely studied problem in data stream summarization. While current techniques have efficient software implementations, their efficiency depends on updates to data structures that are not easily adapted to FPGA or ASIC implementation. In this work, we develop an algorithm and a compact hardware architecture for learning the CDF of a data stream and apply our technique to the problem of on-chip run-time testing for bias in the output of random number generators (RNGs). Unlike previous approaches, our method is successful regardless of the expected output distribution of the RNG under test.

Hardware has become an increasingly attractive target for attackers, yet we still largely lack tools that enable us to analyze large designs for security flaws. Information flow tracking (IFT) models provide an approach to verifying a hardware design's adherence to security properties related to isolation and reachability.

Information Flow Tracking (IFT) provides a formal methodology for modeling and reasoning about security properties related to integrity, confidentiality, and logical side channel. Recently, IFT has been employed for secure hardware design and verification. However, existing hardware IFT techniques either require designers to rewrite their hardware specifications in a new language or do not scale to large designs due to a low level of abstraction. In this work, we propose Register Transfer Level IFT (RTLIFT), which enables verification of security properties in an early design phase, at a higher level of abstraction, and directly on RTL code. The proposed method enables a precise understanding of all logical flows through RTL design and allows various tradeoffs in IFT precision. We show that RTLIFT achieves over 5x speedup in verification performance as compared to gate level IFT while minimizing the required effort for the designer to verify security properties on RTL designs.

Emergence of side channel security attacks has challenged the classic assumptions regarding what data is publicly available. As demonstrated repeatedly, statistical analysis of information collected by measuring completion time of hardware designs can reveal confidential information. Even though timing-based side channel leakage can be easily exploited to breach data privacy, conventional hardware verification tools are not yet suited to assess these vulnerabilities. To acquaint the hardware design process with formal security evaluations, we introduce a model for tracking timing-based information flows through HDL codes. Based on this model, we have developed Clepsydra, a tool for automatically generating circuitry for tracking timing flows and generic logical flows within hardware designs in two distinct channels. The circuit generated by Clepsydra can be analyzed by EDA tools to detect timing leakage or formally prove constant execution time. We present proofs regarding soundness and precision of the proposed model along with results of employing Clepsydra to verify security properties on a variety of hardware units including crypto cores, bus architectures, caches and arithmetic modules.

Hardware Trojans are a significant security threat due to the globalization of hardware design and supply chain. We demonstrate a new type of hardware Trojan hidden behind internal don't care conditions. The proposed Trojans can pass through formal equivalence checking; they may reside after logic synthesis optimizations; and they are resilient to switching probability and side channel analysis. The new Trojans can create a surface for fault attack to retrieve secret information or downgrade performance by increasing power consumption. Experimental results show that these Trojans may stay after logic synthesis and that secret information can be retrieved using fault attack. We present detectability analysis and suggest synthesis optimizations as well as countermeasures that can help mitigate this new Trojan.

Data clustering is a fundamental challenge in data analytics. It is the main task in exploratory data mining and a core technique in machine learning. As the volume, variety, velocity, and variability of data grows, we need more efficient data analysis methods that can scale towards increasingly large and high dimensional data sets. We develop a streaming clustering algorithm that is highly amenable to hardware acceleration. Our algorithm eliminates the need to store the data objects, which removes limits on the size of the data that we can analyze. Our algorithm is highly parameterizable, which allows it to fit to the characteristics of the data set, and scale towards the available hardware resources. Our streaming hardware core can handle more than 40 Msamples/s when processing 3-dimensional streaming data and up to 1.78 Msamples/s for 70-dimensional data. To validate the accuracy and performance of our algorithms we compare it with several common clustering techniques on several different applications. The experimental result shows that it outperforms other prior hardware accelerated clustering systems.

Tools for C/C++ based-hardware development have grown in popularity in recent years. However, the impact of these tools has been limited by their lack of support for integration with vendor IP, external memories, and communication peripherals. In this paper we introduce Tinker, an open-source Board Support Package generator for Altera's OpenCL Compiler. Board Support Packages define memory, communication, and IP ports for easy integration with high level synthesis cores. Tinker abstracts the low-level hardware details of hardware development when creating board support packages and greatly increases the flexibility of OpenCL development. Tinker currently generates custom memory architectures from user specifications. We use our tool to generate a variety of architectures and apply them to two application kernels.

Field Programmable Gate Array (FPGA) implementations of sorting algorithms have proven to be efficient, but existing implementations lack portability and maintainability because they are written in low-level hardware description languages that require substantial domain expertise to develop and maintain. To address this problem, we develop a framework that generates sorting architectures for different requirements (speed, area, power, etc.). Our framework provides ten highly optimized basic sorting architectures, easily composes basic architectures to generate hybrid sorting architectures, enables non-hardware experts to quickly design efficient hardware sorters, and facilitates the development of customized heterogeneous FPGA/CPU sorting systems. Experimental results show that our framework generates architectures that perform at least as well as existing RTL implementations for arrays smaller than 16K elements, and are comparable to RTL implementations for sorting larger arrays. We demonstrate a prototype of an end-to-end system using our sorting architectures for large arrays (16K-130K) on a heterogeneous FPGA/CPU system.

High-level synthesis tools allow programmers to use OpenCL to create FPGA designs. Unfortunately, these tools have a complex compilation process that can take several hours to synthesize a single design. This creates a significant barrier for design optimization since even experts typically need to test many designs due to the non-obvious interactions between the different optimizations. Thus, understanding the design space, and guiding the optimization process is a crucial requirement for enabling the widespread adoption of these high-level synthesis tools. However this requires a significant amount of design space data that is currently unavailable or difficult to generate. To solve this problem, we present an OpenCL FPGA benchmark suite. We outfitted each benchmark with a range of optimization parameters (or knobs), compiled over 8300 unique designs using the Altera OpenCL SDK, executed them on a Terasic DE5 board, and recorded their corresponding performance and utilization characteristics. We describe the resulting design spaces, and perform a statistical analysis of the optimization configurations which provides valuable architecture insights to FPGA developers. We make the benchmarks and results completely open-source to give opportunities for the community to perform additional analyses and provide a repository of well-documented designs for follow-on research.

Secure hardware design is a challenging task that goes far beyond ensuring functional correctness. Important design properties such as non-interference cannot be verified on functional circuit models due to the lack of essential information (e.g., sensitivity level) for reasoning about security. Hardware information flow tracking (IFT) techniques associate data objects in the hardware design with sensitivity labels for modeling security-related behaviors. They allow the designer to test and verify security properties related to confidentiality, integrity, and logical side channels. However, precisely accounting for each bit of information flow at the hardware level can be expensive. In this work, we focus on the precision of the IFT logic. The key idea is to selectively introduce only one sided errors (false positives); these provide a conservative and safe information flow response while reducing the complexity of the security logic. We investigate the effect of logic synthesis on the quality and complexity of hardware IFT and reveal how different logic synthesis optimizations affect the amount of false positives and design overheads of IFT logic. We propose novel techniques to further simplify the IFT logic while adding no, or only a minimum number of, false positives. Additionally, we provide a solution to quantitatively introduce false positives in order to accelerate information flow security verification. Experimental results using IWLS benchmarks show that our method can reduce complexity of GLIFT by 14.47% while adding 0.20% of false positives on average. By quantitatively introducing false positives, we can achieve up to a 55.72% speedup in verification time.

Nonnegative least squares (NNLS) optimization is an important algorithmic component of many problems in science and engineering, including image segmentation, spectral deconvolution, and reconstruction of compressively sensed data. Each of these areas can benefit from high performance implementations suitable for embedded applications. Unfortunately, the NNLS problem has no solution expressible in closed-form, and many popular algorithms are not amenable to compact and scalable hardware implementation. Classical iterative algorithms generally have a per-iteration computational cost with cubic growth, and interdependencies which limit parallel approaches. In this paper we develop two efficient hardware architectures. One is based on a novel algorithm we develop in this paper specifically to reduce FPGA area consumption while preserving performance. We implement our architectures on a very small FPGA and apply them to reconstruction of a compressively sensed signal showing residual error results competitive with traditional algorithms.

Cryptographic function implementations are known to leak information about private keys through timing information. By using statistical analysis of the variations in runtime required to encrypt different messages, an attacker can relatively easily determine the key with high probability. There are many mitigation techniques to combat these side channels; however, there are limited metrics available to quantify the effectiveness of these mitigation attacks. In this work, we employ information theoretic ideas to quantify the amount of leakage that can be extracted from runtime measurements and reveal the influence of individual key bits on the timing observations across a variety of hardware implementations. By studying different RSA hardware architectures (each with different performance optimizations and mitigation techniques), we determine the effectiveness of these information theoretic techniques against the success of attacks. Our experimental results show that mutual information is a promising metric to quantify timing-based information leakage and it also correlates to the attack-ability of a cryptographic implementation.

We present RIFFA 2.1, a reusable integration framework for Field-Programmable Gate Array (FPGA) accelerators. RIFFA provides communication and synchronization for FPGA accelerated applications using simple interfaces for hardware and software. Our goal is to expand the use of FPGAs as an acceleration platform by releasing, as open source, a framework that easily integrates software running on commodity CPUs with FPGA cores. RIFFA uses PCI Express (PCIe) links to connect FPGAs to a CPU’s system bus. RIFFA 2.1 supports FPGAs from Xilinx and Altera, Linux and Windows operating systems, and allows multiple FPGAs to connect to a single host PC system. It has software bindings for C/C++, Java, Python, and Matlab. Tests show that data transfers between hardware and software can reach 97% of the achievable PCIe link bandwidth.

As data centers are increasingly focused on energy efficiency, it becomes important to develop low power implementations of the various applications that run on them. Data compression plays a critical role in data centers to mitigate storage and communication costs. This work focuses on building a low power, high performance implementation for canonical Huffman encoding. We develop a number of different hardware and software implementations targeting Xilinx Zynq FPGA, ARM Cortex-A9, and Intel Core i7. Despite its sequential nature, we show that our hardware accelerated implementation is substantially more energy efficient than both the ARM and Intel Core i7 implementations. When compared to highly optimized software running on the ARM processor, our hardware accelerated implementation has approximately 15 times more throughput with 10% higher power usage, resulting in an 8X benefit in energy efficiency (measured in encodings/Watt). Additionally, our hardware accelerated implementation is up to 80% faster and over 230 times more energy efficient than a highly optimized Core i7 implementation.

Privacy and integrity are important security concerns. These concerns are addressed by controlling information flow, i.e., restricting how information can flow through a system. Most proposed systems that restrict information flow make the implicit assumption that the hardware used by the system is fully ``correct'' and that the hardware's instruction set accurately describes its behavior in all circumstances. The truth is more complicated: modern hardware designs defy complete verification; many aspects of the timing and ordering of events are left totally unspecified; and implementation bugs present themselves with surprising frequency. In this work we describe Sapper, a novel hardware description language for designing security-critical hardware components. Sapper seeks to address these problems by using static analysis at compile-time to automatically insert dynamic checks in the resulting hardware that provably enforce a given information flow policy at execution time. We present Sapper's design and formal semantics along with a proof sketch of its security. In addition, we have implemented a compiler for Sapper and used it to create a non-trivial secure embedded processor with many modern microarchitectural features. We empirically evaluate the resulting hardware's area and energy overhead and compare them with alternative designs.

Robust real time tracking of multiple targets is a requisite feature for many applications. Online boosting has become an effective approach for dealing with the variability in object appearance. This approach can adapt its classifier to changes in appearance at the cost of additional runtime computation. In this paper, we address the task of accelerating online boosting for multiple target tracking. We propose a FPGA hardware accelerated architecture to evaluate and train a boosted classifier in real time. A general purpose CPU based software-only implementation can track a single target at 17 frames per second (FPS). The FPGA accelerated design is capable of tracking a single target at 1160 FPS or 57 independent targets at 30 FPS. This represents a 68× speed up over software.

Robust real time tracking is a requirement for many emerging applications. Many of these applications must track objects even as their appearance changes. Training classifiers online has become an effective approach for dealing with variability in object appearance. Classifiers can learn and adapt to changes online at the cost of additional runtime computation. In this paper, we propose a FPGA accelerated design of an online boosting algorithm that uses multiple classifiers to track and recover objects in real time. Our algorithm uses a novel method for training and comparing pose-specific classifiers along with adaptive tracking classifiers. Our FPGA accelerated design is able to track at 60 frames per second while concurrently evaluating 11 classifiers. This represents a 30× speed up over a CPU based software implementation. It also demonstrates tracking accuracy at state of the art levels on a standard set of videos.

Testing and verifying wireless systems in a real world environments is a challenging but an important problem. This is particular true for the Joint Tactical Radio System (JTRS) where the modulation techniques are optimized towards environments that are difficult to reproduce (e.g., ship to plane, plane to satellite communications). Such cases necessitate a wireless channel emulator to facilitate testing in the laboratory as the protocols are being developed. Furthermore, the increasing complexity of communications protocols and highly variable network scenarios force the channel emulator to support an accurate and complicated channel model that can scale to handle a large number of radios that operate across a wide frequency spectrum. We developed a unique channel impairment emulator prototype to meet these requirements. It maximizes the scalability and performance, operating in a frequency range of 2 MHz to 2 GHz. Moreover, our emulator design accommodates radio operation that use unknown frequency hopping techniques, which is increasingly common in JTRS systems. This key feature to this system is a high throughput channel tracker module that handles high bandwidth intermediate frequency (IF) signals while providing the scalability to handle a large number of channels.

De novo assembly is a widely used methodology in bioinformatics. However, the conventional short-read based de novo assembly is incapable of reliably reconstructing the large-scale structures of human genomes. Recently, a novel optical label based technology has enabled reliable large-scale de novo assembly. Despite its advantage in large-scale genome analysis, this new technology requires a more computationally intensive alignment algorithm than its conventional counterpart. For example, the run-time of reconstructing a human genome is on the order of 10; 000 hours on a sequential CPU. Therefore, in order to practically apply this new technology in genome research, accelerated approaches are desirable. In this paper, we present three different accelerated approaches, multi-core CPU, GPU and FPGA. Against the sequential software baseline, our multi-core CPU design achieved a 8.4× speedup while the GPU and FPGA designs achieved 13.6× and 115× speedups respectively. We also reveal the insights of the design space exploration of this new assembly algorithm on these three different devices by comparing the results.

Embedding real-time 3D reconstruction of a scene from a low-cost depth sensor can improve the development of technologies in the domains of augmented reality, mobile robotics, and more. However, current implementations require a computer with a powerful GPU, which limits its prospective applications with low-power requirements. To implement low-power 3D reconstruction we embedded two prominent algorithms of 3D reconstruction (Iterative Closest Point and Volumetric Integration) on an Altera Stratix V FPGA by using the OpenCL language and the Altera OpenCL SDK. In this paper, we present our application and evaluation of the Altera tool in terms of performance, area, and programmability trade-offs. We have verified that OpenCL can be a viable method for developing FPGA applications by modifying an open-source version of the Microsoft KinectFusion project to run partially on a FPGA.

This paper describes a low cost system for tracking wildlife that is equipped with radio collars. Currently, researchers have to physically go into the field with a directional antenna to try to pinpoint the VHF (very high frequency) signal originating from a wildlife tracking collar. Depending on the terrain, it could take an entire day to locate a single animal. To vastly improve upon this traditional approach, the system proposed here utilizes a small fixed-wing aircraft drone with a simple radio on-board, flying an automated mission. Received signal strength is recorded, and used to create a heat map that shows the collar's position. A prototype of this system was built using off-the-shelf hardware and custom signal processing algorithms. Initial field tests confirm the systems capabilities and its promise for wildlife tracking.

Modern embedded computing systems such as medical devices, airplanes, and automobiles continue to dominate some of the most critical aspects of our lives. In such systems, the movement of information throughout a device must be tightly controlled to prevent violations of privacy or integrity. Unfortunately, bounding the flow of information can often present a significant challenge, as information can flow through channels that are difficult to detect, such as timing channels. As has been demonstrated by recent research in hardware security, information flow tracking techniques deployed at the hardware or gate level show promise at identifying these “timing flows” but provide no formal statements about this claim NOR mechanisms for separating out timing information from other types of flows. In this paper, we first prove that gate-level information flow tracking can in fact detect timing flows. In addition, we work to identify these timing flows separately from other flows by presenting a framework for identifying a different type of flow that we call functional flows. By using this framework to either confirm or rule out the existence of such flows, we leverage the previous work in hardware information flow tracking to effectively isolate timing flows. To show the effectiveness of this model, we demonstrate its usage on three practical examples: a shared bus (I2C), a cache in a MIPS-based processor, and an RSA encryption core, all of which were written in Verilog/VHDL and then simulated in a variety of scenarios. In each scenario, we demonstrate how our framework can be used to identify timing and functional flows and also analyze our model's overhead.

High-assurance systems found in safety-critical infrastructures are facing steadily increasing cyber threats. These critical systems require rigorous guarantees in information flow security to prevent confidential information from leaking to an unclassified domain and the root of trust from being violated by an untrusted party. To enforce bit-tight information flow control, gate-level information flow tracking (GLIFT) has recently been proposed to precisely measure and manage all digital information flows in the underlying hardware, including implicit flows through hardware-specific timing channels. However, existing work in this realm either restricts to two-level security labels or essentially targets two-input primitive gates and several simple multilevel security lattices. This article provides a general way to expand the GLIFT method for multilevel security. Specifically, it formalizes tracking logic for an arbitrary Boolean gate under finite security lattices, presents a precise tracking logic generation method for eliminating false positives in GLIFT logic created in a constructive manner, and illustrates application scenarios of GLIFT for enforcing multilevel information flow security. Experimental results show various trade-offs in precision and performance of GLIFT logic created using different methods. It also reveals the area and performance overheads that should be expected when expanding GLIFT for multilevel security.

This work identifies a new formal basis for hardware information flow security by providing a method to separate timing flows from other flows of information. By developing a framework for identifying these different classes of information flow at the gate-level, one can either confirm or rule out the existence of such flows in a provable manner. To demonstrate the effectiveness of our presented model, we discuss its usage on a practical example: a CPU cache in a MIPS processor written in Verilog HDL and simulated in a scenario which accurately models previous cache-timing attacks. We demonstrate how our framework can be used to isolate the timing channel used in these attacks.

We present RIFFA 2.0, a reusable integration framework for FPGA accelerators. RIFFA 2.0 provides communication and synchronization for FPGA accelerated applications using simple interfaces for hardware and software. Our goal is to expand the use of FPGAs as an acceleration platform by releasing, as open source, a framework that easily integrates software running on commodity CPUs with FPGA cores. RIFFA 2.0 uses PCIe to connect FPGAs to a CPU's system bus. RIFFA 2.0 extends the original RIFFA project by supporting more classes of Xilinx FPGAs, multiple FPGAs in a system, more PCIe link configurations, higher bandwidth, and Linux and Windows operating systems. This release also supports C/C++, Java, and Python bindings. Tests show that data transfers between hardware and software can saturate the PCIe link to achieve the highest bandwidth possible.

Imaging flow cytometry uses high-speed flows and a camera to capture morphological features of hundreds to thousands of cells per second. These morphological features can be useful to isolate sub-populations of cells for life science research and diagnostics. Our experimental setup utilizes a high speed 208×32 resolution CMOS camera, operating at over 140,000 frames per second (FPS). In each frame, the analysis routine detects the presence of an object, and performs morphology measurements. Real-time cell sorting requires a latency under 10 ms in addition to a throughput of 140,000 FPS. In this paper, we will describe GPU and FPGA accelerated implementations of the image analysis necessary for an automated cell sorting system. Our FPGA design results in a 38x speedup over software, providing 2,262 FPS with 11.9 ms of latency. Our GPU implementation shows a 22x speedup, supporting 1,318 FPS with 152 ms of latency.

A common type of triangulation-based active 3D scanner outputs sets of surface coordinates, called profiles, by extracting the salient features of 2D images formed from an object illuminated by a narrow plane of light. Because a conventional 2D image must be digitized and processed for each profile, current systems do not always provide adequate speed and resolution to meet application demands. To address this challenge, a special purpose image sensor is being developed. Using Compressive Sensing, this sensor will be able to digitize compressed measurements of highly structured images, such as those formed in active 3D scanning, at a rate that would represent the conventional equivalent of 50G pixels/second. It is a significant challenge to process such a high-speed data stream at rates approaching realtime. Therefore, we present a single-chip FPGA design for the extraction of surface profiles from a compressed image stream originating from a 1024 by 768 pixel array at a rate of 14K images per second.

As multicore processors find increasing adoption in domains such as aerospace and medical devices where failures have the potential to be catastrophic, strong performance isolation and security become first-class design constraints. When cores are used to run separate pieces of the system, strong time and space partitioning can help provide such guarantees. However, as the number of partitions or the asymmetry in partition bandwidth allocations grows, the additional latency incurred by time multiplexing the network can significantly impact performance.

Securing the supply chain of integrated circuits is of utmost importance to computer security. In addition to counterfeit microelectronics, the theft or malicious modification of designs in the foundry can result in catastrophic damage to critical systems and large projects. In this letter, we describe a 3-D architecture that splits a design into two separate tiers: one tier that contains critical security functions is manufactured in a trusted foundry; another tier is manufactured in an unsecured foundry. We argue that a split manufacturing approach to hardware trust based on 3-D integration is viable and provides several advantages over other approaches.

We present RIFFA, a reusable integration framework for FPGA accelerators. RIFFA provides communication and synchronization for FPGA accelerated software using a standard interface. Our goal is to expand the use of FPGAs as an acceleration platform by releasing, as open source, a no cost framework that easily integrates software on traditional CPUs with FPGA based IP cores, over PCIe, with minimal custom configuration. RIFFA requires no specialized hardware or fee licensed IP cores. It can be deployed on common Linux workstations with a PCIe bus and has been tested on two different Linux distributions using Xilinx FPGAs.

The testing, verification and evaluation of wireless systems is an important but challenging endeavor. The most realistic method to test a wireless system is a field deployment. Unfortunately, this is not only expensive but also time consuming. In this paper, we present the design and implementation of a digital wireless channel emulator, which connects directly to a number of radios, and mimics the wireless channels between them, across a range of scenarios, in real-time. We use high-level synthesis tools to design the emulator while performing design space exploration. We describe the optimizations and tradeoffs that were necessary to reach the target throughput and area requirements.

Real-time optical mapping technology is a technique that can be used in cardiac disease study and treatment technology development to obtain accurate and comprehensive electrical activity over the entire heart. It provides a dense spatial electro-physiology. Each pixel essentially plays the role of a probe on that location of the heart. However, the high throughput nature of the computation causes significant challenges in implementing a real-time optical mapping algorithm. This is exacerbated by high frame rate video for many medical applications (order of 1000 fps). Accelerating optical mapping technologies using multiple CPU cores yields modest improvements, but still only performs at 3.66 frames per second (fps). A highly tuned GPU implementation achieves 578 fps. A FPGA-only implementation is infeasible due to the resource requirements for processing intermediate data arrays generated by the algorithm. We present a FPGA-GPU-CPU architecture that is a real-time implementation of the optical mapping algorithm running at 1024 fps. This represents a 273× speed up over a multi-core CPU implementation.

High assurance systems require strict guarantees on information flow security and fault tolerance or else face catastrophic consequences. Recently, Gate Level Information Flow Tracking (GLIFT) has been proposed to monitor information flows at the level of Boolean logic. At this level, all flows are explicit which makes it possible to detect security violations, even those that occur due to difficult to detect timing channels. In this paper, we show that the encoding technique used in previous GLIFT generation methods includes redundant encoding states, which leads to large overheads in area, delay and verification time. We present a new encoding technique with fewer encoding states by leveraging an inherent property of GLIFT. By denoting don't-care input conditions to logic synthesis tools, smaller GLIFT logic for dynamic information flow tracking is obtained and shorter simulation time for static information flow security verification is achieved. Experimental results using the IWLS benchmarks show average reductions of 39.8%, 31.1% and 57.5% in area, delay and simulation time respectively. Furthermore, the new encoding technique enables the GLIFT tracking logic to function both as information flow tracking and redundant logic. As a result, information flow security and fault tolerance can be simultaneously enforced with the same logic.

Hardware-based side channels are known to expose hard-to-detect security holes enabling attackers to get a foothold into the system to perform malicious activities. Despite this fact, security is rarely accounted for in hardware design flows. As a result, security holes are often only identified after significant damage has been inflicted. Recently, gate level information flow tracking (GLIFT) has been proposed to verify information flow security at the level of Boolean gates. GLIFT is able to detect all logical flows including hardware specific timing channels, which is useful for ensuring properties related to confidentiality and integrity and can even provide real-time guarantees on system behavior. GLIFT can be integrated into the standard hardware design, testing and verification process to eliminate unintended information flows in the target design. However, generating GLIFT logic is a difficult problem due to its inherent complexity and the potential losses in precision. This paper provides a formal basis for deriving GLIFT logic which includes a proof on the NP-completeness of generating precise GLIFT logic and a formal analysis of the complexity and precision of various GLIFT logic generation algorithms. Experimental results using IWLS benchmarks provide a practical understanding of the computational complexity.

Flight control, banking, medical, and other high assurance systems have a strict requirement on correct operation. Fundamental to this is the enforcement of non-interference where particular subsystems should not affect one another. In an effort to help guarantee this policy, recent work has emerged with tracking information flows at the hardware level. This article uses a specific method known as gate-level information flow tracking (GLIFT) to provide a methodology for testing information flows in two common bus protocols, I2C and USB. We show that the protocols do elicit unintended information flows and provide a solution based on time division multiple access (TDMA) that provably isolates devices on the bus from these flows. This paper also discusses the overheads in area and simulation time incurred by this TDMA based solution.

Face recognition systems play a vital role in many applications including surveillance, biometrics and security. In this work, we present a complete real-time face recognition system consisting of a face detection, a recognition and a downsampling module using an FPGA. Our system provides an end-to-end solution for face recognition; it receives video input from a camera, detects the locations of the face(s) using the Viola-Jones algorithm, subsequently recognizes each face using the Eigenface algorithm, and outputs the results to a display. Experimental results show that our complete face recognition system operates at 45 frames per second on a Virtex-5 FPGA.

High assurance systems used in avionics, medical implants, and cryptographic devices often rely on a small trusted base of hardware and software to manage the rest of the system. Crafting the core of such a system in a way that achieves flexibility, security, and performance requires a careful balancing act. Simple static primitives with hard partitions of space and time are easier to analyze formally, but strict approaches to the problem at the hardware level have been extremely restrictive, failing to allow even the simplest of dynamic behaviors to be expressed.

Information flow tracking is an effective tool in computer security for detecting unintended information flows. However, software based information flow tracking implementations have drawbacks in preciseness and performance. As a result, researchers have begun to explore tracking information flow in hardware, and more specifically, understanding the interference of individual bits of information through logical functions. Such gate level information flow tracking (GLIFT) can track information flow in a system at the granularity of individual bits. However, the theoretical basis for GLIFT, which is essential to its adoption in real applications, has never been thoroughly studied. This paper provides fundamental analysis of GLIFT by introducing definitions, properties, and the imprecision problem with a commonly used shadow logic generation method. This paper also presents a solution to this imprecision problem and provides results that show this impreciseness can be tolerated for the benefit of lower area and delay.

There is an increasing trend toward application specific processing, particularly in embedded computing devices that have stringent performance requirements. Achieving the desired area and throughput constraints requires careful tuning of the underlying architecture and high-level design tools are gaining increasing acceptance to achieve this goal while decreasing the design time. Most existing tools employ a bottom-to-top methodology, which piece together functional units, interconnect, and control logic based on the given application; this tends to scale poorly. We developed a tool, simulate and eliminate (S&E), that is fundamentally different from the existing high-level design tools as it employs a top-to-bottom methodology. S&E provides automatic generation of a variety of general purpose processing cores with different parameterization options. Then, the provided application(s) are simulated on this general-purpose architecture and the unneeded functionality is eliminated resulting in application specific architecture. S&E generates completely synthesizable hardware description language for an input C and/or MATLAB code. S&E provides different design methods and parameterization options to enable the user to study area and performance tradeoffs over a large number of different architectures and find the optimum architecture for the desired objective.

Hardware resources are abundant; state-of-the-art processors have over one billion transistors. Yet for a variety of reasons, specialized hardware functions for high assurance processing are seldom (i.e., a couple of features per vendor over twenty years) integrated into these commodity processors, despite a small flurry of late (e.g., ARM TrustZone, Intel VT-x/VT-d and AMD-V/AMD-Vi, Intel TXT and AMD SVM, and Intel AES-NI). Furthermore, as chips increase in complexity, trustworthy processing of sensitive information can become increasingly difficult to achieve due to extensive on-chip resource sharing and the lack of corresponding protection mechanisms. In this paper, we introduce a method to enhance the security of commodity integrated circuits, using minor modifications, in conjunction with a separate integrated circuit that can provide monitoring, access control, and other useful security functions. We introduce a new architecture using a separate control plane, stacked using 3D integration, that allows for the function and economics of specialized security mechanisms, not available from a co-processor alone, to be integrated with the underlying commodity computing hardware. We first describe a general methodology to modify the host computation plane by attaching an optional control plane using 3-D integration. In a developed example we show how this approach can increase system trustworthiness, through mitigating the cache-based side channel problem by routing signals from the computation plane through a cache monitor in the 3-D control plane. We show that the overhead of our example application, in terms of area, delay and performance impact, is negligible.

Understanding the flow of information is an important aspect in computer security. There has been a recent move towards tracking information in hardware and understanding the flow of individual bits through Boolean functions. Such gate level information flow tracking (GLIFT) provides a precise understanding of all flows of information. This paper presents a theoretical analysis of GLIFT. It formalizes the problem, provides fundamental definitions and properties, introduces precise symbolic representations of the GLIFT logic for basic Boolean functions, and gives analytic and quantitative analysis of the GLIFT logic.

This paper presents a hardware architecture for increased performance of color classification. In our architecture, color classification, based on an AdaBoost algorithm, identifies a pixel as having the color of interest or not. We designed the proposed architecture using Verilog HDL and implemented the design in a Xilinx Virtex-5 FPGA. The architecture for color classification can have 598 times performance improvement over an equivalent software solution and 1.9 times performance improvement over the leading hardware color classifier.

Face detection is an important aspect for biometrics, video surveillance and human computer interaction. We present a multi-GPU implementation of the Viola-Jones face detection algorithm that meets the performance of the fastest known FPGA implementation. The GPU design offers far lower development costs, but the FPGA implementation consumes less power. We discuss the performance programming required to realize our design, and describe future research directions.

The emergence of smart cameras has been fueled by increasingly advanced computing platforms that are capable of performing a variety of real-time computer vision algorithms. Smart cameras provide the ability to understand their environment. Object detection and behavior classification play an important role in making such observations. This paper presents a high-performance FPGA implementation of a generalized parts-based object detection and classifier that runs with capability of 266 frames/sec. The detection algorithm is easily reconfigured by simply loading a new representation into on-board memory, i.e., the FPGA can detect and classify a newly specified object and behavior without any changes to the hardware implementation.

Matrix inversion is a common function found in many algorithms used in wireless communication systems. As FPGAs become an increasingly attractive platform for wireless communication, it is important to understand the trade-offs in designing a matrix inversion core on an FPGA. This article describes a matrix inversion core generator tool, GUSTO, that we developed to ease the design space exploration across different matrix inversion architectures. GUSTO is the first tool of its kind to provide automatic generation of a variety of general-purpose matrix inversion architectures with different parameterization options. GUSTO also provides an optimized application-specific architecture with an average of 59% area decrease and 3X throughput increase over its general-purpose architecture. The optimized architectures generated by GUSTO provide comparable results to published matrix inversion architecture implementations, but offer the advantage of providing the designer the ability to study the trade-offs between architectures with different design parameters.

Computing systems designed using reconfigurable hardware are increasingly composed using a number of different Intellectual Property (IP) cores, which are often provided by third-party vendors that may have different levels of trust. Unlike traditional software where hardware resources are mediated using an operating system, IP cores have fine-grain control over the underlying reconfigurable hardware. To address this problem, the embedded systems community requires novel security primitives that address the realities of modern reconfigurable hardware. In this work, we propose security primitives using ideas centered around the notion of “moats and drawbridges.” The primitives encompass four design properties: logical isolation, interconnect traceability, secure reconfigurable broadcast, and configuration scrubbing. Each of these is a fundamental operation with easily understood formal properties, yet they map cleanly and efficiently to a wide variety of reconfigurable devices. We carefully quantify the required overheads of the security techniques on modern FPGA architectures across a number of different applications.

This paper presents a parallelized architecture of multiple classifiers for face detection based on the Viola and Jones object detection method. This method makes use of the AdaBoost algorithm which identifies a sequence of Haar classifiers that indicate the presence of a face. We describe the hardware design techniques including image scaling, integral image generation, pipelined processing of classifiers, and parallel processing of multiple classifiers to accelerate the processing speed of the face detection system. Also we discuss the parallelized architecture which can be scalable for configurable device with variable resources. We implement the proposed architecture in Verilog HDL on a Xilinx Virtex-5 FPGA and show the parallelized architecture of multiple classifiers can have 3.3times performance gain over the architecture of a single classifier and an 84times performance gain over an equivalent software solution.

Digital signal processing applications often require the computation of linear systems. These computations can be considerably expensive and require optimizations for lower power consumption, higher throughput, and faster response time. Unfortunately, system designers do not have the necessary tools to take advantage of the wide flexibility in ways to evaluate these expressions. Therefore, we address the problem of efficiently computing a set of linear systems through a tool, Xquasher, that is developed by us to enable elimination of large common subexpression from expressions with an arbitrary number of terms. Xquasher provides a methodology for efficient computation of both single and multiple linear expressions. We also introduce the concept of power set encoding which helps us to provide an effective optimization method and achieves significant improvement over previously published work. Our tool provides optimized designs with 15% less area with the cost of 3% increase in delay by reducing number of additions on average by 45%.

This paper presents a hardware architecture for face detection based system on AdaBoost algorithm using Haar features. We describe the hardware design techniques including image scaling, integral image generation, pipelined processing as well as classifier, and parallel processing multiple classifiers to accelerate the processing speed of the face detection system. Also we discuss the optimization of the proposed architecture which can be scalable for configurable devices with variable resources. The proposed architecture for face detection has been designed using Verilog HDL and implemented in Xilinx Virtex-5 FPGA. Its performance has been measured and compared with an equivalent software implementation. We show about 35 times increase of system performance over the equivalent software implementation.

Small, dense underwater sensor networks have the potential to greatly improve undersea environmental and structural monitoring. However, few sensor nets exist because commercially available underwater acoustic modems are too costly and energy inefficient to be practical for this applications. Therefore, when designing an acoustic modem for sensor networks, the designer must optimize for low cost and low energy consumption at every level, from the analog electronics, to the signal processing scheme, to the hardware platform. In this paper we focus on the design choice of hardware platform: digital signal processors, microcontrollers, or reconfigurable hardware, to optimize for energy efficiency while keeping costs low. We implement one algorithm used in an acoustic modem design - Matching Pursuits for channel estimation - on all three platforms and perform a design space exploration to compare the timing, power and energy consumption of each implementation. We show that the reconfigurable hardware implementation can provide a maximum of 210X and 52X decrease in energy consumption over the microcontroller and DSP implementations respectively.

Matrix decomposition is required in various algorithms used in wireless communication applications. FPGAs strike a balance between ASICs and DSPs, as they have the programmability of software with performance capacity approaching that of a custom hardware implementation. However, FPGA architectures require designers to make a countless number of system, architectural and logic design decisions. By performing design space exploration, a designer can find the optimal device for a specific application, however very few tools exist which can accomplish this task. This paper presents automatic generation and optimization of decomposition methods using a core generator tool, GUSTO, that we developed to enable easy design space exploration with different parameterization options such as resource allocation, bit widths of the data, number of functional units and organization of controllers and interconnects. We present a detailed study of area and throughput tradeoffs of matrix decomposition architectures using different parameterizations.

Cooperative MIMO is a new technique that allows disjoint wireless communication nodes (e.g. wireless sensors) to form a virtual antenna array to increase bandwidth, reliability and/or transmission distance. It differs fundamentally from other MIMO communication since the signals received from each node have a relative timing and frequency offset due to the distributed nature of their transmitting antennas. Therefore, the receiver must estimate the timing and frequency for each transmitting node, in addition to the MIMO channel. In this paper, we design and implement a receiver for the cooperative MIMO problem using reconfigurable hardware. We discuss the computation required for each stage of the receiver and perform experimental study of the tradeoffs between area, power, performance and quality of results. The end result is an efficient, parameterizable, cooperative MIMO receiver implemented on several different state-of-the-art FPGAs devices.

Matrix inversion is an essential computation for various algorithms which are employed in multi-antenna wireless communication systems. FPGAs are ideal platforms for wireless communication; however, the need for vast amounts of customization throughout the design process of a matrix inversion core can overwhelm the designer. Decomposition methods provide the analytic simplicity and computational convenience necessary for computationally intensive matrix inversion. This paper presents automatic generation of different decomposition based matrix inversion architectures using a matrix inversion core generator tool, GUSTO with different parameterization options. We present automatic generation of a variety of general purpose matrix inversion architectures which have comparable results to published matrix inversion architecture implementations, but offer the advantage of providing the designer the ability to study the tradeoffs between architectures with different design parameters.

The extremely high cost of custom ASIC fabrication makes FPGAs an attractive alternative for deployment of custom hardware. Embedded systems based on reconfigurable hardware integrate many functions onto a single device. Since embedded designers often have no choice but to use soft IP cores obtained from third parties, the cores operate at different trust levels, resulting in mixed-trust designs. The goal of this project is to evaluate recently proposed security primitives for reconfigurable hardware by building a real embedded system with several cores on a single FPGA and implementing these primitives on the system. Overcoming the practical problems of integrating multiple cores together with security mechanisms will help us to develop realistic security-policy specifications that drive enforcement mechanisms on embedded systems.

Nanoscale technology promises dramatically increased device density, but also decreased reliability. With bit error rates projected to be as high as 10%, designing a usable nanoscale memory system poses a significant challenge. In particular, we need to bootstrap a sea of unreliable bits into contiguous address ranges which are preferably as large as 4K-byte virtual memory pages. We accomplish this bootstrapping through a combination of dynamic error correction codes within 32-bit blocks and a static defect map which tracks usability of these blocks. The key insight is that statically-determined defect locations can be much more powerful than dynamically correcting for unknown locations, but that defect maps are only practical at a coarse granularity. Using a combination of BCH error correction codes and a Bloom-Filter-based defect map, we achieve a memory efficiency of 60% and 13% for 4K-byte pages at 1% and 10% bit-error rates, respectively.

Blurring the line between software and hardware, reconfigurable devices strike a balance between the raw high speed of custom silicon and the post-fabrication flexibility of general-purpose processors. While this flexibility is a boon for embedded system developers, who can now rapidly prototype and deploy solutions with performance approaching custom designs, this results in a system development methodology where functionality is stitched together from a variety of "soft IP cores," often provided by multiple vendors with different levels of trust. Unlike traditional software where resources are managed by an operating system, soft IP cores necessarily have very fine grain control over the underlying hardware. To address this problem, the embedded systems community requires novel security primitives which address the realities of modern reconfigurable hardware. We propose an isolation primitive, moats and drawbridges, that are built around four design properties: logical isolation, interconnect traceability, secure reconfigurable broadcast, and configuration scrubbing. Each of these is a fundamental operation with easily understood formal properties, yet maps cleanly and efficiently to a wide variety of reconfigurable devices. We carefully quantify the required overheads on real FPGAs and demonstrate the utility of our methods by applying them to the practical problem of memory protection.

The authors consider a system architecture whereby orthogonal space time block codes (OSTBCs) are applied to a distributed set of wireless nodes. The utility offered is that by employing diversity we are able to greatly reduce the necessary link margin usually required to combat fast fading. A distributed set of wireless nodes are particularly well suited for this task as they are typically separated with significant inter-node distance thus having highly uncorrelated channels to a collector. In a typical application, a wireless sensor network (WSN) will have nodes that may wish to transmit data to a possibly mobile standoff collection point. In this paper, the authors discuss many practical aspects necessary for a real-world implementation including time and frequency offset estimation as well as channel tracking. As the waveform has been targeted to field programmable gate array (FPGA) hardware, we look at the relative implementation complexity of each signal processing element.

Operation scheduling (OS) is a fundamental problem in mapping an application to a computational device. It takes a behavioral application specification and produces a schedule to minimize either the completion time or the computing resources required to meet a given deadline. The OS problem is NP-hard; thus, effective heuristic methods are necessary to provide qualitative solutions. We present novel OS algorithms using the ant colony optimization approach for both timing-constrained scheduling (TCS) and resource-constrained scheduling (RCS) problems. The algorithms use a unique hybrid approach by combining the MAX-MIN ant system metaheuristic with traditional scheduling heuristics. We compiled a comprehensive testing benchmark set from real-world applications in order to verify the effectiveness and efficiency of our proposed algorithms. For TCS, our algorithm achieves better results compared with force-directed scheduling on almost all the testing cases with a maximum 19.5% reduction of the number of resources. For RCS, our algorithm outperforms a number of different list-scheduling heuristics with better stability and generates better results with up to 14.7% improvement. Our algorithms outperform the simulated annealing method for both scheduling problems in terms of quality, computing time, and stability

Design space exploration during high-level synthesis is often conducted through ad hoc probing of the solution space using some scheduling algorithm. This is not only time consuming but also very dependent on designer's experience. We propose a novel design exploration method that exploits the duality of time- and resource-constrained scheduling problems. Our exploration automatically constructs a time/area tradeoff curve in a fast, effective manner. It is a general approach and can be combined with any high-quality scheduling algorithm. In our work, we use the max-min ant colony optimization technique to solve both time- and resource-constrained scheduling problems. Our algorithm provides significant solution-quality savings (average 17.3% reduction of resource counts) with similar runtime compared to using force-directed scheduling exhaustively at every time step. It also scales well across a comprehensive benchmark suite constructed with classic and real-life samples.

Transistor leakage is poised to become the dominant source of power dissipation in digital systems, and reconfigurable devices are not immune to this problem. Modern FPGAs already have a significant amount of memory on the die, and with each generation the proportion of embedded memory to logic cells is growing. While assigning high Vth can limit the leakage power, embedded memory timing is critical to performance and will draw an increasingly significant amount of leakage current. However, unlike in many processor based systems, on-chip memory accesses are often fully deterministic and completely under the control of the scheduler. In this paper we explore a variety of techniques to battle the problem of leakage in FPGA embedded memories that range in complexity and effectiveness. Through the addition of sleep and drowsy modes, controlled by the scheduler, the amount of leakage power can be reduced by several orders of magnitude. We show how even very simple schemes offer large amounts of benefit, and that further reductions are possible through careful leakage-aware data placement.

Design space exploration during high level synthesis is often conducted through ad-hoc probing of the solution space using some scheduling algorithm. This is not only time consuming but also very dependent on designer's experience. We propose a novel design exploration method that exploits the duality between the time and resource constrained scheduling problems. Our exploration automatically constructs a high quality time/area tradeoff curve in a fast, effective manner. It uses the MAX-MIN ant colony optimization to solve both the time and resource constrained scheduling problems. We switch between the time and resource constrained algorithms to quickly traverse the design space. Compared to using force directed scheduling exhaustively at every time step, our algorithm provides a significant solution quality savings (average 17.3% reduction of resource counts) with similar run time on a comprehensive benchmark suite constructed with classic and real-life samples. Our algorithms scale well over different applications and problem sizes.

Carry save adder (CSA) trees are commonly used for high speed implementation of multi-operand additions. We present a method to reduce the number of the adders in CSA trees by extracting common three-term subexpressions. Our method can optimize multiple CSA trees involving any number of variables. This optimization has a significant impact on the total area of the synthesized circuits, as we show in our experiments. To the best of our knowledge, this is the only known method for eliminating common subexpressions in CSA structures. Since extracting common subexpressions can potentially increase delay, we also present a delay aware extraction algorithm that takes into account the different arrival times of the signals

High level synthesis transformations play a major part in shaping the properties of the final circuit. However, most optimizations are performed without much knowledge of the final circuit layout. In this paper, we present a physically aware design flow for mapping high level application specifications to a synthesizable register transfer level hardware description. We study the problem of optimizing the data communication of the variables in the application specification. Our algorithm uses floorplan information that guides the optimization. We develop a simple, yet effective, incremental floorplanner to handle the perturbations caused by the data communication optimization. We show that the proposed techniques can reduce the wirelength of the final design, while maintaining a legal floorplan with the same area as the initial floorplan.

The authors propose a novel defect-tolerant design methodology using Bloom filters for defect mapping for nanoscale computing devices. It is a general approach that can be used for any permanent defects incurred during the manufacturing process. The redundant design methodology does not rely on a voting strategy, thus it utilizes the device redundancy more effectively than existing approaches. Additionally, our method does not have false-positive in defect identification, i.e. it will not report a defective device as functional. Moreover, it is very space economic and can be programmed to fit different scales and characteristics of the underlying specific nanoscale devices used in the system

Distributed Arithmetic based methods are commonly used to implement Digital Signal Processing (DSP) functions such as filters and transforms. These techniques are very efficient for serial implementation of these functions, but occupy large area when fully parallel implementations for high sample rates are required.We present a method for implementing high speed Finite Impulse Response (FIR) filters using just registered adders and hardwired shifts. We extensively use common subexpression elimination to reduce the number of adders. Furthermore, we present a new technique to reduce the number of latches required in the design. We compare our designs with those produced by Xilinx CoregenTM and we observe up to 50% reduction in the number of slices for fully parallel implementations. We also observed an average performance improvement of 21.6%.

A cooperative MIMO network is considered with Ns sensors and a collector node with Mc antennas. In a practical implementation of this network, the sensor carriers have relative frequency offsets which must be estimated along with the MIMO channel. Generalized successive interference cancellation (GSIC) is proposed for this joint estimation problem. The primary operations in GSIC are correlation, FFT and cancellation. A reconfigurable hardware (FPGA) implementation of these GSIC primitives is described. A hybrid analysis/simulation for bit error rate (BER) is presented with results for GSIC using Alamouti and G4ccodes.

While the exact manufacturing process for nanoscale computing devices is uncertain, it is abundantly clear that future technology nodes will see an increase in defect rates. Therefore, it is of paramount importance to construct new architectures and design methodologies that can tolerate large numbers of defects. Defect maps are a necessity in the future design flows, and research on their practical construction is essential. In this work, we study the use of Bloom filters as a data structure for defect maps. We show that Bloom filters provide the right tradeoff between accuracy and space-efficiency. In particular, they can help simplify the nanosystem design flow by embedding defect information within the nanosystem delivered by the manufacturers. We develop a novel nanoscale memory design that uses this concept. It does not rely on a voting strategy, and utilizes the device redundancy more effectively than existing approaches.

We present a method for implementing high speed finite impulse response (FIR) filters using just registered adders and hardwired shifts. We extensively use a modified common subexpression elimination algorithm to reduce the number of adders. We target our optimizations to Xilinx Virtex II devices where we compare our implementations with those produced by Xilinx CoregenTM using Distributed Arithmetic. We observe up to 50% reduction in the number of slices and up to 75% reduction in the number of LUTs for fully parallel implementations. We also observed up to 50% reduction in the total dynamic power consumption of the filters. Our designs perform significantly faster than the MAC filters, which use embedded multipliers.

Polynomial expressions are frequently encountered in many application domains, particularly in signal processing and computer graphics. Conventional compiler techniques for redundancy elimination such as common subexpression elimination (CSE) are not suited for manipulating polynomial expressions, and designers often resort to hand optimizing these expressions. This paper leverages the algebraic techniques originally developed for multilevel logic synthesis to optimize polynomial expressions by factoring and eliminating common subexpressions. The proposed algorithm was tested on a set of benchmark polynomial expressions where savings of 26.7% in latency and 26.4% in energy consumption were observed for computing these expressions on the StrongARM SA1100 processor core. When these expressions were synthesized in custom hardware, average energy savings of 63.4% for minimum hardware constraints and 24.6% for medium hardware constraints over CSE were observed

Modern field programmable gate array (FPGA) architectures provide ample routing resources so that designs can be routed successfully. The routing architecture is designed to handle versatile connection configurations. However, providing such a great flexibility comes at a high cost in terms of area, delay, and power. The authors propose a new FPGA routing architecture that utilizes a mixture of hardwired and traditional flexible switches. The result is an about a 30% reduction in leakage power consumption, a 5% smaller area, and 20% shorter delays, which translates to a 25% increase in the clock frequency. Despite the increase in clock speeds, the overall power consumption is reduced.

This paper presents a novel technique to reduce the number of operations in Multiplierless implementations of linear DSP transforms, by iteratively eliminating two-term common subexpressions. Our method uses a polynomial transformation of linear systems that enables us to eliminate common subexpressions consisting of multiple variables. Our algorithm is fast and produces the least number of additions/subtractions compared to all known techniques. The synthesized examples show significant reductions in the area and power consumption.

Channel estimation and multiuser detection are enabling technologies for future generations of wireless applications. However, sophisticated algorithms are required for accurate channel estimation and multiuser detection, and real-time implementation of these algorithms is difficult. This paper presents architectural design methods for wireless channel estimation which can be leveraged to enable real-time multiuser detection. We redesign the matching pursuit (MP) channel estimation algorithm to reduce the complexity while maintaining the estimation accuracy. Furthermore, we develop a parameterized intellectual property (IP) core, which provides a hardware implementation of the MP algorithm. Experimental results demonstrate the effectiveness and ef- ficiency of the new algorithm and IP core for channel estimation. The implementation of our MP core on a modern, high performance reconfigurable system is about 216 times faster than running the algorithm on a state of the art microprocessor. The MP core possesses the speed required for performing true multiuser detection, enabling future generations of wireless communication applications.

Modern FPGA architectures provide ample routing resources so that designs can be routed successfully. The routing architecture is designed to handle versatile connection configurations. However, providing such great flexibility comes at a high cost in terms of area, delay and power. We propose a new FPGA routing architecture\footnoteThis work was supported in part by a grant from NSF under contract CAREER CCF-0347891 that utilizes a mixture of hardwired and traditional flexible switches. The result is 24% reduction in leakage power consumption, 7% smaller area and 24% shorter delays, which translates to 30% increase in clock frequency. Despite the increase in clock speeds, the overall power consumption is %, including dynamic power, reduced by 8%.

Instruction scheduling is a fundamental step for mapping an application to a computational device. It takes a behavioral application specification and produces a schedule for the instructions onto a collection of processing units. The objective is to minimize the completion time of the given application while effectively utilizing the computational resources. The instruction scheduling problem is NP-hard, thus effective heuristic methods are necessary to provide a qualitative scheduling solution. In this paper, we present a novel instruction scheduling algorithm using MAX-MIN Ant System Optimization approach. The algorithm utilizes a unique hybrid approach by combining the ant system meta-heuristic with list scheduling, where the local and global heuristics are dynamically adjusted to the input application in an iterative manner. Compared with force-directed scheduling and a number of different list scheduling heuristics, our algorithm generates better results over all the tested benchmarks with better stability. Furthermore, by solving the test samples optimally using ILP formulation, we show that our algorithm consistently achieves a near optimal solution.

If current technology scaling trends hold, leakage power dissipation soon becomes the dominant source of power consumption. Caches, due to the fact that they account for the largest fraction of on-chip transistors in most modern processors, are a primary candidate for attacking the leakage problem. While there has been a flurry of research in this area over the last several years, a major question remains unanswered. What is the total potential of existing architectural and circuit techniques to address this important design concern? In this paper, we explore the limits in which existing circuit and architecture technologies may address this growing problem. We find that by using perfect knowledge of the address trace to carefully apply sleep and drowsy modes, the total leakage power from the instruction cache may be reduced to mere 3.6% of the unoptimized case, and the total from the data cache reduced to only 0.9%. We also present a complete parameterized model to determine the optimal leakage savings while the implementation technology changes over time. We further suggest how such limits might be approached using a form of prefetching for low power.

Modern, high performance configurable architectures integrate on-chip, distributed block RAM modules to provide ample data storage. Synthesizing applications to these complex systems requires an effective and efficient approach to conduct data partitioning and storage assignment. In this paper, we present a data and iteration space partitioning solution that focuses on minimizing remote memory accesses or, equivalently, maximizing the local computation. Using the same code but different data partitionings, we can achieve faster clock frequencies, without increasing the number of cycles, by simply minimizing global memory accesses. Other optimization techniques like scalar replacement, prefetching and buffer insertion can further minimize remote accesses and lead to average 4.8/spl times/ speedup in overall runtime.

Efficient distributed algorithms are an important enabling technology for large-scale ad-hoc wireless sensor and communications networks. In this paper, optimal Bayesian data fusion under the assumption of linear Gaussian state and measurement models is presented. Within this framework, an efficient algorithm for distributed state estimation in ad-hoc networks is developed. Approximate algorithms are then developed for further improvements in network resource efficiency. These include a parameterizable tradeoff of improved communications efficiency for increased latency in the rate at which information propagates through the network. It is also shown that the algorithms are well-suited for use with non-linear measurements. Finally, for distributed node position estimation in a mobile ad-hoc network, simulation results show that accurate, efficient node localization is achieved

If current technology scaling trends hold, leakage power dissipation will soon become the dominant source of power consumption. Caches, because of the fact that they account for the largest fraction of on-chip transistors in most modern processors, are a primary candidate for attacking the leakage problem. While there has been a flurry of research in this area over the last several years, a major question remains unanswered---What is the total potential of existing architectural and circuit techniques to address this important design concern? In this paper, we explore the limits in which existing circuit and architecture technologies may address this growing problem. We first formally propose a parameterized model that can determine the optimal leakage savings based on the perfect knowledge of the address trace. By carefully applying the sleep and drowsy modes, we find that the total leakage power from the L1 instruction cache, data cache, and a unified L2 cache may be reduced to mere 3.6, 0.9, and 2.3%, respectively, of the unoptimized case. We further study how such a model can be extended to obtain the optimal leakage power savings for different cache configurations.

Complexities of applications implemented on embedded and programmable systems grow with the advances in capacities and capabilities of these systems. Mapping applications onto them manually is becoming a very tedious task. This draws attention to using high-level synthesis within design flows. Meanwhile, it is essential to provide a flexible formulation of optimization objectives as well as to perform efficient planning for various design objectives early on in the design flow. In this work, we address these issues in the context of data flow graph (DFG) scheduling, which is an essential element within the high-level synthesis flow. We present an algorithm that schedules a chain of operations with data dependencies among consecutive operations at a single step. This local problem is repeated to generate the schedule for the whole DFG. The local problem is formulated as a maximum weight noncrossing bipartite matching. We use a technique from the computational geometry domain to solve the matching problem. This technique provides a theoretical guarantee on the solution quality for scheduling a single chain of operations. Although still being local, this provides a relatively wider perspective on the global scheduling objectives. In our experiments we compared the latencies obtained using our algorithm with the optimal latencies given by the exact solution to the integer linear programming (ILP) formulation of the problem. In 9 out of 14 DFGs tested, our algorithm found the optimal solution, while generating latencies comparable to the optimal solution in the remaining five benchmarks. The formulation of the objective function in our algorithm provides flexibility to incorporate different optimization goals. We present examples of how to exploit the versatility of our algorithm with specific examples of objective functions and experimental results on the ability of our algorithm to capture these objectives efficiently in the final schedules.

Polynomial expressions are used to compute a wide variety of mathematical functions commonly found in signal processing and graphics applications, which provide good opportunities for optimization. However existing compiler techniques for reducing code complexity such as common subexpression elimination and value numbering are targeted towards general purpose applications and are unable to fully optimize these expressions. This work presents algorithms to reduce the number of operations to compute a set of polynomial expression by factoring and eliminating common subexpressions. These algorithms are based on the algebraic techniques for multi-level logic synthesis. Experimental results on a set of benchmark applications with polynomial expressions showed an average of 42.5% reduction in the number of multiplications and 39.6% reduction in the number of clock cycles for computation of these expressions on the ARM processor core, compared to common subexpression elimination.

In the past few years, gate duplication has been studied as a strategy for cutset minimization in partitioning problems. This paper addresses the problem of delay optimization by gate duplication. We present an algorithm to solve the gate duplication problem. It traverses the network from primary outputs(PO) to primary inputs(PI) in topologically sorted order evaluating tuples at the input pins of gates. The tuple's first component corresponds to the input pin required time if that gate is not duplicated. The second component corresponds to the input pin required time if that gate were duplicated. After tuple evaluation the algorithm traverses the network from PI to PO in topologically sorted order, deciding the gates to be duplicated. The last and final traversal is again from PO to PI, in which the gates are physically duplicated. Our algorithm uses the dynamic programming structure. We report delay improvements over other optimization methodologies. Gate duplication, along with other optimization strategies, can be used for meeting the stringent delay constraints in today's ultra complex designs.

Widespread adoption of reconfigurable devices requires system level synthesis techniques to take an application written in a high level language and map it to the reconfigurable device. This paper describes methods for synthesizing the internal representation of a compiler into a hardware description language in order to program reconfigurable hardware devices. We demonstrate the usefulness of static single assignment (SSA) in reducing the amount of data communication in the hardware. However, the placement of Φ-nodes by current SSA algorithms is not optimal in terms of minimizing data communication. We propose a new algorithm which optimally places Φ-nodes, further decreasing area and communication latency. Our algorithm reduces the data communication (measured as total edge weight in a control data flow graph) by as much as 20% for some applications as compared to the best-known SSA algorithm - the pruned algorithm. We also describe future modifications to our model that should increase the effectiveness of our methods.

The global routing problem decomposes the large, complex routing problem into a set of more manageable subproblems. The high correlation between the output of the global router and the detailed router enables the designer to efficiently use the global route to refine the design quickly before running the full detailed route. Hence, routability of the global routing solution is the key factor. The routability of the circuit depends on the congestion of the routing. In this paper, we study Steiner trees in terms of routability. We introduce the notion of flexibility, a geometric property associated with Steiner trees. We show that the flexibility of a Steiner tree is related to its routability. The main contribution of this paper is an algorithm which takes a stable Steiner tree as an input and maps it to a more flexible Steiner tree. Any existing Steiner tree algorithm can be used for the initial construction of the Steiner tree. Experiments with a global router on a subset of nets show that routing congestion is improved by approximately 20% locally throughout the region where those nets are routed.

This paper presents a novel method to reduce routing congestion during placement stage. The proposed approach is used as a post-processing step in placement. Congestion reduction is based on local improvement on the existing layout. However, the approach has a global view of the congestion over the entire design. It uses integer linear programming (ILP) to formulate the problem of conflicts between multiple congested regions, and performs local improvement according to the solution of the ILP problem. The approximation algorithm of the formulated ILP problem is studied and good approximation bounds are given and proved. Experiments show that the proposed approach can effectively alleviate the congestion of global routing results. The low computational complexity of the proposed approach indicates its scalability on large designs.

The increasing demand for complex and specialized embedded hardware must be met by processors which are optimized for performance, yet are also extremely flexible. In our work, we explore the tradeoff between flexibility and performance in the domain of reconfigurable processor design. Specifically, we seek to identify regularly occurring, computation-heavy patterns in an application or set of applications. These patterns become candidates for hard-logic implementation, potentially embedded in the flexible reconfigurable fabric as special optimized instructions. In this work we present an extension to previous work in instruction generation: an algorithm that identifies parallel templates. We discuss the advantages of parallel templates, and prove the correctness of our algorithm. We introduce an All-Pairs Common Slack Graph (APCSG) as an effective tool for parallel template generation. Finally, we demonstrate the effectiveness of our algorithm on several applicationse dataflow graphs, reducing latency on average by 51.98%, without unreasonably increasing chip area.

Deep submicron effects, along with increasing interconnect densities, have increased the complexity of the routing problem. Whereas previously we could focus on minimizing wirelength, we must now consider a variety of objectives during routing. For example, an increased amount of timing restrictions means that we must minimize interconnect delay. But, interconnect delay is no longer simply related to wirelength. Coupling capacitance has become a dominant component of delay due to the shrinking of device sizes. Regardless, the most important objective is producing a routable circuit. Unfortunately, this often conflicts with minimizing interconnect delay as minimum delay routes create congested areas, for which an exact routing cannot be realized without violating design rules. In this work, we use the concept of pattern routing to develop algorithms that guide the router to a solution that minimizes interconnect delay - by considering both coupling and wirelength-without damaging the routability of the circuit. The paper is divided into two parts. The first part demonstrates that pattern routing can be used without affecting the routability of the circuit. We propose two schemes to choose a set of nets to pattern route. Using these schemes, we show that the routability is not hindered. The second part builds on the previous part by presenting a framework for coupling reduction using pattern routing. We develop theory and algorithms relating pattern routing and coupling. Additionally, we give suggestions on how to extend our theory and use our algorithms for both global and detailed routing.

Congestion is one of the fundamental issues in very large scale integration physical design. In this paper, we propose two congestion-estimation approaches for early placement stages. First, we theoretically analyze the peak-congestion value of the design and experimentally validate the estimation approach. Second, we estimate regional congestion at the early stages of top-down placement. This is done by combining the wire-length distribution model and interregion wire estimation. Both approaches are based on the well-known Rent's rule, which is previously used for wirelength estimation. This is the first attempt to predict congestion using Rent's rule. The estimation results are compared with the layout after placement and global routing. Experiments on large industry circuits show that the early congestion estimation based on Rent's rule is a promising approach.

Future computing systems need to balance flexibility, specialization, and performance in order to meet market demands and the computing power required by new applications. Instruction generation is a vital component for determining these trade-offs. In this work, we present theory and an algorithm for instruction generation. The algorithm profiles a dataflow graph and iteratively contracts edges to create the templates. We discuss how to target the algorithm toward the novel problem of instruction generation for hybrid reconfigurable systems. In particular, we target the Strategically Programmable System, which embeds complex computational units such as ALUs, IP blocks, and so on into a configurable fabric. We argue that an essential compilation step for these systems is instruction generation, as it is needed to specify the functionality of the embedded computational units. In addition, instruction generation can be used to create soft reconfigurable macros---tightly sequenced prespecified operations placed in the reconfigurable fabric.

This paper presents the concept of flexibility -- a geometric property associated with Steiner trees. Flexibility is related to the routability of the Steiner tree. We present an optimal algorithm which takes a Steiner tree and outputs a more flexible Steiner tree. Our experiments show that a net with a flexible Steiner tree increases its routability. Experiments with a global router show that congestion is improved by approximately 20\%.

We present an algorithm for simultaneous template generation and matching. The algorithm profiles the graph and iteratively contracts edges to create the templates. The algorithm is general and can be applied to any type of graph, including directed graphs and hypergraphs. We discuss how to target the algorithm towards the novel problem of instruction generation and selection for a hybrid (re)configurable systems. In particular, we target the strategically programmable system, which embeds complex computational units like ALUs, IP blocks, etc. into a configurable fabric. We argue that an essential compilation step for these systems is instruction generation, as it is needed to specify the functionality of the embedded computational units. Additionally, instruction generation can be used to create soft macros tightly sequenced pre-specified operations placed in the configurable fabric.

Emerging reconfigurable systems attain high performance with embedded optimized cores. For mapping designs on such special architectures, synthesis tools, that are aware of the special capabilities of the underlying architecture are necessary. We propose an algorithm to perform simultaneous scheduling and binding, targeting embedded reconfigurable systems. The algorithm differs from traditional scheduling methods in its capability of efficiently utilizing embedded blocks within the reconfigurable system. The algorithm can be used to implement several other scheduling techniques, such as ASAP, ALAP, and list scheduling. Hence we refer to it as a super-scheduler. The algorithm is a path-based scheduling algorithm. At each step, an individual path from the input DFG is scheduled. The experiments with several DFGs extracted from MediaBench suite indicate promising results. The scheduler presents the capability to perform the trade-off between maximally utilizing the high-performance embedded blocks and exploiting parallelism in the schedule.

This paper presents a novel method to reduce routing congestion during placement stage. The proposed approach is used as a post-processing step in placement. Congestion reduction is based on local improvement on the existing layout. However, the approach has a global view of the congestion over the entire design. It uses integer linear programming (ILP) to formulate the conflicts between multiple congested regions, and performs local improvement according to the solution of ILP. Experiments show that the proposed approach can effectively reduce the total overflow of global routing result. The short running time of the algorithm indicates good scalability on large designs.

In this wrok, we develop methods to reduce interconnect delay and noise caused by coupling. First, we explain the Coupling-Free Routing (CFR) problem. CFR takes a set of nets and tries to find a one-bend couple-free routing for a subset of nets. A routed net must not couple with any other routed net. We define coupling as a boolean variable which is true when the coupling of two nets is greater than some threshold. Any pair-wise coupling definition can be used. We argue that this problem is useful in both global and detailed routing

We will review a few key algorithmic and analysis concepts with application to physical design problems. We argue that design and detailed analysis of algorithms is of fundamental importance in developing better physical design tools and to cope with the complexity of present-day designs.

Congestion is one of the fundamental issues in VLSI physical design. In this paper, we propose two congestion estimation approaches for early placement stages. First, we theoretically analyze the peak congestion value of the design and experimentally validate the estimation approach. Second, we estimate regional congestion in the early top-down placement. This is done by combining the wirelength distribution model and inter-region wire estimation. Both approaches are based on the well known Rent's rule, which is previously used for wirelength estimation. This is the first attempt to predict congestion using Rent's rule. The estimation results are compared with the layout after placement and global routing. Experiments on large industry circuits show that the early congestion estimation based on Rent's rule is a promising approach.

In this paper, we show that both the global and local gate duplication problems for delay optimization are NP-complete under certain delay models.

Improvements in FPGA technology have resulted in the introduction of reconfigurable computing machines, where the hardware adapts itself to the running application to gain speedup. We present a top-down compilation method, under development, for such systems. We compile a C program into hierarchical VHDL source files, and annotate them with the placement information of the hardware modules to be configured on the FPGA. Static scheduling combined with a fast, two-stage placement core reduces the compilation time of large programs to minutes.

Predictable routing is the concept of using prespecified patterns to route a net. By doing this, we allow an more accurate prediction mechanism for metrics such as congestion and wirelength earlier in the design flow. Additionally, we can better plan the routes, insert buffers and perform wire sizing earlier. With comparable routing quality we show that we can predictably route up to 30% of a selected subset of nets. Also, we introduce methods for finding a group of nets which can be predictably routed.

Delay optimization is a fundamental goal in logic synthesis. This paper presents gate duplication as a strategy for performance optimization. Many timing optimization strategies have been proposed over the past few years. In the past few years, the research community has looked at gate duplication extensively as a method of reducing the cut-set of partitions. Strategies of logic duplication for cut-set minimization have been suggested. The strength of gate duplication as a cut-set minimizing strategy has been demonstrated. However applicability of this strategy in reducing the circuit delay has not been studied in detail. In this paper we prove the problem of partitioning a set of fanouts between a gate and it's replica (both gates have the same fanins) such that the required time constraint at the input pin is met, to be NP-Complete. Hence even the local optimization by gate duplication problem (formally defined later) is also NP-Complete. We then present an algorithm for gate duplication which is based on the dynamic programming approach. Since the problem of partitioning a set of fanouts between a node and it's replica is NP-Complete, we use a heuristic for making this decision which is optimal under specific conditions. We report delay improvements as high as 8% over highly optimized results generated by SIS. The rest of this paper is organized as follows. Section 2 deals with the delay model and provides basic definitions. Section 3 reviews the complexity of the global gate duplication problem. Section 4 presents the proof of NP-Completeness for the local gate duplication problem. Section 5 describes a heuristic for gate duplication in detail, followed by results in Section 6. This is followed by some observations and conclusion in Section 7.