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

Sparsity, which occurs in both scientific applications and Deep Learning (DL) models, has been a key target of optimization within recent ASIC accelerators due to the potential memory and compute savings. These applications use data stored in a variety of compression formats. We demonstrate that both the compactness of different compression formats and the compute efficiency of the algorithms enabled by them vary across tensor dimensions and amount of sparsity. Since DL and scientific workloads span across all sparsity regions, there can be numerous format combinations for optimizing memory and compute efficiency. Unfortunately, many proposed accelerators operate on one or two fixed format combinations. This work proposes hardware extensions to accelerators for supporting numerous format combinations seamlessly and demonstrates ~ 4 x speedup over performing format conversions in software.

The advent of Deep Learning (DL) has radically transformed the computing industry across the entire spectrum from algorithms to circuits. As myriad application domains embrace DL, it has become synonymous with a genre of workloads across vision, speech, language, recommendations, robotics, and games. The key compute kernel within most DL workloads is general matrix-matrix multiplications (GEMMs), which appears frequently during both the forward pass (inference and training) and backward pass (training). GEMMs are a natural choice for hardware acceleration to speed up training, and have led to 2D systolic architectures like NVIDIA tensor cores and Google Tensor Processing Unit (TPU). Unfortunately, emerging GEMMs in DL are highly irregular and sparse, which lead to poor data mappings on systolic architectures. This paper proposes SIGMA, a flexible and scalable architecture that offers high utilization of all its processing elements (PEs) regardless of kernel shape and sparsity. Within SIGMA includes a novel reduction tree microarchitecture named Forwarding Adder Network (FAN). SIGMA performs 5.7x better than systolic array architectures for irregular sparse matrices, and roughly 3x better than state-of-the-art sparse accelerators. We demonstrate an instance of SIGMA operating at 10.8 TFLOPS efficiency across arbitrary levels of sparsity, with a 65.10 mm^2 and 22.33 W footprint on a 28 nm process.

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

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

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

We present a new approach for multithreaded communication and asynchronous progress in MPI applications, wherein we offload communication processing to a dedicated thread. The central premise is that given the rapidly increasing core counts on modern systems, the improvements in MPI performance arising from dedicating a thread to drive communication outweigh the small loss of resources for application computation, particularly when overlap of communication and computation can be exploited. Our approach allows application threads to make MPI calls concurrently, enqueuing these as communication tasks to be processed by a dedicated communication thread. This not only guarantees progress for such communication operations, but also reduces load imbalance. Our implementation additionally significantly reduces the overhead of mutual exclusion seen in existing implementations for applications using MPI_THREAD_MULTIPLE. Our technique requires no modification to the application, and we demonstrate significant performance improvement (up to 2X) for QCD, 1-D FFT and deep learning CNN applications.

Given the growing importance of large-scale graph analytics, there is a need to improve the performance of graph analysis frameworks without compromising on productivity. GraphMat is our solution to bridge this gap between a user-friendly graph analytics framework and native, hand-optimized code. GraphMat functions by taking vertex programs and mapping them to high performance sparse matrix operations in the backend. We thus get the productivity benefits of a vertex programming framework without sacrificing performance. GraphMat is a single-node multicore graph framework written in C++ which has enabled us to write a diverse set of graph algorithms with the same effort compared to other vertex programming frameworks. GraphMat performs 1.1-7X faster than high performance frameworks such as GraphLab, CombBLAS and Galois. GraphMat also matches the performance of MapGraph, a GPU-based graph framework, despite running on a CPU platform with significantly lower compute and bandwidth resources. It achieves better multicore scalability (13-15X on 24 cores) than other frameworks and is 1.2X off native, hand-optimized code on a variety of graph algorithms. Since GraphMat performance depends mainly on a few scalable and well-understood sparse matrix operations, GraphMat can naturally benefit from the trend of increasing parallelism in future hardware.

This work presents a static-analysis based method for analyzing the robustness of a given embedded control system design, in the presence of quality-faults in sensors, software components, and inter-connections. The method characterizes the individual components of the system by storing the relations between the precision of inputs and the precision of outputs in what we call, lookup tables (LUTs). A network of LUTs thus formed which represent the given control system is converted into a satisfiability modulo theory (SMT) instance, such that a satisfying assignment corresponds to a potential counterexample (the set of quality-faults which violate the given fault-tolerance requirements) or hot-spot in the design. Hot-spots obtained in this manner are counter-verified through simulation to filter the false-positives. Experimental results on the fault-tolerant fuel controller from Simulink automotive library demonstrate the efficacy of the proposed approach.

Overheating of computer chips leads to degradation of performance and reliability. Therefore, preventing chips from overheating in spite of increased performance requirements has emerged as a major challenge. Since the cost of cooling has been rising steadily, various architecture and application design techniques are used to prevent chip overheating. Temperature-aware task scheduling has emerged as an important application design methodology for addressing this problem in multiprocessor SoC systems. In this work we present the formulation and implementation of a method for analyzing the thermal (chip heating) behavior of a MPSoC task schedule, during the early stages of the design. We highlight the challenges in developing such a framework and propose solutions for tackling them. Due to nondeterminism in task execution times and decision branches, multiprocessor applications cannot be evaluated accurately by the current state-of-the-art thermal simulation and steady-state analysis methods. Hence an analysis covering nondeterministic execution behaviors is required for thermal analysis of MPSoC task schedules. To address this issue we propose a model checking-based approach for solving the thermal analysis problem and formulate it as a hybrid automata reachability verification problem. We present an algorithm for constructing this hybrid automata given the task schedule, a set of power profiles of tasks, and the Compact Thermal Model (CTM) of the chip. Information about task power consumption is inferred from Markov chains which are learned from power profiles of tasks, obtained from simulation or emulation runs. A numerical analysis-based algorithm which uses CounterExample-Guided Abstraction Refinement (CEGAR) is developed for reachability analysis of this hybrid automata. We propose a directed simulation methodology which uses results of a time-bounded analysis of the hybrid automata modeling thermal behavior of the application, to simulate the expected worst-case execution runs of the same. The algorithms presented in this work have been implemented in a prototype tool called HeatCheck . We present experimental results and analysis of thermal behavior of a set of task schedules executing on a MPSoC system.

This work presents a static timing-analysis method for verification of scenario-based real-time properties, on graphical task-level models of embedded applications. Scenario-based properties specify timing constraints which must be honored for specific control-flow behaviors and task execution orderings. Static checking of scenario-based properties currently requires computationally expensive model checking methods. Hence the proposed graph-based static timing-analysis algorithm improves upon the state-of-the-art. This is manifested in a significant performance advantage over timed model checking (up to 1000X in several cases), which suffers from state space explosion. The proposed algorithm also employs compositional reasoning and abstraction refinement for handling large problems. We also illustrate methods for using scenario-based timing analysis, which can act as alternatives to traditional timed model checking for verification of timed systems like FDDI and Fischer protocols. We implement this timing verification algorithm as a tool called SymTime and present experimental results for SymTime comparing it with SPIN, UPPAAL, and a TCTL model checker for Time Petri Nets, called Romeo.

Most of the work done in the field of code compression pertains to processors with fixed-length instruction encoding. The design of a code-compression scheme for variable-length instruction encodings poses newer design challenges. In this work, we first investigate the scope for code compression on variable-length instruction-set processors whose encodings are already optimized to a certain extent with respect to their usage. For such ISAs instruction boundaries are not known prior to decoding. Another challenging task of designing a code-compression scheme for such ISAs is designing the decompression hardware, which must decompress code postcache so that we gain in performance. We present two dictionary-based code compression schemes. The first algorithm uses a bit-vector; the second one uses reserved instructions to identify code words. We design additional logic for each of the schemes to decompress the code on-the-fly. We test the two algorithms with a variable-length RISC processor. We provide a detailed experimental analysis of the empirical results obtained by extensive simulation-based design space exploration for this system. The optimized decompressor can now execute compressed program faster than the native program. The experiments demonstrate reduction in code size (up to 30%), speed-up (up to 15%), and bus-switching activity (up to 20%). We also implement one decompressor in a hardware description language and synthesize it to illustrate the small overheads associated with the proposed approach.

With the advent of multiprocessor embedded platforms, application partitioning and mapping have gained primacy as a design step. The output of this design step is a multithreaded partitioned application where each thread is mapped to a processing element (processor or ASIC) in the multiprocessor platform. This partitioned application must be verified to be consistent with the native unpartitioned application. This verification task is called application (or task) partitioning verification. This work proposes a code-block-level containment-checking -based methodology for application partitioning verification. We use a UML-based code-block-level modeling language which is rich enough to model most designs. We formulate the application partitioning verification problem as a special case of the containment checking problem, which we call the complete containment checking problem . We propose a state space reduction technique specific to the containment checking, reachability analysis, and deadlock detection problems. We propose novel data structures and token propagation methodologies which enhance the efficiency of containment checking. We present an efficient containment checking algorithm for the application partitioning verification problem. We develop a containment checking tool called TraceMatch and present experimental results. We present a comparison of the state space reduction achieved by TraceMatch with that achieved by formal analysis and verification tools like Spin, PEP, PROD, and LoLA.

The UML activity diagram language is the de facto language for behavioral modeling capable of block level modeling of real time multiprocessor SoC applications where timing behavior is a critical aspect. Although there are several tools for timing verification of logics with branching time semantics, there are no known model checkers for timing verification of logics with linear time semantics as needed for many verification tasks. This work deals with timing verification of UML activity diagram models of applications. We propose a subset of TPTL (timed prepositional temporal logic) for specifying timing queries. We develop an automata based model checker for verifying such queries. We present a comparison of the proposed timing verification with the state of the art for random test-cases.