Decomposition, the process of breaking down complex problems into manageable parts, is a fundamental component of computational thinking (CT) but remains challenging for novice learners. We present Spark, a multimodal programming interface that supports the externalization of decomposition thinking by organizing user-articulated goals into structured steps and enacting them through a tangible robot, making decomposition visible and open to inspection. The design of Spark is theory-driven, with its user interface aligned to three decomposition rationales: substantive, relational, and functional decomposition. In a study with 20 adult novices, we compared Spark with Scratch, an educational block-based visual programming interface. While both systems were associated with improvements in participants’ self-reported decomposition skills, only Spark was associated with measurable gains on objective assessments and significantly higher task success when experienced first, while maintaining comparable workload and completion times. Participants reported that externalizing the otherwise hidden process of decomposition made programming more tangible and motivating. These findings, highlighting the complementary roles of multimodal interaction in shaping novices’ decomposition experiences, inform the design of interactive programming interfaces that aim to support the externalization of reasoning processes. More broadly, our work contributes to the field of human-AI interaction in learning, illustrating how multimodal interaction can be responsibly integrated to scaffold reasoning, support reflection, and promote equitable participation in computing.

Machine learning is evolving towards high-order models that necessitate pre-training on extensive datasets, a process associated with significant overheads. Traditional models, despite having pre-trained weights, are becoming obsolete due to architectural differences that obstruct the effective transfer and initialization of these weights. To address these challenges, we introduce a novel framework, QuadraNet V2, which leverages quadratic neural networks to create efficient and sustainable high-order learning models. Our method initializes the primary term of the quadratic neuron using a standard neural network, while the quadratic term is employed to adaptively enhance the learning of data non-linearity or shifts. This integration of pre-trained primary terms with quadratic terms, which possess advanced modeling capabilities, significantly augments the information characterization capacity of the high-order network. By utilizing existing pre-trained weights, QuadraNet V2 reduces the required GPU hours for training by 90% to 98.4% compared to training from scratch, demonstrating both efficiency and effectiveness.

For collaborative inference through a cloud computing platform, it is sometimes essential for the client to shield its sensitive information from the cloud provider. In this paper, we introduce Ensembler, an extensible framework designed to substantially increase the difficulty of conducting model inversion attacks by adversarial parties. Ensembler leverages selective model ensemble on the adversarial server to obfuscate the reconstruction of the client’s private information. Our experiments demonstrate that Ensembler can effectively shield input images from reconstruction attacks, even when the client only retains one layer of the network locally. Ensembler significantly outperforms baseline methods by up to $\mathbf{4 3. 5 \%}$ in structural similarity while only incurring 4.8% time overhead during inference.

Large Language Models (LLMs) deployed on edge devices, known as edge LLMs, need to continuously fine-tune their model parameters from user-generated data under limited resource constraints. However, most existing learning methods are not applicable for edge LLMs because of their reliance on high resources and low learning capacity. Prompt tuning (PT) has recently emerged as an effective fine-tuning method for edge LLMs by only modifying a small portion of LLM parameters, but it suffers from user domain shifts, resulting in repetitive training and losing resource efficiency. Conventional techniques to address domain shift issues often involve complex neural networks and sophisticated training, which are incompatible for PT for edge LLMs. Therefore, an open research question is how to address domain shift issues for edge LLMs with limited resources. In this paper, we propose a prompt tuning framework for edge LLMs, exploiting the benefits offered by non-volatile computing-in-memory (NVCiM) architectures. We introduce a novel NVCiM-assisted PT framework, where we narrow down the core operations to matrix-matrix multiplication, which can then be accelerated by performing in-situ computation on NVCiM. To the best of our knowledge, this is the first work employing NVCiM to improve the edge LLM PT performance.

The diagnosis and treatment of individuals with communication disorders offers many opportunities for the application of speech technology, but research so far has not adequately considered: the diversity of conditions, the challenges of limited data, and the role of pragmatic deficits. This paper explores how a general-purpose model of perceived pragmatic similarity may overcome these limitations. It shows that a simple model can capture utterance aspects that are relevant to diagnosis of autism and of specific language impairment, outlines how it might support several use cases for clinicians and clients, and analyzes its performance and limitations.

For reliability-critical silicon systems, transient errors caused by cosmic rays necessitate comprehensive and efficient reliability analysis before product deployment. Fault injection (FI) serves as a cost-effective alternative to expensive irradiation experiments for evaluating system robustness. However, simulation-based FI is constrained by the performance of the underlying hardware platform, making it impractical for large-scale designs, where achieving high fault coverage can take months or even years. Furthermore, most transient errors have no impact on system functionality, and filtering out these insignificant errors in advance can significantly enhance the efficiency of reliability analysis. To address these challenges, we propose Tenpura, a fault evaluation platform designed for ultra-fast reliability analysis. In Tenpura, a transient fault scope narrowing method is introduced to narrow the FI scope via the proposed scan-based activity tracing flow, further optimizing fault analysis and improving overall efficiency. By leveraging FPGA emulation and scan chain-based fault analysis at the pre-silicon stage, Tenpura achieves high-efficiency fault reduction (88.49–96.26% across three design under tests (DUTs) including RISC-V cores and NVDLA-based AI accelerator) within one month, delivering over an order of magnitude faster fault analysis compared to SOTA methods.

Along with the National Institute of Standards and Technology (NIST) post-quantum cryptography (PQC) standardization process, efficient hardware acceleration for PQC has become a priority. Among the NIST-selected PQC digital signature schemes, FALCON shows great promise due to its compact key sizes and efficient Signature Verification procedure. However, FALCON is regarded as highly computationally complex, and as a result, few works for hardware acceleration of FALCON can be found in the literature, where the few existing ones only target high-performance. To fill the gap, this paper presents a Lightweight and Efficient hardware accelerator for the Signature Verification portion of FALCON (LEAF), specifically for resource-constrained applications. We propose an efficient design strategy, including a novel data dependence flow, to maximize the utilization of very small resources for all arithmetic procedures. Then, the proposed full-hardware LEAF is built, containing an ultra-lightweight number theoretical transform (NTT) core with a novel twiddle factor access pattern. Finally, we conduct a thorough evaluation to demonstrate the efficiency of LEAF. To the best of our knowledge, this is the first lightweight and meanwhile most resource-efficient FALCON Signature Verification full-hardware accelerator in the literature, offering 65% and 66% less aggregate resource usage and achieving 24% and 14% less equivalent area-time product (eATP), compared to the state-of-the-art for FALCON-512 and FALCON-1024, respectively. We hope that this work can spur further research in the field.

The combination of Large Language Models (LLM) and Automatic Speech Recognition (ASR), when deployed on edge devices (called edge ASR-LLM), can serve as a powerful personalized assistant to enable audio-based interaction for users. Compared to text-based interaction, edge ASR-LLM allows accessible and natural audio interactions. Unfortunately, existing ASR-LLM models are mainly trained in high-performance computing environments and produce substantial model weights, making them difficult to deploy on edge devices. More importantly, to better serve users’ personalized needs, the ASR-LLM must be able to learn from each distinct user, given that audio input often contains highly personalized characteristics that necessitate personalized on-device training. Since individually fine-tuning the ASR or LLM often leads to suboptimal results due to modality-specific limitations, end-to-end training ensures seamless integration of audio features and language understanding (cross-modal alignment), ultimately enabling a more personalized and efficient adaptation on edge devices. However, due to the complex training requirements and substantial computational demands of existing approaches, cross-modal alignment between ASR audio and LLM can be challenging on edge devices. In this work, we propose a resource-efficient cross-modal alignment framework that bridges ASR and LLMs on edge devices to handle personalized audio input. Our framework enables efficient ASR-LLM alignment on resource-constrained devices like Raspberry Pi 5 (8GB RAM), achieving 50x training time speedup while improving the alignment quality by more than 50%. To the best of our knowledge, this is the first work to study efficient ASR-LLM alignment on resource-constrained edge devices.

We present RASO, a foundation model designed to Recognize Any Surgical Object, offering robust open-set recognition capabilities across a broad range of surgical procedures and object classes, in both surgical images and videos. RASO leverages a novel weakly-supervised learning framework that generates tag-image-text pairs automatically from large-scale unannotated surgical lecture videos, significantly reducing the need for manual annotations. Our scalable data generation pipeline gathers 2,200 surgical procedures and produces 3.6 million tag annotations across 2,066 unique surgical tags. Our experiments show that RASO achieves improvements of 2.9 mAP, 4.5 mAP, 10.6 mAP, and 7.2 mAP on four standard surgical benchmarks respectively in zero-shot settings, and surpasses state-of-the-art models in supervised surgical action recognition tasks. We will open-source our code, model, and dataset to facilitate further research.

Physics-Informed Neural Networks (PINNs) are a kind of deep-learning-based numerical solvers for partial differential equations (PDEs). Existing PINNs often suffer from failure modes of being unable to propagate patterns of initial conditions. We discover that these failure modes are caused by the simplicity bias of neural networks and the mismatch between PDE’s continuity and PINN’s discrete sampling. We reveal that the State Space Model (SSM) can be a continuous-discrete articulation allowing initial condition propagation, and that simplicity bias can be eliminated by aligning a sequence of moderate granularity. Accordingly, we propose PINNMamba, a novel framework that introduces sub-sequence modeling with SSM. Experimental results show that PINNMamba can reduce errors by up to 86.3% compared with state-of-the-art architecture. Our code is available at Supplementary Material.

Identifying effective interventions from the scientific literature is challenging due to the high volume of publications, specialized terminology, and inconsistent reporting formats, making manual curation laborious and prone to oversight. To address this challenge, this paper proposes a novel framework leveraging large language models (LLMs), which integrates a progressive ontology prompting (POP) algorithm with a dual-agent system, named LLM-Duo. On the one hand, the POP algorithm conducts a prioritized breadth-first search (BFS) across a predefined ontology, generating structured prompt templates and action sequences to guide the automatic annotation process. On the other hand, the LLM-Duo system features two specialized LLM agents, an explorer and an evaluator, working collaboratively and adversarially to continuously refine annotation quality. We showcase the real-world applicability of our framework through a case study focused on speech-language intervention discovery. Experimental results show that our approach surpasses advanced baselines, achieving more accurate and comprehensive annotations through a fully automated process. Our approach successfully identified 2,421 interventions from a corpus of 64,177 research articles in the speech-language pathology domain, culminating in the creation of a publicly accessible intervention knowledge base with great potential to benefit the speech-language pathology community.

For resource-constrained AI accelerators applied in edge computing, achieving high power efficiency in neural network (NN) model computation is crucial. However, current designs often overlook the efficiency of off-chip/on-chip data interaction, leading to high latency, which in turn results in suboptimal power efficiency during computation. Additionally, inefficient memory bank allocation further exacerbates latency by causing underutilization of storage resources, thereby contributing to higher overall latency and energy consumption. To address these challenges, this paper proposes a scalable multi-path rolling data refresh and layer-wise bank allocation architecture. The rolling data refresh mechanism enables efficient data interaction between off-chip and on-chip storage, reducing latency and minimizing the area overhead of on-chip memories. The layer-wise bank allocation optimizes on-chip memory utilization according to specific application requirements, improving memory efficiency. A case study on a 28nm AI accelerator demonstrates a 30.6% reduction in area, achieves a power efficiency of 7.36–10.28 TOPS/W, and reduces external memory access by 2.63% to 37.24% on VGG16 and ViT-Small.

Reliability-demanding devices often require numerous fault injections (FIs) for reliability analysis in the product cycle. However, software-based FI typically demonstrates extremely low efficiency due to low simulation throughput, especially for large-scale designs, while hardware-based FI presents challenges related to complexity of setup and limited scalability. Additionally, FIs often occur in intervals where errors do not affect the system’s outcome, e.g., after final read before next write, necessitating efficient pruning of non-impactful FIs. To address this, a general-purpose FI-specialized framework, Genshin, is proposed for rapid reliability analysis. On the hardware side, we provide an FI-specialized design, which works with Design Under Test (DUT) chips on PCB boards and supports FI control based on the scan chain (SC). An integrated programmable logic allows for flexible and custom FI pattern definitions. Furthermore, an architecturally correct execution (ACE) analysis generates pruned fault tables for DUTs. In Genshin, the SC logic achieves 3,802-65,388 cycles/FI across SC lengths ranging from 2,795 to 61,393 in different DUTs, while the programmable logic enables custom error patterns such as layout-aware multi-bit upset (MBU). Furthermore, the pruned fault tables achieve fault reduction rates from 45.80% to 83.21%.

Physics‑Informed Neural Networks (PINNs) often exhibit “failure modes” in which the PDE residual loss converges while the solution error stays large, a phenomenon traditionally blamed on local optima separated from the true solution by steep loss barriers. We challenge this understanding by demonstrate that the real culprit is insufficient arithmetic precision: with standard FP32, the L‑BFGS optimizer prematurely satisfies its convergence test, freezing the network in a spurious failure phase. Simply upgrading to FP64 rescues optimization, enabling vanilla PINNs to solve PDEs without any failure modes. These results reframe PINN failure modes as precision‑induced stalls rather than inescapable local minima and expose a three‑stage training dynamic—un‑converged, failure, success—whose boundaries shift with numerical precision. Our findings emphasize that rigorous arithmetic precision is the key to dependable PDE solving with neural networks. Our code is available at Supplementary Material.

In an era, where the exponential growth of image data driven by the Internet of Things (IoT) is outpacing traditional storage solutions, this work explores and advances the potential of implicit neural representation (INR) as a transformative approach to image compression. INR leverages the function approximation capabilities of neural networks to represent various types of data. While previous research has employed INR to achieve compression by training small networks to reconstruct large images, no work has explored past the fundamental barrier of using one network per image. This work proposes a novel advancement by breaking this barrier and representing multiple images with a single network. By modifying the loss function during training, the proposed approach allows a small number of weights to represent a large number of images, even those significantly different from each other. A thorough analytical study of the convergence of this new training method is also carried out, establishing upper bounds that not only confirm the method’s validity but also offer insights into optimal hyperparameter design. The proposed method is evaluated on the Kodak, ImageNet, and CIFAR-10 datasets. Experimental results demonstrate that all 24 images in the Kodak dataset can be represented by linear combinations of two sets of weights, achieving a peak signal-to-noise ratio (PSNR) of 26.5 dB with as low as 0.2 bits per pixel (BPP). The proposed method matches the rate-distortion performance of state-of-the-art image codecs, such as BPG, on the CIFAR-10 dataset. Additionally, the proposed method maintains the fundamental properties of INR, such as arbitrary resolution reconstruction of images.

FPGA-based edge servers are used in many applications in smart cities, hospitals, retail, etc. Equipped with heterogeneous FPGA-based accelerator cards, the servers can be implemented with multiple tasks, including efficient video prepossessing, machine learning algorithm acceleration, etc. These servers are required to implement inference during the daytime while retraining the model during the night to adapt to new environments, domains, or new users. During the retraining, conventionally, the incoming data are transmitted to the cloud, and then the updated machine learning models will be transferred back to the edge server. Such a process is inefficient and cannot protect users’ privacy, so it is desirable for the models to be directly trained on the edge servers. Deploying convolutional neural network (CNN) training on heterogeneous resource-constrained FPGAs is challenging since it needs to consider both the complex data dependency of the training process and the communication bottleneck among different FPGAs. Previous multiaccelerator training algorithms select optimal scheduling strategies for data parallelism (DP), tensor parallelism (TP), and pipeline parallelism (PP). However, PP cannot deal with batch normalization (BN) which is an essential CNN operator, while purely applying DP and TP suffers from resource under-utilization and intensive communication costs. In this work, we propose MTrain, a novel multiaccelerator training scheduling strategy that transfers the training process into a multibranch workflow, thus independent suboperations of different branches are executed on different training accelerators in parallelism for better utilization and reduced communication overhead. Experimental results show that we can achieve efficient CNN training on heterogeneous FPGA-based edge servers with$1.07\times $–$2.21\times $speedup under 15-GB/s peer-to-peer bandwidth compared to the state-of-the-art work.

The scaling laws have become the de facto guidelines for designing large language models (LLMs), but they were studied under the assumption of unlimited computing resources for both training and inference. As LLMs are increasingly used as personalized intelligent assistants, their customization (i.e., learning through fine-tuning) and deployment onto resource-constrained edge devices will become more and more prevalent. An urgent but open question is how a resource-constrained computing environment would affect the design choices for a personalized LLM. We study this problem empirically in this work. In particular, we consider the tradeoffs among a number of key design factors and their intertwined impacts on learning efficiency and accuracy. The factors include the learning methods for LLM customization, the amount of personalized data used for learning customization, the types and sizes of LLMs, the compression methods of LLMs, the amount of time afforded to learn, and the difficulty levels of the target use cases. Through extensive experimentation and benchmarking, we draw a number of surprisingly insightful guidelines for deploying LLMs onto resource-constrained devices. For example, an optimal choice between parameter learning and RAG may vary depending on the difficulty of the downstream task, the longer fine-tuning time does not necessarily help the model, and a compressed LLM may be a better choice than an uncompressed LLM to learn from limited personalized data.

TheNth-degree truncated polynomial ring units (NTRUs)-based postquantum cryptography (PQC) has drawn significant attention from the research communities, e.g., the National Institute of Standards and Technology (NIST) PQC standardization process selected algorithm Fast Fourier lattice-based compact (Falcon). Following the research trend, efficient hardware accelerator design for polynomial multiplication (an important component of the NTRU-based PQC) is crucial. Unlike the commonly used number theoretic transform (NTT) method, in this article, we have presented a novel SChoolbook-Originated Polynomial multiplication accElerators (SCOPE) design framework. Overall, we have proposed the schoolbook-based method in an innovative format to implement the targeted polynomial multiplication, first through a schoolbook-variant version and then through a Toeplitz matrix-vector product (TMVP)-based approach. Four layers of coherent and interdependent efforts have been carried out: 1) a novel lookup table (LUT)-based point-wise multiplier is proposed along with a related modular reduction technique to obtain optimal implementation; 2) a new hardware accelerator is introduced for the targeted polynomial multiplication, deploying the proposed point-wise multiplier; 3) the proposed architecture is extended to a TMVP-based polynomial multiplication accelerator; and 4) the efficiency of the proposed accelerators is demonstrated through implementation and comparison. Finally, the proposed design strategy is also extended to another NTRU-based scheme and other schoolbook- and toom-cook-based polynomial multiplications (used in other PQC), and obtains the same superior performance. We hope that the outcome of this research can impact the ongoing NIST PQC standardization process and related full-hardware implementation work for schemes like Falcon.

Kubernetes ($K$8s) is a container orchestration plat-form for cloud-based IaaS environments. While it operates on either bare-metal servers or VMs, users prefer VMs for cost savings and agility reasons despite the added network overhead. This overhead, stemming from dual network tunneling at the VM and container levels, degrades performance. To address this, we present UniNet, a SmartNIC-based solution that offloads container-level network tunneling. We designed UniNet to be compatible with leading Container Network Interfaces (CNIs). This approach involves three key elements: (1) transforming VF-based NICs into a container network gateway, (2) offloading the critical path of the data plane functionalities to SmartNICs for enhanced performance and reduced latency, and (3) instituting an isolated control plane that separates VM- and container-level rule insertions, making it tenant-accessible. UniNet boosts CNI throughput by 7.08 x on average, cuts tail latency by 41.6 %, and reduces CPU usage by up to 5.6 x for the receiver and 4.02 x for the sender, respectively.

Neural Architecture Search (NAS) has become the de fecto tools in the industry in automating the design of deep neural networks for various applications, especially those driven by mobile and edge devices with limited computing resources. The emerging large language models (LLMs), due to their prowess, have also been incorporated into NAS recently and show some promising results. This paper conducts further exploration in this direction by considering three important design metrics simultaneously, i.e., model accuracy, fairness, and hardware deployment efficiency. We propose a novel LLM-based NAS framework, FL-NAS, in this paper, and show experimentally that FL-NAS can indeed find high-performing DNNs, beating state-of-the-art DNN models by orders-of-magnitude across almost all design considerations.

Recent progress in computer vision-oriented neural network designs is mostly driven by capturing high-order neural interactions among inputs and features. And there emerged a variety of approaches to accomplish this, such as Transformers and its variants. However, these interactions generate a large amount of intermediate state and/or strong data dependency, leading to considerable memory consumption and computing cost, and therefore compromising the overall runtime performance. To address this challenge, we rethink the high-order interactive neural network design with a quadratic computing approach. Specifically, we propose QuadraNet — a comprehensive model design methodology from neuron reconstruction to structural block and eventually to the overall neural network implementation. Leveraging quadratic neurons’ intrinsic high-order advantages and dedicated computation optimization schemes, QuadraNet could effectively achieve optimal cognition and computation performance. Incorporating state-of-the-art hardware-aware neural architecture search and system integration techniques, QuadraNet could also be well generalized in different hardware constraint settings and deployment scenarios. The experiment shows that QuadraNet achieves up to 1.5 × throughput, 30% less memory footprint, and similar cognition performance, compared with the state-of-the-art high-order approaches.

Textual analogies that make comparisons between two concepts are often used for explaining complex ideas, creative writing, and scientific discovery.In this paper, we propose and study a new task, called Analogy Detection and Extraction (AnaDE), which includes three synergistic sub-tasks: 1) detecting documents containing analogies, 2) extracting text segments that make up the analogy, and 3) identifying the source and target concepts being compared.To facilitate the study of this new task, we create a benchmark dataset by scraping Metamia.com and investigate the performances of state-of-the-art models on all sub-tasks to establish the first-generation benchmark results for this new task.We find that the Longformer model achieves the best performance on all three sub-tasks demonstrating its effectiveness for handling long texts.Moreover, smaller models fine-tuned on our dataset perform better than non-fine-tuned ChatGPT, suggesting high task difficulty.Overall, the models achieve a high performance on document detection suggesting that it could be used to develop applications like analogy search engines.Further, there is a large room for improvement on the segment and concept extraction tasks 1 .

Large Language Models (LLMs) deployed on edge devices learn through fine-tuning and updating a certain portion of their parameters. Although such learning methods can be optimized to reduce resource utilization, the overall required resources remain a heavy burden on edge devices. Instead, Retrieval-Augmented Generation (RAG), a resource-efficient LLM learning method, can improve the quality of the LLM-generated content without updating model parameters. However, the RAG-based LLM may involve repetitive searches on the profile data in every user-LLM interaction. This search can lead to significant latency along with the accumulation of user data. Conventional efforts to decrease latency result in restricting the size of saved user data, thus reducing the scalability of RAG as user data continuously grows. It remains an open question: how to free RAG from the constraints of latency and scalability on edge devices? In this paper, we propose a novel framework to accelerate RAG via Computing-in-Memory (CiM) architectures. It accelerates matrix multiplications by performing in-situ computation inside the memory while avoiding the expensive data transfer between the computing unit and memory. Our framework, Robust CiM-backed RAG (RoCR), utilizing a novel contrastive learning-based training method and noise-aware training, can enable RAG to efficiently search profile data with CiM. To the best of our knowledge, this is the first work utilizing CiM to accelerate RAG.

The past neural network design has largely focused on feature \textit{representation space} dimension and its capacity scaling (e.g., width, depth), but overlooked the feature \textit{interaction space} scaling. Recent advancements have shown shifted focus towards element-wise multiplication to facilitate higher-dimensional feature interaction space for better information transformation. Despite this progress, multiplications predominantly capture low-order interactions, thus remaining confined to a finite-dimensional interaction space. To transcend this limitation, classic kernel methods emerge as a promising solution to engage features in an infinite-dimensional space. We introduce InfiNet, a model architecture that enables feature interaction within an infinite-dimensional space created by RBF kernel. Our experiments reveal that InfiNet achieves new state-of-the-art, owing to its capability to leverage infinite-dimensional interactions, significantly enhancing model performance.

DNNs are rapidly evolving from streamlined single-modality single-task (SMST) to multi-modality multi-task (MMMT) with large variations for different layers and complex data dependencies among layers. To support such models, hardware systems also evolved to be heterogeneous. The heterogeneous system comes from the prevailing trend to integrate diverse accelerators into the system for lower latency. FPGAs have high computation density and communication bandwidth and are configurable to be deployed with different designs of accelerators, which are widely used for various machine-learning applications. However, scaling from SMST to MMMT on heterogeneous FPGAs is challenging since MMMT has much larger layer variations, a massive number of layers, and complex data dependency among different backbones. Previous mapping algorithms are either inefficient or over-simplified which makes them impractical in general scenarios. In this work, we propose CHEF to enable efficient implementation of MMMT models in realistic heterogeneous FPGA clusters, i.e. deploying heterogeneous accelerators on heterogeneous FPGAs (A2F) and mapping the heterogeneous DNNs on the deployed heterogeneous accelerators (M2A). We propose CHEF-A2F, a two-stage accelerators-to-FPGAs deployment approach to co-optimize hardware deployment and accelerator mapping. In addition, we propose CHEF-M2A, which can support general and practical cases compared to previous mapping algorithms. To the best of our knowledge, this is the first attempt to implement MMMT models in real heterogeneous FPGA clusters. Experimental results show that the latency obtained with CHEF is near-optimal while the search time is 10000X less than exhaustively searching the optimal solution.

We present a GPU solution for exact maximal clique enumeration (MCE) that performs a search tree traversal following the Bron-Kerbosch algorithm. Prior works on parallelizing MCE on GPUs perform a breadth-first traversal of the tree, which has limited scalability because of the explosion in the number of tree nodes at deep levels. We propose to parallelize MCE on GPUs by performing depth-first traversal of independent subtrees in parallel. Since MCE suffers from high load imbalance and memory capacity requirements, we propose a worker list for dynamic load balancing, as well as partial induced subgraphs and a compact representation of excluded vertex sets to regulate memory consumption. Our evaluation shows that our GPU implementation on a single GPU outperforms the state-of-the-art parallel CPU implementation by a geometric mean of 4.9× (up to 16.7×), and scales efficiently to multiple GPUs. Our code has been open-sourced to enable further research on accelerating MCE.

Graphics Processing Units (GPUs) have traditionally relied on the host CPU to initiate access to the data storage. This approach is well-suited for GPU applications with known data access patterns that enable partitioning of their dataset to be processed in a pipelined fashion in the GPU. However, emerging applications such as graph and data analytics, recommender systems, or graph neural networks, require fine-grained, data-dependent access to storage. CPU initiation of storage access is unsuitable for these applications due to high CPU-GPU synchronization overheads, I/O traffic amplification, and long CPU processing latencies. GPU-initiated storage removes these overheads from the storage control path and, thus, can potentially support these applications at much higher speed. However, there is a lack of systems architecture and software stack that enable efficient GPU-initiated storage access. This work presents a novel system architecture, BaM, that fills this gap. BaM features a fine-grained software cache to coalesce data storage requests while minimizing I/O traffic amplification. This software cache communicates with the storage system via high-throughput queues that enable the massive number of concurrent threads in modern GPUs to make I/O requests at a high rate to fully utilize the storage devices and the system interconnect. Experimental results show that BaM delivers 1.0x and 1.49x end-to-end speed up for BFS and CC graph analytics benchmarks while reducing hardware costs by up to 21.7x over accessing the graph data from the host memory. Furthermore, BaM speeds up data-analytics workloads by 5.3x over CPU-initiated storage access on the same hardware.

Efficient or near-zero-cost proxies were proposed recently to address the demanding computational issues of Neural Architecture Search (NAS) in designing deep neural networks (DNNs), where each candidate architecture network only requires one iteration of backpropagation. The values obtained from proxies are used as predictions of architecture performance for downstream tasks. However, two significant drawbacks hinder the wide adoption of these efficient proxies: (1) they are not adaptive to various NAS search spaces; and (2) they are not extensible to multi-modality downstream tasks. To address these two issues, we first propose an Extensible proxy (Eproxy) that utilizes self-supervised, few-shot training to achieve near-zero costs. A key component to our Eproxy’s efficiency is the introduction of a barrier layer with randomly initialized frozen convolution parameters, which adds non-linearities to the optimization spaces so that Eproxy can discriminate the performance of architectures at an early stage. We further propose a Discrete Proxy Search (DPS) method to find the optimized training settings for Eproxy with only a handful of benchmarked architectures on the target tasks. Our extensive experiments confirm the effectiveness of both Eproxy and DPS. On the NDS-ImageNet search spaces, Eproxy+DPS achieves a higher average ranking correlation (Spearman ρ = 0.73) than the previous efficient proxy (Spearman ρ = 0.56). On the NAS-Bench-Trans-Micro search spaces with seven tasks, Eproxy+DPS delivers comparable performance with the early stopping method (146× faster). For the end-to-end task such as DARTS-ImageNet-1k, our method delivers better results than NAS performed on CIFAR-10 while only requiring one GPU hour with a single batch of CIFAR-10 images. Our code is available at https://github.com/leeyeehoo/GenNAS-Zero.

BEEP is a state-of-the-art subgraph enumerator that delivers high performance through a combination of balanced, parallel GPU processing and novel algorithmic improvements. With a rapidly increasing demand for fast tools on large graphs, GPU-based subgraph enumerators are of growing interest. Most existing GPU enumerators are based on Breadth First Search (BFS), which often impose limitations on hardware resources due to excessive memory requirements. PARSEC [12] was the first GPU enumerator to adopt Depth First Search (DFS) that demonstrated impressive speedups and its adaptability to hardware with limited memory resources. However, PARSEC’s DFS implementation suffers from computational inefficiencies and load imbalances. BEEP introduces novel search space reduction techniques and load balancing strategies to tackle these challenges in DFS-based parallelization and achieves exceptional performance and scalability. Experimental results indicate that BEEP outperforms PARSEC with geometric mean speedups of up to 10.52 × across disparate data graphs and up to 7.28 × across various queries with maximum speedups of 33.46 ×. This makes BEEP the fastest subgraph enumerator to date. Furthermore, a multi-GPU implementation is developed that exhibits almost linear scalability with the number of devices.

Nowadays integrated circuits (ICs) are underpinning all major information technology innovations including the current trends of artificial intelligence (AI). Modern IC designs often involve analyses of complex phenomena (such as timing, noise, and power etc.) for tens of billions of electronic components, like resistance (R), capacitance (C), transistors and gates, interconnected in various complex structures. Those analyses often need to strike a balance between accuracy and speed as those analyses need to be carried out many times throughout the entire IC design cycles. With the advancement of AI, researchers also start to explore news ways in leveraging AI to improve those analyses. This paper focuses on one of the most important analyses, timing analysis for interconnects. Since IC interconnects can be represented as an RC-tree, a specialized graph as tree, we design a novel tree-based graph neural network, SyncTREE, to speed up the timing analysis by incorporating both the structural and physical properties of electronic circuits. Our major innovations include (1) a two-pass message-passing (bottom-up and top-down) for graph embedding, (2) a tree contrastive loss to guide learning, and (3) a closed formular-based approach to conduct fast timing. Our experiments show that, compared to conventional GNN models, SyncTREE achieves the best timing prediction in terms of both delays and slews, all in reference to the industry golden numerical analyses results on real IC design data.

Analogies inspire creative solutions to problems, and facilitate the creative expression of ideas and the explanation of complex concepts. They have widespread applications in scientific innovation, creative writing, and education. The ability to discover creative analogies that are not explicitly mentioned but can be inferred from the web is highly desirable to power all such applications dynamically and augment human creativity. Recently, Large Pre-trained Language Models (PLMs), trained on massive Web data, have shown great promise in generating mostly known analogies that are explicitly mentioned on the Web. However, it is unclear how they could be leveraged for mining creative analogies not explicitly mentioned on the Web. We address this challenge and propose Creative Analogy Mining (CAM), a novel framework for mining creative analogies, which consists of the following three main steps: 1) Generate analogies using PLMs with effectively designed prompts, 2) Evaluate their quality using scoring functions, and 3) Refine the low-quality analogies by another round of prompt-based generation. We propose both unsupervised and supervised instantiations of the framework so that it can be used even without any annotated data. Based on human evaluation using Amazon Mechanical Turk, we find that our unsupervised framework can mine 13.7% highly-creative and 56.37% somewhat-creative analogies. Moreover, our supervised scores are generally better than the unsupervised ones and correlate moderately with human evaluators, indicating that they would be even more effective at mining creative analogies. These findings also shed light on the creativity of PLMs 1.

Quantization for Convolutional Neural Network (CNN) has shown significant progress with the intention of reducing the cost of computation and storage with low-bitwidth data inputs. There are, however, no systematic studies on how an existing full-bitwidth processing unit, such as CPUs and DSPs, can be better utilized to carry out significantly higher computation throughput for convolution under various quantized bitwidths. In this study, we propose HiKonv, a unified solution that maximizes the compute throughput of a given underlying processing unit to process low-bitwidth quantized data inputs through novel bitwise parallel computation. We establish theoretical performance bounds using a full-bitwidth multiplier for highly parallelized low-bitwidth convolution, and demonstrate new breakthroughs for high-performance computing in this critical domain. For example, a single 32-bit processing unit can deliver 128 binarized convolution operations (multiplications and additions) under one CPU instruction, and a single$27\times 18$DSP core can deliver eight convolution operations with 4-bit inputs in one cycle. We demonstrate the effectiveness of HiKonv on CPU and FPGA for both convolutional layers or a complete DNN model. For a convolutional layer quantized to 4-bit, HiKonv achieves a$3.17\times$latency improvement over the baseline implementation using C++ on CPU. Compared to the DAC-SDC 2020 champion model for FPGA, HiKonv achieves a$2.37\times$: throughput improvement and$2.61\times$DSP efficiency improvement, respectively.

Can machines know what twin prime is?From the composition of this phrase, machines may guess twin prime is a certain kind of prime, but it is still difficult to deduce exactly what twin stands for without additional knowledge.Here, twin prime is a jargon-a specialized term used by experts in a particular field.Explaining jargon is challenging since it usually requires domain knowledge to understand.Recently, there is an increasing interest in extracting and generating definitions of words automatically.However, existing approaches, either extraction or generation, perform poorly on jargon.In this paper, we propose to combine extraction and generation for jargon definition modeling: first extract self-and correlative definitional information of target jargon from the Web and then generate the final definitions by incorporating the extracted definitional information.Our framework is remarkably simple but effective: experiments demonstrate our method can generate high-quality definitions for jargon and outperform state-of-the-art models significantly, e.g., BLEU score from 8.76 to 22.66 and human-annotated score from 2.34 to 4.04. 1

We propose DEER (Descriptive Knowledge Graph for Explaining Entity Relationships)an open and informative form of modeling entity relationships.In DEER, relationships between entities are represented by free-text relation descriptions.For instance, the relationship between entities of machine learning and algorithm can be represented as "Machine learning explores the study and construction of algorithms that can learn from and make predictions on data."To construct DEER, we propose a self-supervised learning method to extract relation descriptions with the analysis of dependency patterns and generate relation descriptions with a transformer-based relation description synthesizing model, where no human labeling is required.Experiments demonstrate that our system can extract and generate highquality relation descriptions for explaining entity relationships.The results suggest that we can build an open and informative knowledge graph without human annotation.

Graph convolutional networks (GCNs) have recently achieved great empirical success in learning graph-structured data. To address its scalability issue due to the recursive embedding of neighboring features, graph topology sampling has been proposed to reduce the memory and computational cost of training GCNs, and it has achieved comparable test performance to those without topology sampling in many empirical studies. To the best of our knowledge, this paper provides the first theoretical justification of graph topology sampling in training (up to) three-layer GCNs for semi-supervised node classification. We formally characterize some sufficient conditions on graph topology sampling such that GCN training leads to diminishing generalization error. Moreover, our method tackles the non-convex interaction of weights across layers, which is under-explored in the existing theoretical analyses of GCNs. This paper characterizes the impact of graph structures and topology sampling on the generalization performance and sample complexity explicitly, and the theoretical findings are also justified through numerical experiments.

Counting k-cliques in a graph is an important problem in graph analysis with many applications such as community detection and graph partitioning. Counting k-cliques is typically done by traversing search trees starting at each vertex in the graph. Parallelizing k-clique counting has been well-studied on CPUs and many solutions exist. However, there are no performant solutions for k-clique counting on GPUs.

Subgraph enumeration is an important problem in the field of Graph Analytics with numerous applications. The problem is provably NP-complete and requires sophisticated heuristics and highly efficient implementations to be feasible on problem sizes of realistic scales. Parallel solutions have shown a lot of promise on CPUs and distributed environments. Recently, GPU-based parallel solutions have also been proposed to take advantage of the massive execution resources in modern GPUs. Subgraph enumeration involves traversing a search tree for each vertex of the data graph to find matches of a query in a graph. Most GPU-based solutions traverse the tree in breadth-first manner that exploits parallelism at the cost of high memory requirement and presents a formidable challenge for processing large graphs with high-degree vertices since the memory capacity of GPUs is significantly lower than that of CPUs. In this work, we propose a novel GPU solution based on a hybrid BFS and DFS approach where the top level(s) of the search trees are traversed in a fully parallel, breadth-first manner while each subtree is traversed in a more space-efficient, depth-first manner. The depth-first traversal of subtrees requires less memory but presents more challenges for parallel execution. To overcome the less parallel nature of depth-first traversal, we exploit fine-grained parallelism in each step of the depth-first traversal of sub-trees. We further identify and implement various optimizations to efficiently utilize memory and compute resources of the GPUs. We evaluate our performance in comparison with the state-of-the-art GPU and CPU implementations. We outperform the GPU and CPU implementations with a geometric mean speedup of 9.47× (up to 92.01×) and 2.37× (up to 12.70×), respectively. We also show that the proposed approach can efficiently process the graphs that previously cannot be processed by the state-of-the-art GPU solutions due to their excessive memory requirement.

Graph Neural Networks (GNNs) have shown success in learning from graph-structured data, with applications to fraud detection, recommendation, and knowledge graph reasoning. However, training GNN efficiently is challenging because: 1) GPU memory capacity is limited and can be insufficient for large datasets, and 2) the graph-based data structure causes irregular data access patterns. In this work, we provide a method to statistically analyze and identify more frequently accessed data ahead of GNN training. Our data tiering method not only utilizes the structure of input graph, but also an insight gained from actual GNN training process to achieve a higher prediction result. With our data tiering method, we additionally provide a new data placement and access strategy to further minimize the CPU-GPU communication overhead. We also take into account of multi-GPU GNN training as well and we demonstrate the effectiveness of our strategy in a multi-GPU system. The evaluation results show that our work reduces CPU-GPU traffic by 87-95% and improves the training speed of GNN over the existing solutions by 1.6-2.1x on graphs with hundreds of millions of nodes and billions of edges.

With the advent of big data across multiple high-impact applications, we are often facing the challenge of complex heterogeneity. The newly collected data usually consist of multiple modalities and are characterized with multiple labels, thus exhibiting the co-existence of multiple types of heterogeneity. Although state-of-the-art techniques are good at modeling the complex heterogeneity with sufficient label information, such label information can be quite expensive to obtain in real applications. Recently, researchers pay great attention to contrastive learning due to its prominent performance by utilizing rich unlabeled data. However, existing work on contrastive learning is not able to address the problem of false-negative pairs, i.e., some 'negative' pairs may have similar representations if they have the same label. To overcome the issues, in this paper, we propose a unified heterogeneous learning framework, which combines both the weighted unsupervised contrastive loss and the weighted supervised contrastive loss to model multiple types of heterogeneity. We first provide a theoretical analysis showing that the vanilla contrastive learning loss easily leads to the sub-optimal solution in the presence of false-negative pairs, whereas the proposed weighted loss could automatically adjust the weight based on the similarity of the learned representations to mitigate this issue. Experimental results on real-world data sets demonstrate the effectiveness and the efficiency of the proposed framework modeling multiple types of heterogeneity.

Yong Xie, Dakuo Wang, Pin-Yu Chen, Jinjun Xiong, Sijia Liu, Oluwasanmi Koyejo. Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2022.

Acceleration of deep neural network (DNN) inference has gained increasing attention recently with the wide adoption of DNNs for practical applications. For computer vision tasks where inputs are images, existing works mostly focus on improving the throughput of inference for multiple images. However, in many real-time applications, it is critical to reduce the latency of a single image inference, which is more complicated than improving the throughput because of the inherent data dependencies. On the other hand, from human brain's perspective, the complexity in our visual surroundings is first encoded as a pattern of light on a two dimensional array of photoreceptors, with little direct resemblance to the original input or the ultimate percept. Within just a few hundred microns of retinal thickness, this initial signal encoded by our photoreceptors must be transformed into an adequate representation of the entire visual scene. Inspired by how the retina helps human brain incept new information efficiently, we present an end-to-end structured framework built using any existing convolutional neural network (CNN) as the backbone. The proposed framework, called VisualNet, can create task parallelism for the backbone during the inference of a single image. Experiments using a number of neural networks for the ImageNet classification task and the CIFAR-10 classification task on GPUs and CPUs show that the proposed VisualNet reduces the latency of the regular network it builds on by up to 80.6% when both are fully parallelized with state-of-the-art acceleration libraries. At the same time, VisualNet can achieve similar or slightly higher accuracy.

Deep neural network (DNN)-based video analysis has become one of the most essential and challenging tasks to capture implicit information from video streams. Although DNNs significantly improve the analysis quality, they introduce intensive compute and memory demands and require dedicated hardware for efficient processing. The customized heterogeneous system is one of the promising solutions with general-purpose processors (CPUs) and specialized processors (DNN Accelerators). Among various heterogeneous systems, the combination of CPU and FPGA has been intensively studied for DNN inference with improved latency and energy consumption compared to CPU + GPU schemes and with increased flexibility and reduced time-to-market cost compared to CPU + ASIC designs. However, deploying DNN-based video analysis on CPU + FPGA systems still presents challenges from the tedious RTL programming, the intricate design verification, and the time-consuming design space exploration. To address these challenges, we present a novel framework, called EcoSys, to explore co-design and optimization opportunities on CPU-FPGA heterogeneous systems for accelerating video analysis. Novel technologies include 1) a coherent memory space shared by the host and the customized accelerator to enable efficient task partitioning and online DNN model refinement with reduced data transfer latency; 2) an end-to-end design flow that supports high-level design abstraction and allows rapid development of customized hardware accelerators from Python-based DNN descriptions; 3) a design space exploration (DSE) engine that determines the design space and explores the optimized solutions by considering the targeted heterogeneous system and user-specific constraints; and 4) a complete set of co-optimization solutions, including a layer-based pipeline, a feature map partition scheme, and an efficient memory hierarchical design for the accelerator and multithreading programming for the CPU. In this article, we demonstrate our design framework to accelerate the long-term recurrent convolution network (LRCN), which analyzes the input video and output one semantic caption for each frame. EcoSys can deliver 314.7 and 58.1 frames/s by targeting the LRCN model with AlexNet and VGG-16 backbone, respectively. Compared to the multithreaded CPU and pure FPGA design, EcoSys achieves$20.6\times $and$5.3\times $higher throughput performance.

Jie Huang, Kevin Chang, JinJun Xiong, Wen-mei Hwu. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2021.

Along with the development of AI democratization, the machine learning approach, in particular neural networks, has been applied to wide-range applications. In different application scenarios, the neural network will be accelerated on the tailored computing platform. The acceleration of neural networks on classical computing platforms, such as CPU, GPU, FPGA, ASIC, has been widely studied; however, when the scale of the application consistently grows up, the memory bottleneck becomes obvious, widely known as memory-wall. In response to such a challenge, advanced quantum computing, which can represent 2N states with N quantum bits (qubits), is regarded as a promising solution. It is imminent to know how to design the quantum circuit for accelerating neural networks. Most recently, there are initial works studying how to map neural networks to actual quantum processors. To better understand the state-of-the-art design and inspire new design methodology, this paper carries out a case study to demonstrate an end-to-end implementation. On the neural network side, we employ the multilayer perceptron to complete image classification tasks using the standard and widely used MNIST dataset. On the quantum computing side, we target IBM Quantum processors, which can be programmed and simulated by using IBM Qiskit. This work targets the acceleration of the inference phase of a trained neural network on the quantum processor. Along with the case study, we will demonstrate the typical procedure for mapping neural networks to quantum circuits.

As Federated Learning (FL) has been widely used for collaborative training, a considerable computational straggler issue emerged: when FL deploys identical neural network models to heterogeneous devices, the ones with weak computational capacities, referred to as stragglers, may significantly delay the synchronous parameter aggregation. Although discarding stragglers from the collaboration can relieve this issue to a certain extent, stragglers may keep unique and critical information learned from the non-identical dataset, and directly discarding will harm the overall collaboration performance. Therefore, in this paper, we propose Helios – a heterogeneity-aware FL framework to tackle the straggler issue. Helios identifies individual devices’ heterogeneous training capability, and therefore the expected neural network model training volumes regarding the collaborative training pace. For straggling devices, a “softtraining” method is proposed to dynamically compress the original identical training model into the expected volume through a rotated neuron training approach. With extensive algorithm analysis and optimization schemes, stragglers can be accelerated while retaining the convergence for local training as well as federated collaboration. Experiments show that Helios can provide up to $2.5\times$ training acceleration and maximum 4.64% convergence accuracy improvement in various collaboration settings.

MPI derived datatypes are an abstraction that simplifies handling of non-contiguous data in MPI applications. These datatypes are recursively constructed at runtime from primitive Named Types defined in the MPI standard. More recently, the development and deployment of CUDA-aware MPI implementations has encouraged the transition of distributed high-performance MPI codes to use GPUs. Such implementations allow MPI functions to directly operate on GPU buffers, easing integration of GPU compute into MPI codes. This work first presents a novel datatype handling strategy for nested strided datatypes, which finds a middle ground between the specialized or generic handling in prior work. This work also shows that the performance characteristics of non-contiguous data handling can be modeled with empirical system measurements, and used to transparently improve MPI_Send/Recv latency. Finally, despite substantial attention to non-contiguous GPU data and CUDA-aware MPI implementations, good performance cannot be taken for granted. This work demonstrates its contributions through an MPI interposer library, TEMPI. TEMPI can be used with existing MPI deployments without system or application changes. Ultimately, the interposed-library model of this work demonstrates MPI_Pack speedup of up to 242000x and MPI_Send speedup of up to 59000x compared to the MPI implementation deployed on a leadership-class supercomputer. This yields speedup of more than 917x in a 3D halo exchange with 3072 processes.

We study the problem of concept induction in visual reasoning, i.e., identifying concepts and their hierarchical relationships from question-answer pairs associated with images; and achieve an interpretable model via working on the induced symbolic concept space. To this end, we first design a new framework named object-centric compositional attention model (OCCAM) to perform the visual reasoning task with object-level visual features. Then, we come up with a method to induce concepts of objects and relations using clues from the attention patterns between objects’ visual features and question words. Finally, we achieve a higher level of interpretability by imposing OCCAM on the objects represented in the induced symbolic concept space. Experiments on the CLEVR and GQA datasets demonstrate: 1) our OCCAM achieves a new state of the art without human-annotated functional programs; 2) our induced concepts are both accurate and sufficient as OCCAM achieves an on-par performance on objects represented either in visual features or in the induced symbolic concept space.

Prosody plays an important role in characterizing the style of a speaker or an emotion, but most non-parallel voice or emotion style transfer algorithms do not convert any prosody information. Two major components of prosody are pitch and rhythm. Disentangling the prosody information, particularly the rhythm component, from the speech is challenging because it involves breaking the synchrony between the input speech and the disentangled speech representation. As a result, most existing prosody style transfer algorithms would need to rely on some form of text transcriptions to identify the content information, which confines their application to high-resource languages only. Recently, SpeechSplit has made sizeable progress towards unsupervised prosody style transfer, but it is unable to extract high-level global prosody style in an unsupervised manner. In this paper, we propose AutoPST, which can disentangle global prosody style from speech without relying on any text transcriptions. AutoPST is an Autoencoder-based Prosody Style Transfer framework with a thorough rhythm removal module guided by the self-expressive representation learning. Experiments on different style transfer tasks show that AutoPST can effectively convert prosody that correctly reflects the styles of the target domains.

Most existing neural architecture search (NAS) algorithms are dedicated to and evaluated by the downstream tasks, e.g., image classification in computer vision. However, extensive experiments have shown that, prominent neural architectures, such as ResNet in computer vision and LSTM in natural language processing, are generally good at extracting patterns from the input data and perform well on different downstream tasks. In this paper, we attempt to answer two fundamental questions related to NAS. (1) Is it necessary to use the performance of specific downstream tasks to evaluate and search for good neural architectures? (2) Can we perform NAS effectively and efficiently while being agnostic to the downstream tasks? To answer these questions, we propose a novel and generic NAS framework, termed Generic NAS (GenNAS). GenNAS does not use task-specific labels but instead adopts regression on a set of manually designed synthetic signal bases for architecture evaluation. Such a self-supervised regression task can effectively evaluate the intrinsic power of an architecture to capture and transform the input signal patterns, and allow more sufficient usage of training samples. Extensive experiments across 13 CNN search spaces and one NLP space demonstrate the remarkable efficiency of GenNAS using regression, in terms of both evaluating the neural architectures (quantified by the ranking correlation Spearman's rho between the approximated performances and the downstream task performances) and the convergence speed for training (within a few seconds). For example, on NAS-Bench-101, GenNAS achieves 0.85 rho while the existing efficient methods only achieve 0.38. We then propose an automatic task search to optimize the combination of synthetic signals using limited downstream-task-specific labels, further improving the performance of GenNAS. We also thoroughly evaluate GenNAS's generality and end-to-end NAS performance on all search spaces, which outperforms almost all existing works with significant speedup. For example, on NASBench-201, GenNAS can find near-optimal architectures within 0.3 GPU hour.

The lottery ticket hypothesis (LTH) states that learning on a properly pruned network (the winning ticket) has improved test accuracy over the original unpruned network. Although LTH has been justified empirically in a broad range of deep neural network (DNN) involved applications like computer vision and natural language processing, the theoretical validation of the improved generalization of a winning ticket remains elusive. To the best of our knowledge, our work, for the first time, characterizes the performance of training a pruned neural network by analyzing the geometric structure of the objective function and the sample complexity to achieve zero generalization error. We show that the convex region near a desirable model with guaranteed generalization enlarges as the neural network model is pruned, indicating the structural importance of a winning ticket. Moreover, as the algorithm for training a pruned neural network is specified as an (accelerated) stochastic gradient descent algorithm, we theoretically show that the number of samples required for achieving zero generalization error is proportional to the number of the non-pruned weights in the hidden layer. With a fixed number of samples, training a pruned neural network enjoys a faster convergence rate to the desired model than training the original unpruned one, providing a formal justification of the improved generalization of the winning ticket. Our theoretical results are acquired from learning a pruned neural network of one hidden layer, while experimental results are further provided to justify the implications in pruning multi-layer neural networks.

Phrase mining is one of the fundamental NLP tasks that can have significant impact on the efficacy of many downstream applications.Many supervised and unsupervised phrase mining approaches have been proposed.Some rely on linguistic analyzers, and others are language agnostic.A daunting challenge in this task is to distinguish quality phrases from noise phrases, which tightly coexists with quality phrases in the entire frequency spectrum.Most existing approaches to phrase mining, however, rely on frequency-based statistics, hence suffer from quality loss.In this paper, we propose an unsupervised phrase mining framework, "PhraseScope", which consists of a sequence of filters, namely cohesion, domain, and graph filters, to remove noise phrase.Each filter is responsible for removing noise phrase of particular characteristics.Collectively, our proposed filters are capable of detecting and removing noise phrases effectively while preserving quality phrases.Our results show significant improvement in both recall and precision over state-of-the-art frameworks when tested on three different domains of datasets.

Graph Convolutional Networks (GCNs) are increasingly adopted in large-scale graph-based recommender systems. Training GCN requires the minibatch generator traversing graphs and sampling the sparsely located neighboring nodes to obtain their features. Since real-world graphs often exceed the capacity of GPU memory, current GCN training systems keep the feature table in host memory and rely on the CPU to collect sparse features before sending them to the GPUs. This approach, however, puts tremendous pressure on host memory bandwidth and the CPU. This is because the CPU needs to (1) read sparse features from memory, (2) write features into memory as a dense format, and (3) transfer the features from memory to the GPUs. In this work, we propose a novel GPU-oriented data communication approach for GCN training, where GPU threads directly access sparse features in host memory through zero-copy accesses without much CPU help. By removing the CPU gathering stage, our method significantly reduces the consumption of the host resources and data access latency. We further present two important techniques to achieve high host memory access efficiency by the GPU: (1) automatic data access address alignment to maximize PCIe packet efficiency, and (2) asynchronous zero-copy access and kernel execution to fully overlap data transfer with training. We incorporate our method into PyTorch and evaluate its effectiveness using several graphs with sizes up to 111 million nodes and 1.6 billion edges. In a multi-GPU training setup, our method is 65--92% faster than the conventional data transfer method, and can even match the performance of all-in-GPU-memory training for some graphs that fit in GPU memory.

We analyze the learning problem of one-hidden-layer nonoverlapping convolutional neural networks with the rectified linear unit (ReLU) activation function from the perspective of model estimation. The training outputs are assumed to be generated by the neural network with the unknown ground-truth parameters plus some additive noise, and the objective is to estimate the model parameters by minimizing a nonconvex squared loss function of the training data. Assuming that the training set contains a finite number of samples generated from the Gaussian distribution, we prove that the accelerated gradient descent (GD) algorithm with a proper initialization converges to the ground-truth parameters (up to the noise level) with a linear rate even though the learning problem is nonconvex. Moreover, the convergence rate is proved to be faster than the vanilla GD. The initialization can be achieved by the existing tensor initialization method. In contrast to the existing works that assume an infinite number of samples, we theoretically establish the sample complexity of the required number of training samples. Although the neural network considered here is not deep, this is the first work to show that accelerated GD algorithms can find the global optimizer of the nonconvex learning problem of neural networks. This is also the first work that characterizes the sample complexity of gradient-based methods in learning convolutional neural networks with the nonsmooth ReLU activation function. This work also provides the tightest bound so far of the estimation error with respect to the output noise.

Neural machine translation (NMT) is one of the most critical applications in natural language processing (NLP) with the main idea of converting text in one language to another using deep neural networks. In recent year, we have seen continuous development of NMT by integrating more emerging technologies, such as bidirectional gated recurrent units (GRU), attention mechanisms, and beam-search algorithms, for improved translation quality. However, with the increasing problem size, the real-life NMT models have become much more complicated and difficult to implement on hardware for acceleration opportunities. In this article, we aim to exploit the capability of FPGAs to deliver highly efficient implementations for real-life NMT applications. We map the inference of a large-scale NMT model with total computation of 172 GFLOP to a highly optimized high-level synthesis (HLS) IP and integrate the IP into Xilinx VCU118 FPGA platform. The model has widely used key features for NMTs, including the bidirectional GRU layer, attention mechanism, and beam search. We quantize the model to mixed-precision representation in which parameters and portions of calculations are in 16-bit half precision, and others remain as 32-bit floating-point. Compared to the float NMT implementation on FPGA, we achieve 13.1× speedup with an end-to-end performance of 22.0 GFLOPS without any accuracy degradation. Based on our knowledge, this is the first work that successfully implements a real-life end-to-end NMT model to an FPGA on board.

The current Deep Learning (DL) landscape is fast-paced and is rife with non-uniform models, hardware/software (HW/SW) stacks. Currently, there is no DL benchmarking platform to facilitate the evaluation and comparison of DL innovations, be it models, frameworks, libraries, or hardware. As a result, the current practice of evaluating the benefits of proposed DL innovations is both arduous and error-prone - stifling the adoption of the innovations. In this work, we first identify 10 design features that are desirable within a DL benchmarking platform. These features include: performing the evaluation in a consistent, reproducible, and scalable manner, being framework and hardware agnostic, supporting real-world benchmarking workloads, providing in-depth model execution inspection across the HW/SW stack levels, etc. We then propose MLModelScope, a DL benchmarking platform that realizes these 10 design objectives. MLModelScope introduces a specification to define DL model evaluations and provides a runtime to provision the evaluation workflow using the user-specified HW/SW stack. MLModelScope defines abstractions for frameworks and supports the board range of DL models and evaluation scenarios. We implement MLModelScope as an open-source project with support for all major frameworks and hardware architectures. Through MLModelScope's evaluation and automated analysis workflows, we perform a case-study analysis of 37 models across 4 systems and show how model, hardware, and framework selection affects model accuracy and performance under different benchmarking scenarios. We further demonstrate how MLModelScope's tracing capability gives a holistic view of model execution and helps pinpoint bottlenecks.

The ability to match pieces of code to their corresponding natural language descriptions and vice versa is fundamental for natural language search interfaces to software repositories.In this paper, we propose a novel multiperspective cross-lingual neural framework for code-text matching, inspired in part by a previous model for monolingual text-to-text matching, to capture both global and local similarities.Our experiments on the CoNaLa dataset show that our proposed model yields better performance on this cross-lingual text-to-code matching task than previous approaches that map code and text to a single joint embedding space.

We consider the problem of unsupervised domain adaptation for semantic segmentation by easing the domain shift between the source domain (synthetic data) and the target domain (real data) in this work. State-of-the-art approaches prove that performing semantic-level alignment is helpful in tackling the domain shift issue. Based on the observation that stuff categories usually share similar appearances across images of different domains while things (i.e. object instances) have much larger differences, we propose to improve the semantic-level alignment with different strategies for stuff regions and for things: 1) for the stuff categories, we generate feature representation for each class and conduct the alignment operation from the target domain to the source domain; 2) for the thing categories, we generate feature representation for each individual instance and encourage the instance in the target domain to align with the most similar one in the source domain. In this way, the individual differences within thing categories will also be considered to alleviate over-alignment. In addition to our proposed method, we further reveal the reason why the current adversarial loss is often unstable in minimizing the distribution discrepancy and show that our method can help ease this issue by minimizing the most similar stuff and instance features between the source and the target domains. We conduct extensive experiments in two unsupervised domain adaptation tasks, i.e. GTA5 → Cityscapes and SYNTHIA → Cityscapes, and achieve the new state-of-the-art segmentation accuracy.

High quality AI solutions require joint optimization of AI algorithms and their hardware implementations. In this work, we are the first to propose a fully simultaneous, Efficient Differentiable DNN (deep neural network) architecture and implementation co-search (EDD) methodology. We formulate the co-search problem by fusing DNN search variables and hardware implementation variables into one solution space, and maximize both algorithm accuracy and hardware implementation quality. The formulation is differentiable with respect to the fused variables, so that gradient descent algorithm can be applied to greatly reduce the search time. The formulation is also applicable for various devices with different objectives. In the experiments, we demonstrate the effectiveness of our EDD methodology by searching for three representative DNNs, targeting low-latency GPU implementation and FPGA implementations with both recursive and pipelined architectures. Each model produced by EDD achieves similar accuracy as the best existing DNN models searched by neural architecture search (NAS) methods on ImageNet, but with superior performance obtained within 12 GPU-hour searches. Our DNN targeting GPU is 1.40× faster than the state-of-the-art solution reported in Proxyless [1], and our DNN targeting FPGA delivers 1.45× higher throughput than the state-of-the-art solution reported in DNNBuilder [2].

We introduce and study semantic capacity of terms.For example, the semantic capacity of artificial intelligence is higher than that of linear regression since artificial intelligence possesses a broader meaning scope.Understanding semantic capacity of terms will help many downstream tasks in natural language processing.For this purpose, we propose a two-step model to investigate semantic capacity of terms, which takes a large text corpus as input and can evaluate semantic capacity of terms if the text corpus can provide enough cooccurrence information of terms.Extensive experiments in three fields demonstrate the effectiveness and rationality of our model compared with well-designed baselines and human-level evaluations.

High quality AI solutions require joint optimization of AI algorithms, such as deep neural networks (DNNs), and their hardware accelerators. To improve the overall solution quality as well as to boost the design productivity, efficient algorithm and accelerator co-design methodologies are indispensable. In this paper, we first discuss the motivations and challenges for the Algorithm/Accelerator co-design problem, and then provide several effective solutions. Especially, we highlight three leading works of effective co-design methodologies: 1) the first simultaneous DNN/FPGA co-design method; 2) a bi-directional light weight DNN and accelerator co-design method; 3) a differentiable and efficient DNN and accelerator co-search method. We demonstrate the effectiveness of the proposed co-design approaches using extensive experiments on both FPGAs and GPUs, with comparisons to existing works. This paper emphasizes the importance and efficacy of algorithm-accelerator co-design, and calls for more research breakthroughs in this interesting and demanding area.

The arrival of 5G together with advances in artificial intelligence, machine learning, cloud computing, virtualization, and service orchestration have created a ubiquitous computing model at the network edge, enabling a host of new, AI driven edge computing applications. Although edge computing shares many characteristics of cloud computing, there are unique challenges for edge computing to meet the ever growing demands for scalability, security and multi-tenancy, especially in the upcoming 5G era. These challenges are discussed through two typical edge computing use cases: streaming video analytics and industrial IoT. A number of open research problems are discussed to call for help from the design automation community with the focus on new automation methodologies in building a cloud-native end-to-end edge computing platform.

Existing FPGA-based DNN accelerators typically fall into two design paradigms. Either they adopt a generic reusable architecture to support different DNN networks but leave some performance and efficiency on the table because of the sacrifice of design specificity. Or they apply a layer-wise tailor-made architecture to optimize layer-specific demands for computation and resources but loose the scalability of adaptation to a wide range of DNN networks. To overcome these drawbacks, this paper proposes a novel FPGA-based DNN accelerator design paradigm and its automation tool, called DNNExplorer, to enable fast exploration of various accelerator designs under the proposed paradigm and deliver optimized accelerator architectures for existing and emerging DNN networks. Three key techniques are essential for DNNExplorer's improved performance, better specificity, and scalability, including (1) a unique accelerator design paradigm with both high-dimensional design space support and fine-grained adjustability, (2) a dynamic design space to accommodate different combinations of DNN workloads and targeted FPGAs, and (3) a design space exploration (DSE) engine to generate optimized accelerator architectures following the proposed paradigm by simultaneously considering both FPGAs' computation and memory resources and DNN networks' layer-wise characteristics and overall complexity. Experimental results show that, for the same FPGAs, accelerators generated by DNNExplorer can deliver up to 4.2x higher performances (GOP/s) than the state-of-the-art layer-wise pipelined solutions generated by DNNBuilder [1] for VGG-like DNN with 38 CONV layers. Compared to accelerators with generic reusable computation units, DNNExplorer achieves up to 2.0x and 4.4x DSP efficiency improvement than a recently published accelerator design from academia (HybridDNN [2]) and a commercial DNN accelerator IP (Xilinx DPU [3]), respectively.

Although graph neural networks (GNNs) have made great progress recently on learning from graph-structured data in practice, their theoretical guarantee on generalizability remains elusive in the literature. In this paper, we provide a theoretically-grounded generalizability analysis of GNNs with one hidden layer for both regression and binary classification problems. Under the assumption that there exists a ground-truth GNN model (with zero generalization error), the objective of GNN learning is to estimate the ground-truth GNN parameters from the training data. To achieve this objective, we propose a learning algorithm that is built on tensor initialization and accelerated gradient descent. We then show that the proposed learning algorithm converges to the ground-truth GNN model for the regression problem, and to a model sufficiently close to the ground-truth for the binary classification problem. Moreover, for both cases, the convergence rate of the proposed learning algorithm is proven to be linear and faster than the vanilla gradient descent algorithm. We further explore the relationship between the sample complexity of GNNs and their underlying graph properties. Lastly, we provide numerical experiments to demonstrate the validity of our analysis and the effectiveness of the proposed learning algorithm for GNNs.

There has been a rapid proliferation of machine learning/deep learning (ML) models and wide adoption of them in many application domains. This has made profiling and characterization of ML model performance an increasingly pressing task for both hardware designers and system providers, as they would like to offer the best possible system to serve ML models with the target latency, throughput, cost, and energy requirements while maximizing resource utilization. Such an endeavor is challenging as the characteristics of an ML model depend on the interplay between the model, framework, system libraries, and the hardware (or the HW/SW stack). Existing profiling tools are disjoint, however, and only focus on profiling within a particular level of the stack, which limits the thoroughness and usefulness of the profiling results.This paper proposes XSP - an across-stack profiling design that gives a holistic and hierarchical view of ML model execution. XSP leverages distributed tracing to aggregate and correlate profile data from different sources. XSP introduces a leveled and iterative measurement approach that accurately captures the latencies at all levels of the HW/SW stack in spite of the profiling overhead. We couple the profiling design with an automated analysis pipeline to systematically analyze 65 state-of-the-art ML models. We demonstrate that XSP provides insights which would be difficult to discern otherwise.

As Deep Learning (DL) models have been increasingly used in latency-sensitive applications, there has been a growing interest in improving their response time. An important venue for such improvement is to profile the execution of these models and characterize their performance to identify possible optimization opportunities. However, the current profiling tools lack the highly desired abilities to characterize ideal performance, identify sources of inefficiency, and quantify the benefits of potential optimizations. Such deficiencies have led to slow characterization/optimization cycles that cannot keep up with the fast pace at which new DL models are introduced.We propose Benanza, a sustainable and extensible benchmarking and analysis design that speeds up the characterization/optimization cycle of DL models on GPUs. Benanza consists of four major components: a model processor that parses models into an internal representation, a configurable benchmark generator that automatically generates micro-benchmarks given a set of models, a database of benchmark results, and an analyzer that computes the "lower-bound" latency of DL models using the benchmark data and informs optimizations of model execution. The "lower-bound" latency metric estimates the ideal model execution on a GPU system and serves as the basis for identifying optimization opportunities in frameworks or system libraries. We used Benanza to evaluate 30 ONNX models in MXNet, ONNX Runtime, and PyTorch on 7 GPUs ranging from Kepler to the latest Turing, and identified optimizations in parallel layer execution, cuDNN convolution algorithm selection, framework inefficiency, layer fusion, and using Tensor Cores.

The need for higher energy efficiency has resulted in the proliferation of accelerators across platforms, with custom and reconfigurable accelerators adopted in both edge devices and cloud servers. However, existing solutions fall short in providing accelerators with low-latency, high-bandwidth access to the working set and suffer from the high latency and energy cost of data transfers. Such costs can severely limit the smallest granularity of the tasks that can be accelerated and thus the applicability of the accelerators. In this work, we present FReaC Cache, a novel architecture that natively supports reconfigurable computing in the last level cache (LLC), thereby giving energy-efficient accelerators low-latency, high-bandwidth access to the working set. By leveraging the cache's existing dense memory arrays, buses, and logic folding, we construct a reconfigurable fabric in the LLC with minimal changes to the system, processor, cache, and memory architecture. FReaC Cache is a low-latency, low-cost, and low-power alternative to off-die/offchip accelerators, and a flexible, and low-cost alternative to fixed function accelerators. We demonstrate an average speedup of 3X and Perf/W improvements of 6.1X over an edge-class multi-core CPU, and add 3.5% to 15.3% area overhead per cache slice.

The past few years have seen a surge of applying Deep Learning (DL) models for a wide array of tasks such as image classification, object detection, machine translation, etc. While DL models provide an opportunity to solve otherwise intractable tasks, their adoption relies on them being optimized to meet target latency and resource requirements. Benchmarking is a key step in this process but has been hampered in part due to the lack of representative and up-to-date benchmarking suites. This paper proposes DLBricks, a composable benchmark generation design that reduces the effort of developing, maintaining, and running DL benchmarks. DLBricks decomposes DL models into a set of unique runnable networks and constructs the original model's performance using the performance of the generated benchmarks. Since benchmarks are generated automatically and the benchmarking time is minimized, DLBricks can keep up-to-date with the latest proposed models, relieving the pressure of selecting representative DL models. We evaluate DLBricks using 50 MXNet models spanning 5 DL tasks on 4 representative CPU systems. We show that DLBricks provides an accurate performance estimate for the DL models and reduces the benchmarking time across systems (e.g. within 95% accuracy and up to 4.4× benchmarking time speedup on Amazon EC2 c5.xlarge).

Modern analytics and recommendation systems are increasingly based on graph data that capture the relations between entities being analyzed. Practical graphs come in huge sizes, offer massive parallelism, and are stored in sparse-matrix formats such as compressed sparse row (CSR). To exploit the massive parallelism, developers are increasingly interested in using GPUs for graph traversal. However, due to their sizes, graphs often do not fit into the GPU memory. Prior works have either used input data pre-processing/partitioning or unified virtual memory (UVM) to migrate chunks of data from the host memory to the GPU memory. However, the large, multi-dimensional, and sparse nature of graph data presents a major challenge to these schemes and results in significant amplification of data movement and reduced effective data throughput. In this work, we propose EMOGI, an alternative approach to traverse graphs that do not fit in GPU memory using direct cache-line-sized access to data stored in host memory. This paper addresses the open question of whether a sufficiently large number of overlapping cache-line-sized accesses can be sustained to 1) tolerate the long latency to host memory, 2) fully utilize the available bandwidth, and 3) achieve favorable execution performance. We analyze the data access patterns of several graph traversal applications in GPU over PCIe using an FPGA to understand the cause of poor external bandwidth utilization. By carefully coalescing and aligning external memory requests, we show that we can minimize the number of PCIe transactions and nearly fully utilize the PCIe bandwidth with direct cache-line accesses to the host memory. EMOGI achieves 2.60X speedup on average compared to the optimized UVM implementations in various graph traversal applications. We also show that EMOGI scales better than a UVM-based solution when the system uses higher bandwidth interconnects such as PCIe 4.0.

Deep neural networks (DNNs) have become core computation components within low latency Function as a Service (FaaS) prediction pipelines. Cloud computing, as the defacto backbone of modern computing infrastructure, has to be able to handle user-defined FaaS pipelines containing diverse DNN inference workloads while maintaining isolation and latency guarantees with minimal resource waste. The current solution for guaranteeing isolation and latency within FaaS is inefficient. A major cause of the inefficiency is the need to move large amount of data within and across servers. We propose TrIMS as a novel solution to address this issue. TrIMSis a generic memory sharing technique that enables constant data to be shared across processes or containers while still maintaining isolation between users. TrIMS consists of a persistent model store across the GPU, CPU, local storage, and cloud storage hierarchy, an efficient resource management layer that provides isolation, and a succinct set of abstracts, applicationAPIs, and container technologies for easy and transparent integration with FaaS, Deep Learning (DL) frameworks, and user code. We demonstrate our solution by interfacing TrIMS with the Apache MXNet framework and demonstrate up to 24x speedup in latency for image classification models, up to 210x speedup for large models, and up to8×system throughput improvement.

Various convolutional neural networks (CNNs) were developed recently that achieved accuracy comparable with that of human beings in computer vision tasks such as image recognition, object detection and tracking, etc. Most of these networks, however, process one single frame of image at a time, and may not fully utilize the temporal and contextual correlation typically present in multiple channels of the same image or adjacent frames from a video, thus limiting the achievable throughput. This limitation stems from the fact that existing CNNs operate on deterministic numbers. In this paper, we propose a novel statistical convolutional neural network (SCNN), which extends existing CNN architectures but operates directly on correlated distributions rather than deterministic numbers. By introducing a parameterized canonical model to model correlated data and defining corresponding operations as required for CNN training and inference, we show that SCNN can process multiple frames of correlated images effectively, hence achieving significant speedup over existing CNN models. We use a CNN based video object detection as an example to illustrate the usefulness of the proposed SCNN as a general network model. Experimental results show that even a nonoptimized implementation of SCNN can still achieve 178% speedup over existing CNNs with slight accuracy degradation.

Neural machine translation (NMT) is a popular topic in Natural Language Processing which uses deep neural networks (DNNs) for translation from source to targeted languages. With the emerging technologies, such as bidirectional Gated Recurrent Units (GRU), attention mechanisms, and beam-search algorithms, NMT can deliver improved translation quality compared to the conventional statistics-based methods, especially for translating long sentences. However, higher translation quality means more complicated models, higher computation/memory demands, and longer translation time, which causes difficulties for practical use. In this paper, we propose a design methodology for implementing the inference of a real-life NMT (with the problem size = 172 GFLOP) on FPGA for improved run time latency and energy efficiency. We use High-Level Synthesis (HLS) to build high-performance parameterized IPs for handling the most basic operations (multiply-accumulations) and construct these IPs to accelerate the matrix-vector multiplication (MVM) kernels, which are frequently used in NMT. Also, we perform a design space exploration by considering both computation resources and memory access bandwidth when utilizing the hardware parallelism in the model and generate the best parameter configurations of the proposed IPs. Accordingly, we propose a novel hybrid parallel structure for accelerating the NMT with affordable resource overhead for the targeted FPGA. Our design is demonstrated on a Xilinx VCU118 with overall performance at 7.16 GFLOPS.

Using flash-based solid state drives (SSDs) as main memory has been proposed as a practical solution towards scaling memory capacity for data-intensive applications. However, almost all existing approaches rely on the paging mechanism to move data between SSDs and host DRAM. This inevitably incurs significant performance overhead and extra I/O traffic. Thanks to the byte-addressability supported by the PCIe interconnect and the internal memory in SSD controllers, it is feasible to access SSDs in both byte and block granularity today. Exploiting the benefits of SSD's byte-accessibility in today's memory-storage hierarchy is, however, challenging as it lacks systems support and abstractions for programs. In this paper, we present FlatFlash, an optimized unified memory-storage hierarchy, to efficiently use byte-addressable SSD as part of the main memory. We extend the virtual memory management to provide a unified memory interface so that programs can access data across SSD and DRAM in byte granularity seamlessly. We propose a lightweight, adaptive page promotion mechanism between SSD and DRAM to gain benefits from both the byte-addressable large SSD and fast DRAM concurrently and transparently, while avoiding unnecessary page movements. Furthermore, we propose an abstraction of byte-granular data persistence to exploit the persistence nature of SSDs, upon which we rethink the design primitives of crash consistency of several representative software systems that require data persistence, such as file systems and databases. Our evaluation with a variety of applications demonstrates that, compared to the current unified memory-storage systems, FlatFlash improves the performance for memory-intensive applications by up to 2.3x, reduces the tail latency for latency-critical applications by up to 2.8x, scales the throughput for transactional database by up to 3.0x, and decreases the meta-data persistence overhead for file systems by up to 18.9x. FlatFlash also improves the cost-effectiveness by up to 3.8x compared to DRAM-only systems, while enhancing the SSD lifetime significantly.

While embedded FPGAs are attractive platforms for DNN acceleration on edge-devices due to their low latency and high energy efficiency, the scarcity of resources of edge-scale FPGA devices also makes it challenging for DNN deployment. In this paper, we propose a simultaneous FPGA/DNN co-design methodology with both bottom-up and top-down approaches: a bottom-up hardware-oriented DNN model search for high accuracy, and a top-down FPGA accelerator design considering DNN-specific characteristics. We also build an automatic co-design flow, including an Auto-DNN engine to perform hardware-oriented DNN model search, as well as an Auto-HLS engine to generate synthesizable C code of the FPGA accelerator for explored DNNs. We demonstrate our co-design approach on an object detection task using PYNQ-Z1 FPGA. Results show that our proposed DNN model and accelerator outperform the state-of-the-art FPGA designs in all aspects including Intersection-over-Union (IoU) (6.2% higher), frames per second (FPS) (2.48× higher), power consumption (40% lower), and energy efficiency (2.5× higher). Compared to GPU-based solutions, our designs deliver similar accuracy but consume far less energy.

Omer Anjum, Hongyu Gong, Suma Bhat, Wen-Mei Hwu, JinJun Xiong. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

Unlike traditional PCIe-based FPGA accelerators, heterogeneous SoC-FPGA devices provide tighter integrations between software running on CPUs and hardware accelerators. Modern heterogeneous SoC-FPGA platforms support multiple I/O cache coherence options between CPUs and FPGAs, but these options can have inadvertent effects on the achieved bandwidths depending on applications and data access patterns. To provide the most efficient communications between CPUs and accelerators, understanding the data transaction behaviors and selecting the right I/O cache coherence method is essential. In this paper, we use Xilinx Zynq UltraScale+ as the SoC platform to show how certain I/O cache coherence method can perform better or worse in different situations, ultimately affecting the overall accelerator performances as well. Based on our analysis, we further explore possible software and hardware modifications to improve the I/O performances with different I/O cache coherence options. With our proposed modifications, the overall performance of SoC design can be averagely improved by 20%.

The rapidly growing demands for powerful AI algorithms in many application domains have motivated massive investment in both high-quality deep neural network (DNN) models and high-efficiency implementations. In this position paper, we argue that a simultaneous DNN/implementation co-design methodology, named Neural Architecture and Implementation Search (NAIS), deserves more research attention to boost the development productivity and efficiency of both DNN models and implementation optimization. We propose a stylized design methodology that can drastically cut down the search cost while preserving the quality of the end solution. As an illustration, we discuss this DNN/implementation methodology in the context of both FPGAs and GPUs. We take autonomous driving as a key use case as it is one of the most demanding areas for high quality AI algorithms and accelerators. We discuss how such a co-design methodology can impact the autonomous driving industry significantly. We identify several research opportunities in this exciting domain.

Multi-scale context module and single-stage encoder-decoder structure are commonly employed for semantic segmentation. The multi-scale context module refers to the operations to aggregate feature responses from a large spatial extent, while the single-stage encoder-decoder structure encodes the high-level semantic information in the encoder path and recovers the boundary information in the decoder path. In contrast, multi-stage encoder-decoder networks have been widely used in human pose estimation and show superior performance than their single-stage counterpart. However, few efforts have been attempted to bring this effective design to semantic segmentation. In this work, we propose a Semantic Prediction Guidance (SPG) module which learns to re-weight the local features through the guidance from pixel-wise semantic prediction. We find that by carefully re-weighting features across stages, a two-stage encoder-decoder network coupled with our proposed SPG module can significantly outperform its one-stage counterpart with similar parameters and computations. Finally, we report experimental results on the semantic segmentation benchmark Cityscapes, in which our SPGNet attains 81.1% on the test set using only 'fine' annotations.

Fine-grained action detection is an important task with numerous applications in robotics and human-computer interaction. Existing methods typically utilize a two-stage approach including extraction of local spatio-temporal features followed by temporal modeling to capture long-term dependencies. While most recent papers have focused on the latter (long-temporal modeling), here, we focus on producing features capable of modeling fine-grained motion more efficiently. We propose a novel locally-consistent deformable convolution, which utilizes the change in receptive fields and enforces a local coherency constraint to capture motion information effectively. Our model jointly learns spatio-temporal features (instead of using independent spatial and temporal streams). The temporal component is learned from the feature space instead of pixel space, e.g. optical flow. The produced features can be flexibly used in conjunction with other long-temporal modeling networks, e.g. ST-CNN, DilatedTCN, and ED-TCN. Overall, our proposed approach robustly outperforms the original long-temporal models on two fine-grained action datasets: 50 Salads and GTEA, achieving F1 scores of 80.22% and 75.39% respectively.

Driven by deep learning, there has been a surge of specialized processors for matrix multiplication, referred to as Tensor Core Units (TCUs). These TCUs are capable of performing matrix multiplications on small matrices (usually 4 × 4 or 16 × 16) to accelerate HPC and deep learning workloads. Although TCUs are prevalent and promise increase in performance and/or energy efficiency, they suffer from over specialization as only matrix multiplication on small matrices is supported. In this paper we express both reduction and scan in terms of matrix multiplication operations and map them onto TCUs. To our knowledge, this paper is the first to try to broaden the class of algorithms expressible as TCU operations and is the first to show benefits of this mapping in terms of: program simplicity, efficiency, and performance. We implemented the reduction and scan algorithms using NVIDIA's V100 TCUs and achieved 89% -- 98% of peak memory copy bandwidth. Our results are orders of magnitude faster (up to 100 × for reduction and 3 × for scan) than state-of-the-art methods for small segment sizes (common in HPC and deep learning applications). Our implementation achieves this speedup while decreasing the power consumption by up to 22% for reduction and 16% for scan.

Recent advancements in deep learning techniques facilitate intelligent-query support in diverse applications, such as content-based image retrieval and audio texturing. Unlike conventional key-based queries, these intelligent queries lack efficient indexing and require complex compute operations for feature matching. To achieve high-performance intelligent querying against massive datasets, modern computing systems employ GPUs in-conjunction with solid-state drives (SSDs) for fast data access and parallel data processing. However, our characterization with various intelligent-query workloads developed with deep neural networks (DNNs), shows that the storage I/O bandwidth is still the major bottleneck that contributes 56%--90% of the query execution time.

The current landscape of cognitive pipelines exercises many Machine Learning (ML) and Deep Learning (DL) building blocks. These ML and DL building blocks leverage non-uniform frameworks, models, and system stacks. Currently, there is no end-to-end tool that facilitates ML and DL building blocks evaluation and introspection within cognitive pipelines. Due to the absence of such tools, the current practice for evaluating and comparing the benefits of hardware or software innovations on end-to-end cognitive pipelines is both arduous and error-prone - stifling the rate of adoption of innovations. We propose MLModelScope: a hardware/software agnostic platform to facilitate evaluation and introspection of cognitive pipelines in the cloud or on the edge. We describe the design and implementation of MLModelScope and show how it provides a holistic view of the execution of components within cognitive pipelines. MLModelScope aids application developers in experimenting with and discovering cognitive models, data scientists in comparing and evaluating published algorithms, and system architects in optimizing system stacks for cognitive applications.

Data-intensive applications such as machine learning and analytics have created a demand for faster interconnects to avert the memory bandwidth wall and allow GPUs to be effectively leveraged for lower compute intensity tasks. This has resulted in wide adoption of heterogeneous systems with varying underlying interconnects, and has delegated the task of understanding and copying data to the system or application developer. No longer is a malloc followed by memcpy the only or dominating modality of data transfer; application developers are faced with additional options such as unified memory and zero-copy memory. Data transfer performance on these systems is now impacted by many factors including data transfer modality, system interconnect hardware details, CPU caching state, CPU power management state, driver policies, virtual memory paging efficiency, and data placement.

The production of sports highlight packages summarizing a game's most exciting moments is an essential task for broadcast media. Yet, it requires labor-intensive video editing. We propose a novel approach for auto-curating sports highlights, and demonstrate it to create a first of a kind, real-world system for the editorial aid of golf and tennis highlight reels. Our method fuses information from the players’ reactions (action recognition such as high-fives and fist pumps), players’ expressions (aggressive, tense, smiling, and neutral), spectators (crowd cheering), commentator (tone of the voice and word analysis), and game analytics to determine the most interesting moments of a game. We accurately identify the start and end frames of key shot highlights with additional metadata, such as the player's name and the whole number, or analysts input allowing personalized content summarization and retrieval. In addition, we introduce new techniques for learning our classifiers with reduced manual training data annotation by exploiting the correlation of different modalities. Our work has been demonstrated at a major golf tournament (2017 Masters) and two major international tennis tournaments (2017 Wimbledon and U.S. Open), successfully extracting highlights through the course of the sporting events. For the 2017 Masters, 54% of the clips selected by our system overlapped with the official highlights reels. Furthermore, user studies showed that 90% of the non-overlapping ones were of the same quality of the official clips for the 2017 Masters, while the automatic selection of clips for highlights of 2017 Wimbledon and 2017 US Open agreed with human preferences 80% and 84.2% of the time, respectively.

Measuring similarity between texts is an important task for several applications.Available approaches to measure document similarity are inadequate for document pairs that have non-comparable lengths, such as a long document and its summary.This is because of the lexical, contextual and the abstraction gaps between a long document of rich details and its concise summary of abstract information.In this paper, we present a document matching approach to bridge this gap, by comparing the texts in a common space of hidden topics.We evaluate the matching algorithm on two matching tasks and find that it consistently and widely outperforms strong baselines.We also highlight the benefits of the incorporation of domain knowledge to text matching.

The world has seen in recent years great successes in applying deep learning (DL) for many application domains. Though powerful, DL is not easy to be used well. In this invited paper, we study an urban taxi demand forecast problem using DL, and we show a number of key insights in modeling a domain problem as a suitable DL task. We also conduct a systematic comparison of two recent deep neural networks (DNNs) for taxi demand prediction, i.s., the ST-ResNet and FLC-Net, on New York city taxi record dataset. Our experimental results show DNNs indeed outperform most traditional machine learning techniques, but such superior results can only be achieved with proper design of the right DNN architecture, where domain knowledge plays a key role.

Machine learning and deep learning has attracted a lot of attention from industry, media, academia and government alike, and its impact to business and industries can't be over emphasized. The subject is broad with many on-going research and development. I plan to present an effective tutorial on such a broad subject in a two-hour duration to the DA community. My plan is to teach some of the most important fundamental techniques that are proven to be common and universal to many popular machine learning and deep learning algorithms. Covered topics will include the general iterative algorithm for solving unconstrained optimization problems, gradient descent and stochastic gradient descent methods, fundamental concepts in machine learning (such as training, testing, and cross validation, bias, variance), differences between machine learning, AI, and data mining, popular machine learning algorithms such as perceptron, logistic regression, decision tree and random forest, and deep learning algorithm such as ANN and CNN. A central theme to all the algorithmic coverage is a common set of techniques that are proven to be critical for their deep understanding. If time permits, I will also share some of my experience in applying those techniques to various industry solutions and how that relates to my deep DA roots.

With the rapid growth of medical and biomedical image data, energy-efficient solutions for analyzing such image data that can be processed fast and accurately on platforms with low power budget are highly desirable. This paper uses segmenting glial cells in brain microscopy images as a case study to demonstrate how to achieve biomedical image segmentation with significant energy saving and minimal comprise in accuracy. Specifically, we design, train, implement, and evaluate Fully Convolutional Networks (FCNs) for biomedical image segmentation on IBM's neurosynaptic DNN processor - TrueNorth (TN). Comparisons in terms of accuracy and energy dissipation of TN with that of a low power NVIDIA TX2 mobile GPU platform have been conducted. Experimental results show that TN can offer at least two orders of magnitude improvement in energy efficiency when compared to TX2 GPU for the same workload.

In coal-fired power plants, it is critical to improve the operational efficiency of boilers for sustainability. In this work, we formulate real-time boiler control as an optimization problem that looks for the best distribution of temperature in different zones and oxygen content from the flue to improve the boiler's stability and energy efficiency. We employ an efficient algorithm by integrating appropriate machine learning and optimization techniques. We obtain a large dataset collected from a real boiler for more than two months from our industry partner, and conduct extensive experiments to demonstrate the effectiveness and efficiency of the proposed algorithm.

Using FPGA to accelerate Deep Neural Networks (DNNs) requires RTL programming, hardware verification, and precise resource allocation, which is both time-consuming and challenging. To address this issue, we present AccDNN, an end-to-end automation tool that can generate high-performance DNN designs on FPGAs automatically. Highlights of this tool include high-quality RTL network layer IPs, a fine-grained layer-based pipeline architecture, and a column-based cache scheme for high throughput, low latency, and reduced on-chip memory utilization. AccDNN also includes an automatic design space exploration tool, called A-REALM, used to generate optimized parallelism schemes by considering external memory access bandwidth, data reuse behaviors, resource availability, and network complexity. We demonstrate AccDNN on four DNNs (Alexnet, ZF, VGG16, and YOLO) on two Xilinx FPGAs (ZC706 and KU115) for edge- and cloud-computing, respectively. AccDNN generates designs that deliver 263 GOPS and 36.4 GOPS/W on ZC706 without any batching and 2109 GOPS and 94.5 GOPS/W on KU115.

Deep Convolutional Neural Networks (CNN) have become a Swiss knife in solving critical arti cial intelligence tasks. However, deploying deep CNN models for latency-critical tasks remains to be challenging because of the complex nature of CNNs. Recently, FPGA has become a favorable device to accelerate deep CNNs thanks to its high parallel processing capability and energy e ciency. In this work, we explore di erent fast convolution algorithms including Winograd and Fast Fourier Transform (FFT), and nd an optimal strategy to apply them together on di erent types of convolutions. We also propose an optimization scheme to exploit parallelism on novel CNN architectures such as Inception modules in GoogLeNet. We implement a con gurable IP-based face recognition acceler- ation system based on FaceNet using High-Level Synthesis. Our implementation on a Xilinx Ultrascale device achieves 3.75x la- tency speedup compared to a high-end NVIDIA GPU and surpasses previous FPGA results signi cantly.

Building a high-performance FPGA accelerator for Deep Neural Networks (DNNs) often requires RTL programming, hardware verification, and precise resource allocation, all of which can be time-consuming and challenging to perform even for seasoned FPGA developers. To bridge the gap between fast DNN construction in software (e.g., Caffe, TensorFlow) and slow hardware implementation, we propose DNNBuilder for building high-performance DNN hardware accelerators on FPGAs automatically. Novel techniques are developed to meet the throughput and latency requirements for both cloud- and edge-devices. A number of novel techniques including high-quality RTL neural network components, a fine-grained layer-based pipeline architecture, and a column-based cache scheme are developed to boost throughput, reduce latency, and save FPGA on-chip memory. To address the limited resource challenge, we design an automatic design space exploration tool to generate optimized parallelism guidelines by considering external memory access bandwidth, data reuse behaviors, FPGA resource availability, and DNN complexity. DNNBuilder is demonstrated on four DNNs (Alexnet, ZF, VGG16, and YOLO) on two FPGAs (XC7Z045 and KU115) corresponding to the edge- and cloud-computing, respectively. The fine-grained layer-based pipeline architecture and the column-based cache scheme contribute to 7.7x and 43x reduction of the latency and BRAM utilization compared to conventional designs. We achieve the best performance (up to 5.15x faster) and efficiency (up to 5.88x more efficient) compared to published FPGA-based classification-oriented DNN accelerators for both edge and cloud computing cases. We reach 4218 GOPS for running object detection DNN which is the highest throughput reported to the best of our knowledge. DNNBuilder can provide millisecond-scale real-time performance for processing HD video input and deliver higher efficiency (up to 4.35x) than the GPU-based solutions.

The physical memory capacity of servers is expected to increase drastically with deployment of the forthcoming non-volatile memory technologies. This is a welcomed improvement for emerging data-intensive applications. For such servers to be cost-effective, nonetheless, we must cost-effectively increase compute throughput and memory bandwidth commensurate with the increase in memory capacity without compromising application readiness. Tackling this challenge, we present Memory Channel Network (MCN) architecture in this paper. Specifically, first, we propose an MCN DIMM, an extension of a buffered DIMM where a small but capable processor called MCN processor is integrated with a buffer device on the DIMM for near-memory processing. Second, we implement device drivers to give the host and MCN processors in a server an illusion that they are independent heterogeneous nodes connected through an Ethernet link. These allow the host and MCN processors in a server to run a given data-intensive application together based on popular distributed computing frameworks such as MPI and Spark without any change in the host processor hardware and its application software, while offering the benefits of high-bandwidth and low-latency communications between the host and the MCN processors over memory channels. As such, MCN can serve as an application-transparent framework which can seamlessly unify near-memory processing within a server and distributed computing across such servers for data-intensive applications. Our simulation running the full software stack shows that a server with 8 MCN DIMMs offers 4.56X higher throughput and consume 47.5% less energy than a cluster with 9 conventional nodes connected through Ethernet links, as it facilitates up to 8.17X higher aggregate DRAM bandwidth utilization. Lastly, we demonstrate the feasibility of MCN with an IBM POWER8 system and an experimental buffered DIMM.

Textual grounding is an important but challenging task for human-computer inter- action, robotics and knowledge mining. Existing algorithms generally formulate the task as selection from a set of bounding box proposals obtained from deep net based systems. In this work, we demonstrate that we can cast the problem of textual grounding into a unified framework that permits efficient search over all possible bounding boxes. Hence, the method is able to consider significantly more proposals and doesn’t rely on a successful first stage hypothesizing bounding box proposals. Beyond, we demonstrate that the trained parameters of our model can be used as word-embeddings which capture spatial-image relationships and provide interpretability. Lastly, at the time of submission, our approach outperformed the current state-of-the-art methods on the Flickr 30k Entities and the ReferItGame dataset by 3.08% and 7.77% respectively.

In this paper, two techniques based on Q -learning and action dependent heuristic dynamic programming (ADHDP) are demonstrated for the demand-side management of domestic electric water heaters (DEWHs). The problem is modeled as a dynamic programming problem, with the state space defined by the temperature of output water, the instantaneous hot water consumption rate, and the estimated grid load. According to simulation, Q-learning and ADHDP reduce the cost of energy consumed by DEWHs by approximately 26% and 21%, respectively. The simulation results also indicate that these techniques will minimize the energy consumed during load peak periods. As a result, the customers saved about $466 and $367 annually by using Q-learning and ADHDP techniques to control their DEWHs (100 gallons tank size) operation, which is better than the cost reduction that resulted from using the state-of-the-art ($246) control technique under the same simulation parameters. To the best of the authors' knowledge, this is the first work that uses the approximate dynamic programming techniques to solve the DEWH's load management problem.

Adaptive test of integrated circuits (IC) promises to increase the quality and yield of products with reduced manufacturing test cost compared to traditional static test flows. Two mostly widely used techniques are Statistical Process Control (SPC) and Part Average Testing (PAT), whose capabilities to capture complex correlation between test measurements and the underlying IC's physical and electrical properties are, however, limited. Based on recent progress on machine learning, this paper proposes a novel deep learning based method for adaptive test. Compared to most machine learning techniques, deep learning has the distinctive advantage of being able to capture the underlying key features automatically from data without manual intervention. In this paper, we start from a trained deep neuron network (DNN) with a much higher accuracy than the conventional test flow for the pass and fail prediction. We further develop two novel applications by leveraging the features learned from DNN: one to enable partial testing, i.e., make decisions on pass and fail without finishing the entire test flow, and two to enable dynamic test ordering, i.e., changing the sequence of tests adaptively. Experiment results show significant improvement on the accuracy and effectiveness of our proposed method.

Runtime noise management systems typically rely on on-chip noise sensors to accurately capture voltage emergencies. As such, the threshold voltage for noise sensors to report emergencies serves as a critical tuning knob between the system failure rate and false alarms. Unfortunately, the problem of optimal threshold voltage computation remains open in literature despite its importance. The problem is further complicated by process variations, which introduce significant variations in load currents and thus in noise across different chips. A uniform noise margin may not work optimally for all the chips. In this paper, we first formulate the problem of minimizing the system alarm rate subject to a given system failure rate constraint. We then put forward a uniform scheme to find an optimal solution for all chips. Compared to a seemingly more intuitive approach which is too conservative, experimental results over a set of industrial designs show an average of 20.6% reduction in system alarm rate under the same system failure rate constraint. We further show that with the help of Iddqmeasurements during testing which reveal process variation information, it is possible and efficient to compute a per-chip optimal threshold voltage threshold. It further reduces the alarm rate by 12.3% on average compared with uniform threshold approach. To the best of the authors knowledge, this is the first in-depth study on optimal threshold voltage computation for noise sensors. We hope that it shall point out new directions for systematic studies of on-chip noise sensor utilization.

Big data analytics is the latest spotlight with all the glare of fame ranging from media coverage to booming startup companies to eye-catching merges and acquisitions. On the contrary, the $336 billion industry of semiconductor was seen as an “old-fashioned” business, with fading interests from the best and brightest among young graduates and engineers. How will modern big data analytics help the semiconductor industry walk through this transition? This paper answers this question via a number of practical but challenging problems arising from semiconductor manufacturing process. We show that many existing machine learning algorithms are not well positioned to solve these problems, and novel techniques involving temporal, structural and hierarchical properties need to be developed to solve these problems.

The lack of accurate yet open to public simulation infrastructure has puzzled researchers in the memcomputing area for sometime. In this paper, we propose for the first time a full tool chain called MSim that supports the cycle-accurate microarchitecture level simulation for memcomputing studies. With MSim, the performance gains of utilizing memcomputing for arbitrary applications on user configurable computer system architectures can be evaluated in high accuracy. In addition, MSim provides flexible interfaces with pervasive object-oriented design, which makes it well-suited as a good base platform for researchers to explore new memcomputing technologies.

Runtime noise management systems typically respond to on-chip noise sensors to accurately capture voltage emergencies. As such, the threshold voltage for noise sensors to report emergencies serves as a critical tuning knob between the system failure rate and the runtime performance loss (RPL) due to false alarms. Unfortunately, the problem of optimal threshold voltage computation remains open in literature despite its importance. The problem is further complicated by process variations, which introduce significant variations in load currents and thus in noise across different chips. A uniform noise margin may not work optimally for all the chips. In this paper, we first formulate the problem of minimizing the system failure rate subject to a given RPL constraint. We then put forward a uniform scheme to find an optimal solution for all chips. Compared to a seemingly more intuitive approach which is too conservative, experimental results over a set of industrial designs show an average of 32.1% reduction in system failure rate under the same RPL constraint. We further show that with the help of Iddqmeasurements during testing which reveals process variation information, it is possible and efficient to compute a per-chip optimal threshold voltage. Such an approach further reduces the system failure rate by 25.0% on average compared with the uniform threshold approach, under the same RPL constraint. To the best of the authors knowledge, this is the first in-depth study on optimal threshold voltage computation for noise sensors. We hope that it shall point out new directions for systematic studies of on-chip noise sensor utilization.

The real time anomaly detection in wide area monitoring of smart grids is critical to enhance the reliability of power systems. However, capturing the features of anomalous interruption and then detecting them at real time is difficult for large-scale smart grids, because the measurement data volume and complexity increases drastically with the exponential growth of data from the immense intelligent monitoring devices to be rolled out and the need for fast information retrieval from those mass data. Most of existing anomaly detection methods fail to handle it well. This paper proposes a spatial-temporal correlation based anomalous behavior model to capture the characteristics of anomaly such as transmission line outages in smart grid. Inspired by Ledoit-Wolf Shrinkage (LWS) method, we develop the real time anomaly detection (ReTAD) algorithm to overcome the issue of gigantic measurement data volume. The proposed algorithm is not only suitable for large number of power systems with high dimensional measurement data, but at the same time is also low computational complexity to apply for real time detection. Using 14-, 30, and 2383-bus systems, our experimental study demonstrates that our proposed ReTAD algorithm successfully detects the anomalous events at real time.

This paper addresses geospatial interpolation for meteorological measurements in which we estimate the values of climatic metrics at unsampled sites with existing observations. Providing climatological and meteorological conditions covering a large region is potentially useful in many applications, such as smart grid. However, existing research works on interpolation either cause a large number of complex calculations or are lack of high accuracy. We propose a Bayesian compressed sensing based non-parametric statistical model to efficiently perform the spatial interpolation task. Student-t priors are employed to model the sparsity of unknown signals' coefficients, and the Approximated Variational Inference (AVI) method is provided for effective and fast learning. The presented model has been deployed at IBM, targeting for aiding the intelligent management of smart grid. The evaluations on two real world datasets demonstrate that our algorithm achieves state-of-the-art performance in both effectiveness and efficiency.

Runtime noise management systems can enforce power integrity without significantly increasing design margins. These systems typically respond to on-chip noise sensors to accurately capture voltage emergencies. Unfortunately, it remains an open problem in the literature how to optimally place a given number of noise sensors for best voltage emergency detection, or how to best set the threshold voltage for these sensors. In this paper, we formally define the problem of noise sensor placement along with a novel sensing quality metric to be maximized. We then put forward an efficient algorithm to solve it, which is proven to attain the best result in the class of polynomial complexity approximations. We further solve the problem to minimize the system failure rate subject to a given runtime performance loss (RPL) constraint. Experimental results on a set of industrial power grid designs show that, compared to a simple average-noise based heuristic and two state-of-the-art temperature sensor placement algorithms aimed at recovering the full map or capturing the hot spots at all times, the proposed method on average can reduce the miss rate of voltage emergency detections by 7.4x, 15x, and 6.2x, respectively. The trade-off between the system failure rate and the RPL is also presented. To the best of the authors' knowledge, this is the very first in-depth work on noise sensor deployment.

The relentless technology scaling has led to significantly reduced noise margin and complicated functionalities. As such, design time techniques per se are less likely to ensure power integrity, resulting in runtime voltage emergencies. To alleviate the issue, recently several works have shed light on the possibilities of dynamic noise management systems. Most of these works rely on on-chip noise sensors to accurately capture voltage emergencies. However, they all assume, either implicitly or explicitly, that the placement of the sensors is given. It remains an open problem in the literature how to optimally place a given number of noise sensors for best voltage emergency detection. In this paper, we formally define the problem of noise sensor placement along with a novel sensing quality metric (SQM) to be maximized. We then put forward an efficient algorithm to solve it, which is proved to be optimal in the class of polynomial complexity approximations. Experimental results on a set of industrial power grid designs show that compared with a simple average-noise based heuristic and two state-of-the-art temperature sensor placement algorithms aiming at recovering the full map or capturing the hot spots at all times, the proposed method on average can reduce the miss rate of voltage emergency detections by 7.4x, 15x and 6.2x, respectively.

Although order statistics have been studied for several decades, most of the results are based on the assumption of independent and identically distributed (i.i.d.) random variables. In the literature, how to compute the m th order statistics of n correlated random variables is still a problem. This article proposes a recursive algorithm based on statistical min/max operations to compute order statistics for general correlated and not necessarily identically distributed random variables. The algorithm has an O( mn ) time complexity and O( m + n ) space complexity. A binary tree-based data structure is further developed to allow selective update of the order statistics with O( nm 2 ) time. As a vehicle to demonstrate the algorithm, we apply it to the path selection algorithm in at-speed testing. A novel metric multilayer process space coverage metric is proposed to quantitatively gauge the quality of path selection. We then show that such a metric is directly linked to the order statistics, and our recursive algorithm can thus be applied. By employing a branch-and-bound path selection algorithm with these techniques, this article shows that selecting an optimal set of paths for a multimillion-gate design can be performed efficiently. Compared to the state of the art, experimental results show both the efficiency of our algorithms and better quality of our path selection.

The increasing significance of variability in modern sub-micron manufacturing process has led to the development and use of statistical techniques for chip timing analysis and optimization. Statistical timing involves fundamental operations like statistical-add, sub, max and min to propagate timing information (modeled as random variables with known probability distributions) through a timing graph model of a chip design. Although incremental timing during optimization updates timing information of only certain parts of the timing-graph, lack of established reversible statistical max or min techniques forces more-than-required computations.

Statistical static timing analysis (SSTA) is ideal for random variations but is not suitable for environmental variations like Vdd and temperature. SSTA uses statistical approximation, according to which circuit timing is predicted accurately only for highly probable combinations of variational parameters. SSTA is not able to handle accurately deterministic sources of variation like supply voltage. This paper presents a novel technique for modeling nonseparable deterministic and statistical variations in single timing run.

To enable statistical static timing analysis, for each cell in a digital library, a timing model that considers variations must be characterized. In this paper, we propose a dynamic method to accurately and efficiently characterize a cell's delay and output slew as a function of random mismatch variations. Based on a tight error bound for characterization using partial devices, our method sequentially performs simulations based on decreasing importance of devices and stops when the error requirement is met. Results on an industrial 32nm library demonstrate that the proposed method achieves significantly better accuracy-efficiency trade-off compared to other partial finite differencing approaches.

This paper presents a method to compute criticality probabilities of paths in parameterized statistical static timing analysis. We partition the set of all the paths into several groups and formulate the path criticality into a joint probability of inequalities. Before evaluating the joint probability directly, we simplify the inequalities through algebraic elimination, handling topological correlation. Our proposed method uses conditional probabilities to obtain the joint probability, and statistics of random variables representing process parameters are changed to take into account the conditions. To calculate the conditional statistics of the random variables, we derive analytic formulas by extending Clark's work. This allows us to obtain the conditional probability density function of a path delay, given the path is critical, as well as to compute criticality probabilities of paths. Our experimental results show that the proposed method provides 4.2X better accuracy on average in comparison to the state-of-art method.

In the face of large-scale process variations, statistical timing methodology has advanced significantly over the last few years, and statistical path selection takes advantage of it in at-speed testing. In deterministic path selection, the separation of path selection and test generation is known to require time consuming iteration between the two processes. This paper shows that in statistical path selection, this is not only the case, but also the quality of results can be severely degraded even after the iteration. To deal with this issue, we consider testability in the first place by integrating a satisfiability (SAT) solver, and this necessitates a new statistical path selection method. We integrate the SAT solver in a novel way that leverages the conflict analysis of modern SAT solvers, which provides more than 4X speedup without special optimizations of the SAT solver for this particular application. Our proposed method is based on a generalized path criticality metric whose properties allow efficient pruning. Our experimental results show that the proposed method achieves 47% better quality of results on average, and up to 361X speedup compared to statistical path selection followed by test generation.

In this article, we present a new full-chip statistical leakage estimation considering the spatial correlation condition (strong or weak). The new algorithm can deliver linear time, O ( N ), time complexity, where N is the number of grids on chip. The proposed algorithm adopts a set of uncorrelated virtual variables over grid cells to represent the original physical random variables and the cell size is determined by the spatial correlation length. In this way, each physical variable is always represented by virtual variables locally. We prove the number of neighbor cells for each grid cell is not related to the condition of spatial correlation (from no correlation to 100% correlated), which leads to linear time complexity in terms of number of gates. We compute the gate leakage by the orthogonal polynomials-based collocation method. The total leakage of a whole chip can be computed by simply summing up the coefficients of corresponding orthogonal polynomials in each grid cell. Furthermore, we develop a look-up table to cache statistical information for each type of gate instead of calculating leakage for every single instance of gate on a chip. As a result, a new statistical leakage characterization in Standard Cell Library (SCL) is put forward. Furthermore, an incremental analysis algorithm is proposed to update the chip-level statistical leakage information efficiently after a few changes are made. The proposed method has no restrictions on static leakage models, or types of leakage distributions. The large circuit examples in 45nm CMOS process demonstrate the proposed algorithm is 1000X faster than a recently proposed grid-based method with similar accuracy and many orders of magnitude times speedup over the Monte Carlo method. Experimental results also show the incremental analysis provides about 10X further speedup. We expect the incremental analysis could achieve more speedup over the full leakage analysis for larger problem sizes.

The most challenging problem in the current block-based statistical static timing analysis (SSTA) is how to handle the max operation efficiently and accurately. Existing SSTA techniques suffer from limited modeling capability by using a linear delay model with Gaussian distribution, or have scalability problems due to expensive operations involved to handle non-Gaussian variation sources or nonlinear delays. To overcome these limitations, we propose efficient algorithms to handle the max operation in SSTA with both quadratic delay dependency and non-Gaussian variation sources simultaneously. Based on such algorithms, we develop an SSTA flow with quadratic delay model and non-Gaussian variation sources. All the atomic operations, max and add, are calculated efficiently via either closed-form formulas or low dimension (at most 2-D) lookup tables. We prove that the complexity of our algorithm is linear in both variation sources and circuit sizes, hence our algorithm scales well for large designs. Compared to Monte Carlo simulation for non-Gaussian variation sources and nonlinear delay models, our approach predicts the mean, standard deviation and 95% percentile point with less than 2% error, and the skewness with less than 10% error.

This paper presents a method to compute criticality probabilities of paths in parameterized statistical static timing analysis (SSTA). We partition the set of all the paths into several groups and formulate the path criticality into a joint probability of inequalities. Before evaluating the joint probability directly, we simplify the inequalities through algebraic elimination, handling topological correlation. Our proposed method uses conditional probabilities to obtain the joint probability, and statistics of random variables representing process parameters are changed due to given conditions. To calculate the conditional statistics of the random variables, we derive analytic formulas by extending Clark's work. This allows us to obtain the conditional probability density function of a path delay, given the path is critical, as well as to compute criticality probabilities of paths. Our experimental results show that the proposed method provides 4.2X better accuracy on average in comparison to the state-of-art method.

In the face of large-scale process variations, statistical timing methodology has advanced significantly over the last few years, and statistical path selection takes advantage of it in at-speed testing. In deterministic path selection, the separation of path selection and test generation is known to require time consuming iteration between the two processes. This paper shows that in statistical path selection, this is not only the case, but also the quality of results can be severely degraded even after the iteration. To deal with this issue, we consider testability in the first place by integrating a SAT solver, and this necessitates a new statistical path selection method. Our proposed method is based on a generalized path criticality metric which properties allow efficient pruning. Our experimental results show that the proposed method achieves 47% better quality of results on average, and up to 361x speedup compared to statistical path selection followed by test generation.

Multi-agent simulation (MAS) is a widely used paradigm for modeling and simulating real world complex system, ranging from ant colony foraging to online trading. The performance of existing MAS software, however, suffers when simulating massive-scale multi-agent systems on traditional serial processing processors. In this paper, we propose an FPGA-based framework for massive-scale grid-based MAS. Memory interleaving, parallel tasks partition, and computing pipeline are adopted to improve system throughput. A classical MAS benchmark, Conway's Game of Life, is used as a case study to illustrate how to map grid-based models to our MAS framework. We implemented it on a Xilinx Virtex-5 FPGA board and achieved a speedup of 290x with two million agents, compared to the C implementation.

A chip disposition criterion is used to decide whether to accept or discard a chip during chip testing. Its quality directly impacts both yield and product quality loss (PQL). The importance becomes even more significant with the increasingly large process variation. For the first time, this paper rigorously formulates the optimal chip disposition problem, and proposes an elegant solution. We show that the optimal chip disposition criterion is different from the existing industry practice. Our solution can find the optimal disposition criterion efficiently with better yield under the same PQL constraint, or lower PQL under the same yield constraint.

Power delivery network (PDN) is a distributed resistance-inductance-capacitance (RLC) network with its dominant resonance frequency in the low-to-middle frequency range. Though high-performance chips' working frequencies are much higher than this resonance frequency in general, chip runtime loading frequency is not. When a chip executes a chunk of instructions repeatedly, the induced current load may have harmonic components close to this resonance frequency, causing excessive power integrity degradation. Existing PDN design solutions are, however, mainly targeted at reducing high-frequency noise and not effective to suppress such resonance noise. In this work, we propose a novel approach to proactively suppress this type of noise. A method based on the high dimension generalized Markov process is developed to predict current load variation. Based on such prediction, a clock frequency actuator design is proposed to proactively select an optimal clock frequency to suppress the resonance. To the best of our knowledge, this is the first in-depth study on proactively reducing instruction loop induced PDN resonance noise at the runtime.

Transistor sizing is a classic Computer-Aided Design problem that has received much attention in the literature. Due to the increasing importance of process variations in deep sub-micron circuits, nominal circuit tuning is not sufficient, and the sizing problem warrants revisiting. This paper addresses the sizing problem statistically in which transistor sizes are automatically adjusted to maximize parametric yield at a given timing performance, or maximize performance at a required parametric yield. Specifically, we describe an implementation of a statistical tuner using interior point nonlinear optimization with an objective function that is directly dependent on statistical process variation. Our results show that for process variation sensitive circuits, consisting of thousands of independently tunable devices, a statistically aware tuner can give more robust, higher yield solutions when compared to deterministic circuit tuning and is thus an attractive alternative to the Monte Carlo methods that are typically used to size devices in such circuits. To the best of our knowledge, this is the first publication of a working system to optimize device sizes in custom circuits using a process variation aware tuner.

Full-chip statistical leakage power analysis typically requires quadratic time complexity in the presence of spatial correlation. When spatial correlation are strong (with large spatial correlation length), efficient linear time complexity analysis can be attained as the number of variational variables can be significantly reduced. However this is not the case for circuits where gate leakage currents are weakly correlated. In this paper, we present a linear time algorithm for statistical leakage power analysis in the presence of weak spatial correlation. The new algorithm exploits the fact that gate leakage current can be efficiently computed locally when correlation is weak. We adopt a newly proposed spatial correlation model where a new set of location-dependent uncorrelated variables are defined over virtual grids to represent the original physical random variables via fitting. To compute the leakage current of a gate on the new set of variables, the new method uses the orthogonal polynomials based collocation method, which can be applied to any gate leakage models. The total leakage currents are then computed by simply summing up the resulting orthogonal polynomials (their coefficients) on the new set of variables for all gates. Experimental results show that the proposed method is about two orders of magnitude faster than the recently proposed grid-based method [3] with similar accuracy and many orders of magnitude times over the Monte Carlo method.

In this paper, we present an approved linear-time algorithm for statistical leakage analysis in the present of any spatial correlation condition (strong or weak). The new algorithm adopts a new set of uncorrelated variables over virtual grids to represent the original physical random variables and the grid size (thus of number of new random variables) is determined by the spatial correlation length. In this way, each physical variable is always represented by virtual variables locally. We prove that the number of neighboring virtual grids for each grid is not related to condition of spatial correlation, which leads to linear time complexity in terms of number of gates. We compute the gate leakage by the orthogonal polynomials based collocation method. The total leakage of a whole chip can be computed by simply summing up the coefficients of corresponding orthogonal polynomials for each grid. Furthermore, look-up table can be created to cache statistical information for each type of gates in library instead of calculating leakage for every single gate on chip. As a result, we end up with O(N) time complexity, where N is the number of grids on chip. The proposed method has no restrictions on static leakage models, types of statistical distributions for leakage currents. Experimental results show that the proposed method is about 1000X faster than the recently proposed grid-based method [2] with similar accuracy and many orders of magnitude times over the Monte Carlo method.

Process variations make at-speed testing significantly more difficult. They cause subtle delay changes that are distributed in contrast to the localized nature of a traditional fault model. Due to parametric variations, different paths can be critical in different parts of the process space, and the union of such paths must be tested to obtain good process space coverage. This paper proposes an integrated at-speed structural testing methodology, and develops a novel branch-and-bound algorithm that elegantly and efficiently solves the hitherto open problem of statistical path tracing. The resulting paths are used for at-speed structural testing. A new test quality metric is proposed, and paths which maximize this metric are selected. After chip timing has been performed, the path selection procedure is extremely efficient. Path selection for a multimillion gate chip design can be completed in a matter of seconds.

Power delivery network (PDN) is a distributed RLC network with its dominant resonance frequency in the low-to-middle frequency range. Though high-performance chips' working frequencies are much higher than this resonance frequency in general, chip runtime loading frequency is not. When a chip executes a chunk of instructions repeatedly, the induced current load may have harmonic components close to this resonance frequency, causing excessive power integrity degradation. Existing PDN design solutions are, however, mainly targeted at reducing high-frequency noise and not effective to suppress such resonance noise. In this work, we propose a novel approach to proactively suppress this type of noise. A method based on a high dimension generalized Markov process is developed to predict current load variation. Based on such prediction, a clock frequency actuator design is proposed to proactively select an optimal clock frequency to suppress the resonance. To the best of our knowledge, this is the first in-depth study on proactively reducing runtime instruction execution induced PDN resonance noise.

Power distribution networks (PDNs) are designed and analyzed iteratively. Random walk is among the most efficient methods for PDN analysis. We develop in this paper an incremental and on-demand random walk to reduce iterative analysis time. During each iteration, we map the design changes as positive or negative random walks for observed nodes. To update PDN analysis result, we only need to apply these extra positive or negative walks, instead of doing all walks from scratch. We show that different execution orders for these walks do not affect accuracy but do affect the runtime because of the cancellation between positive and negative walks. Considering this cancellation effect, we optimize the walk order by solving a min-energy electromagnetic particles placement problem and, as a result, further reduce the runtime to about 8times compared to the worst order. Experiments show that, compared to random walk from scratch, our algorithm has similar accuracy but reduces the iterative analysis time by up to 18times for on-chip PDN sizing, and by up to 13times for package ball assignment with substrate routing. In addition, our incremental random walk has a linear time complexity with respect to the number of observed nodes and is more suitable for on-demand analysis, compared to random walk from scratch and its big warm-up cost.

Increasingly large process variations make selection of a set of critical paths for at-speed testing essential yet challenging. This paper proposes a novel multilayer process space coverage metric to quantitatively gauge the quality of path selection. To overcome the exponential complexity in computing such a metric, this paper reveals its relationship to a concept called order statistics for a set of correlated random variables, efficient computation of which is a hitherto open problem in the literature. This paper then develops an elegant recursive algorithm to compute the order statistics (or the metric) in provable linear time and space. With a novel data structure, the order statistics can also be incrementally updated. By employing a branch-and-bound path selection algorithm with above techniques, this paper shows that selecting an optimal set of paths for a multi-million-gate design can be performed efficiently. Compared to the state-of-the-art, experimental results show both the efficiency of our algorithms and better quality of our path selection.

Correct ordering of timing quantities is essential for both timing analysis and design optimization in the presence of process variation, because timing quantities are no longer a deterministic value, but a distribution. This paper proposes a novel metric, called tiered criticalities, which guarantees to provide a unique order for a set of correlated timing quantities while properly taking into account full process space coverage. Efficient algorithms are developed to compute this metric, and its effectiveness on path ranking for at-speed testing is also demonstrated.

Process variation is recognized as a major source of parametric yield loss, which occurs because a fraction of manufactured chips do not satisfy timing or power constraints. On the other hand, both chip performance and chip leakage power depend on supply voltage. This dependence can be used for converting the fraction of too slow or too leaky chips into good ones by adjusting their supply voltage. This technique is called voltage binning [4]. All the manufactured chips are divided into groups (bins) and each group is assigned its individual supply voltage. This paper proposes a statistical technique of yield computation for different voltage binning schemes using results of statistical timing and variational power analysis. The paper formulates and solves the problem of computing optimal supply voltages for a given binning scheme.

For nanometer manufacturing, process variation causes significant uncertainty for circuit performance verification. Statistical static timing analysis (SSTA) is thus developed to estimate timing distribution under process variation. Most existing SSTA techniques have difficulty in handling the non-Gaussian variation distribution and nonlinear dependence of delay on variation sources. To address this problem, we first propose a new method to approximate the max operation of two non-Gaussian random variables through second-order polynomial fitting. With such approximation, we then present new non-Gaussian SSTA algorithms for three delay models: quadratic model, quadratic model without crossing terms (semiquadratic model), and linear model. All the atomic operations (max and sum) of our algorithms are performed by closed-form formulas; hence, they scale well for large designs. Experimental results show that compared to the Monte Carlo simulation, our approach predicts the mean, standard deviation, skewness, and 95% percentile point within 1%, 1%, 6%, and 1% error, respectively.

In the face of increased process variations, at-speed manufacturing test is necessary to detect subtle delay defects. This procedure necessarily tests chips at a slightly higher speed than the target frequency required in the field. The additional performance required on the tester is calledtestmargin. There are many good reasons for margin, including voltage and temperature requirements, incomplete test coverage, aging effects, coupling effects, and accounting for modeling inaccuracies. By taking advantage of statistical timing, this paper proposes an optimal method of test margin determination to maximize yield while staying within a prescribed shipped product quality loss limit. If process information is available from the wafer testing of scribe-line structures or on-chip process monitoring circuitry, this information can be leveraged to determine aper-chiptestmarginwhich can further improve yield.

Existing static timing methodologies apply various techniques to address increasingly larger process variations. The techniques include multi-corner timing, on-chip variation (OCV) derating coefficients, and path-based common path pessimism removal (CPPR) procedures. These techniques, however, destroy the benefits of linear run-time and incrementality possessed by classical static timing. The major contribution of this work is an efficient statistical timing methodology with comprehensive modeling of process variations, while at the same time retaining those key benefits. Our methodology is compatible with existing characterization methods and scales well to large chip designs. To achieve this goal, three techniques are developed: (1) building the statistical delay model based on existing multi-corner library characterization; (2) modeling spatial correlation in a scalable manner; and (3) avoiding the time-consuming CPPR procedure by removing common path pessimism in the clock network by an incremental block-based technique. Experimental results on industrial 90 nm ASIC designs show that the proposed timing methodology correctly handles all types of process variation, achieves high correlation with traditional multi-corner timing with more than 4 × speedup, and is a vehicle for pessimism reduction.

In the nanometer manufacturing region, process variation causes significant uncertainty for circuit performance verification. Statistical static timing analysis (SSTA) is thus developed to estimate timing distribution under process variation. However, most of the existing SSTA techniques have difficulty in handling the non-Gaussian variation distribution and non-linear dependency of delay on variation sources. To solve such a problem, in this paper, we first propose a new method to approximate the max operation of two non-Gaussian random variables through second-order polynomial fitting. We then present new non-Gaussian SSTA algorithms under two types of variational delay models: quadratic model and semi-quadratic model (i.e., quadratic model without crossing terms). All atomic operations (such as max and sum) of our algorithms are performed by closed-form formulas, hence they scale well for large designs. Experimental results show that compared to the Monte-Carlo simulation, our approach predicts the mean, standard deviation, and skewness within 1%, 1%, and 5% error, respectively. Our approach is more accurate and also 20x faster than the most recent method for non-Gaussian and nonlinear SSTA.

Criticality and yield gradients are two crucial diagnostic metrics obtained from statistical static timing analysis (SSTA). They provide valuable information to guide timing optimization and timing- driven physical synthesis. Existing work in the literature, however, computes both metrics in a non-incremental manner, i.e., after one or more changes are made in a previously-timed circuit, both metrics need to be recomputed from scratch, which is obviously undesirable for optimizing large circuits. The major contribution of this paper is to propose two novel techniques to compute both criticality and yield gradients efficiently and incrementally. In addition, while node and edge criticalities are addressed in the literature, this paper for the first time describes a technique to compute path criticalities. To further improve algorithmic efficiency, this paper also proposes a novel technique to update "chip slack" incrementally. Numerical results show our methods to be over two orders of magnitude faster than previous work.

In the face of increased process variations, at-speed manufacturing test is necessary to detect subtle delay defects. This procedure necessarily tests chips at a slightly higher speed than the target frequency required in the field. The additional performance required on the tester is called test margin. There are many good reasons for margin including voltage and temperature requirements, incomplete test coverage, aging effects, coupling effects and accounting for modeling inaccuracies. By taking advantage of statistical timing, this paper proposes an optimal method of test margin determination to maximize yield while staying within a prescribed shipped product quality loss (SPQL) limit. If process information is available from wafer testing of scribe line structures or on-chip process monitoring circuitry, this information can be leveraged to determine a per- chip test margin which can further improve yield.

An efficient method is proposed to consider the process variations with spatial correlation, for chip-level capacitance extraction based on the window technique. In each window, an efficient technique of Hermite polynomial collocation (HPC) is presented to extract the statistical capacitance. The capacitance covariances between windows are then calculated to reflect the spatial correlation. The proposed method is practical for chip-level extraction task, and the experiments on full-path extraction exhibit its high accuracy and efficiency.

Process variations make at-speed testing significantly more difficult. They cause subtle delay changes that are distributed rather than the localized nature of a traditional fault model. Due to parametric variations, different paths can be critical in different parts of the process space, and the union of such paths must be tested to obtain good process space coverage. This paper proposes a novel branch-and-bound algorithm that elegantly and efficiently solves the hitherto open problem of statistical path tracing. The resulting paths are used for at-speed structural testing. A new Test Quality Metric (TQM) is proposed and paths which maximize this metric are selected. After chip timing has been performed, the path selection procedure is extremely efficient. Path selection for a multi-million gate chip design can be completed in a matter of seconds.

This paper presents a fast and accurate solution, namely Fashion, to routability-driven global routing problem. Fashion is based on two efficient yet effective techniques: 1) dynamic pattern routing (DPR) and 2) movable-segment-driven DPR. These two techniques enable Fashion to explore large solution space to achieve high routability with low time complexity. Compared with BoxRouter, Fashion has a shorter wire length and reduces overflow and runtime by 5 and 15 times, respectively. Compared with FastRoute, Fashion has similar runtime but 90% smaller overflow and 1.9% shorter wire length. Fashion is significantly better than Labyrinth and Fengshui in terms of overflow, wire length, and runtime.

This paper solves the variation-aware decoupling capacitance (decap) budgeting problem. Unlike previous works which only consider worst case design, for the first time, we consider the input of both process variation and operation variation for decap budgeting. A novel stochastic current model is proposed that efficiently and accurately captures temporal correlation between clock cycles, logic-induced correlation between ports, and current variation due to process variation with spatial correlation. An iterative alternative programming algorithm that is applicable to a variety of current models is then developed. Compared with the baseline model which assumes maximum current peaks at all ports, the model considering temporal correlation reduces noise by up to 5times, and the model considering both temporal and logic-induced correlations reduces noise by up to 17times. Compared with using deterministic process parameters, considering process variation (in particular Leffvariation) reduces the mean noise by up to 4times and 3sigma noise by up to 13times when both applying the current model with temporal and logic-induced correlations. Note that stochastic optimization has been used mainly for process variation in the literature, but this paper convincingly demonstrate that stochastic optimization considering operation variation is effective to reduce overdesign introduced by worst case design for power integrity. Such stochastic optimization has a wide scope of applications to design problems. To the best of our knowledge, this is the first in-depth study on decap insertion for power network design considering current correlations including process variation.

This paper presents a fast and accurate global routing algorithm, DpRouter, based on two efficient techniques: (1) dynamic pattern routing (Dpr), and (2) segment movement. These two techniques enable DpRouter to explore large solution space to achieve better routability with low time complexity. Compared with the state-of-the-arts, experimental results show that we consistently obtain better routing quality in terms of both congestion and wire length, while simultaneously achieving a more than 30x runtime speedup. We envision that this algorithm can be further leveraged in other routing applications, such as FPGA routing.

Existing statistical static timing analysis (SSTA) techniques suffer from limited modeling capability by using a linear delay model with Gaussian distribution, or have scalability problems due to expensive operations involved to handle non-Gaussian variation sources or non-linear delays. To overcome these limitations, we propose a novel SSTA technique to handle both nonlinear delay dependency and non-Gaussian variation sources simultaneously. We develop efficient algorithms to perform all statistical atomic operations (such as max and add) efficiently via either closed-form formulas or one-dimensional lookup tables. The resulting timing quantity provably preserves the correlation with variation sources to the third-order. We prove that the complexity of our algorithm is linear in both variation sources and circuit sizes, hence our algorithm scales well for large designs. Compared to Monte Carlo simulation for non-Gaussian variation sources and nonlinear delay models, our approach predicts all timing characteristics of circuit delay with less than 2% error.

Meeting the tight performance specifications mandated by the customer is critical for contract manufactured ASICs. To address this, at speed test has been employed to detect subtle delay failures in manufacturing. However, the increasing process spread in advanced nanometer ASICs poses considerable challenges to predicting hardware performance from timing models. Performance verification in the pres- ence of process variation is difficult because the critical path is no longer unique. Different paths become frequency limiting in different process corners. In this paper, we present a novel variation-aware method based on statistical timing to select critical paths for structural test. Node criticalities are computed to determine the probabilities of different circuit nodes being on the critical path across process variation.Moreover, path delays are projected into different process corners using their linear delay function forms. Experimental results for three multimillion gate ASICs demonstrate the effectiveness of our methods.

This paper solves the variation-aware on-chip decoupling capacitance (decap) budgeting problem. Unlike previous work assuming the worst-case current load, we develop a novel stochastic current model, which efficiently and accurately captures operation variation such as temporal correlation between clock cycles and logic-induced correlation between ports. The models also considers current variation due to process variation with spatial correlation. We then propose an iterative alternative programming algorithm to solve the decap budgeting problem under the stochastic current model. Experiments using industrial examples show that compared with the baseline model which assumes maximum currents at all ports and under the same decap area constraint, the model considering temporal correlation reduces the noise by up to 5times, and the model considering both temporal and logic-induced correlations reduces the noise by up to 17times. Compared with the model using deterministic process parameters, considering process variation tLej f variation in this paper reduces the mean noise by up to 4times and the 3 sigma noise by up to 13times. While the existing stochastic optimization has been used mainly for process variation purpose, this paper to the best of our knowledge is the first in-depth study on stochastic optimization taking into account both operation and process variations for power network design. We convincingly show that considering operation variation is highly beneficial for power integrity optimization and this should be researched for optimizing signal and thermal integrity as well.

In ultra-deep sub-micron technologies, modeling waveform shapes correctly is essential for accurate timing and noise analysis. Due to process and environmental variations, there is a need for a variational waveform model that is compact, efficient and accurate. The mode) should capture correlations due to common dependence on process parameters. This paper proposes a waveform model derived from basic transformations of a nominal waveform in the absence of variations. The transformations are parameterized by variational quantities that capture the sensitivity of the waveform to process parameters. The resulting waveform model works well with current-source models for static timing analysis. Numerical results are presented to demonstrate the accuracy of the model both in capturing variational waveforms and in propagating waveforms through logic gates.

Abstract—This paper presents extensions of the dynamicprogramming (DP) framework to consider buffer insertion and wire-sizing under effects of process variation. We study the effectiveness of this approach to reduce timing impact caused by chemical–mechanical planarization (CMP)-induced systematic variation and random Leffprocess variation in devices. We first present a quantitative study on the impact of CMP to interconnect parasitics. We then introduce a simple extension to handle CMP effects in the buffer insertion and wire sizing problem by simultaneously considering fill insertion (SBWF).We also tackle the same problem but with random Leffprocess variation (vSBWF) by incorporating statistical timing into the DP framework. We develop an efficient yet accurate heuristic pruning rule to approximate the computationally expensive statistical problem. Experiments under conservative assumption on process variation show that SBWF algorithm obtains 1.6% timing improvement over the variationunaware solution. Moreover, our statistical vSBWF algorithm results in 43.1% yield improvement on average. We also show that our approaches have polynomial time complexity with respect to the net-size. The proposed extensions on the DP framework is orthogonal to other power/area-constrained problems under the same framework, which has been extensively studied in the literature.

We propose a provably transitive-closure ordering rule with theoretical foundations to prune suboptimal design solutions in the presence of process variations. As an example, this probabilistic ordering rule is applied to develop an efficient variational buffering algorithm. Compared to the conventional deterministic approach, variational buffering improves the parametric timing yield by 15.7% on average. This transitive-closure ordering rule may be leveraged to solve other computer-aided-design problems considering process variation effects

The increased variability of process parameters makes it important yet challenging to extract the statistical characteristics and spatial correlation of process variation. Recent progress in statistical static-timing analysis also makes the extraction important for modern chip designs. Existing approaches extract either only a deterministic component of spatial variation or these approaches do not consider the actual difficulties in computing a valid spatial-correlation function, ignoring the fact that not every function and matrix can be used to describe the spatial correlation. Applying mathematical theories from random fields and convex analysis, we develop: 1) a robust technique to extract a valid spatial-correlation function by solving a constrained nonlinear optimization problem and 2) a robust technique to extract a valid spatial-correlation matrix by employing a modified alternative-projection algorithm. Our novel techniques guarantee to extract a valid spatial-correlation function and matrix from measurement data, even if those measurements are affected by unavoidable random noises. Experiment results, obtained from data generated by a Monte Carlo model, confirm the accuracy and robustness of our techniques and show that we are able to recover the correlation function and matrix with very high accuracy even in the presence of significant random noises

System-on-chip and system-in-package result in increased number of I/O cells and complicated constraints for both chip designs and package designs. This renders the traditional manually tuned and chip-centered I/O designs suboptimal in terms of both turn around time and design quality. In this paper, we formally introduce a set of design constraints suitable for chip-package co-design. We formulate a constraint-driven I/O planning and placement problem, and solve it by a multi-step algorithm based upon integer linear programming. Experiment results using real industry designs show that the proposed algorithm can effectively find a large scale I/O placement solution and satisfy all given design constraints in less than 10 minutes. In contrast, the state-of-the-art without considering those design constraints simply cannot meet all design constraints by relying solely upon the conventional iterative approach

Chips manufactured in 90 nm technology have shown large parametric variations, and a worsening trend is predicted. These parametric variations make circuit optimization difficult since different paths are frequency-limiting in different parts of the multi-dimensional process space. Therefore, it is desirable to have a new diagnostic metric for robust circuit optimization. This paper presents a novel algorithm to compute the criticality probability of every edge in the timing graph of a design with linear complexity in the circuit size. Using industrial benchmarks, we verify the correctness of our criticality computation via Monte Carlo simulation. We also show that for large industrial designs with 442,000 gates, our algorithm computes all edge criticalities in less than 160 seconds.

Both custom IC and FPGA designs in the nanometer regime suffer from process variations. But different from custom ICs, FPGAs, programmability offers a unique design freedom to leverage process variation and improve circuit performance. We propose the following variation aware chip-wise placement flow in this paper. First, we obtain the variation map for each chip by synthesizing the test circuits for each chip as a preprocessing step before detailed placement. Then we use the trace-based method to estimate the performance gain achievable by chipwise placement. Such estimation provides a lower bound of the performance gain without detailed placement. Finally, if the gain is significant, a variation aware chipwise placement is used to place the circuits according to the variation map for each chip. Our experimental results show that, compared to the existing FPGA placement, variation aware chipwise placement improves circuit performance by up to 19.3% for the tested variation maps.

A comprehensive probabilistic methodology is proposed to solve the buer insertion problem with the consideration of process variations. In contrast to a recent work, we point out, for the rst time, that the correlation between the required arrival time and the downstream loading ca-pacitance must be considered in order to solve the problem \\correctly". We develop an ecient bottom-up recursive al-gorithm to calculate the joint probability density function that accurately captures the above correlation, and propose eective pruning rules to exclude probabilistically inferior solutions. We verify our buer insertion using timing anal-ysis with both device and interconnect variations, and show that compared to the conventional buer insertion algorithm using nominal device and interconnect parameters, our new buer insertion methodology can reduce the probability of timing violation by up to 30%. 1.

Increased variability of process parameters and recent progress in statistical static timing analysis make extraction of statistical characteristics of process variation and spatial correlation an important yet challenging problem in modern chip designs. Unfortunately, existing approaches either focus on extraction of only a deterministic component of spatial variation or do not consider actual difficulties in computing a valid spatial correlation function and matrix, simply ignoring the fact that not every function and matrix can be used to describe the spatial correlation. Based upon the mathematical theory of random fields and convex analysis, in this paper, we develop (1) a robust technique to extract a valid spatial correlation function by solving a constrained nonlinear optimization problem; and (2) a robust technique to extract a valid spatial correlation matrix by employing a modified alternative projection algorithm.Our novel techniques guarantee to extract a valid spatial correlation function and matrix that are closest to measurement data, even if those measurements are affected by unavoidable random noises. Experiment results based upon a Monte-Carlo model confirm the accuracy and robustness of our techniques, and show that we are able to recover the correlation function and matrix with very high accuracy even in the presence of significant random noises.

This paper presents a novel global routing algorithm, AT-PO-GR, to minimize the routing area under both congestion, timing, and RLC crosstalk constraints. The proposed algorithm is consisted of three key parts: (1) timing and congestion optimization; (2) crosstalk budgeting and estimation; and (3) crosstalk elimination and local refinement. Compared with the recent work introduced in [9] and [10], the proposed algorithm can achieve smaller routing area and fewer shields under the same design constraints, yet use less running time.

We extend an existing probabilistic congestion model to consider shielding for crosstalk reduction. We then develop a multilevel router to study the impact of various congestion models on routing congestion by using large industrial design examples. We show that (1) when shielding is applied as a post-routing optimization for crosstalk reduction, the existing probabilistic model, when compared to a deterministic routing-order dependent congestion model, reduces routing congestion by 17.1% on average under the given routing area constraints, or reduces routing area by 9.4% on average under the given routing congestion constraints; (2) our extended probabilistic congestion model considering shielding enables shielding reservation and minimization for routing and achieves routing congestion (or area) reduction by 47.7% (or 31.0%) on average under the given routing area (or congestion) constraints, when compared to the above deterministic congestion model not able to estimate shielding and therefore not able to minimize shielding during routing.

A comprehensive probabilistic methodology is proposed to solve the buffer insertion problem with the consideration of process variations. In contrast to a recent work, we point out, for the first time, that the correlation between the required arrival time and the downstream loading capacitance must be considered in order to solve the problem "correctly". We develop an efficient bottom-up recursive algorithm to calculate the joint probability density function that accurately captures the above correlation, and propose effective pruning rules to exclude probabilistically inferior solutions. We verify our buffer insertion using timing analysis with both device and interconnect variations, and show that compared to the conventional buffer insertion algorithm using nominal device and interconnect parameters, our new buffer insertion methodology can reduce the probability of timing violation by up to 30%.

Abstract—This paper presents extensions of the dynamic-programming (DP) framework to consider buffer insertion and wire-sizing under effects of process variation. We study the effectiveness of this approach to reduce timing impact caused by chemical–mechanical planarization (CMP)-induced systematic variation and random Leff process variation in devices. We first present a quantitative study on the impact of CMP to interconnect parasitics. We then introduce a simple extension to handle CMP effects in the buffer insertion and wire sizing problem by simulta-neously considering fill insertion (SBWF). We also tackle the same problem but with random Leff process variation (vSBWF) by in-corporating statistical timing into the DP framework. We develop an efficient yet accurate heuristic pruning rule to approximate the computationally expensive statistical problem. Experiments under conservative assumption on process variation show that SBWF algorithm obtains 1.6 % timing improvement over the variation-unaware solution. Moreover, our statistical vSBWF algorithm results in 43.1 % yield improvement on average. We also show that our approaches have polynomial time complexity with respect to the net-size. The proposed extensions on the DP framework is orthogonal to other power/area-constrained problems under the same framework, which has been extensively studied in the literature. Index Terms—Buffering, dummy fill insertion, fill patterns, interconnect optimization, process variation, random Leff variation, systematic CMP variation, wire sizing. I.

In this paper, we study an extended global routing problem with RLC crosstalk constraints. Considering simultaneous shield insertion and net ordering, we propose a multiphase algorithm to synthesize a global routing solution with track assignment to satisfy the RLC crosstalk constraint at each sink. The key algorithm phase is global routing synthesis with shield reservation and minimization based on prerouting shield estimation. Experiments using large industrial benchmarks show that compared to the best alternative with postrouting shield insertion and net ordering, the proposed algorithm with shield reservation and minimization reduces the congestion by 18.4% with a smaller runtime. To the best of our knowledge, this is the first in-depth study on global routing synthesis with RLC crosstalk constraints.

Conventional physical design flow separates the design of power network and signal network. Such a separated approach results in slow design convergence for wire-limited deep sub-micron designs. We present a novel design methodology that simultaneously considers global signal routing and power network design under integrity constraints. The key part to this approach is a simple yet accurate power net estimation formula that decides the minimum number of power nets needed to satisfy both power and signal integrity constraints prior to detailed layout. The proposed design methodology is a one-pass solution to the co-design of power and signal networks in the sense that no iteration between them is required in order to meet design closure. Experiment results using large industrial benchmarks show that compared to the state-of-the-art alternative design approach, the proposed method can reduce the power network area by 19.4% on average under the same signal and power integrity constraints with better routing quality, but use less runtime.

Considering the voltage drop constraint over a distributed model for power/ground (P/G) network, we study the following two problems for physical synthesis of sleep transistors: the min-area sleep transistor insertion (and sizing) (T IS) problem with respect to a fixed P/G network, and the simultaneous sleep transistor insertion and P/G network sizing (T IPGS) problem to minimize the weighted area of sleep transistors and P/G network. We show that there may exist multiple sleep transistor insertion solutions that all lead to a same minimum area in the T IS and T IPGS problems. We develop optimal algorithms to T IS and T IPGS problems by modeling the circuit as a single current source, and then extend to the case modeling the circuit as distributed current sources. Compared with the best known approach, our algorithms achieve area reduction by up to 44.1% and 61.3% for T IS and T IPGS, respectively.

Existing layout-optimization methods for both capacitive and inductive (RLC) crosstalk reduction assume a set of interconnects with a priori given crosstalk bounds in a routing region. RLC crosstalk budgeting is critical for effectively applying these methods at the full-chip level. In this paper, we formulate a full-chip routing optimization problem with RLC crosstalk budgeting, and solve this problem with a multiphase algorithm. In phase I, we solve an optimal RLC crosstalk budgeting based on linear programming to partition crosstalk bounds at sinks into bounds for net segments in routing regions. In phase II, we perform simultaneous shield insertion and net ordering to meet the partitioned crosstalk bounds in each region. In phase III, we carry out a local refinement procedure to reduce the total number of shields. Compared with the best alternative approach in experiments, the proposed algorithm reduces the total routing area by up to 5.71% and uses less runtime. To the best of our knowledge, this work is the first in-depth study on full-chip routing optimization with RLC crosstalk budgeting.

Existing layout optimization methods often assume a set of interconnects with given RLC crosstalk bounds in a routing region. RLC crosstalk bound partitioning is critical for effectively applying these methods at the full-chip level. In this paper, we develop an optimal crosstalk budgeting scheme based on linear programming (LP) formulation, and apply it to shield insertion and net ordering at the full-chip level. Experiment results show that compared to the best alternative approach, the LP based method reduces the total routing area by up to 7.61% and also uses less runtime. To the best of our knowledge, this is the first in-depth work that studies the RLC crosstalk budgeting problem.