We propose machine learning (ML) power, the first ML-based framework that: 1) accelerates end-to-end RTL power estimation by addressing both its key bottlenecks—RTL simulation and power-model evaluation—and 2) extends ML-based power models to system-on-chips (SoCs) with configurable intellectual property (IP) blocks. ML-Power builds models that predict power versus time traces of each SoC block using a very small subset of internal signals called power proxies. The framework is composed of three components: ML-based power proxy activity estimation (PACE), exploiting spatio-temporal correlations for power proxy selection and ML-based power model evaluation (SCOPE), and representative configuration selection using active learning (RECAL). PACE trains a sequence-to-sequence (seq2seq) ML model to translate a transaction-level execution trace into a cycle-level trace of the power proxy signals, allowing much faster simulation models to be used in place of RTL simulation. SCOPE selects power proxies and trains ML-based power models for each block within the SoC. RECAL enables ML-Power to handle SoCs with configurable intellectual property (IP) blocks by using active learning to select a small subset of representative configurations, which are then used to train a unified power model that generalizes across the entire design space. We evaluate ML-Power on an ARM SSE-300 SoC and two RISC-V-based SoCs. Compared to prior state-of-the-art ML-based power estimation frameworks, SCOPE trains power models$\sim 65\times $faster, picks 40% fewer proxies, and achieves 2% lower estimation error. For the two RISC-V SoCs with configurable IP blocks, ML-Power achieves less than 10% error in per-cycle power across the entire design space using only 10–14 training configurations. ML-Power also achieves$\sim 300\times $inference-time speedup over a commercial RTL power estimation tool with less than 7% error in per-cycle power estimates.

The design space for edge AI hardware supporting large language model (LLM) inference and continual learning is underexplored. We present 3D-CIMlet, a thermal-aware modeling and co-design framework for 2.5D/3D edge-LLM engines exploiting heterogeneous computing-in-memory (CIM) chiplets, adaptable for both inference and continual learning. We develop memory-reliability-aware chiplet mapping strategies for a case study of edge LLM system integrating RRAM, capacitor-less eDRAM, and hybrid chiplets in mixed technology nodes. Compared to 2 D baselines, $2.5 \mathrm{D} / 3 \mathrm{D}$ designs improve energy efficiency by up to 9.3 x and 12 x, with up to 90.2% and 92.5% energy-delay product (EDP) reduction respectively, on edge LLM continual learning.

Accurate power estimation early in the design cycle is crucial for the design of power-efficient System-on-Chips (SoCs). Power estimation has been researched at various levels of abstraction, with a well-known trade-off between efficiency and accuracy. Recent work has shown great promise for machine learning (ML) techniques to advance the state-of-the-art in power estimation. We propose ML-Power, the first ML-based framework that can address both key bottlenecks involved in power estimation, viz. simulation and power model evaluation. ML-Power builds and uses models that estimate power in each SoC block using a very small subset of internal signals, known as power proxies. ML-Power consists of two key components, PACE and SCOPE. PACE trains a sequence-to-sequence ML model to translate a transaction-level execution trace into a cycle-level trace of the power proxy signals, allowing much faster simulation models to be used in place of RTL simulation. SCOPE selects power proxies and trains ML-based power models for blocks (IPs) within the SoC. SCOPE improves upon prior work in ML-based power modeling by exploiting spatio-temporal correlations among SoC blocks to minimize the number of power proxies while also improving estimation accuracy. We evaluate ML-Power for an ARM SSE-300 SoC and two RISC-V based SoCs. Compared to prior state-of-the-art ML-based power estimation frameworks, SCOPE trains power models ∼65× faster, picks 40% fewer proxies, and achieves 2% lower estimation error. ML-Power also achieves ∼300× speedup over a commercial RTL power estimation tool with less than 7% error in per-cycle power estimates.

Event cameras have emerged as a promising sensing modality for autonomous navigation systems, owing to their high temporal resolution, high dynamic range and negligible motion blur. To achieve the best performance across a range of vision tasks using the asynchronous temporal event streams from such sensors, recent research has shown that a mix of Artificial Neural Networks (ANNs), Spiking Neural Networks (SNNs), as well as hybrid SNN-ANN algorithms are desirable. However, we observe that such workloads achieve poor utilization and performance on commodity edge platforms which feature heterogeneous processing elements such as CPUs, GPUs and neural accelerators. This is due to the mismatch between the irregular nature of event streams and diverse characteristics of algorithms on the one hand and the underlying hardware platform on the other. We propose Ev-Edge, a framework that contains three key optimizations to boost the performance of event-based vision algorithms on edge platforms: (1) An Event2Sparse Frame converter directly transforms raw event streams into sparse frames, enabling the use of sparse libraries with minimal encoding overheads (2) A Dynamic Sparse Frame Aggregator merges sparse frames at runtime by trading off the temporal granularity of events and computational demand, thereby improving hardware utilization, and (3) A Network Mapper maps concurrently executing tasks to different processing elements while also selecting layer precision while considering both compute and communication overheads. On several state-of-art networks for a range of autonomous navigation tasks, Ev-Edge achieves 1.28x-2.05x improvements in latency and 1.23x-2.15x in energy over an all-GPU implementation on the NVIDIA Jetson Xavier AGX platform for single-task execution scenarios. Ev-Edge also achieves 1.43x-1.81x latency improvements over round-robin scheduling methods in multi-task execution scenarios.

Conditional neural networks (NNs) are networks in which the computations performed vary based on the input. Many NNs of interest (such as autoregressive transformers for sequence generation tasks) are inherently conditional since they process variable-length inputs or produce variable-length outputs. In addition, popular NN optimization techniques, such as early exit, result in the computational footprint varying across inputs. Computational irregularity across inputs presents a challenge to batching, a technique widely used to improve hardware utilization and throughput during NN inference. To address this challenge, we propose BatchCond, an optimized batching framework for Conditional NNs that consists of two key steps: 1) computational similarity-driven batching (SimBatch) and 2) adaptive batch reorganization (ABR). SimBatch utilizes a lightweight DNN predictor to create batches of inputs that are more likely to share similar computational patterns, thereby reducing computational irregularity. Further, ABR addresses residual irregularity by dynamically splitting batches into computationally similar sub-batches in a hardware-aware manner. Our experiments demonstrate that BatchCond improves the overall throughput of batched inference by up to$6.6\times $(mean of$2.5\times $) across a suite of diverse Conditional NNs, including early-exit networks, dynamic slimmable networks, and autoregressive transformers. Code is available athttps://github.com/surya00060/BatchCond.

The last decade has seen the emergence of Deep Neural Networks (DNNs) as the de facto algorithm for various computer vision applications. In intelligent edge devices, sensor data streams acquired by the device are processed by a DNN application running on either the edge device itself or in the cloud. However, “edge-only” and “cloud-only” execution of State-of-the-Art DNNs may not meet an application’s latency requirements due to the limited compute, memory, and energy resources in edge devices, dynamically varying bandwidth of edge-cloud connectivity networks, and temporal variations in the computational load of cloud servers. This work investigates distributed (partitioned) inference across edge devices (mobile/end device) and cloud servers to minimize end-to-end DNN inference latency. We study the impact of temporally varying operating conditions and the underlying compute and communication architecture on the decision of whether to run the inference solely on the edge, entirely in the cloud, or by partitioning the DNN model execution among the two. Leveraging the insights gained from this study and the wide variation in the capabilities of various edge platforms that run DNN inference, we propose PArtNNer , a platform-agnostic adaptive DNN partitioning algorithm that finds the optimal partitioning point in DNNs to minimize inference latency. PArtNNer can adapt to dynamic variations in communication bandwidth and cloud server load without requiring pre-characterization of underlying platforms. Experimental results for six image classification and object detection DNNs on a set of five commercial off-the-shelf compute platforms and three communication standards indicate that PArtNNer results in 10.2× and 3.2× (on average) and up to 21.1× and 6.7× improvements in end-to-end inference latency compared to execution of the DNN entirely on the edge device or entirely on a cloud server, respectively. Compared to pre-characterization-based partitioning approaches, PArtNNer converges to the optimal partitioning point 17.6× faster.

Transformers have achieved great success in a wide variety of natural language processing (NLP) tasks due to the self-attention mechanism, which assigns an importance score for every word relative to other words in a sequence. However, these models are very large, often reaching hundreds of billions of parameters, and therefore require a large number of dynamic random access memory (DRAM) accesses. Hence, traditional deep neural network (DNN) accelerators such as graphical processing units (GPUs) and tensor processing units (TPUs) face limitations in processing Transformers efficiently. In-memory accelerators based on nonvolatile memory (NVM) promise to be an effective solution to this challenge, since they provide high storage density while performing massively parallel matrix–vector multiplications (MVMs) within memory arrays. However, attention score computations, which are frequently used in Transformers unlike convolutional neural networks (CNNs) and recurrent neural network (RNNs), require MVMs where both the operands change dynamically for each input. As a result, conventional NVM-based accelerators incur high write latency and write energy when used for Transformers and further suffer from the low endurance of most NVM technologies. To address these challenges, we present X-Former, a hybrid in-memory hardware accelerator that consists of both NVM and CMOS processing elements to execute transformer workloads efficiently. To improve the hardware utilization of X-Former, we also propose a sequence blocking dataflow, which overlaps the computations of the two processing elements and reduces execution time. Across several benchmarks, we show that X-Former achieves up to$69.8\times $and$13\times $improvements in latency and energy over a NVIDIA GeForce GTX 1060 GPU and up to$24.1\times $and$7.95\times $improvements in latency and energy over a state-of-the-art in-memory NVM accelerator.

Spiking Neural Networks are a class of artificial neural networks that process information as discrete spikes. The time and energy consumed in SNN implementations is strongly dependent on the number of spikes processed. We explore this sensitivity from an adversarial perspective and propose SpikeAttack, a completely new class of attacks on SNNs. SpikeAttack impacts the efficiency of SNNs via imperceptible perturbations that increase the overall spiking activity of the network, leading to increased time and energy consumption. Across four SNN benchmarks, SpikeAttackresults in 1.7x-2.5X increase in spike activity, leading to increases of 1.6x-2.3x and 1.4x-2.2x in latency and energy consumption, respectively.

Ensembles improve the accuracy and robustness of Graph Neural Networks (GNNs), but suffer from high latency and storage requirements. To address this challenge, we propose GNN Ensembles through Error Node Isolation (GEENI). The key concept in GEENI is to identify nodes that are likely to be incorrectly classified (error nodes) and suppress their outgoing messages, leading to simultaneous accuracy and efficiency improvements. GEENI also enables aggressive approximations of the constituent models in the ensemble while maintaining accuracy. To improve the efficacy of GEENI, we propose techniques for diverse ensemble creation and accurate error node identification. Our experiments establish that GEENI models are simultaneously up to 4.6% (3.8%) more accurate and up to 2.8X (5.7X) faster compared to non-ensemble (conventional ensemble) GNN models.

Remarkable advances in machine learning and artificial intelligence have been made in various domains, achieving near-human performance in a plethora of cognitive tasks including vision, speech and natural language processing. However, implementations of such cognitive algorithms in conventional "von-Neumann" architectures are orders of magnitude more area and power expensive than the biological brain. Therefore, it is imperative to search for fundamentally new approaches so that the improvement in computing performance and efficiency can keep up with the exponential growth of the AI computational demand. In this article, we present a cross-layer approach to the exploration of new paradigms in cognitive computing. This effort spans new learning algorithms inspired from biological information processing principles, network architectures best suited for such algorithms, and neuromorphic hardware substrates such as computing-in-memory fabrics in order to build intelligent machines that can achieve orders of improvement in energy efficiency at cognitive processing. We argue that such cross-layer innovations in cognitive computing are well-poised to enable a new wave of autonomous intelligence across the computing spectrum, from resource-constrained IoT devices to the cloud.

Approximate computing (AxC) has been long accepted as a design alternative for efficient system implementation at the cost of relaxed accuracy requirements. Despite the AxC research activities in various application domains, AxC thrived the past decade when it was applied in Machine Learning (ML). The by definition approximate notion of ML models but also the increased computational overheads associated with ML applications-that were effectively mitigated by corresponding approximations-led to a perfect matching and a fruitful synergy. AxC for AI/ML has transcended beyond academic prototypes. In this work, we enlighten the synergistic nature of AxC and ML and elucidate the impact of AxC in designing efficient ML systems. To that end, we present an overview and taxonomy of AxC for ML and use two descriptive application scenarios to demonstrate how AxC boosts the efficiency of ML systems.

Compression techniques such as quantization and pruning are indispensable for deploying state-of-the-art Deep Neural Networks (DNNs) on resource-constrained edge devices. Quantization is widely used in practice - many commercial platforms already support 8-bits, with recent trends towards ultra-low precision (4-bits and below). Pruning, which increases network sparsity (incidence of zero-valued weights), enables compression by storing only the nonzero weights and their indices. Unfortunately, the compression benefits of pruning deteriorate or even vanish in ultra-low precision DNNs. This is due to (i) the unfavorable tradeoff between the number of bits needed to store a weight (which reduces with lower precision) and the number of bits needed to encode an index (which remains unchanged), and (ii) the lower sparsity levels that are achievable at lower precisions.

Transformers have greatly advanced the state-of-the-art in Natural Language Processing (NLP) in recent years, but present very large computation and storage requirements. We observe that the design process of Transformers (pre-train a foundation model on a large dataset in a self-supervised manner, and subsequently fine-tune it for different downstream tasks) leads to task-specific models that are highly over-parameterized, adversely impacting both accuracy and inference efficiency. We propose AxFormer, a systematic framework that applies accuracy-driven approximations to create optimized transformer models for a given downstream task. AxFormer combines two key optimizations — accuracy-driven pruning and selective hard attention. Accuracy-driven pruning identifies and removes parts of the fine-tuned transformer that hinder performance on the given downstream task. Sparse hard-attention optimizes attention blocks in selected layers by eliminating irrelevant word aggregations, thereby helping the model focus only on the relevant parts of the input. In effect, AxFormer leads to models that are more accurate, while also being faster and smaller. Our experiments on GLUE and SQUAD tasks show that AxFormer models are up to 4.5% more accurate, while also being up to 2.5× faster and up to 3.2× smaller than conventional fine-tuned models. In addition, we demonstrate that AxFormer can be combined with previous efforts such as distillation or quantization to achieve further efficiency gains. Code is available at https://github.com/amrnag/Specialized-Transformers.

Piezoelectric FETs (PeFETs) are a promising class of ferroelectric devices that use the piezoelectric effect to modulate strain in the channel. They present several desirable properties for on-chip memory, such as non-volatility, high-density, and low-power write capability. In this work, we present the first effort to design and evaluate cache architectures using PeFETs.

Spiking Neural Networks (SNNs) have attracted considerable attention due to their suitability to processing temporal input streams, as well as the emergence of highly power-efficient neuromorphic hardware platforms. The computational cost of evaluating a Spiking Neural Network (SNN) is strongly correlated with the number of timesteps for which it is evaluated. To improve the computational efficiency of SNN evaluation, we propose layerwise disaggregated SNNs (LD-SNNs), wherein the number of timesteps is independently optimized for each layer of the network. In effect, LD-SNNs allow for a better allocation of computational effort across layers in a network, resulting in an improved tradeoff between accuracy and efficiency. We propose a methodology to design optimized LD-SNNs from any given SNN. Across four benchmark networks, LD-SNNs achieve 1.67-3.84x reduction in synaptic updates and 1.2-2.56x reduction in neurons evaluated. These improvements translate to 1.25-3.45x faster inference on four different hardware platforms including two server-class platforms, a desktop platform and an edge SoC.

Real-time machine vision applications running on resource-constrained embedded systems face challenges for maintaining performance. An especially challenging scenario arises when multiple applications execute at the same time, creating contention for the computational resources of the system. This contention results in increase in inference delay of the machine vision applications, which can be unacceptable for time-critical tasks. To address this challenge, we propose an adaptive model selection framework that mitigates the impact of system contention and prevents unexpected increases in inference delay by trading off the application accuracy minimally. The framework has two parts, which are performed pre-deployment and at runtime. The pre-deployment part profiles the system for contention in a black-box manner and produces a model set that is specifically optimized for the contention levels observed in the system. The runtime part predicts the inference delays of each model considering the system contention and selects the best model according to the predictions for each frame. Compared to a fixed individual model with similar accuracy, our framework improves the performance by significantly reducing the inference delay violations against a specified threshold. We implement our framework on the Nvidia Jetson TX2 platform and show that our approach achieves greater than 20% reductions in delay violations over the individual baseline models.

Precision scaling has emerged as a popular technique to optimize the compute and storage requirements of Deep Neural Networks (DNNs). Efforts toward creating ultra-low-precision (sub-8-bit) DNNs for efficient inference suggest that the minimum precision required to achieve a given network-level accuracy varies considerably across networks, and even across layers within a network. This translates to a need to support variable precision computation in DNN hardware. Previous proposals for precision-reconfigurable hardware, such as bit-serial architectures, incur high overheads, significantly diminishing the benefits of lower precision. We propose Ax-BxP, a method for approximate blocked computation wherein each multiply-accumulate operation is performed block-wise (a block is a group of bits), facilitating re-configurability at the granularity of blocks. Further, approximations are introduced by only performing a subset of the required block-wise computations to realize precision re-configurability with high efficiency. We design a DNN accelerator that embodies approximate blocked computation and propose a method to determine a suitable approximation configuration for any given DNN. For the AlexNet, ResNet50, and MobileNetV2 DNNs, Ax-BxP achieves improvement in system energy and performance, respectively, over an 8-bit fixed-point (FxP8) baseline, with minimal loss (<1% on average) in classification accuracy. Further, by varying the approximation configurations at a finer granularity across layers and data-structures within a DNN, we achieve improvement in system energy and performance, respectively.

The use of deep learning (DL) to real-world applications, such as computer vision, speech recognition, and robotics, has become ubiquitous. This can be largely attributed to a virtuous cycle between algorithms, data and computing, and storage capacity, which has driven rapid advances in all these dimensions. The ever-increasing demand for computation and memory from DL workloads presents challenges across the entire spectrum of computing platforms, from edge devices to the cloud. Hence, there is a need to explore new hardware paradigms that go well beyond the current mainstays such as graphical processing units (GPUs), tensor processing units (TPUs), and neural processing units (NPUs). A key bottleneck of current platforms is the so-called memory wall, which arises from the need to move large amounts of data between memory and compute units, expending considerable time and energy. One promising solution to this challenge is to move some computations either closer to memory, within the memory subsystem, or even within individual memory arrays. This approach, which is broadly referred to as compute-in-memory (CiM), has the potential to break the memory wall, and thereby greatly improve speed and power consumption. In this article, we provide an overview of CiM techniques used at different levels of the memory hierarchy and based on different memory technologies, including static random access memories (SRAMs), nonvolatile memories (NVMs), and DRAMs. We also discuss architectural approaches to designing CiM-based DL accelerators. Finally, we discuss the challenges associated with adopting CiM in future DL accelerators.

Graph Neural Networks (GNNs) apply deep learning to inputs represented as graphs. They use fully-connected layers to extract features from the nodes/edges of a graph and aggregate these features using message passing between nodes, thereby combining two distinct computational patterns: dense, regular computations and sparse, irregular computations. To address the computational challenges posed by GNNs, we propose GNNERATOR, an accelerator with heterogeneous compute engines optimized for these two patterns. Further, we propose feature-blocking, a novel GNN dataflow that beneficially trades off irregular memory accesses during aggregation for regular memory accesses during feature extraction. We show that GNNERATOR achieves speedups of 5.7-37x over an NVIDIA RTX 2080-Ti, and 2.3x-3.8x over HyGCN, a state-of-the-art GNN accelerator.

Transformers have transformed the field of natural language processing. Their superior performance is largely attributed to the use of stacked “self-attention” layers, each of which consists of matrix multiplies as well as softmax operations. As a result, unlike other neural networks, the softmax operation accounts for a significant fraction of the total run-time of Transformers. To address this, we propose Softermax, a hardware-friendly softmax design. Softermax consists of base replacement, low-precision softmax computations, and an online normalization calculation. We show Softermax results in 2.35x the energy efficiency at 0.90x the size of a comparable baseline, with negligible impact on network accuracy.

Approximate Computing (AxC) is a popular design paradigm wherein selected computations are executed approximately to gain efficiency with minimal impact on application-level quality. Most efforts in AxC target specialized accelerators and domain-specific processors, with relatively limited focus on General-Purpose Processors (GPPs). However, GPPs are still broadly used to execute applications that are amenable to AxC, making AxC for GPPs a critical challenge. A key bottleneck in applying AxC to GPPs is that their execution units account for only a small fraction of total energy, requiring a holistic approach targeting compute, memory and control front-ends. This paper proposes such an approach that leverages the application property of value similarity, i.e., input operands to computations that occur close-in-time take similar values. Such similar computations are dynamically pre-detected and the fetch-decode-execute of entire instruction sequences are skipped to benefit performance. To this end, we propose a set of lightweight micro-architectural and ISA extensions called VSX that enable: (i) similarity detection amongst values in a cache-line, (ii) skipping of pre-defined instructions and/or loop iterations when similarity is detected, and (iii) substituting outputs of skipped instructions with saved results from previously executed computations. We also develop compiler techniques, guided by user annotations, to benefit from VSX in the context of common Machine Learning (ML) kernels. Our RTL implementation of VSX for a low-power RISC-V processor incurred 2.13% area overhead and yielded 1.19×-3.84× speedup with <0.5 % accuracy loss on 6 ML benchmarks.

Quantization, or reducing the precision of variables and operations, and pruning, or removing neurons and connections are two popular approaches for improving the efficiency of DNNs. These directions have been pursued largely separately. In this work, we investigate combining DNN quantization and pruning as each of them is pushed to its limits. Specifically, we explore the efficacy of pruning DNNs for inference in the ultralow precision (sub-8 bit) regime. Pruning requires the use of sparse formats to store and access only the non-zero values. We provide analytical expressions for the storage required by these sparse formats. We demonstrate that with decreasing weight precision, the overhead of indexing non-zero locations starts to dominate, greatly diminishing the benefits of pruning. We specifically analyze the compression ratios of two popular sparse formats – Compressed Sparse Column (CSC) and Sparsity Map (Smap) – and demonstrate that they drop significantly, even degrading to <1 (inflation) in some cases. To address this challenge, we make a key observation that the best-performing sparse format varies across different precisions and sparsity levels. Based on this observation, we propose a hybrid compression scheme that dynamically chooses between sparse formats at both the network and layer-level granularities. We further propose a new scheme, compressed Sparsity Map (cSmap), to enhance the performance of hybrid compression. The cSmap scheme improves the Smap scheme by applying compression methods widely used in manufacturing test. Across 6 state-of-the-art Convolutional Neural Networks (CNNs) and Recurrent Neural Networks (RNNs), the proposed hybrid compression scheme improves the average compression ratio by 18.3% - 34.7% compared to previous approaches.

Resistive crossbars designed with nonvolatile memory devices have emerged as promising building blocks for deep neural network (DNN) hardware, due to their ability to compactly and efficiently realize vector-matrix multiplication (VMM), the dominant computational kernel in DNNs. However, a key challenge with resistive crossbars is that they suffer from a range of device and circuit level nonidealities, such as driver resistance, sensing resistance, sneak paths, interconnect parasitics, nonlinearities in the peripheral circuits, stochastic write operations, and process variations. These nonidealities can lead to errors in VMMs, eventually degrading the DNN's accuracy. It is therefore critical to study the impact of crossbar nonidealities on the accuracy of large-scale DNNs (with millions of neurons and billions of synaptic connections). However, this is challenging because the existing device and circuit models are too slow to use in application-level evaluations. We present RxNN, a fast and accurate simulation framework to evaluate large-scale DNNs on resistive crossbar systems. RxNN splits and maps the computations involved in each DNN layer into crossbar operations, and evaluates them using a fast crossbar model (FCM) that accurately captures the errors arising due to crossbar nonidealities while being four-to-five orders of magnitude faster than circuit simulation. FCM models a crossbar-based VMM operation using three stages-nonlinear models for the input and output peripheral circuits (digital-to-analog and analog-to-digital converters), and an equivalent nonideal conductance matrix for the core crossbar array. We implement RxNN by extending the Caffe machine learning framework and use it to evaluate a suite of six large-scale DNNs developed for the ImageNet Challenge (ILSVRC). Our experiments reveal that resistive crossbar nonidealities can lead to significant accuracy degradations (9.6%-32%) for these large-scale DNNs. To the best of our knowledge, this article is the first quantitative evaluation of the accuracy of large-scale DNNs on resistive crossbar-based hardware. We also demonstrate that RxNN enables fast model-in-the-loop retraining of DNNs to partially mitigate the accuracy degradation.

Deep neural networks (DNNs) have gained tremendous popularity in recent years due to their ability to achieve superhuman accuracy in a wide variety of machine learning tasks. However, the compute and memory requirements of DNNs have grown rapidly, creating a need for energy-efficient hardware. Resistive crossbars have attracted significant interest in the design of the next generation of DNN accelerators due to their ability to natively execute massively parallel vector-matrix multiplications within dense memory arrays. However, crossbar-based computations face a major challenge due to device and circuit-level nonidealities, which manifest as errors in the vector-matrix multiplications and eventually degrade DNN accuracy. To address this challenge, there is a need for tools that can model the functional impact of nonidealities on DNN training and inference. Existing efforts toward this goal are either limited to inference or are too slow to be used for large-scale DNN training. We propose TxSim, a fast and customizable modeling framework to functionally evaluate DNN training on crossbar-based hardware considering the impact of nonidealities. The key features of TxSim that differentiate it from prior efforts are: 1) it comprehensively models nonidealities during all training operations (forward propagation, backward propagation, and weight update) and 2) it achieves computational efficiency by mapping crossbar evaluations to well-optimized Basic Linear Algebra Subprograms (BLAS) routines and incorporates speedup techniques to further reduce simulation time with minimal impact on accuracy. TxSim achieves 6×- 108× improvement in simulation speed over prior works, and thereby makes it feasible to evaluate the training of large-scale DNNs on crossbars. Our experiments using TxSim reveal that the accuracy degradation in DNN training due to nonidealities can be substantial (3%-36.4%) for large-scale DNNs and data sets, underscoring the need for further research in mitigation techniques. We also analyze the impact of various device and circuit-level parameters and the associated nonidealities to provide key insights that can guide the design of crossbar-based DNN training accelerators.

We consider existing and emerging neural workloads, and what hardware accelerators might be best suited for said workloads. We begin with a discussion of analog crossbar arrays, which are known to be well-suited for matrix-vector multiplication operations that are commonplace in existing neural network models such as convolutional neural networks (CNNs). We highlight candidate crosspoint devices, what device and materials challenges must be overcome for a given device to be employed in a crossbar array for a computationally interesting neural workload, and how circuit and algorithmic optimizations may be employed to mitigate undesirable characteristics from devices/materials. We then discuss two emerging neural workloads. We first consider machine learning models for one- and few-shot learning tasks (i.e., where a network can be trained with just one or a few, representative examples of a given class). Notably crossbar-based architectures can be used to accelerate said models. Hardware solutions based on content addressable memory arrays will also be discussed. We then consider machine learning models for recommendation systems. Recommendation models, an emerging class of machine learning models, employ distinct neural network architectures that operate of continuous and categorical input features which make hardware acceleration challenging. We will discuss the open research challenges and opportunities within this space.

Deep Neural Networks (DNNs) have transformed the field of artificial intelligence and represent the state-of-the-art in many machine learning tasks. There is considerable interest in using DNNs to realize edge intelligence in highly resource-constrained devices such as wearables and IoT sensors. Unfortunately, the high computational requirements of DNNs pose a serious challenge to their deployment in these systems. Moreover, due to tight cost (and hence, area) constraints, these devices are often unable to accommodate hardware accelerators, requiring DNNs to execute on the General Purpose Processor (GPP) cores that they contain. We address this challenge through lightweight micro-architectural extensions to the memory hierarchy of GPPs that exploit a key attribute of DNNs, viz. sparsity, or the prevalence of zero values. We propose SparseCache, an enhanced cache architecture that utilizes a null cache based on a Ternary Content Addressable Memory (TCAM) to compactly store zero-valued cache lines, while storing non-zero lines in a conventional data cache. By storing address rather than values for zero-valued cache lines, SparseCache increases the effective cache capacity, thereby reducing the overall miss rate and execution time. SparseCache utilizes a Zero Detector and Approximator (ZDA) and Address Merger (AM) to perform reads and writes to the null cache. We evaluate SparseCache on four state-of-the-art DNNs programmed with the Caffe framework. SparseCache achieves 5-28% reduction in miss-rate, which translates to 5-21% reduction in execution time, with only 0.1% area and 3.8% power overhead in comparison to a low-end Intel Atom Z-series processor.

Multi-view object detection or the problem of detecting an object using multiple viewpoints, is an important problem in computer vision with varied applications such as distributed smart cameras and collaborative drone swarms. Multi-view object detection algorithms based on deep neural networks (DNNs) achieve high accuracy by view pooling, or aggregating features corresponding to the different views. However, when these algorithms are realized on networks of edge devices, the communication cost incurred by view pooling often dominates the overall latency and energy consumption.In this paper, we propose techniques for communication-efficient view pooling that can be used to improve the efficiency of distributed multi-view object detection and apply them to state-of-the-art multi-view DNNs. First, we propose significance-aware feature selection, which identifies and communicates only those features from each view that are likely to impact the pooled result (and hence, the final output of the DNN). Second, we propose multi-resolution view pooling, which divides views into dominant and non-dominant views, and down-scales the features from non-dominant views using an additional network layer before communicating them for pooling. The dominant and non-dominant views are pooled separately and the results are jointly used to derive the final classification. We implement and evaluate the proposed pooling schemes using a model test-bed of twelve Raspberry Pi 3b+ devices and show that they achieve 9X - 36X reduction in data communicated and 1.8X reduction in inference latency, with no degradation in accuracy.

Ternary Deep Neural Networks (DNNs), which employ ternary precision for weights and activations, have recently been shown to attain accuracies close to full-precision DNNs, raising interest in their efficient hardware realization. In this work we propose a Non-Volatile Ternary Compute-Enabled memory cell (TeC-Cell) based on ferroelectric transistors (FEFETs) for inmemory computing in the signed ternary regime. In particular, the proposed cell enables storage of ternary weights and employs multi-word-line assertion to perform massively parallel signed dot-product computations between ternary weights and ternary inputs. We evaluate the proposed design at the array level and show 72% and 74% higher energy efficiency for multiply-andaccumulate (MAC) operations compared to standard nearmemory computing designs based on SRAM and FEFET, respectively. Furthermore, we evaluate the proposed TeC-Cell in an existing ternary in-memory DNN accelerator. Our results show 3.3X-3.4X reduction in system energy and 4.3X-7X improvement in system performance over SRAM and FEFET based nearmemory accelerators, across a wide range of DNN benchmarks including both deep convolutional and recurrent neural networks.

Deep Neural Networks are an important class of machine learning algorithms that have demonstrated state-of-the-art accuracy for different cognitive tasks like image and speech recognition. Modem deep networks have millions to billions of parameters, which leads to high memory and energy requirements during training as well as during inference on resource-constrained edge devices. Consequently, pruning techniques have been proposed that remove less significant weights in deep networks, thereby reducing their memory and computational requirements. Pruning is usually performed after training the original network, and is followed by further retraining to compensate for the accuracy loss incurred during pruning. The prune-and-retrain procedure is repeated iteratively until an optimum tradeoff between accuracy and efficiency is reached. However, such iterative retraining adds to the overall training complexity of the network. In this work, we propose a dynamic pruning-while-training procedure, wherein we prune filters of the convolutional layers of a deep neural network during training itself, thereby precluding the need for separate retraining. We evaluate our dynamic pruning-while-training approach with three different pre-existing pruning strategies, viz. mean activation-based pruning, random pruning, and L1 normalization-based pruning. Our results for VGG-16 trained on CIFAR10 shows that L1 normalization provides the best performance among all the techniques explored in this work with less than 1% drop in accuracy after pruning 80% of the filters compared to the original network. We further evaluated the L1 normalization based pruning mechanism on CIFAR100. Results indicate that pruning while training yields a compressed network with almost no accuracy loss after pruning 50% of the filters compared to the original network and ~5% loss for high pruning rates (> 80%). The proposed pruning methodology yields 41% reduction in the number of computations and memory accesses during training for CIFAR10, CIFAR100 and ImageNet compared to training with retraining for 10 epochs.

Traditional computing systems based on the von Neumann architecture are fundamentally bottlenecked by data transfers between processors and memory. The emergence of data-intensive workloads, such as machine learning (ML), creates an urgent need to address this bottleneck by designing computing platforms that utilize the principle of colocated memory and processing units. Such an approach, known as “in-memory computing,” can potentially eliminate data movement costs by computing inside the memory array itself. Crossbars based on resistive nonvolatile memory (NVM) devices have shown immense promise in serving as the building blocks of in-memory computing systems for ML workloads. This is because their high density can lead to higher on-chip storage capacity, while they can also perform massively parallel, in situ matrix-vector multiplication (MVM) operations, thereby accelerating the main computational kernel of ML workloads. However, resistive crossbar-based analog computing is inherently approximate due to the device- and circuit-level nonidealities. Furthermore, the area and energy costs of peripheral circuits for conversions between the analog and digital domains can greatly diminish the intrinsic efficiency of crossbar-based MVM computation. We present a comprehensive overview of the emerging paradigm of computing using NVM crossbars for accelerating ML workloads. We describe the design principles of resistive crossbars, including the devices and associated circuits that constitute them. We discuss intrinsic approximations arising from the device and circuit characteristics and study their functional impact on the MVM operation. Next, we present an overview of spatial architectures that exploit the high storage density of NVM crossbars. Furthermore, we elaborate on software frameworks that effectively capture device-circuit-architecture characteristics to evaluate the performance of large-scale deep neural networks (DNNs) using resistive crossbar-based hardware. Finally, we discuss open challenges and future research directions that need to be explored in order to realize the vision of resistive crossbars as the building blocks of future computing platforms.

Adversarial attacks have exposed serious vulnerabilities in deep neural networks (DNNs), causing misclassifications through human-imperceptible perturbations to DNN inputs. We explore a new direction in the field of adversarial attacks by suggesting attacks that aim to degrade the energy or latency of DNNs rather than their classification accuracy. As a specific embodiment of this new threat vector, we propose and demonstrate adversarial sparsity attacks, which modify a DNN's inputs so as to reduce sparsity (or the incidence of zeros) in its internal activation values. Exploiting sparsity in hardware and software has emerged as a popular approach to improve DNN efficiency in resource-constrained systems. The proposed attack, therefore, increases the execution time and energy consumption of sparsity-optimized DNN implementations, raising concern over their deployment in latency and energy-critical applications. We propose a systematic methodology to generate adversarial inputs for sparsity attacks by formulating an objective function that quantifies the network's activation sparsity and minimizing this function using iterative gradient-descent techniques. To prevent easy detection of the attack, we further ensure that the perturbation magnitude is within a specified constraint and that the perturbation does not affect classification accuracy. We launch both white-box and black-box versions of adversarial sparsity attacks on image recognition DNNs and demonstrate that they decrease activation sparsity by 1.16×-1.82×. On a sparsity-optimized DNN accelerator, the attack results in degradations of 1.12×-1.59× in latency and 1.18×-1.99× in energy-delay product (EDP). Additionally, we analyze the impact of various hyperparameters and constraints on the attack's efficacy. Finally, we evaluate defense techniques, such as activation thresholding and input quantization and demonstrate that the proposed attack is able to withstand them, highlighting the need for further efforts in this new direction within the field of adversarial machine learning.

The ability of several important application domains to tolerate inexactness or approximations in a large fraction of their computations has lead to the advent of approximate computing, a new design paradigm that exploits the intrinsic error-resilient nature to optimize computing platforms for energy and performance. A promising approach to approximate computing is to design approximate circuits, or circuit implementations that are highly efficient but differ in functionality from their original specifications subject to a prespecified quality constraint. While a slew of manual design techniques for approximate circuits have demonstrated their significant potential, a key requirement for their mainstream adoption is to develop automatic methodologies and tools that are general and scalable to any given circuit and quality specification. In this article, we propose SALSA, a systematic methodology for automatic logic synthesis of approximate circuits. Given a golden RTL specification of a circuit and a quality constraint that defines the amount of error that may be introduced in the implementation, SALSA synthesizes an approximate version of the circuit that adheres to the prespecified quality bounds. We make two key contributions: 1) the rigorous formulation of the problem of approximate logic synthesis (ALS), enabling the generation of circuits that is corrected by construction and 2) mapping the problem of approximate synthesis into an equivalent traditional logic synthesis problem, thereby allowing the capabilities of existing synthesis tools to be fully utilized for ALS. In order to achieve these benefits, SALSA forms a virtual quality constraint circuit (QCC) that encodes the quality constraints using logic functions called Q-functions. It then captures the flexibility that engendered by them as approximation don't cares (ADCs), which are used for circuit simplification using traditional don't care-based optimization techniques. We utilized SALSA to automatically synthesize approximate circuits ranging from arithmetic building blocks (adders, multipliers, and MAC) to entire datapaths (DCT, FIR, IIR, SAD, FFT Butterfly, and Euclidean distance), demonstrating scalability and significant improvements in area (1.1× to 1.85× for tight error constraints, and 1.2× to 4.75× for relaxed error constraints) and power (1.15× to 1.75× for tight error constraints, and 1.3× to 5.25× for relaxed error constraints).

Deep Neural Networks (DNNs) have advanced the state-of-the-art in a variety of machine learning tasks and are deployed in increasing numbers of products and services. However, the computational requirements of training and evaluating large-scale DNNs are growing at a much faster pace than the capabilities of the underlying hardware platforms that they are executed upon. To address this challenge, one promising approach is to exploit the error resilient nature of DNNs by skipping or approximating computations that have negligible impact on classification accuracy. Almost all prior efforts in this direction propose static DNN approximations by either pruning network connections, implementing computations at lower precision, or compressing weights. In this work, we propose Dynamic Variable Effort Deep Neural Networks (D y VED eep ) to reduce the computational requirements of DNNs during inference. Complementary to the aforementioned static approaches, DyVEDeep is a dynamic approach that exploits heterogeneity in the DNN inputs to improve their compute efficiency with comparable classification accuracy and without requiring any re-training. D y VED eep equips DNNs with dynamic effort mechanisms that identify computations critical to classifying a given input and focus computational effort only on the critical computations, while skipping or approximating the rest. We propose three dynamic effort mechanisms that operate at different levels of granularity viz. neuron, feature, and layer levels. We build D y VED eep versions of six popular image recognition benchmarks (CIFAR-10, AlexNet, OverFeat, VGG-16, SqueezeNet, and Deep-Compressed-AlexNet) within the Caffe deep-learning framework. We evaluate D y VED eep on two platforms—a high-performance server with a 2.7 GHz Intel Xeon E5-2680 processor and 128 GB memory, and a low-power Raspberry Pi board with an ARM Cortex A53 processor and 1 GB memory. Across all benchmarks, D y VED eep achieves 2.47×--5.15× reduction in the number of scalar operations, which translates to 1.94×--2.23× and 1.46×--3.46× performance improvement over well-optimized baselines on the Xeon server and the Raspberry Pi, respectively, with comparable classification accuracy.

Resistive crossbars have shown strong potential as the building blocks of future neural fabrics, due to their ability to natively execute vector-matrix multiplication (the dominant computational kernel in DNNs). However, a key challenge that arises in resistive crossbars is that non-idealities in the synaptic devices, interconnects, and peripheral circuits of resistive crossbars lead to errors in the computations performed. When large-scale DNNs are executed on resistive crossbar systems, these errors compound and result in unacceptable degradation in application-level accuracy. We propose CxDNN, a hardware-software methodology that enables the realization of large-scale DNNs on crossbar systems by compensating for errors due to non-idealities, greatly mitigating the degradation in accuracy. CxDNN is composed of (i) an optimized mapping technique to convert floating-point weights and activations to crossbar conductances and input voltages, (ii) a fast one-time re-training method to recover accuracy loss due to this conversion, and (iii) low-overhead compensation hardware to mitigate dynamic and hardware-instance-specific errors. Unlike previous efforts that are limited to small networks and require the training and deployment of hardware-instance-specific models, CxDNN presents a scalable compensation methodology that can address large DNNs (e.g., ResNet-50 on ImageNet) and maintains the train-once-deploy-anywhere tenet of current DNN application. We evaluated CxDNN on six top DNNs on the ImageNet dataset with 0.5--13.8 million neurons and 0.5--15.5 billion connections. CxDNN achieves 16.9%--49% improvement in the top-1 classification accuracy, effectively mitigating a key challenge to the use of resistive crossbar--based neural fabrics.

The use of lower precision has emerged as a popular technique to optimize the compute and storage requirements of complex deep neural networks (DNNs). In the quest for lower precision, recent studies have shown that ternary DNNs (which represent weights and activations by signed ternary values) represent a promising sweet spot, achieving accuracy close to full-precision networks on complex tasks. We propose TiM-DNN, a programmable in-memory accelerator that is specifically designed to execute ternary DNNs. TiM-DNN supports various ternary representations including unweighted {-1, 0, 1}, symmetric weighted {-a, 0, a}, and asymmetric weighted {-a, 0, b} ternary systems. The building blocks of TiM-DNN are TiM tiles- specialized memory arrays that perform massively parallel signed ternary vector-matrix multiplications with a single access. TiM tiles are in turn composed of ternary processing cells (TPCs), bit-cells that function as both ternary storage units and signed ternary multiplication units. We evaluate an implementation of TiM-DNN in 32-nm technology using an architectural simulator calibrated with SPICE simulations and RTL synthesis. We evaluate TiM-DNN across a suite of state-of-the-art DNN benchmarks including both deep convolutional and recurrent neural networks. A 32-tile instance of TiM-DNN achieves a peak performance of 114 TOPs/s, consumes 0.9-W power, and occupies 1.96 mm2 chip area, representing a 300× and 388× improvement in TOPS/W and TOPS/mm2, respectively, compared to an NVIDIA Tesla V100 GPU. In comparison to specialized DNN accelerators, TiM-DNN achieves 55×-240× and 160×-291× improvement in TOPS/W and TOPS/mm2, respectively. Finally, when compared to a well-optimized near-memory accelerator for ternary DNNs, TiM-DNN demonstrates 3.9×-4.7× improvement in system-level energy and 3.2×-4.2× speedup, underscoring the potential of in-memory computing for ternary DNNs.

Memory subsystems are a major energy bottleneck in computing platforms due to frequent transfers between processors and off-chip memory. We propose approximate memory compression, a technique that leverages the intrinsic resilience of emerging workloads such as machine learning and data analytics to reduce off-chip memory traffic, thereby improving energy and performance. We realize approximate memory compression by enhancing the memory controller to be aware of approximate memory regions-regions in memory that contain approximation-resilient data-and to transparently compress (decompress) the data written to (read from) these regions. To provide control over approximations, each approximate memory region is associated with an error constraint such as the maximum error that may be introduced in each data element. The quality-aware memory controller subjects memory transactions to a compression scheme that introduces approximations, thereby reducing memory traffic, while adhering to the specified error constraint for each approximate memory region. A software interface is provided to allow programmers to identify data structures (DSs) that are resilient to approximations. A runtime quality control framework automatically determines the error constraints for the identified DSs such that a given target application-level quality is maintained. We evaluate our proposal by applying it to three different main memory technologies in the context of a general-purpose computing system-DDR3 DRAM, LPDDR3 DRAM, and spin-transfer torque magnetic RAM (STT-MRAM). To demonstrate the feasibility of the proposed concepts, we also implement a hardware prototype using the Intel UniPHY-DDR3 memory controller and Nios-II processor, a Hynix DDR3 DRAM module, and a Stratix-IV field-programmable gate array (FPGA) development board. Across a wide range of machine learning benchmarks, approximate memory compression obtains significant benefits in main memory energy (1.18× for DDR3 DRAM, 1.52× for LPDDR3 DRAM, and 2.0× for STT-MRAM) and a simultaneous improvement in execution time (5.2% for DDR3 DRAM, 5.4% for LPDDR3 DRAM, and 9.3% for STT-MRAM) with nearly identical application output quality.

Memory Augmented Neural Networks (MANNs) enhance a deep neural network with an external differentiable memory, enabling them to perform complex tasks well beyond the capabilities of conventional deep neural networks. We identify a unique challenge that arises in MANNs due to soft reads and writes to the differentiable memory, each of which requires access to all the memory locations. This characteristic of MANN workloads severely limits the performance of MANNs on CPUs, GPUs, and classical neural network accelerators. We present the first effort to design a hardware architecture that improves the efficiency of MANNs. Leveraging the intrinsic ability of resistive crossbars to efficiently realize in-memory computations, we propose X-MANN, a memory-centric crossbar-based architecture that is specialized to match the compute characteristics observed in MANNs. We design a transposable crossbar processing unit that can efficiently perform the different computational kernels of MANNs. To improve performance of soft writes in X-MANN, we propose an incremental write mechanism that leverages the characteristics of soft write operations. We develop an architectural simulator for X-MANN that utilizes array-level timing and power models of resistive crossbars calibrated from SPICE simulations. Across a suite of MANN benchmarks, X-MANN achieves 23.7×-45.7× speedup and 75.1×-267.1× reduction in energy over state-of-the-art GPU implementations.

Approximate Computing (AxC), which leverages the intrinsic resilience of applications to approximations in their underlying computations, has emerged as a promising approach to improving computing system efficiency. Most prior efforts in AxC take a compute-centric approach and approximate arithmetic or other compute operations through design techniques at different levels of abstraction. However, emerging workloads such as machine learning, search and data analytics process large amounts of data and are significantly limited by the memory sub-systems of modern computing platforms.In this work, we shift the focus of approximations from computations to data, and propose a data-centric approach to AxC, which can boost the performance of memory-subsystem-limited applications. The key idea is to modulate the application's data-accesses in a manner that reduces off-chip memory traffic. Specifically, we propose a data-access approximation technique called data subsetting, in which all accesses to a data structure are redirected to a subset of its elements so that the overall footprint of memory accesses is decreased. We realize data subsetting in a manner that is transparent to hardware and requires only minimal changes to application software. Recognizing that most applications of interest represent and process data as multi-dimensional arrays or tensors, we develop a templated data structure called SubsettableTensor that embodies mechanisms to define the accessible subset and to suitably redirect accesses to elements outside the subset. As a further optimization, we observe that data subsetting may cause some computations to become redundant and propose a mechanism for application software to identify and eliminate such computations. We implement SubsettableTensor as a C++ class and evaluate it using parallel software implementations of 7 machine learning applications on a 48-core AMD Opteron server. Our experiments indicate that data subsetting enables 1.33×-4.44× performance improvement with <;0.5% loss in application-level quality, underscoring its promise as a new approach to approximate computing.

Spiking Neural Networks (SNNs), which represent information as sequences of spikes, are gaining interest due to the emergence of low-power hardware platforms such as IBM TrueNorth and Intel Loihi, and their intrinsic ability to process temporal streams of data (e.g., outputs from event-based cameras). A spike produced by a neuron in an SNN is an event that triggers updates to the membrane potentials of each of the fanout neurons based on the weight associated with the synaptic connection, possibly resulting in other spikes being generated. The time and energy consumption in SNN implementations are dominated by accesses to the synaptic weights from memory and communication of spikes through the on-chip network. To improve the energy-efficiency of SNNs, we therefore propose Dynamic Spike Bundling (DSB), wherein an event to fanout neurons is not generated for every spike; instead, spikes produced by a neuron that occur close in time are dynamically bundled, with a single event being generated for the entire spike bundle. This reduces memory accesses as the synaptic weight can be fetched just once and reused across all spikes in the bundle. The communication traffic is also reduced as fewer messages are communicated between neurons.To evaluate DSB, we develop B-SNNAP, an event-driven SNN accelerator with hardware support for dynamically bundling spikes with minimal overheads. Across 7 image recognition benchmarks including CIFAR100 and ImageNet datasets, DSB achieves 1.15×-3.8× reduction in energy for <;0.1% loss in accuracy, and upto 5.1× savings when <;1% accuracy loss is tolerable.

We propose a non-volatile memory based on cross-coupled reconfigurable ferroelectric transistors (R-FEFETs) which features differential read along with low power computation-in-memory (CiM). Exploiting the dynamic modulation of hysteresis in R-FEFETs, we achieve the aforementioned functionalities with just 2 access transistors (in addition to 2 R-FEFETs). The differential access of the proposed memory not only enhances the sense margin during read, but also enables natural computation of AND and NOR logic functions between two bits stored in the array, with the assertion of two word-lines. Using this feature, we propose a CiM architecture involving the use of a compact compute module integrated to a sense amplifier which performs Boolean logic as well as arithmetic operations such as addition of two words with a single array access. Unlike existing non-volatile CiM designs, our work features: (i) a self-referenced read operation due to differential access and (ii) a single universal voltage reference for all compute operations. At the array-level, the proposed design (R-FEFET-CiM) achieves 33%, 27% and 12% lower write, read and compute energies respectively, at iso-access time compared to FEFET based CiM (FEFET-CiM). System analysis performed by integrating our R-FEFET-CiM in the Nios II processor shows total system energy savings of 24% and 14% across various benchmarks, compared to near-memory computing and FEFET-CiM, respectively.

Memory-augmented neural networks (MANNs)-- which augment a traditional Deep Neural Network (DNN) with an external, differentiable memory-- are emerging as a promising direction in machine learning. MANNs have been shown to achieve one-shot learning and complex cognitive capabilities that are well beyond those of classical DNNs. We analyze the computational characteristics of MANNs and observe that they present a unique challenge due to soft reads and writes to the differentiable memory, each of which requires access to all the memory locations. This results in poor performance of MANNs on modern CPUs, GPUs, and other accelerators. To address this, we present Manna, a specialized hardware inference accelerator for MANNs. Manna is a memory-centric design that focuses on maximizing performance in an extremely low FLOPS/Byte context. The key architectural features from which Manna derives efficiency are: (i) investing most of the die area and power in highly banked on-chip memories that provide ample bandwidth rather than large matrix-multiply units that would be underutilized due to the low reuse (ii) a hardware-assisted transpose mechanism for accommodating the diverse memory access patterns observed in MANNs, (iii) a specialized processing tile that is equipped to handle the nearly-equal mix of MAC and non-MAC computations present in MANNs, and (iv) methods to map MANNs to Manna that minimize data movement while fully exploiting the little reuse present. We evaluate Manna by developing a detailed architectural simulator with timing and power models calibrated by synthesis to the 15 nm Nangate Open Cell library. Across a suite of 10 benchmarks, Manna demonstrates average speedups of 39x with average energy improvements of 122x over an NVIDIA 1080-Ti Pascal GPU and average speedups of 24x with average energy improvements of 86x over a state-of-the-art NVIDIA 2080-Ti Turing GPU.

Deep Neural Networks (DNNs) have emerged as the method of choice for solving a wide range of machine learning tasks. The enormous computational demand posed by DNNs is a key challenge for computing system designers and has most commonly been addressed through the design of DNN accelerators. However, these specialized accelerators utilize large quantities of multiply-accumulate units and on-chip memory and are prohibitive in area and cost constrained systems such as wearable devices and IoT sensors. In this work, we take a complementary approach and improve the performance of DNNs on general-purpose processor (GPP) cores. We do so by exploiting a key attribute of DNNs, viz. sparsity or the prevalence of zero values. We propose Sparsity-aware Core Extensions (SparCE) - a set of low-overhead micro-architectural and ISA extensions that dynamically detect whether an operand (e.g., the result of a load instruction) is zero and subsequently skip a set of future instructions that use it. To maximize performance benefits, SparCE ensures that the instructions to be skipped are prevented from even being fetched, as squashing instructions comes with a penalty (e.g., a pipeline stall). SparCE consists of 2 key micro-architectural enhancements. First, a Sparsity Register File (SpRF) is utilized to track registers that are zero. Next, a Sparsity-Aware Skip Address (SASA) Table is used to indicate instruction sequences that can be skipped, and to specify conditions on SpRF registers that trigger instruction skipping. When an instruction is fetched, SparCE dynamically pre-identifies whether the following instruction(s) can be skipped, and if so appropriately modifies the program counter, thereby skipping the redundant instructions and improving performance. We model SparCE using the gem5 architectural simulator, and evaluate our approach on 6 state-of-the-art image-recognition DNNs in the context of both training and inference using the Caffe deep learning framework. On a scalar microprocessor, SparCE achieves 1.11×-1.96× speedups across both convolution and fully-connected layers that exhibit 10-90 percent sparsity. These speedups translate to 19-31 percent reduction in execution time at the overall application-level. We also evaluate SparCE on a 4-way SIMD ARMv8 processor using the OpenBLAS library, and demonstrate that SparCE achieves 8-15 percent reduction in the application-level execution time.

In-memory computing is a promising approach to alleviating the processor-memory data transfer bottleneck in computing systems. While spintronics has attracted great interest as a non-volatile memory technology, recent work has shown that its unique properties can also enable in-memory computing. We summarize efforts in this direction, and describe three different designs that enhance STT-MRAM to perform logic, arithmetic, and vector operations and evaluate transcendental functions within memory arrays.

Accelerator-based computing, which has been a mainstay of System-on-Chips (SoCs) is of growing interest to a wider range of computing systems. However, the significant design effort required to identify a computational target for acceleration, design a hardware accelerator, verify the correctness of the accelerator, integrate the accelerator into the system, and rewrite applications to use the accelerator, is a major bottleneck to the widespread adoption of accelerator-based computing. The classical approach to this problem is based on top-down methodologies such as automatic HW/SW partitioning and high-level synthesis (HLS). While HLS has advanced significantly and is seeing increased adoption, it does not leverage the ability of experienced human designers to craft highly optimized RTL, nor does it leverage the growing body of already existing hardware accelerators. In this work, we propose ACCLIB, a design framework that allows software developers to utilize existing libraries of predesigned hardware accelerators automatically with no prior knowledge of the function of the accelerators, with minimal knowledge of hardware design, and with minimal design effort. To accomplish this, ACCLIB uses formal verification techniques to match a target software function with a functionally equivalent accelerator from a library of accelerators. It also generates the required HW/SW interfaces as well as the code necessary to offload the computation to the accelerator. We validate ACCLIB by applying it to accelerate six different applications using a library of hardware accelerators in just over one hour per application, demonstrating that the proposed approach has the potential to lower the barrier to adoption of accelerator-based computing.

Modern computing platforms expend significant amounts of time and energy in transmitting data across on-chip and off-chip interconnects. This challenge is exacerbated in prevalent data-intensive workloads such as machine learning, data analytics and search. However, these workloads also present a unique opportunity in the form of intrinsic resilience to approximations in computations and data. We explore approximate compression of communication traffic, which leverages this intrinsic resilience to improve communication bandwidth and reduce the energy consumed by interconnects. Specifically, we propose AxBA, an approximate bus architecture framework that is aware of the data amenable to approximations and seamlessly compresses/decompresses the corresponding transactions on the bus without requiring any changes to pre-designed masters and slaves. AxBA uses a lightweight compression scheme based on approximate deduplication, which is suitable for the tight latency constraints imposed by bus-based interconnects. To facilitate software development on AxBA-based systems, we introduce a software interface that enables programmers to identify regions of the system address space that are amenable to approximations. We also propose a run-time quality monitoring framework that automatically determines the error constraints for the identified regions such that a specified application-level quality is maintained. We demonstrate the feasibility of the proposed concepts by realizing a prototype AxBA system on a Cyclone-IV FPGA development board using an Intel Nios II processor-based SoC. Across a suite of six machine learning benchmarks, AxBA obtains an average improvement in system performance of 29% and a 25% reduction in system-level energy for a 0.5% loss in application-level quality.

The emergence of the Internet of Things (IoT) and pervasive computing challenges in securely and conveniently connecting devices with limited user interfaces. In particular, discovering and bootstrapping a wireless connection (e.g., Wi-Fi and Bluetooth Low Energy) between two devices that share no prior knowledge, commonly known as pairing, often requires users to go through cumbersome tasks of manually discovering the target device and entering a long passkey. When the devices do not have a proper user interface to enter a passkey, the security of pairing is often given up, leaving the communication vulnerable to a number of attacks. To alleviate this challenge, we propose a usable and secure out-of-band (OOB) communication method called SyncVibe, leveraging the inherent nature of close-proximity transmission of mechanical vibration. SyncVibe utilizes a vibration motor and an accelerometer, that are already ubiquitously available or easy to embed in mobile and wearable devices, to transmit and receive pairing information. By simply keeping two devices in direct contact, the user can bootstrap a secure, high-bandwidth wireless connection without manual pairing procedures. The proposed method maximizes accuracy and effective data throughput with a vibration clock recovery technique, which inserts a minimal amount of extra bit patterns to assure synchronization between the transmitter and the receiver. In addition, SyncVibe can automatically adjust its detection thresholds in response to various vibration noises and transmission media. Our implementation of SyncVibe demonstrates high-accuracy transmission, proving itself as a suitable OOB communication channel for short data transmission for secure device pairing.

Neural networks, with their remarkable ability to derive meaning from a large volume of complicated or imprecise data, can be used to extract patterns and detect trends that are too complex for the von Neumann computing paradigm. Their considerable computational requirements stretch the capabilities of even modern computing platforms. We propose an approximate multiplier that exploits the inherent application resilience to error and utilizes the notion of computation sharing to achieve improved energy consumption for neural networks. We also propose a Multiplier-less Artificial Neuron (MAN), which is even more compact and energy efficient. We also propose a network retraining methodology to recover some of the accuracy loss due to the use of these approximate multipliers. We evaluated the proposed algorithm/design on several recognition applications. The results show that we achieve ∼33%, ∼32%, and ∼25% reduction in power consumption and ∼33%, ∼34%, and ∼27% reduction in area, respectively, for 12-, 8-, and 4-bit MAN, with a maximum ∼2.4% loss in accuracy compared to a conventional neuron implementation of equivalent bit precision. These comparisons were performed under iso-speed conditions.

Long Short Term Memory (LSTM) networks are a class of recurrent neural networks that are widely used for machine learning tasks involving sequences, including machine translation, text generation, and speech recognition. Large-scale LSTMs, which are deployed in many real-world applications, are highly compute intensive. To address this challenge, we propose AxLSTM, an application of approximate computing to improve the execution efficiency of LSTMs. An LSTM is composed of cells, each of which contains a cell state along with multiple gating units that control the addition and removal of information from the state. The LSTM execution proceeds in timesteps, with a new symbol of the input sequence processed at each timestep. AxLSTM consists of two techniques-Dynamic Timestep Skipping (DTS) and Dynamic State Reduction (DSR). DTS identifies, at runtime, input symbols that are likely to have little or no impact on the cell state and skips evaluating the corresponding timesteps. In contrast, DSR reduces the size of the cell state in accordance with the complexity of the input sequence, leading to a reduced number of computations per timestep. We describe how AxLSTM can be applied to the most common application of LSTMs, viz., sequence-to-sequence learning. We implement AxLSTM within the TensorFlow deep learning framework and evaluate it on 3 state-of-the-art sequence-to-sequence models. On a 2.7 GHz Intel Xeon server with 128 GB memory and 32 processor cores, AxLSTM achieves 1.08 × -1.31× speedups with minimal loss in quality, and 1.12 × -1.37× speedups when moderate reductions in quality are acceptable.

In-memory computing is a promising approach to addressing the processor-memory data transfer bottleneck in computing systems. We propose spin-transfer torque compute-in-memory (STT-CiM), a design for in-memory computing with spin-transfer torque magnetic RAM (STT-MRAM). The unique properties of spintronic memory allow multiple wordlines within an array to be simultaneously enabled, opening up the possibility of directly sensing functions of the values stored in multiple rows using a single access. We propose modifications to STT-MRAM peripheral circuits that leverage this principle to perform logic, arithmetic, and complex vector operations. We address the challenge of reliable in-memory computing under process variations by extending error-correction code schemes to detect and correct errors that occur during CiM operations. We also address the question of how STT-CiM should be integrated within a general-purpose computing system. To this end, we propose architectural enhancements to processor instruction sets and on-chip buses that enable STT-CiM to be utilized as a scratchpad memory. Finally, we present data mapping techniques to increase the effectiveness of STT-CiM. We evaluate STT-CiM using a device-to-architecture modeling framework, and integrate cycle-accurate models of STT-CiM with a commercial processor and on-chip bus (Nios II and Avalon from Intel). Our system-level evaluation shows that STT-CiM provides the system-level performance improvements of 3.93 times on average (up to 10.4 times), and concurrently reduces memory system energy by 3.83 times on average (up to 12.4 times).

Many key technologies of our society, including so-called artificial intelligence (AI) and big data, have been enabled by the invention of transistor and its ever-decreasing size and ever-increasing integration at a large scale. However, conventional technologies are confronted with a clear scaling limit. Many recently proposed advanced transistor concepts are also facing an uphill battle in the lab because of necessary performance tradeoffs and limited scaling potential. We argue for a new pathway that could enable exponential scaling for multiple generations. This pathway involves layering multiple technologies that enable new functions beyond those available from conventional and newly proposed transistors. The key principles for this new pathway have been demonstrated through an interdisciplinary team effort at C-SPIN (a STARnet center), where systems designers, device builders, materials scientists and physicists have all worked under one umbrella to overcome key technology barriers. This paper reviews several successful outcomes from this effort on topics such as the spin memory, logic-in-memory, cognitive computing, stochastic and probabilistic computing and reconfigurable information processing.

STT-MRAM has attracted great interest for use as on-chip memory due to its high density, near-zero leakage and high endurance. However, its overall energy efficiency is limited by the energy requirements of spin-transfer torque switching during writes and reliable single-ended sensing during reads. Leveraging the ability of many applications to produce acceptable outputs under approximations to computations and data, we propose the use of approximate storage to improve the energy efficiency of STT-MRAM based caches. Towards this end, we explore a combination of different approximation techniques at the circuit and architecture levels that yield significant energy benefits for small probabilities of errors in reads, writes, and retention. A key challenge arises when introducing approximate storage into a cache - data that can tolerate different levels of approximation (or not at all) may be dynamically loaded into a cache line at different times. In addition, it is necessary to manage the approximations so as to obtain a desirable energy-quality tradeoff at the application level. We propose STAxCache (Spintronic Approximate Cache), an STT-MRAM based approximate L2 cache architecture that retains the full flexibility of a conventional cache, while allowing for different levels of approximation to different parts of a program's memory address space. We introduce a simple interface that allows the programmer to specify the quality requirements for different data structures, and instructions in the ISA to expose this information to STAxCache. We utilize a device-to-architecture simulation framework to evaluate STAxCache and achieve 1.44x improvement in L2 cache energy for negligible (<; 0.5%) loss in application-level quality across a suite of 8 benchmarks.

Spiking Neural Networks (SNNs) are widely regarded as the third generation of artificial neural networks, and are expected to drive new classes of recognition, data analytics and computer vision applications. However, large-scale SNNs (e.g., of the scale of the human visual cortex) are highly compute and data intensive, requiring new approaches to improve their efficiency. Complementary to prior efforts that focus on parallel software and the design of specialized hardware, we propose AxSNN, the first effort to apply approximate computing to improve the computational efficiency of evaluating SNNs. In SNNs, the inputs and outputs of neurons are encoded as a time series of spikes. A spike at a neuron's output triggers updates to the potentials (internal states) of neurons to which it is connected. AxSNN determines spike-triggered neuron updates that can be skipped with little or no impact on output quality and selectively skips them to improve both compute and memory energy. Neurons that can be approximated are identified by utilizing various static and dynamic parameters such as the average spiking rates and current potentials of neurons, and the weights of synaptic connections. Such a neuron is placed into one of many approximation modes, wherein the neuron is sensitive only to a subset of its inputs and sends spikes only to a subset of its outputs. A controller periodically updates the approximation modes of neurons in the network to achieve energy savings with minimal loss in quality. We apply AxSNN to both hardware and software implementations of SNNs. For hardware evaluation, we designed SNNAP, a Spiking Neural Network Approximate Processor that embodies the proposed approximation strategy, and synthesized it to 45nm technology. The software implementation of AxSNN was evaluated on a 2.7 GHz Intel Xeon server with 128 GB memory. Across a suite of 6 image recognition benchmarks, AxSNN achieves 1.4–5.5x reduction in scalar operations for network evaluation, which translates to 1.2–3.62x and 1.26–3.9x improvement in hardware and software energies respectively, for no loss in application quality. Progressively higher energy savings are achieved with modest reductions in output quality.

Deep Neural Networks (DNNs) have demonstrated state-of-the-art performance on a broad range of tasks involving natural language, speech, image, and video processing, and are deployed in many real world applications. However, DNNs impose significant computational challenges owing to the complexity of the networks and the amount of data they process, both of which are projected to grow in the future. To improve the efficiency of DNNs, we propose ScaleDeep, a dense, scalable server architecture, whose processing, memory and interconnect subsystems are specialized to leverage the compute and communication characteristics of DNNs. While several DNN accelerator designs have been proposed in recent years, the key difference is that ScaleDeep primarily targets DNN training, as opposed to only inference or evaluation. The key architectural features from which ScaleDeep derives its efficiency are: (i) heterogeneous processing tiles and chips to match the wide diversity in computational characteristics (FLOPs and Bytes/FLOP ratio) that manifest at different levels of granularity in DNNs, (ii) a memory hierarchy and 3-tiered interconnect topology that is suited to the memory access and communication patterns in DNNs, (iii) a low-overhead synchronization mechanism based on hardware data-flow trackers, and (iv) methods to map DNNs to the proposed architecture that minimize data movement and improve core utilization through nested pipelining. We have developed a compiler to allow any DNN topology to be programmed onto ScaleDeep, and a detailed architectural simulator to estimate performance and energy. The simulator incorporates timing and power models of ScaleDeep's components based on synthesis to Intel's 14nm technology. We evaluate an embodiment of ScaleDeep with 7032 processing tiles that operates at 600 MHz and has a peak performance of 680 TFLOPs (single precision) and 1.35 PFLOPs (half-precision) at 1.4KW. Across 11 state-of-the-art DNNs containing 0.65M-14.9M neurons and 6.8M-145.9M weights, including winners from 5 years of the ImageNet competition, ScaleDeep demonstrates 6x-28x speedup at iso-power over the state-of-the-art performance on GPUs.

Mobile, wearable, and implantable devices integrate an increasing number and variety of sensors such as microphones, image sensors, and accelerometers. These devices spend substantial amounts of time reading the sensors within them, thereby incurring significant energy dissipation over off-chip serial interconnects. This paper proposes AXSERBUS, a quality-configurable approximate serial bus that exploits the locality of sensory data and the error resiliency of sensing applications to reduce energy dissipation. AXSERBUS significantly reduces signal transitions by encoding the differentials of sensory data in three encoding modes, depending on the magnitude of the differentials: very small differentials are zeroed out, incurring no energy dissipation; intermediate differentials are encoded using special low-transition count patterns; and for high differentials, the absolute value (not the differential) of the data is transmitted. Compared to previous schemes, the proposed multi-level encoding results in more data being encoded as low-energy patterns. In addition, in the intermediate differential encoding mode, the differentials are encoded in an approximate manner, and the approximation bounds are proportional to the magnitude of the differentials. Since small differentials are more frequent than large differentials in sensory data, the proposed encoding scheme also minimizes quality degradation. We demonstrate that AXSERBUS achieves improved energy vs. quality tradeoffs compared to previous schemes. In the context of an optical character recognition (OCR) application, AXSERBUS achieves 79.4% reduction in dynamic power dissipation, while maintaining accuracy above 95%.

Memory subsystems are a major energy bottleneck in computing platforms due to frequent transfers between processors and off-chip memory. We propose approximate memory compression, a technique that leverages the intrinsic resilience of emerging workloads such as machine learning and data analytics to reduce off-chip memory traffic and energy. To realize approximate memory compression, we enhance the memory controller to be aware of memory regions that contain approximation-resilient data, and to transparently compress/decompress the data written to/read from these regions. To provide control over approximations, the quality-aware memory controller conforms to a specified error constraint for each approximate memory region. We design a software interface that programmers can use to identify data structures that are resilient to approximations. We also propose a runtime quality control framework that automatically determines the error constraints for the identified data structures such that a given target application-level quality is maintained. We evaluate our proposal by implementing a hardware prototype using the Intel UniPHY-DDR3 memory controller and NIOS-II processor, a Hynix DDR3 DRAM module, and a Stratix-IV FPGA development board. Across a suite of 8 machine learning benchmarks, approximate memory compression obtains a 1.28× benefit in DRAM energy and a simultaneous 11.5% improvement in execution time for a small (<; 1.5%) loss in output quality.

Spiking neural networks (SNNs) represent the third generation of neural networks and are expected to enable new classes of machine learning applications. However, evaluating large-scale SNNs (e.g., of the scale of the visual cortex) on power-constrained systems requires significant improvements in computing efficiency. A unique attribute of SNNs is their event-driven nature-information is encoded as a series of spikes, and work is dynamically generated as spikes propagate through the network. Therefore, parallel implementations of SNNs on multi-cores and GPGPUs are severely limited by communication and synchronization overheads. Recent years have seen great interest in deep learning accelerators for non-spiking neural networks, however, these architectures are not well suited to the dynamic, irregular parallelism in SNNs. Prior efforts on specialized SNN hardware utilize spatial architectures, wherein each neuron is allocated a dedicated processing element, and large networks are realized by connecting multiple chips into a system. While suitable for large-scale systems, this approach is not a good match to size or cost constrained mobile devices. We propose PEASE, a Programmable Event-driven processor Architecture for SNN Evaluation. PEASE comprises of Spike Processing Units (SPUs) that are dynamically scheduled to execute computations triggered by a spike. Instructions to the SPUs are dynamically generated by Spike Schedulers (SSs) that utilize event queues to track unprocessed spikes and identify neurons that need to be evaluated. The memory hierarchy in PEASE is fully software managed, and the processing elements are interconnected using a two-tiered bus-ring topology matching the communication characteristics of SNNs. We propose a method to map any given SNN to PEASE such that the workload is balanced across SPUs and SPU clusters, while pipelining across layers of the network to improve performance. We implemented PEASE at the RTL level and synthesized it to IBM 45 technology. Across 6 SNN benchmarks, our 64-SPU configuration of PEASE achieves 7.1×-17.5× and 2.6×-5.8× speedups, respectively, over software implementations on an Intel Xeon E5-2680 CPU and NVIDIA Tesla K40C GPU. The energy reductions over the CPU and GPU are 71×-179× and 198×-467×, respectively.

Computed Tomography (CT) Image Reconstruction is an important technique used in a variety of domains, including medical imaging, electron microscopy, non-destructive testing and transportation security. Model-based Iterative Reconstruction (MBIR) using Iterative Coordinate Descent (ICD) is a CT algorithm that produces state-of-the-art results in terms of image quality. However, MBIR is highly computationally intensive and challenging to parallelize, and has traditionally been viewed as impractical in applications where reconstruction time is critical. We present the first GPU-based algorithm for ICD-based MBIR. The algorithm leverages the recently-proposed concept of SuperVoxels, and efficiently exploits the three levels of parallelism available in MBIR to better utilize the GPU hardware resources. We also explore data layout transformations to obtain more coalesced accesses and several GPU-specific optimizations for MBIR that boost performance. Across a suite of 3200 test cases, our GPU implementation obtains a geometric mean speedup of 4.43X over a state-of-the-art multi-core implementation on a 16-core iso-power CPU.

Most computer systems authenticate users only once at the time of initial login, which can lead to security concerns. Continuous authentication has been explored as an approach for alleviating such concerns. Previous methods for continuous authentication primarily use biometrics, e.g., fingerprint and face recognition, or behaviometrics, e.g., key stroke patterns. We describe CABA, a novel continuous authentication system that is inspired by and leverages the emergence of sensors for pervasive and continuous health monitoring. CABA authenticates users based on their BioAura, an ensemble of biomedical signal streams that can be collected continuously and non-invasively using wearable medical devices. While each such signal may not be highly discriminative by itself, we demonstrate that a collection of such signals, along with robust machine learning, can provide high accuracy levels. We demonstrate the feasibility of CABA through analysis of traces from the MIMIC-II dataset. We propose various applications of CABA, and describe how it can be extended to user identification and adaptive access control authorization. Finally, we discuss possible attacks on the proposed scheme and suggest corresponding countermeasures.

Designing reliable systems, while eschewing the high overheads of conventional fault tolerance techniques, is a critical challenge in the deeply scaled CMOS and post-CMOS era. To address this challenge, we leverage the intrinsic resilience of application domains such as multimedia, recognition, mining, search, and analytics where acceptable outputs are produced despite occasional approximate computations. We propose stochastic checkers (checkers designed using stochastic logic) as a new approach to performing error checking in an approximate manner at greatly reduced overheads. Stochastic checkers are inherently inaccurate and require long latencies for computation. To limit the loss in error coverage, as well as false positives (correct outputs flagged as erroneous), caused due to the approximate nature of stochastic checkers, we propose input permuted partial replicas of stochastic logic, which improves their accuracy with minimal increase in overheads. To address the challenge of long error detection latency, we propose progressive checking policies that provide an early decision based on a prefix of the checker's output bitstream. This technique is further enhanced by employing progressively accurate binary-to-stochastic converters. Across a suite of error-resilient applications, we observe that stochastic checkers lead to greatly reduced overheads (29.5% area and 21.5% power, on average) compared with traditional fault tolerance techniques while maintaining high coverage and very low false positives.

In this brief, we present a new approach to optimize energy efficiency of object detection tasks using semantic decomposition to build a hierarchical classification framework. We observe that certain semantic information like color/texture is common across various images in real-world data sets for object detection applications. We exploit these common semantic features to distinguish the objects of interest from the remaining inputs (nonobjects of interest) in a data set at a lower computational effort. We propose a 2-stage hierarchical classification framework, with increasing levels of complexity, wherein the first stage is trained to recognize the broad representative semantic features relevant to the object of interest. The first stage rejects the input instances that do not have the representative features and passes only the relevant instance to the second stage. Our methodology thus allows us to reject certain information at lower complexity and utilize the full computational effort of a network only on a smaller fraction of inputs resulting in energy-efficient detection.

Approximate computing is an emerging design paradigm that exploits the intrinsic ability of applications to produce acceptable outputs even when their computations are executed approximately. In this paper, we explore approximate computing for a key computation pattern, reduce-andrank (RnR), which is prevalent in a wide range of workloads, including video processing, recognition, search, and data mining. An RnR kernel performs a reduction operation (e.g., distance computation, dot product, and L1-norm) between an input vector and each of a set of reference vectors, and ranks the reduction outputs to select the top reference vectors for the current input. We propose three complementary approximation strategies for the RnR computation pattern. The first is interleaved reductionand-ranking, wherein the vector reductions are decomposed into multiple partial reductions and interleaved with the rank computation. Leveraging this transformation, we propose the use of intermediate reduction results and ranks to identify future computations that are likely to have a low impact on the output, and can, hence, be approximated. The second strategy, inputsimilarity-based approximation, exploits the spatial or temporal correlation of inputs (e.g., pixels of an image or frames of a video) to identify computations that are amenable to approximation. The third strategy, reference vector reordering, rearranges the order in which the reference vectors are processed such that vectors that are relatively more critical in evaluating the correct output, are processed at the beginning of RnR operation. The number of these critical reference vectors is usually small, which renders a substantial portion of the total computation to be amenable to approximation. These strategies address a key challenge in approximate computing-identification of which computations to approximate-and may be used to drive any approximation mechanism, such as computation skipping or precision scaling to realize performance and energy improvements. A second key challenge in approximate computing is that the extent to which computations can be approximated varies significantly from application to application, and across inputs for even a single application. Hence, input-adaptive approximation, or the ability to automatically modulate the degree of approximation based on the nature of each individual input, is essential for obtaining optimal energy savings. In addition, to enable quality configurability in RnR kernels, we propose a kernel-level quality metric that correlates well to application-level quality, and identify key parameters that can be used to tune the proposed approximation strategies dynamically. We develop a runtime framework that modulates the identified parameters during the execution of RnR kernels to minimize their energy while meeting a given target quality. To evaluate the proposed concepts, we designed quality-configurable hardware implementations of six RnR-based applications from the recognition, mining, search, and video processing application domains in 45-nm technology. Our experiments demonstrate a 1.13×-3.18× reduction in energy consumption with virtually no loss in output quality (<;0.5%) at the application level. The energy benefits further improve up to 3.43× and 3.9× when the quality constraints are relaxed to 2.5% and 5%, respectively.

The pervasiveness of IoT devices will usher an unprecedented growth in the amount of digital data produced and consumed. Realizing the rich class of applications enabled by IoT devices requires large-scale machine learning systems to analyze, organize and draw inferences from data. State-of-the-art machine learning algorithms are highly compute and data intensive, posing significant computational challenges across the spectrum of computing devices, from low-power client devices to the cloud. As benefits due to semiconductor technology scaling diminish, addressing the computational gap requires identifying new sources of computing efficiency. We highlight 3 approaches viz. machine learning accelerators, approximate computing and post-CMOS technologies that demonstrate significant promise in bridging the efficiency gap. Such technologies may be instrumental in enabling machine learning based IoT applications to enter the mainstream.

Approximate computing is an emerging paradigm to improve the efficiency of computing systems by leveraging the intrinsic resilience of applications to their computations being executed in an approximate manner. Prior efforts on approximate hardware design have largely focused on circuit-level techniques. We propose a new approach, clock overgating, for the design of approximate circuits at the Register Transfer Level (RTL). The key idea is to gate the clock signal to selected Flip-Flops (FFs) in the circuit, even during execution cycles in which the circuit functionality is sensitive to their state. This saves power in the clock tree, the FF itself and in its downstream logic, while a quality loss ensues if the erroneous FF state propagates to the circuit output. We develop a systematic methodology to identify an energy-efficient overgating configuration for any given circuit and quality constraint. Towards this end, we develop 3 key strategies --- significance-based overgating, grouping FFs into overgating islands, and utilizing internal signals of the circuit as triggers for overgating --- that efficiently prune the large space of possible overgating configurations. We evaluate clock overgating by designing approximate versions of 6 machine learning accelerators, and demonstrate energy benefits of 1.36× on average (and upto 1.80×) for negligible (<0.5%) loss in application quality (classification accuracy).

Neuromorphic algorithms are being increasingly deployed across the entire computing spectrum from data centers to mobile and wearable devices to solve problems involving recognition, analytics, search and inference. For example, large-scale artificial neural networks (popularly called deep learning) now represent the state-of-the art in a wide and ever-increasing range of video/image/audio/text recognition problems. However, the growth in data sets and network complexities have led to deep learning becoming one of the most challenging workloads across the computing spectrum. We posit that approximate computing can play a key role in the quest for energy-efficient neuromorphic systems. We show how the principles of approximate computing can be applied to the design of neuromorphic systems at various layers of the computing stack. At the algorithm level, we present techniques to significantly scale down the computational requirements of a neural network with minimal impact on its accuracy. At the circuit level, we show how approximate logic and memory can be used to implement neurons and synapses in an energy-efficient manner, while still meeting accuracy requirements. A fundamental limitation to the efficiency of neuromorphic computing in traditional implementations (software and custom hardware alike) is the mismatch between neuromorphic algorithms and the underlying computing models such as von Neumann architecture and Boolean logic. To overcome this limitation, we describe how emerging spintronic devices can offer highly efficient, approximate realization of the building blocks of neuromorphic computing systems.

Designing reliable systems, while eschewing the high overheads of conventional fault tolerance techniques, is a critical challenge in the deeply scaled CMOS and post-CMOS era. To address this challenge, we leverage the intrinsic resilience of application domains such as multimedia, recognition, mining, search, and analytics where acceptable outputs are produced despite occasional approximate computations. We propose stochastic checkers, wherein a stochastic logic based realization of the circuit is used as an error checker, and the original circuit's output is declared to be correct if it lies within a certain range of the checker's output. The key benefit of stochastic checkers is that the intrinsic compactness of stochastic logic leads to greatly reduced overheads. However, due to the approximate nature of stochastic circuits, errors that cause the output to be within a certain range of the correct value may not be detected (missed coverage). In addition, some correct outputs may be incorrectly flagged as erroneous (false positives). To limit the number of missed errors and false positives, we propose a technique that uses input permuted partial replicas of the stochastic logic to improve accuracy without greatly increasing the overheads. We also address the challenge of error detection latency (due to the bit-serial nature of stochastic logic) through progressive checking policies that produce an early decision based on a prefix of the checker's output bitstream. We evaluate stochastic checkers on hardware implementations of a suite of error-resilient applications, and demonstrate that they can lead to greatly reduced overheads (29.5% area and 21.5% power, on average) compared to traditional fault tolerance techniques, while achieving very high coverage (average of 99.5%) and very low false positives (average of 0.1%).

Computed Tomography (CT) Image Reconstruction is an important technique used in a wide range of applications, ranging from explosive detection, medical imaging to scientific imaging. Among available reconstruction methods, Model Based Iterative Reconstruction (MBIR) produces higher quality images and allows for the use of more general CT scanner geometries than is possible with more commonly used methods. The high computational cost of MBIR, however, often makes it impractical in applications for which it would otherwise be ideal. This paper describes a new MBIR implementation that significantly reduces the computational cost of MBIR while retaining its benefits. It describes a novel organization of the scanner data into super-voxels (SV) that, combined with a super-voxel buffer (SVB), dramatically increase locality and prefetching, enable parallelism across SVs and lead to an average speedup of 187 on 20 cores.

Extending double-gate FinFET scaling to sub-10nm technology regime requires device-engineering techniques for countering the rise of direct source to drain tunneling (DSDT), edge direct tunneling (EDT) and short channel effects (SCE) that degrade FinFET I-V characteristics. Symmetric underlap is effective for eliminating EDT, diminishing DSDT, and lowering the fringe component of gate capacitance. However, excessive symmetric underlap also lowers the on-current, which is mainly due to thermionic emission. In this work, it is demonstrated that at sub-10nm node, asymmetric underlapped FinFETs with slightly longer underlap toward drain side than source side are superior to symmetric underlapped FinFETs due to further improvement in Ion/Ioffand reduction in gate-to-drain capacitance. Using quantum mechanical device simulations, FinFETs with various degrees of underlap have been analyzed for improvement in I-V characteristics. A FinFET model for circuit simulations has been constructed that captures the major sub-10nm leakage components, namely, thermionic emission, DSDT, EDT, direct gate oxide tunneling and its associated components. By simulating a 10-stage NAND circuit and a LEON3 processor with interconnect parasitics using these devices, it is shown that asymmetric underlap instead of symmetric underlap in sub-10nm FinFETs can offer lower energy consumption with improved performance for near-threshold logic and higher energy-efficiency for super-threshold logic operation.

Spin-Transfer Torque MRAMs are attractive due to their non-volatility, high density, and zero leakage. However, STT-MRAMs suffer from poor reliability due to shared read and write paths. Additionally, conflicting requirements for data retention and writeability (both related to the energy barrier height of the storage device) makes design more challenging. Furthermore, the energy barrier height depends on the geometry of the storage. Any variations in the geometry of the storage device lead to variations in the energy barrier height. In order to address the poor reliability of STT-MRAMs, usage of Error Correcting Codes (ECC) has been proposed. Unlike traditional CMOS memory technologies, ECC is expected to correct both soft and hard errors in STT-MRAMs. To achieve acceptable yield with low write power, stronger ECC is required, resulting in increased number of encoded bits and degraded memory capacity. In this article, we propose Failure-aware ECC (FaECC), which masks permanent faults while maintaining the same correction capability for soft errors without increased number of encoded bits. Furthermore, we investigate the impact of process variations on run-time reliability of STT-MRAMs. In order to analyze the effectiveness of our methodology, we developed a cross-layer simulation framework that consists of device, circuit and array level analysis of STT-MRAM memory arrays. Our results show that using FaECC relaxes the requirements on the energy barrier height, which reduces the write energy and results in smaller access transistor size and memory array area.

Spin-transfer torque magnetic memory (STT-MRAM) has gained significant research interest due to its nonvolatility and zero standby leakage, near unlimited endurance, excellent integration density, acceptable read and write performance, and compatibility with CMOS process technology. However, several obstacles need to be overcome for STT-MRAM to become the universal memory technology. This paper first reviews the fundamentals of STT-MRAM and discusses key experimental breakthroughs. The state of the art in STT-MRAM is then discussed, beginning with the device design concepts and challenges. The corresponding bit-cell design solutions are also presented, followed by the STT-MRAM cache architectures suitable for on-chip applications.

Domain wall memory (DWM) is a recently developed spin-based memory technology in which several bits of data are densely packed into the domains of a ferromagnetic wire. DWM has shown great promise in enabling non-volatile memory with very high density and energy efficiency, and has been explored for secondary storage and off-chip memory. In this work, we explore the use of DWM within the on-chip cache hierarchy of general purpose computing platforms. Our work is motivated by the fact that DWMs enable much higher density compared to SRAM, DRAM, and other spin-based memory technologies such as STT-MRAM. However, DWMs also pose the unique challenge of serial access to the bits stored in a cell, leading to large and variable access latencies. In addition, DWMs share the inherent write inefficiency of other spin-based memories. We propose TapeCache, a DWM-based cache design that employs device, circuit, and architectural techniques to address these challenges. At the device level, we perform write optimization by employing a new write mechanism based on domain wall shifts to achieve fast, energy-efficient writes in DWM. At the circuit level, we propose different DWM bit-cell designs that are tailored to the distinct architectural requirements of different levels in the cache hierarchy. At the architecture level, we propose a new cache organization and suitable management policies that mitigate the performance penalty arising from serial access to bits in a DWM cell. We show that the holistic device-circuit-architecture co-design enables all the levels in the cache hierarchy to be realized using DWM and benefit from its improved density. Over a wide range of SPEC CPU 2006 benchmarks, TapeCache achieves an average energy improvement of 7.5x, with virtually identical performance and 7.8x improvement in area, compared to an iso-capacity SRAM cache. Compared to an iso-capacity STT-MRAM cache, TapeCache obtains 3.1x improvement in area and 2x average energy savings along with 1.1 percent performance improvement.

As CMOS technology begins to face significant scaling challenges, considerable research efforts are being directed to investigate alternative device technologies that can serve as a replacement for CMOS. Spintronic devices, which utilize the spin of electrons as the state variable for computation, have recently emerged as one of the leading candidates for post-CMOS technology. Recent experiments have shown that a nano-magnet can be switched by a spin-polarized current and this has led to a number of novel device proposals over the past few years. In this paper, we provide a review of different mechanisms that manipulate the state of a nano-magnet using current-induced spin-transfer torque and demonstrate how such mechanisms have been engineered to develop device structures for energy-efficient on-chip memory and logic.

We propose a design technique for embedding read-only memory (ROM) in spin-transfer torque MRAM (STT-MRAM) arrays by adding an extra bit-line in every column of the array. RAM and ROM data, which can be different, are stored in the same bitcell and the ROM capacity may be as large as the RAM capacity. Furthermore, our proposed ROM-embedding technique is applicable to any resistive memory technology in which the bit-cell topology is identical to that of the STT-MRAM bit-cell. An additional sense amplifier is required in the peripheral circuitry, hence we propose an area-optimized peripheral circuitry to minimize the total area penalty of embedding ROM. Our analysis reveals that the ROM may be embedded in the STT-MRAM array without area overhead and without any penalty in the performance of the memory as RAM. Furthermore, our simulations show that the embedded ROM may be used to accelerate applications that use lookup tables with as much as 30% improvement in instructions per cycle of a processor using ROM-embedded STT-MRAM for its L2 cache.

The scaling of integrated circuits into the nanometer regime has led to variations emerging as a primary design concern. Most efforts in the area of variation-tolerant design have focused on the physical, circuit, and logic levels of abstraction. However, inevitable increases in the magnitude of variations with scaling have elevated them to a design concern that must be addressed starting at the system level. We address the problem of analyzing the performance of system-onchip (SoC) architectures in the presence of variations. A modern SoC is a complex ensemble of components that are organized into multiple voltage and frequency domains or islands. The impact of variations on the clock frequencies of individual SoC components may be analyzed using existing tools, such as circuit-level statistical timing analysis. However, the key challenge that needs to be addressed is how to translate these component-level clock frequency distributions into a system-level performance distribution. This task is particularly complex and challenging due to the interdependences between components' execution, indirect effects of shared resources, and interactions between multiple system-level execution paths. We argue that an accurate variation-aware performance analysis requires Monte Carlo-based repeated system execution. We describe a framework variability emulation for SoC performance analysis (VESPA)-that leverages emulation to significantly speed up the performance analysis without sacrificing the generality and accuracy achieved by Monte Carlo-based simulation. We further improve the efficiency of VESPA by utilizing correlated sampling to reduce the number of samples needed for Monte Carlo simulations. We demonstrate the utility of VESPA by applying it to design variation-tolerant architectures for three example SoCs. Our experiments show the performance improvements of ~180× compared with the state-of-the-art hardware-software cosimulation tools and also underscore the potential of VESPA to enable variation-aware design and exploration at the system level.

Tomographic reconstruction, which involves computing a 3-D volume from its 2-D projections, is an important problem in imaging with wide-ranging applications, including medical scanners, electron microscopy, nondestructive testing, and transportation security. Model-based iterative reconstruction (MBIR) is a popular approach to 3-D reconstruction that has demonstrated the state-of-the-art reconstruction quality on several applications, and has been deployed in commercial healthcare systems. However, software implementations of MBIR on commodity general-purpose processors demonstrate poor performance due to its high compute and data requirements and cache unfriendly data access patterns. In this paper, we develop an efficient MBIR accelerator (EMBIRA) that achieves significant performance and energy improvement over software implementations. EMBIRA utilizes arrays of three types of specialized processing elements that match MBIR's computation patterns, and is further operated as a two-level nested pipeline to fully exploit the parallelism present in the algorithm. Another important source from which EMBIRA derives its efficiency is by constraining the sequence in which voxels1 in the 3-D volume are reconstructed. This enables better data reuse within the accelerator, thereby significantly reducing the number of off-chip memory accesses. To demonstrate the benefits of EMBIRA, we implemented a prototype on an Altera DE5 field-programmable gate array (FPGA) platform that includes an Altera Stratix V GX FPGA and DDR3 memory. Our implementation of EMBIRA, operating at 165 MHz, achieved 51.8× (5.8×) improvement in performance, and 355× (199×) improvement in energy, compared with optimized sequential (multithreaded) software implementations on a 48-core 2.3-GHz AMD Opteron-based server.

Implantable and wearable medical devices are used for monitoring, diagnosis, and treatment of an ever-increasing range of medical conditions, leading to an improved quality of life for patients. The addition of wireless connectivity to medical devices has enabled post-deployment tuning of therapy and access to device data virtually anytime and anywhere but, at the same time, has led to the emergence of security attacks as a critical concern. While cryptography and secure communication protocols may be used to address most known attacks, the lack of a viable secure connection establishment and key exchange mechanism is a fundamental challenge that needs to be addressed. We propose a vibration-based secure side channel between an external device (medical programmer or smartphone) and a medical device. Vibration is an intrinsically short-range, user-perceptible channel that is suitable for realizing physically secure communication at low energy and size/weight overheads. We identify and address key challenges associated with the vibration channel, and propose a vibration-based wakeup and key exchange scheme, named SecureVibe, that is resistant to battery drain attacks. We analyze the risk of acoustic eavesdropping attacks and propose an acoustic masking countermeasure. We demonstrate and evaluate vibration-based wakeup and key exchange between a smartphone and a prototype medical device in the context of a realistic human body model.

Spintronic memories are promising candidates for future on-chip storage due to their high density, non-volatility and near-zero leakage. However, the energy consumed by read and write operations presents a major challenge to their use as energy-efficient on-chip memory. Leveraging the ability of many applications to tolerate impreciseness in their underlying computations and data, we explore approximate storage as a new approach to improving the energy-efficiency of spintronic memories. We identify and characterize mechanisms in STT-MRAM bit-cells that provide favorable energy-quality trade-offs, i.e., disproportionate energy improvements at the cost of small probabilities of read/write failures. Based on these mechanisms, we design a quality-configurable memory array in which data can be stored to varying levels of accuracy based on application requirements. We integrate the quality-configurable array as a scratchpad in the memory hierarchy of a programmable vector processor and expose it to software by introducing quality-aware load/store instructions within the ISA. We evaluate the energy benefits of our proposal using a device-to-architecture modeling framework and demonstrate 40% and 19.5% improvement in memory energy and overall application energy respectively, for negligible (< 0.5%) quality loss across a suite of recognition and vision applications.

Diminishing benefits from technology scaling have pushed designers to look for new sources of computing efficiency. Multicores and heterogeneous accelerator-based architectures are a by-product of this quest to obtain improvements in the performance of computing platforms at similar or lower power budgets. In light of the need for new innovations to sustain these improvements, we discuss approximate computing, a field that has attracted considerable interest over the last decade. While the core principles of approximate computing---computing efficiently by producing results that are good enough or of sufficient quality---are not new and are shared by many fields from algorithm design to networks and distributed systems, recent e.orts have seen a percolation of these principles to all layers of the computing stack, including circuits, architecture, and software. Approximate computing techniques have also evolved from ad hoc and applicationspecific to more broadly applicable, supported by systematic design methodologies. Finally, the emergence of workloads such as recognition, mining, search, data analytics, inference and vision are greatly increasing the opportunities for approximate computing. We describe the vision and key principles that have guided our work in this area, and outline a holistic cross-layer framework for approximate computing.

Supervised machine-learning algorithms are used to solve classification problems across the entire spectrum of computing platforms, from data centers to wearable devices, and place significant demand on their computational capabilities. In this paper, we propose scalable-effort classifiers, a new approach to optimizing the energy efficiency of supervised machine-learning classifiers. We observe that the inherent classification difficulty varies widely across inputs in real-world datasets; only a small fraction of the inputs truly require the full computational effort of the classifier, while the large majority can be classified correctly with very low effort. Yet, state-of-the-art classification algorithms expend equal effort on all inputs, irrespective of their difficulty. To address this inefficiency, we introduce the concept of scalable-effort classifiers, or classifiers that dynamically adjust their computational effort depending on the difficulty of the input data, while maintaining the same level of accuracy. Scalable effort classifiers are constructed by utilizing a chain of classifiers with increasing levels of complexity (and accuracy). Scalable effort execution is achieved by modulating the number of stages used for classifying a given input. Every stage in the chain contains an ensemble of biased classifiers, where each biased classifier is trained to detect a single class more accurately. The degree of consensus between the biased classifiers' outputs is used to decide whether classification can be terminated at the current stage or not. Our methodology thus allows us to transform any given classification algorithm into a scalable-effort chain. We build scalable-effort versions of 8 popular recognition applications using 3 different classification algorithms. Our experiments demonstrate that scalable-effort classifiers yield 2.79x reduction in average operations per input, which translates to 2.3x and 1.5x improvement in energy for hardware and software implementations, respectively.

Spintronic memories are considered to be promising candidates for future on-chip memories due to their high density, nonvolatility, and near-zero leakage. However, they also face challenges such as high write energy and latency and limited read speed due to single-ended sensing. Further, the conflicting requirements of read and write operations lead to stringent design constraints that severely compromises their benefits. Recently, domain wall memory was proposed as a spintronic memory that has a potential for very high density by storing multiple bits in the domains of a ferromagnetic nanowire. While reliable operation of DWM memory with multiple domains faces many challenges, single-bit cells that utilize domain wall motion for writes have been experimentally demonstrated [Fukami et al. 2009]. This bit-cell, which we refer to as Domain Wall Memory with Shift-based Write (DWM-SW), achieves improved write efficiency and features decoupled read-write paths, enabling independent optimizations of read and write operations. However, these benefits are achieved at the cost of sacrificing the original goal of improved density. In this work, we explore multilevel storage as a new direction to enhance the density benefits of DWM-SW. At the device level, we propose a new device--multilevel DWM with shift-based write (ML-DWM-SW)--that is capable of storing 2 bits in a single device. At the circuit level, we propose a ML-DWM-SW based bit-cell design and layout. The ML-DWM-SW bit-cell incurs no additional area overhead compared to the DWM-SW bit-cell despite storing an additional bit, thereby achieving roughly twice the density. However, it requires a two-step write operation and has data-dependent read and write energies, which pose unique challenges. To address these issues, we propose suitable architectural optimizations: (i) intra-word interleaving and (ii) bit encoding. We design “all-spin” cache architectures using the proposed ML-DWM-SW bit-cell for both general purpose processors as well as general purpose graphics processing units (GPGPUs). We perform an iso-capacity replacement of SRAM with spintronic memories and study the energy and area benefits at iso-performance conditions. For general purpose processors, the ML-DWM-SW cache achieves 10X reduction in energy and 4.4X reduction in cache area compared to an SRAM cache and 2X and 1.7X reduction in energy and area, respectively, compared to an STT-MRAM cache. For GPGPUs, the ML-DWM-SW cache achieves 5.3X reduction in energy and 3.6X area reduction compared to SRAM and 3.5X energy reduction and 1.9X area reduction compared to STT-MRAM.

As CMOS nears the end of the projected scaling roadmap, significant effort has been devoted to the search for new materials and devices that can realize memory and logic. Spintronics, which uses the spin of electrons to represent and manipulate information, is one of the promising directions for the post-CMOS era. While the potential of spintronic memories is relatively well known, realizing logic remains an open and critical challenge. All spin logic (ASL) is a recently proposed logic style that realizes Boolean logic using spin-transfer-torque devices based on the principle of nonlocal spin torque. ASL has advantages such as density, nonvolatility, and low operating voltage. However, it also suffers from drawbacks such as low speed and static power dissipation. Recent work has shown that, in the context of simple arithmetic circuits (adders and multipliers), the efficiency of ASL can be greatly improved using techniques that utilize its unique characteristics. An evaluation of ASL across a broad range of circuits, considering the known optimization techniques, is an important next step in determining its viability. In this paper, we propose a systematic methodology for the synthesis of ASL circuits. Our methodology performs various optimizations that benefit ASL, such as intracycle power gating, stacking of ASL nanomagnets, and fine-grained logic pipelining. We utilize the proposed methodology to evaluate the suitability of ASL implementations for a wide range of benchmarks, viz., random combinational and sequential logic, digital signal processing circuits, and the Leon SPARC3 general-purpose processor. Based on our evaluation, we identify: 1) the large current requirement of nanomagnets at fast switching speeds; 2) the static power dissipation in the all-metallic devices; and 3) the short spin flip length in interconnects as key bottlenecks that limit the competitiveness of ASL. We further evaluate the impact of various potential improvements in device parameters on the efficiency of ASL.

Machine learning is being used in a wide range of application domains to discover patterns in large datasets. Increasingly, the results of machine learning drive critical decisions in applications related to healthcare and biomedicine. Such health-related applications are often sensitive, and thus, any security breach would be catastrophic. Naturally, the integrity of the results computed by machine learning is of great importance. Recent research has shown that some machine-learning algorithms can be compromised by augmenting their training datasets with malicious data, leading to a new class of attacks called poisoning attacks. Hindrance of a diagnosis may have life-threatening consequences and could cause distrust. On the other hand, not only may a false diagnosis prompt users to distrust the machine-learning algorithm and even abandon the entire system but also such a false positive classification may cause patient distress. In this paper, we present a systematic, algorithm-independent approach for mounting poisoning attacks across a wide range of machine-learning algorithms and healthcare datasets. The proposed attack procedure generates input data, which, when added to the training set, can either cause the results of machine learning to have targeted errors (e.g., increase the likelihood of classification into a specific class), or simply introduce arbitrary errors (incorrect classification). These attacks may be applied to both fixed and evolving datasets. They can be applied even when only statistics of the training dataset are available or, in some cases, even without access to the training dataset, although at a lower efficacy. We establish the effectiveness of the proposed attacks using a suite of six machine-learning algorithms and five healthcare datasets. Finally, we present countermeasures against the proposed generic attacks that are based on tracking and detecting deviations in various accuracy metrics, and benchmark their effectiveness.

Due to limitations of cooling methods such as using fan and heat sink, dynamic thermal management (DTM) is being widely adopted to manage the temperature of computing systems. However, application of DTM can reduce the system performance and thereby affect the quality of real-time applications. Real-time video encoding, which has high computational need and hard deadlines, is a commonly used application that can be severely affected by the usage of DTM. We study the effect of DTM on a widely used H.264 video encoder and formulate a multidimensional optimization problem to maximize video quality and minimize bit rate while ensuring that the video encoder can run in real time in spite of DTM effects. We model the effects of adapting encoding parameters on video quality, bit rate, and encoder speed. We propose a dynamic application adaptation method to efficiently solve the optimization problem by optimally adapting the encoding parameters in response to DTM effects. In addition, we show that the proposed dynamic application adaptation method would reduce the need for cooling methods such as forced convection cooling. We implement the proposed approach on an Intel® Core™ 2 Duo platform where dynamic voltage and frequency scaling (DVFS) is used for DTM. Our measurements with several videos reveal that when DTM is applied, the video quality is affected significantly. However, using the proposed adaptation algorithm, the encoder can run in real time, and the quality loss is minimized with only a marginal increase in the bit rate.

Dynamic thermal management (DTM) is commonly used to ensure reliable and safe operation in modern computing systems. DTM techniques are based on slowing down or shutting down parts of a system; hence, they effectively reduce system performance and thereby adversely impact applications. In this paper, we focus on real-time applications in which degradation in performance translates to a loss in application quality, and address the problem of quality-optimized DTM, wherein the objective of DTM is to satisfy specified temperature constraints while optimizing application quality metrics. We first introduce a new DTM method called dynamic work scaling (DWS), which is based on modulating an application's computational requirements. Next, we observe that application quality and platform temperature are effectively determined by two key parameters, viz., the application's computational requirement and the platform's computing capacity, and formulate the relationship between them. Finally, we propose a quality-optimized DTM based on joint dynamic work and voltage/frequency scaling (DWVFS). We have implemented the proposed DTM technique and evaluated it for two applications: 1) H.264 video encoding and 2) turbo decoding. Our results demonstrate that DWVFS can provide superior results in terms of application quality compared with both DVFS and DWS-based DTM at identical temperature constraints.

Multithreaded programs are commonly written and optimized for homogeneous multi-core processors assuming equal performance from all the cores. This assumption greatly simplifies the partitioning and balancing of an application's workload across threads; however, it no longer holds when the frequencies of the cores differ due to within-die variations, leading to a degradation in performance. We observe that, in addition to the frequency of the core that it executes on, the performance of a thread is also dependent on the share of shared system resources, such as last-level cache, that it receives. We propose variation-aware cache partitioning as an approach to redress the variation-induced imbalance in the execution times of threads, thereby improving the performance of multi-threaded programs. We discuss the challenges involved in realizing our proposal, including synchronization (e.g., barriers) across threads, which results in faster threads being limited by slower threads, the complex and non-linear relationship between a thread's performance and the cache capacity allocated to it, and the fact that different program phases, can respond quite differently to varying cache capacity. We propose a runtime scheme to perform spatio-temporal cache partitioning while considering both chip characteristics (frequency variations) and program characteristics. We evaluate the proposed technique by applying it to an ensemble of variation-impacted multi-cores executing multi-threaded programs from the PARSEC and SPEC-OMP suites, and demonstrate that it results in an average performance improvement of 15% by mitigating the impact of frequency variations.

Many applications produce acceptable results when their underlying computations are executed in an approximate manner. For such applications, approximate circuits enable hardware implementations that exhibit improved efficiency for a given quality. Previous efforts have largely focused on the design of approximate combinational logic blocks such as adders and multipliers. In practice, however, designers are concerned with the quality of outputs generated by a sequential circuit after several cycles of computation, rather than an embedded combinational block. We propose ASLAN (Automatic methodology for Sequential Logic ApproximatioN), the first effort towards the synthesis of approximate sequential circuits. Given a sequential circuit and an output quality constraint, ASLAN creates an approximate version of the circuit that consumes lower energy, while meeting the specified quality bound. The key challenges in approximating sequential circuits are (i) to model how errors due to approximations are generated, re-circulate through the combinational logic over multiple cycles of operation, and eventually impact quality of the final output, and (ii) to select the most beneficial approximations, i.e., those that result in higher energy savings for smaller impact on quality. ASLAN addresses the first challenge by constructing a virtual Sequential Quality Constraint Circuit (SQCC) and utilizing formal verification techniques to ensure that the selected approximations meet the quality constraint. To address the second challenge, ASLAN identifies combinational blocks in the sequential circuit that are amenable to approximation, generates local quality-energy trade-off curves for them, and uses a gradient-descent approach to iteratively approximate the entire sequential circuit. We used ASLAN to automatically synthesize approximate versions of ten sequential benchmarks, resulting in energy reductions of 1.20X-2.44X for tight quality constraints, and 1.32X-4.42X for moderate quality constraints. We present case studies of using the approximate circuits generated by ASLAN in two popular applications - MPEG Encoding and K-Means Clustering - obtaining 1.32X energy savings with 0.5% PSNR degradation, and 1.26X energy savings with 0.8% increase in mean cluster radius, respectively.

General-purpose Graphics Processing Units (GPGPUs) are widely used for executing massively parallel workloads from various application domains. Feeding data to the hundreds to thousands of cores that current GPGPUs integrate places great demands on the memory hierarchy, fueling an ever-increasing demand for on-chip memory. In this work, we propose STAG, a high density, energy-efficient GPGPU cache hierarchy design using a new spintronic memory technology called Domain Wall Memory (DWM). DWMs inherently offer unprecedented benefits in density by storing multiple bits in the domains of a ferromagnetic nanowire, which logically resembles a bit-serial tape. However, this structure also leads to a unique challenge that the bits must be sequentially accessed by performing “shift” operations, resulting in variable and potentially higher access latencies. To address this challenge, STAG utilizes a number of architectural techniques : (i) a hybrid cache organization that employs different DWM bit-cells to realize the different memory arrays within the GPGPU cache hierarchy, (ii) a clustered, bit-interleaved organization, in which the bits in a cache block are spread across a cluster of DWM tapes, allowing parallel access, (iii) tape head management policies that predictively configure DWM arrays to reduce the expected number of shift operations for subsequent accesses, and (iv) a shift aware promotion buffer (SaPB), in which accesses to the DWM cache are predicted based on intra-warp locality, and locations that would incur a large shift penalty are promoted to a smaller buffer. Over a wide range of benchmarks from the Rodinia, ISPASS and Parboil suites, STAG achieves significant benefits in performance (12.1% over SRAM and 5.8% over STT-MRAM) and energy (3.3X over SRAM and 2.6X over STT-MRAM).

Recognition and Mining are emerging application domains that are becoming prevalent across the entire spectrum of computing platforms, and place very high demands on their capabilities. We propose a Stochastic Recognition and Mining processor (StoRM), which uses Stochastic Computing (SC) to efficiently realize computational kernels from these domains. Stochastic computing facilitates compact, power-efficient realization of arithmetic operations by representing and processing information as pseudo-random bit-streams. However, the overhead of conversion between representations, and the exponential relationship between precision and bit-stream length, are key challenges that limit the efficiency of stochastic designs. The proposed architecture for StoRM consists of a 2D array of Stochastic Processing Elements (StoPEs) with a streaming memory hierarchy, enabling binary-to-stochastic conversion to be amortized across rows or columns of StoPEs. We propos vector processing and segmented stochastic processing in the StoPEs to mitigate the unfavorable tradeoff between precision and bit-stream length. We also exploit the compactness of StoPEs to increase parallelism, thereby improving performance and energy efficiency. Finally, leveraging the resilience of RM applications to approximations in their computations, we design StoRM to support modulation of the stochastic bit-stream length, and utilize this capability to to optimize energy for a desired output quality. StoRM achieves 2-3X energy-delay improvements over a conventional design without sacrificing output quality, and upto 10X (20X) improvements when upto 5% (10%) loss in output quality is allowed. Our results also demonstrate that the proposed design techniques greatly enhance the applicability and benefits of stochastic computing.

Variations have emerged as one of the most significant challenges facing the design of integrated circuits in nanoscale technologies. As a consequence, variation tolerant design has become essential at all levels of design abstraction.

Deep Learning Networks (DLNs) are bio-inspired large-scale neural networks that are widely used in emerging vision, analytics, and search applications. The high computation and storage requirements of DLNs have led to the exploration of various avenues for their efficient realization. Concurrently, the ability of emerging post-CMOS devices to efficiently mimic neurons and synapses has led to great interest in their use for neuromorphic computing.

Neuromorphic algorithms, which are comprised of highly complex, large-scale networks of artificial neurons, are increasingly used for a variety of recognition, classification, search and vision tasks. However, their computational and energy requirements can be quite high, and hence their energy-efficient implementation is of great interest.

Implantable and wearable medical devices (IWMDs) are commonly used for diagnosing, monitoring, and treating various medical conditions. A general trend in these medical devices is toward increased functional complexity, software programmability, and connectivity to body area networks (BANs). However, as IWMDs become more “intelligent,” they also become less trustworthy-less reliable and more prone to attacks. Various shortcomings-hardware failures, software errors, wireless attacks, malware and software exploits, and side-channel attacks-could undermine the trustworthiness of IWMDs and BANs. While these concerns have been recognized for some time, recent demonstrations of security attacks on commercial products, e.g., pacemakers and insulin pumps, have elevated medical device security from the realm of theoretical possibility to an immediate concern. The trustworthiness of IWMDs must be addressed aggressively and proactively due to the potential for catastrophic consequences. Conventional fault tolerance and information security solutions, e.g., redundancy and cryptography, that have been employed in general-purpose and embedded computing systems cannot be applied to many IWMDs due to their extreme size and power constraints and unique usage models. While several recent efforts address defense of IWMDs against specific security attacks, a holistic strategy that considers all concerns and types of threats is required. This paper discusses trustworthiness concerns in IWMDs and BANs through a comprehensive identification and analysis of potential threats and, for each threat, provides a discussion of the merits and inadequacies of current solutions.

Applications from several application domains exhibit the property of inherent application resilience, offering entirely new avenues for performance and power optimization by relaxing the conventional requirement of exact (numerical or Boolean) equivalence between the specification and hardware implementation. We propose scalable effort hardware as a design approach to tap the reservoir of application resilience and translate it into highly efficient hardware implementations. The first tenet of the scalable effort design approach is to identify mechanisms at each level of design abstraction (circuit, architecture, and algorithm) that can be used to vary the computational effort expended toward generation of the correct (exact) result, and to expose these mechanisms as control knobs in the implementation. These scaling mechanisms can be utilized to achieve improved energy efficiency while maintaining an acceptable (and often, near identical) level of quality of the overall result. The second tenet of the scalable effort design approach is that fully exploiting the potential of application resilience requires synergistic cross-layer optimization of scaling mechanisms identified at different levels of design abstraction. We have implemented an energy-efficient recognition and mining (RM) processor based on the proposed scalable effort design approach. Results from the execution of support vector machine training and classification, generalized learning vector quantization training, and k-means clustering on the scalable effort RM processor show that it can achieve energy reductions of 1.2×-5× with negligible impact on output quality, and 2.2×-50× with moderate loss in output quality, across various data sets. Our results also establish that cross-layer optimization across different scaling mechanisms leads to higher energy savings (1.4×-2× on an average) for a given output quality compared with each of the individual techniques.

Approximate computing is an emerging design paradigm that enables highly efficient hardware and software implementations by exploiting the inherent resilience of applications to in-exactness in their computations. Previous work in this area has demonstrated the potential for significant energy and performance improvements, but largely consists of ad hoc techniques that have been applied to a small number of applications. Taking approximate computing closer to mainstream adoption requires (i) a deeper understanding of inherent application resilience across a broader range of applications (ii) tools that can quantitatively establish the inherent resilience of an application, and (iii) methods to quickly assess the potential of various approximate computing techniques for a given application. We make two key contributions in this direction. Our primary contribution is the analysis and characterization of inherent application resilience present in a suite of 12 widely used applications from the domains of recognition, data mining, and search. Based on this analysis, we present several new insights into the nature of resilience and its relationship to various key application characteristics. To facilitate our analysis, we propose a systematic framework for Application Resilience Characterization (ARC) that (a) partitions an application into resilient and sensitive parts and (b) characterizes the resilient parts using approximation models that abstract a wide range of approximate computing techniques. We believe that the key insights that we present can help shape further research in the area of approximate computing, while automatic resilience characterization frameworks such as ARC can greatly aid designers in the adoption approximate computing.

Recovery based design (RBD) is a promising approach for the design of energy-efficient circuits under variations. RBD instruments circuits with mechanisms to identify and correct timing violations, thereby allowing reduced guard bands or design margins. In addition, RBD enables aggressive voltage overscaling to a point where timing errors occur even under nominal conditions. A major barrier to the widespread adoption of RBD is that traditional design practices and synthesis tools result in circuits with so-called"path walls", leading to an explosion in the number of timing errors beyond a certain critical operating voltage. To alleviate this effect, previous techniques focused on combinational circuit optimizations such as sizing, use of dual Vth cells, re-structuring, etc. to favorably reshape the path delay distribution. However, these techniques are limited by the inherent sequential structure of the circuit, which defines the boundaries of the combinational logic.

Implantable and wearable medical devices (IWMDs) are commonly used for diagnosing, monitoring, and treating various medical conditions. A general trend in IWMDs is towards increased functional complexity, software programmability, and connectivity to body area networks (BANs). However, as medical devices become more "intelligent," they also become less trustworthy -- less reliable and more vulnerable to malicious attacks. Various shortcomings -- hardware failures, software errors, wireless attacks, malware and software exploits, and side-channel attacks -- could undermine the trustworthiness of IWMDs and BANs. The trustworthiness of IWMDs must be addressed aggressively and proactively due to the potential for catastrophic consequences. While some recent efforts address the defense of IWMDs against specific security attacks, a holistic strategy that considers all concerns and types of threats is required. This paper discusses trustworthiness concerns in IWMDs and BANs through a comprehensive identification and analysis of potential threats and, for each threat, provides a discussion of the merits and inadequacies of current solutions.

Many applications are inherently resilient to inexactness or approximations in their underlying computations. Approximate circuit design is an emerging paradigm that exploits this inherent resilience to realize hardware implementations that are highly efficient in energy or performance. In this work, we propose Substitute-And-SIMplIfy (SASIMI), a new systematic approach to the design and synthesis of approximate circuits. The key insight behind SASIMI is to identify signal pairs in the circuit that assume the same value with high probability, and substitute one for the other. While these substitutions introduce functional approximations, if performed judiciously, they result in some logic to be eliminated from the circuit while also enabling downsizing of gates on critical paths (simplification), resulting in significant power savings. We propose an automatic synthesis framework that performs substitution and simplification iteratively, while ensuring that a user-specified quality constraint is satisfied. We extend the proposed framework to perform automatic synthesis of quality configurable circuits that can dynamically operate at different accuracy levels depending on application requirements. We used SASIMI to automatically synthesize approximate and quality configurable implementations of a wide range of arithmetic units (Adders, Multipliers, MAC), complex data paths (SAD, FFT butterfly, Euclidean distance) and ISCAS85 benchmarks, using various error metrics such as error rate and average error magnitude. The synthesized approximate circuits demonstrate power improvements of 10%–28% for tight error constraints, and 30%–60% for relaxed error constraints. The quality configurable circuits obtain between 14%–40% improvement in energy in the approximate mode, while incurring no energy overheads in the accurate mode.

Spin-based memories are promising candidates for future on-chip memories due to their high density, non-volatility, and very low leakage. However, the high energy and latency of write operations in these memories is a major challenge. In this work, we explore a new approach - shift based write - that offers a fast and energy-efficient alternative to performing writes in spin-based memories. We propose DWM-TAPESTRI, a new all-spin cache design that utilizes Domain Wall Memory (DWM) with shift based writes at all levels of the cache hierarchy. The proposed write scheme enables DWM to be used, for the first time, in L1 caches and in tag arrays, where the inefficiency of writes in spin memories has traditionally precluded their use. At the circuit level, we propose bit-cell designs utilizing shift-based writes, which are tailored to the differing requirements of different levels in the cache hierarchy. We also propose pre-shifting as an architectural technique to hide the latency of shift operations that is inherent to DWM. We performed a systematic device-circuit-architecture evaluation of the proposed design. Over a wide range of SPEC 2006 benchmarks, DWM-TAPESTRI achieves 8.2X improvement in energy and 4X improvement in area, with virtually identical performance, compared to an iso-capacity SRAM cache. Compared to an iso-capacity STT-MRAM cache, the proposed design achieves around 1.6X improvement in both area and energy under iso-performance conditions.

Summary form only given. With the explosion in digital data, computing platforms are increasingly being used to execute applications (such as web search, data analytics, sensor data processing, recognition, mining, and synthesis) for which “correctness” is defined as producing results that are good enough, or of sufficient quality. Such applications invariably demonstrate a high degree of inherent resilience to their underlying computations being executed in an approximate manner. This inherent resilience is due to several factors including redundancy in the input data, the statistical nature of the computations themselves, and the acceptability (often, inevitability) of less-than-perfect results. Approximate computing is an approach to designing systems that are more efficient, by leveraging the inherent resilience of applications. We will outline a range of approximate computing techniques that we have developed from software to architecture to circuits, which have shown promising results. We conclude with a discussion of some of the challenges that need to be addressed to facilitate a broader adoption of approximate computing.

Spin-based devices promise to revolutionize computing platforms by enabling high-density, low-leakage memories. However, stringent tradeoffs between critical design metrics such as read and write stability, reliability, density, performance and energy-efficiency limit the efficiency of conventional spin-transfer-torque devices and bit-cells. We propose a new multi-level cell design with domain wall magnets (DWM-MLC) that significantly improves upon the read/write performance, density, and write energy consumption of conventional spin memories. The fundamental design tradeoff between read and write operations are addressed in DWM-MLC by decoupling the read and write paths, thereby allowing separate optimization for reads and writes. A thicker tunneling oxide is used for higher readability, while a domain-wall-shift (DWS) based write mechanism is used to improve write speed and energy. The storage of multiple bits per cell and the ability to use smaller transistors lead to a net improvement in density compared to conventional spin memories. We perform a systematic evaluation of DWM-MLC at different levels of design abstraction. At the circuit level, DWM-MLC achieves 2X improvement in density, read energy and read latency over its 1-bit counterpart. We evaluate an “all-spin” cache hierarchy that uses DWM-MLC for both L1 and L2, resulting in 4.4X (1.7X) area improvement and 10X (2X) energy reduction at iso-performance over SRAM (STT-MRAM).

Approximate computing leverages the intrinsic resilience of applications to inexactness in their computations, to achieve a desirable trade-off between efficiency (performance or energy) and acceptable quality of results. To broaden the applicability of approximate computing, we propose quality programmable processors, in which the notion of quality is explicitly codified in the HW/SW interface, i.e., the instruction set. The ISA of a quality programmable processor contains instructions associated with quality fields to specify the accuracy level that must be met during their execution. We show that this ability to control the accuracy of instruction execution greatly enhances the scope of approximate computing, allowing it to be applied to larger parts of programs. The micro-architecture of a quality programmable processor contains hardware mechanisms that translate the instruction-level quality specifications into energy savings. Additionally, it may expose the actual error incurred during the execution of each instruction (which may be less than the specified limit) back to software.

Low power is an imperative requirement for portable multimedia devices employing various signal processing algorithms and architectures. In most multimedia applications, human beings can gather useful information from slightly erroneous outputs. Therefore, we do not need to produce exactly correct numerical outputs. Previous research in this context exploits error resiliency primarily through voltage overscaling, utilizing algorithmic and architectural techniques to mitigate the resulting errors. In this paper, we propose logic complexity reduction at the transistor level as an alternative approach to take advantage of the relaxation of numerical accuracy. We demonstrate this concept by proposing various imprecise or approximate full adder cells with reduced complexity at the transistor level, and utilize them to design approximate multi-bit adders. In addition to the inherent reduction in switched capacitance, our techniques result in significantly shorter critical paths, enabling voltage scaling. We design architectures for video and image compression algorithms using the proposed approximate arithmetic units and evaluate them to demonstrate the efficacy of our approach. We also derive simple mathematical models for error and power consumption of these approximate adders. Furthermore, we demonstrate the utility of these approximate adders in two digital signal processing architectures (discrete cosine transform and finite impulse response filter) with specific quality constraints. Simulation results indicate up to 69% power savings using the proposed approximate adders, when compared to existing implementations using accurate adders.

Several current and emerging applications do not have a unique result for a given input; rather, functional correctness is defined in terms of output quality. Recently proposed design techniques exploit the inherent resilience of such applications and achieve improved efficiency (energy or performance) by foregoing correct execution of all the constituent computations. Hardware and software systems that are thus designed may be viewed as scalable effort systems, since they offer the capability to modulate the effort that they expend towards computation, thereby allowing for trade-offs between output quality and efficiency. We propose the concept of Dynamic Effort Scaling (DES), which refers to dynamic management of the control knobs that are exposed by scalable effort systems. We argue the need for DES by observing that the degree of resilience often varies significantly across applications, across datasets, and even within a dataset. We propose a general conceptual framework for DES by formulating it as a feedback control problem, wherein the scaling mechanisms are regulated with the goal of maintaining output quality at or above a specified limit. We present an implementation of Dynamic Effort Scaling for recognition and mining applications and evaluate it for the support vector machines and K-means clustering algorithms under various application scenarios and datasets. Our results clearly demonstrate the benefits of the proposed approach---statically setting the scaling mechanisms leads to either significant error overshoot or significant opportunities for energy savings left on the table unexploited. In contrast, DES is able to effectively regulate the output quality while maximally exploiting the time-varying resiliency in the workload.

Data center-scale clusters are evolving towards heterogeneous hardware for power, cost, differentiated price-performance, and other reasons. MapReduce is a well-known programming model to process large amount of data on data center-scale clusters. Most MapReduce implementations have been designed and optimized for homogeneous clusters. Unfortunately, these implementations perform poorly on heterogeneous clusters (e.g., on a 90-node cluster that contains 10 Xeon-based servers and 80 Atom-based servers, Hadoop performs worse than on 10-node Xeon-only or 80-node Atom-only homogeneous sub-clusters for many of our benchmarks). This poor performance remains despite previously proposed optimizations related to management of straggler tasks. In this paper, we address MapReduce's poor performance on heterogeneous clusters. Our first contribution is that the poor performance is due to two key factors: (1) the non-intuitive effect that MapReduce's built-in load balancing results in excessive and bursty network communication during the Map phase, and (2) the intuitive effect that the heterogeneity amplifies load imbalance in the Reduce computation. Our second contribution is Tarazu, a suite of optimizations to improve MapReduce performance on heterogeneous clusters. Tarazu consists of (1) Communication-Aware Load Balancing of Map computation (CALB) across the nodes, (2) Communication-Aware Scheduling of Map computation (CAS) to avoid bursty network traffic and (3) Predictive Load Balancing of Reduce computation (PLB) across the nodes. Using the above 90-node cluster, we show that Tarazu significantly improves performance over a baseline of Hadoop with straightforward tuning for hardware heterogeneity.

Iterative-convergence algorithms are frequently used in a variety of domains to build models from large data sets. Cluster implementations of these algorithms are commonly realized using parallel programming models such as MapReduce. However, these implementations suffer from significant performance bottlenecks, especially due to large volumes of network traffic resulting from intermediate data and model updates during the iterations. To address these challenges, we propose partitioned iterative convergence (PIC), a new approach to programming and executing iterative convergence algorithms on frameworks like MapReduce. In PIC, we execute the iterative-convergence computation in two phases - the best-effort phase, which quickly produces a good initial model and the top-off phase, which further refines this model to produce the final solution. The best-effort phase iteratively performs the following steps: (a) partition the input data and the model to create several smaller, model-building sub-problems, (b) independently solve these sub-problems using iterative convergence computations, and (c) merge solutions of the sub-problems to create the next version of the model. This partitioned, loosely coupled execution of the computation produces a model of good quality, while drastically reducing network traffic due to intermediate data and model updates. The top-off phase further refines this model by employing the original iterative-convergence computation on the entire (un-partitioned) problem until convergence. However, the number of iterations executed in the top-off phase is quite small, resulting in a significant overall improvement in performance. We have implemented a library for PIC on top of the Hadoop MapReduce framework, and evaluated it using five popular iterative-convergence algorithms (Page Rank, K-Means clustering, neural network training, linear equation solver and image smoothing). Our evaluations on clusters ranging from 6 nodes to 256 nodes demonstrate a 2.5X-4X speedup compared to conventional implementations using Hadoop.

Parameter variations have emerged as a significant threat to continued CMOS scaling in the nanometer regime. Due to increasing performance penalties associated with worst-case design, recovery based design has emerged as a promising approach for dealing with the impact of variations. Previous work has applied recovery based design at the circuit and micro-architecture levels of abstraction. In this work, we address the problem of designing variation-tolerant SoCs using the recovery based design paradigm. We demonstrate that a monolithic implementation of recovery based design fails to scale for large SoCs. We propose the concept of recovery islands, wherein each island consists of one or more SoC components that can recover independent of the rest of the SoC, and demonstrate how our proposal can be easily realized via minor changes to a traditional SoC design flow. We study the tradeoffs involved in applying recovery based design at the system level. We demonstrate that it is critical to account for (i) the inherent diversity of the error-voltage profiles among various components in an SoC, and (ii) the impact of error recovery in a component on overall system performance. We then propose a systematic recovery-based SoC design methodology that partitions a given SoC into recovery islands and also computes the optimal operating points for each island, taking into account the various system level trade-offs involved. We evaluate our framework on three different SoC designs, an 802.11b MAC processor, an MPEG encoder and a Wireless Video Capture system and demonstrate an average of 32% energy savings over conventional designs.

Spin-transfer torque magnetic RAM (STT MRAM) has emerged as a promising candidate for on-chip memory in future computing platforms. We present a cross-layer (device-circuit-architecture) approach to energy-efficient cache design using STT MRAM. At the device and circuit levels, we consider different genres of MTJs and bitcells, and evaluate their impact on the area, energy and performance of caches. In addition, we propose micro-architectural techniques viz. sequential cache read and partial cache line update, which exploit the non-volatility of STT MRAM to further improve energy efficiency of STT MRAM caches. A detailed comparison of STT MRAM caches with SRAM-based caches is also presented. Our results indicate that the proposed optimizations significantly enhance the efficiency of STT MRAM for designing lower level caches.

Approximate computing has emerged as a new design paradigm that exploits the inherent error resilience of a wide range of application domains by allowing hardware implementations to forsake exact Boolean equivalence with algorithmic specifications. A slew of manual design techniques for approximate computing have been proposed in recent years, but very little effort has been devoted to design automation.

This paper presents a methodology to model and analyze the functional behavior of logic circuits under timing variations. In the framework, first a Time Accurate Model (TAM) of the circuit is constructed. The TAM represents the behavior of the circuit in the functional domain under a discrete time model. Afterwards, Variation Logic is inserted to apply the timing variations. Moreover, the circuit TAM is enhanced by Time Control (TC) logic to model the circuit frequency. We apply the proposed methodology to analyze a circuit or an approximate circuit under timing variations as well as to analyze a circuit under timing-induced errors for approximate computing.

Summary form only given. This work proposes an approach to model and evaluate the functional behavior of logic circuits under timing variations. In the approach, first we construct a Time Accurate Model (TAM) of the circuit to represent its timing behavior in a functional domain under a discrete time model. Then, timing variations are applied by using Variation Logic (VL).

Domain Wall Memory (DWM) is a recently developed spin-based memory technology in which several bits of data are densely packed into the domains of a ferromagnetic wire. DWM has shown great promise in enabling non-volatile memory with unprecedented density and high energy efficiency. In this work, we propose TapeCache, a first attempt to employ DWMs as last-level caches in general purpose computing platforms. DWMs enable much higher density compared to SRAM, DRAM, and other spin-based memory technologies such as STT-MRAM. However, they also pose unique challenges such as serial access to the bits stored in a DWM cell, leading to variable access latencies. We propose a novel circuit-architecture co-design for TapeCache, consisting of (i) a multi-port DWM macro-cell optimized for read operations considering the asymmetry in applications' read/write characteristics, and (ii) a new cache organization and suitable management policies that mitigate the performance penalty arising from serial access to bits in a macro-cell. Over a wide range of SPEC 2006 benchmarks, TapeCache achieves 7.8X improvement in area, an average energy improvement of 7.3X, and an average performance improvement of 1.2% compared to an iso-capacity SRAM cache. Compared to an iso-capacity STT-MRAM cache, TapeCache obtains 2.3X improvement in area and 1.4X average energy savings with virtually identical performance.

Pipelining is a well-known approach to increasing parallelism and performance. We address the problem of software pipelining for heterogeneous parallel platforms that consist of different multi-core and many-core processing units. In this context, pipelining involves two key steps -- partitioning an application into stages and mapping and scheduling the stages onto the processing units of the heterogeneous platform. We show that the inter-dependency between these steps is a critical challenge that must be addressed in order to achieve high performance. We propose an Automatic Heterogeneous Pipelining framework (AHP) that generates an optimized pipelined implementation of a program from an annotated unpipelined specification. Across three complex applications (image classification, object detection, and document retrieval) and two heterogeneous platforms (Intel Xeon multi-core CPUs with Intel MIC and NVIDIA GPGPU accelerators), AHP achieves a throughput improvement of up to 1.53x (1.37x on average) over a heterogeneous baseline that exploits data and task parallelism.

Many information security attacks exploit vulnerabilities in “trusted” and privileged software executing on the system, such as the operating system (OS). On the other hand, most security mechanisms provide no immunity to security-critical user applications if vulnerabilities are present in the underlying OS. While technologies have been proposed that facilitate isolation of security-critical software, they require either significant computational resources and are hence not applicable to many resource-constrained embedded systems, or necessitate extensive redesign of the underlying processors and hardware. In this work, we propose INVISIOS: a lightweight, minimally intrusive hardware-software architecture to make the execution of security-critical software invisible to the OS, and hence protected from its vulnerabilities. The INVISIOS software architecture encapsulates the security-critical software into a self-contained software module. While this module is part of the kernel and is run with kernel-level privileges, its code, data, and execution are transparent to and protected from the rest of the kernel. The INVISIOS hardware architecture consists of simple add-on hardware components that are responsible for bootstrapping the secure core, ensuring that it is exercised by applications in only permitted ways, and enforcing the isolation of its code and data. We implemented INVISIOS by enhancing a full-system emulator and Linux to model the proposed software and hardware enhancements, and applied it to protect a commercial cryptographic library. Our experiments demonstrate that INVISIOS is capable of facilitating secure execution at very small overheads, making it suitable for resource-constrained embedded systems and systems-on-chip.

Software-defined radio (SDR) implements a radio system in software that executes on a programmable processor. The components of SDR, such as the filters, amplifiers, and modulators, can be easily reconfigured to adapt to the operating environment and user preferences. However, the flexibility of radio reconfiguration brings along the serious security concern of malicious modification of software in the SDR system, leading to radio malfunction and interference with other users' communications. Both the SDR device and the network need to be protected from such malicious radio reconfiguration. In this article, a new architecture targeted at protecting SDR devices from malicious reconfiguration is proposed. The architecture is based on robust separation of the radio operation environment and user application environment, through the use of virtualization. A new radio middleware layer is designed to securely intercept all attempts to reconfigure the radio, and a security policy monitor checks the target configuration against security policies that represent the interests of various parties. Even if the operating system in the user application environment is compromised, the proposed architecture can ensure secure reconfiguration in the radio operation environment. We have prototyped the proposed secure SDR architecture using VMware and the GNU Radio toolkit and demonstrate that overheads incurred by the architecture are small and tolerable. Therefore, we believe that the proposed solution could be applied to address secure SDR reconfiguration in both general-purpose and embedded computing systems.

Virtualization is a rapidly evolving technology that can be used to provide a range of benefits to computing systems, including improved resource utilization, software portability, and reliability. Virtualization also has the potential to enhance security by providing isolated execution environments for different applications that require different levels of security. For security-critical applications, it is highly desirable to have a small trusted computing base (TCB), since it minimizes the surface of attacks that could jeopardize the security of the entire system. In traditional virtualization architectures, the TCB for an application includes not only the hardware and the virtual machine monitor (VMM), but also the whole management operating system (OS) that contains the device drivers and virtual machine (VM) management functionality. For many applications, it is not acceptable to trust this management OS, due to its large code base and abundance of vulnerabilities. For example, consider the "computing-as-a-service” scenario where remote users execute a guest OS and applications inside a VM on a remote computing platform. It would be preferable for many users to utilize such a computing service without being forced to trust the management OS on the remote platform. In this paper, we address the problem of providing a secure execution environment on a virtualized computing platform under the assumption of an untrusted management OS. We propose a secure virtualization architecture that provides a secure runtime environment, network interface, and secondary storage for a guest VM. The proposed architecture significantly reduces the TCB of security-critical guest VMs, leading to improved security in an untrusted management environment. We have implemented a prototype of the proposed approach using the Xen virtualization system, and demonstrated how it can be used to facilitate secure remote computing services. We evaluate the performance penalties incurred by the proposed architecture, and demonstrate that the penalties are minimal.

In this paper, we address the problem of variation-aware selection of voltage levels for system-on-chips (SoCs) that are organized into multiple frequency and voltage domains. Conventionally, the voltage levels for each domain, as well as the mapping between frequencies and voltages, are determined without considering variations. In the presence of variations, these choices are often suboptimal since the frequency versus voltage characteristics vary from one SoC instance to another and across different voltage domains within an instance. We present a two-pronged approach to address this problem. First, we propose breaking the conventional fixed coupling between voltage levels and frequencies and demonstrate that performing this association based on the characteristics of individual chip instances can lead to significant improvements in power and performance. Second, we show that voltage levels that are computed while accounting for variations can lead to further improvements. We present a methodology to determine a set of discrete voltage levels in a variation-aware manner by generating and quantizing the ideal voltage distribution for a given SoC. Our experiments on an 802.11 MAC processor SoC indicate that the proposed techniques lead to significant improvements in power and performance characteristics in the presence of variations. We obtained an improvement of up to 68% in parametric yield (number of chips meeting power and performance targets) compared to conventional voltage scaling.

The disaggregation of the semiconductor design and manufacturing process has resulted in integrated circuit (IC) piracy becoming an important concern to the semiconductor industry. To address this concern, we present a method for achieving robust IC protection at the circuit level through direct injection of process variations. In the proposed approach, the circuit is enhanced by including process variation (PV) sensors and modifying the design during synthesis to inject the outputs of the PV sensors into the logic at carefully selected nodes. As a result, each fabricated IC is rendered inoperative unless a unique per-chip unlocking key is applied. After fabrication, the response of each chip to specially generated test vectors is used to construct the correct per-chip unlocking key. We propose a methodology to automatically modify circuits by identifying pairs of injection and correction points, while avoiding delay penalty and minimizing area overheads. We propose the use of a cryptographic preprocessor to separate the internal key used from the external unlocking key, further enhancing the resistance of the proposed approach against several attacks. Our methodology is scalable to the key size and requires only a small area overhead to achieve reasonable security levels (e.g., 7% for 64-bit keys in a 8 k gate design). We analyze the security of the proposed technique under several attack scenarios and believe that it offers robust protection against a wide range of attacks.

Several recently proposed design techniques leverage the inherent error resilience of applications for improved efficiency (energy or performance). Hardware and software systems that are thus designed may be viewed as "scalable effort systems", since they offer the capability to modulate the effort that they expend towards computation, thereby allowing for tradeoffs between output quality and efficiency.

We address the problem of analyzing the performance of System-on-chip (SoC) architectures in the presence of variations. Existing techniques such as gate-level statistical timing analysis compute the distributions of clock frequencies of SoC components. However, we demonstrate that translating component-level characteristics into a system-level performance distribution is a complex and challenging problem due to the inter-dependencies between components' execution, indirect effects of shared resources, and interactions between multiple system-level “execution paths”. We argue that accurate variation-aware system-level performance analysis requires repeated system execution, which is prohibitively slow when based on simulation. Emulation is a widely-used approach to drastically speedup system-level simulation, but it has not been hitherto applied to variation analysis. We describe a framework - Variability Emulation for SoC Performance Analysis (VESPA) - that adapts and applies emulation to the problem of variation aware SoC performance analysis. The proposed framework consists of three phases: component variability characterization, variation-aware emulation setup, and Monte-carlo driven emulation. We demonstrate the utility of the proposed framework by applying it to design variation-aware architectures for two example SoCs - an 802.11 MAC processor and an MPEG encoder. Our results suggest that variability emulation has great potential to enable variation-aware design and exploration at the system level.

Approximate computing techniques that exploit the inherent resilience in algorithms through mechanisms such as voltage over-scaling (VOS) have gained significant interest. In this work, we focus on meta-functions that represent computational kernels commonly found in application domains that demonstrate significant inherent resilience, namely Multimedia, Recognition and Data Mining. We propose design techniques (dynamic segmentation with multi-cycle error compensation, and delay budgeting for chained data path components) which enable the hardware implementations of these meta-functions to scale more gracefully under voltage over-scaling. The net effect of these design techniques is improved accuracy (fewer and smaller errors) under a wide range of over-scaled voltages. Results based on extensive transistor-level simulations demonstrate that the optimized meta-function implementations consume up to 30% less energy at iso-error rates, while achieving upto 27% lower error rates at iso-energy when compared to their baseline counterparts. System-level simulations for three applications, motion estimation, support vector machine based classification and k-means based clustering are also presented to demonstrate the impact of the improved meta-functions at the application level.

Approximate computing, which refers to a class of techniques that relax the requirement of exact equivalence between the specification and implementation of a computing system, has attracted significant interest in recent years. We propose a systematic methodology, called MACACO, for the Modeling and Analysis of Circuits for Approximate Computing. The proposed methodology can be utilized to analyze how an approximate circuit behaves with reference to a conventional correct implementation, by computing metrics such as worst-case error, average-case error, error probability, and error distribution. The methodology applies to both timing-induced approximations such as voltage over-scaling or over-clocking, and functional approximations based on logic complexity reduction. The first step in MACACO is the construction of an equivalent untimed circuit that represents the behavior of the approximate circuit at a given voltage and clock period. Next, we construct a virtual error circuit that represents the error in the approximate circuit's output for any given input or input sequence. Finally, we apply conventional Boolean analysis techniques (SAT solvers, BDDs) and statistical techniques (Monte-Carlo simulation) in order to compute the various metrics of interest. We have applied the proposed methodology to analyze a range of approximate designs for datapath building blocks. Our results show that MACACO can help a designer to systematically evaluate the impact of approximate circuits, and to choose between different approximate implementations, thereby facilitating the adoption of such circuits for approximate computing.

We present a runtime framework for the execution of work-loads represented as parallel-operator directed acyclic graphs (PO-DAGs) on heterogeneous multi-core platforms. PO-DAGs combine coarse-grained parallelism at the graph level with fine-grained parallelism within each node, lending naturally to exploiting the intra --- and inter-processing element parallelism present in heterogeneous platforms. We identify four important criteria - Suitability, Locality, Availability and Criticality (SLAC) --- and show that all these criteria must be considered by a heterogeneous runtime framework in order to achieve good performance under varying application and platform characteristics.

The incidence of malicious code and software vulnerability exploits on embedded platforms is constantly on the rise. Yet, little effort is being devoted to combating such threats to embedded systems. Moreover, adapting security approaches designed for general-purpose systems generally fails because of the limited processing capabilities of their embedded counterparts. In this work, we evaluate a malware and software vulnerability exploit defense framework for embedded systems. The proposed framework extends our prior work, which defines two isolated execution environments: a testing environment, wherein an untrusted application is first tested using dynamic binary instrumentation (DBI), and a real environment, wherein a program is monitored at runtime using an extracted behavioral model, along with a continuous learning process. We present a suite of software and hardware optimizations to reduce the overheads induced by the defense framework on embedded systems. Software optimizations include the usage of static analysis, complemented with DBI in the testing environment (i.e., a hybrid software analysis approach is used). Hardware optimizations exploit parallel processing capabilities of multiprocessor systems-on-chip. We have evaluated the defense framework and proposed optimizations on the ARM-Linux operating system. Experiments demonstrate that our framework achieves a high coverage of considered security threats, with acceptable performance penalties (the average execution time of applications goes up to 1.68X, considering all optimizations, which is much smaller than the 2.72X performance penalty when no optimizations are used).

Virtualization is a rapidly evolving technology that can be used to provide a range of benefits to computing systems, including improved resource utilization, software portability, and reliability. For security-critical applications, it is highly desirable to have a small trusted computing base (TCB), since it minimizes the surface of attacks that could jeopardize the security of the entire system. In traditional virtualization architectures, the TCB for an application includes not only the hardware and the virtual machine monitor (VMM), but also the whole management operating system (OS) that contains the device drivers and virtual machine (VM) management functionality. For many applications, it is not acceptable to trust this management OS, due to its large code base and abundance of vulnerabilities. In this paper, we address the problem of providing a secure execution environment on a virtualized computing platform under the assumption of an untrusted management OS. We propose a secure virtualization architecture that provides a secure run-time environment, network interface, and secondary storage for a guest VM. The proposed architecture significantly reduces the TCB of security-critical guest VMs, leading to improved security in an untrusted management environment. We have implemented a prototype of the proposed approach using the Xen virtualization system, and demonstrated how it can be used to facilitate secure remote computing services. We evaluate the performance penalties incurred by the proposed architecture, and demonstrate that the penalties are minimal.

With the advent of mainstream parallel computing, applications can obtain better performance only by scaling to platforms with larger numbers of cores. This is widely considered to be a very challenging problem due to the difficulty of parallel programming and the bottlenecks to efficient parallel execution. Inspired by how networking and storage systems have scaled to handle very large volumes of packet traffic and persistent data, we propose a new approach to the design of scalable, parallel computing platforms. For decades, computing platforms have gone to great lengths to ensure that every computation specified by applications is faithfully executed. While this design philosophy has remained largely unchanged, applications and the basic characteristics of their workloads have changed considerably. A wide range of existing and emerging computing workloads have an inherent forgiving nature. We therefore argue that adopting a best-effort service model for various software and hardware components of the computing platform stack can lead to drastic improvements in scalability. Applications are cognizant of the best-effort model, and separate their computations into those that may be executed on a best-effort basis and those that require the traditional execution guarantees. Best-effort computations may be exploited to simply reduce the computing workload, shape it to be more suitable for parallel execution, or execute it on unreliable hardware components. Guaranteed computations are realized either through an overlay software layer on top of the best-effort substrate, or through the use of application-specific strategies. We describe a system architecture for a best-effort computing platform, provide examples of parallel software and hardware that embody the best-effort model, and show that large improvements in performance and energy efficiency are possible through the adoption of this approach.

Algorithms from several interesting application domains exhibit the property of inherent resilience to "errors" from extrinsic or intrinsic sources, offering entirely new avenues for performance and power optimization by relaxing the conventional requirement of exact (numerical or Boolean) equivalence between the specification and hardware implementation.

It is widely believed that most Recognition and Mining (RM) workloads can easily take advantage of parallel computing platforms because these workloads are dataparallel. Contrary to this popular belief, we present RM workloads for which conventional parallel implementations scale poorly on multi-core platforms. We identify off-chip memory transfers and overheads in the parallel runtime library as the primary bottlenecks that limit speedups to be well below the ideal linear speedup expected for data-parallel workloads. To achieve improved parallel scalability, we identify and exploit several interesting properties of RM workloads - sparsity of model updates, low spatial locality among model updates, presence of insignificant computations, and the inherently self-healing nature of these algorithms in the presence of errors. We leverage these domain-specific characteristics to improve parallel scalability in two major ways. First, we utilize data dependency relaxation to simultaneously execute multiple training iterations in parallel, thereby increasing the granularity of the parallel tasks and significantly lowering the run-time overheads of fine-grained threading. Second, we strategically drop selected computations that are insignificant to the accuracy of the final result, but account for a disproportionately large amount of off-chip (memory and coherence) traffic. Through the application of the proposed techniques, we show that much higher speedups are possible on multi-core platforms for two important RM applications - document search using semantic indexing, and eye detection in images using generalized learning vector quantization. On an 8-core platform, we achieve application speedups of 5.5X and 7.3X compared to sequential implementations. Compared to conventional parallel implementations of these applications using Intel's TBB, the proposed techniques result in 4.3X and 4.9X improvements. Although the optimized parallel implementations are not numerically equivalent to the sequential implementations, the output quality is shown to be comparable (and within the margin of variation produced by processing the input data in a different order). We also explore error mitigation techniques that can be used to ensure that the accuracy of results is not compromised.

Security is rapidly becoming a critical factor in the IC design and test cycle. To provide higher levels of assurance and trust to designers, manufacturers and end users of integrated circuits (ICs), there is a need to integrate security measures during design, validation, and manufacturing test covering all aspects of security threats in hardware. These threats include secret information leakage, malicious hardware modifications in an untrusted foundry, hardware IP piracy and reverse engineering efforts. This session will have three presentations focusing on the design, validation, and test challenges for attack-resistant secure hardware systems.

The operational characteristics of integrated circuits in nanoscale semiconductor technology are expected to be increasingly affected by variations in the manufacturing process and the operating environment. In this paper, we address the problem of incorporating the effects of variations into system-level power analysis tools. We consider both manufacturing-induced (die-to-die and within-die) variations in device characteristics, and operation-induced dynamic variations in on-chip temperature. To motivate our work, we first analyze the impact of variations on the power consumption of an example System-on-Chip (SoC). We show how simple extensions of current approaches to system-level power estimation (based on spreadsheets or system-level simulation) are not well-suited to performing variation-aware power-estimation. We propose a system-level power estimation methodology that accurately and efficiently analyzes the impact of variations on SoC power consumption. The proposed methodology combines fast trace analysis, power-state based leakage modeling, efficient thermal analysis, and Monte Carlo sampling to generate SoC power distributions, and power variability traces over time. The key benefit of the methodology is that it captures critical inter-dependencies between component workload profiles, leakage power, and variations in temperature and device parameters, while avoiding time-consuming iterative simulations. Our implementation of the proposed methodology within an in-house system-level power estimation framework indicates speedups of up to 4 orders of magnitude with negligible loss in accuracy as compared to Monte Carlo techniques. We also illustrate the application of our analysis framework can be used to explore a new class of “variation-aware” system-level power management techniques.

Software defined radio (SDR) is a rapidly evolving technology which implements some functional modules of a radio system in software executing on a programmable processor. SDR provides a flexible mechanism to reconfigure the radio, enabling networked devices to easily adapt to user preferences and the operating environment. However, the very mechanisms that provide the ability to reconfigure the radio through software also give rise to serious security concerns such as unauthorized modification of the software, leading to radio malfunction and interference with other users' communications. Both the SDR device and the network need to be protected from such malicious radio reconfiguration. In this paper, we propose a new architecture to protect SDR devices from malicious reconfiguration. The proposed architecture is based on robust separation of the radio operation environment and user application environment through the use of virtualization. A secure radio middleware layer is used to intercept all attempts to reconfigure the radio, and a security policy monitor checks the target configuration against security policies that represent the interests of various parties. Therefore, secure reconfiguration can be ensured in the radio operation environment even if the operating system in the user application environment is compromised. We have prototyped the proposed secure SDR architecture using VMware and the GNU Radio toolkit, and demonstrate that the overheads incurred by the architecture are small and tolerable. Therefore, we believe that the proposed solution could be applied to address SDR security concerns in a wide range of both general-purpose and embedded computing systems.

Recognition and mining (RM) applications are an emerging class of computing workloads that will be commonly executed on future multi-core and many-core computing platforms. The explosive growth of input data and the use of more sophisticated algorithms in RM applications will ensure, for the foreseeable future, a significant gap between the computational needs of RM applications and the capabilities of rapidly evolving multi- or many-core platforms. To address this gap, we propose a new parallel programming model that inherently embodies the notion of best-effort computing, wherein the underlying parallel computing environment is not expected to be perfect. The proposed best-effort programming model leverages three key characteristics of RM applications: (1) the input data is noisy and it often contains significant redundancy, (2) computations performed on the input data are statistical in nature, and (3) some degree of imprecision in the output is acceptable. As a specific instance of the best-effort parallel programming model, we describe an “iterative-convergence” parallel template, which is used by a significant class of RM applications. We show how best-effort computing can be used to not only reduce computational workload, but to also eliminate dependencies between computations and further increase parallelism. Our experiments on an 8-core machine demonstrate a speed-up of 3.5X and 4.3X for the K-means and GLVQ algorithms, respectively, over a conventional parallel implementation. We also show that there is almost no material impact on the accuracy of results obtained from best-effort implementations in the application context of image segmentation using K-means and eye detection in images using GLVQ.

Graphics processing units (GPUs) have emerged as important players in the transition of the computing industry from sequential to multi- and many-core computing. We propose a software framework for execution of domain-specific parallel templates on GPUs, which simultaneously raises the abstraction level of GPU programming and ensures efficient execution with forward scalability to large data sizes and new GPU platforms. To achieve scalable and efficient GPU execution, our framework focuses on two critical problems that have been largely ignored in previous efforts-processing large data sets that do not fit within the GPU memory, and minimizing data transfers between the host and GPU. Our framework takes domain-specific parallel programming templates that are expressed as parallel operator graphs, and performs operator splitting, of-fload unit identification, and scheduling of off-loaded computations and data transfers between the host and the GPU, to generate a highly optimized execution plan. Finally, a code generator produces a hybrid CPU/GPU program in accordance with the derived execution plan, that uses lower-level frameworks such as CUDA. We have applied the proposed framework to templates from the recognition domain, specifically edge detection kernels and convolutional neural networks that are commonly used in image and video analysis. We present results on two different GPU platforms from NVIDIA (a Tesla C870 GPU computing card and a GeForce 8800 graphics card) that demonstrate 1.7-7.8X performance improvements over already accelerated baseline GPU implementations. We also demonstrate scalability to input data sets and application memory footprints of 6 GB and 17 GB, respectively, on GPU platforms with only 768 MB and 1.5 GB of memory.

The power characteristics of system-on-chips (SoCs) in nanoscale technologies are significantly impacted by manufacturing process variations, making it important to consider these effects during system-level power analysis and optimization. In this paper, we identify and address the problem of designing effective power management schemes in the presence of such variations. In particular, we demonstrate that conventional power management schemes, which are designed without considering the impact of variations, can result in substantial power wastage. We therefore propose two approaches to variation-aware power management, namely, design-specific and chip-specific approaches. In each of these approaches, the goal is to consider the impact of variations while deriving power management policy parameters, in order to optimize metrics that are relevant under variations. We motivate and introduce these metrics, and present both exact and heuristic approaches to optimize them. The methods are designed and implemented in the context of two power management frameworks, namely an ideal oracle-based framework and a timeout-based framework. We experimentally evaluate the proposed ideas using an ARM946 processor core model. For the oracle-based framework, variation-aware power management can result in improvements of upto 59% for$\mu +\sigma$, and upto 55% for 95th percentile of the energy distribution, over conventional power management schemes that do not consider variations. For the timeout-based framework, we obtain reductions of upto 43% in$\mu+\sigma$and upto 55% in the 99th percentile of the energy distribution.

Cryptographic accelerators and security processors are often used in embedded systems in order to enable enhanced security without significantly impacting performance or power consumption. However, realizing the performance promised by them requires the design of efficient software architectures for crypto offloading (offloading cryptographic operations from a host processor). In this paper, we describe an efficient software architecture for IPSec crypto offloading on a state-of-the-art mobile application processor system-on-chip (SoC) that includes a programmable security processor. We consider both user-space and kernel-space implementations of IPSec, compare their performance, and identify factors that limit the efficiency of crypto offloading. We describe two optimizations, called protocol-level crypto offloading and adaptive crypto offloading, which further improve the performance of IPSec by (i) offloading higher granularity computations to reduce the crypto offloading overheads, and (ii) using crypto offloading judiciously based on the trade-off between the savings in processing cycles vs. the overhead of communication with the security processor. We measure the performance of our implementation of IPSec crypto offloading using a commercial network protocol stack on the mobile application processor SoC, under a wide range of workloads. Our results indicate that efficient crypto offloading can result in application-level improvements of up to 10.6X in data rate and up to 5X in latency, enabling IPSec to be used for emerging high-bandwidth and interactive mobile applications.

Trusted platforms have been proposed as a promising approach to enhance the security of general-purpose computing systems. However, for many resource-constrained embedded systems, the size and cost overheads of a separate Trusted Platform Module (TPM) chip are not acceptable. One alternative is to use a software-based TPM, which implements TPM functions using software that executes in a protected execution domain on the embedded processor itself. However, since many embedded systems have limited processing capabilities and are battery-powered, it is also important to ensure that the computational and energy requirements for SW-TPMs are acceptable. In this article, we perform an evaluation of the energy and execution time overheads for a SW-TPM implementation on a handheld appliance (Sharp Zaurus PDA). We characterize the execution time and energy required by each TPM command through actual measurements on the target platform. We observe that for most commands, overheads are primarily due to the use of 2,048-bit RSA operations that are performed within the SW-TPM. In order to alleviate SW-TPM overheads, we evaluate the use of Elliptic Curve Cryptography (ECC) as a replacement for the RSA algorithm specified in the Trusted Computing Group (TCG) standards. In addition, we also evaluate the overheads of using the SW-TPM in the context of various end applications, including trusted boot of the Linux operating system (OS), a secure VoIP client, and a secure Web browser. Furthermore, we analyze the computational workload involved in running SW-TPM commands using ECC. We then present a suite of hardware and software enhancements to accelerate these commands—generic custom instructions and exploitation of parallel processing capabilities in multiprocessor systems-on-chip (SoCs). We report results of evaluating the proposed architectures on a commercial embedded processor (Xtensa from Tensilica). Through uniprocessor and multiprocessor optimizations, we could achieve speed-ups of up to 5.71X for individual TPM commands.

Software-based self-test (SBST) has recently emerged as an effective methodology for the manufacturing test of processors and other components in systems-on-chip (SoCs). By moving test related functions from external resources to the SoC's interior, in the form of test programs that the on-chip processor executes, SBST significantly reduces the need for high-cost, big-iron testers, and enables high-quality at-speed testing and performance binning. Thus far, SBST approaches have focused almost exclusively on the functional (programmer visible) components of the processor. In this paper, we analyze the challenges involved in testing an important component of modern processors, namely, the pipelining logic, and propose a systematic SBST methodology to address them. We first demonstrate that SBST programs that only target the functional components of the processor are not sufficient to test the pipeline logic, resulting in a significant loss of overall processor fault coverage. We further identify the testability hotspots in the pipeline logic using two fully pipelined reduced instruction set computer (RISC) processor benchmarks. Finally, we develop a systematic SBST methodology that enhances existing SBST programs so that they comprehensively test the pipeline logic. The proposed methodology is complementary to previous SBST techniques that target functional components (their results can form the input to our methodology, and thus we can reuse the test development effort behind preexisting SBST programs). We automate our methodology and incorporate it in an integrated software environment (developed using Java, XML, and archC) for the automatic generation of SBST routines for microprocessors. We apply the methodology to the two complex benchmark RISC processors with respect to two fault models: stuck-at fault model and transition delay fault model. Simulation results show that our methodology provides significant improvements for the two fault models, both for the entire processor (12% fault coverage improvement on average) and for the pipeline logic itself (19% fault coverage improvement on average), compared to a conventional SBST approach.

The on-chip communication architecture is a primary determinant of overall performance in complex system-on-chip (SoC) designs. Since the communication requirements of SoC components can vary significantly over time, communication architectures that dynamically detect and adapt to such variations can substantially improve system performance. In this paper, we propose Flexbus, a new architecture that can efficiently adapt thelogicalconnectivityof the communication architecture and the components connected to it. Flexbus achieves this by dynamically controlling both the communication architecture topology, as well as the mapping of SoC components to the communication architecture. This is achieved through newdynamicbridgeby-pass, andcomponentremappingtechniques. In this paper, we introduce these techniques, describe how they can be realized within modern on-chip buses, and discuss policies for run-time reconfiguration of Flexbus-based architectures.The techniques underlying Flexbus are general, and are applicable to a variety of bus standards. We have implemented Flexbus as an extension of the popular AMBA AHB bus, and have evaluated it using a commercial design flow. We report on experiments conducted to analyze its area, timing, and performance under a wide variety of system-level traffic profiles. We have applied Flexbus to two example SoC designs: 1) an IEEE 802.11 MAC processor and 2) an UMTS turbo decoder. Our results show that Flexbus provides gains of up to 34.55 % in application data-rates over conventional architectures, with negligible area overhead and a 3.2% penalty in clock period.

The power characteristics of System-on-chips (SoCs) in nanoscale technologies are significantly impacted by process variations, making it important to consider these effects during system-level power analysis and optimization. In this paper, we identify and address the problem of designing effective power management schemes in the presence of such variations. In particular, we demonstrate that conventional power management schemes, which are designed without considering the impact of variations, can result in substantial power wastage. We therefore propose two approaches to variation-aware power management, namely, design-specific and chip-specific approaches. In each of these approaches, the goal is to consider the impact of variations while deriving the values of parameters that govern popular power management policies. The policy parameters are derived so as to optimize metrics that are relevant under variations. We motivate and introduce these metrics, and use a combination of analytical and empirical approaches to optimize them. We experimentally evaluate the proposed ideas in the context of an ARM processor core, and demonstrate that variation-aware power management can result in improvements of upto 59% in μ + σ of the energy distribution, and upto 55% for the 95th percentile of the energy distribution, with respect to conventional power management schemes that do not consider variations.

Fast and accurate power analysis is a critical requirement for designing power-efficient System-on-Chips (SoCs). Current system-level power analysis tools are incapable of generating power estimates under real-life workloads within an acceptable amount of time, even for moderately complex SoCs. Our work addresses this problem by borrowing on emulation, which is a widely used technique to accelerate functional verification. Unfortunately, hardware emulation of all the necessary functions for full SoC power analysis is likely to be infeasible for most systems, due to constraints on emulation capacity, and the lack of emulation-ready, synthesizable models for some SoC components early in the design process.

This paper presents an automatic methodology to perform characterization-based high-level software macromodeling. Macromodeling-based estimation can be used to speed up simulation-based software-performance/energy estimation. High-level software macromodels, which are significantly faster to evaluate than detailed models of the target hardware platform, can be used instead of the latter during simulation, resulting in orders-of-magnitude simulation speedup. However, in order to realize this potential, significant challenges need to be overcome in both the generation and use of macromodels-including how to identify the parameters to be used in the macromodel, how to define the template function to which the macromodel is fitted, etc. The authors' methodology attempts to address the aforementioned issues. Given a subprogram to be macromodeled for execution time and/or energy consumption, the proposed methodology automates the steps of parameter identification, data collection through detailed simulation, macromodel template selection, and fitting. The authors propose a novel technique to identify potential macromodel parameters and perform data collection, which draws from the concept of data-structure serialization used in distributed programming. They utilize symbolic-regression techniques to concurrently filter out irrelevant macromodel parameters, construct a macromodel function, and derive the optimal coefficient values to minimize fitting error. Experiments with several realistic benchmarks suggest that the proposed methodology improves estimation accuracy and enables wide applicability of macromodeling to complex embedded software, while realizing its potential for estimation speedup

Software energy estimation is a critical step in the design of energy-efficient embedded systems. Instruction-level simulation techniques, despite several advances, remain too slow for iterative use in system-level exploration and for embedded systems with high software complexity. In this paper, we propose a methodology called hybrid simulation, which combines instruction set simulation with selective native execution (execution of some parts of the program directly on the simulation host computer). Hybrid simulation attempts to overcome the disadvantages of instruction-level simulation (low speed) and pure native execution (estimation accuracy and inapplicability to target-dependent code) while exploiting their advantages. In order to perform the energy estimation for natively executed subprograms, hybrid simulation leverages previously developed techniques for software energy macromodeling. This paper identifies and addresses the main challenges involved in hybrid simulation, including control/data transfer and memory synchronization between instruction set simulation and native execution domains, estimation errors due to macromodeling, and simulation overheads for switching between domains. We present an automatic tool flow for hybrid simulation, which analyzes a given program and selects functions for native execution in order to achieve maximum estimation efficiency while limiting estimation error. Our tool generates native ldquodrop-inrdquo modules that are linked into the instruction set simulator (ISS) and simulation ldquostubsrdquo that are linked with the application to facilitate hybrid simulation. We have applied the proposed hybrid simulation methodology to a variety of embedded software programs, resulting in average speedups of 25.2x (maximum of 124) and estimation error of only 3% (maximum of 6%), as compared to one of the fastest publicly available ISSs.

Systems-on-chip often use hardware accelerators or coprocessors to provide efficient implementations of application-specific functions. The emergence of extensible processor cores with supporting design tools has given designers with another viable alternative, namely, the use of application-specific custom instructions. Coprocessors and custom instructions can be viewed as two different forms of hardware acceleration that are applicable at different levels of granularity and offer differing tradeoffs. Classical hardware/software-partitioning techniques and application-specific instruction-set design tools address the individual problems of coprocessor generation and custom-instruction addition. However, given a complex application, it is not clear which design choice (coprocessors or custom instructions or a combination) will result in better performance, area, or power consumption. We demonstrate that a combination of custom instructions and coprocessors is often the best solution in many applications, making the case for a hybrid custom-instruction and coprocessor-synthesis methodology. We propose such a methodology that builds upon the basic observations that coprocessors are usually good for coarse-grained tasks and require minimal intervention or support from the processor, while custom instructions are usually suited to fine-grained operations that are best integrated into a processor pipeline. Our methodology uses a hierarchical task-graph representation in order to support both coarse-and fine-grained views of an application, which are necessary to make meaningful tradeoffs. We propose a hierarchical synthesis algorithm that incorporates multiobjective evolutionary optimization in order to handle different design dimensions, such as area and performance, and provide a wide range of nondominated solutions. We have implemented the proposed methodology in the context of a commercial extensible processor-based platform (Xtensa from Tensilica). Our design flow uses a commercial behavioral-synthesis tool and an existing automatic-custom-instruction-generation tool. Our experiments with several applications show that simultaneous custom-instruction and coprocessor synthesis can achieve significantly better area/performance tradeoffs than using only one of them.

This paper proposes four types of source code transformations for operating system (OS)-driven embedded software programs to reduce their energy consumption. Their key features include spanning of process boundaries and minimization of the energy consumed in the execution of OS services—opportunities which are beyond the reach of conventional compiler optimizations and source code transformations. We have applied the proposed transformations to several multiprocess benchmark programs in the context of an embedded Linux OS running on an Intel StrongARM processor. They achieve up to 37.9% (23.8%, on average) energy reduction compared to highly compiler-optimized implementations.

In this paper, we propose an efficient and secure embedded processing architecture that addresses various challenges involved in using face-based biometrics for authenticating a user to an embedded system. Our paper considers the use of robust face verifiers (PCA-LDA, Bayesian), and analyzes the computational workload involved in running their software implementations on an embedded processor. We then present a suite of hardware and software enhancements to accelerate these algorithms-fixed-point arithmetic, various code optimizations, generic custom instructions and dedicated coprocessors, and exploitation of parallel processing capabilities in multiprocessor systems-on-chip (SoCs). We also identify attacks targeted against the authentication process, and develop security measures to ensure the integrity of biometric code/data. We evaluated the proposed architectures in the context of popular open-source software implementations of face authentication algorithms running on a commercial embedded processor (Xtensa from Tensilica). Our paper shows that fast, in-system verification is possible even in the context of many resource-constrained embedded systems. We also demonstrate that the security of the authentication process for the given attack model can be achieved with minimum hardware overheads

As computer systems penetrate deeper into our lives and handle private data, safety-critical applications, and transactions of high monetary value, efforts to breach their security also assume significant dimensions way beyond an amateur hacker's play. Until now, security was always an afterthought. This is evident in regular updates to antivirus software, patches issued by vendors after software bugs are discovered, etc. However, increasingly, we are realizing the need to incorporate security during the design of a system, be it software or hardware. We invoke this philosophy in the design of a hardware-based system to enable protection of a program's data during execution. In this paper, we develop a general framework that provides security assurance against a wide class of security attacks. Our work is based on the observation that a program's normal or permissible behavior with respect to data accesses can be characterized by various properties. We present a hardware/software approach wherein such properties can be encoded as data attributes and enforced as security policies during program execution. These policies may be application- specific (e.g., access control for certain data structures), compiler- generated (e.g., enforcing that variables are accessed only within their scope), or universally applicable to all programs (e.g., disallowing WRITES to unallocated memory). We show how an embedded system architecture can support such policies by: 1) enhancing the memory hierarchy to represent the attributes of each datum as security tags that are linked to it throughout its lifetime and 2) adding a configurable hardware checker that interprets the semantics of the tags and enforces the desired security policies. We evaluated the effectiveness of the proposed architecture in enforcing various security policies for several embedded benchmark applications. Our experiments in the context of the Simplescalar framework demonstrate that the proposed solution ensures run-time validation of application-defined data properties with minimal execution time overheads.

The functionality of mobile devices, such as cell phones and personal digital assistants (PDAs), has evolved to include various applications where security is a critical concern (secure web transactions, mobile commerce, download and playback of protected audio/video content, connection to corporate private networks, etc.). Security mechanisms (e.g., secure communication protocols) involve cryptographic algorithms, and are often quite computationally intensive, challenging the constrained processing and battery resources of mobile devices. Extensive design effort and aggressive hardware and software optimizations are required to address this challenge. Previous work has addressed the design of hardware architectures (custom accelerators, domain-specific processors, etc.) to accelerate security processing, and many emerging systems-on-chip (SoCs) feature some form of hardware support for security. In this paper, we address the complementary problem of mapping a complex security software library to an SoC platform with security hardware enhancements. We present a systematic methodology for exploring the software architecture for security processing for a commercial heterogeneous multiprocessor SoC for mobile devices. The SoC contains multiple host processors executing applications and a dedicated programmable security processing engine. We developed an exploration methodology to map the code and data of security software libraries onto the platform, with the objective of maximizing the overall application-visible performance. The salient features of the methodology include: 1) the use of real performance measurements from a prototyping board, which contains the target platform, to drive the exploration; 2) a new data structure access profiling framework that allows us to accurately model the communication overheads involved in off loading a given set of functions to the security processor; and 3) an exact branch-and-bound-based design space exploration algorithm that determines the best mapping of security library functions and data structures to the host and security processors. We used the proposed framework to map a commercial security library to the target mobile application SoC. The resulting optimized software architecture outperformed several manually designed software architectures, resulting in up to 12.5 times speed-up for individual cryptographic operations (encryption, hashing) and 2.2-6.2 times speed-up for applications such as a digital rights management (DRM) agent and secure sockets layer (SSL) client. We also demonstrate the applicability of our framework to software architecture exploration in other multiprocessor scenarios.

Memory-intensive applications present unique challenges to an application-specific integrated circuit (ASIC) designer in terms of the choice of memory organization, memory size requirements, bandwidth and access latencies, etc. The high potential of single-chip distributed logic-memory architectures in addressing many of these issues has been recognized in general-purpose computing, and more recently, in ASIC design. The high-level synthesis (HLS) techniques presented in this paper are motivated by the fact that many memory-intensive applications exhibit irregular array data access patterns. Synthesis should, therefore, be capable of determining a partitioned architecture, wherein array data and computations may have to be heterogeneously distributed for achieving the best performance speed-up. We use a combination of clustering and min-cut style partitioning techniques to yield distributed architectures, based on simulation profiling while considering various factors including data access locality, balanced workloads, inter-partition communication, etc. Our experiments with several benchmark applications show that the proposed techniques yielded two-way partitioned architectures that can achieve upto 2.1 x (average of 1.9 x) performance speed-up over conventional HLS solutions, while achieving upto 1.5 x (average of 1.4 x) performance speed-up over the best homogeneous partitioning solution feasible. At the same time, the reduction in the energy-delay product over conventional single-memory designs is upto 2.7 x (average of 2.0 x). A larger amount of partitioning makes further system performance improvement achievable at the cost of chip area.

Cryptographic algorithms, irrespective of their theoretical strength, can be broken through weaknesses in their implementations. The most successful of these attacks are side-channel attacks which exploit unintended information leakage, e.g., timing information, power consumption, etc., from the implementation to extract the secret key. We propose a novel framework for implementing side-channel attacks where the attack is modeled as a search problem which takes the leaked information as its input, and deduces the secret key by using a satisfiability solver, a powerful Boolean reasoning technique. This approach can substantially enhance the scope of side-channel attacks by allowing a potentially wide range of internal variables to be exploited (not just those that are trivially related to the key). The proposed technique is particularly suited for attacking cryptographic software implementations which may inadvertently expose the values of intermediate variables in their computations (even though, they are very careful in protecting secret keys through the use of on-chip key generation and storage). We demonstrate our attack on standard software implementations of three popular cryptographic algorithms: DES, 3DES, and AES. Our attack technique is automated and does not require mathematical expertise on the part of the attacker

Security protocols, such as IPSec and SSL, are being increasingly deployed in the context of networked embedded systems. The resource-constrained nature of embedded systems and, in particular, the modest capabilities of embedded processors make it challenging to achieve satisfactory performance while executing security protocols. A promising approach for improving performance in embedded systems is to use application-specific instruction set processors that are designed based on configurable and extensible processors. In this paper, we perform a comprehensive performance analysis of the IPSec protocol on a state-of-the-art configurable and extensible embedded processor (Xtensa from Tensilica Inc.). We present performance profiles of a lightweight embedded IPSec implementation running on the Xtensa processor, and examine in detail the various factors that contribute to the processing latencies, including cryptographic and protocol processing. In order to improve the efficiency of IPSec processing on embedded devices, we then study the impact of customizing an embedded processor by synergistically 1) configuring architectural parameters, such as instruction and data cache sizes, processor-memory interface width, write buffers, etc., and 2) extending the base instruction set of the processor using custom instructions for both cryptographic and protocol processing. Our experimental results demonstrate that upto 3.2times speedup in IPSec processing is possible over a popular embedded IPSec software implementation

We present a systematic methodology for exploring the security processing software architecture for a commercial heterogeneous multiprocessor system-on-chip (SoC) for mobile devices. The SoC contains multiple host processors executing applications and a dedicated programmable security processing engine. We developed an exploration methodology to map the code and data of security software libraries onto the platform, with the objective of maximizing the overall application-visible performance. The salient features of the methodology include (i) the use of real performance measurements from a prototyping board that contains the target platform to drive the exploration, (ii) a new data structure access profiling framework that allows us to accurately model the communication overheads involved in offloading a given set of functions to the security processor, and (iii) an exact branch-and-bound based design space exploration algorithm that determines the best mapping of security library functions and data structures to the host and security processors.We used the proposed framework to map a commercial security library to the target mobile application SoC. The resulting optimized software architecture outperformed several manually-designed software architectures, resulting in upto 12.5X speedup for individual cryptographic operations (encryption, hashing) and 2.2X-6.2X speedup for applications such as a Digital Rights Management (DRM) agent and Secure Sockets Layer (SSL) client. We also demonstrate the applicability of our framework to software architecture exploration in other multiprocessor scenarios.

Software-based self-test (SBST) has recently emerged as an effective methodology for the manufacturing test of processors and other components in Systems-on-Chip (SoCs). By moving test related functions from external resources to the SoC’s interior, in the form of test programs that the on-chip processor executes, SBST eliminates the need for high-cost testers, and enables high-quality at-speed testing. Thus far, SBST approaches have focused almost exclusively on the functional (directly programmer visible) components of the processor. In this paper, we analyze the challenges involved in testing an important component of modern processors, namely, the pipelining logic, and propose a systematic SBST methodology to address them. We first demonstrate that SBST programs that only target the functional components of the processor are insufficient to test the pipeline logic, resulting in a significant loss of fault coverage. We further identify the testability hotspots in the pipeline logic. Finally, we develop a systematic SBST methodology that enhances existing SBST programs to comprehensively test the pipeline logic. The proposed methodology is complementary to previous SBST techniques that target functional components (their results can form the input to our methodology), and can reuse the test development effort behind existing SBST programs. We applied the methodology to two complex, fully pipelined processors. Results show that our methodology provides fault coverage improvements of up to 15% (12 % on average) for the entire processor, and fault coverage improvements of 22 % for the pipeline logic, compared to a conventional SBST approach.

Dynamic variations in application functionality and performance requirements can lead to the imposition of widely disparate requirements on system-on-chip (SoC) platform hardware over time. This has led to interest in the design and use of adaptive SoC platforms that are capable of providing high performance in the face of such variations. Recent advances in circuits and architectures are enabling platforms that contain various mechanisms for runtime adaptation. However, the problem of exploiting such configurability in a coordinated manner at the system level remains a challenging task. In this work, we focus on two configurable subsystems of SoC platforms that play a crucial role in determining overall system performance, namely, the on-chip communication architecture, and the on-chip memory architecture. Using detailed case studies, we demonstrate the limitations of designs in which the architectural configuration of a bus-based communication architecture and the placement of data in memory are statically optimized, and those in which each is customized separately, without considering their interdependence. We propose an integrated methodology for dynamically relocating on-chip data and reconfiguring the communication architecture, and discuss the necessary hardware support. Experiments conducted on an SoC platform that integrates decoders for the UMTS (3G) and IEEE 802.11a (wireless LAN) standards demonstrate that the proposed integrated adaptation technique helps boost the maximum achievable performance by up to 32% over the best statically optimized design

Embedded multiprocessors pose new challenges in the design and implementation of embedded software. This has led to the need for programming interfaces that expose the capabilities of the underlying hardware. In addition, for systems that implement applications consisting of multiple concurrent threads of computation, the optimized management of inter-thread communication is crucial for realizing high-performance. This paper presents the design of an application-adaptive thread library that conforms to the IEEE POSIX 1003.1c threading standard (Pthreads). The library adapts the placement of both explicitly marked application data objects, as well as implicitly created data objects, in a physically distributed on-chip memory architecture, based on the application's data access characteristics

Online monitoring of a physical phenomenon over a geographical area is a popular application of sensor networks. Networks representative of this class of applications are typically operated in one of two modes, viz. an always-on mode where every sensor reading is streamed to a base station, possibly after in-network aggregation, and a snapshot mode where a user queries the network for an instantaneous summary of the observed field. However, a continuum of data acquisition policies exists between these two extreme modes, depending upon the rate and manner in which each sensor node is queried. In this work, we explore this continuum to improve network energy efficiency. We present a data acquisition framework that models the evolution of the observed data field at each sensor location as a function of time and uses an active learning based criterion to intelligently sample each sensor. Sensor nodes in our framework are organized in a clustered hierarchy. Time-dependent models of sensor readings are maintained at cluster-head nodes, which sample nodes in their cluster in a way that minimizes total energy consumption while maintaining confidence bounds on the overall model. We use sparse Gaussian processes to model sensor readings and variance minimization based active learning to intelligently select sensor nodes for querying. Finally, we present simulation results demonstrating up to 70% savings in total network energy, compared to the base case, in which sensors are sampled according to a cyclic schedule.

Process variations will increasingly impact the operational characteristics of integrated circuits in nanoscale semiconductor technologies. Researchers have proposed various design techniques to address process variations at the mask, circuit, and logic levels. However, as the magnitude of process variations increases, their effects will need to be addressed earlier in the design cycle.In this paper, we propose techniques for accurately and efficiently incorporating the effects of process variations into system-level power estimation tools. To motivate our work, we first study the impact of process variations on the power consumption of an example System-on-Chip (SoC). We consider simple extensions of current approaches to system-level power estimation (spreadsheet-based and simulation-based power estimation), and demonstrate their limitations in performing variation-aware power estimation. We propose a system-level power estimation methodology that can accurately and efficiently analyze the impact of process variations on SoC power. The proposed methodology combines efficient trace-based analysis, power-state based leakage modeling, and Monte Carlo sampling. The key benefit of the proposed methodology is that it captures the necessary inter-dependencies while avoiding iterative system-level simulation. Our implementation of the proposed techniques within an in-house system-level power estimation framework indicates 2-5 orders of magnitude efficiency gains, with negligible loss in accuracy, compared to direct Monte Carlo techniques that require iterative system simulation.

High-level synthesis (HLS) of memory-intensive applications has featured several innovations in terms of enhancements made to the basic memory organization and data layout. However, increasing performance and energy demands faced by application-specific integrated circuits (ASICs) are forcing designers to alter the fundamental architectural template of the HLS output, namely, a controller datapath associated with a memory subsystem (monolithic, partitioned, etc.). An architectural template for the HLS output that consists of a controller-datapath circuit associated with a memory subsystem into which computation units have been integrated is proposed. The enhanced memory subsystem is called computation-unit integrated memory (CIM). A CIM offers higher memory bandwidth (relative to what is offered through the system bus) to computation units present locally within it and reduces the overall communication between the memory subsystem and the controller datapath, thus providing a template highly suitable for deriving efficient implementations of memory-intensive applications. This paper addresses the challenge of providing a systematic synthesis framework for a CIM-based architecture. This framework can analyze the various tradeoffs involved in selecting suitable operations in a behavior for execution using a CIM and generate a high-performance low-overhead implementation. Efficient data reuse of register files have also been fully exploited to further improve system performance. Experiments with several behaviors indicate that an average performance improvement of 2.02times(a maximum of 2.70times) is possible with very low area overheads. The energy-delay product improves by an average of 2.5times(maximum of 3.8times)

In this paper, the authors present compression techniques for effectively reducing the test-data-volume requirements of modern systems-on-a-chip (SOC). Their techniques are based on the following observations: 1) Conventional test compression schemes, which are designed to satisfy various constraints including low hardware overheads and decompression times, cannot fully exploit compression opportunities present in test data and 2) due to the diversity of components used in SOCs (and consequently in their test strategies and test-data characteristics), a single compression strategy may not be best suited to handle them. The authors propose the use of multilevel and heterogeneous test compression schemes to address the above issues and demonstrate that they can provide significant reductions in the test volume above currently known state-of-the-art test compression techniques. An architecture that reuses infrastructure components already present in SOCs (programmable processors, on-chip communication architecture, memory, etc.) for an efficient implementation of their techniques is proposed. Finally, the authors suggest various architectural-customization techniques, such as partitioning of the decompression functionality between the hardware and software and the addition of custom instructions, to improve decompression times and reduce hardware overheads. Experiments with several designs, including an industrial media-processing SOC, demonstrate the efficacy of the proposed techniques in achieving test-data-volume reductions with low overheads

The complexity of many embedded software applications and their stringent performance requirements have reached a point where they can no longer be supported by conventional embedded-system architectures based on a single general-purpose processor. Nanometer fabrication technologies have made it feasible to integrate several embedded processors on a single chip to create multiprocessor systems-on-chip (MPSoCs) for a wide range of applications. It is already well known that, for embedded systems, customizing the processor to the application can significantly increase performance and energy efficiency. Single-chip heterogeneous multiprocessors, where the different processors are customized to the tasks they perform, are thus attracting attention. Despite their significant potential, a primary bottleneck to their adoption remains the development of programming paradigms and tools to alleviate the design complexity. Some advances have been made in the areas of custom multiprocessor architecture, tool support, and design methodology in order to reduce the design turnaround time. However, because of the heterogeneity of the custom processors, the designers are still required to manually map the application tasks to the different processors and, at the same time, customize each processor so that the overall performance requirements are satisfied. A multilevel custom multiprocessor-synthesis methodology to perform the assignment and scheduling of the application tasks on the various processors together with processor customization in an integrated manner is proposed. This paper focuses on extensible processors, which provide a good tradeoff between efficiency, flexibility, and design turnaround time, by combining a configurable base processor with hardware that implements custom instructions to extend its instruction set. This paper motivates the need for such an integrated approach by demonstrating that custom-instruction selection has complex interdependencies with task assignment and scheduling, and performing these steps independently often results in significant degradation in the quality of the synthesized multiprocessor architecture. The methodology presented here uses an iterative improvement algorithm to first assign and schedule tasks on processors and then select custom instructions along the critical path. It utilizes the concept of "expected execution time" to connect these two steps. It not only considers the currently selected custom instructions for the current task assignment and schedule, but also the possibility of better custom instructions being selected in future iterations. The methodology presented here is also enhanced to integrate task-level software pipelining to further increase the parallelism in the task graph and provide opportunities for multiprocessing. In this paper, the proposed heterogeneous multiprocessor-synthesis methodology is implemented in the context of a commercial extensible-processor design flow, using the Xtensa platform from Tensilica Inc. The presented tool was evaluated by automatically generating custom multiprocessor architectures for several complex embedded software benchmarks. The results show that architectures synthesized by the proposed methodology demonstrate an average speedup of 2.0/spl times/ (up to 2.9/spl times/) compared to symmetric multiprocessor architectures in which the processors have not been augmented with custom instructions. To the best of the authors' knowledge, this is the first tool for the synthesis of custom MPSoCs using extensible processors.

Most methods for hardware power estimation operate at the register-transfer level (RTL) or lower levels of design abstraction. Since cycle-accurate functional descriptions (CAFDs) are being widely adopted in integrated circuit (IC) design flows, power estimation can potentially benefit from the inherent increase in the efficiency of a cycle-based functional simulation. However, attempts at power estimation for functional descriptions have suffered from a poor accuracy because the design decisions performed during their synthesis lead to an unavoidable large uncertainty in any power estimate that is based solely on the functional description. The authors propose a methodology for a CAFD power estimation that combines the accuracy achieved by structural RTL power estimation with the efficiency of cycle-accurate functional simulation. This goal is achieved by viewing a CAFD as an abstraction of a specific known RTL implementation that is synthesized from it. The authors identify correlations between a CAFD and its RTL implementation and "back-annotate" information into the CAFD solely for power estimation. The resulting RTL-aware CAFD contains a layer of code that instantiates virtual placeholders for RTL components and maps values of CAFD variables into the RTL components' inputs/outputs, thus enabling efficient and accurate power estimation. Power estimation is performed in the proposed methodology by simply cosimulating the RTL-aware CAFD with a simulatable power-model library that contains power macromodels for each RTL component. Techniques to further improve the speed of CAFD power estimation through the use of control-state-based adaptive power sampling are presented. The authors have implemented and evaluated the proposed techniques in the context of a commercial C-based hardware design flow. Experiments with a number of large industrial designs (up to 1 000 000 gates) demonstrate that the proposed methodology achieves an accuracy very close to RTL power estimation with two-three orders of magnitude speedup in estimation times

Security is becoming an everyday concern for a wide range of electronic systems that manipulate, communicate, and store sensitive data. An important and emerging category of such electronic systems are battery-powered mobile appliances, such as personal digital assistants (PDAs) and cell phones, which are severely constrained in the resources they possess, namely, processor, battery, and memory. This work focuses on one important constraint of such devices-battery life-and examines how it is impacted by the use of various security mechanisms. In this paper, we first present a comprehensive analysis of the energy requirements of a wide range of cryptographic algorithms that form the building blocks of security mechanisms such as security protocols. We then study the energy consumption requirements of the most popular transport-layer security protocol: Secure Sockets Layer (SSL). We investigate the impact of various parameters at the protocol level (such as cipher suites, authentication mechanisms, and transaction sizes, etc.) and the cryptographic algorithm level (cipher modes, strength) on the overall energy consumption for secure data transactions. To our knowledge, this is the first comprehensive analysis of the energy requirements of SSL. For our studies, we have developed a measurement-based experimental testbed that consists of an iPAQ PDA connected to a wireless local area network (LAN) and running Linux, a PC-based data acquisition system for real-time current measurement, the OpenSSL implementation of the SSL protocol, and parameterizable SSL client and server test programs. Based on our results, we also discuss various opportunities for realizing energy-efficient implementations of security protocols. We believe such investigations to be an important first step toward addressing the challenges of energy-efficient security for battery-constrained systems.

Embedded system security is often compromised when "trusted" software is subverted to result in unintended behavior, such as leakage of sensitive data or execution of malicious code. Several countermeasures have been proposed in the literature to counteract these intrusions. A common underlying theme in most of them is to define security policies at the system level in an application-independent manner and check for security violations either statically or at run time. In this paper, we present a methodology that addresses this issue from a different perspective. It defines correct execution as synonymous with the way the program was intended to run and employs a dedicated hardware monitor to detect and prevent unintended program behavior. Specifically, we extract properties of an embedded program through static program analysis and use them as the bases for enforcing permissible program behavior at run time. The processor architecture is augmented with a hardware monitor that observes the program's dynamic execution trace, checks whether it falls within the allowed program behavior, and flags any deviations from expected behavior to trigger appropriate response mechanisms. We present properties that capture permissible program behavior at different levels of granularity, namely inter-procedural control flow, intra-procedural control flow, and instruction-stream integrity. We outline a systematic methodology to design application-specific hardware monitors for any given embedded program. Hardware implementations using a commercial design flow, and cycle-accurate performance simulations indicate that the proposed technique can thwart several common software and physical attacks, facilitating secure program execution with minimal overheads

On-chip communication architectures play an important role in determining the overall performance of System-on-Chip (SoC) designs. Communication architectures should be flexible so as to offer high performance over a wide range of traffic characteristics. In particular, the resource sharing mechanism of the communication architecture, which determines how the often-conflicting requirements of different components are served, is of utmost importance. Conventional SoC architectures typically employ priority or time-division multiple-access (TDMA)-based communication architectures. However, these techniques are often inadequate. In the former, low-priority components may suffer from starvation, while in the latter, depending on the request profile, high-priority traffic may be subject to large latencies. This paper presents LOTTERYBUS, a high-performance SoC communication architecture based on new randomized on-chip communication protocols that addresses the shortcomings mentioned above. LOTTERYBUS provides each SoC component with a flexible, proportional, and probabilistically guaranteed share of the on-chip communication bandwidth. We present two variants of LOTTERYBUS. In the first variant, its architectural parameters are statically configured, leading to relatively low hardware overhead and design complexity. In the second variant, these parameters are allowed to vary dynamically, enabling more sophisticated use of LOTTERYBUS, at additional hardware cost. We have performed experiments to investigate the performance of LOTTERYBUS across a range of communication traffic characteristics. We have used LOTTERYBUS in designing a 4times4 ATM switch subsystem, and have compared its performance with conventional architectures. The results show that LOTTERYBUS provides fine-grained control over bandwidth allocation, and also provides significant reduction in average transaction latencies (up to 85%) compared to conventional architectures. Hardware implementations using a commercial 0.15-mum cell-based library indicate that the advantages provided by LOTTERYBUS are accompanied by modest hardware overheads compared to conventional architectures

Custom processors based on application-specific or domain-specific instruction sets are gaining popularity, and are often used to implement critical architectural blocks in complex systems-on-chip. While several advances have been made in the area of custom processor architectures, tools, and design methodologies, designers are still required to manually perform some critical tasks, such as selection of the custom instructions best suited to the given application and design constraints. We present a scalable methodology for the synthesis of a custom processor from an embedded software program. A key feature of the proposed methodology is its scalability, which is achieved by exploiting the structured, hierarchical nature of large software programs. We motivate the need for such a methodology, and describe the algorithms used for the critical steps, including hardware resource budgeting, local optimizations, and global exploration. Our methodology utilizes the concept of "soft" instruction templates, which can be adapted by adding operations to them or deleting operations from them at any time during the design space exploration process, allowing for global design decisions to be interleaved with fine-grained optimizations. To the best of our knowledge, this is the first work that uses the program hierarchy to derive soft instruction templates to synthesize application-specific processors for scalable applications. We have integrated our methodology in an open-source compiler, and verified it using a commercial extensible processor. Experiments with several benchmarks indicate that our methodology can effectively tackle large programs. It results in the synthesis of high-quality custom processors that demonstrate an average speedup of 2.82times and a maximum speedup of 6.07times. As a side-effect, the processor energy is also reduced. The average and maximum reduction in the energy-delay product for the benchmarks are 7.64times and 18.85times, respectively. The CPU times required for custom processor synthesis are quite small, indicating that the proposed techniques can be applied to embedded software programs of significant complexity

In this work, we propose and investigate the idea of enhancing a System-on-Chip (SoC) communication architecture (the fabric that integrates system components and carries the communication traffic between them) to facilitate higher security. We observe that a wide range of common security attacks are manifested as abnormalities in the system-level communication traffic. Therefore, the communication architecture, with its global system-level visibility, can be used to detect them. The communication architecture can also effectively react to security attacks by disallowing the offending communication transactions, or by notifying appropriate components of a security violation. We describe the general principles involved in a security-enhanced communication architecture (SECA) and show how several security objectives can be encoded in terms of policies that govern the inter-component communication traffic. We detail the implementation of SECA in the context of a popular commercial on-chip bus architecture (the AMBA architecture from ARM) through a combination of a centralized security enforcement module, and enhancements to the bus interfaces of system components. We illustrate how SECA can be used to enhance embedded system security in several application scenarios. A simple instance of SECA has been implemented in a commercial application processor SoC for mobile phones. We provide results of experiments performed to validate the proposed concepts through system-level simulation, and evaluate their overheads through hardware implementation using a commercial design flow.

In this work, we propose a new paradigm called power emulation, which exploits hardware acceleration to drastically speedup power estimation. Power emulation is based on the observation that most power estimation tools typically perform the following sequence of operations: simulating the circuit to obtain value traces or statistics for the inputs of its constituent components, evaluating power models for each circuit component based on the input values seen during simulation, and aggregating the power consumption of individual components to compute the circuit's power consumption. We further recognize that the steps involved in power estimation (power model evaluation, aggregation) can themselves be thought of as synthesizable functions and implemented as hardware circuits. Thus, any given design can be enhanced by adding to it .power estimation hardware., and the resulting power model enhanced circuit can be mapped onto a hardware prototyping platform. While drastic speedups in power estimation (orders of magnitude) are possible using this approach, a significant challenge arises due to the increase in circuit size as a result of adding power estimation hardware. We propose a systematic methodology to reduce the size of the power model enhanced circuit through a suite of techniques, including power model reuse across different circuit components, regulating the granularity of components for power modeling, exploiting inter-component power correlations, resource sharing for power model computations, and the use of block memories for efficient storage within power models. We demonstrate the benefits of the proposed power emulation paradigm by applying it to register-transfer level (RTL) power estimation for industrial designs, resulting in speedups from around 10X to over 500X compared to state-of-the-art commercial power estimation tools.

User authentication, which refers to the process of verifying the identity of a user, is becoming an important security requirement in various embedded systems. While conventional solutions for user authentication have relied on password-based mechanisms, they are increasingly being replaced by biometric technologies such as fingerprint, face, and voice recognition, which are known to provide higher levels of security for user authentication. This paper investigates the problem of supporting efficient fingerprint-based user authentication in embedded systems. For improving the performance of fingerprint-based authentication, we propose hardware/software enhancements that include a generic set of custom instruction extensions to an embedded processor's instruction set architecture, a memory-aware software re-design, and fixed-point arithmetic. We believe that the custom instruction set extensions proposed in this work are generic enough to speed up many fingerprint matching algorithms and even other biometric algorithms. Our experiments with an open-source, high-fidelity fingerprint authentication algorithm and a testbed featuring a commercial extensible processor show that performance is improved by a factor of 10.4X when using the proposed enhancements, while incurring modest overheads.

Software energy estimation is a critical step in the design of energyefficient embedded systems. Instruction-level simulation techniques, despite several advances, remain too slow for iterative use in systemlevel exploration. In this paper, we propose a methodology called hybrid simulation, which combines instruction set simulation with selective native execution (execution of some parts of the program directly on the simulation host computer), thereby overcoming the disadvantages of instruction-level simulation (low speed) and pure native execution (estimation accuracy, inapplicability to targetdependent code), while exploiting their advantages. Previously developed techniques for software energy macromodeling are utilized to estimate energy consumption for natively executed sub-programs. We identify and address the main challenges involved in hybrid simulation, and present an automatic tool flow for it, which analyzes a given program and selects functions for native execution in order to achieve maximum estimation efficiency while limiting estimation error. We have applied the proposed hybrid simulation methodology to a variety of embedded software programs, resulting in an average speed-up of 70% and estimation error of at most 6%, compared to one of the fastest publicly-available instruction set simulators.

In this paper, we describe FLEXBUS, a flexible, high-performance onchip communication architecture featuring a dynamically configurable topology. FLEXBUS is designed to detect run-time variations in communication traffic characteristics, and efficiently adapt the topology of the communication architecture, both at the system-level, through dynamic bridge by-pass, as well as at the component-level, using component re-mapping. We describe the FLEXBUS architecture in detail and present techniques for its run-time configuration based on the characteristics of the on-chip communication traffic. The techniques underlying FLEXBUS can be used in the context of a variety of on-chip communication architectures. In particular, we demonstrate its application to AMBA AHB, a popular commercial on-chip bus. Detailed experiments conducted on the FLEXBUS architecture using a commercial design flow, and its application to an IEEE 802.11 MAC processor design, demonstrate that it can provide significant performance gains as compared to conventional architectures (up to 31.5% in our experiments), with negligible hardware overhead.

Security is emerging as an important concern in embedded system design. The security of embedded systems is often compromised due to vulnerabilities in "trusted" software that they execute. Security attacks exploit these vulnerabilities to trigger unintended program behavior, such as the leakage of sensitive data or the execution of malicious code. In this work, we present a hardware-assisted paradigm to enhance embedded system security by detecting and preventing unintended program behavior. Specifically, we extract properties of an embedded program through static program analysis, and use them as the bases for enforcing permissible program behavior in real-time as the program executes. We present an architecture for hardware-assisted run-time monitoring, wherein the embedded processor is augmented with a hardware monitor that observes the processor's dynamic execution trace, checks whether the execution trace falls within the allowed program behavior, and flags any deviations from the expected behavior to trigger appropriate response mechanisms. We present properties that can be used to capture permissible program behavior at different levels of granularity within a program, namely inter-procedural control flow, intra-procedural control flow, and instruction stream integrity. We also present a systematic methodology to design application-specific hardware monitors for any given embedded program. We have evaluated the hardware requirements and performance of the proposed architecture for several embedded software benchmarks. Hardware implementations using a commercial design flow, and architectural simulations using the SimpleScalar framework, indicate that the proposed technique can thwart several common software and physical attacks, facilitating secure program execution with minimal overheads.

In this paper, we present power emulation, a novel design paradigm that utilizes hardware acceleration for the purpose of fast power estimation. Power emulation is based on the observation that the functions necessary for power estimation (power model evaluation, aggregation, etc.) can be implemented as hardware circuits. Therefore, we can enhance any given design with "power estimation hardware", map it to a prototyping platform, and exercise it with any given test stimuli to obtain power consumption estimates. Our empirical studies with industrial designs reveal that power emulation can achieve significant speedups (10X to 500X) over state-of-the-art commercial register-transfer level (RTL) power estimation tools.

Abstract — Battery life extension is the principal driver for energy-efficient wireless sensor network (WSN) design. However, there is growing awareness that in order to truly maximize the operating life of battery-powered systems such as sensor nodes, it is important to discharge the battery in a manner that maximizes the amount of charge extracted from it. In spite of this, there is little published data that quantitatively analyzes the effectiveness with which modern wireless sensor nodes discharge their batteries, under different operating conditions. In this paper, we report on systematic experiments that we conducted to quantify the impact of key wireless sensor network design and environmental parameters on battery performance. Our testbed consists of MICA2DOT Motes, a commercial lithiumcoin battery, and a suite of techniques for measuring battery performance. We evaluate the extent to which known electrochemical phenomena, such as rate-capacity characteristics, charge recovery and thermal effects, can play a role in governing the selection of key WSN design parameters such as power levels, packet sizes, etc. We demonstrate that battery characteristics significantly alter and complicate otherwise well-understood trade-offs in WSN design. In particular, we analyze the non-trivial implications of battery characteristics on WSN power control strategies, and find that a battery-aware approach to power level selection leads to a 52 % increase in battery efficiency. We expect our results to serve as a quantitative basis for future research in designing battery-efficient sensing applications and protocols. I.

With the increasing cost of on-chip global communication, high-performance designs for data-intensive applications require architectures that distribute hardware resources (computing logic, memories, interconnect, etc.) throughout the chip, while restricting computations and communications to geographic proximities. In this paper, we present a methodology for high-level synthesis (HLS) of distributed logic-memory architectures, i.e., architectures that have logic and memory distributed across several partitions in a chip. Conventional HLS tools are capable of extracting parallelism from a behavior for architectures that assume a monolithic controller/datapath communicating with a memory or memory hierarchy. This paper provides techniques to extend the synthesis frontier to more general architectures that can extract both coarse and fine-grained parallelism from data accesses and computations in a synergistic manner. Our methodology selects many possible ways of organizing data and computations, carefully examines the tradeoffs (i.e., communication overheads, synchronization costs, area overheads) in choosing one solution over another, and utilizes conventional HLS techniques for intermediate steps. We have evaluated the proposed framework on several benchmarks by generating register-transfer level (RTL) implementations using an existing commercial HLS tool with and without our enhancements, and by subjecting the resulting RTL circuits to logic synthesis and layout. The results show that circuits designed as distributed logic-memory architectures using our framework achieve significant (up to 5.3/spl times/, average of 3.5/spl times/) performance improvements over well-optimized conventional designs with small area overheads (up to 19.3%, 15.1% on average). At the same time, the reduction in the energy-delay product is by an average of 5.9/spl times/ (up to 11.0/spl times/).

This paper presents a technique for exploiting input statistics for energy and performance optimization of embedded software. The proposed technique is based on the fact that the computational complexities of programs or subprograms are often highly dependent on the values assumed by input and intermediate program variables during execution. This observation is exploited in the proposed software synthesis technique by augmenting the program with optimized versions of one or more subprograms that are specialized to, and executed under, specific input subspaces. We propose a methodology for input space-adaptive software synthesis that consists of the following steps: 1) control and value profiling of the input program; 2) application of compiler transformations in a preprocessing step; 3) identification of subprograms and corresponding input subspaces that hold the highest potential for optimization; and 4) an iterative application of known compiler transformations to realize performance and energy savings. We propose novel metrics based on the entropies of program variables to characterize subprograms and input subspaces that hold significant potential for optimization. The chosen subprograms are optimized by translating the input subspaces into value constraints on their variables, and iteratively applying known compiler transformations (that were not applicable in the context of the original program). We have evaluated input space-adaptive software synthesis by compiling the resulting optimized programs to two commercial embedded systems: an embedded system based on the Fujitsu SPARClite processor, and the Compaq iPAQ personal digital assistant (PDA) [64 MB memory, 206 MHz Intel StrongARM central processing unit (CPU)]. The energy and execution-time savings were calculated using energy-aware instruction-level simulators, as well as through direct-current measurement on the iPAQ. Our results demonstrate that the proposed technique can reduce energy by up to 54.5% (average of 30.6% and 25.6% for the SPARClite-based system and the iPAQ, respectively) while simultaneously improving performance by up to 59.6% (average of 31.3% and 31.5% for the SPARClite-based system and the iPAQ, respectively). In effect, improvements in the energy-delay product of up to 81.1% (average of 51.0% and 47.7% for the SPARClite-based system and the iPAQ, respectively) were observed. The energy savings resulting from our technique are fairly processor independent, and complementary to conventional compiler optimizations.

As embedded systems get more complex, deployment of embedded operating systems (OSs) as software run-time engines has become common. In particular, this trend is true even for battery-powered embedded systems, where maximizing battery life is a primary concern. In such OS-driven embedded software, the overall energy consumption depends very much on which OS is used and how the OS is used. Therefore, the energy effects of the OS need to be studied in order to design low-energy systems effectively.In this paper, we discuss the motivation for performing OS energy characterization and propose a methodology to perform the characterization systematically. The methodology consists of two parts. The first part is analysis , which is concerned with identifying a set of components that can be used to characterize the OS energy consumption, called energy characteristics . The second part is macromodeling , which is concerned with obtaining quantitative macromodels for the energy characteristics. It involves the process of experiment design, data collection, and macromodel fitting. The OS energy macromodels can be used conveniently as OS energy estimators in high-level or architectural optimization of embedded systems for low-energy consumption.As far as we know, this work is the first attempt to systematically tackle energy macromodeling of an embedded OS. To demonstrate our approach, we present experimental results for two well-known embedded OSs, namely, μC/OS and embedded Linux OS.

Efficient energy and performance estimation of embedded software is a critical part of any system-level design flow. Macromodeling based estimation is an attempt to speed up estimation by exploiting reuse that is inherent in the design process. Macromodeling involves pre-characterizing reusable software components to construct high-level models, which express the execution time or energy consumption of a sub-program as a function of suitable parameters. During simulation, macromodels can be used instead of detailed hardware models, resulting in orders of magnitude simulation speedup. However, in order to realize this potential, significant challenges need to be overcome in both the generation and use of macromodels--- including how to identify the parameters to be used in the macromodel, how to define the template function to which the macromodel is fitted, em etc. This paper presents an automatic methodology to perform characterization-based high-level software macromodeling, which addresses the aforementioned issues. Given a sub-program to be macromodeled for execution time and/or energy consumption, the proposed methodology automates the steps of parameter identification, data collection through detailed simulation, macromodel template selection, and fitting. We propose a novel technique to identify potential macromodel parameters and perform data collection, which draws from the concept of bf data structure serialization used in distributed programming. We utilize bf symbolic regression techniques to concurrently filter out irrelevant macromodel parameters, construct a macromodel function, and derive the optimal coefficient values to minimize fitting error. Experiments with several realistic benchmarks suggest that the proposed methodology improves estimation accuracy and enables wide applicability of macromodeling to complex embedded software, while realizing its potential for estimation speedup. We describe a case study of how macromodeling can be used to rapidly explore algorithm-level energy tradeoffs, for the tt zlib data compression library.

The growing number of instances of breaches in information security in the last few years has created a compelling case for efforts towards secure electronic systems. Embedded systems, which will be ubiquitously used to capture, store, manipulate, and access data of a sensitive nature, pose several unique and interesting security challenges. Security has been the subject of intensive research in the areas of cryptography, computing, and networking. However, despite these efforts, security is often mis-construed by designers as the hardware or software implementation of specific cryptographic algorithms and security protocols. In reality, it is an entirely new metric that designers should consider throughout the design process, along with other metrics such as cost, performance, and power..This paper is intended to introduce embedded system designers and design tool developers to the challenges involved in designing secure embedded systems. We attempt to provide a unified and holistic view of embedded system security by first analyzing the typical functional security requirements for embedded systems from an end-user perspective. We then identify the implied challenges for embedded system architects, as well as hardware and software designers (e.g., tamper-resistant embedded system design, processing requirements for security, impact of security on battery life for battery-powered systems, etc.). We also survey solution techniques to address these challenges, drawing from both current practice and emerging research, and identify open research problems that will require innovations in embedded system architecture and design methodologies.

High-level synthesis (HLS) of memory-intensive applications has featured several innovations in terms of enhancements made to the basic memory organization and data layout. However, increasing performance and energy demands faced by application-specific integrated circuits (ASIC) are forcing designers to alter the fundamental architectural template of the HLS output, namely, a controller-datapath associated with a memory subsystem (monolithic, banked, etc.). We propose an architectural template for the HLS output that consists of a controller-datapath circuit associated with a memory subsystem into which computation units have been integrated. The enhanced memory subsystem is called computation-unit integrated memory (CIM). A CIM offers higher memory bandwidth (relative to what is offered through the system bus) to computation units present locally within it and reduces the overall communication between the memory subsystem and the controller-datapath, thus providing a template highly suitable for deriving efficient implementations of memory-intensive applications. This work addresses the challenge of providing an automatic synthesis framework for a CIM-based architecture. Our framework can analyze the various trade-offs involved in selecting suitable operations in a behavior for execution using a CIM and generate a high-performance, low-overhead implementation. Experiments with several behaviors indicate that an average performance improvement of 1.88/spl times/ (a maximum of 2.63/spl times/) is possible with very low area overheads. The energy-delay product improves by an average of 2.1/spl times/ (maximum of 3.4/spl times/).

Cycle-accurate functional descriptions (CAFD) are being widely adopted in integrated circuit (IC) design flows. Power estimation can potentially benefit from the inherent increase in simulation efficiency of cycle-based functional simulation. Currently, most approaches to hardware power estimation operate at the register-transfer level (RTL), or lower levels of design abstraction. Attempts at power estimation for functional descriptions have suffered from poor accuracy because the design decisions performed during their synthesis lead to an unavoidable, large uncertainty in any power estimate that is based solely on the functional description. We propose a methodology for CAFD power estimation that combines the accuracy achieved by power estimation at the structural RTL with the efficiency of cycle-accurate functional simulation. We achieve this goal by viewing a CAFD as an abstraction of a specific, known RTL implementation that is synthesized from it. We identify correlations between a CAFD and its RTL implementation, and "back-annotate" information into the CAFD solely for the purpose of power estimation. The resulting RTL-aware CAFD contains a layer of code that instantiates virtual placeholders for RTL components, and maps values of CAFD variables into the RTL components' inputs/outputs, thus enabling efficient and accurate power estimation. Power estimation is performed in our methodology by simply co-simulating the RTL-aware CAFD with a simulatable power model library that contains power macro-models for each RTL component. We present techniques to further improve the speed of CAFD power estimation, through the use of control state-based adaptive power sampling. We have implemented and evaluated the proposed techniques in the context of a commercial C-based hardware design flow. Experiments with a number of large industrial designs (up to 1 million gates) demonstrate that the proposed methodology achieves accuracy very close to RTL power estimation with two-to-three orders of magnitude speedup in estimation times.

In this paper, we present an efficient and accurate methodology for estimating the energy consumption of application programs running on extensible processors. Extensible processors, which are getting increasingly popular in embedded system design, allow a designer to customize a base processor core through instruction set extensions. Existing processor energy macromodeling techniques are not applicable to extensible processors, since they assume that the instruction set architecture as well as the underlying structural description of the micro-architecture remain fixed. Our solution to the above problem is a hybrid energy macromodel suitably parameterized to estimate the energy consumption of an application running on the corresponding application-specific extended processor instance, which incorporates any custom instruction extension. Such a characterization is facilitated by careful selection of macromodel parameters/variables that can capture both the functional and structural aspects of the execution of a program on an extensible processor. Another feature of the proposed energy characterization flow is the use of regression analysis to build the macromodel. Regression analysis allows for in-situ characterization, thus allowing arbitrary test programs to be used during macromodel construction. We validated the proposed methodology by characterizing the energy consumption of a state-of-the-art extensible processor (Tensilica's Xtensa). We used the macromodel to analyze the energy consumption of several benchmark applications with custom instructions. The mean absolute error in the macromodel estimates is only 3.3%, when compared to the energy values obtained by a commercial tool operating on the synthesized register-transfer level (RTL) description of the custom processor. Our approach achieves an average speedup of three orders of magnitude over the commercial RTL energy estimator. Our experiments show that the proposed methodology also achieves good relative accuracy, which is essential in energy optimization studies. Hence, our technique is both efficient and accurate.

The ability to efficiently and accurately estimate battery life under different design choices at the system level is an important aid in designing battery-efficient systems. Recently developed battery models help by estimating battery life under given profiles of the battery discharge current over time. However, existing techniques for energy (or average power) estimation do not provide sufficient information (such as time profiles of system power consumption) to drive battery-life estimation. Techniques that are capable of generating such profiles often lack the efficiency required to support exploration at the system level. In this paper, we describe techniques for efficient generation of system-level power profiles, for use in a battery-life estimation framework. Our power profiling technique allows a designer to experiment with: 1) the mapping of system tasks to a set of architectural components and 2) the mapping of system communications to a specified communication architecture, and efficiently generate system power profiles for each alternative. The resulting profiles can then be analyzed using existing battery models to estimate battery lifetime and capacity. Extensive experiments conducted on an IEEE 802.11 MAC processor design demonstrate that our power profiler offers orders of magnitude improvement in runtimes over state-of-the-art cosimulation-based power estimation techniques, while suffering minimal loss of accuracy (average profiling error was 3.8%).

Rapid growth in the complexity of system-on-chips is being accompanied by increasing volume and diversity of on-chip communication traffic, which in turn, is driving the development of advanced system-level communication architectures. While these architectures have the potential to improve system performance, they pose significant new challenges to the system designer, owing to the complex design space defined by the availability of numerous network topologies, communication protocols, and mapping alternatives for system communications. In this paper, we address the problem of mapping a system's communication requirements to a given communication architecture template. We illustrate the nature of the communication architecture design space, and describe an exploration methodology that uses efficient algorithms to help automate the process of mapping the system communications to the selected template. In addition, we demonstrate the importance of simultaneously optimizing the on-chip communication protocols in order to maximize system performance. Experiments conducted on example systems, including a cell forwarding unit of an ATM switch, indicate that the proposed techniques aid in automatically constructing communication architectures that have high performance. For the systems we considered, the solutions generated using our methodology had 53% superior performance (on average), over those based on conventional architectures and mapping approaches. The algorithms used in the proposed methodology are computationally efficient, and scale well with increasing communication architecture complexity.

In this paper, we present a methodology for the design of high-performance system-on-chip communication architectures. The approach is based on the addition of a layer of circuitry called the communication architecture tuner (CAT) layer around an existing communication architecture topology. The added layer provides a system with the capability of adapting to runtime variability in the communication needs of its constituent components. For example, more critical data may be handled differently, leading to lower communication latencies. The CAT associated with each component monitors its internal state, analyzes the communication transactions it generates, and "predicts" the relative importance of the transactions in terms of their impact on system-level performance metrics. It then configures the protocol parameters of the underlying communication architecture (e.g., priorities, burst modes, etc.) to best suit the system's changing communication needs. We illustrate the issues and tradeoffs involved in the design of CAT-based communication architectures, and present algorithms that automate the key steps. Experiments with example systems indicate that performance metrics (e.g., number of missed deadlines, average processing time) for systems with CAT-based communication architectures are significantly (sometimes over an order of magnitude) better than those with conventional communication architectures.

This paper proposes a novel circuit design methodology, called common-case computation (CCC)-based design, and new design automation algorithms for optimizing energy consumption and performance. The proposed techniques are applicable in conjunction with any high-level design methodology, where a structural register-transfer level (RTL) description and its corresponding scheduled behavioral (cycle-accurate functional) description are available. It is a well-known fact that in behavioral descriptions of hardware circuits (and also in software programs), a small set of computations often account for most of the computational complexity. However, in the hardware implementations (structural RTL or lower level), the common cases and the remaining computations are typically treated alike. This paper shows that identifying and exploiting common cases during the design process can lead to implementations that are much more efficient in terms of energy consumption and performance.

Efficiency and flexibility are critical, but often conflicting, design goals in embedded system design. The recent emergence of extensible processors promises a favorable tradeoff between efficiency and flexibility, while keeping design turnaround times short. Current extensible processor design flows automate several tedious tasks, but typically require designers to manually select the parts of the program that are to be implemented as custom instructions. In this work, we describe an automatic methodology to select custom instructions to augment an extensible processor, in order to maximize its efficiency for a given application program. We demonstrate that the number of custom instruction candidates grows rapidly with program size, leading to a large design space, and that the quality (speedup) of custom instructions varies significantly across this space, motivating the need for the proposed flow. Our methodology features cost functions to guide the custom instruction selection process, as well as static and dynamic pruning techniques to eliminate inferior parts of the design space from consideration. Furthermore, we employ a two-stage process, wherein a limited number of promising instruction candidates are first short-listed using efficient selection criteria, and then evaluated in more detail through cycle-accurate instruction set simulation and synthesis of the corresponding hardware, to identify the custom instruction combinations that result in the highest program speedup or maximize speedup under a given area constraint. We have evaluated the proposed techniques using a state-of-the-art extensible processor platform, in the context of a commercial design flow. Experiments with several benchmark programs indicate that custom processors synthesized using automatic custom instruction selection can result in large improvements in performance (up to 5.4/spl times/, an average of 3.4/spl times/), energy (up to 4.5/spl times/, an average of 3.2/spl times/), and energy-delay products (up to 24.2/spl times/, an average of 12.6/spl times/), while speeding up the design process significantly.

This paper presents a new high-level synthesis methodology to generate optimized register-transfer level (RTL) implementations for multiprocess behavioral descriptions. The concurrent communicating processes specification paradigm is widely used in digital circuit and system design, and is employed in all popular hardware description languages. It has been shown that interprocess communication and synchronization can result in complex timing interdependencies, which significantly affect the performance of a multiprocess system. In this paper, we demonstrate that state-of-the-art high-level synthesis tools can generate significantly suboptimal implementations for behaviors that contain concurrent communicating processes. We present an analysis of how interprocess communication impacts high-level synthesis steps, and describe a new methodology to adapt existing high-level synthesis tools to optimize multiprocess descriptions. Our methodology is based on executing multiprocess performance analysis and process-by-process scheduling in an iterative manner. We present algorithms for key steps in the proposed methodology. We have performed extensive experiments in the context of a commercial high-level design flow to evaluate the proposed techniques. The results clearly demonstrate the utility of our techniques in synthesizing implementations with superior area, performance, and energy consumption. For example, up to 40% performance improvement (average of 35.6%) was achieved with little or no area overhead (average of 4.8%). In effect, the proposed techniques lead to a shift of the entire area-delay tradeoff curve for a design, to include superior designs that were hitherto infeasible. Our techniques also simultaneously result in up to 50% (average of 33.5%) improvement in energy and up to 69% (average of 58.3%) improvement in the energy-delay product.

Many modern electronic systems---including personal computers, PDAs, cell phones, network routers, smart cards, and networked sensors to name a few---need to access, store, manipulate, or communicate sensitive information, making security a serious concern in their design. Embedded systems, which account for a wide range of products from the electronics, semiconductor, telecommunications, and networking industries, face some of the most demanding security concerns---on the one hand, they are often highly resource constrained, while on the other hand, they frequently need to operate in physically insecure environments.Security has been the subject of intensive research in the context of general-purpose computing and communications systems. However, security is often misconstrued by embedded system designers as the addition of features, such as specific cryptographic algorithms and security protocols, to the system. In reality, it is a new dimension that designers should consider throughout the design process, along with other metrics such as cost, performance, and power.The challenges unique to embedded systems require new approaches to security covering all aspects of embedded system design from architecture to implementation. Security processing, which refers to the computations that must be performed in a system for the purpose of security, can easily overwhelm the computational capabilities of processors in both low- and high-end embedded systems. This challenge, which we refer to as the "security processing gap," is compounded by increases in the amounts of data manipulated and the data rates that need to be achieved. Equally daunting is the "battery gap" in battery-powered embedded systems, which is caused by the disparity between rapidly increasing energy requirements for secure operation and slow improvements in battery technology. The final challenge is the "assurance gap," which relates to the gap between functional security measures (e.g., security services, protocols, and their constituent cryptographic algorithms) and actual secure implementations. This paper provides an introduction to the challenges involved in secure embedded system design, discusses recent advances in addressing them, and identifies opportunities for future research.

This paper presents a high-level design methodology, called input space adaptive design, and new design automation algorithms for optimizing energy consumption and performance. Our techniques can be applied to behaviors described in hardware description languages, predesigned register-transfer level (RTL) circuits, or in the context of traditional high-level design methodologies. An input space adaptive design exploits the well-known fact that the quality of circuits can be significantly optimized by employing algorithms and implementation architectures that adapt to input statistics. This paper shows that harnessing the principles of input space adaptive design into a structured high-level design methodology can lead to large improvements in performance and energy consumption. We illustrate the tradeoffs involved in such designs, and demonstrate the need for a systematic design methodology in order to realize the full potential for performance and energy improvements. We propose a methodology for input space adaptive design that consists of the following steps: identification of parts of the behavior that hold the highest potential for optimization, selection of input subspaces whose occurrence can lead to significant reductions in implementation complexity, and transformation of the behavior to realize performance and/or energy savings. Evaluations of performance, energy, and area characteristics of input space adaptive designs in the context of a commercial high-level design flow indicate that such designs can reduce energy consumption by up to 58.9% (average of 40.0%), and simultaneously improve performance by up to 57.5% (average of 41.8%) compared to well-optimized designs that do not employ such techniques. The energy-delay product is reduced by up to 77.9% (average of 64.8%). When the performance improvements are translated into additional energy savings through supply voltage reduction, input space adaptive designs consume up to 74.2% (average of 68.8%) less energy at the same performance. The average area overhead is only 7.4%.

Software-based self-test (SBST) is an emerging approach to address the challenges of high-quality, at-speed test for complex programmable processors and systems-on chips (SoCs) that contain them. While early work on SBST has proposed several promising ideas, many challenges remain in applying SBST to realistic embedded processors. We propose a systematic scalable methodology for SBST that automates several key steps. The proposed methodology consists of (i) identifying test program templates that are well suited for test delivery to each module within the processor, (ii) extracting input/output mapping functions that capture the controllability/observability constraints imposed by a test program template for a specific module-under-test, (iii) generating module-level tests by representing the input/output mapping functions as virtual constraint circuits, and (iv) automatic synthesis of a software self-test program from the module-level tests. We propose novel RTL simulation-based techniques for template ranking and selection, and techniques based on the theory of statistical regression for extraction of input/output mapping functions. An important advantage of the proposed techniques is their scalability, which is necessitated by the significant and growing complexity of embedded processors.To demonstrate the utility of the proposed methodology, we have applied it to a commercial state-of-the-art embedded processor (Xtensa™ from Tensilica Inc.). We believe this is the first practical demonstration of software-based self-test on a processor of such complexity. Experimental results demonstrate that software self-test programs generated using the proposed methodology are able to detect most (95.2%) of the functionally testable faults, and achieve significant simultaneous improvements in fault coverage and test length compared with conventional functional test.

As intelligent electronic systems pervade all aspects of our lives, capturing. storing, and communicating a wide range of sensitive and personal data, security is emerging as a critical concern that must be addressed in order to enable several current and future applications. Mobile appliances, which will play a critical role in enabling the visions of ubiquitous computing and communications, and ambient intelligence, are perhaps the most challenging to secure - they often rely on a public medium for (wireless) communications, are easily lost or stolen due to their small form factors and mobility, and are highly constrained in cost and size, as well as computing and battery resources. This paper presents an introduction to security concerns in mobile appliances, and translates them into challenges that confront system architects, HW engineers, and SW developers, including how to bridge the processing and battery gaps, efficient tamper-proofing of devices, content protection, etc. Recent innovations and emerging commercial technologies that address these issues are also highlighted. We envision that. for a large class of embedded systems, security considerations will pervade all aspects of system design, driving innovations in system architecture, software, circuits, and design methodologies.

In this paper, we describe a comprehensive high-level synthesis system for control-flow intensive as well as data-dominated behaviors. We propose a new control-data flow graph model to preserve the parallelism inherent in the application, as well as to facilitate high-level synthesis. Our algorithm, which is based on an iterative improvement strategy, performs clock selection, scheduling, module selection, resource allocation and assignment simultaneously to fully derive the benefits of design space exploration at the behavior level. The system can be used to optimize area, power or energy, by selecting the cost function accordingly. Experimental results show that for energy-optimized designs, energy is reduced by up to 79.4% (an average of 42.2%), with an average of 24.8% area overhead, compared to area-optimized designs. For power-optimized designs, power is reduced by up to 70.8% (an average of 56.7%), with an average of 25.2% area overhead, compared to area-optimized designs. No Vdd scaling is performed to obtain the above results.

Security is critical to a wide range of wireless data applications and services. While several security mechanisms and protocols have been developed in the context of the wired Internet, many new challenges arise due to the unique characteristics of battery powered embedded systems. In this work, we focus on an important constraint of such devices -- battery life -- and examine how it is impacted by the use of security protocols.We present a comprehensive analysis of the energy requirements of a wide range of cryptographic algorithms that are used as building blocks in security protocols. Furthermore, we study the energy consumption requirements of the most popular transport-layer security protocol SSL (Secure Sockets Layer). To our knowledge, this is the first comprehensive analysis of the energy requirements of SSL. For our studies, we have developed a measurement-based experimental testbed that consists of an iPAQ PDA connected to a wireless LAN and running Linux, a PC-based data acquisition system for real-time current measurement, the OpenSSL implementation of the SSL protocol, and parametrizable SSL client and server test programs. We investigate the impact of various parameters at the protocol level (such as cipher suites, authentication mechanisms, and transaction sizes, etc.) and the cryptographic algorithm level (cipher modes, strength) on overall energy consumption for secure data transactions.Based on our results, we discuss various opportunities for realizing energy-efficient implementations of security protocols. We believe such investigations to be an important first step towards addressing the challenges of energy efficient security for battery-constrained systems.

The increasing complexity and software content of embedded systems has led to the frequent use of system software to help applications access hardware resources easily and efficiently. In this paper, we present a method for detailed analysis of real-time operating system (RTOS) power consumption. RTOSs form an important component of the system software layer. Despite the widespread use of, and significant role played by, RTOSs in mobile and low-power embedded systems, little is known about their power-consumption effects. This paper presents a method of producing a hierarchical energy-consumption profile for applications as they interact with an RTOS. As a proof-of-concept, we use our infrastructure to produce the power profiles for a commercial RTOS, /spl mu/C/OS-II, running several applications on an embedded system based on the Fujitsu SPARClite processor. These examples demonstrate that an RTOS can have a significant impact on power consumption. We discuss ways in which application software can be designed to use an RTOS in a power-efficient manner. We believe that this is a first step toward establishing a systematic approach to power optimization of embedded systems containing RTOSs.

Energy consumption has become a major focus in the design of embedded systems (e.g., mobile computing and wireless communication devices). In particular, a shift of emphasis from hardware-oriented low-energy design techniques to energy-efficient embedded software design has occurred progressively in the past few years. To that end, various techniques have been developed for the design of energy-efficient embedded software. In operating system (OS)-driven embedded systems, the OS has a significant impact on the system's energy consumption directly (energy consumption associated with the execution of the OS functions and services), as well as indirectly (interaction of the OS with the application software). As a first step toward designing energy-efficient OS-based embedded systems, it is important to analyze the energy consumption of embedded software by taking the OS energy characteristics into account. To facilitate such studies, we present, in this work, an energy simulation framework that can be used to analyze the energy consumption characteristics of an embedded system featuring the embedded Linux OS running on the StrongARM processor. The framework allows software designers to study the energy consumption of the system software in relation to the application software, identify the energy hot spots, and perform design changes based on the knowledge of the OS energy consumption characteristics as well as application-OS interactions.

We present efficient techniques for estimating switching activity and power consumption at the register-transfer level (RTL), using a combination of macro-modeling for datapath blocks, and control logic analysis techniques based on partial delay information. Previous work on estimating switching activity and power at the RTL has ignored the presence of glitches at various datapath and control signals. We demonstrate that glitches can form a significant component of the switching activity at signals in typical RTL circuits. In particular, for control-flow intensive designs, we show that the controller substantially affects the activity and power consumption in the datapath due to the presence of glitches at control signals. Since the final implementation of the controller is not available during high-level design iterations, we develop techniques that estimate glitching activity at control signals using control expressions and partial delay information. For datapath blocks that operate on word-level data, we construct piecewise linear models that capture the variation of output glitching activity and power consumption with various word-level parameters like mean, standard deviation, spatial and temporal correlations, and glitching activity at the block's inputs. For RTL blocks that operate on bit vectors that need not have an associated word-level value, we present accurate bit-level modeling techniques for glitching activity as well as power consumption. This allows us to perform accurate power estimation for control-flow intensive circuits, where most of the power consumed is dissipated in non-arithmetic components like multiplexers, registers, vector logic operators, etc. Experimental results on several RTL designs demonstrate the accuracy of the proposed estimation techniques. Our RTL power estimator produced estimates that were within 7% of those produced by an in-house power analysis tool on the final gate-level implementation, while being over 50/spl times/ faster than its gate-level counterpart.

Communication-based power management (CBPM) is a new battery-driven system-level power management methodology in which the system-level communication architecture regulates the execution of various system components, with the aim of improving battery efficiency, and hence, battery life. Unlike conventional power management policies (that attempt to efficiently shut down idle components), CBPM may delay the execution of selected system components even when they are active, in order to adapt the system-level current discharge profile to suit the battery's characteristics.In this paper, we present a methodology for the design of CBPM based systems, which consists of system-level performance and power profiling, battery discharge analysis, instrumentation of system components to facilitate CBPM, definition of CBPM policies, and generation of the CBPM-based system architecture. We present extensive evaluations of CBPM, and demonstrate its application to the design of an IEEE 801.11 Wireless LAN MAC processor system. Our results indicate that CBPM based systems are significantly more battery efficient than those based on conventional power management techniques. Further, we demonstrate that CBPM enables design-time as well as run-time tradeoffs between system performance and battery life.

Security protocols are critical to enabling the growth of a wide range of wireless data services and applications. However, they impose a high computational burden that is mismatched with the modest processing capabilities and battery resources available on wireless clients. Bridging the security processing gap, while retaining sufficient programmability in order to support a wide range of current and future security protocol standards, requires the use of novel system architectures and design methodologies.We present the system-level design methodology used to design a programmable security processor platform for next-generation wireless handsets. The platform architecture is based on (i) a configurable and extensible processor that is customized for efficient domain-specific processing, and (ii) layered software libraries implementing cryptographic algorithms that are optimized to the hardware platform. Our system-level design methodology enables the efficient co design of optimal cryptographic algorithms and an optimized system architecture. It includes novel techniques for algorithmic exploration and tuning, performance characterization and macro-modeling of software libraries, and architecture refinement based on selection of instruction extensions to accelerate performance-critical, computation-intensive operations. We have designed a programmable security processor platform to support both public-key and private key operations using the proposed methodology, and have evaluated its performance through extensive system simulations as well as hardware prototyping. Our experiments demonstrate large performance improvements (e.g., 31.0X for DES, 33.9X for 3DES, 17.4X for AES, and upto 66.4X for RSA) compared to well-optimized software implementations on a state-of-the-art embedded processor.

Rapid growth in the complexity of wireless devices, communication protocols, and applications, combined with slow improvements in battery technologies, have created a "battery gap" that is only projected to increase with advances in wireless communication technologies and applications. Conventional approaches to bridging this gap exploit low-power network protocols and handset architectures. However, it is now well known that minimizing the total energy or average power drawn from a battery does not necessarily lead to maximizing battery life, calling for new battery-driven approaches to protocol and hardware design. We present a battery-efficient architecture for an 802.11 MAC processor, which incorporates a new battery-driven approach to power management. The MAC processor employs a novel on-chip bus architecture that is capable of regulating the profile of the current drawn by the system, enabling battery discharge at high efficiencies. The proposed battery friendly MAC processor architecture enables significant increases in battery capacity and lifetime, while minimizing performance impacts. Further, the developed architecture provides mechanisms that allow for trade-offs between battery life and performance, and can be configured to adapt the power management techniques based on the network traffic characteristics.

Providing acceptable levels of security imposes significant computational requirements on wireless clients, servers, and network elements. These requirements are often beyond the modest processing capabilities and energy (battery) resources available on wireless clients. The relatively small sizes of wireless data transactions imply that public-key encryption algorithms dominate the security processing requirements. We propose techniques to improve the computational efficiency of public-key encryption algorithms. We focus on the modular exponentiation based encryption/decryption employed in many popular public-key algorithms. We study an extensive suite of algorithmic optimizations to the basic modular exponentiation algorithm and new advanced techniques. The proposed algorithmic optimizations lead to an "algorithm design space", across which performance varies significantly (over an order-of-magnitude). We evaluated the proposed algorithmic optimization techniques by obtaining processing times for the SSL (secure sockets layer) handshake protocol on a state-of-the-art embedded processor by using the optimal algorithm configuration and a popular conventional algorithm configuration. The results demonstrate that the optimum algorithm configuration leads to a 5.7/spl times/ improvement in SSL handshake protocol processing times. The proposed techniques are complementary to, and can be applied in conjunction with, improvements in security mechanisms and protocols, new hardware architectures, and improvements in silicon technologies.

With the increasing cost of global communication on-chip, high-performance designs for data-intensive applications require architectures that distribute hardware resources (computing logic, memories, interconnect, etc.) throughout a chip, while restricting computations and communications to geographic proximities. In this paper, we present a methodology for high-level synthesis (HLS) of distributed logic-memory architectures, i.e., architectures that have logic and memory distributed across several partitions in a chip. Conventional HLS tools are capable of extracting parallelism from a behavior for architectures that assume a monolithic controller/datapath communicating with a memory or memory hierarchy. This work provides techniques to extend the synthesis frontier to more general architectures that can extract both coarse- and fine-grained parallelism from data accesses and computations in a synergistic manner. Our methodology selects many possible ways of organizing data and computations, carefully examines the trade-offs (i.e., communication overheads, synchronization costs, area overheads) in choosing one solution over another, and utilizes conventional HLS techniques for intermediate steps.We have evaluated the proposed framework on several benchmarks by generating register-transfer level (RTL) implementations using an existing commercial HLS tool with and without our enhancements, and by subjecting the resulting RTL circuits to logic synthesis and layout. The results show that circuits designed as distributed logic-memory architectures using our framework achieve significant (upto, 5.31X average of 3.45X) performance improvements over well-optimized conventional designs with small area overheads (upto 19.3%, 15.1% on average).

Efficiency and flexibility are critical, but often conflicting, design goals in embedded system design. The recent emergence of extensible processors promises a favorable tradeoff between efficiency and flexibility, while keeping design turnaround times short. Current extensible processor design flows automate several tedious tasks, but typically require designers to manually select the parts of the program that are to be implemented as custom instructions.In this work, we describe an automatic methodology to select custom instructions to augment an extensible processor, in order to maximize its efficiency for a given application program. We demonstrate that the number of custom instruction candidates grows rapidly with program size, leading to a large design space, and that the quality (speedup) of custom instructions varies significantly across this space, motivating the need for the proposed flow. Our methodology features cost functions to guide the custom instruction selection process, as well as static and dynamic pruning techniques to eliminate inferior parts of the design space from consideration. Further, we employ a two-stage process, wherein a limited number of promising instruction candidates are first selected, and then evaluated in more detail through cycle-accurate instruction set simulation and synthesis of the corresponding hardware, to identify the custom instruction combinations that result in the highest program speedup or maximize speedup under a given area constraint.We have evaluated the proposed techniques using a state-of-the-art extensible processor platform, in the context of a commercial design flow. Experiments with several benchmark programs indicate that custom processors synthesized using automatic custom instruction selection can result in large improvements in performance (upto 5.4X, average of 3.4X), energy (upto 4.5X, average of 3.2X), and energy-delay product (upto 24.2X, average of 12.6X), while speeding up the design process significantly.

A large and increasing number of modern embedded systems are subject to tight power/energy constraints. It has been demonstrated that the operating system (OS) can have a significant impact on the energy efficiency of the embedded system. Hence, analysis of the energy effects of the OS is of great importance. Conventional approaches to energy analysis of the OS (and embedded software, in general) require the application software to be completely developed and integrated with the system software, and that either measurement on a hardware prototype or detailed simulation of the entire system be performed. Since this process requires significant design effort, unfortunately, it is typically too late in the design cycle to perform high-level or architectural optimizations on the embedded software, restricting the scope of power savings. Our work recognizes the need to provide embedded software designers with feedback about the effect of different OS services on energy consumption early in the design cycle. As a first step in that direction, this paper presents a systematic methodology to perform energy analysis and macro-modeling of an embedded OS. Our energy macro-models provide software architects and developers with an intuitive model for the OS energy effects, since they directly associate energy consumption with OS services and primitives that are visible to the application software. Our methodology consists of (i) an analysis stage, where we identify a set of energy components, called energy characteristics, which are useful to the designer in making OS-related design trade-offs, and (ii) a subsequent macromodeling stage, where we collect data for the identified energy components and automatically derive macro-models for them. We validate our methodology by deriving energy macro-models for two state-of-the-art embedded OS's, /spl mu/C/OS and Linux OS.

Test automation has been a cornerstone of the manufacturing test industry, much as electronic design automation has been to the semiconductor industry. Thus, it is fair to say that test automation providers will have a significant role to play in addressing the challenges involved in testing system-chips of the future. This session contains presentations that examine the test challenges presented by system-level integration, from the perspective of the providers of test tools and methodologies. The presenters will highlight innovations that will lead to improved test flows, addressing critical issues such as testing cost, test application time, and reuse of test hardware for silicon debug.

Presents an efficient and accurate high level software energy estimation methodology using the concept of characterization-based macromodeling. In characterization-based macromodeling, a function or subroutine is characterized using an accurate lower level energy model of the target processor to construct a macromodel that relates the energy consumed in the function under consideration to various parameters that can be easily observed or calculated from a high-level programming language description. The constructed macromodels eliminate the need for significantly slower instruction-level interpretation or hardware simulation that is required in conventional approaches to software energy estimation. Two different approaches to macromodeling for embedded software offer distinct efficiency-accuracy characteristics: 1) complexity-based macromodeling, where the variables that determine the algorithmic complexity of the function under consideration are used as macromodeling parameters and 2) profiling-based macromodeling, where internal profiling statistics for the functions are used as the parameters in the energy macromodels.

We present efficient power estimation techniques for hardware-software (HW-SW) system-on-chip (SoC) designs. Our techniques are based on concurrent and synchronized execution of multiple power estimators that analyze different parts of the SoC (we refer to this as coestimation), driven by a system-level simulation master. We motivate the need for power coestimation, and demonstrate that performing independent power estimation for the various system components can lead to significant errors in the power estimates, especially for control-intensive and reactive-embedded systems. We observe that the computation time for performing power coestimation is dominated by: i) the requirement to analyze/simulate some parts of the system at lower levels of abstraction in order to obtain accurate estimates of timing and switching activity information and ii) the need to communicate between and synchronize the various simulators. Thus, a naive implementation of power coestimation may be too inefficient to be used in an iterative design exploration framework. To address this issue, we present several acceleration (speed-up) techniques for power coestimation. The acceleration techniques are energy caching, software power macro-modeling, and statistical sampling. Our speed-up techniques reduce the workload of the power estimators for the individual SoC components, as well as their communication/synchronization overhead. Experimental results indicate that the use of the proposed acceleration techniques results in significant (8/spl times/ to 87/spl times/) speed-ups in SOC power estimation time, with minimal impact on accuracy. We also show the utility of our coestimation tool to explore system-level power tradeoffs for a TCP/IP check-sum engine subsystem.

This paper presents Lotterybus, a novel high-performance communication architecture for system-on-chip (SoC) designs. The Lotterybus architecture was designed to address the following limitations of current communication architectures: (i) lack of control over the allocation of communication bandwidth to different system components or data flows (e.g., in static priority based shared buses), leading to starvation of lower priority components in some situations, and (ii) significant latencies resulting from variations in the time-profile of the communication requests (e.g., in time division multiplexed access (TDMA) based architectures), sometimes leading to larger latencies for high-priority communications.

This paper presents an efficient and accurate high-level software energy estimation methodology using the concept of characterization-based macro-modeling. In characterization-based macro-modeling, a function or sub-routine is characterized using an accurate lower-level energy model of the target processor, to construct a macro-model that relates the energy consumed in the function under consideration to various parameters that can be easily observed or calculated from a high-level programming language description. The constructed macro-models eliminate the need for significantly slower instruction-level interpretation or hardware simulation that is required in conventional approaches to software energy estimation.

This paper presents a high-level design methodology, called input space adaptive design, and new design automation algorithms for optimizing energy consumption and performance. An input space adaptive design exploits the well-known fact that the quality of hardware circuits and software programs can be significantly optimized by employing algorithms and implementation architectures that adapt to the input statistics. We propose a methodology for such designs which includes identifying parts of the behavior to be optimized, selecting appropriate input sub-spaces, transforming the behavior, and verifying the equivalence of the original and optimized designs. Experimental results indicate that such designs can reduce energy consumption by up to 70.6% (average of 55.4%), and simultaneously improve performance by up to 85.1% (average of 58.1%), leading to a reduction in the energy-delay product by up to 95.6% (average of 80.7%), compared to well-optimized designs that do not employ such techniques.

The use of nanometer technologies is making it increasingly important to consider transient characteristics of a circuit's power dissipation (e.g., peak power, and power gradient or differential) in addition to its average power consumption. Current transient power analysis and reduction approaches are mostly at the transistor- and logic-levels. We argue that, as was the case with average power minimization, architectural solutions to transient power problems can complement and significantly extend the scope of lower-level techniques. In this work, we present a high-level synthesis approach to transient power management. We demonstrate how high-level synthesis can impact the cycle-by-cycle peak power and peak power differential for the synthesized implementation. Further, we demonstrate that it is necessary to consider transient power metrics judiciously in order to minimize or avoid area and performance overheads. In order to alleviate the limits on parallelism imposed by peak power constraints, we propose a novel technique based on the selective insertion of data monitor operations in the behavioral description. We present enhanced scheduling algorithms that can accept constraints on transient power characteristics (in addition to the conventional resource and performance constraints). Experimental results on several example designs obtained using a state-of-the-art commercial design flow and technology library indicate that high-level synthesis with transient power management results in significant benefits-peak power reductions of up to 32% (average of 25%), and peak power differential reductions of up to 59% (average of 42%)-with minimal performance overheads.

This paper presents a novel system-level performance analysis technique to support the design of custom communication architectures for system-on-chip integrated circuits. Our technique fills a gap in existing techniques for system-level performance analysis, which are either too slow to use in an iterative communication architecture design framework (e.g., simulation of the complete system) or are not accurate enough to drive the design of the communication architecture (e.g., techniques that perform a "static" analysis of the system performance). Our technique is based on a hybrid trace-based performance-analysis methodology in which an initial cosimulation of the system is performed with the communication described in an abstract manner (e.g., as events or abstract data transfers). An abstract set of traces are extracted from the initial cosimulation containing necessary and sufficient information about the computations and communications of the system components. The system designer then specifies a communication architecture by: 1) selecting a topology consisting of dedicated as well as shared communication channels (shared buses) interconnected by bridges; 2) mapping the abstract communications to paths in the communication architecture; and 3) customizing the protocol used for each channel. The traces extracted in the initial step are represented as a communication analysis graph (CAG) and an analysis of the CAG provides an estimate of the system performance as well as various statistics about the components and their communication. Experimental results indicate that our performance-analysis technique achieves accuracy comparable to complete system simulation (an average error of 1.88%) while being over two orders of magnitude faster.

The increasing complexity and software content of embedded systems has led to the frequent use of system software that helps applications access underlying hardware resources easily and efficiently. In this paper, we analyze the power consumption of real-time operating systems (RTOSs), which form an important component of the system software layer. Despite the widespread use of, and significant role played by, RTOSs in mobile and low-power embedded systems, little is known about their power consumption characteristics. This work presents the power profiles for a commercial RTOS, μC/OS, running several applications on an embedded system based on the Fujitsu SPARClite processor. Our work demonstrates that the RTOS can consume a significant fraction of the system power and, in addition, impact the power consumed by other software components. We illustrate the ways in which application software can be designed to use the RTOS in a power-efficient manner. We believe that this work is a first step towards establishing a systematic approach to RTOS power modeling and optimization.

In this chapter, we present a general methodology for the design of custom system-on-chip communication architectures. Our technique is based on the addition of a layer of circuitry, called the Communication Architecture Tuner (CAT), around any existing communication architecture topology. The added layer enhances the ability of the system to adapt to changing communication needs of its constituent components. For example, more critical data may be handled differently, leading to lower communication latencies. The CAT monitors the internal state and communication transactions of each component, and “predicts” the relative importance of each communication transaction in terms of its potential impact on different system-level performance metrics. It then configures the protocol parameters of the underlying communication architecture (e.g., priorities, DMA modes,etc.) to best suit the system's changing communication needs.

We present efficient power estimation techniques for HW/SW System-On-Chip (SOC) designs. Our techniques are based on concurrent and synchronized execution of multiple power estimators that analyze different parts of the SOC (we refer to this as co-estimation), driven by a system-level simulation master. We motivate the need for power co-estimation, and demonstrate that performing independent power estimation for the various system components can lead to significant errors in the power estimates, especially for control-intensive and reactive embedded systems. We observe that the computation time for performing power co-estimation is dominated by: (i) the requirement to analyze/simulate some parts of the system at lower levels of abstraction in order to obtain accurate estimates of timing and switching activity information and (ii) the need to communicate between and synchronize the various simulators. Thus, a naive implementation of power co-estimation may be too inefficient to be used in an iterative design exploration framework. To address this issue, we present several acceleration (speedup) techniques for power co-estimation. The acceleration techniques are energy caching, software power macromodeling, and statistical sampling. Our speedup techniques reduce the workload of the power estimators for the individual SOC components, as well as their communication/synchronization overhead. Experimental results indicate that the use of the proposed acceleration techniques results in significant (8/spl times/ to 87/spl times/) speedups in SOC power estimation time, with minimal impact on accuracy. We also show the utility of our co-estimation tool to explore system-level power tradeoffs for a TCP/IP network interface card sub-system and an automotive controller.

In this paper, we present a methodology and efficient algorithms for the design of high-performance system-on-chip communication architectures. Our methodology automatically and optimally maps the various communications between system components onto a target communication architecture template that can consist of an arbitrary interconnection of shared or dedicated channels. In addition, our techniques simultaneously configure the communication protocols of each channel in the architecture in order to optimize system performance. We motivate the need for systematic exploration of the communication architecture design space, and highlight the issues involved through illustrative examples. We present a methodology and algorithms that address these issues, including the size and complexity of the design space. We present experimental results on example systems, including a cell forwarding unit of an ATM switch, that demonstrate the benefits of using the proposed techniques. Experimental results indicate that our techniques are successful in achieving significant improvements in system performance over conventional communication architectures (observed speedups over typical architectures such as single shared buses averaged 53%). Moreover, we demonstrate that our design space exploration methodology and optimization algorithms are efficient (low CPU times), underlining their usefulness as part of any system design flow.

This paper addresses the problem of synthesizing fault-secure controller/data path circuits from behavioral specifications. These circuits are guaranteed to either produce the correct output, or to flag an error. We use an iterative improvement-based behavioral synthesis framework that performs functional unit selection, clock selection, scheduling, and resource sharing with the aim of minimizing the area of the synthesized circuit, while allowing multicycling, chaining, and functional unit pipelining. We present a dynamic comparison selection algorithm that can be used during behavioral synthesis to determine which intermediate results in the computation need to be secured in order to enable maximal resource sharing. Previous work on synthesizing fault-secure data paths has focused on ensuring that aliasing (a condition when the circuit produces an incorrect output and does not flag an error) cannot occur in any part of the design. We demonstrate that such an approach can lead to unnecessarily large overheads. In order to alleviate the overheads incurred for fault security, our behavioral synthesis framework uses ALiasing Probability analysiS (ALPS) in order to identify resource sharing configurations that reduce area while introducing a very low probability of aliasing (of the order of 10/sup -10/ for a bit-width of 32) in the resultant data path. Experimental results performed for several behavioral descriptions demonstrate that our techniques synthesize more compact circuits than techniques available in the literature, e.g., double modular redundancy or zero-aliasing techniques.

Speculative execution refers to the execution of parts of a computation before the execution of the conditional operations that decide whether they need to be executed. It has been shown to be a promising technique for eliminating performance bottlenecks imposed by control flow in hardware and software implementations alike. In this paper, we present techniques to incorporate speculative execution in a fine-grained manner into scheduling of control-flow-intensive behavioral descriptions. We demonstrate that failing to take into account information such as resource constraints and branch probabilities can lead to significantly suboptimal performance. We also demonstrate that it may be necessary to speculate simultaneously along multiple paths, subject to resource constraints, in order to minimize the delay overheads incurred when prediction errors occur. Experimental results on several benchmarks show that our speculative scheduling algorithm can result in significant (up to seven-fold) improvements in performance (measured in terms of the average number of clock cycles) as compared to scheduling without speculative execution. Also, the best and worst case execution times for the speculatively performed schedules are the same as or better than the corresponding values for the schedules obtained without speculative execution.

This paper presents a design methodology, called common-case computation (CCC), and new design automation algorithms for optimizing power consumption or performance. The proposed techniques are applicable in conjunction with any high-level design methodology where a structural register-transfer level (RTL) description and its corresponding scheduled behavioral (cycle-accurate functional RTL) description are available. It is a well-known fact that in behavioral descriptions of hardware (also in software), a small set of computations (CCCs) often accounts for most of the computational complexity. However, in hardware implementations (structural RTL or lower level), CCCs and the remaining computations a typically treated alike. This paper shows that identifying and exploiting CCCs during the design process can lead to implementations that are much more efficient in terms of power consumption or performance. We propose a CCC-based high-level design methodology with the following steps: extraction of common-case behaviors and execution conditions from the scheduled description, simplification of the common-case behaviors in a stand-alone manner, synthesis of common-case detection and execution circuits from the common-case behaviors, and composing the original design with the common-case circuits, resulting in a CCC-optimized design. We demonstrate that CCC-optimized designs reduce power consumption by up to 91.5%, or improve performance by up to 76.6% compared to designs derived without special regard for CCCs.

This paper addresses the problem of efficient and accurate performance analysis to drive the exploration and design of bus-based system-on-chip (SOC) communication architectures. Our technique fills a gap in existing techniques for system-level performance analysis, which are either too slow to use in an iterative communication architecture design framework (e.g., simulation of the complete system), or are not accurate enough to drive the design of the communication architecture (e.g., techniques that perform a static analysis of the system performance). The proposed system-level performance analysis technique consists of: initial co-simulation performed after HW/SW partitioning and mapping, with the communication between components modeled in an abstract manner (e.g., as events or data transfers); extraction of abstracted symbolic traces, represented as a bus and synchronization event (BSE) graph, that captures the activity of the various system components and their communication over time; and manipulation of the BSE graph using the bus parameters, to derive the behavior of the system accounting for effects of the bus architecture. We present experimental results on several example systems, including a TCP/IP network interface card sub-system. The results indicate that our performance estimation technique is over two orders of magnitude faster than performing a complete system simulation, while being very accurate (within 2.2% of performance estimates derived from accurate HW/SW co-simulation).

We propose a novel procedure based on uninterpreted symbolic simulation for checking the scheduling step in high-level synthesis. The primary task in scheduling is the assignment of time steps or, equivalently, states to operations. Various transformations like operation reordering and loop unrolling may be performed in the process to meet the optimization criteria. The contribution of our proposal lied in its ability to efficiently handle loops and a wide range of loop transformations performed during scheduling. Our algorithm is based on loop invariant extraction using a combination of uninterpreted symbolic simulation and induction techniques. In spite of its wide scope, our procedure is relatively complete and practical. This work is a part of our effort to provide a suite of techniques for verifying the various steps involved in the high-level synthesis process. It is being implemented in an in-house verification system for checking equivalence of designs generated from high-level specifications through successive refinements. We present case studies to demonstrate the applicability of our approach. These case studies consist of examples where equivalence cannot be established using conventional FSM-based methods. By providing a viable automated equivalence checking technique for such examples, we improve on the state of the art.

This paper presents a low-overhead controller-based power management technique that redesigns control logic to reconfigure the existing data path components under idle conditions so as to minimize unnecessary activity. Controller-based power management exploits the fact that though the control signals in a register-transfer level implementation are fully specified, they can be respecified under certain states/conditions when the data path components that they control need not be active. We demonstrate that controller-based power management is often better-suited to control-flow intensive designs than comparable conventional power management techniques such as operand isolation. We present an algorithm to perform power management through controller redesign that consists of constructing an activity graph for each data path component, identifying conditions under which the component need not be active, and relabeling the activity graph resulting in redesign of the corresponding control expressions. We provide a comprehensive analysis of the potential side effects of controller-based power management on circuit delay, glitching activity at control and data path signals, and formation of false combinational cycles. Our algorithm avoids the above negative effects of controller-based power management to maximize power savings and minimize overheads. We present experimental results which demonstrate that (1) controller-based power management results in large power savings at minimal overheads for control-flow intensive designs, which pose several challenges to conventional power management techniques and (2) it is important to consider the various potential negative effects while performing controller-based power management in order to obtain maximal power savings.

In this paper, we present design for testability (DFT) and hierarchical test generation techniques for facilitating the testing of application-specific programmable processors (ASPPs) and application-specific instruction processors (ASIPs). The method utilizes the register-transfer level (RTL) circuit description of an ASPP or ASIP to come up with a set of test microcode patterns which can be written into the instruction read-only memory (ROM) of the processor. These lines of microcode dictate a new control/data flow in the circuit and can be used to test modules which are not easily testable. The new control/data flow is used to justify precomputed test sets of a module from the system primary inputs to the module inputs and propagate output responses from the module output to the system primary outputs. The testability analysis, which is based on the relevant control/data flow extracted from the RTL circuit, is symbolic. Thus, it is independent of the bit-width of the data path and is extremely fast. The test microcode patterns are a by-product of this analysis. If the derived test microcode cannot test all untested modules in the circuit, then test multiplexers are added (usually to the off-critical paths of the data path) to test these modules. This is done to guarantee the testability of all modules in the circuit. If the control microcode memory of the processor is erasable, then the test microcode lines can be erased once the testing of the chip is over. In that case, the DFT scheme has very little overhead (typically less than 1%). Otherwise, the test microcode lines remain as an overhead in the control memory. The method requires the addition of only one external test pin. Application of this technique to several examples has resulted in a very high fault coverage (above 99.6%) for all of them. The test generation time is about three orders of magnitude smaller compared to an efficient gate-level sequential test generator. The average area overhead (without assuming an erasable ROM) is 3.1% while the delay overheads are negligible. This method does not require any scan in the controller or data path. It is also amenable to at-speed testing.

We present design-for-low-power techniques for register-transfer level (RTL) controller/data path circuits. We analyze the generation and propagation of glitches in both the control and data path parts of the circuit. In data-flow intensive designs, glitching power is primarily due to the chaining of arithmetic functional units. In control-flow intensive designs, on the other hand, multiplexer networks and registers dominate the total circuit power consumption, and the control logic can generate a significant amount of glitches at its outputs, which in turn propagate through the data path to account for a large portion of the glitching power in the entire circuit. Our analysis also highlights the relationship between the propagation of glitches from control signals and the bit-level correlation between data signals. Based on the analysis, we develop techniques that attempt to reduce glitching power consumption by minimizing propagation of glitches in the RTL circuit. Our techniques include restructuring multiplexer networks (to enhance data correlations and eliminate glitchy control signals), clocking control signals, and inserting selective rising/falling delays, in order to kill the propagation of glitches from control as well as data signals. In addition, we present a procedure to automatically perform the well-known power-reduction technique of clock gating through an efficient structural analysis of the RTL circuit, while avoiding the introduction of glitches on the clock signals. Application of the proposed power optimization techniques to several RTL circuits shows significant power savings, with negligible area and delay overheads.

In this paper, we present a power-management methodology targeted toward high-level synthesis of data-dominated behavioral descriptions. It is founded on the observation that variable assignment can significantly affect power-management opportunities in the synthesized architecture, i.e., variable assignment determines whether or not spurious operations get executed by functional units in the architecture. We introduce perfectly power managed architectures, whose functional units do not execute any spurious operations. We present a variable assignment technique which, when used in high-level synthesis, produces architectures which are perfectly power-managed. Unlike many previously proposed power-management techniques, our method does not add latches or any other circuitry in front of functional units or registers and is, therefore, free of the attendant performance penalty. Experimental results indicate savings of up to 52.5% (average 23.0%) in power consumption over already power-optimized architectures. The area overheads due to our technique are also low and averaged 2.5% for our examples.

Considering testability during the early stages of the design flow can have several benefits, including significantly improved fault coverage, reduced test hardware overheads, and reduced design iteration times. This paper presents an overview of high level design methodologies that consider testability during the early (behavior and architecture) stages of the design flow, and their testability benefits. The topics reviewed include behavioral and RTL test synthesis approaches that generate easily testable implementations targeting ATPG (full and partial scan) and BIST methodologies, and techniques to use high-level information for ATPG.

Speculative execution refers to the execution of parts of a computation before the execution of the conditional operations that decide whether it needs to be executed. It has been shown to be a promising technique for eliminating performance bottlenecks imposed by control flow in hardware and software implementations alike. In this paper, we present techniques to incorporate speculative execution in a fine-grained manner into scheduling of control-flow intensive behavioral descriptions. We demonstrate that failing to take into account information such as resource constraints and branch probabilities can lead to significantly sub-optimal performance. We also demonstrate that it may be necessary to speculate simultaneously along multiple paths, subject to resource constraints, in order to minimize the delay overheads incurred when prediction errors occur. Experimental results on several benchmarks show that our speculative scheduling algorithm can result in significant (upto seven-fold) improvements in performance (measured in terms of the average number of clock cycles) as compared to scheduling without speculative execution. Also, the best and worst case execution times for the speculatively performed schedules are the same as or better than the corresponding values for the schedules obtained without speculative execution.

We propose a complete procedure for verifying register-transfer logic against its scheduled behavior in a high-level synthesis environment Our proposal advances the state of the art because it is the first such verification procedure that is both complete and practical.Hardware verification is known to be a hard problem and the proposed verification technique leverages off the fact that highlevel synthesis -performed manually or by means of high-level synthesis software -proceeds from the algorithmic description of the design to structural RTL through a sequence of very well defined steps, each limited in its scope.The major contribution is the partitioning of the equivalence checking task into two simpler subtasks, verifying the validity of register sharing, and verifying correct synthesis of the RTL interconnect and control.While state space traversal is unavoidable for verifying validity of the register sharing, we automatically abstract out irrelevant portions oftbe design, significantly simpliQing the task that must be performed by a back-end model checker.The second task of verifying the RTL is not only shown to reduce to a combinational equivalence check,we present a novel and fast RTL technique for combinational equivalence check instead of using slower gate level techniques.The verification procedure has been applied to several large circuits, and is illustrated on the implementation of a sort algorithm.

We present techniques to transform scheduled descriptions of control-flow intensive designs to facilitate power management. We investigate the factors that inhibit the application of power management in synthesized RTL implementations. Based on these insights, we present transformation techniques based on the concepts of variable protection, variable re-naming and re-assignment, and limited controller state memory insertion that result in inherently powermanaged architectures. Our transformation techniques can be easily used in conjunction with any existing resource sharing algorithm or in the framework of existing high-level synthesis tools. Experimental results on control-flow intensive designs indicated reductions of upto 76.6% (35.6% on average) in power consumption at area overheads not exceeding 10.1% (1.1% on average) over already poweroptimized designs.

In this paper, we present a technique for extracting functional (control/data flow) information from register-transfer level controller/data path circuits, and illustrate its use in design for hierarchical testability of these circuits. This scheme does not require any additional behavioral information. It identifies a suitable control and data flow from the register-transfer level circuit, and uses it to test each embedded element in the circuit by symbolically justifying its precomputed test set from the system primary inputs to the element inputs and symbolically propagating the output response to the system primary outputs. When symbolic justification and propagation become difficult, it inserts test multiplexers at suitable points to increase the symbolic controllability and observability of the circuit. These test multiplexers are mostly restricted to off-critical paths. Testability analysis and insertion are completely based on the register-transfer level circuit and the functional information automatically extracted from it, and are independent of the data path bit width owing to their symbolic nature. Furthermore, the data path test set is obtained as a byproduct of this analysis without any further search. Unlike many other design-for-testability techniques, this scheme makes the combined controller-data path very highly testable. It is general enough to handle control-flow-intensive register-transfer level circuits like protocol handlers as well as data-flow intensive circuits like digital filters. It results in low area/delay/power overheads, high fault coverage, and very low test generation times (because it is symbolic and independent of bit width). Also, a large part of our system-level test sets can be applied at speed. Experimental results on many benchmarks show the average area, delay, and power overheads for testability to be 3.1, 1.0, and 4.2%, respectively. Over 99% fault coverage is obtained in most cases with two-four orders of magnitude test generation time advantage over an efficient gate-level sequential test pattern generator and one-three orders of magnitude advantage over an efficient gate-level combinational test pattern generator (that assumes full scan). In addition, the test application times obtained for our method are comparable with those of gate-level sequential test pattern generators, and up to two orders of magnitude smaller than designs using full scan.

Abstract — In this paper, we present design for testability (DFT) and hierarchical test generation techniques for facilitating the testing of application-specific programmable processors (ASPP’s) and application-specific instruction processors (ASIP’s). The method utilizes the register-transfer level (RTL) circuit description of an ASPP or ASIP to come up with a set of test microcode patterns which can be written into the instruction read-only memory (ROM) of the processor. These lines of microcode dictate a new control/data flow in the circuit and can be used to test modules which are not easily testable. The new control/data flow is used to justify precomputed test sets of a module from the system primary inputs to the module inputs and propagate output responses from the module output to the system primary outputs. The testability analysis, which is based on the relevant control/data flow extracted from the RTL circuit,

This paper presents a low-overhead controller-based powermanagement technique that re-specifies control signals to reconfigureexisting multiplexer networks and functional units to minimizeunnecessary activity. We demonstrate that conventional powermanagement techniques may often not be suited to control-flowintensive designs, and provide a comprehensive analysis of thepotential negative effects of power management on circuit delay,glitching activity at control and data path signals, and formationof false combinational cycles. We present techniques to performpower management through controller re-specification while avoidingthe above negative effects, and demonstrate the efficiency ofthe techniques through experiments.

We present a dynamic algorithm for test sequence compaction and test application time (TAT) reduction in combinational and sequential circuits. Several dynamic test compaction algorithms for combinational circuits have been proposed. However, few dynamic methods have been reported in the literature for sequential circuits. Our algorithm is based on two key ideas: (1) at any point during the test generation process, we identify bottlenecks that prevent vector compaction and TAT reduction for test sequences generated thus far, and (2) future test sequences are generated with an aim to eliminate bottlenecks of earlier generated test sequences. If all bottlenecks of a test sequence are eliminated, the sequence is dropped from the test set. Our algorithm can also target TAT reduction under the recently proposed partial scan-in/scan-out model by identifying and eliminating scan bottlenecks. If only the scan bottlenecks of a test sequence are eliminated, the test sequence can be trimmed to reduce the scan-in/scan-out cycles required to apply the sequence. For sequential circuits, we propose a sliding anchor frame technique to specify the unspecified inputs in a test sequence. The anchor frame is the first frame processed by a sequential test generator that is based on an iterative array model of the circuit, and the vector corresponding to the anchor frame is called the anchor vector. Under the sliding anchor frame technique, every vector in the test sequence being extended is considered as an anchor vector. This has the same effect as allowing observation of fault effects at every vector in the sequence, leading to a higher quality of compaction. The final test set generated by our algorithm cannot be further compacted using many known static vector compaction or TAT reduction techniques. For example, reverse or any other order of fault simulation, along with any specification of unspecified values in test sequences, cannot further reduce the number of vectors or TAT. Experimental results on combinational and sequential benchmark circuits, and large production VLSI circuits are reported to demonstrate the effectiveness of our approach.

In recent years, there has been growing interest in behavioral (high-level) synthesis for testability. This is due to the fact that testability features, such as scan or the built-in self-test, may incur large overheads if introduced during logic synthesis in the later phase of the design cycle. Related previous work attempted to generate system-level test sets using hierarchical testability during behavioral synthesis. There, the test generation scheme is independent of bit width and is, therefore, capable of handling complex controller/data path circuits with large data path bit widths (e.g., 32), which has posed a serious challenge to logic-level sequential test generators. However, this previous work is not applicable when another high-level synthesis system is used. In this paper, we present techniques that add minimal test hardware to a given register-transfer level (RTL) circuit obtained by behavioral synthesis in order to ensure that the embedded elements in the circuit are hierarchically testable. An important byproduct of our design for testability (DFT) procedure is a system-level test set that delivers precomputed test sets to each element in the RTL circuit. This eliminates the need to apply gate-level sequential test generation to the combined controller/data path. We performed extensive experiments with several complex controller/data path circuits synthesized by three different high-level synthesis systems which do not target testability. The key advantages of our method, illustrated by these experiments, include: 1) the area, delay, and power overheads incurred for testability are very low (the average area, delay, and power overheads for a large number of benchmarks are 3.5, 0.5, and 3.4%, respectively), 2) both the DFT hardware addition and test generation algorithms are independent of the data path bit width.

In this paper, we present SCALP, a comprehensive low-power data path synthesis system that performs the various high-level synthesis tasks (transformations, scheduling, clock selection, module selection, and hardware allocation and assignment) with an aim of reducing the power consumption in the synthesized data path. Focusing on only one or a small subset of the high-level synthesis tasks makes it difficult to realize the full potential for power savings at the algorithm and architecture levels. Our synthesis algorithms, which are based on an iterative improvement strategy with efficient pruning techniques, are capable of performing the various high-level synthesis tasks (and considering their interactions) in an efficient manner. Supply voltage and clock period pruning strategies are used for quickly eliminating inferior design points during the search for the minimum power solution. Estimating switched capacitance accurately at intermediate stages during high-level synthesis can be challenging since the exact structure of the circuit, which affects both physical capacitance and switching activity, may not be available, and due to the high computational complexity of running register-transfer level power analysis tools several times during high-level synthesis. SCALP overcomes the above problems by maintaining a complete image of the structural register-transfer level (RTL) circuit (this is possible since we have a complete solution at any point during iterative improvement), and employing a very fast switched capacitance estimation technique that Is based on the concept of switched capacitance matrices. Our system can handle diverse module libraries and utilize complex scheduling constructs such as multicycling, chaining, and structural pipelining. Retiming and functional pipelining are used in our system to meet tight performance constraints, and to enable the ensuing synthesis steps to better explore the implementation space. Results on several real-life examples are presented to demonstrate the effectiveness of the algorithm. Power estimates obtained using switch-level simulation after layout indicate that up to an order-of-magnitude of power savings can be obtained using our synthesis system.

We present design-for-low-power techniques based on glitch reduction for register-transfer level circuits.We analyze the generation and propagation of glitches in both the control and data path parts of the circuit.Based on the analysis, we develop techniques that attempt to reduce glitching power consumption by minimizing generation and propagation of glitches in the RTL circuit.Our techniques include restructuring multiplexer networks (to enhance data correlations, eliminate glitchy control signals, and reduce glitches on data signals), clocking control signals, and inserting selective rising/falling delays.Our techniques are suited to control-flow intensive designs, where glitches generated at control signals have a significant impact on the circuit's power consumption, and multiplexers and registers often account for a major portion of the total power.Application of the proposed techniques to several examples shows significant power savings, with negligible area and delay overheads.

We present a technique for extracting functional (control/dataflow) information from register transfer level (RTL) controller/data path circuits and illustrate its use in design for hierarchical testability of these circuits. This testing procedure and design for testability (DFT) technique is general enough to handle RTL control flow intensive circuits like protocol handlers as well as data flow intensive circuits like digital filters. It makes the combined controller-data path highly testable and does not require any external behavioral information. This scheme has the advantages of low area/delay/power overheads (average of 3.2%, 0.9% and 4.1%, respectively, for benchmarks), high fault coverage (over 99% for most cases), very low test generation times (because it is independent of bit-width), and the advantage of at-speed testing. Experiments show a 2-to-4 (1-to-3) orders of magnitude test generation time advantage over an efficient gate-level sequential test generator (combinational test generator that assumes full scan).

We present techniques for estimating switching activity and power consumption in register-transfer level (RTL) circuits. Previous work on this topic has ignored the presence of glitching activity at various data path and control signals, which can lead to significant underestimation of switching activity. For data path blocks that operate on word-level data, we construct piecewise linear models that capture the variation of output glitching activity and power consumption with various word-level parameters like mean, standard deviation, spatial and temporal correlations, and glitching activity at the block's inputs. For RTL blocks that operate on data that need not have an associated word-level value, we present accurate bit-level modeling techniques for glitching activity as well as power consumption. This allows us to perform accurate power estimation for control-flow intensive circuits, where most of the power consumed is dissipated in non-arithmetic components like multiplexers, registers, vector logic operators, etc. Since the final implementation of the controller is not available during high-level design iterations, we develop techniques that estimate glitching activity at control signals using control expressions and partial delay information. Experiments on example RTL designs resulted in power estimates that were within 7% of those produced by an inhouse power analysis tool on the final gate-level implementation.

This paper proposes a controller-based technique for minimizing switching activity in controller/data path circuits. Though the control signals in a register transfer level (RTL) implementation are fully specified, they can be respecified under certain states/conditions when the data path components that they control need not be active. Unlike techniques that insert extra circuitry like transparent latches, controller re-specification is a low-overhead technique that merely reconfigures existing multiplexer networks and functional units to minimize activity in the data path. Hence, it is well suited to control-flow intensive designs, where power consumption in multiplexer networks forms a major component of the total power consumption. Our controller re-specification algorithm consists of constructing an activity graph for each data path component, identifying conditions under which the component need not be active, and re-labeling the activity graph resulting in re-specification of the corresponding control expressions. Application of the proposed technique to several RTL circuits demonstrated the ability to reduce the total (controller+data path) power consumption by up to 51.8% compared to the initial area-optimized implementations, with nominal area and delay overheads.

We present several techniques for accelerating dynamic vector compaction for combinational and sequential circuits. A key feature of all our techniques is that they significantly improve the computation times without adversely affecting the quality of test sets that can be derived using state-of-the-art compaction methods. Our techniques are based on three key ideas: (1) identification of support sets, (2) target fault switching, and (3) use of dynamic equivalent and untestable fault analysis, All these techniques are useful in significantly reducing the number of faults that have to be considered by a test generator or a fault simulator in a dynamic vector compaction system. For fault simulation, support sets quickly identify a large subset of faults that are guaranteed to be undetectable by a given input sequence. For test generation, support sets identify a large subset of faults that are guaranteed to be undetectable by any extension of a partially specified test sequence. Experimental results on ISCAS 89 benchmark circuits and large production VLSI circuits are included. For full scan designs, our acceleration techniques reduce the overall computation times by a factor of 2 to 3 without adversely affecting the quality (size) of the computed test sets or their fault coverages. The improvement factors obtained are higher for larger circuits. The acceleration techniques enabled the computation of compact test sets for large production circuits that the base test generation system was unable to process in more than 2 CPU days on a Silicon Graphics MIPS 4400 workstation. Results for sequential circuits also show that our acceleration techniques significantly improve the computation times for dynamic vector compaction.

We address the problem of minimizing power consumption in behavioral synthesis of data-dominated circuits. The complex nature of power as a cost function implies that the effects of several behavioral synthesis tasks like module selection, clock selection, scheduling and resource sharing on supply voltage and switched capacitance need to be considered simultaneously to fully derive the benefits of design space exploration at the behavior level. We present an efficient algorithm for performing scheduling, clock selection, module selection, and resource allocation and assignment simultaneously with an aim of reducing the power consumption in the synthesized data path. The algorithm, which is based on an iterative improvement strategy, is capable of escaping local minima in its search for a low power solution. The algorithm considers diverse module libraries and complex scheduling constructs such as multicycling chaining, and structural pipelining. We describe supply voltage and clock pruning strategies that significantly improve the efficiency of our algorithm by cutting down on the computational effort involved in exploring candidate supply voltages and clock periods that are unlikely to lead to the best solution. Experimental results are reported to demonstrate the effectiveness of the algorithm. Our techniques can be combined with other known methods of behavioral power optimization like data path replication and transformations, to result in a complete data path synthesis system for low power applications.

Most behavioral synthesis and design for testability techniques target subsequent gate-level sequential test generation, which is frequently incapable of handling complex controller/data path circuits with large data path bit-widths. Hierarchical testing attempts to counter the complexity of test generation by exploiting information from multiple levels of the design hierarchy. We present techniques that add minimal test hardware to the given register-transfer level (RTL) design obtained through behavioral synthesis in order to ensure that all the embedded modules in the circuit are hierarchically testable. An important by-product of our DFT procedure is a system-level test set that is guaranteed to deliver pre-computed module test sets to each module in the RTL circuit. This eliminates the need to apply gate-level sequential test generation to the controller/data path. We performed extensive experiments with several complex data path/controller circuits synthesized by two different high level synthesis systems which do not target testability.

Power consumption has been established as an important factor in the synthesis of VLSI circuits. However, very little work has been done at the behavior level for power estimation and low power synthesis. We demonstrate how hardware sharing affects the capacitance and transition activity, and hence the power dissipation in the synthesized data paths, and that the power-optimal allocation varies with input characteristics. We present a simulation-based method that measures both intra- and inter-iteration effects of hardware sharing on switched capacitance. This method enables us to accurately capture sufficient information to evaluate allocation options from a switched capacitance point of view. Using the information thus obtained, we formulate allocation as an Integer Linear Programming (ILP) problem with the total switched capacitance in the data path as the objective function. Thus, the decisions of how much hardware sharing should be performed and what allocation is best from the power point of view, are performed optimally for the given model. Experimental results are presented including accurate power measurements made at the switch level.

Circuits that have an underlying acyclic topology are guaranteed to be combinational since feedback is necessary for sequential behavior. However, the reverse is not true, i,e., feedback is not a sufficient condition since there do exist combinational logic circuits that are cyclic. In fact, such combinational circuits occur often in bus structures in data paths. This class of circuits has largely been ignored by conventional combinational single-stuck-at fault test pattern generators which assume that the circuit topology is acyclic. There has not been a formal study of the test generation problem for these circuits. Also, no algorithms and tools exist for this purpose. In practice, test generation for these circuits is handled in an awkward manner, typically with poor fault coverage. This work provides, for the first time, a formal analysis of the test generation problem for these circuits. This analysis leads to a clear insight into generation of tests, as well as a classification of untestable faults for such circuits. We demonstrate that cyclic combinational circuits may have untestable faults that do not correspond to redundancies. This insight is then translated to a testing algorithm which has been implemented in the program RAM. RAM has been successful in providing complete or near complete coverage on a range of typical examples, which is significantly higher than that provided by conventional techniques.>

We present a behavioral synthesis method targeting low power consumption for data-dominated CMOS circuits. A study of how the high-level synthesis process affects power consumption is presented, based on, which we have developed the first allocation method for low power. We also present a method of optimizing the controller to reduce data path power dissipation. We consider loops, conditional branches, and scheduling constructs such as multicycling, chaining and structural pipelining. The techniques were implemented within the framework of an existing behavioral synthesis system. Experiments performed on various examples and benchmarks show that low power circuits can be synthesized by our method with very low or zero overheads.>