In this paper, we propose a novel agentic AI system called XPF, which enables users to create "agents" using just natural language, where each agent is capable of executing complex, real-world business workflows in an accurate and reliable manner. XPF provides an interface to develop and iterate over the agent creation process and then deploy the agent in production when satisfactory results are produced consistently. The key components of XPF include: (a) planner, which leverages LLM to generate a step-by-step plan, which can further be edited by a human (b) compiler, which leverages LLM to compile the plan into a flow graph (c) executor, which handles distributed execution of the flow graph (using LLM, tools, RAG, etc.) on an underlying cluster and (d) verifier, which helps in verification of the output (through human generated tests or auto-generated tests using LLM). We develop five different agents using XPF and conduct experiments to evaluate one particular aspect i.e. difference in accuracy and reliability of the five agents with "human-generated" vs "auto-generated" plans. Our experiments show that we can get much more accurate and reliable response for a business workflow when step-by-step instructions (in natural language) are given by a human familiar with the workflow, rather than letting the LLM figure out the execution plan steps. In particular, we observe that "human-generated" plan almost always gives 100% accuracy whereas "auto-generated" plan almost never gives 100% accuracy. In terms of reliability, we observe through Rouge-L, Blue and Meteor scores, that the output from "human-generated" plan is much more reliable than "auto-generated" plan.

Roadside LiDAR (Light Detection and Ranging) sensors promise safer and faster traffic management and vehicular operations. However, occlusion and small view angles are significant challenges to widespread use of roadside LiDARs. We consider fusing data from multiple LiDARs at a traffic intersection to better estimate traffic parameters than one can estimate from a single LiDAR. The key challenge is to calibrate multiple LiDARs both in time and space. The problem is more complex when heterogeneous sensors differ in resolution and are positioned arbitrarily on a traffic intersection.

In Video Analytics Pipelines (VAP), Analytics Units (AUs) such as object detection and face recognition operating on remote servers rely heavily on surveillance cameras to capture high-quality video streams to achieve high accuracy. Modern network cameras offer an array of parameters that directly influence video quality. While a few of such parameters, e.g., exposure, focus and white balance, are automatically adjusted by the camera internally, the others are not. We denote such camera parameters as non-automated (NAUTO) parameters. In this work, we first show that in a typical surveillance camera deployment, environmental condition changes can have significant adverse effect on the accuracy of insights from the AUs, but such adverse impact can potentially be mitigated by dynamically adjusting NAUTO camera parameters in response to changes in environmental conditions. Second, since most end-users lack the skill or understanding to appropriately configure these parameters and typically use a fixed parameter setting, we presentCamTuner, to our knowledge, the first framework that dynamically adapts NAUTO camera parameters to optimize the accuracy of AUs in a VAP in response to adverse changes in environmental conditions.CamTuneris based on SARSA reinforcement learning and it incorporates two novel components: a light-weight analytics quality estimator and a virtual camera that drastically speed up offline RL training. Our controlled experiments and real-world VAP deployment show that compared to a VAP using the default camera setting,CamTunerenhances VAP accuracy by detecting 15.9% additional persons and 2.6% –4.2% additional cars (without any false positives) in a large enterprise parking lot.CamTuneropens up new avenues for elevating video analytics accuracy, transcending mere incremental enhancements achieved through refining deep-learning models.

Retrieval-augmented generation (RAG) systems combine the strengths of language generation and information retrieval to power many real-world applications like chatbots. Use of RAG for understanding of videos is appealing but there are two critical limitations. One-time, upfront conversion of all content in large corpus of videos into text descriptions entails high processing times. Also, not all information in the rich video data is typically captured in the text descriptions. Since user queries are not known apriori, developing a system for video to text conversion and interactive querying of video data is challenging.

Ensuring high-quality video content for wireless users has become increasingly vital. Nevertheless, maintaining a consistent level of video quality faces challenges due to the fluctuating encoded bitrate, primarily caused by dynamic video content, especially in live streaming scenarios. Video compression is typically employed to eliminate unnecessary redundancies within and between video frames, thereby reducing the required bandwidth for video transmission. The encoded bitrate and the quality of the compressed video depend on encoder parameters, specifically, the quantization parameter (QP). Poor choices of en-coder parameters can result in reduced bandwidth efficiency and high likelihood of non-conformance. Non-conformance refers to the violation of the peak signal-to-noise ratio (PSNR) constraint for an encoded video segment. To address these issues, a real-time deep learning-based H.264 controller is proposed. This controller dynamically estimates the optimal encoder parameters based on the content of a video chunk with minimal delay. The objective is to maintain video quality in terms of PSNR above a specified threshold while minimizing the average bitrate of the compressed video. Experimental results, conducted on both QCIF dataset and a diverse range of random videos from public datasets, validate the effectiveness of this approach. Notably, it achieves improvements of up to 2.5 times in average bandwidth usage compared to the state-of-the-art adaptive bitrate video streaming, with a negligible non-conformance probability below 10−2.

Edge computing has emerged as a transformative technology that reduces application latency, improves cost efficiency, enhances security, and enables large-scale deployment of applications across various domains. In environmental monitoring, systems such as MegaSense[49], use low-cost sensors to gather and process real-time air quality data through edge-cloud collaboration, highlighting the critical role of edge computing in enabling scalable, efficient solutions. Similarly, marine science increasingly requires real-time processing and analysis of marine data from remote, resource-constrained environments. In this paper, we extend the power of edge computing by integrating it with Generative Artificial Intelligence(GenAI),specifically large language models (LLMs), to address challenges in marine science applications. We propose DiCE-M (Distributed Code generation and Execution for Marine applications), a robust system that uses LLM to generate distributed code for marine applications and then utilizes a runtime to efficiently execute it on an edge+cloud computing infrastructure. Specifically, DiCE-M leverages edge computing to execute lightweight AI models locally on unmanned surface vehicles(USVs)while offloading complex tasks to the cloud, thus balancing computational load and enabling realtime monitoring in marine environments. We use marine litter identification as an example application to demonstrate the utility of DiCE-M. Our results show that DiCE-M reduces latency by more than 2X when marine litter is not detected and cuts cloud computing costs by more than half compared to traditional cloud-based approaches. By selectively cropping and transmitting relevant image portions, DiCE-M further improves bandwidth efficiency, making it a reliable and cost-effective solution for deploying AI-drivenapplications on resource-constrained USVs in dynamic marine environments.

One of the key metrics of interest for stream processing applications is “latency”, which indicates the total time it takes for the application to process and generate insights from streaming input data. For mission-critical video analytics applications like surveillance and monitoring, it is of paramount importance to report an incident as soon as it occurs so that necessary actions can be taken right away. Stream processing applications are typically developed as a chain of microser-vices and are deployed on container orchestration platforms like Kubernetes. Allocation of system resources like “cpu” and “memory” to individual application microservices has direct impact on “latency”. Kubernetes does provide ways to allocate these resources e.g. through fixed resource allocation or through vertical pod autoscaler (VPA), however there is no straight-forward way in Kubernetes to prioritize “latency” for an end-to-end application pipeline. In this paper, we present LARA, which is specifically designed to improve “latency” of stream processing application pipelines. LARA uses a regression-based technique for resource allocation to individual microservices. We implement four real-world video analytics application pipelines i.e. license plate recognition, face recognition, human attributes detection and pose detection, and show that compared to fixed allocation, LARA is able to reduce latency by up to 2.8X and is consistently better than VPA. While reducing latency, LARA is also able to deliver over 2X throughput compared to fixed allocation and is almost always better than VPA.

JPEG remains one of the most widespread lossy image coding methods. However, the non-differentiable nature of JPEG restricts the application in deep learning pipelines. Several differentiable approximations of JPEG have recently been proposed to address this issue. This paper conducts a comprehensive review of existing diff. JPEG approaches and identifies critical details that have been missed by previous methods. To this end, we propose a novel diff. JPEG approach, overcoming previous limitations. Our approach is differentiable w.r.t. the input image, the JPEG quality, the quantization tables, and the color conversion parameters. We evaluate the forward and backward performance of our diff. JPEG approach against existing methods. Additionally, extensive ablations are performed to evaluate crucial design choices. Our proposed diff. JPEG resembles the (non-diff.) reference implementation best, significantly surpassing the recent-best diff. approach by 3.47dB (PSNR) on average. For strong compression rates, we can even improve PSNR by 9.51dB. Strong adversarial attack results are yielded by our diff. JPEG, demonstrating the effective gradient approximation. Our code is available at https://github.com/necla-ml/Diff-JPEG.

Modern applications are designed as an interacting set of microservices, and these applications are typically deployed on container orchestration platforms like Kubernetes. Several attractive features in Kubernetes make it a popular choice for deploying applications, and automatic scaling is one such feature. The default horizontal scaling technique in Kubernetes is the Horizontal Pod Autoscaler (HPA). It scales each microservice independently while ignoring the interactions among the microservices in an application. In this paper, we show that ignoring such interactions by HPA leads to inefficient scaling, and the optimal scaling of different microservices in the application varies as the stream content changes. To automatically adapt to variations in stream content, we present a novel system called DataX AutoScaler that leverages knowledge of the entire stream processing application pipeline to efficiently auto-scale different microservices by taking into account their complex interactions. Through experiments on real-world video analytics applications, such as face recognition and pose classification, we show that DataX AutoScaler adapts to variations in stream content and achieves up to 43% improvement in overall application performance compared to a baseline system that uses HPA.

Edge Intelligence has received attention in the recent times for its potential towards improving responsiveness, reducing the cost of data transmission, enhancing security and privacy, and enabling autonomous decisions by edge devices. However, edge devices lack the power and compute resources necessary to execute most Al models. In this paper, we present FactionFormer, a novel method to deploy resource-intensive deep-learning models, such as vision transformers (ViT), on resource-constrained edge devices. Our method is based on a key observation: edge devices are often deployed in settings where they encounter only a subset of the classes that the resource-intensive Al model is trained to classify, and this subset changes across deployments. Therefore, we automatically identify this subset as a faction, devise on-the fly a bespoke resource-efficient ViT called a modelette for the faction, and set up an efficient processing pipeline consisting of a modelette on the device, a wireless network such as 5G, and the resource-intensive ViT model on an edge server, all of which work collaboratively to do the inference. For several ViT models pre-trained on benchmark datasets, FactionFormer’s modelettes are up to 4× smaller than the corresponding baseline models in terms of the number of parameters, and they can infer up to 2.5× faster than the baseline setup where every input is processed by the resource-intensive ViT on the edge server. Our work is the first of its kind to propose a device-edge collaborative inference framework where bespoke deep learning models for the device are automatically devised on-the-fly for most frequently encountered subset of classes.

IoT sensors, especially video cameras, are ubiquitously deployed around the world to perform a variety of computer vision tasks in several verticals including retail, health-care, safety and security, transportation, manufacturing, etc. To amortize their high deployment effort and cost, it is desirable to perform multiple video analytics tasks, which we refer to as Analytical Units (AUs), off the video feed coming out of every camera. As AUs typically use deep-learning based AI/ML models, their performances depend on the quality of the input video. The most recent work has shown that dynamically adjusting the camera setting exposed by popular network cameras can help improve the quality of the video feed and hence the AU accuracy, in a single AU setting. In this paper, we first show that in a multi-AU setting, changing the camera setting has disproportionate impact on different AUs performance. In particular, the optimal setting for one AU may severely degrade the performance for another AU, and further, the impact on different AUs varies as the environmental condition changes. We then present Elixir, a system to enhance the video stream quality for multiple analytics on a video stream. Elixir leverages Multi-Objective Reinforcement Learning (MORL), where the RL agent caters to the objectives from different AUs and adjusts the camera setting to simultaneously enhance the performance of all AUs. To define the multiple objectives in MORL, we develop new AU-specific quality estimator values for each individual AU. We evaluate Elixir through real-world experiments on a testbed with three cameras deployed next to each other (overlooking a large enterprise parking lot) running Elixir and two baseline approaches, respectively. Elixir correctly detects 7.1% (22,068) and 5.0% (15,731) more cars, 94% (551) and 72% (478) more faces, and 670.4% (4975) and 158.6% (3507) more persons than the default-setting and time-sharing approaches, respectively. It also detects 115 license plates, far more than the time-sharing approach (7) and the default setting (0).

We present "Application in a Box" (AnB) product concept aimed at simplifying the deployment and operation of remote 5G applications. AnB comes pre-configured with all necessary hardware and software components, including sensors like cameras, hardware and software components for a local 5G wireless network, and 5G-ready apps. Enterprises can easily download additional apps from an App Store. Setting up a 5G infrastructure and running applications on it is a significant challenge, but AnB is designed to make it fast, convenient, and easy, even for those without extensive knowledge of software, computers, wireless networks, or AI-based analytics. With AnB, customers only need to open the box, set up the sensors, turn on the 5G networking and edge computing devices, and start running their applications. Our system software automatically deploys and optimizes the pipeline of microservices in the application on a tiered computing infrastructure that includes device, edge, and cloud computing. Application scalability, dynamic resource management, placement of critical tasks for low-latency response, and dynamic network bandwidth allocation for efficient 5G network usage are all automatically orchestrated.AnB offers cost savings, simplified setup and management, and increased reliability and security. We’ve implemented several real-world applications, such as collision prediction at busy traffic light intersections and remote construction site monitoring using video analytics. With AnB, deployment and optimization effort can be reduced from several months to just a few minutes. This is the first-of-its-kind approach to easing deployment effort and automating self-optimization of the application during system operation.

Millions of cameras at the edge are being deployed to power a variety of different deep learning applications. However, the frames captured by these cameras are not always pristine—they can be distorted due to lighting issues, sensor noise, compression etc. Such distortions not only deteriorate visual quality, they impact the accuracy of deep learning applications that process such video streams. In this work, we introduce AQuA, to protect application accuracy against such distorted frames by scoring the level of distortion in the frames. It takes into account the analytical quality of frames, not the visual quality, by learning a novel metric, classifier opinion score , and uses a lightweight, CNN-based, object-independent feature extractor. AQuA accurately scores distortion levels of frames and generalizes to multiple different deep learning applications. When used for filtering poor-quality frames at edge, it reduces high-confidence errors for analytics applications by 17%. Through filtering, and due to its low overhead (14 ms), AQuA can also reduce computation time and average bandwidth usage by 25%. Finally, we discuss numerous new avenues of optimizations of video analytics pipelines enabled by AQuA.

Roadside LiDAR (Light Detection and Ranging) sensors are recently being explored for intelligent transportation systems aiming at safer and faster traffic management and vehicular operations. A key challenge in such systems is to efficiently transfer massive point-cloud data from the roadside LiDAR devices to the edge connected through a 5G network for real-time processing. In this paper, we consider the problem of compressing roadside (i.e. static) LiDAR data in real-time that provides a unique condition unexplored by current methods. Existing point-cloud compression methods assume moving LiDARs (that are mounted on vehicles) and do not exploit spatial consistency across frames over time.

Meta learning algorithms for few-shot video recognition use complex, episodic training but they often fail to learn effective feature representations. In contrast, we propose a new and simpler few-shot video recognition method that does not use meta-learning, but its performance compares well with the best meta-learning proposals. Our new few-shot video classification pipeline consists of two distinct phases. In the pre-training phase, we learn a good video feature extraction network that generates a feature vector for each video. After a sparse sampling strategy selects frames from the video, we generate a video feature vector from the sampled frames. Our proposed video feature extractor network, which consists of an image feature extraction network followed by a new transformer encoder, is trained end-to-end by including a classifier head that uses cosine similarity layer instead of the traditional linear layer to classify a corpus of labeled video examples. Unlike prior work in meta learning, we do not use episodic training to learn the image feature vector. Also, unlike prior work that averages frame-level feature vectors into a single video feature vector, we combine individual frame-level feature vectors by using a new Transformer encoder that explicitly captures the key, temporal properties in the sequence of sampled frames. End-to-end training of the video feature extractor ensures that the proposed Transformer encoder captures important temporal properties in the video, while the cosine similarity layer explicitly reduces the intra-class variance of videos that belong to the same class. Next, in the few-shot adaptation phase, we use the learned video feature extractor to train a new video classifier by using the few available examples from novel classes. Results on SSV2-100 and Kinetics-100 benchmarks show that our proposed few-shot video classifier outperforms the meta-learning-based methods and achieves the best state-of-the-art accuracy. We also show that our method can easily discern between actions and their inverse (for example, picking something up vs. putting something down), while prior art, which averages image feature vectors, is unable to do so.

With the growth of 5G, Internet of Things (IoT), edge computing and cloud computing technologies, the infrastructure (compute and network) available to emerging applications (AR/VR, autonomous driving, industry 4.0, etc.) has become quite complex. There are multiple tiers of computing (IoT devices, near edge, far edge, cloud, etc.) that are connected with different types of networking technologies (LAN, LTE, 5G, MAN, WAN, etc.). Deployment and management of applications in such an environment is quite challenging. In this paper, we propose ROMA, which performs resource orchestration for microservices-based 5G applications in a dynamic, heterogeneous, multi-tiered compute and network fabric. We assume that only application-level requirements are known, and the detailed requirements of the individual microservices in the application are not specified. As part of our solution, ROMA identifies and leverages the coupling relationship between compute and network usage for various microservices and solves an optimization problem in order to appropriately identify how each microservice should be deployed in the complex, multi-tiered compute and network fabric, so that the end-to-end application requirements are optimally met. We implemented two real-world 5G applications in video surveillance and intelligent transportation system (ITS) domains. Through extensive experiments, we show that ROMA is able to save up to 90%, 55% and 44% compute and up to 80%, 95% and 75% network bandwidth for the surveillance (watchlist) and transportation application (person and car detection), respectively. This improvement is achieved while honoring the application performance requirements, and it is over an alternative scheme that employs a static and overprovisioned resource allocation strategy by ignoring the resource coupling relationships.

In Video Analytics Pipelines (VAP), Analytics Units (AUs) such as object detection and face recognition running on remote servers critically rely on surveillance cameras to capture high-quality video streams in order to achieve high accuracy. Modern IP cameras come with a large number of camera parameters that directly affect the quality of the video stream capture. While a few of such parameters, e.g., exposure, focus, white balance are automatically adjusted by the camera internally, the remaining ones are not. We denote such camera parameters as non-automated (NAUTO) parameters. In this paper, we first show that environmental condition changes can have significant adverse effect on the accuracy of insights from the AUs, but such adverse impact can potentially be mitigated by dynamically adjusting NAUTO camera parameters in response to changes in environmental conditions. We then present CamTuner, to our knowledge, the first framework that dynamically adapts NAUTO camera parameters to optimize the accuracy of AUs in a VAP in response to adverse changes in environmental conditions. CamTuner is based on SARSA reinforcement learning and it incorporates two novel components: a light-weight analytics quality estimator and a virtual camera that drastically speed up offline RL training. Our controlled experiments and real-world VAP deployment show that compared to a VAP using the default camera setting, CamTuner enhances VAP accuracy by detecting 15.9% additional persons and 2.6%--4.2% additional cars (without any false positives) in a large enterprise parking lot and 9.7% additional cars in a 5G smart traffic intersection scenario, which enables a new usecase of accurate and reliable automatic vehicle collision prediction (AVCP). CamTuner opens doors for new ways to significantly enhance video analytics accuracy beyond incremental improvements from refining deep-learning models.

Design of multitasking deep learning models has mostly focused on improving the accuracy of the constituent tasks, but the challenges of efficiently deploying such models in a device-edge collaborative setup (that is common in 5G deployments) has not been investigated. Towards this end, in this paper, we propose an approach called Chimera1for training (done Offline) and deployment (done Online) of multitasking deep learning models that are splittable across the device and edge. In the offline phase, we train our multi-tasking setup such that features from a pre-trained model for one of the tasks (called the Primary task) are extracted and task-specific sub-models are trained to generate the other (Secondary) tasks' outputs through a knowledge distillation like training strategy to mimic the outputs of pre-trained models for the tasks. The task-specific sub-models are designed to be significantly lightweight than the original pre-trained models for the Secondary tasks. Once the sub-models are trained, during deployment, for given deployment context, characterized by the configurations, we search for the optimal (in terms of both model performance and cost) deployment strategy for the generated multitasking model, through finding one or multiple suitable layer(s) for splitting the model, so that inference workloads are distributed between the device and the edge server and the inference is done in a collaborative manner. Extensive experiments on benchmark computer vision tasks demonstrate that Chimera generates splittable multitasking models that are at least ~ 3 x parameter efficient than the existing such models, and the end-to-end device-edge collaborative inference becomes ~ 1.35 x faster with our choice of context-aware splitting decisions.

Devices with limited computing resources use smaller AI models to achieve low-latency inferencing. However, model accuracy is typically much lower than the accuracy of a bigger model that is trained and deployed in places where the computing resources are relatively abundant. We describe DyCo, a novel system that ensures privacy of stream data and dynamically improves the accuracy of small models used in devices. Unlike knowledge distillation or federated learning, DyCo treats AI models as black boxes. DyCo uses a semi-supervised approach to leverage existing training frameworks and network model architectures to periodically train contextualized, smaller models for resource-constrained devices. DyCo uses a bigger, highly accurate model in the edge-cloud to auto-label data received from each sensor stream. Training in the edge-cloud (as opposed to the public cloud) ensures data privacy, and bespoke models for thousands of live data streams can be designed in parallel by using multiple edge-clouds. DyCo uses the auto-labeled data to periodically re-train, stream-specific, bespoke small models. To reduce the periodic training costs, DyCo uses different policies that are based on stride, accuracy, and confidence information. We evaluate our system, and the contextualized models, by using two object detection models for vehicles and people, and two datasets (a public benchmark and another real-world proprietary dataset). Our results show that DyCo increases the mAP accuracy measure of small models by an average of 16.3% (and up to 20%) for the public benchmark and an average of 19.0% (and up to 64.9%) for the real-world dataset. DyCo also decreases the training costs for contextualized models by more than an order of magnitude.

Centralized cloud computing with 100+ milliseconds network latencies cannot meet the tens of milliseconds to sub-millisecond response times required for emerging 5G applications like autonomous driving, smart manufacturing, tactile internet, and augmented or virtual reality. We describe a new, dynamic runtime that enables such applications to make effective use of a 5G network, computing at the edge of this network, and resources in the centralized cloud, at all times. Our runtime continuously monitors the interaction among the microservices, estimates the data produced and exchanged among the microservices, and uses a novel graph min-cut algorithm to dynamically map the microservices to the edge or the cloud to satisfy application-specific response times. Our runtime also handles temporary network partitions, and maintains data consistency across the distributed fabric by using microservice proxies to reduce WAN bandwidth by an order of magnitude, all in an application-specific manner by leveraging knowledge about the application's functions, latency-critical pipelines and intermediate data. We illustrate the use of our runtime by successfully mapping two complex, representative real-world video analytics applications to the AWS/Verizon Wavelength edge-cloud architecture, and improving application response times by 2x when compared with a static edge-cloud implementation.

Microservices-based video analytics pipelines routinely use multiple deep convolutional neural networks. We observe that the best allocation of resources to deep learning engines (or microservices) in a pipeline, and the best configuration of parameters for each engine vary over time, often at a timescale of minutes or even seconds based on the dynamic content in the video. We leverage these observations to develop Magic-Pipe, a self-optimizing video analytic pipeline that leverages AI techniques to periodically self-optimize. First, we propose a new, adaptive resource allocation technique to dynamically balance the resource usage of different microservices, based on dynamic video content. Then, we propose an adaptive microservice parameter tuning technique to balance the accuracy and performance of a microservice, also based on video content. Finally, we propose two different approaches to reduce unnecessary computations due to unavoidable mismatch of independently designed, re-usable deep-learning engines: a deep learning approach to improve the feature extractor performance by filtering inputs for which no features can be extracted, and a low-overhead graph-theoretic approach to minimize redundant computations across frames. Our evaluation of Magic-Pipe shows that pipelines augmented with self-optimizing capability exhibit application response times that are an order of magnitude better than the original pipelines, while using the same hardware resources, and achieving similar high accuracy.

Identification of people with elevated body temperature can reduce or dramatically slow down the spread of infectious diseases like COVID-19. We present a novel fever-screening system, F3S, that uses edge machine learning techniques to accurately measure core body temperatures of multiple individuals in a free-flow setting. F3S performs real-time sensor fusion of visual camera with thermal camera data streams to detect elevated body temperature, and it has several unique features: (a) visual and thermal streams represent very different modalities, and we dynamically associate semantically-equivalent regions across visual and thermal frames by using a new, dynamic alignment technique that analyzes content and context in real-time, (b) we track people through occlusions, identify the eye (inner canthus), forehead, face and head regions where possible, and provide an accurate temperature reading by using a prioritized refinement algorithm, and (c) we robustly detect elevated body temperature even in the presence of personal protective equipment like masks, or sunglasses or hats, all of which can be affected by hot weather and lead to spurious temperature readings. F3S has been deployed at over a dozen large commercial establishments, providing contact-less, free-flow, real-time fever screening for thousands of employees and customers in indoors and outdoor settings.

The massively parallel computation capability has made GPGPUs a promising platform for convolutional neural networks (CNNs). In this paper, we present HppCnn, a CNN library achieves both the high performance and portability on GPGPUs. In HppCnn, we propose a novel three-step approach to implement convolutional kernels using Nvidia cuBLAS efficiently. To overcome limitations of our three-step approach, we improve cuBLAS by enabling nested parallelism, and implement a low-cost auto-tuning module to leveraging existing libraries in the runtime. The experiments show HppCnn achieves significant speedups over both other cuBLAS-based and hand-optimized solutions. The results also show our solution delivers near-optimal performance on GPUs with the portability.

Leveraging large data sets, deep Convolutional Neural Networks (CNNs) achieve state-of-the-art recognition accuracy. Due to the substantial compute and memory operations, however, they require significant execution time. The massive parallel computing capability of GPUs make them as one of the ideal platforms to accelerate CNNs and a number of GPU-based CNN libraries have been developed. While existing works mainly focus on the computational efficiency of CNNs, the memory efficiency of CNNs have been largely overlooked. Yet CNNs have intricate data structures and their memory behavior can have significant impact on the performance. In this work, we study the memory efficiency of various CNN layers and reveal the performance implication from both data layouts and memory access patterns. Experiments show the universal effect of our proposed optimizations on both single layers and various networks, with up to 27.9× for a single layer and up to 5.6× on the whole networks.

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.

Intel Xeon Phi coprocessors provide excellent performance acceleration for highly parallel applications and have been deployed in several top-ranking supercomputers. One popular approach of programming the Xeon Phi is the offload model, where parallel code is executed on the Xeon Phi, while the host system executes the sequential code. However, Xeon Phi's Many Integrated Core Platform Software Stack (MPSS) lacks fault-tolerance support for offload applications. This paper introduces Snapify, a set of extensions to MPSS that provides three novel features for Xeon Phi offload applications: checkpoint and restart, process swapping, and process migration. The core technique of Snapify is to take consistent process snapshots of the communicating offload processes and their host processes. To reduce the PCI latency of storing and retrieving process snapshots, Snapify uses a novel data transfer mechanism based on remote direct memory access (RDMA). Snapify can be used transparently by single-node and MPI applications, or be triggered directly by job schedulers through Snapify's API. Experimental results on OpenMP and MPI offload applications show that Snapify adds a runtime overhead of at most 5%, and this overhead is low enough for most use cases in practice.

Many applications use graphs to represent and analyze data, but the effective deployment of graph algorithms on many-core processors is still a challenge. Many-core devices offer higher peak performance than multi-core devices; however, many-core programming is still a specialized skill. While compilation and runtime frameworks for parallelizing graph applications on multi-core CPUs exist, there is still a need for comparable frameworks for many-core devices. We propose GRapid: a compilation and runtime framework that generates efficient parallel implementations of generic graph applications for multi-core CPUs, NVIDIA GPUs and Intel Xeon Phi. Applications are expressed using a platform-agnostic programming API. Our source-to-source compiler performs platform-specific code transformations and optimizations, handles data transfers between the host and the coprocessor, and generates several functionally-equivalent code variants for the target platform. Our runtime library provides an efficient dynamic memory management scheme for applications where the graph topology is modified during processing. We used the proposed framework to rapidly generate efficient implementations of four graph applications on different target processors. Such rapid prototyping and re-targeting capability has obvious programmability advantages, but it can also be used to quickly identify target processors that better match the application's computational needs.

Orchestrating data transfers between CPUs and a coprocessor manually is cumbersome, particularly for multi-dimensional arrays and other data structures with multi-level pointers, which are common in scientific computations. This work describes a system that includes both compile-time and runtime solutions for this problem, with the overarching goal of improving programmer productivity while maintaining performance.

We propose a cluster scheduling technique for compute clusters with Xeon Phi coprocessors. Even though the Xeon Phi runs Linux which allows multiprocessing, cluster schedulers generally do not allow jobs to share coprocessors because sharing can cause oversubscription of coprocessor memory and thread resources. It has been shown that memory or thread oversubscription on a many core like the Phi results in job crashes or drastic performance loss. We first show that such an exclusive device allocation policy causes severe coprocessor underutilization: for typical workloads, on average only 38% of the Xeon Phi cores are busy across the cluster. Then, to improve coprocessor utilization, we propose a scheduling technique that enables safe coprocessor sharing without resource oversubscription. Jobs specify their maximum memory and thread requirements, and our scheduler packs as many jobs as possible on each coprocessor in the cluster, subject to resource limits. We solve this problem using a greedy approach at the cluster level combined with a knapsack-based algorithm for each node. Every coprocessor is modeled as a knapsack and jobs are packed into each knapsack with the goal of maximizing job concurrency, i.e., as many jobs as possible executing on each coprocessor. Given a set of jobs, we show that this strategy of packing for high concurrency is a good proxy for (i) reducing make span, without the need for users to specify job execution times and (ii) reducing coprocessor footprint, or the number of coprocessors required to finish the jobs without increasing make span. We implement the entire system as a seamless add on to Condor, a popular distributed job scheduler, and show make span and footprint reductions of more than 50% across a wide range of workloads.

Applications executing on multicore processors can now easily offload computations to many core processors, such as Intel Xeon Phi coprocessors. However, it requires high levels of expertise and effort to tune such offloaded applications to realize high-performance execution. Previous efforts have focused on optimizing the execution of offloaded computations on many core processors. However, we observe that the data transfer overhead between multicore and many core processors, and the limited device memories of many core processors often constrain the performance gains that are possible by offloading computations. In this paper, we present three source-to-source compiler optimizations that can significantly improve the performance of applications that offload computations to many core processors. The first optimization automatically transforms offloaded codes to enable data streaming, which overlaps data transfer between multicore and many core processors with computations on these processors to hide data transfer overhead. This optimization is also designed to minimize the memory usage on many core processors, while achieving the optimal performance. The second compiler optimization re-orders computations to regularize irregular memory accesses. It enables data streaming and factorization on many core processors, even when the memory access patterns in the original source codes are irregular. Finally, our new shared memory mechanism provides efficient support for transferring large pointer-based data structures between hosts and many core processors. Our evaluation shows that the proposed compiler optimizations benefit 9 out of 12 benchmarks. Compared with simply offloading the original parallel implementations of these benchmarks, we can achieve 1.16x-52.21x speedups.

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.

Scalable distributed data-stores are increasingly used for storing large datasets in diverse applications. The need for transactional support in these applications has motivated several recent efforts. A common theme underlying these efforts is the creation of disjoint groups of objects (entity-groups) on which efficient local transactional support is provided using multi-version concurrency control. A lock-based protocol is used to support distributed transactions across entity-groups. A significant drawback of this scheme is that the latency of distributed transactions increases with the number of entity-groups it operates on. This is due to the commit overhead of local transactions, and network overhead due to distributed locks. We address this problem using lock-localization -- locks for distributed objects are dynamically migrated and placed in distinct entity-groups in the same datastore. This reduces the overhead of multiple local transactions while acquiring locks. Application-oriented clustering of locks in these new entity-groups leads to a decrease in network overhead. Separating locks from data in this manner, however, affects the latency of local transactions. To account for this, we propose protocols and policies for selective, adaptive, and dynamic migration of locks. Using TPC-C benchmark, we provide detailed evaluation of the system.

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.

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.

Work division between the processor and accelerator is a common theme in modern heterogenous computing. Recent efforts (such as LEO and OpenAcc) provide directives that allow the developer to mark code regions in the original application from which offloadable tasks can be generated by the compiler. Auto-tuners and runtime schedulers work with the options (i.e., offloadable tasks) generated at compile time, which is limited by the directives specified by the developer. There is no provision for offload restructuring.

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.

Heterogeneous architectures comprising a multicore CPU and many-core GPU(s) are increasingly being used within cluster and cloud environments. In this paper, we study the problem of optimizing the overall throughput of a set of applications deployed on a cluster of such heterogeneous nodes. We consider two different scheduling formulations. In the first formulation, we consider jobs that can be executed on either the GPU or the CPU of a single node. In the second formulation, we consider jobs that can be executed on the CPU, GPU, or both, of any number of nodes in the system. We have developed scheduling schemes addressing both of the problems. In our evaluation, we first show that the schemes proposed for first formulation outperform a blind round-robin scheduler and approximate the performances of an ideal scheduler that involves an impractical exhaustive exploration of all possible schedules. Next, we show that the scheme proposed for the second formulation outperforms the best of existing schemes for heterogeneous clusters, TORQUE and MCT, by up to 42%.

MapReduce has emerged as one of the most popular programming models for data parallel enterprise applications. Despite advances in runtime, the opportunities for optimizing MapReduce applications remain largely unexplored. In this paper, we present a framework for performing holistic compiler optimizations on legacy MapReduce applications. We have identified and implemented two optimizations and evaluated them with a set of Hadoop applications on a cluster of Xeon servers. Our experiments show that performance gains of more than 3X can be achieved without user involvement.

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.

Graphics Processing Units (GPUs) are increasingly becoming part of HPC clusters. Nevertheless, cloud computing services and resource management frameworks targeting heterogeneous clusters including GPUs are still in their infancy. Further, GPU software stacks (e.g., CUDA driver and runtime) currently provide very limited support to concurrency.

GPU-based clusters are increasingly being deployed in HPC environments to accelerate a variety of scientific applications. Despite their growing popularity, the GPU devices themselves are under-utilized even for many computationally-intensive jobs. This stems from the fact that the typical GPU usage model is one in which a host processor periodically offloads computationally intensive portions of an application to the coprocessor. Since some portions of code cannot be offloaded to the GPU (for example, code performing network communication in MPI applications), this usage model results in periods of time when the GPU is idle. GPUs could be time-shared across jobs to "fill" these idle periods, but unlike CPU resources such as the cache, the effects of sharing the GPU are not well understood. Specifically, two jobs that time-share a single GPU will experience resource contention and interfere with each other. The resulting slow-down could lead to missed job deadlines. Current cluster managers do not support GPU-sharing, but instead dedicate GPUs to a job for the job's lifetime.

Intel MIC (Many Integrated Core) is the first x86-based coprocessor architecture aimed at accelerating multi-core HPC applications. In the most common usage model, parallel code sections are offloaded to the MIC coprocessor using LEO (Language Extensions for Offload). The developer is responsible for identifying and specifying offloadable code regions, managing data transfers between the CPU and MIC and optimizing the application for performance, which requires some amount of effort and experimentation. In this paper, we present Apricot, an optimizing compiler and productivity tool for x86-compatible many-core coprocessors (such as Intel MIC) that minimizes developer effort by (i) automatically inserting LEO clauses for parallelizable code regions, (ii) selectively offloading some of the code regions to the coprocessor at runtime based on a cost model that we have developed, (iii) applying a set ofoptimizations for minimizing the data communication overhead and improving overall performance. Apricot is intended to assist programmers in porting existing multi-core applications and writing new ones to take advantage of the many-core coprocessor, while maximizing overall performance. Experiments with SpecOMP and NAS Parallel benchmarks show that Apricot can successfully transform OpenMP applications to run on the MIC coprocessor with good performance gains.

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.

Heterogeneous computing nodes are becoming commonplace today, and recent trends strongly indicate that clusters, supercomputers, and cloud environments will increasingly host more heterogeneous resources, with some being massively parallel (e.g., GPU). With such heterogeneous environments becoming common, it is important to revisit scheduling problems for clusters and cloud environments. In this paper, we formulate and address the problem of value-driven scheduling of independent jobs on heterogeneous clusters, which captures both the urgency and relative priority of jobs. Our overall scheduling goal is to maximize the aggregate value or yield of all jobs. Exploiting the portability available from the underlying programming model, we propose four novel scheduling schemes that can automatically and dynamically map jobs onto heterogeneous resources. Additionally, to improve the utilization of massively parallel resources, we also propose heuristics to automatically decide when and which jobs can share a single resource.

Applications that use learning and classification algorithms operate on large amounts of unstructured data, and have stringent performance constraints. For such applications, the performance of general purpose processors scales poorly with data size because of their limited support for fine-grained parallelism and absence of software-managed caches. The large intermediate data in these applications also limits achievable performance on many-core processors such as GPUs. To accelerate such learning applications, we present a programmable accelerator that can execute multiple learning and classification algorithms. To architect such an accelerator, we profile five representative workloads, and find that their computationally intensive portions can be formulated as matrix or vector operations generating large amounts of intermediate data, which are then reduced by a secondary operation such as array ranking, finding max/min and aggregation. Our proposed accelerator, called MAPLE, has hundreds of simple processing elements (PEs) laid out in a two-dimensional grid, with two key features. First, it uses dynamic in-memory processing where on-chip memory blocks perform the secondary reduction operations. Second, MAPLE uses banked off-chip memory, and organizes its PEs into independent groups each with its own off-chip memory bank. These two features allow MAPLE to scale its performance with data size. We also present an Atom based energy-efficient heterogeneous system with MAPLE as the accelerator that satisfies the application’s performance requirements at a lower system power. This article describes the MAPLE architecture, explores its design space with a simulator, illustrates how to automatically map application kernels to the hardware, and presents its performance improvement and energy benefits over classic server-based implementations. We implement a 512-PE FPGA prototype of MAPLE and find that it is 1.5-10x faster than a 2.5 GHz quad-core Xeon processor despite running at a modest 125 MHz clock rate. With MAPLE connected to a 1.6GHz dual-core Atom, we show an energy improvement of 38-84% over the Xeon server coupled to a 1.3 GHz 240 core Tesla GPU.

Coprocessors such as GPUs are increasingly being deployed in clusters to process scientific and compute-intensive jobs. In this work, we study if GPU-based heterogeneous clusters can benefit client-server applications. Specifically, we consider the practical situation where multiple client-server applications share a heterogeneous cluster (multi-tenancy), and experience unpredictable variations in incoming client request rates, including steep load spikes. Even for "compute-intensive" client-server applications, it is unclear if a GPU-based cluster can seamlessly deliver acceptable response times in the presence of multi-tenancy and load spikes. We argue that a cluster-level scheduler that is aware of application load, request deadlines and the heterogeneity is necessary in this situation. We propose a novel scheduler called Symphony that enables efficient, dynamic sharing of a GPU-based heterogeneous cluster across multiple concurrently-executing client-server applications, each with arbitrary load spikes. Symphony performs three key tasks: it (i) monitors the load on each application, (ii) collects past performance data and dynamically builds simple performance models of available processing resources and (iii) computes a priority for pending requests based on the above parameters and the requests' slack. Based on this, it reorders client requests across different applications to achieve acceptable response times. We also define how client-server applications should interact with a scheduler such as Symphony, and develop an API to this end. We deploy Symphony as user-space middleware on a high-end heterogeneous cluster with dual quad-core Xeon CPUs and dual NVIDIA Fermi GPUs. An evaluation using representative applications shows that in the presence of load spikes (i) Symphony incurs 2-20× fewer requests that do not meet response time constraints compared with other schedulers, and (ii) in order to achieve the same performance as Symphony, other schedulers need 2× more cluster nodes.

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.

Driven by the emergence of GPUs as a major player in high performance computing and the rapidly growing popularity of cloud environments, GPU instances are now being offered by cloud providers. The use of GPUs in a cloud environment, however, is still at initial stages, and the challenge of making GPU a true shared resource in the cloud has not yet been addressed.This paper presents a framework to enable applications executing within virtual machines to transparently share one or more GPUs. Our contributions are twofold: we extend an open source GPU virtualization software to include efficient GPU sharing, and we propose solutions to the conceptual problem of GPU kernel consolidation. In particular, we introduce a method for computing the affinity score between two or more kernels, which provides an indication of potential performance improvements upon kernel consolidation. In addition, we explore molding as a means to achieve efficient GPU sharing also in the case of kernels with high or conflicting resource requirements. We use these concepts to develop an algorithm to efficiently map a set of kernels on a pair of GPUs. We extensively evaluate our framework using eight popular GPU kernels and two Fermi GPUs. We find that even when contention is high our consolidation algorithm is effective in improving the throughput, and that the runtime overhead of our framework is low.

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.

For learning and classification workloads that operate on large amounts of unstructured data with stringent performance constraints, general purpose processor performance scales poorly with data size. In this paper, we present a programmable accelerator for this workload domain. To architect the accelerator, we profile five representative workloads, and find that their computationally intensive portions can be formulated as matrix or vector operations generating large amounts of intermediate data, which are then reduced by a secondary operation such as array ranking, finding max/min and aggregation. The proposed accelerator, called MAPLE, has hundreds of simple processing elements (PEs) laid out in a two-dimensional grid, with two key features. First, it uses in-memory processing where on-chip memory blocks perform the secondary reduction operations. By doing so, the intermediate data are dynamically processed and never stored or sent off-chip. Second, MAPLE uses banked off-chip memory, and organizes its PEs into independent groups each with its own off-chip memory bank. These two features together allow MAPLE to scale its performance with data size. This paper describes the MAPLE architecture, explores its design space with a simulator, and illustrates how to automatically map application kernels to the hardware. We also implement a 512-PE FPGA prototype of MAPLE and find that it is 1.5-10x faster than a 2.5 GHz quad-core Xeon processor despite running at a modest 125 MHz.

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.

Convolutional neural networks (CNN) applications range from recognition and reasoning (such as handwriting recognition, facial expression recognition and video surveillance) to intelligent text applications such as semantic text analysis and natural language processing applications. Two key observations drive the design of a new architecture for CNN. First, CNN workloads exhibit a widely varying mix of three types of parallelism: parallelism within a convolution operation, intra-output parallelism where multiple input sources (features) are combined to create a single output, and inter-output parallelism where multiple, independent outputs (features) are computed simultaneously. Workloads differ significantly across different CNN applications, and across different layers of a CNN. Second, the number of processing elements in an architecture continues to scale (as per Moore's law) much faster than off-chip memory bandwidth (or pin-count) of chips. Based on these two observations, we show that for a given number of processing elements and off-chip memory bandwidth, a new CNN hardware architecture that dynamically configures the hardware on-the-fly to match the specific mix of parallelism in a given workload gives the best throughput performance. Our CNN compiler automatically translates high abstraction network specification into a parallel microprogram (a sequence of low-level VLIW instructions) that is mapped, scheduled and executed by the coprocessor. Compared to a 2.3 GHz quad-core, dual socket Intel Xeon, 1.35 GHz C870 GPU, and a 200 MHz FPGA implementation, our 120 MHz dynamically configurable architecture is 4x to 8x faster. This is the first CNN architecture to achieve real-time video stream processing (25 to 30 frames per second) on a wide range of object detection and recognition tasks.

In this paper, we describe a runtime to automatically enhance the performance of applications running on heterogeneous platforms consisting of a multi-core (CPU) and a throughput-oriented many-core (GPU). The CPU and GPU are connected by a non-coherent interconnect such as PCI-E, and as such do not have shared memory. Heterogeneous platforms available today such as [9] are of this type. Our goal is to enable the programmer to seamlessly use such a system without rewriting the application and with minimal knowledge of the underlying architectural details. Assuming that applications perform function calls to computational kernels with available CPU and GPU implementations, our runtime achieves this goal by automatically scheduling the kernels and managing data placement. In particular, it intercepts function calls to well-known computational kernels and schedules them on CPU or GPU based on their argument size and location. To improve performance, it defers all data transfers between the CPU and the GPU until necessary. By managing data placement transparently to the programmer, it provides a unified memory view despite the underlying separate memory sub-systems.

Memory is a scarce resource during embedded system design. Increasing memory often increases packaging costs, cooling costs, size, and power consumption. This article presents CRAMES, a novel and efficient software-based RAM compression technique for embedded systems. The goal of CRAMES is to dramatically increase effective memory capacity without hardware or application design changes, while maintaining high performance and low energy consumption. To achieve this goal, CRAMES takes advantage of an operating system's virtual memory infrastructure by storing swapped-out pages in compressed format. It dynamically adjusts the size of the compressed RAM area, protecting applications capable of running without it from performance or energy consumption penalties. In addition to compressing working data sets, CRAMES also enables efficient in-RAM filesystem compression, thereby further increasing RAM capacity. CRAMES was implemented as a loadable module for the Linux kernel and evaluated on a battery-powered embedded system. Experimental results indicate that CRAMES is capable of doubling the amount of RAM available to applications running on the original system hardware. Execution time and energy consumption for a broad range of examples are rarely affected. When physical RAM is reduced to 62.5% of its original quantity, CRAMES enables the target embedded system to support the same applications with reasonable performance and energy consumption penalties (on average 9.5% and 10.5%), while without CRAMES those applications either may not execute or suffer from extreme performance degradation or instability. In addition to presenting a novel framework for dynamic data memory compression and in-RAM filesystem compression in embedded systems, this work identifies the software-based compression algorithms that are most appropriate for use in low-power embedded systems.

Online memory compression is a technology that increases the amount of memory available to applications by dynamically compressing and decompressing their working datasets on demand. It has proven extremely useful in embedded systems with tight physical RAM constraints. The technology can be used to increase functionality, reduce size, and reduce cost, without modifying applications or hardware. This article presents a new software-based online memory compression algorithm for embedded systems. In comparison with the best algorithms used in online memory compression, our new algorithm has a competitive compression ratio but is twice as fast. In addition, we describe several practical problems encountered in developing an online memory compression infrastructure and present solutions. We present a method of adaptively managing the uncompressed and compressed memory regions during application execution. This memory management scheme adapts to the predicted memory requirements of applications. It permits efficient compression for a wide range of applications. We have evaluated our techniques on a portable embedded device and have found that the memory available to applications can be increased by 2.5× with negligible performance and power consumption penalties, and with no changes to hardware or applications. Our techniques allow existing applications to execute with less physical memory. They also allow applications with larger working datasets to execute on unchanged embedded system hardware, thereby increasing functionality.

We present a massively parallel coprocessor for accelerating Convolutional Neural Networks (CNNs), a class of important machine learning algorithms. The coprocessor functional units, consisting of parallel 2D convolution primitives and programmable units performing sub-sampling and non-linear functions specific to CNNs, implement a ldquometa-operatorrdquo to which a CNN may be compiled to. The coprocessor is serviced by distributed off-chip memory banks with large data bandwidth. As a key feature, we use low precision data and further increase the effective memory bandwidth by packing multiple words in every memory operation, and leverage the algorithmpsilas simple data access patterns to use off-chip memory as a scratchpad for intermediate data, critical for CNNs. A CNN is mapped to the coprocessor hardware primitives with instructions to transfer data between the memory and coprocessor. We have implemented a prototype of the CNN coprocessor on an off-the-shelf PCI FPGA card with a single Xilinx Virtex5 LX330T FPGA and 4 DDR2 memory banks totaling 1 GB. The coprocessor prototype can process at the rate of 3.4 billion multiply accumulates per second (GMACs) for CNN forward propagation, a speed that is 31x faster than a software implementation on a 2.2 GHz AMD Opteron processor. For a complete face recognition application with the CNN on the coprocessor and the rest of the image processing tasks on the host, the prototype is 6-10times faster, depending on the host-coprocessor bandwidth.

We present a massively parallel FPGA-based coprocessor for Support Vector Machines (SVMs), a machine learning algorithm whose applications include recognition tasks such as learning scenes, situations and concepts, and reasoning tasks such as analyzing the recognized scenes and semantics. The coprocessor architecture, targeted at both SVM training and classification, is based on clusters of vector processing elements (VPEs) operating in single-instruction multiple data (SIMD) mode to take advantage of large amounts of data parallelism in the application. We use the FPGA's DSP elements as parallel multiply-accumulators (MACs), a core computation in SVMs. A key feature of the architecture is that it is customized to low precision arithmetic which permits one DSP unit to perform two or more MACs in parallel. Low precision also reduces the required number of parallel off-chip memory accesses by packing multiple data words on the FPGA-memory bus. We have built a prototype using an off-the-shelf PCI-based FPGA card with a Xilinx Virtex 5 FPGA and 1 GB DDR2 memory. For SVM training, we observe application-level end-to-end computation speeds of over 9 billion multiply-accumulates per second (GMACs). For SVM classification, using data packing, the application speed increases to 14 GMACs. The FPGA-based system is about 20times faster than a dual Opteron 2.2 GHz processor CPU, and dissipates around 10 W of power.

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.

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.

Designing reliable software for sensor networks is challenging because application developers have little visibility into, and understanding of the post-deployment behavior of code executing on resource constrained nodes in remote and ill-reproducible environments. To address this problem, this paper presents HERMES, a lightweight framework and prototype tool that provides fine-grained visibility and control of a sensor node's software at run-time. HERMES's architecture is based on the notion of interposition, which enables it to provide these properties in a minimally intrusive manner, without requiring any modification to software applications being observed and controlled. HERMES provides a general, extensible, and easy-to-use framework for specifying which software components to observe and control as well as when and how this observation and control is done. We have implemented and tested a fully functional prototype of HERMES for the SOS sensor operating system. Our performance evaluation, using real sensor nodes as well as cycle-accurate simulation, shows that HERMES successfully achieves its objective of providing fine-grained and dynamic visibility and control without incurring significant resource overheads. We demonstrate the utility and flexibility of HERMES by using our prototype to design, implement, and evaluate three case-studies: debugging and testing deployed sensor network applications, performing transparent software updates in sensor nodes, and implementing network traffic shaping and resource policing.

We present a new, massively parallel architecture for accelerating machine learning algorithms, based on arrays of variable-resolution arithmetic vector processing elements (VPE). Groups of VPEs operate in SIMD (single instruction multiple data) mode, and each group is connected to an independent memory bank. In this way memory bandwidth scales with the number of VPE, and the main data flows are local, keeping power dissipation low. With 256 VPEs, implemented on two FPGA (field programmable gate array) chips, we obtain a sustained speed of 19 GMACS (billion multiply-accumulate per sec.) for SVM training, and 86 GMACS for SVM classification. This performance is more than an order of magnitude higher than that of any FPGA implementation reported so far. The speed on one FPGA is similar to the fastest speeds published on a Graphics Processor for the MNIST problem, despite a clock rate of the FPGA that is six times lower. High performance at low clock rates makes this massively parallel architecture particularly attractive for embedded applications, where low power dissipation is critical. Tests with Convolutional Neural Networks and other learning algorithms are under way now.

This paper presents a test data compression scheme that can be used to further improve compressions achieved by LFSR reseeding. The proposed compression technique can be implemented with very low hardware overhead. Unlike most commercial test data compression tools, the proposed method requires no special ATPG that is customized for the proposed scheme and can be used to compress test patterns generated by any ATPG tool. The test data to be stored in the ATE memory are much smaller than that for previously published schemes and the number of test patterns that need to be generated is smaller than other weighted random pattern testing schemes. Experimental results on a large industry design show that over 1600X compression is achievable by the proposed scheme with the number of patterns comparable to that of highly compacted deterministic patterns.

This paper presents a new blocking logic to block unknowns for temporal compactors. The proposed blocking logic can reduce data volume required to control the blocking logic and also increase the number of scan cells that are observed by the temporal compactors. Control patterns, which describe values required at the control signals of the blocking logic, are compressed by LFSR reseeding. In this paper, the blocking logic gates for some groups of scan chains that do not capture unknowns are bypassed. Since all the scan cells in these scan chain groups are observed without specifying the corresponding bits in control patterns, fewer specified bits are required and more scan cells are observed. The seed size is further reduced by reducing numbers of specified bits in the densely specified control patterns. The proposed method can always achieve the same fault coverage that can be achieved by direct observation of scan chains. Experiments with large industrial designs clearly demonstrate that the proposed method is scalable to large circuits. Hardware overhead for the proposed blocking logic is very low

This paper presents a hybrid compaction scheme for test responses containing unknown values, which consists of a space compactor and an unknown-blocking Multiple Input Signature Registers (MISR). The proposed scheme guarantees no coverage loss for the modeled faults. The proposed hybrid scheme can also be tuned to observe any user- specified percentage of responses for controlling the coverage loss for un-modeled faults. The experimental results demonstrate that, in comparison with a space compactor or an unknown-blocking MISR alone, the hybrid compaction scheme achieves a lower coverage loss without demanding more test-data volume. In addition, we propose a quantitative approach to estimate the required percentage of observable responses for the proposed scheme, directly based on a test-quality metric of un-modeled faults.

This paper presents a test data compression scheme that combines weighted random pattern testing and LFSR reseeding. Test patterns generated by the proposed decompressor can achieve high n-detection fault coverage. The proposed technique computes weight sets from a set of test cubes that are generated by a traditional 1-detection ATPG tool. The computed weight sets are modified to achieve high ndetection fault coverage. The proposed decompressor can be implemented with low area overhead. Since the proposed technique requires no special ATPG that is customized for the proposed scheme, it can compress test patterns generated by any ATPG tool and generate test patterns from the compressed test data that achieve high n-detection fault coverage. Experimental results show that test patterns generated by the proposed decompressor can achieve very high 5- detection stuck-at fault coverage and high compression for large benchmark circuits

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.

Since structured application specific integrated chip (ASIC) products require very short turn around time, long automatic test pattern generation (ATPG) run time is undesirable. Large structured ASICs often require a large number of test patterns to achieve the desired fault coverage. This paper presents the first test point insertion technique for structured ASICs that can reduce test set sizes and ATPG run time. Only unused flip-flops in the structured ASIC design are used to implement test points, so the proposed technique does not incur any hardware overhead. Since test points are inserted during a post-layout step, considering both timing and layout information, hence test points can be inserted without changing the existing layout or routing. Novel gain functions are defined that specifically quantify the reduction in test volume and test time to select the best signal lines for inserting test points. The gain function described in this paper is also applicable to regular cell based ASICs. The proposed test point insertion technique can be used in conjunction with any compression technique (Jas et al., 2003) to further reduce the test volume. Experimental results clearly demonstrate the effectiveness and scalability of the proposed technique. Using less than 1% of extra flip-flops and very little run time for test point insertion, test generation time was reduced by up 42.9% and test data volume by up to 25.9% while also achieving a near 100% fault efficiency for very large industrial (400K-5M signal lines) designs

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.

For a space compactor, degradation of fault detection capability caused by the masking effects from unknown values is much more serious than that caused by error masking (i.e. aliasing). In this paper, we first propose a mathematical framework to estimate the percentage of observable responses under unknown-induced masking for a space compactor. We further develop a prediction scheme which can correlate the percentage of observable responses with the modeled-fault coverage and with a n-detection metric for a given test set. As a result, the quality of a space compactor can be measured directly based on its test quality, instead of based on indirect metrics such as the number of tolerated unknowns or the aliasing probability. With the prediction scheme above, we propose a construction flow for space compactors to achieve the desired level of test quality while maximizing the compaction ratio.

The presence of unknown values in simulation is the great est barrier to effective test response compaction. For space compactors, some responses may not be observable due to the masking effect caused by unknown values. This paper reports on experiments conducted to evaluate the impact on the test quality of various percentages of observable responses for both modeled and un-modeledfaults.

This paper presents an efficient method to block unknown values from entering temporal compactors. The control signals for the blocking logic are generated by an LFSR. The proposed technique minimizes the size of the LFSR by propagating only one fault effect for each fault and balancing the number of specified bits in each control pattern. The linear solver to find seeds of the LFSR intelligently chooses a solution such that the impact on test quality is minimal. Experimental results show that sizes of control data for the proposed method are smaller than prior work and run time of the proposed method is several orders of magnitude smaller than that of prior work. Hardware overhead is very low.

Longest prefix matching (LPM) is a fundamental part of various network processing tasks. Previously proposed approaches for LPM result in prohibitive cost and power dissipation (TCAMs) or in large memory requirements and long lookup latencies (tries), when considering future line-rates, table sizes and key lengths (e.g., IPv6). Hash-based approaches appear to be an excellent candidate for LPM with the possibility of low power, compact storage, and O(1) latencies. However, there are two key problems that hinder their practical deployment as LPM solutions. First, naive hash tables incur collisions and resolve them using chaining, adversely affecting worst-case lookup-rate guarantees that routers must provide. Second, hash functions cannot directly operate on wildcard bits, a requirement for LPM, and current solutions require either considerably complex hardware or large storage space. In this paper we propose a novel architecture which successfully addresses for the first time, both key problems in hash based LPM - making the following contributions: (1) We architect an LPM solution based upon a recently-proposed, collision-free hashing scheme called Bloomier filter, by eliminating its false positives in a storage efficient way. (2) We propose a novel scheme called prefix collapsing, which provides support for wildcard bits with small additional storage and reduced hardware complexity. (3) We exploit prefix collapsing and key characteristics found in real update traces to support fast and incremental updates, a feature generally not available in collision-free hashing schemes

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

In this paper, an automatic test pattern generator (ATPG)-based scan-path test point insertion technique, which can achieve high delay fault coverage for scan designs, is proposed. In the proposed technique, the shift dependency between adjacent scan flip-flops, which causes some delay faults to be untestable in the standard scan environment, is broken by inserting test points, which can be combinational gates as well as flip-flops. Instead of topology-based approaches used in prior publications, the proposed technique uses a special ATPG to identify pairs of adjacent scan flip-flops between which test points are inserted to improve fault coverage. Since the proposed technique inserts test points only where they are necessary, it can drastically reduce hardware overhead compared to circuit topology-based techniques. One hundred percent transition delay coverage was attained for all ISCAS 89 benchmark circuits except one. This is achieved with very small numbers of test points. On average, about 40% reduction in scan chain length against a prior approach was achieved by the proposed method for benchmark circuits with default scan chain order.

With the help of HW/SW codesign, system-on-chip (SoC) can effectively reduce cost, improve reliability, and produce versatile products. The growing complexity of SoC designs makes on-chip communication subsystem design as important as computation subsystem design. While a number of codesign methodologies have been proposed for on-chip computation subsystems, many works are needed for on-chip communication subsystems. This paper proposes application-specific networks-on-chip (ASNoC) and its design methodology. ASNoC is used for two high-performance SoC applications. The methodology (1) can automatically generate optimized ASNoC for different applications, (2) can generate a corresponding distributed shared memory along with an ASNoC, (3) can use both recorded and statistical communication traces for cycle-accurate performance analysis, (4) is based on standardized network component library and floorplan to estimate power and area, (5) adapts an industrial-grade network modeling and simulation environment, OPNET, which makes the methodology ready to use, and (6) can be easily integrated into current HW/SW codesign flow. Using the methodology, ASNoC is generated for a H.264 HDTV decoder SoC and Smart Camera SoC. ASNoC and 2D mesh networks-on-chip are compared in performance, power, and area in detail. The comparison results show that ASNoC provide substantial improvements in power, performance, and cost compared to 2D mesh networks-on-chip. In the H.264 HDTV decoder SoC, ASNoC uses 39% less power, 59% less silicon area, 74% less metal area, 63% less switch capacity, and 69% less interconnection capacity to achieve 2X performance compared to 2D mesh networks-on-chip.

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.

The presence of unknown values in the simulation result is a key barrier to effective output response compaction in practice. This paper proposes a simple circuit module, called a response shaper, to reshape the scan-out responses before feeding them to a space compactor. Along with the proposed reshaping algorithm, response shapers can help the space compactor to reduce the number of undetectable modeled and unmodeled faults in the presence of unknown values. Moreover, the proposed compaction scheme is ATPG-independent and its hardware requirement is pattern-independent. In our experiments, we use a simple XOR compactor as the space compactor to evaluate the effectiveness of the response shaper. The results show that the number of undetectable faults and unobservable scan-out responses can be significantly reduced in comparison with the results of a convolutional compactor. The number of the extra scan-in bits required for the control signals of the response shapers is only a small fraction of the total test data volume. Also, its hardware overhead is acceptable and the runtime of the reshaping algorithm is scalable for large industrial designs.

This paper proposes a response compactor, named ChiYun compactor, to compact scan-out responses in the presence of unknown values. By adding storage elements into an Xor network, a ChiYun compactor can offer multiple chances for a scan-out response to be observed at ATE channels in one to several scan-shift cycles. We also develop a mathematical analysis to predict the percentage of scan-out responses masked by the unknown values for the ChiYun compactor. With this analysis, we can derive the optimal configuration of a ChiYun compactor for minimizing the masking of scan-out responses. We further propose a selection scheme for the ChiYun compactor to selectively observe partial Xor results for improving the fault coverage. The experimental results demonstrate the effectiveness of the proposed mathematical analysis and the selection scheme. We also demonstrate that the unknown tolerance of a ChiYun compactor is higher than that of a state-of-the-art response compactor proposed in (Wang, 2003).

This paper studied an H. 264 HDTV decoder on two multiprocessor system-on-chip architectures. Two types of networks-on-chip, the RAW network and the application specific networks-on-chip, were used. Regular-topology networks-on-chip (mesh, torus, and fat tree) have been proposed. However, we showed in this paper that the application-specific networks-on-chip provided substantial improvements in power, performance, and cost compared to regular-topology networks-on-chip. We measured the power, performance, area, total switch and link capacity, and switch and link utilization based on floorplans and circuit designs. Measurement results showed th at the application-specific networks-on-chip was both faster in absolute terms and more efficient. The application-specific networks-on-chip used 39% less power, 59% less silicon area, 74% less metal area, 63% less switch capacity, and 69% less link capacity to achieve 2X performance compared to the RAW network.

This paper presents an input test data compression scheme that combines the advantages of weighted pseudorandom testing techniques and LFSR reseeding. The scheme requires low area overhead and the compression achieved is not limited by the LFSR reseeding bounds. The test data storage requirements of both the static and dynamic versions of the proposed scheme are lower than previously published results. The total numbers of test patterns that need to be applied are much lower than that for any weighted pseudorandom testing or hybrid BIST scheme. Further, the method provides an easy way to trade off between test application time and test data compression. The static version of the scheme can be easily implemented without any modification to the current test generation flow while the dynamic version can be used if the ATPG can be modified. Experimental results on a large industry design show that over 100/spl times/ compression is achievable by the proposed scheme.

A novel scan-based delay test approach, referred as the hybrid delay scan, is proposed in this paper. The proposed scan-based delay testing method combines advantages of the skewed-load and broad-side approaches. Unlike the skewed-load approach whose design requirement is often too costly to meet due to the fast switching scan enable signal, the hybrid delay scan does not require a strong buffer or buffer tree to drive the fast switching scan enable signal. Hardware overhead added to standard scan designs to implement the hybrid approach is negligible. Since the fast scan enable signal is internally generated, no external pin is required. Transition delay fault coverage achieved by the hybrid approach is equal to or higher than that achieved by the broad-side load for all ISCAS 89 benchmark circuits. On an average, about 4.5% improvement in fault coverage is obtained by the hybrid approach over the broad-side approach.

In this paper we study bus-based and switch-based on-chip networks for an embedded video application, the smart camera SoC (system on chip). We analyze network performance and overall system performance in detail. We explore system performance using crossbars with different sizes, fixed size but different numbers of ports, and different numbers of shared memories. We find that network is a performance bottleneck in our design, and the system using an optimized NoC can outperform one using a bus by 132%. Our simulations are based upon recorded real communication traces, which give more accurate system performance. Our study finds that for the Smart Camera system, a 16-bit/port 3/spl times/3 crossbar with two shared memories shows 85.7% performance improvement over the bus-based model and also has less maximum network throughput than the bus-based model. This design example illustrates a methodology to quickly and accurately estimate the performance of NoC's at architecture level.

In recent years instruction code compression/decompression technologies have emerged as an efficient way to a) reduce the memory usage of an embedded system, b) to improve performance through effectively higher bandwidths and/or to c) reduce the overall power consumption of a system processing compressed code. We have presented efficient code compression/decompression techniques and architectures in the past. For the commercialization phase, we designed a novel hardware/software code compression/decompression platform (CoCo). It consists of a software platform that prepares, optimizes, compresses and compiles instruction code and a generic, parameterizable FPGA-based hardware architecture in form of a hardware platform that allows to rapidly evaluate prototypes of diverse compression/decompression technologies. We show the flexibility of CoCo, its ability to achieve code compression ratios (parameterizable) of up to 50% with a slight system performance gain and its ability to apply compression on real-world compiled code without any limitations where others have made implicit software-restrictive assumptions.

In this paper,an automatic test pattern generator (ATPG)-based scan-path test point insertion technique,which can achieve high delay fault coverage for scan designs,is proposed. In the proposed technique,the shift dependency between adjacent scan flip-flops,which causes some delay faults to be untestable in the standard scan environment,is broken by inserting test points,which can be combinational gates as well as flip-flops. Instead of topology-based approaches used in prior publications,the proposed technique uses a special ATPG to identify pairs of adjacent scan flip-flops between which test points are inserted to improve fault coverage. Since the proposed technique inserts test points only where they are necessary,it can drastically reduce hardware overhead compared to circuit topology-based techniques. One hundred percent transition delay coverage was attained for all ISCAS 89 benchmark circuits except one. This is achieved with very small numbers of test points. On average,about 40% reduction in scan chain length against a prior approach was achieved by the proposed method for benchmark circuits with default scan chain order. Index Terms—Delay fault,scan testing,test point insertion,transition delay fault.

The speed of new VLSI designs is rapidly increasing. Assuring the performance of the circuit requires that the circuit be tested at its intended operating speed. The high cost of high speed testers makes it impossible for the testers to follow the designs in terms of speed increase. This gap between the speed of the new circuits and the speed of the testers is not likely to disappear. In this paper, we focus on at-speed strategies for testing high speed designs on slower testers. Conventional at-speed testing strategies assume that the primary inputs/outputs can be applied/observed at the circuit rated speed. This requires a high speed tester. Our assumption is that a fast clock matching the speed of the designs is available. We describe two classes of at-speed strategies that can be used on a low speed tester. The first class consists of testing schemes for which the test generation procedure is independent of the speed of the tester. These methods apply multiple input patterns in one tester cycle and the test application time for them can be long. The strategies in the second class of at-speed testing schemes integrate the tester's speed limitations with the test generation process. Due to constraints placed at the test generation process, these schemes might result in a reduced fault coverage. To increase the fault coverage and reduce the test application time, the slow-fast-slow and at-speed strategies can be combined for testing high speed designs on slower testers. We present preliminary experimental results for at-speed schemes for slow testers for transition faults.

An effective partial scan approach selects flip-flops (FPs) in the minimum feedback vertex set (MFVS) of the FF dependency graph, so that all loops, except self-loops, are broken. However, the MFVS of the circuit (the minimum number of gates whose removal makes the circuit acyclic) is a lower bound and in many cases, significantly smaller than the MFVS of the FF dependency graph. Since only FFs can be considered for scan, this paper investigates the possibility of repositioning FFs so that, in the modified circuit, every circuit MFVS gate drives at least one FF that can be scanned. We show that resynthesis and retiming can always transform any circuit into an equivalent circuit whose FF dependency graph MFVS is equal to the MFVS of the original circuit. Therefore, the MVFS of a circuit is a tight lower bound on the number of scan FFs needed. We first identify the necessary and sufficient conditions under which legal retiming can produce the desired FF repositioning. We show that circuits that do not satisfy these conditions can always be suitably modified using two new resynthesis transformations. The modified circuit can always be retimed to achieve the desired FF repositioning. Experimental results for several large sequential benchmarks show that the number of scan FFs required for the resynthesized and retimed circuit is significantly smaller than that required for the original circuit.

We investigate two strategies to guarantee temporal correctness of a combinational circuit. We first propose a new technique to identify and test primitive faults. A primitive fault is a path delay fault that has to be tested to guarantee the performance of the circuit. Primitive faults can consist of single- (SPDF's) or multiple path delay faults (MPDF's). Testing strategies for single primitive faults exist. In this paper, we focus on identifying and testing multiple primitive faults. Identification and testing of these faults is important for at least two reasons: (1) a large percentage of paths in production circuits remain untestable under the SPDF model, and (2) distributed manufacturing defects usually adversely affect more than one path and these defects can be detected only by analyzing multiple affected paths. The SPDF's contained in a multiple primitive fault have to merge at some gate(s). Our methodology can quickly (1) rule out a large number of gates as possible merging gates for primitive faults, and (2) prune the combinations of paths that can never belong to any primitive fault. Our identification procedure also finds a test for the fault. We present a complete algorithm for identifying and testing double path delay faults, Identifying and testing all primitive faults is impractical for large designs. This is because no efficient methods are known for testing primitive faults that include a large number of paths. However, to guarantee that the performance of a digital circuit is not affected by timing defects, it is necessary to test all primitive faults. Our second contribution is a new design for testability method. Our method guarantees that only primitive faults with at most two paths can exist in the circuit in the test mode. The main idea is to efficiently identify a small set of signals for inserting test points to eliminate primitive faults with more than two paths. Our test points only provide controllability. Addition of a single test point can lower the cardinality of several primitive faults. Our approach efficiently re-evaluates primitive delay fault testability of the circuit after insertion of a test point. After a few iterations only primitive faults with at most two paths can exist in the circuit in the test mode. Experimental results on several multilevel combinational benchmark circuits are included to demonstrate the usefulness of our techniques.

Given a test sequence and a list of faults detected by the sequence, vector restoration techniques extract a minimal subsequence that detects a chosen subset of faults. Vector restoration techniques are useful in static compaction of test sequences and in fault diagnosis. We propose a new vector restoration technique that is a significant improvement over the state of the art in several ways: (1) a sequence of length n can be restored with only O(nlog2n) simulations while known approaches require simulation of O(n/sup 2/) vectors; (2) a two-step restoration process is used that makes vector restoration practical for large designs; and (3) the restoration process for several faults is overlapped to provide significant acceleration in vector restoration. Our new ideas can be used to improve run-times of known static compaction and fault diagnosis methods. We integrated the proposed vector restoration technique into a static test sequence compaction system. Our experiments show that the new restoration technique, as compared to known techniques, is for (1) about 2 times faster for the ISCAS benchmark circuits, and for (2) 3 to 5 times faster on large, industrial designs. Using the new restoration technique, we successfully processed large industrial designs that could not be handled by earlier techniques in 2 CPU days.

We propose a new static test set compaction method based on a careful examination of attributes of fault coverage curves. Our method is based on two key ideas: (1) fault-list and test-set partitioning, and (2) vector re-ordering. Typically, the first few vectors of a test set detect a large number of faults. The remaining vectors usually constitute a large fraction of the test set, but these vectors ore included to detect relatively few hard faults. We show that significant compaction can be achieved by partitioning faults into hard and easy faults. This significantly reduces the computational cost for static test set compaction without affecting quality of compaction. The second technique re-orders vectors in a test yet by moving sequences that detect hard faults to the beginning of the test set. Fault simulation of the newly concatenated re-ordered test set results in the omission of several vectors so that the compact test set is smaller than the original test set. Experiments on several ISCAS 89 sequential benchmark circuits and large production circuits show that our compaction procedure yields significant test set reductions in low execution times.

We extend the subsequence removal technique to provide significantly higher static compaction for sequential circuits. We show that state relaxation techniques can be used to identify more or larger cycles in a test set. State relaxation creates more opportunities for subsequence removal and hence, results in better compaction. Relaxation of a state is possible since not all memory elements in a finite state machine have to be specified for a state transition. The proposed technique has several advantages: (1) test sets that could not be compacted by existing subsequence removal techniques can now be compacted, (2) the size of cycles in a test set can be significantly increased by state relaxation and removal of the larger sized cycles leads to better compaction, (3) only two fault simulation passes are required as compared to trial and re-trial methods that require multiple fault simulation passes, and (4) significantly higher compaction is achieved in short execution times as compared to known subsequence removal methods, Experiments on ISCAS89 sequential benchmark circuits and several synthesized circuits show that the proposed technique consistently results in significantly higher compaction in short execution times.

: We propose a new technique for static compaction of test sequences. Our method is based on two key ideas: (1) overlapped vector restoration, and (2) identification, pruning, and re-ordering of segments. Overlapped restoration provides a significant computational advantage for large circuits. Segments partition the compaction problem into sub-problems. Segments are identified, dynamically pruned and re-ordered to achieve further compaction and speed up. When compared to the fastest method proposed in [8], our method was 5 to 30 times faster on ISCAS circuits and 20 to 50 times faster on large, industrial designs. The new algorithm was able to successfully process large industrial designs that could not be handled by earlier techniques [8] in 2 CPU days. I. Introduction Reduction in test set size can be achieved using static or dynamic test set compaction algorithms. Dynamic techniques [9, 10, 14, 15, 16] perform compaction concurrently with the test generation process. These techniq...

Vector restoration based static compaction techniques report significant compaction. In this paper we propose a new technique for static compaction which gives comparable or better compaction and runs 10 to 50 times faster than the fastest method. The new technique solves the problem of compaction by dividing it into small subproblems (referred to as segments). The solutions to these segments (or subproblems) are then dynamically merged providing excellent speed up without compromising on compaction efficiency. Further speed up is achieved by compacting the individual segments using an accelerated vector-restoration based compaction technique. If a fault requires a sequence of length n to be detected, in our approach the number of vectors that need to be simulated for restoring the sequence is O(n logan), while the prevailing approaches require simulation on O(n/sup 2/) vectors. Experimental results demonstrate substantial speedups compared to the prevailing vector restoration based techniques, while giving comparable or better compaction. When compared to the fastest method, our method was 5 to 30 times faster on ISCAS circuits and 10 to 50 times faster on real-life production circuits. For example, on one of the production circuits, our method gave 27 percent compaction in 188 seconds, while an improved version of the fastest method gave 25 percent compaction in 10200 seconds. In addition, our method could successfully process large industrial designs which could not be completed by earlier techniques in 2 CPU days.

To guarantee the temporal correctness of a digital circuit a set of multiple path delay faults called primitive faults need to be tested. Primitive faults can contain one or more faulty paths. Existing techniques can identify and test primitive faults containing up to two or three paths. Identifying and testing primitive faults that consist of a larger number of paths is impractical for large designs. We propose a design for testability method that assures the temporal correctness of the circuit without the need to test all primitive faults in the circuit. In the test mode, only primitive faults that contain up to two paths can affect the circuit performance. Our methodology efficiently identifies a small set of potential locations for inserting control points to eliminate primitive faults with more than two paths. Addition of a single control point can lower the cardinality of several primitive faults. Our approach re-evaluates primitive delay fault testability of the circuit after insertion of every control point. After a few iterations only primitive faults with at most two paths can exist in the circuit in the test mode. Experimental results on several circuits are included to demonstrate our method.

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.

Production VLSI circuits typically consist of primitives like tristate buffers, bidirectional buffers, and bus configurations that assume non-Boolean values like the high-impedance state. We describe a systematic methodology for extending test generation algorithms that work on combinational circuits with only Boolean primitives to full-scan production circuits. Key features of the methodology are illustrated using the energy minimization based test generation algorithm for combinational circuits. The main features of our methodology that make the test generation algorithm practical for large production circuits are: (1) only one Boolean variable is used to represent the value on a signal and all signals assume only Boolean values during the test generation procedure; (2) the function of non-Boolean primitives is separated into Boolean and non-Boolean components with energy functions required only for the Boolean component; and (3) non-Boolean components are implicitly considered in the energy minimization procedure. In this process, no new energy functions other than the normal Boolean gate energy functions are needed. We give a method for identifying and removing redundancies in production circuits using energy minimization. The formulation is also applicable to Boolean satisfactorily and BDD methods. We first use the test generation algorithm for identifying undetectable faults and then relax specific constraints in the original test generation problem by ignoring the non-Boolean components. We show that undetectability in the relaxed formulation implies redundancy. We report redundancy removal results for production VLSI circuits, ISCAS 85, and full-scan versions of the ISCAS 89 benchmark circuits.

We propose a new method to identify and test primitive faults in combinational circuits described as multi-level or two-level netlists. A primitive fault is a multiple path delay fault for which none of the single paths contained in the fault is robustly or non-robustly testable while the presence of the fault can degrade the circuit performance. Identification and testing of primitive faults is important for at least two reasons: (1) a large percentage of paths in production circuits remain untestable under the single-path delay fault model, (2) distributed manufacturing defects usually adversely affect more than one path and these defects can be detected only by analyzing multiple affected paths. The single-path delay faults contained in a primitive fault have to merge at some gate(s). Our methodology for identifying primitive faults can quickly (1) rule out a large number of gates as possible merging points for primitive faults, and (2) prune the combination of paths that can never belong long any primitive fault. Our identification procedure also finds a test for the fault. We present a complete algorithm for identifying and testing double path delay faults. This procedure can be extended to identify primitive faults consisting of three or more paths. Experimental results on several multi-level combinational benchmark circuits are included to demonstrate the usefulness of our technique.

We show that existing synthesis techniques may produce asynchronous circuits that are not initializable by gate level analysis tools even when the design is functionally initializable. Due to the absence of any initialization sequence, a fault simulator or test generator that assumes an unknown starting state will be completely ineffective for these circuits. In this paper, we show that proper consideration of initializability during the asynchronous circuit synthesis procedure can guarantee initializable implementations. We show that the assignment of don't cares during the synthesis procedure affects the initializability of the final implementation. We present a novel implicit enumeration procedure that selectively assigns don't cares to obtain an initializable implementation. Initialization sequences are obtained as a by-product of our synthesis procedure.

This paper presents software (model) transformations that can be used to effectively generate high fault coverage test sets. Unlike synthesis or design for testability methods which involve hardware modifications, this approach does not modify the hardware design. Instead, it transforms a software model of the design into a new software model that has desirable testability properties. A sequential test generator generates tests for the new model. The new model may not be functionally equivalent to the original design but our transformations guarantee that the tests generated for the new model can always be inverse mapped to serve as tests for the original design. Experimental results show that significantly high fault coverage can be achieved by using this approach.

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.

Production VLSI circuits typically consist of primitives like tri-state buffers, bidirectional buffers and bus configurations that assume non-Boolean values like the high-impedance state. The present work describes a systematic methodology for extending test generation algorithms to full-scan production circuits. Key features of the methodology are illustrated using the energy minimization based test generation algorithm for combinational circuits. The main features of our methodology that make the test generation algorithm practical for large production circuits are: (1) only one Boolean variable is used to represent the value on a signal and all signals assume only Boolean values during the test generation procedure, (2) function of non-Boolean primitives is separated into Boolean and non-Boolean components, and energy functions are derived only for the Boolean component, and (3) non-Boolean components are implicitly considered in the energy minimization procedure. In this process, no new energy functions other than the normal Boolean gate energy functions are needed. Further, in this paper, we report the first known method of identifying and removing redundancies in production circuits using formulations based on energy minimization, satisfiability or BDD-based methods. We first use the test generation algorithm for identifying undetectable faults and then relax specific constraints in the original test generation problem by ignoring the non-Boolean components. We show that undetectability in the relaxed formulation implies redundancy. Redundancy removal results on several production VLSI circuits, ISCAS 85 and full-scan versions of the ISCAS 89 benchmark circuits are reported.

We give two theorems for identifying untestable faults in sequential circuits. The first, the single-fault theorem, states that if a single fault in a combinational array is untestable then that fault is untestable in the sequential circuit. The array replicates the combinational logic and can have any finite length. We assume that the present state inputs of the left-most block are completely controllable. The next state outputs of the right-most block are considered observable. A combinational test pattern generator determines the detectability of single faults in the right-most block. The second theorem, called the multifault theorem, uses the array model with a multifault consisting of a single fault in every block. The theorem states that an untestable multifault in the array corresponds to an untestable single fault in the sequential circuit. For the array with a single block both theorems identify combinational redundancies. Experiments on ISCAS benchmarks show that using a small array size (typically, two to four blocks) we can identify a large number of sequentially untestable faults.>

We present a new formulation of the delay testing problem as an energy minimization problem. Two important applications have motivated this work. First, it can be used to efficiently generate robust and nonrobust tests for path delay faults in scan and hold type of sequential circuits. Second, It allows the design of a special class of delay fault testable circuits, called (k,K)-circuits, that have polynomial-time test generation complexity. For the new formulation, the relationship between input and output signal states of a logic gate for an arbitrary pair of input vectors is expressed through an energy function. The minimum-energy states of this function correspond to signal values that are consistent with the gate's logic function. The function also implicitly includes the information about the potential hazards due to arbitrary delay distributions in the circuit. The energy function for the circuit is the summation of the individual gate energy functions. To derive tests for a given delay fault, this function is suitably modified such that any minimum-energy state is guaranteed to be a test. The specific modifications to the energy function depend on the type (robust or nonrobust, with or without hazards) of delay test desired. For (k, K)-circuits, we show that the energy function can be minimized in polynomial-time. For general circuits, where the problem still has an exponential complexity, the recently proposed transitive closure based test generation technique is very effective in generating tests. This approach efficiently determines a delay test or establishes that no test is possible for the given delay fault. We report experimental results on various sequential benchmark circuits (full-scan versions) showing the feasibility and practicality of the new methods.>

We present new algorithms for embedding test functions into the state diagram of a finite state machine. We first identify the cases where test functions can be embedded into the state diagram of the given object machine without using an extra input line. When such embedding is possible, our method finds it. In other cases, an extra input line must be added to the object machine to make the embedding possible. For the extra input case, we use partition theory and state variable dependencies in the object machine to obtain a mapping of the test machine states onto the object machine states. This mapping introduces a minimum number of extra state variable dependencies in the augmented machine as compared to the dependencies in the object machine. Experimental results on several MCNC benchmarks show that our method yields augmented machine implementations that have lower area than corresponding full scan designs. The test generation complexity for the augmented machine implementation is the same as that for a full scan design. We further consider the embedding of test functions into machines specified as an interconnection of finite state machines. We incorporate test functions into each component finite state machine such that the augmented interconnected machine has the same testability properties as the product machine with test function.>

We present a new area-efficient procedure for embedding test function into the gate-level implementation of a sequential circuit. First, we develop a test machine embedding technique for a given gate-level implementation of a finite state machine. The test machine states are mapped onto the states of the given circuit such that a minimum number of new state variable dependencies are introduced. The composite function is optimized. Experimental results show that our method yields testable machine implementations that have lower area than the corresponding full scan designs. The test generation complexity for our machine implementation is the same as that for a full scan design. To apply the method to large gate-level designs, we partition the circuit into interconnected finite-state machines. Each component state machine can be specified either as its gate-level implementation or as the extracted state diagram. We incorporate test functions into each component finite state machine such that the entire interconnection of the augmented components has the same testability properties as the product machine with a single test function. ISCAS '89 benchmark circuits are partitioned into component finite state machines using a new testability-directed partitioning algorithm. Again, our embedding procedure results in testable circuits that have lower area than the corresponding full scan designs.>

We develop an exact algorithm for selecting flip-flops in partial scan designs to break all feedback cycles.The main ideas that allow us to solve this hard problem exactly for large, practical instances are -graph transformations, a partitioning scheme used in the branch and bound procedure, and pruning techniques based on an integer linear programming formulation of the minimum feedback vertex set (MFVS) problem.We have obtained optimum solutions for the ISCAS '89 benchmark circuits and several production VLSI circuits within reasonable computation time.For example, the optimal number of scan flip-flops required to eliminate all cycles except self-loops in the circuit s38417 is 374.This optimal solution was obtained in 32 CPU seconds on a SUN Sparc 2 workstation.

Article Free Access Share on Resynthesis and retiming for optimum partial scan Authors: Srimat T. Chakradhar C&C Research Laboratories, NEC, 4 Independence Way, Princeton, NJ C&C Research Laboratories, NEC, 4 Independence Way, Princeton, NJView Profile , Sujit Dey C&C Research Laboratories, NEC, 4 Independence Way, Princeton, NJ C&C Research Laboratories, NEC, 4 Independence Way, Princeton, NJView Profile Authors Info & Claims DAC '94: Proceedings of the 31st annual Design Automation ConferenceJune 1994 Pages 87–93https://doi.org/10.1145/196244.196288Published:06 June 1994Publication History 36citation145DownloadsMetricsTotal Citations36Total Downloads145Last 12 Months6Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present a procedure for synthesizing initializable asynchronous circuits from functionally uninitializable Signal Transition Graphs (STG). After characterizing the necessary conditions for functional uninitializability, we propose a technique that transforms the original STG into an equivalent, functionally initializable STG. It is shown that initializability can be achieved by sacrificing minimal concurrency without violating the syntactic properties of the STG required for a hazard-free implementation. The synthesis of a trigger module illustrates this procedure.>

This paper presents a technique to enhance the testability of sequential circuits by repositioning registers. A novel retiming for testability technique is proposed that reduces cycle lengths in the dependency graph, converts sequential redundancies into combinational redundancies, and yields retimed circuits that usually require fewer scan registers to break all cycles (except self-loops) as compared to the original circuit. The retiming technique is based on a new minimum cost flow formulation that simultaneously considers the interactions among all strongly connected components (SCCs) of the circuit to minimize the number of registers in the SCCs. Experimental results on several large sequential circuits demonstrate the effectiveness of the proposed retiming for testability technique.>

We describe a continuous optimization approach for the test generation of combinational circuits. We extend the domain of signal values from the traditional Boolean 0 or 1 value to the real unit interval /spl lsqb/0, 1/spl rsqb/. Responses of Boolean gates comprising the circuit are also extended to deal with real input values. Non-linear smooth functions are constructed for every gate. A non-linear continuous function for the entire circuit is obtained as a summation of the individual gate functions. A similar function is derived for the faulty circuit. We construct an objective function using the good and faulty circuit functions. The objective function is minimized when at least one of the corresponding outputs of the good and faulty circuit differ. The test generation problem is formulated as the minimization of the objective function over a unit hypercube in the Euclidean space. The dimension of the space is equal to the number of primary inputs of the circuit. We optimize the smooth function inside a convex polytope using a variant of gradient descent and line search strategies. We start at the center of the hypercube and follow a trajectory to one of the corners of the hypercube that corresponds to a test vector. Preliminary experimental results on the ISCAS '85 and '89 benchmark circuits demonstrate the feasibility of our approach.>

We examine the representational capabilities of first-order and second-order single-layer recurrent neural networks (SLRNN's) with hard-limiting neurons. We show that a second-order SLRNN is strictly more powerful than a first-order SLRNN. However, if the first-order SLRNN is augmented with output layers of feedforward neurons, it can implement any finite-state recognizer, but only if state-splitting is employed. When a state is split, it is divided into two equivalent states. The judicious use of state-splitting allows for efficient implementation of finite-state recognizers using augmented first-order SLRNN's.

ABSTRACT: We propose a novel sequential delay op-timization technique based on network flow methods that simultaneously exploits delays on all paths in the circuit. We view the sequential circuit as an intercon-nection of path segments with pre-specified delays. Path segments are bounded by flip-flops, primary inputs or primary outputs. Recognizing that a delay optimizer can satisfy certain delay constraints more easily than others, we first propose a measure of difficulty for the delay optimizer. Our measure is based on explicit path delays to be satisfied by the delay optimizer. Also, our measure induces a partial order on the set of possible delay constraints. We then compute a set of delay con-straints that is optimal with respect to our measure. The delay constraint set is optimal in the sense that it is the easiest constraint that can be specified to the delay optimizer. We formulate the delay constraint cal-culation problem as a minimum cost network flow prob-lem. If the delay optimizer satisfies the optimal delay constraint set, then the resynthesized circuit may have several pat hs exceeding the desired clock period. How-ever, we show that the resynthesized circuit can always be retimed to achieve the desired clock period. Exper-imental results on MCNC synthesis benchmarks show that our method improves the performance of circuits beyond what is achievable using optimal retiming and conventional combinational logic synthesis. 1.

We present a new area-efficient procedure for embedding test function into the gate-level implementation of a sequential circuit. We use partition theory and a state variable dependency minimization criterion to map the test function states onto the states of the given circuit. The test generation complexity for our implementation is the same as that for a full scan design. To apply the method to large gate-level designs, we partition the circuit into interconnected finite-state machines. We incorporate test functions into each component machine such that the augmented interconnected machine has the same testability properties as the product machine with test function. Several ISCAS 89 benchmark circuits are partitioned into component finite state machines using a testability-directed partitioned into component finite state machines using a testability-directed partitioning algorithm. Our embedding procedure results in testable circuits that have smaller area than the corresponding full scan designs.>

A transitive-closure-based test generation algorithm is presented. A test is obtained by determining signal values that satisfy a Boolean equation derived from the neural network model of the circuit incorporating necessary conditions for fault activation and path sensitization. The algorithm is a sequence of two main steps that are repeatedly executed: transitive closure computation and decision-making. A key feature of the algorithm is that dependences derived from the transitive closure are used to reduce ternary relations to binary relations that in turn dynamically update the transitive closure. The signals are either determined from the transitive closure or are enumerated until the Boolean equation is satisfied. Experimental results on the ISCAS 1985 and the combinational parts of ISCAS 1989 benchmark circuits are presented to demonstrate efficient test generation and redundancy identification. Results on four state-of-the-art production VLSI circuits are also presented.>

A statistical model of parallel processing and a performance evaluation technique are introduced. A task is characterized by the number of atoms and by activity. An atom is the smallest part of computation that cannot be distributed to multiple processors and all atoms of a task are assumed to be equal in computational effort. Furthermore, atoms of the task became active with a fixed probability a called the activity. The task is equally divided among processors and the computation is synchronized at periodic instances when the results can be shared. The amount of computational activity of a processor within the period between synchronizations is assumed to be a binomial random variable. The performance of the multiprocessor system is derived from the maximum order-statistic of these random variables. The theoretical performance predicted by the analysis agrees well with the reported experimental performance of logic simulation of production VLSI chips, and several observed phenomena are explainable.>

We present a transitive closure (TC) based test generation algorithm.A test k obtained by determining signal values that sattsfy a Boolean expression constructed from the ctrcuit netltst and the fault.The atgorithm is a sequenceof two main stepsthat are repeatedly executed: TC computation and dectsion- maldng.To compute the TC of the ctrcuit, we construct an hnpltcation graph whose vertices are labeled as the true and fatse states of alt signals.A directed edge (z, y) tn this graph represents the controlling htfluence of the true state of signal z on the true state of signal y that are connected through a wire or a gate.Since the implication graph only includes pairwtse (or btnary) relations, it is a partial representation of the netlist.The TC of the bnplication graph contatns pairwise logical relationships among all signats.When signal relationships describing fault activation and path sensittzatton are included, TC determines signal fixations and logical contradictions that dtrectly identify many redundancies.Sensitization of physical and logical dominators, unique path sensitization, static and dynamic learntng and other techniques that are useful in determiatng necessary stgnal assignments are implicit tn the preeess.If signals thus determined satisfy the Boolean formula, we have a test.Otherwtse, we use the decision-making step, fix an unasstf+ned signal, and update the TC to find further logical consequences.

We recently proposed an unconventional digital circuit modeling technique and formulated test generation as an energy minimization problem [7]. Although energy minimization is as hard as test generation, the new approach has two advantages. Since the circuit function is mathematically expressed, operations research techniques like linear and non-linear programming can be applied to test generation. The non-causal form of the model makes parallel processing possible. The energy function E, a quadratic 0-1 function, is split into two sub-functions, a homogeneous posiform and an inhomogeneous posiform. The minimum of E is the sum of the minima of the two sub-functions, each having a minimum value of 0. We obtain a minimizing point of the homogeneous posiform, in time complexity that is linear in the number of sub-function terms, and check if the other sub-function becomes 0. When both become 0, we have a test vector. We discuss several easily parallelizable speedup techniques using the transitive closure and other graph properties. Preliminary results on combinational circuits confirm the feasibility of this technique.

A statistical model is presented of parallel processing based on circuit activity defined as the average number of gates evaluated at a time step. The number of active gates in a processor is assumed to be a random variable with a binomial probability density function. The performance of the multiprocessor system is derived from the maximum order-statistic of these random variables. When the gates can be equally divided among the p processors, the lower bound on speedup is found to be a*p, where a is the average circuit activity. For unequal division of gates, the lower bound on speedup is less than a*p. Interestingly, for very low activity, speedups significantly higher than the lower bounds are possible.>

A statistical model for analyzing the performance of synchronized iterative algorithms on a multiprocessor system is presented. Key ideas are illustrated using logic simulation as an example problem. The authors introduce activity as a relevant parameter and analyze the behavior of the parallel processing system using an analytical method. The statistical performance results agree with and satisfactorily explain empirical observations on production VLSI circuits obtained by other researchers. It is shown that as the number of processors is increased, the speedup rapidly changes from p to a*p, where a is the activity and p is the number of processors. Low activity reduces speedup. A lower bound on the speedup of the parallel processing system is presented. For high activity, this lower bound is quite close to the actual speedup.>

A new automatic test pattern generation (ATPG) methodology that has the potential to exploit fine-grain parallel computing and relaxation techniques is described. This approach is radically different from the conventional methods used to generate tests for circuits from their gate level description. The digital circuit is represented as a bidirectional network of neurons. The circuit function is coded in the firing thresholds of neurons and the weights of interconnection links. This neural network is suitably reconfigured for solving the ATPG problem. A fault is injected into the neural network and an energy function is constructed with global minima at test vectors. The authors simulated the neural network on a serial computer, and determined the global minima of the energy function using a directed search technique augmented by probabilistic relaxation. Preliminary results on combinational circuits confirm the feasibility of this technique.>

An automatic test pattern generation (ATPG) methodology that has the potential to exploit fine-grain parallel computing and relaxation techniques is described. The approach is radically different from the conventional methods used to generate tests for circuits from their gate-level descriptions. A digital circuit is represented as a bidirectional network of neurons. The circuit function is coded in the firing thresholds of neurons and the weights of interconnection links. This neural network is suitably reconfigured for solving the ATPG problem. A fault is injected into the neural network and an energy function is constructed with global minima at test vectors. Global minima are determined by a probabilistic relaxation technique augmented by a directed search. Preliminary results on combinational circuits confirm the feasibility of the technique.>