The Boolean Satisfiability (SAT) problem is the key problem in computer theory and application. Field-programmable gate array (FPGA) has been addressed frequently to accelerate the SAT solving process in the last few years owing to its parallelism and flexibility. We have proposed a novel SAT solver based on an improved local search algorithm on the reconfigurable hardware platform. The new software preprocessing procedure and hardware architecture are involved to solve large-scale SAT problems instances. As compared with the past solvers, the proposed solver has the following advantages: the preprocessing technology can strongly improve the efficiency of solver; the strategy of strengthening the variable selection can avoid the same variable flipped continuously and repeatedly. It reduces the possibility of search falling into local minima. The experimental results indicate that the solver can solve problems of up to 32K variables/128K clauses without off-chip memory banks, and has better performance than previous works.

Deep learning has become a highly popular research field, and previously deep learning algorithms ran primarily on CPUs and GPUs. However, with the rapid development of deep learning, it was discovered that existing processors could not meet the specific large-scale computing requirements of deep learning, and custom deep learning accelerators have become popular. The majority of the primary workloads in deep learning are general matrix-matrix multiplications (GEMMs), and emerging GEMMs are highly sparse and irregular. The TPU and SIGMA are typical GEMM accelerators in recent years, but the TPU does not support sparsity, and both the TPU and SIGMA have insufficient utilization rates of the Processing Element (PE). We design and implement SparGD, a sparse GEMM accelerator with dynamic dataflow. SparGD has specific PE structures, flexible distribution networks and reduction networks, and a simple dataflow switching module. When running sparse and irregular GEMMs, SparGD can maintain high PE utilization while utilizing sparsity, and can switch to the optimal dataflow according to the computing environment. For sparse, irregular GEMMs, our experimental results show that SparGD outperforms systolic arrays by 30 times and SIGMA by 3.6 times.

The Boolean Satisfiability (SAT) problem is the key problem in computer theory and application. A parallel multi-thread SAT solver named pprobSAT+ on a configurable hardware is proposed. In the algorithm, multithreads are executed simultaneously to hide the circuit stagnate. In order to improve the working frequency and throughput of the SAT solver, the deep pipeline strategy is adopted. When all data stored in block random access memory of the field programmable gate array, the solver can achieve maximum performance. If partial data are stored in the external memory, the size of the problem instances the SAT solver can be greatly improved. The experimental results show that the speedup of three-thread SAT solver is approximately 2.4 times with single thread, and shows that the pprobSAT+ have achieved substantial improvement while a solution is found.

The Boolean satisfiability (SAT) problem is the key problem in computer theory and application. A novel algorithm is introduced to implement a SLS hardware solver called probSAT+. The algorithm has no complex heuristic, and it only depends on the concepts of preprocessing technology, probability distribution and centralized search. Through constraining the initial assignments of the variables, the number of flipped variables was reduced while the solver finding a solution. Moreover, the algorithm no longer adopts some non-continuous if-then-else decisions, but depends on a single continuous function f(x,v). The flipping probability is not obtained by complex calculations, instead being selected by looking up tables, which effectively improves the performance of the solver. As far as we know, the probability distribution selection strategy descripted by hardware description language is firstly adopted by hardware SAT solver, which can be easily transplanted to any programmable logic device. The experimental results show that the probSAT+ solver is generally lower than the advanced software solver in the number of flips (up to 9.8 $\times {10}^6$ ), and the speedup is approximately 2.6 times with single thread, which shows that the probSAT+ has better results with fewer variables flipping times when a solution can be found. In addition, the success ratio of the solver in finding a solution of the problem in a suitable time is 100%.

The Processing-In-Memory (PIM) architecture becomes a promising candidate for realizing energy-efficient CNN acceleration by integrating computation and memory. For deploying a CNN, the PIM-based designs need a scheduling scheme to translate massive hardware resources into actual performance. The scheduling scheme includes the intra-layer scheduling scheme to map data of one layer and the inter-layer scheduling scheme to allocate resources for multiple layers. Currently, the research of scheduling schemes for PIM-based studies is in its early stages and faces the following limitations. First, the intra-layer scheduling scheme mainly uses the Weight Stationary (WS) data flow to avoid weight movements. However, the amount of activation movement is larger than that of the weight movement for some DNNs or layers, making the activation movement become the bottleneck for reducing latency and energy consumption. Second, the Input Stationary (IS) data flow provides new opportunities to further reduce activation movements. However, the traditional IS data flow introduces a huge amount of across-crossbar computations and relies on the 3D-ReRAM structure. Third, the layer-wise processing structure of the DNN introduces complex inter-layer data dependence and imbalance workload, decreasing pipeline efficiency. Fourth, there is little study on co-optimization of intra-layer and inter-layer scheduling schemes. Inspired by these observations, we propose the Hybrid data flow based Intra-layer and inter-layer Scheduling schemes Optimization framework for PIM-based architectures, named HiSo. Specifically, we propose a novel data flow, named PP-IS, that replaces the convolution unrolling with selecting activations according to convolution windows to reduce activation movements. We also define and optimize the partition methods to improve data reuse and computational parallelism for the WS and PP-IS data flows. Then, we trade off performance and energy efficiency by using the hybrid data flows. Finally, we further improve energy efficiency and performance by co-optimization of intra-layer and inter-layer scheduling schemes. Our experimental results and analysis demonstrate the potential of the HiSo. Compared to the state-of-the-art design, the NEBULA, the HiSo can significantly improve energy efficiency, performance, and power efficiency by 1.03× ∼ 17.98×, 1.6× ∼ 50.7×, and 1.2× ∼ 229×, respectively.