Recently, sparse tensor algebra (SpTA) plays an increasingly important role in machine learning. However, due to the unstructured sparsity of SpTA, the general-purpose processors (e.g., GPU and CPU) are inefficient because of the underutilized hardware resources. Sparse kernel accelerators are optimized for specific tasks. However, their dedicated processing units and data paths cannot effectively support other SpTA tasks with different dataflow and various sparsity, resulting in performance degradation. This paper proposes FEASTA, a Flexible and Efficient Accelerator for Sparse Tensor Algebra. To process general SpTA tasks with various sparsity efficiently, we design FEASTA meticulously from three levels. At the dataflow abstraction level, we apply the Einstein Summation on the sparse fiber tree data structure to model the unified execution flow of general SpTA as joining and merging the fiber tree. At the instruction set architecture (ISA) level, a general SpTA ISA is proposed based on the execution flow. It includes different types of instructions for dense and sparse data, achieving flexibility and efficiency at the instruction level. At the architecture level, an instruction-driven architecture consisting of configurable and high-performance function units is designed, supporting the flexible and efficient ISA. Evaluations show that FEASTA has 5.40× geomean energy efficiency improvements compared to GPU among various workloads. FEASTA delivers 1.47× and 3.19× higher performance on sparse matrix multiplication kernels compared to state-of-the-art sparse matrix accelerator and CPU extension. Across diverse kernels, FEASTA achieves 1.69-12.70× energy efficiency over existing architectures.

Sparse Matrix-Matrix Multiplication (SpMM) is one of the key operators in many fields, showing dynamic features in terms of sparsity, element distribution, and data dependency. Previous studies have proposed FPGA-based SpMM accelerators with fixed configurations of on-chip dataflow, leaving three major challenges unsolved: 1) Partitioning matrices with the fixed sub-matrix size to fit limited on-chip buffer on FPGA leads to performance loss because the optimal sub-matrix size to minimize memory access varies with dynamic sparsity. 2) The fixed row-wise allocation scheme of sparse elements in streaming architecture leads to unbalanced workloads because of dynamic element distribution across sparse matrix rows. 3) Read-after-write (RAW) hazard caused by floating-point adder makes the elements in one row cannot be processed consecutively. Architectures with fixed execution order rely on time-consuming pre-processing to deal with dynamic data dependency. Motivated by the observation that fixed configurations lead to performance loss, we propose DySpMM by introducing the dynamic design methodology to SpMM architectures. The configurable data distributor is introduced to enable dynamic sub-matrix size, achieving up to 3.79× less memory access amount. The element-wise allocator is designed for dynamic workload balance, improving utilization up to 3.74×. The interleaved reorder unit is proposed to reorder the elements and dynamically avoid RAW hazards at runtime, avoiding time-consuming pre-processing. We implement DySpMM on U280 FPGA, and the evaluation shows that it achieves 1.42× geomean throughput compared with the state-of-the-art accelerator Sextans and 1.78× energy efficiency compared with V100S GPU.

Graph Attention Network (GAT) has demonstrated better performance in many graph tasks than previous Graph Neural Networks (GNN). However, it involves graph attention operations with extra computing complexity. While a large amount of existing literature has researched GNN acceleration, few have focused on the attention mechanism in GAT. The graph attention mechanism makes the computation flow different. Therefore, previous GNN accelerators can not support GAT well. Besides, GAT distinguishes the importance of neighbors and makes it possible to reduce the workload through runtime tailoring. We present NTGAT, a software-hardware co-design approach to accelerate GAT with runtime node tailoring. Our work comprises both a runtime node tailoring algorithm and an accelerator design. We propose a pipeline sorting method and a hardware unit to support node tailoring during inference. The experiments show that our algorithm can reduce up to 86% of aggregation workload while incurring slight accuracy loss (<0.4%). And the FPGA based accelerator can achieve up to 3.8× speedup and 4.98× energy efficiency comparing to the GPU baseline.

The 3D point cloud neural networks, including point-based and voxel-based networks, play an essential role in various 3D applications. Many previous works have proposed dedicated accelerators to speed up 3D point cloud neural network processing. Yet, two major challenges still exist: (1) Inefficient memory access due to large off-chip data access volume. The point-based method visits massive redundant points, while the voxel-based method fails to reuse on-chip voxel data, leading to up to 983× data access compared with original input data. (2) Poor scalability due to low computing unit utilization. The computing unit is under-utilized when scaled with a larger computing array size, as low as 16.37% when scaling the current accelerator’s computing capability to general-purpose processors (e.g., GPUs).To solve the above challenges, we propose MARS, a memory access reduced and scalable accelerator for both point-based and voxel-based 3D point cloud neural networks. To reduce the memory access, MARS filters out unnecessary off-chip point data access by 6.52× in volume for point-based networks and increases on-chip data reuse to reduce off-chip data access by 26.31× for voxel-based networks. To improve scalability, MARS also features an elastic computing array architecture that can be dynamically configured at runtime to fit different tasks, providing 7.09× higher computing unit utilization. Extensive experiments show that MARS achieves 1.76× over speedup and 3.97× PointAcc for point-based and end-to-end voxel-based point cloud neural networks, respectively.

As a new algorithm of graph embedding, graph neural networks (GNNs) have been widely used in many fields. However, GNN computing has the characteristics of both sparse graph processing and dense neural network, which make it difficult to be deployed efficiently on the existing graph processing accelerators or neural network accelerators. Recently, some GNN accelerators have been proposed, but the following challenges have not been fully solved: 1) the minibatch GNN inference scenario has the potential of software and hardware co-design, which can bring 30% computation amount reduction, and this is not well utilized. Besides, the cost of message flow graph construction is large and may account for more than 50% of the total delay; 2) the feature aggregation has a large amount of data access and relatively small amount of computation, which leads to low on-chip data reuse, only 10% of dense computing; and 3) without the optimization of sparse computing units, simple memory bank and cross bar architecture can easily lead to bank access conflict and load imbalance, reducing the utilization of computing units to less than 60%. In order to solve the above problems, we propose a algorithm-hardware co-design scheme to accelerate GNN inference, which includes three technologies: 1) a reuse-aware sampling method is proposed for minibatch inference scenarios, which reduces 30% of the calculation and improves the on-chip reusability of local data; 2) through the nodewise parallelism-aware quantization, the features and weights are quantized to integers with eight or four bits, which reduces the amount of memory access by at least four times; and 3) an accelerator supporting the above technologies is designed and evaluated, and different operations are supported by the sampling-inference integration architecture. The multibank on-chip memory pool is designed to support data reuse, and edge stream reordering is used to reduce data access conflicts, improving the utilization of computing units by$1.5\times $. Combined with the above technologies, the experiments show that our design achieves$9.2\times $speedup and$29\times $energy efficiency improvement compared with the Deep Graph Library framework running on servers equipped with CPU and GPU.

Recently, Graph Convolutional Networks (GCNs) have shown powerful learning capabilities in graph processing tasks. Computing GCNs with conventional von Neumann architectures usually suffers from limited memory bandwidth due to the irregular memory access. Recent work has proposed Processing-In-Memory (PIM) architectures to overcome the bandwidth bottleneck in Convolutional Neural Networks (CNNs) by performing in-situ matrix-vector multiplication. However, the performance improvement and computation parallelism of existing CNN-oriented PIM architectures is hindered when performing GCNs because of the large scale and sparsity of graphs. To tackle these problems, this paper presents a parallelism enhancement framework for PIM-based GCN architectures. At the software level, we propose a fixed-point quantization method for GCNs, which reduces the PIM computation overhead with little accuracy loss. We also introduce the vertex clustering algorithm to the graph, minimizing the inter-cluster links and realizing cluster-level parallel computing on multi-core systems. At the hardware level, we design a Resistive Random Access Memory (RRAM) based multi-core PIM architecture for GCN, which supports the cluster-level parallelism. Besides, we propose a coarse-grained pipeline dataflow to cover the RRAM write costs and improve the GCN computation throughput. At the software/hardware interface level, we propose a PIM-aware GCN mapping strategy to achieve the optimal tradeoff between resource utilization and computation performance. We also propose edge dropping methods to reduce the inter-core communications with little accuracy loss. We evaluate our framework on typical datasets with multiple widely-used GCN models. Experimental results show that the proposed framework achieves$698\times, 89\times$, and$41\times$speedup with$7108\times,255\times$, and$31\times$energy efficiency enhancement compared with CPUs, GPUs, and ASICs, respectively.

Convolutional neural networks (CNNs) have been widely used in many tasks, but training CNNs is time consuming and energy hungry. Using the low-bit integer format has been proved promising for speeding up and improving the energy efficiency of CNN inference, while CNN training can hardly benefit from such a technique because of the following challenges: 1) the integer data format cannot meet the requirements of the data dynamic range in training, resulting in the accuracy drop; 2) the floating-point data format keeps sizeable dynamic range with much more exponent bits, thus using it results in higher accumulation power than using the integer data format; and 3) there are some specially designed data formats (e.g., with group-wise scaling) that have the potential to deal with the former two problems but common hardware platforms cannot support them efficiently. To tackle all these challenges and make the training phase of CNNs benefit from the low-bit format, we propose a low-bit training framework for CNNs to pursue a better tradeoff between accuracy and energy efficiency: 1) we adopt element-wise scaling to increase the dynamic range of data representation, which significantly reduces the quantization error; 2) group-wise scaling with hardware friendly factor format is designed to reduce the element-wise exponent bits without degrading the accuracy; and 3) we design the customized hardware unit that implements the low-bit tensor convolution arithmetic with our multilevel scaling data format. Experiments show that our framework achieves a superior tradeoff between the accuracy and the bit-width than previous low-bit training studies. For training various models on CIFAR-10, using 1-bit mantissa and 2-bit exponent is adequate to keep the accuracy loss within 1%. On larger datasets like ImageNet, using 4-bit mantissa and 2-bit exponent is adequate. Through the energy consumption simulation of the whole network, we can see that training a variety of models with our framework could achieve$4.9\times $–$10.2\times $higher energy efficiency than full-precision arithmetic.

INFerence-as-a-Service (INFaaS) has become a primary workload in the cloud. However, existing FPGA-based Deep Neural Network (DNN) accelerators are mainly optimized for the fastest speed of a single task, while the multi-tenancy of INFaaS has not been explored yet. As the demand for INFaaS keeps growing, simply increasing the number of FPGA-based DNN accelerators is not cost-effective, while merely sharing these single-task optimized DNN accelerators in a time-division multiplexing way could lead to poor isolation and high-performance loss for INFaaS. On the other hand, current cloud-based DNN accelerators have excessive compilation overhead, especially when scaling out to multi-FPGA systems for multi-tenant sharing, leading to unacceptable compilation costs for both offline deployment and online reconfiguration. Therefore, it is far from providing efficient and flexible FPGA virtualization for public and private cloud scenarios. Aiming to solve these problems, we propose a unified virtualization framework for general-purpose deep neural networks in the cloud, enabling multi-tenant sharing for both the Convolution Neural Network (CNN), and the Recurrent Neural Network (RNN) accelerators on a single FPGA. The isolation is enabled by introducing a two-level instruction dispatch module and a multi-core based hardware resources pool. Such designs provide isolated and runtime-programmable hardware resources, which further leads to performance isolation for multi-tenant sharing. On the other hand, to overcome the heavy re-compilation overheads, a tiling-based instruction frame package design and a two-stage static-dynamic compilation, are proposed. Only the lightweight runtime information is re-compiled with ∼1 ms overhead, thus guaranteeing the private cloud’s performance. Finally, the extensive experimental results show that the proposed virtualized solutions achieve up to 3.12× and 6.18× higher throughput in the private cloud compared with the static CNN and RNN baseline designs, respectively.

With the down-scaling of CMOS technology, the design complexity of very large-scale integrated is increasing. Although the application of machine learning (ML) techniques in electronic design automation (EDA) can trace its history back to the 1990s, the recent breakthrough of ML and the increasing complexity of EDA tasks have aroused more interest in incorporating ML to solve EDA tasks. In this article, we present a comprehensive review of existing ML for EDA studies, organized following the EDA hierarchy.

FPGAs have shown great potential in providing low-latency and energy-efficient solutions for deep neural network (DNN) inference applications. Currently, the majority of FPGA-based DNN accelerators in the cloud run in a time-division multiplexing way for multiple users sharing a single FPGA, and require re-compilation with $\sim$100s overhead. Such designs lead to poor isolation and heavy performance loss for multiple users, which are far away from providing efficient and flexible FPGA virtualization for neither public nor private cloud scenarios. To solve these problems, we introduce a novel virtualization framework for instruction architecture set (ISA) based on DNN accelerators by sharing a single FPGA. We enable the isolation by introducing a two-level instruction dispatch module and a multi-core based hardware resources pool. Such designs provide isolated and runtime-programmable hardware resources, further leading to performance isolation for multiple users. On the other hand, to overcome the heavy re-compilation overheads, we propose a tiling-based instruction frame package design and two-stage static-dynamic compilation. Only the light-weight runtime information is re-compiled with $\sim$1 ms overhead, thus the performance is guaranteed for the private cloud. Our extensive experimental results show that the proposed virtualization design achieves 1.07-1.69x and 1.88-3.12x throughput improvement over previous static designs using the single-core and the multi-core architectures, respectively.

FPGAs have shown great potential in providing low-latency and energy-efficient solutions for deep learning applications, especially for the deep neural network (DNN). Currently, the majority of FPGA based DNN accelerators are designed for single-task and static-workload applications, making it difficult to adapt to the multi-task and dynamic-workload applications in the cloud. To meet these requirements, DNN accelerators need to support multi-task concurrent execution and low-overhead runtime resources reconfiguration. However, neither instruction set architecture (ISA) based nor template-based FPGA accelerators can support both functions at the same time. In this paper, we introduce a novel FPGA virtualization framework for ISA-based DNN accelerators in the cloud. As for the design goals of supporting multi-task and runtime reconfiguration, we propose a two-level instruction dispatch module and deep learning hardware resources pooling technique at the hardware level. As for the software level, we propose a tiling-based instruction frame package design and two-stage static-dynamic compilation. Furthermore, we propose a history information aware scheduling algorithm for the proposed ISA-based deep learning accelerators in the cloud scenario. According to our evaluation on Xilinx VU9P FPGA, the proposed virtualization method achieves 1.88x to 2.20x higher throughput and 1.36x to 1.77x lower latency against the static baseline design.

Consider a standard recommendation/retrieval problem where given a query, the goal is to retrieve the most relevant items. Inductive matrix completion (IMC) method is a standard approach for this problem where the given query as well as the items are embedded in a common low-dimensional space. The inner product between a query embedding and an item embedding reflects relevance of the (query, item) pair. Non-linear IMC (NIMC) uses non-linear networks to embed the query as well as items, and is known to be highly effective for a variety of tasks, such as video recommendations for users, semantic web search, etc. Despite its wide usage, existing literature lacks rigorous understanding of NIMC models. A key challenge in analyzing such models is to deal with the non-convexity arising out of non-linear embeddings in addition to the non-convexity arising out of the low-dimensional restriction of the embedding space, which is akin to the low-rank restriction in the standard matrix completion problem. In this paper, we provide the first theoretical analysis for a simple NIMC model in the realizable setting, where the relevance score of a (query, item) pair is formulated as the inner product between their single-layer neural representations. Our results show that under mild assumptions we can recover the ground truth parameters of the NIMC model using standard (stochastic) gradient descent methods if the methods are initialized within a small distance to the optimal parameters. We show that a standard tensor method can be used to initialize the solution within the required distance to the optimal parameters. Furthermore, we show that the number of query-item relevance observations required, a key parameter in learning such models, scales nearly linearly with the input dimensionality thus matching existing results for the standard linear inductive matrix completion.

With the dramatic increase in the complexity of modern integrated circuits (ICs), direct analysis and verification of IC power distribution networks (PDNs) have become extremely computationally expensive. Various power grid reduction methods are proposed to reduce the grid size for fast verification and simulation but usually suffer from poor scalability. In this paper, we present a convex optimization-based framework for power grid reduction. Edge sparsification is formulated as a weighted convex optimization problem with sparsity-inducing penalties, which provides an accurate control over the final error. A greedy coordinate descent (GCD) method with optimality guarantee is proposed along with a novel coordinate selection strategy to improve the efficiency and accuracy of edge sparsification. Experimental results demonstrate that the proposed approach achieves better performance compared with traditional gradient descent methods, and 98% accuracy and good sparsity for industrial benchmarks.

In this paper, we consider regression problems with one-hidden-layer neural networks (1NNs). We distill some properties of activation functions that lead to local strong convexity in the neighborhood of the ground-truth parameters for the 1NN squared-loss objective and most popular nonlinear activation functions satisfy the distilled properties, including rectified linear units (ReLUs), leaky ReLUs, squared ReLUs and sigmoids. For activation functions that are also smooth, we show local linear convergence guarantees of gradient descent under a resampling rule. For homogeneous activations, we show tensor methods are able to initialize the parameters to fall into the local strong convexity region. As a result, tensor initialization followed by gradient descent is guaranteed to recover the ground truth with sample complexity $ d \cdot \log(1/\epsilon) \cdot \mathrm{poly}(k,\lambda )$ and computational complexity $n\cdot d \cdot \mathrm{poly}(k,\lambda) $ for smooth homogeneous activations with high probability, where $d$ is the dimension of the input, $k$ ($k\leq d$) is the number of hidden nodes, $\lambda$ is a conditioning property of the ground-truth parameter matrix between the input layer and the hidden layer, $\epsilon$ is the targeted precision and $n$ is the number of samples. To the best of our knowledge, this is the first work that provides recovery guarantees for 1NNs with both sample complexity and computational complexity linear in the input dimension and logarithmic in the precision.

This paper considers the problem of safe mission planning of dynamic systems operating under uncertain environments. Much of the prior work on achieving robust and safe control requires solving second-order cone programs (SOCP). Unfortunately, existing general purpose SOCP methods are often infeasible for real-time robotic tasks due to high memory and computational requirements imposed by existing general optimization methods. The key contribution of this paper is a fast and memory-efficient algorithm for SOCP that would enable robust and safe mission planning on-board robots in realtime. Our algorithm does not have any external dependency, can efficiently utilize warm start provided in safe planning settings, and in fact leads to significant speed up over standard optimization packages (like SDPT3) for even standard SOCP problems. For example, for a standard quadrotor problem, our method leads to speedup of 1000× over SDPT3 without any deterioration in the solution quality. Our method is based on two insights: a) SOCPs can be interpreted as optimizing a function over a polytope with infinite sides, b) a linear function can be efficiently optimized over this polytope. We combine the above observations with a novel utilization of Wolfe's algorithm [1] to obtain an efficient optimization method that can be easily implemented on small embedded devices. In addition to the above mentioned algorithm, we also design a two-level sensing method based on Gaussian Process for complex obstacles with non-linear boundaries such as a cylinder.

The execution-simulation gap (ESG) is a fundamental property of public physical unclonable function (PPUF), which exploits the time gap between direct IC execution and computer simulation. ESG needs to consider both advanced computing scheme, including parallel and approximate computing scheme, and IC physical realization. In this paper, we propose a novel PPUF design, whose execution is equivalent to solving the hard-to-parallel and hard-to-approximate max-flow problem in a complete graph on chip. Thus, max-flow problem can be used as the simulation model to bound the ESG rigorously. To enable an efficient physical realization, we propose a crossbar structure and adopt source degeneration technique to map the graph topology on chip. The difference on asymptotic scaling between execution delay and simulation time is examined in the experimental results. The measurability of output difference is also verified to prove the physical practicality.

In this paper, we study the mixed linear regression (MLR) problem, where the goal is to recover multiple underlying linear models from their unlabeled linear measurements. We propose a non-convex objective function which we show is {\em locally strongly convex} in the neighborhood of the ground truth. We use a tensor method for initialization so that the initial models are in the local strong convexity region. We then employ general convex optimization algorithms to minimize the objective function. To the best of our knowledge, our approach provides first exact recovery guarantees for the MLR problem with $K \geq 2$ components. Moreover, our method has near-optimal computational complexity $\tilde O (Nd)$ as well as near-optimal sample complexity $\tilde O (d)$ for {\em constant} $K$. Furthermore, we show that our non-convex formulation can be extended to solving the {\em subspace clustering} problem as well. In particular, when initialized within a small constant distance to the true subspaces, our method converges to the global optima (and recovers true subspaces) in time {\em linear} in the number of points. Furthermore, our empirical results indicate that even with random initialization, our approach converges to the global optima in linear time, providing speed-up of up to two orders of magnitude.