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.

Recently, the emerging resistive random access memory (RRAM) shows its potential to construct a processing-in-memory (PIM) architecture. It supports a variety of computation modes, including the digital mode and the analog mode. Both modes can perform parallel computation inside an RRAM crossbar. However, the lack of automatic synthesis flow limits their application scenarios. Although previous works implement several large-scale applications, e.g., image processing algorithms and neural networks, using these two modes, most of their implementations are designed manually or semi-manually. In our view, the lack of a specific application representation is a limiting factor for developing a synthesis flow. Therefore, in this work, we propose the skeleton as an application representation. Users can model applications and their potential parallelism in RRAM with nested skeletons and primitive operations. Then, we propose SSR, a skeleton-based flow that can automatically synthesize large-scale applications to RRAM crossbars. For an application represented in skeletons, SSR first partitions it into the digital part and the potential analog part. After that, SSR optimizes primitive operations and allocates bounding boxes to skeletons for both parts under the guide of pre-synthesis results. Finally, SSR maps bounding boxes of skeletons onto crossbars to enable pipelined computation. Experimental evaluations on several popular applications show that SSR improves throughput, latency, and area multiple times over previous works.

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.

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.