Boolean equivalence allows Boolean networks with identical functionality to exhibit diverse graph structures. This gives more room for exploration in logic optimization, while also posing a challenge for tasks involving consistency between Boolean networks. To tackle this challenge, we introduceBoolSkeleton, a novel Boolean network skeletonization method that improves the consistency and reliability of design-specific evaluations.BoolSkeletoncomprises two key steps: preprocessing and reduction. In preprocessing, the Boolean network is transformed into a defined Boolean dependency graph, where nodes are assigned the functionality-related status. Next, the homogeneous and heterogeneous patterns are defined for the node-level pattern reduction step. Heterogeneous patterns are preserved to maintain critical functionality-related dependencies, while homogeneous patterns can be reduced. ParameterKof the pattern further constrains the fanin size of these patterns, enabling fine-tuned control over the granularity of graph reduction. To validateBoolSkeleton’s effectiveness, we conducted four analysis/downstream tasks around the Boolean network: compression analysis, classification, critical path analysis, and timing prediction, demonstrating its robustness across diverse scenarios. Furthermore, it improves above 55% in the average accuracy compared to the original Boolean network for the timing prediction task. These experiments underscore the potential ofBoolSkeletonto enhance design consistency in logic synthesis.

As hardware design complexity increases, hardware fuzzing emerges as a promising tool for automating the verification process. However, a significant gap still exists before it can be applied in industry. This paper aims to summarize the current progress of hardware fuzzing from an industry-use perspective and propose solutions to bridge the gap between hardware fuzzing and industrial verification. First, we review recent hardware fuzzing methods and analyze their compatibilities with industrial verification. We establish criteria to assess whether a hardware fuzzing approach is compatible. Second, we examine whether current verification tools can efficiently support hardware fuzzing. We identify the bottlenecks in hardware fuzzing performance caused by insufficient support from the industrial environment. To overcome the bottlenecks, we propose a prototype, HwFuzzEnv, providing the necessary support for hardware fuzzing. With this prototype, the previous hardware fuzzing method can achieve a several hundred times speedup in industrial settings. Our work could serve as a reference for EDA companies, encouraging them to enhance their tools to support hardware fuzzing efficiently in industrial verification.

Debugging hardware designs requires significant manual effort during hardware development. After engineers identify a bug-triggering test case in simulation-based hardware verification, they usually spend considerable time analyzing the execution trace to localize the bug. Although numerous automated hardware debugging techniques exist, they are not applicable to large designs and deep bugs. A primary reason for their limitations is that these techniques only utilize the information of a single bug-triggering test case for bug localization, which prevents them from effectively analyzing intricate hardware systems and figure out the root cause of bugs. To solve this problem, in this paper, we transform the hardware bug localization problem into a test generation problem, aiming to find a set of effective witness test cases beyond the initial bug-triggering test case to enhance hardware bug localization. Witness test cases refer to the cases that do not trigger the bug in the faulty design. By analyzing the execution differences between passing and failing test cases with spectrum-based method, we can eliminate innocent design statements and localize the buggy ones. To further refine the suspicious area, we define the criteria for effective witness test cases and use a mutation-based strategy to generate such test cases. Based on this approach, we propose an automated hardware bug localization framework named Wit-HW. We evaluate Wit-HW on 41 bugs from various hardware designs. The experimental results show that Wit- effectively localize 49% / 73% / 88% bugs within Top-1 / Top-5 / Top-10 ranks, significantly outperforming state-of-the-art bug localization techniques. Additionally, we evaluate Wit-HW on 13 real-world bugs collected from open-source hardware projects, showcasing the robust performance of our method.

Quantum computing has garnered significant interest for its potential to achieve exponential speedups over classical approaches. However, in the Noisy Intermediate-Scale Quantum (NISQ) era, quantum circuit scalability remains limited by gate fidelity and qubit counts, restricting physical implementations to small-scale circuits. While prior work has explored logic network structures for quantum circuit synthesis, these methods often neglect the spatial structure intrinsic to Boolean functions. In this paper, we leverage this spatial structure, encoded by parallelotopes embedded in the hypercube defined by the Boolean function, to access a broader optimization space, enhancing synthesis efficiency and reducing circuit complexity. We propose the Spatial Structure-based Hypercube Reduction (SSHR), a novel synthesis method tailored for small-scale Boolean functions (≤ 8). SSHR extracts global spatial features to minimize the use of Multi-Control Toffoli (MCT) gates. To further exploit spatial correlations, we introduce two variants: SSHR-H employs heuristic functions to accelerate synthesis runtime, while SSHR-I integrates an Integer Linear Programming (ILP) solver to maximize spatial structure utilization. Our approach outperforms existing techniques in small-scale circuit synthesis, achieving 56% and 81% reductions in CNOT gate counts compared to the Exclusive Sum-of-Products (ESOP) and Xor-And-Inverter Graph (XAG) methods, respectively.

Generative large language models' (LLMs) inference suffers from inefficiency because of the token dependency brought by autoregressive decoding. Recently, speculative inference has been proposed to alleviate this problem, which introduces small language models to generate draft tokens and adopts the original large language model to conduct verification. Although speculative inference can enhance the efficiency of the decoding procedure, we find that it presents variable resource demands due to the distinct computation patterns of the models used in speculative inference. This variability impedes the full realization of speculative inference's acceleration potential in current systems.

Coarse-Grained Reconfigurable Array (CGRA) is a parallel architecture providing high energy efficiency and spatial-temporal re-configurability. Beyond loop scheduling for throughput optimization, program transformation is also crucial in CGRA mapping to optimize overall performance and efficiency. However, existing studies on program transformation optimization face challenges in exploring the transformation space systematically and evaluating candidates efficiently, leading to sub-optimal results. To tackle these challenges, this paper introduces PT-Map, an efficient program transformation optimization framework for CGRA mapping. PT-Map defines a comprehensive transformation space and employs a CGRA-specialized top-down exploration approach. It also incorporates a bottom-up evaluation scheme using architectural parameters and a graph neural network-based predictive model. Experiments demonstrate that PT-Map achieves up to 2.95X/1.80X speedups and 59.0%/23.2% energy-delay-product (EDP) reductions over the state-of-the-art approaches MapZero and PBP, respectively.

SAT-based exact synthesis is a critical technique in logic synthesis to generate optimal circuits for given Boolean functions. The lengthy trial-and-error process limits its application in on-the-fly logic optimization and optimal netlist library construction. Previous research focuses on reducing the execution time of each trial. However, unnecessary SAT solver calls and varying execution times among encoding methods remained issues. This paper presents BESWAC to boost exact synthesis from the flow level. It leverages initial value prediction, encoding method selection, and an optional early exit to call SAT solvers efficiently and wisely. Moreover, BESWAC can seamlessly integrate existing acceleration methods focusing on individual trials. Experimental results show that BESWAC achieves a 1.79x speedup compared to state-of-the-art exact synthesis flows.

Exact synthesis is a critical technique in logic synthesis to generate optimal circuits for given Boolean functions. Recent progress in SAT solvers makes SAT-based methods practical. However, the intractable and unpredictable execution time has limited its application with potential quality degradation and runtime overhead. To ease such limitations, we propose an incremental SAT-based method for exact synthesis (IncSyn). It leverages previous knowledge to accelerate the finding of a new optimal circuit. IncSyn uncovers the relationships between functions and modifies the encoding and synthesis flow correspondingly. We speed up the exact synthesis by up to 15x and achieve scale advancements, solving considerable cases of up to 12-input Boolean functions within tolerable time. The proposed method reduces the average runtime for optimal library building and on-the-fly rewrite by 6% and 64%, respectively.

This paper introduces AceRoute, an adaptive compute-efficient FPGA router that tackles the long-standing issue of lengthy FPGA compilation times given complicated FPGA architectures and designs to synthesize. We thoroughly profile modern FPGA routing patterns and identify the runtime hotspot: routing bottleneck connections in congested designs. However, previous works on routing acceleration hardly target mitigating connection-wise routing difficulties by characterizing device resource expansions and shifting path-exploration modes of connections.

Due to the escalating complexity of chip design and the exorbitant cost of building cutting-edge manufacturing facilities, outsourcing the fabrication of Integrated Circuits (ICs) is prevalent in modern semiconductor industry. However, significant security risks may arise because untrustworthy foundries can conduct insidious attacks without close supervision. Since prior works show the feasibility of implementing practical foundry-level Trojan attacks that circumvent post-fabrication detection, IC designers should protect their IC layouts before sending them to a third-party foundry, and such protections are known as design-time defenses. To this end, security metrics for layout vulnerability assessment are crucial to test the effectiveness of the proposed defenses. However, existing metrics are geometric-only and Trojan-oblivious, failing to capture the fundamental aspects of foundry-level Trojan insertion and the associated side effects.To bridge the gap between real attacks and threat prediction, we present SiliconCritic, a simulation-based, extensible framework that leverages design-time techniques to simulate the blackbox foundry-level Trojan attacks and post-fabrication analysis. SiliconCritic encodes the difficulty of inserting a specific Trojan into a finalized physical layout by measuring the variation of side-channel parameters (timing, power) after the simulated Trojan insertion, where larger deviations denote better detectability and thus enhanced security. SiliconCritic allows IC designers to interactively refine defensive strategies against the objective Trojan based on the feedback of side-channel analysis. Through evaluations on real-world ASIC designs and reported hardware Trojans, SiliconCritic demonstrates the limitations of existing layout-level defenses and highlights the influence of Trojan properties on defensive efficacy. Our work refreshes the understanding of Trojan prevention and suggests future directions for defenses against untrustworthy foundries.

Power is a great concern in integrated circuits (ICs) design flow, especially in portable devices. As an early stage in electronic design automation (EDA), logic synthesis can significantly affect the quality of the design. It is essential to optimize power in logic synthesis. However, logic synthesis only has a limited concern in power due to its inaccurate estimation. This is because critical physical information is missing at this stage. Furthermore, the empirical optimization sequences need enhancement, and they are not optimal for power, while optimizing power in the early stage is effective. Technology mapping can also improve power optimization with comprehensive power metrics in this sub-15 nm era. Therefore, we propose PowerSyn, a logic synthesis framework with early power optimization. It consists of a practical power model, a power-oriented logic optimization module, and a technology mapping stage. The power model leverages probability propagation considering glitches and static power. The acrlong RL-based logic optimization generates high-quality and rapid-convergence command sequence with early power optimization. We also modify traditional technology mapping with novel power-related metrics. We evaluate PowerSyn on the EPFL benchmark suite. Experiment results show that our flow achieves an average power savings of 16.1% compared to the state-of-the-art open-source logic optimization flow. It also delivers an 8.8% and a 2.1% reduction in latency and area, respectively. The flow incurs less than 12.2% execution time overhead during inference for command generation.

With the ever-shrinking feature size of transistors, the exorbitant cost has driven the massive outsourcing of integrated circuits (IC) fabrication. However, this outsourcing poses significant security risks because untrustworthy foundries can conduct insidious fabrication-time attacks without close supervision. Therefore, it is crucial to undertake design-time protection before sending finalized design layouts to the foundry. Foundry-level hardware Trojan has emerged as a major security threat, but existing design-time countermeasures lack sufficient consideration of good trade-offs between design security and performance.This work proposes an automatic framework, GDSII-Guard, to strengthen implemented physical layouts against potential fabrication-time Trojan attacks while preserving design performance, power, and quality. We develop an Engineering Change Order (ECO) placement and routing (P&R) flow containing elaborate anti-Trojan operators to prevent Trojan insertion. Moreover, we introduce a multi-objective optimization model with evolutionary strategies that incorporate anti-Trojan flow information to exploit balances between the aforementioned multiple design metrics. Experimental results demonstrate that GDSII-Guard reduces the overall risk of Trojan attacks on given designs by 98.8% with minimized timing, power, and design quality impact, surpassing existing approaches prominently.

NPN classification is an essential problem in the design and verification of digital circuits. Most existing works explored variable symmetries and cofactor signatures to develop their classification methods. However, cofactor signatures only consider the face characteristics of Boolean functions. In this paper, we propose a new NPN classifier using both face and point characteristics of Boolean functions, including cofactor, influence, and sensitivity. The new method brings a new perspective to the classification of Boolean functions. The classifier only needs to compute some signatures, and the equality of corresponding signatures is a prerequisite for NPN equivalence. Therefore, these signatures can be directly used for NPN classification, thus avoiding the exhaustive transformation enumeration. The experiments show that the proposed NPN classifier gains better NPN classification accuracy with comparable speed.

NPN classification has many applications in the synthesis and verification of digital circuits. The canonical-form-based method is the most common approach, designing a canonical form as representative for the NPN equivalence class first and then computing the transformation function according to the canonical form. Most works use variable symmetries and several signatures, mainly based on the cofactor, to simplify the canonical form construction and computation. This paper describes a novel canonical form and its computation algorithm by introducing Boolean influence to NPN classification, which is a basic concept in analysis of Boolean functions. We show that influence is input-negation-independent, input-permutation-dependent, and has other structural information than previous signatures for NPN classification. Therefore, it is a significant ingredient in speeding up NPN classification. Experimental results prove that influence plays an important role in reducing the transformation enumeration in computing the canonical form. Compared with the state-of-the-art algorithm implemented in ABC, our influence-aided canonical form for exact NPN classification gains up to 5.5x speedup.

Rewriting is a common procedure in logic synthesis aimed at improving the performance, power, and area (PPA) of circuits. The traditional reconvergence-driven And-Inverter Graph (AIG) rewriting method focuses solely on optimizing the reconvergence cone through Boolean algebra minimization. However, there exist opportunities to incorporate other node-rewriting algorithms that are better suited for specific cones. In this paper, we propose an adaptive reconvergence-driven AIG rewriting algorithm that combines two key techniques: multi-strategy-based AIG rewriting and strategy learning-based algorithm selection. The multi-strategy-based rewriting method expands upon the traditional approach by incorporating support for multi-node-rewriting algorithms, thus expanding the optimization space. Additionally, the strategy learning-based algorithm selection method determines the most suitable node-rewriting algorithm for a given cone. Experimental results demonstrate that our proposed method yields a significant average improvement of 5.567% in size and 5.327% in depth.

Chiplet-based designs have gained recognition as a promising alternative to monolithic SoCs due to their lower manufacturing costs, improved re-usability, and optimized technology specialization. Despite progress made in various related domains, the design of chiplets remains largely reliant on manual processes. In this paper, we provide an examination of the historical evolution of chiplets, encompassing a review of crucial design considerations and a synopsis of recent advancements in relevant fields. Further, we identify and examine the opportunities and challenges in the automated design of chiplets. To further demonstrate the potential of this nascent area, we present a novel task that

Super-resolution (SR) techniques aim to restore a high-resolution (HR) image from low-resolution (LR) images, which are often used to assist the enhancement of image/video quality under the rapid development of HR and high-frame-rate media. Recently, neural network (NN)-based methods perform much better image reconstruction quality than classical approaches. However, the unacceptable computation complexity as well as the huge memory footprints of NNs limit the throughputs and scalability of these SR systems. In this work, we analyze several key issues in the design of NN-based SR systems first. Then, we propose a three-level systematic optimization methodology for SR systems to reduce computation overhead and keep image quality. At the algorithm level, we introduce image blocking to SR tasks and develop a block-wise SR algorithm based on the hybrid of NN and interpolation with a consistent image block evaluation metric. The configurable hybrid parameters help the SR algorithm to achieve a flexible tradeoff between the computation overhead and image quality. At the operator level, we focus on the transpose convolution operators commonly used for upsampling in SR NNs. We propose an efficient Winograd-based transposed convolution acceleration method. Through the efficient subconvolutions conversion and the Winograd specialization, this methods enables unified Winograd transformations and simplified data access patterns. At the data level, we propose a novel quantization method for Winograd-aware SR NNs to get better-quantized accuracy. Comprehensive evaluations demonstrate the effectiveness of these optimizations. Our SR system reduces a large number of multiplications with great scalability and supports 4K@120 fps and 8K@30 fps outputs with acceptable image quality degradation.

Graph convolutional network (GCN) is a promising but computing- and memory-intensive learning model. Processing-in-memory (PIM) architecture based on the resistive random access memory-based crossbar (ReRAM crossbar) is a natural fit for GCN inference. It can reduce the data movements and compute the vector-matrix multiplication (VMM) in analog. However, it requires an unbearable crossbar cost to leverage the massive parallelism exhibited in GCNs. First, this article explores the design space for GCN inference on ReRAM crossbars and presents the first PIM-based GCN accelerator named PIMGCN, PIMGCN employs dense data mapping and a search-execute architecture to take full advantage of the intravertex parallelisms with acceptable crossbars cost. Two scheduling strategies for PIMGCN to maximize the intervertex parallelisms and optimize the pipeline are proposed. The optimal scheduling is reduced to a maximum independent set problem, which is solved by a novel node-grouping algorithm. Second, this article explores the task-irrelevant information in the graphs and proposes an adaptively sparsified GCN network targeted for PIMGCN, which is named as ASparGCN. ASparGCN exploits a multilayer perceptron (MLP)-based edge predictor to get edge selection strategies for each GCN layer separately and adaptively in the training stage, and only inferences with the selected edges in the test stage. We design two regularization terms to guide the selection strategies to achieve architecture-friendly sparse graphs for PIMGCN. The overall algorithm-architecture co-design is named as PASGCN. Compared to the state-of-the-art software framework running on Intel Xeon CPU and NVIDIA RTX8000 GPU, PASGCN achieves an average of$16455\times $and$110.7\times $speedup and 8.0E$+ 06\times $and 6.67E$+ 03\times $energy reduction, respectively. Compared with the ASIC accelerator HyGCN (Yan et al., 2020), PASGCN achieves$326.31\times $speedup and$124.8\times $energy reduction.

Multiplier-accumulator (MAC) is a crucial arithmetic element widely used in digital integrated circuits. Customized MACs are necessary for different scenarios but need great effort due to the huge architecture design space. In this paper, we develop EasyMAC, a flexible Chisel-based MAC generator with a canonical architectural representation. We design a compact and canonical sequence representation to express the architecture of MACs. And the MAC generator takes the compact representation as input to gain the Verilog codes. We also give a case study on developing a heuristic design space exploration (DSE) method based on this representation. The experimental result shows the effectiveness of the representation in DSE. Using the percent relative range of the power-delay-area product as a metric to measure the optimization opportunities that this representation exposes, the relative range is 17.4% and 23.1% for 16×16 and 25×18 MACs, respectively. At last, we discuss some promising directions of EasyMAC.

Modern heterogeneous multi-processor system-on-chips (SoCs) have diverse needs of area, performance, and scalability for on-chip networks (OCNs). And it remains a challenge to design, evaluate, and explore a suitable OCN for a specific SoC to meet different requirements. Some open-source OCN generators have been developed to generate synthesizable RTL codes, provide fast testing, and enable design space exploration. However, none of them provides the levels of abstraction to trade off the various needs.In this paper, we propose Purlin, a versatile toolkit for the generation and simulation of OCNs. We put forward a uniform network generation and simulation flow across distributed routing, source routing, and circuit-switched OCNs to enable effective trade-offs. Purlin enables network customization through the network basic, flow control, and routing function interfaces and provides some predefined architectures. Among the architectures, the latency-optimized distributed routing OCN reduces 79.3% latency compared to a state-of-the-art OCN generator. With the routing function customization interface, we implement a deadlock-free adaptive routing function in the library, which reduces 16.1% latency. We provide compilation tools with customizable routing algorithms to generate the packet headers in source-routing or the configurations in circuit-switched OCNs from a programmed destination address. A source routing OCN using a customized routing algorithm further reduces 8.4% latency compared to a distributed routing OCN.

Coarse-grained reconfigurable architecture (CGRA) is a promising programmable device with high performance and power efficiency. The CGRA compilation problem is to map an application onto a 3D time-space model of CGRA. Adding the circuitry of synchronizers can relax the mapping constraint for data alignment in time; and thus, it significantly influences the compilation performance. However, data-departure synchronizers may be infeasible, because an output value may be used multiple times and has a high fan-out. Instead, data-arrival synchronizers can further improve performance and mappability of CGRAs with acceptable overhead, compared to the synchronization methods based on detour routing, register files, and FIFO.In this work, we design two kinds of data-arrival synchronizers and formulate them in an integer linear programming (ILP) based mapping approach. The separate ILP formulations of placement and routing speed up the architecture exploration with synchronizers by up to 3.03x. The experimental study shows that data-arrival synchronizers improve CGRA performance by 19.8% on average. The results of our quantitative study show that synchronizers also improve the mapping success rate by 1.91x on average. In conclusion, CGRAs with appropriate synchronizers have better mappability while using fewer resources.

Boolean matching is significant to digital integrated circuits design. An exhaustive method for Boolean matching is computationally expensive even for functions with only a few variables, because the time complexity of such an algorithm for an n-variable Boolean function is O(2n+1n!). Sensitivity is an important characteristic and a measure of the complexity of Boolean functions. It has been used in analysis of the complexity of algorithms in different fields. This measure could be regarded as a signature of Boolean functions and has great potential to help reduce the search space of Boolean matching. In this paper, we introduce Boolean sensitivity into Boolean matching and design several sensitivity-related signatures to enhance fast Boolean matching. First, we propose some new signatures that relate sensitivity to Boolean equivalence. Then, we prove that these signatures are prerequisites for Boolean matching, which we can use to reduce the search space of the matching problem. Besides, we develop a fast sensitivity calculation method to compute and compare these signatures of two Boolean functions. Compared with the traditional cofactor and symmetric detection methods, sensitivity is a series of signatures of another dimension. We also show that sensitivity can be easily integrated into traditional methods and distinguish the mismatched Boolean functions faster. To the best of our knowledge, this is the first work that introduces sensitivity to Boolean matching. The experimental results show that sensitivity-related signatures we proposed in this paper can reduce the search space to a very large extent, and perform up to 3x speedup over the state-of-the-art Boolean matching methods.

Advanced Driver-Assistance Systems (ADAS) are complex systems consisting of many computer vision tasks including image classification, object detection and semantic segmentation. FPGA is a feasible solution for deep learning based computer vision accelerator due to its high performance and energy efficiency. However, design a high performance FPGA accelerator requires good understanding of basic hardware concepts and consumes a long compilation time. Overlays can alleviate the above problems by accelerating applications in a software via a hardware architecture and a compiler. In this paper, we propose an FPGA-based neural network overlay processor for ADAS. The overlay architecture contains almost all common computation layers for learning based ADAS. In addition, we design a compiler that can automatically compile the high-level description of neural networks from deep learning framework like Caffe and Tensorflow into FPGA configurable codes, which can be executed by our overlay architecture without reprogramming. Experiments show that our overlay can process learning tasks in ADAS with low latency and low memory usage.

Processing-in-memory (PIM) exploits massive parallelism with high energy efficiency and becomes a promising solution to the von Neumann bottleneck. Recently, the emerging metal-oxide resistive random access memory (RRAM) shows its potential to construct a PIM architecture, because several stateful logic operations, e.g., IMP and NOR, can be executed in an RRAM crossbar in parallel. Previous synthesis flows focus on improving latency with stateful logic operations, but they ignore that the memory should be used primarily for storage. i.e., most of the area in the crossbar is used for computation but not storage. In this situation, storage and computation still have to be separated into different crossbars, which leads to considerable data transfer overhead and limited parallelism. In this work, we define the ratio of storage in a crossbar as area utilization. We aim to improve the area utilization without throughput loss by proposing STAR, a novel synthesis flow for the stateful logic. We present two optimization strategies to reduce the computation area in STAR. First, we reduce the area for redundant inputs. For the shared constants among different rows (or columns), we encode them as immediate values into the control signals without writing them into the crossbar at runtime. For the other inputs, we only store one copy of them in the crossbar. Second, we reduce the area for intermediate variables by reusing invalid cells. And we design a scheduling algorithm to find a computation sequence with the minimal variable erasing cycles. Invalid primary inputs can also be erased in this algorithm. Furthermore, we present a case study of the image convolution to demonstrate the effectiveness of STAR. Experimental evaluation shows that STAR achieves 33.03% more area utilization and a 1.43x throughput compared to SIMPLER, the state-of-the-art stateful logic synthesis flow. Our image convolution implementation also provides 78.36% more area utilization and a 1.48x throughput compared with IMAGING, the state-of-the-art stateful logic-based image processing accelerator.

Modern commercial Field-Programmable Gate Array (FPGA) architectures support dual-output look-up tables (LUTs). If the number of total inputs in two small LUTs do not exceed the constraint, e.g., 5 in Xilinx UltraScale+ series, we can pack them into one dual-output LUT to reduce area, i.e., the number of LUTs. However, previous works have not fully utilized this feature. They usually generate single-output LUTs in the technology mapping phase and merge LUTs in a later packing phase. In this situation, they cannot get LUT merging information during technology mapping and will generate some single-output LUTs that are not suitable for merging.

Processing-in-memory (PIM) provides massive parallelism with high energy efficiency and becomes a promising solution to the memory wall problem. Recently, the emerging metal-oxide resistive random access memory (RRAM) has shown its potential to design a PIM architecture. Several stateful logic operations, e.g., NOR and NAND, can be executed in parallel in an RRAM crossbar. Although previous works have designed some algorithms using the stateful logic, it is still under exploration how to fully exploit its potential high parallelism and design an asymptotically fast algorithm for a given function. In this work, we theoretically analyze the parallelism in an RRAM crossbar and design several asymptotically optimal arithmetic algorithms. In detail, we first propose the Single Instruction Multiple Lines (SIML) model to unify the stateful logic families and prove three lower bounds on the time complexity of a parallel RRAM algorithm. Then, we design three algorithms for integer addition functions with the stateful logic, guided by the lower bound analysis. All of them reach the time complexity lower bound. Finally, We make two extensions of the integer addition algorithms, supporting multiplication functions by decomposing them to additions and supporting the flex-point data type by proposing an exponent and mantissa update flow. Experimental evaluation shows that our integer algorithms achieves a speedup up to 13.79x over the previous RRAM algorithms. Our flex-point implementation achieves a 26.60x speedup and saves 73.68% energy compared to an ARM.

FPGAs are very attractive to accelerate the deep neural networks (DNNs). While single FPGA can provide good performance for small-scale DNNs, support for large-scale DNNs is limited due to higher resource demand. In this paper, we propose an efficient mapping approach for accelerating large-scale DNNs on asymmetric multi-FPGA architectures. In this approach, the neural network mapping can be formulated as a resource allocation problem. We design a dynamic programming-based partitioning to solve this problem optimally. Experimental results using the large-scale ResNet-152 demonstrate that our approach deploys sixteen FPGAs to provide an advantage of 16.4x GOPS over the state-of-the-art work.

FPGAs are commercially available off-the-shelf for implementing convolutional neural network (CNN) accelerators to trade off accuracy, performance, and power. Systolic array architecture for CNN accelerators on FPGAs has the potential to run at a high frequency due to its regular and simple interconnections. However, current FPGA CAD tools are unable to synthesize and layout systolic arrays in high quality. In this paper, we identify the reasons for the frequency degradation of systolic array designs for CNN accelerators. We also propose two methods to improve the frequency at the front-end and the back-end, respectively. The experimental results show that our methods are able to achieve 1.29 × higher frequency and attain 1.5TOPS for the VGG16 network on the Xilinx KCU1500 platform.

Placement is probably the most critical process in the FPGA design flow. The demand for high performance continues to increase, but existing placers are still faced with numerous challenges including very long runtime, poor scalability, and restricted space exploration. In this paper we propose a novel timing-driven placement algorithm called BoxPlacer, which is supported by the force directed concept. BoxPlacer firstly uses a simple policy to create the initial box for placement. Then a force-directed iterative scheme is used to reduce the box size and determine the global placement. At last, the same concept is employed to eliminate the overlaps between reduced boxes to ensure the legalization in detailed placement. Notice that timing is always used to drive the placement in BoxPlacer. We demonstrate the effectiveness of our BoxPlacer by comparing the experimental results with that produced by the academic simulated annealing-based placer. Notably, our BoxPlacer achieves on average about 8x runtime advantage with 9% smaller critical path delay and 6% shorter wirelength.

FPGAs are very attractive to accelerate the deep neural networks (DNNs). While single-FPGA can provide good performance for small-scale DNNs, support for large-scale DNNs is very limited due to they require higher resource demand. In this paper, we propose an efficient mapping approach for accelerating large-scale DNNs on an asymmetric multi-FPGA architecture. Relative to the state-of-the-art single-FPGA resource reuse for large-scale DNNs, we consider multi-FPGA fashion to strive for higher performance. In this fashion, the neural network mapping problem can be formulated as a resource allocation problem, and a dynamic programming-based partitioning is designed to solve this problem optimally. Notice that the network topology and communication bandwidth of multiple FPGAs are always used to guide the partitioning to boost the performance while satisfying the constraints of resource-performance trade-off in a single FPGA. Experimental results using the large-scale ResNet-152 demonstrate that our approach deploys sixteen FPGAs to provide an advantage of 16.4x GOPS over the state-of-the-art work.

Stochastic gradient descent (SGD) is a widely-used algorithm in many applications, especially in the training process of deep learning models. Low-precision implementation for SGD has been studied as a major acceleration approach. However, if not appropriately used, low-precision implementation can deteriorate its convergence because of the rounding error when gradients become small near a local optimum. In this work, to balance throughput and algorithmic accuracy, we apply the Q-learning technique to adjust the precision of SGD automatically by designing an appropriate decision function. The proposed decision function for Q-learning takes the error rate of the objective function, its gradients, and the current precision configuration as the inputs. Q-learning then chooses proper precision adaptively for hardware efficiency and algorithmic accuracy. We use reconfigurable devices such as FPGAs to evaluate the adaptive precision configurations generated by the proposed Q-learning method. We prototype the framework using LeNet-5 model with MNIST and CIFAR10 datasets and implement it on a Xilinx KCU1500 FPGA board. In the experiments, we analyze the throughput of different precision representations and the precision-selection of our framework. The results show that the proposed framework with adapative precision increases the throughput by up to 4.3× compared to the conventional 32-bit floating point setting, and it achieves both the best hardware efficiency and algorithmic accuracy.

The non-exact projective NPNP (NP3) Boolean matching problem is practically significant in the applications of technology mapping, logic verification, and hardware security. However, its difficulty compels an unsatisfactory running time, and conventional algorithms for the basic NPNP Boolean matching problem perform terribly on the non-exact and projective type. In this paper, we propose a novel algorithm to solve this newly rising NP3 Boolean matching problem, and multiple types of optimization were applied to further improve the performance. Experimental results indicate that our algorithm has outstanding outcomes.

Due to the continuous scaling of integration density and the increasing diversity of customized designs, there are increasing demands on the scalability and the customization of EDA tools and flows. Commercial EDA tools usually provide an interface of TCL scripting to extract and modify the design information for a flexible design flow. However, we observe that the current TCL scripting is not designed for the complete netlist extraction, resulting in a significant degradation in performance. For example, it takes over 20 minutes to extract the complete netlist of a 466K-cell design using TCL. This extraction may be repeated several times when interfacing between the existing EDA platforms and the actual distributed EDA algorithms. This drastic decrease in efficiency is a great barrier for customized EDA tool development. In this paper, we propose to build a distributed framework on top of TCL to accelerate the netlist extraction and use the distribution detailed placement as an example to demonstrate its capability. This framework is promising in scaling out physical design algorithms to run on a cluster.