Prefix adders are widely used in compute-intensive applications for their high speed. However, designing optimized prefix adders is challenging due to strict design rules and an exponentially large design space. We introduce PrefixGPT, a generative pre-trained Transformer (GPT) that directly generates optimized prefix adders from scratch. Our approach represents an adder's topology as a two-dimensional coordinate sequence and applies a legality mask during generation, ensuring every design is valid by construction. PrefixGPT features a customized decoder-only Transformer architecture. The model is first pre-trained on a corpus of randomly synthesized valid prefix adders to learn design rules and then fine-tuned to navigate the design space for optimized design quality. Compared with existing works, PrefixGPT not only finds a new optimal design with a 7.7% improved area-delay product (ADP) but exhibits superior exploration quality, lowering the average ADP by up to 79.1%. This demonstrates the potential of GPT-style models to first master complex hardware design principles and then apply them for more efficient design optimization.

As CMOS technology scales down, transistor aging has become a major threat to the long-term reliability of digital circuits. Existing solutions, such as aging-aware synthesis and approximate computing, suffer from either limited optimization space or early-stage accuracy loss. To address the above limitations, we propose ARCSyn, an aging-aware logic synthesis framework that generates accuracy-reconfigurable circuits capable of switching between accurate and approximate modes depending on aging conditions. Experimental results show that ARCSyn effectively extends circuit lifetime by 9.5 times while satisfying user-specified error constraints with only 3.72% area overhead.

Stochastic computing, an unconventional computing paradigm, often struggles with the costly random number generator (RNG)-based decorrelators. To solve this issue, we propose CoMix-D, a real-time solution that needs no RNGs. It uses a deterministic mixing architecture built from LiteSync, LiteDesync, and BitAggregator. Compared to state-of-the-art methods, CoMix-D achieves substantial savings of 80.1% in area and 59.9% in power without compromising accuracy.

Modern FPGAs support dual-output LUT to reduce the area of FPGA designs. Several existing works explored the use of dual-output LUTs in approximate computing. However, they are limited to small-scale arithmetic circuits. To address this issue, we propose QUADOL, a quality-driven approximate logic synthesis (ALS) method leveraging dual-output LUTs for modern FPGAs. It can approximately merge two single-output LUTs into a dual-output LUT. The selection of LUTs for approximate merging is formulated as a maximum matching problem to maximize area savings. To further enhance existing ALS methods, we also propose QUADOL+, a generic framework to integrate QUADOL into existing ALS methods. Experimental results showed that QUADOL+ achieves significant area reduction over prior works.

Electronic design automation requires unified circuit representations that jointly capture functionality, structure, and optimization behavior. Aligning heterogeneous circuit data (e.g., Verilog codes and AND-inverter graphs (AIGs)) remains challenging due to substantial semantic gaps. Existing contrastive learning approaches rely on carefully defined cross-modal anchors, which are often difficult to construct and limit alignment quality. We propose UniCircuit, an anchor-free multimodal framework that integrates Verilog, AIG, and synthesis flow representations. UniCircuit employs a singular value decomposition-based alignment mechanism to capture shared semantics without predefined anchors. Experimental results show that UniCircuit achieves 52.94% higher quality-of-result (QoR) prediction accuracy and 79.35% better cross-modal retrieval recall@5 compared to state-of-the-art methods.

Stochastic computing (SC) generally suffers from long latency. One solution is to apply proper random number sources (RNSs) to generate the bit streams. However, existing RNS designs either have low accuracy or high hardware cost. To address this drawback, motivated by the fact that a uniform spatial distribution generally leads to high accuracy for an SC circuit, we propose a basic architecture to produce a uniform spatial distribution and a further detailed implementation of it. For the implementation, we further propose a method to optimize its hardware cost and an algorithm following a guiding principle to improve its accuracy. The method for hardware cost optimization allows hardware cost reduction while keeping the accuracy. Our experimental results show that the proposed implementation achieves both high accuracy and low hardware cost. For example, compared to a state-of-the-art stochastic number generator design, our design can reduce hardware cost by over 80%, while achieving higher accuracy

Approximate computing is an emerging paradigm to improve the energy efficiency for error-tolerant applications. Many iterative approximate logic synthesis (ALS) methods were proposed to automatically design approximate circuits. However, as the sizes of circuits grow, the runtime of ALS grows rapidly. Thus, a crucial challenge is to ensure circuit quality while improving the efficiency of ALS. This work proposes a dual-phase iterative framework to accelerate the iterative ALS flows. In the first phase, a comprehensive circuit analysis is performed to gather the necessary information, including the error information. In the second phase, minimal incremental computation is employed based on the information from the first phase. The experimental results show that the proposed method achieves an acceleration by up to 21.8 × without loss of circuit quality compared to the state-of-the-art methods.

Approximate multipliers (AppMults) are widely employed in deep neural network (DNN) accelerators to reduce the area, delay, and power consumption. However, the inaccuracies of AppMults degrade DNN accuracy, necessitating a retraining process to recover accuracy. A critical step in retraining is computing the gradient of the AppMult, i.e., the partial derivative of the approximate product with respect to each input operand. Conventional methods approximate this gradient using that of the accurate multiplier (AccMult), often leading to suboptimal retraining results, especially for AppMults with relatively large errors. To address this issue, we propose a difference-based gradient approximation of AppMults to improve retraining accuracy. Experimental results show that compared to the state-of-the-art methods, our method improves the DNN accuracy after retraining by 4.10% and 2.93% on average for the VGG and ResNet models, respectively. Moreover, after retraining a ResNet18 model using a 7-bit AppMult, the final DNN accuracy does not degrade compared to the quantized model using the 7-bit AccMult, while the power consumption is reduced by 51%.

Single instruction, multiple data (SIMD) is a popular design style of logic-in-memory (LiM) architectures, which enables memory arrays to perform logic operations to achieve low energy consumption and high throughput. To implement a target function on the data stored in memory, the function is first transformed into a netlist of the supported logic operations by logic synthesis. Then, a scheduler transforms the netlist into an instruction sequence given to the architecture, where an instruction either performs a logic operation in the netlist on memory rows within a single array or copies the data from one array to another. Most existing schedulers focus on optimizing the execution sequence of the operations to minimize the number of memory rows needed, neglecting the energy-consuming copy instructions that cannot be avoided when working with arrays with limited sizes. In this work, we focus on reducing the number of copy instructions to decrease the total energy consumption. We propose MASIM, a multi-array scheduler for SIMD logic-in-memory architectures. It consists of a priority-based scheduling algorithm and an iterative improvement process. Compared to the best existing scheduler, MASIM reduces the number of copy instructions by 63.2% on average, which leads to a 28.0% reduction in energy. The experiment also shows that MASIM can be applied to various SIMD LiM architectures, showing its wide applicability.

As electronic devices become increasingly compact, designing printed circuit boards (PCBs) has become more challenging, particularly in the routing step, which is now more complex and time-consuming. In this work, we propose a method that applies generative pretrained transformers (GPTs) for PCB routing, referred to as GPCB routing. Initially, we convert the detailed routing information of the PCB into network flow-based encodings. Consequently, GPCB routing tokenizes routing patterns, effectively transforming the routing task into a form of token encoding prediction. To enhance prediction accuracy, we implement a 2-D sliding window with a local memory scheme, thereby expanding the sensing area of GPCB. Additionally, we propose a multi-information fusion scheme to identify the start and end points of multiple wires to further improve the prediction accuracy. Compared to existing routing methods, GPCB has the distinct advantage of learning routing strategies from human experts, breaking the limitations of traditional model-based routing approaches. Moreover, GPCB operates as a parallel routing method capable of predicting multiple routes simultaneously, resulting in significant enhancements in routing performance. Based on the experimental results, GPCB consistently outperforms in terms of routability, runtime, and wirelength.

Approximate computing is an emerging paradigm for designing error-resilient applications. It reduces circuit area, power, and delay at the cost of introducing errors. This article proposes a powerful technique, termed approximate resubstitution (AppResub), to approximately simplify the circuit. AppResub replaces a node’s function with a simpler approximate function on existing nodes in the circuit to reduce the hardware cost. Leveraging AppResub, an efficient flow for approximate logic synthesis (ALS) is developed by iteratively applying a set of promising AppResubs for circuit simplification. To evaluate errors caused by a set of AppResubs, a novel error model capable of efficiently computing an error upper bound is used to smartly apply AppResubs in the ALS flow. The experimental results demonstrate that compared to a state-of-the-art method, the proposed flow further reduces 20.9% area and 21.7% delay under the mean error distance constraint, while being$400\times $faster. The code of our flow is open-source.

This article introduces OpenLS-DGF, an adaptive logic synthesis dataset generation framework, to enhance machine-learning (ML) applications within the logic synthesis process. Previous dataset generation flows were tailored for specific tasks or lacked integrated ML capabilities. While OpenLS-DGF supports various ML tasks by encapsulating the three fundamental steps of logic synthesis: 1) Boolean representation; 2) logic optimization; and 3) technology mapping. It preserves the original information in both Verilog and ML-friendly GraphML formats. The Verilog files offer semi-customizable capabilities, enabling researchers to insert additional steps and incrementally refine the generated dataset. Furthermore, OpenLS-DGF includes an adaptive circuit engine that facilitates the final dataset management and downstream tasks. The generated OpenLS-D-v1 dataset comprises 46 combinational designs from established benchmarks, totaling over 966 000 Boolean circuits. OpenLS-D-v1 supports integrating new data features, making it more versatile for new tasks. This article demonstrates the versatility of OpenLS-D-v1 through four distinct downstream tasks: circuit classification, circuit ranking, quality of results (QoR) prediction, and probability prediction. Each task is chosen to represent essential steps of logic synthesis, and the experimental results show the generated dataset from OpenLS-DGF achieves prominent diversity and applicability. The source code and datasets are available athttps://github.com/Logic-Factory/ACE/blob/master/OpenLS-DGF.

In-memory computing (IMC) is a technique that enables memory to perform computation so that data transfer between processor and memory can be reduced, improving energy efficiency. A popular IMC design style is based on the single-instruction-multiple-data (SIMD) concept. The SIMD IMC can implement a high-level function by two steps: 1) synthesis and 2) scheduling. The former converts the high-level function into a netlist of the supported primitive logic operations, while the latter determines the execution sequence of the operations. To fully exploit the advantage of SIMD IMC, it is crucial to find a schedule for the given netlist with less memory usage, known as memory footprint (MF). In this work, we first propose an optimal scheduler that can minimize the MF for small netlists. It is at least$8\times $faster than the state-of-the-art optimal method. For large netlists, we propose a recursive partition-based scheduler consisting of a scheduling-friendly bipartition algorithm and our optimal scheduler. Compared to four state-of-the-art heuristic methods, ours reduces the MF by 54.7%, 48.9%, 44.0%, and 25.5%, respectively, under the same runtime. Our experiments also demonstrate that our scheduler achieves good end-to-end performance when applied to various IMC architectures. The code of our scheduler is made open-source.

Approximate computing emerges as an energy-efficient computing paradigm designed for applications that can tolerate errors. Many iterative methods for approximate logic synthesis (ALS) have been developed to automatically synthesize approximate circuits. Nonetheless, most of them overlook the potential of applying multiple local approximate changes (LACs) simultaneously in one iteration, which can significantly reduce the overall computation time. In this article, we propose AccALS 2.0, a novel framework for further accelerating iterative ALS flows, which is based on simultaneous selection of multiple LACs in a single round. However, there are two challenges for selecting multiple LACs. The first is that the mutual influence of multiple LACs can affect the estimation of the circuit error. The second is that there may exist conflicts among multiple LACs. To address these issues, first, we propose an efficient measure for the mutual influence between two LACs. With its help, we transform the problems of solving the LAC conflicts and selecting multiple LACs into a unified maximum independent set problem for solving. The experimental results showed that AccALS 2.0 outperforms state-of-the-art ALS methods in runtime, while achieving similar or better-circuit quality.

Accurate quantitative precipitation estimation (QPE) is essential for managing water resources, monitoring flash floods, creating hydrological models, and more. Traditional methods of obtaining precipitation data from rain gauges and radars have limitations such as sparse coverage and inaccurate estimates for different precipitation types and intensities. Symbolic regression, a machine learning method that generates mathematical equations fitting the data, presents a unique approach to estimating precipitation that is both accurate and interpretable. Using WSR-88D dual-polarimetric radar data from Oklahoma and Florida over three dates, we tested symbolic regression models involving genetic programming and deep learning, symbolic regression on separate clusters of the data, and the incorporation of knowledge-based loss terms into the loss function. We found that symbolic regression is both accurate in estimating rainfall and interpretable through learned equations. Accuracy and simplicity of the learned equations can be slightly improved by clustering the data based on select radar variables and by adjusting the loss function with knowledge-based loss terms. This research provides insights into improving QPE accuracy through interpretable symbolic regression methods.

Computing with memory is an energy-efficient computing approach. It pre-computes a function and stores its values in a lookup table (LUT), which can be retrieved at runtime. Approximate Boolean decomposition reduces the LUT size for implementing complex functions, but it takes a long time to find a decomposition with a minimal error. In this work, to address this issue, we propose an efficient Ising model-based approximate Boolean decomposition solver. First, a new column-based approximate disjoint decomposition method is proposed to fit the Ising model. Then, it is adapted to the Ising model-based optimization solver. Moreover, two improvement techniques are developed for an efficient search of the approximate disjoint decomposition when using simulated bifurcation to solve the Ising model. Experimental results show that compared to the state-of-the-art work, our approach achieves a 11% smaller mean error distance with an average 1.16× speedup when approximately decomposing 16-input Boolean functions.

Stochastic computing (SC) is an unconventional computing paradigm with unique features. Designing SC circuits is dramatically different from designing binary computing (BC) circuits. To support the agile design of SC circuits, we propose SCGen, a versatile generator framework, which provides users with a C++ interface to easily specify SC circuits and supports 1) accelerated accuracy simulation, 2) accelerated design space exploration (DSE) for accuracy maximization guided by simulated annealing (SA) and genetic algorithm (GA), 3) circuit optimization by random number source (RNS) sharing, 4) circuit verification via symbolic expression analysis, and 5) automatic Verilog code generation. Furthermore, we extend SCGen to also support agile design of hybrid SC-BC circuits. The experimental results show that our proposed DSE acceleration methods achieve up to 59x speedup, the DSE with SA and GA can get an average reduction of 4.0% and 12.7%, respectively, in accuracy loss compared to random search, and RNS sharing reduces the average area and power by 41% and 47%, respectively.

Approximate computing is an effective computing paradigm to reduce area, delay, and power for error-tolerant applications. Average error is a widely-used metric for approximate circuits, measuring the average deviation between the outputs of exact and approximate circuits. This paper proposes VACSEM, a formal method to verify average errors in approximate circults using simulatlon-enhanced model counting. VACSEM leverages circuit structure information and logic simulation to speed up verification. Experimental results show that VACSEM is on average 35 x faster than the state-of-the-art method.

Many in-memory computing (IMC) designs based on single instruction multiple data (SIMD) concept have been proposed in recent years to perform primitive logic operations within memory, for improving energy efficiency. To fully exploit the advantage of SIMD IMC, it is crucial to identify an optimized schedule for the operations with less intermediate memory usage, known as memory footprint (MF). In this work, we implement a recursive partition-based scheduler which consists of our scheduler-friendly partition algorithm and a modified optimal scheduler. Compared to three state-of-the-art heuristic strategies, ours can reduce MF by 56.9%, 46.0%, and 31.9%, respectively.

Approximate high-level synthesis (HLS) technique has been proposed in recent years to produce approximate designs automatically from a high-level description. All existing approximate HLS methods work on two-operand approximate units. In this paper, we propose CLAST, a cross-layer approximate high-level synthesis using configurable three-operand approximate adders. The experimental results show that CLAST outperforms previous HLS tools by achieving 57.0% improvement in area-delay product, while maintaining a high accuracy.

Recently, the bit-serial-based processing-in-memory (PIM) has evolved as a promising solution to enhance the computing performance of data-intensive applications, due to its high performance and programmability. However, it is absent that a compiler can automatically convert an arbitrary Boolean function (generic workload) into PIM instructions, with optimized scheduling w.r.t. the varying hardware resource and specification. To fill the gap, we develop a logic compiler for bit-serial-based PIM (PIMLC). In PIMLC, we propose a workload-resource-aware scheduling to minimize the execution latency of a given parallel workload. Thanks to PIMLC, PIM can achieve$15.55\times$and$19.03\times$speedup (geo-mean) for SRAM- and ReRAM-PIM respectively, compared to the naive scheduling of prior work. PIMLC is publicly available at: https://github.com/Intelligent-Computing-Research-GroupIPIMLC.

Processing-in-Memory (PIM) has been widely explored for accelerating data-intensive machine learning computation that mainly consists of general-matrix-multiplication (GEMM), by mitigating the burden of data movements and exploiting the ultra-high memory parallelism. The two mainstreams of PIM, the analog- and digital-type, have both been exploited in accelerating machine learning workloads by numerous outstanding prior works. Currently, the digital-PIM is increasingly favored due to the broader computing support and the avoidance of errors caused by intrinsic non-idealities, e.g., process variation. Nevertheless, it still lacks further optimization considering the characteristics of the GEMM computation, including better efficient data layout and scheduling, and the ability to handle the sparsity of activations at the bit-level. To boost the performance and efficiency of digital SRAM PIM, we propose the architecture called VSPIM that performs the computation in a bit-serial fashion, with unique support of vector-scalar computing pattern. The novelties of the VSPIM can be concluded as follows: 1) support bit-serial based scalar-vector computing via ingenious parallel bit-broadcasting; 2) refine the GEMM mapping strategy and computing pattern to enhance performance and efficiency; 3) powered by the introduced scalar-vector operation, the bit-sparsity of activation is leveraged to halt unnecessary computation to maximize efficiency and throughput. Our comprehensive evaluation shows that, compared to the state-of-the-art SRAM-based digital-PIM design (Neural Cache), VSPIM can significantly boost the performance and energy efficiency by up to$8.87\times$and$4.81\times$respectively, with negligible area overhead, upon multiple representative neural networks.

Given the stringent requirements of energy efficiency for Internet-of-Things edge devices, approximate multipliers, as a basic component of many processors and accelerators, have been constantly proposed and studied for decades, especially in error-resilient applications. The computation error and energy efficiency largely depend on how and where the approximation is introduced into a design. Thus, this article aims to provide a comprehensive review of the approximation techniques in multiplier designs ranging from algorithms and architectures to circuits. We have implemented representative approximate multiplier designs in each category to understand the impact of the design techniques on accuracy and efficiency. The designs can then be effectively deployed in high-level applications, such as machine learning, to gain energy efficiency at the cost of slight accuracy loss.

Approximate computing is an energy-efficient computing paradigm for error-tolerant applications. To automatically synthesize approximate circuits, many iterative approximate logic synthesis (ALS) methods have been proposed. However, most of them do not consider applying multiple local approximate changes (LACs) in a single round, which can lead to a much shorter runtime. In this paper, we propose AccALS, a novel framework for Accelerating iterative ALS flows, based on simultaneous selection of multiple LACs in a single round. When selecting multiple LACs, there may exist conflicts among them. One important component of AccALS is a novel method to solve the conflicts. Another is an efficient measure for the mutual influence between two LACs. With its help, the problem of selecting multiple LACs is transformed into a maximum independent set problem to solve. The experimental results showed that compared to a state-of-the-art method, AccALS accelerates by up to 24.6× with a negligible circuit quality loss.

Approximate computing is an effective computing paradigm to improve energy efficiency for error-tolerant applications. Approximate logic synthesis (ALS) methods are designed to generate approximate circuits under certain error constraints. This paper focuses on ALS methods under the maximum error constraint and proposes MECALS, a maximum error checking technique for ALS. MECALS models maximum error using partial Boolean difference and performs fast error checking with SAT sweeping. Based on MECALS, we design an efficient ALS flow. Our experimental results show that compared to a state-of-the-art ALS method, our flow is 13× faster and improves area and delay reduction by 39.2% and 26.0%, respectively.

Storing pre-computed results of frequently-used functions into lookup table (LUT) is a popular way to improve energy efficiency, but its advantage diminishes as the number of input bits increases. A recent work shows that by decomposing the target function approximately, the total LUT entries can be dramatically reduced, leading to significant energy saving. However, its heuristic approximate decomposition algorithm leads to sub-optimal approximation quality. Also, its rigid hardware architecture only supports disjoint decomposition and may have unnecessary extra power consumption sometimes. To address these issues, we develop a novel approximate decomposition algorithm based on beam search and simulated annealing, which can reduce 11.1% approximation error. We also propose a non-disjoint approximate decomposition method and two reconfigurable architectures. The first has 10.4% less error using 19.2% less energy and the second has 23.0% less error with same energy consumption compared to the state-of-the-art design.

Approximate computing is a promising computing paradigm for designing energy-efficient systems. To automatically generate approximate circuits, many local iterative approximate logic synthesis (ALS) methods have been proposed. They need to specify a particular local approximation change and apply it to modify the local structure of a circuit in each round. This will lose some global optimization opportunities, thus, degrading circuit quality. In this paper, we propose DASALS, a differentiable archltecture search-driven ALS method, to directly search the whole circuit structure to obtain the approximate circuits with better circuit quality-accuracy trade-off. DASALS is based on a proper continuous relaxation of the discrete search space of ALS and an efficient gradient descent-based search algorithm. The experimental results show that compared with a state-of-the-art method, DASALS on average reduces the area-delay product by 10.82% and mean square error by 10.93%.

Transistor network minimization is an important step in designing new standard cells. Existing methods for minimizing transistor networks all rely on some heuristic techniques. Hence, there is still room for further improvement. In this work, we propose MiniTNtk, an exact synthesis-based method for minimizing transistor networks. It models the generation of the transistor network for a Boolean function as a Boolean satisfiability (SAT) problem and can return a transistor network with the fewest transistors. Furthermore, sometimes, it is necessary to limit the number of transistors in series. We propose an extension of MiniTNtk for minimizing the transistor network under a bound on the number of transistors in series. The experimental results showed that MiniTNtk is the first method that achieves the optimal transistor networks for a set of Boolean functions with known optimal solutions to the best of our knowledge. Additionally, compared with related works, MiniTNtk reduces the number of transistors by up to 9.39% over all 4-input P-class representative functions. Moreover, the experiment on a complex Boolean function demonstrated the high efficiency of MiniTNtk.

Logic synthesis (LS) is a process that transforms a high-level logic circuit description into a gate-level netlist, typically via a heuristic algorithm. Such a process can be decomposed into a series of transformation primitives, where each primitive optimizes the netlist while preserving the functional equivalence. However, identifying a desirable primitive sequence (PS) to achieve design goals is challenging, due to the immense design space. Recent advances in artificial intelligence offer the opportunity to leverage machine learning techniques to tackle the combinatorial optimization problem associated with PS. Unfortunately, the existing works either require time-consuming training for each circuit or incur high computational costs. To address these issues, we redefine the optimization of LS as a sequence generation problem and propose a generative pre-trained transformer (GPT) with offline reinforcement learning, which is named as GPT-LS. Thanks to the OpenABC-D dataset, GPT-LS is pre-trained on diverse circuits and its massive intermediate data during the synthesis, by utilizing the offline reinforcement learning technique of decision transformer. Then, GPT-LS is able to generate PS for unseen circuits to conduct optimized LS. According to our comprehensive experiments, GPT-LS achieves results that match those of previous state-of-the-art methods in a significantly shorter time. It is available at: github.com/Intelligent-Computing-Research-Group/GPT-LS.

Approximate computing is an emerging paradigm for error-tolerant applications. By introducing a reasonable amount of inaccuracy, both the area and delay of a circuit can be reduced significantly. To produce approximate circuits automatically, many approximate logic synthesis (ALS) algorithms are proposed. However, they mainly focus on area reduction and are not optimal in reducing the circuit delay. In this article, we propose HEDALS, a Highly Efficient Delay-driven ALS framework, which supports various types of local approximate changes (LACs), circuit representations, and average error metrics. To reduce delay, HEDALS builds a critical error graph (CEG) consisting of nodes on the critical paths and error information, and finds an optimized set of LACs in the CEG by either a maximum flow-based method or a priority cut-based method. The resulting set of LACs is applied to shorten all critical paths simultaneously so that the circuit delay is reduced. Besides, the simultaneous application of multiple LACs also makes HEDALS extremely fast. Compared to a state-of-the-art method, on average, HEDALS can reduce the circuit delay by 32.3%, while being$167\times $faster. The code of HEDALS is made open-source.

Stochastic computing (SC) is a re-emerging paradigm to realize complicated computation by simple circuitry. Although SC has strong tolerance to bit flip errors, manufacturing defects may still cause unacceptably large computation errors. SC circuits commonly adopt linear feedback shift registers (LFSRs) for stochastic bit stream generation. In this study, we observe that the computation error of a faulty LFSR-based SC circuit can be reduced by LFSR reseeding. We propose novel methods to use LFSR reseeding to 1) repair a faulty SC circuit and 2) minimize an SC circuit by constant replacement. Our experiments show the effectiveness of our proposed methods. Notably, the proposed SC circuit minimization method achieves an average 36% area-delay product reduction over the state-of-the-art fully-shared LFSR design with no reduction of the computation accuracy.

One main fault-tolerant method for a neural network accelerator based on resistive random access memory crossbars is the programming-based method, which is also known as write-and-verify (W-V). In the basic W-V scheme, all devices in crossbars are programmed repeatedly until they are close enough to their targets, which costs huge overhead. To reduce the cost, we optimize the W-V scheme by proposing a probabilistic termination criterion on a single device and a systematic optimization method on multiple devices. Furthermore, we propose a joint algorithm that assists the novel W-V scheme by incremental retraining, which further reduces the W-V cost. Compared to the basic W-V scheme, our proposed method improves the accuracy by 0.23% for ResNet18 on CIFAR10 with only 9.7% W-V cost under variation with σ = 1.2.

Approximate computing is an emerging computing paradigm to design energy-efficient systems. Many greedy approximate logic synthesis (ALS) methods have been proposed to automatically synthesize approximate circuits. They typically need to consider all local approximate changes (LACs) in each iteration of the ALS flow to select the best one, which is time-consuming. In this paper, we propose SEALS, a Sensitivity-driven Efficient ALS method to speed up a greedy ALS flow. SEALS centers around a newly proposed concept called sensitivity, which enables a fast and accurate error estimation method and an efficient method to filter out unpromising LACs. SEALS can handle any statistical error metric. The experimental results show that it outperforms a state-of-the-art ALS method in runtime by 12X to 15X without reducing circuit quality.

Approximate multipliers have attracted significant attention of researchers for designing low-power systems. The most area-consuming part of a multiplier is its compressor tree (CT). Hence, the prior works proposed various approximate compressors to reduce the area of the CT. However, the compression strategy for the approximate compressors has not been systematically studied: Most of the prior works apply their ad hoc strategies to arrange approximate compressors. In this work, we propose OPACT, a method for optimizing approximate compressor tree for approximate multiplier. An integer linear programming problem is first formulated to co-optimize CT's area and error. Moreover, since different connection orders of the approximate compressors can affect the error of an approximate multiplier, we formulate another mixed-integer programming problem for optimizing the connection order. The experimental results showed that OPACT can produce approximate multipliers with an average reduction of 24.4% and 8.4% in power-delay product and mean error distance, respectively, compared to the best existing designs with the same types of approximate compressors used.

Univariate functions are widely used. Several recent works propose to implement them by an unconventional computing paradigm, stochastic computing (SC). However, existing SC designs either have a high hardware cost due to the area-consuming randomizer or a low accuracy. In this work, we propose a low-cost high-accuracy SC architecture for univariate functions. It consists of only a single stochastic number generator and a minimum number of D flip-flops. We also apply three methods, random number source (RNS) negating, RNS scrambling, and input scrambling, to improve the accuracy of the architecture. To efficiently configure the architecture to achieve a high accuracy, we further propose a design space exploration algorithm. The experimental results show that compared to the conventional architecture, the area of the proposed architecture is reduced by up to 76%, while its accuracy is close to or sometimes even higher than that of the conventional architecture.

High-level synthesis (HLS) automatically transforms highlevel programming language into RTL design. It is widely used to program FPGAs as accelerators. HLS tools have many knobs that can be controlled by users to produce designs with different area-latency trade-offs.

Probability propagation is an important task used in logic network analysis, which propagates signal probabilities from its primary inputs to its primary outputs. It has many applications such as power estimation, reliability analysis, and error analysis for approximate circuits. Existing methods for the task can be divided into two categories: simulation-based and probability-based methods. However, most of them suffer from low accuracy or bad scalability. In this work, we propose ASPPLN, a method for accelerated symbolic probability propagation in logic network, which has a linear complexity with the network size. We first introduce a new definition in a graph called redundant input and take advantage of it to simplify the propagation process without losing accuracy. Then, a technique called symbol limitation is proposed to limit the complexity of each node's propagation according to the partial probability significances of the symbols. The experimental results showed that compared to the existing methods, ASPPLN improves the estimation accuracy of switching activity by up to 24.70%, while it also has a speedup of up to 29X.

Stochastic computing (SC) generally suffers from long latency. One solution is to apply proper random number sources (RNSs). Nevertheless, current RNS designs either have high hardware cost or low accuracy. To address the issue, motivated by that the uniform spatial distribution generally leads to a high accuracy for an SC circuit, we propose a basic architecture to generate the uniform spatial distribution and a further detailed implementation of it. For the implementation, we further propose a method to optimize its hardware cost and a method to optimize its accuracy. The method for hardware cost optimization can optimize the hardware cost without affecting the accuracy. The experimental results show that our proposed implementation can achieve both low hardware cost and high accuracy. Compared to the state-of-the-art stochastic number generator design, the proposed design can reduce 88% area with close accuracy.

High-level synthesis (HLS) transforms designs specified by high-level programming language into RTL designs. In order to get the optimal designs, many design space exploration (DSE) methods are proposed. However, most of them consider the HLS tool as a black box, ignoring crucial information from the synthesis process, particularly the scheduling step. In this work, we propose to extract some useful information from scheduling to guide the DSE and develop a genetic algorithm (GA)-based DSE method based on our in-house HLS tool. The experimental results show that our method can obtain more Pareto-optimal points than the counterpart without using the scheduling information. It also outperforms a traditional GA-based HLS DSE method by using only a quarter of the total run time. For a large benchmark, our method finds 95.7% Pareto-optimal designs by visiting only 0.18% total promising design points.

Approximate computing is an emerging low-power design technique for error-tolerant applications. One key enabling technique for approximate circuit design is approximate logic synthesis (ALS). Many ALS methods are based on a scheme that iteratively selects one single local approximate change (LAC) in each round until the error bound is reached. However, this scheme fails to consider the joint effect of multiple LACs whose induced errors may counteract with each other when applied simultaneously. In this work, we propose a method to select multiple LAC candidates in a single round under a given bound on maximum error distance (MaxED). It first builds a miter by adding a multiplexer into the network for each LAC candidate in the network. Then, a quantified satisfiability problem is formulated on the miter and solved to obtain a maximal set of LACs that can be applied simultaneously. The experimental results show that under the normalized MaxED bound of 1%, our method reduces the circuit area by up to 39%, which is 20% higher than the area reduction achieved by a baseline method that iteratively selects one single LAC per round.

Approximate multiplier is a fundamental arithmetic block for designing energy-efficient systems, which can be realized by approximate 4-2 compressors. However, the prior works all design approximate 4-2 compressors manually, so the area optimality of the circuits cannot be guaranteed. In this paper, given any input distribution and error bound, we propose MinAC, an exact synthesis-based method to automatically produce minimal-area approximate 4-2 compressors. To directly obtain an area-optimal circuit using an industrial gate library, gates with multiple outputs are taken into account during the exact synthesis. The experimental results show that compared with the existing methods, MinAC on average can produce approximate 4-2 compressors with 39.8%, 44.2%, and 7.9% reduction in area-delay-product, power-delay-product, and mean error distance, respectively. The code of MinAC is available at https://github.conySJTU-ECTL/MinAC.

Approximate computing is a promising alternative to improve energy efficiency for IoT devices on the edge. This work proposes a piecewise-linearly-approximated and unbiased floating-point approximate multiplier with run-time configurability. We provide a theoretically sound formulation that turns multiplication approximation to an optimization problem. With the formulation and findings, a multi-level architecture is proposed to easily incorporate run-time configurability and module execution parallelism. Finally, the proposed multiplier is further optimized to reduce the circuit implementation complexity, making the multiplier linearly dependent on the precision requirement, instead of quadratically or exponentially as in prior work. When compared to the prior state-of-the-art approximate floating-point multiplier, ApproxLP M. Imaniet al, “ApproxLP: Approximate multiplication with linearization and iterative error control,” inProc. ACM/IEEE Des. Autom. Conf., 2019, pp. 1–6., the proposed multiplier outperforms in all the aspects including accuracy, area, and delay. By replacing a full-precision floating-point multiplier in GPU, the proposed design can improve the energy efficiency for various edge computing tasks. Even with Level 1 approximation, the proposed multiplier improves energy efficiency up to 20× for machine learning on CIFAR-10, with almost negligible accuracy loss.

Approximate computing is an emerging strategy to improve the energy efficiency of many error-tolerant applications. To design an approximate circuit automatically, many approximate logic synthesis (ALS) methods have been proposed, among which many are greedy. To improve the synthesis quality of these greedy methods, one key is to calculate the errors of all candidate approximate transformations accurately. However, the traditional simulation-based method is time consuming. Instead, many existing methods just perform quick but inaccurate error estimation. In this work, to improve both the accuracy and runtime of error estimation, we propose VECBEE, a versatile efficiency–accuracy configurable batch error estimation method for greedy ALS. It is based on Monte Carlo simulation and an efficient technique to capture whether a signal change due to an introduced approximation will be propagated to each primary output. VECBEE is generally applicable to any statistical error measurement, such as error rate and average error magnitude, and any graph-based circuit representation. It allows a flexible tradeoff between the error estimation accuracy and the runtime, while even the fully accurate version is much faster than the traditional simulation-based method. We apply VECBEE to two representative greedy ALS methods and demonstrate its effectiveness in generating better approximate circuits. The code of VECBEE is made open source.

Resistance variation in memristor device hinders the practical use of resistive random access memory (RRAM) crossbars as neural network (NN) accelerators. Previous fault-tolerant methods cannot effectively handle cycle-to-cycle variation (CCV). Many of them also use a pair of positive-weight and negative-weight crossbars to store a weight matrix, which implicitly enhances the fault tolerance but doubles the hardware cost. This paper proposes a novel solution that dramatically reduces the NN accuracy loss under CCV, while still using a single crossbar to store a weight matrix. The key idea is to introduce digital offsets into the crossbar, which further enables two techniques to conquer CCV. The first is a variation-aware weight optimization method that determines the optimal target weights to be written into the crossbar; the second is a post-writing tuning method that optimally sets the digital offsets to recover the accuracy loss due to variation. Simulation results show that the accuracy maintains the ideal value for LeNet with MNIST and only drops by 2.77% over the ideal value for ResNet-18 with CIFAR-10 under a large resistance variation. Moreover, compared to state-of-the-art fault-tolerant methods, our method achieves a better NN accuracy with at least 50% fewer crossbars.

Multiplier is an important arithmetic circuit. State-of-the-art designs consist of a partial product generator (PPG), a compressor tree (CT), and a carry propagation adder (CPA), with the last two components dominating the area and delay. Existing representative works optimize the CT and the CPA separately, adding a rigid boundary between these two components. In this paper, we break the boundary by proposing GOMIL, a global optimization for multiplier by integer linear programming. Two ILP sub-problems are first formulated to optimize the CT and the prefix structure in the CPA, respectively. Then, they are unified to provide a global optimization to the multiplier. The proposed method is applicable to not only multipliers with the AND gate-based PPG, but also those with Booth encoding-based PPG. The experimental results showed that the multipliers optimized by GOMIL can reduce the power-delay product by up to 71%, compared to the state-of-the-art multipliers developed in industry. The code of GOMIL is made open-source.

As the scale of VLSI circuits increases rapidly, multi-FPGA prototyping systems have been widely used for logic verification. Due to the limited number of connections between FPGAs, however, the routability of prototyping systems is a bottleneck. As a consequence, timing division multiplexing (TDM) technique has been proposed to improve the usability of prototyping systems, but it causes a dramatic increase in system delay. In this paper, we propose ALIFRouter, a practical architecture-level inter-FPGA router, to improve the chip performance by reducing the corresponding system delay. ALIFRouter consists of three major stages, including i) routing topology generation, ii) TDM ratio assignment, and iii) system delay optimization. Additionally, a multi-thread parallelization method is integrated into the three stages to improve the efficiency of ALIFRouter. With the proposed algorithm, major performance indicators of multi-FPGA systems such as signal multiplexing ratio can be improved significantly.

A popular way to implement an arithmetic function is through a lookup table (LUT), which stores the pre-computed outputs for all the inputs. However, its size grows exponentially with the number of input bits. In this work, targeting at computing kernels of error-tolerant applications, we propose DALTA, a reconfigurable decomposition-based approximate lookup table architecture, to approximately implement those kernels with dramatically reduced size. We also propose integer linear programming-based approximate decomposition methods to map a given function to the architecture. Our architecture features with low energy consumption and high speed. The experimental results show that our architecture achieves energy and latency savings by 56.5% and 92.4%, respectively, over the state-of-the-art approximate LUT architecture.

Stochastic computing (SC) operates on stochastic bit streams, which can realize complex arithmetic functions with simple circuits. A previous work shows that by introducing a little approximation error for the target function, the cost of SC circuits can be dramatically reduced. However, the previous heuristic method only explores a limited subset of the solution space, so the optimality of the results cannot be guaranteed. In this paper, we propose MinSC, an exact synthesis-based method for minimal-area stochastic circuits under relaxed error bound. First, a novel search method is proposed to find the best approximation polynomial for a target function. Then, considering gates with different fanin numbers and areas, an exact SC synthesis method using satisfiability modulo theories is designed to obtain an area-optimal SC circuit realizing the best approximation polynomial. The experimental results show that compared with the state-of-the-art method, given an error ratio 0.05, MinSC on average reduces the gate number, area, delay, and area-delay-product of the SC circuits by 60.24%, 47.24%, 7.10%, 57.07%, respectively.

Approximate computing is an emerging circuit design paradigm. It improves the energy efficiency of circuits by introducing some errors. Recent works propose to apply approximate multipliers to design low-power neural network (NN) accelerators. Different from existing methods, in this paper, we advocate a method that integrates approximate logic synthesis (ALS) into the design loop of low-power NN accelerators. ALS automatically synthesizes a good approximate circuit and can take input distribution into consideration. With the help of ALS, the NN computation pattern can be exploited to design an approximate multiplier that fits better with the NN. The experimental results show that the proposed method can generate an extremely small approximate multiplier with area only 4.2% of the accurate version, while it can still achieve a high accuracy of 97.9% for LeNet-5 on MNIST dataset.

Multiplications have been commonly conducted in quantized CNNs, filters, and reconfigurable cores, and so on, which are widely deployed in mobile and embedded applications. Most multipliers are designed to perform multiplications with symmetric bit-widths, i.e., n - by n -bit multiplication. Such features would cause extra area overhead and performance loss when m - by n -bit multiplications ( m > n ) are deployed in the same hardware design, resulting in inefficient multiplication operations. It is highly desired and challenging to propose a reconfigurable multiplier design to accommodate operands with both symmetric and asymmetric bit-widths. In this work, we propose a reconfigurable approximate multiplier to support multiplications at various precisions, i.e., bit-widths. Unlike prior works of approximate adders assuming a uniform weight distribution with bit-wise independence, scenarios like a quantized CNN may have a centralized weight distribution and hence follow a Gaussian-like distribution with correlated adjacent bits. Thus, a new block-based approximate adder is also proposed as part of the multiplier to ensure energy-efficient operation with an awareness of the bit-wise correlation. Our experimental results show that the proposed approximate adder significantly reduces the error rate by 76% to 98% over a state-of-the-art approximate adder for Gaussian-like distribution scenarios. Evaluation results show that the proposed multiplier is 19% faster and 22% more power saving than a Xilinx multiplier IP at the same bit precision and achieves a 23.94-dB peak signal-to-noise ratio, which is comparable to the accurate one of 24.10 dB when deployed in a Gaussian filter for image processing tasks.

Neural network (NN) computing contains a large number of multiply-and-accumulate (MAC) operations. The performance of NN accelerator is limited with the traditional von Neumann architecture due to the tremendous off-chip memory accesses. Resistive random-access memory (ReRAM)-based crossbars can naturally perform matrix–vector multiplication (MVM) operations and are well suitable for NN accelerators. In the existing ReRAM-based NN accelerators, the synaptic weights represented by the conductances of ReRAMs are mainly based on the binary coding. However, the imperfect fabrication process combined with stochastic filament-based switching leads to resistance variations of ReRAMs, which can significantly alter the weights in binary synapses and degrade the NN accuracy. Moreover, the NN accuracy further deteriorates with multilevel cells (MLCs) used for reducing hardware overhead. In this article, a novel unary coding of synaptic weights is proposed to overcome the resistance variations of MLCs and achieve reliable ReRAM-based neuromorphic computing. A variation-aware optimal mapping scheme is also proposed in compliance with the unary coding to guarantee high accuracy by leveraging a unique feature of unary coding—the existence of multiple ways to represent the same value. The optimal mapping obtains very small errors for weights with resistance variations of MLCs. Our simulation results show that under resistance variations, the proposed method achieves less than 0.08% and 3.43% accuracy loss on CIFAR10 and ImageNet, respectively, compared to the ideal accuracy. With each synaptic weight represented by four 2-b MLCs, the proposed method improves the accuracy over the traditional binary coding scheme by 83.39% and 87.6% for CIFAR10 and ImageNet, respectively.

Quantized CNNs, featured with different bit-widths at different layers, have been widely deployed in mobile and embedded applications. The implementation of a quantized CNN may have multiple multipliers at different precisions with limited resource reuse or one multiplier at higher precision than needed causing area overhead. It is then highly desired to design a multiplier by accounting for the characteristics of quantized CNNs to ensure both flexibility and energy efficiency. In this work, we present a reconfigurable approximate multiplier to support multiplications at various precisions, i.e., bit-widths. Moreover, unlike prior works assuming uniform distribution with bit-wise independence, a quantized CNN may have centralized weight distribution and hence follow a Gaussian-like distribution with correlated adjacent bits. Thus, a new block-based approximate adder is also proposed as part of the multiplier to ensure energy efficient operation with awareness of bit-wise correlation. Our experimental results show that the proposed adder significantly reduces the error rate by 76-98% over a state-of-the-art approximate adder for such scenarios. Moreover, with the deployment of the proposed multiplier, which is 17% faster and 22% more power saving than a Xilinx multiplier IP at the same precision, a quantized CNN implemented in FPGA achieves 17% latency reduction and 15% power saving compared with a full precision case.

Approximate computing is an emerging design technique for error-resilient applications. It improves circuit area, power, and delay at the cost of introducing some errors. Approximate logic synthesis (ALS) is an automatic process to produce approximate circuits. This paper proposes approximate resubstitution with approximate care set and uses it to build a simulation-based ALS flow. The experimental results demonstrate that the proposed method saves 7%-18% area compared to state-of-the-art methods. The code of ALSRAC is made open-source.

Neural network (NN) computing contains a large number of multiply-and-accumulate (MAC) operations, which is the speed bottleneck in traditional von Neumann architecture. Resistive random access memory (ReRAM)-based crossbar is well suited for matrix-vector multiplication. Existing ReRAM-based NNs are mainly based on the binary coding for synaptic weights. However, the imperfect fabrication process combined with stochastic filament-based switching leads to resistance variations, which can significantly affect the weights in binary synapses and degrade the accuracy of NNs. Further, as multi-level cells (MLCs) are being developed for reducing hardware overhead, the NN accuracy deteriorates more due to the resistance variations in the binary coding. In this paper, a novel unary coding of synaptic weights is presented to overcome the resistance variations of MLCs and achieve reliable ReRAM-based neuromorphic computing. The priority mapping is also proposed in compliance with the unary coding to guarantee high accuracy by mapping those bits with lower resistance states to ReRAMs with smaller resistance variations. Our experimental results show that the proposed method provides less than 0.45% and 5.48% accuracy loss on LeNet (on MNIST dataset) and VGG16 (on CIFAR-10 dataset), respectively, with acceptable hardware cost.

Stochastic computing (SC) has been widely used in neural networks (NNs) due to its simple hardware cost and high fault tolerance. Conventionally, SC-based NN accelerators adopt a hybrid stochastic-binary format, using an accumulative parallel counter to convert bitstreams into a binary number. This method, however, sacrifices the fault tolerance and causes a high hardware cost. In order to fully exploit the superior fault tolerance of SC, taking a ternary neural network (TNN) as an example, we propose a parallel SC-based NN accelerator purely using bitstream computation. We apply a bitonic sorting network for simultaneously implementing the accumulation and activation function with parallel bitstreams. The proposed design not only has high fault tolerance, but also achieves at least 2.8× energy efficiency improvement over the binary computing counterpart.

One of the challenges stochastic computing (SC) faces is the high cost of stochastic number generators (SNG). A solution to it is inserting D flip-flops (DFFs) into the circuit. However, the accuracy of the stochastic circuits would be affected and it is crucial to capture it. In this work, we propose an efficient method to analyze the accuracy of stochastic circuits with DFFs inserted. Furthermore, given the importance of multiplication, we apply this method to analyze stochastic multiplier with DFFs inserted. Several interesting claims are obtained about the use of probability conversion circuits. For example, using weighted binary generator is more accurate than using comparator. The experimental results show the correctness of the proposed method and the claims. Furthermore, the proposed method is up to 560× faster than the simulation-based method.

With the downscaling of CMOS technology, the circuit design margin becomes more and more tight due to wider guardband, which is required to counteract the severer transistor aging and variations. Thus, reliability-enhanced circuit design is urgently needed to reduce the guardband. In this paper, a reliability-enhanced design framework based on approximate synthesis is proposed to completely eliminate the aging guardband. It mainly includes two key parts: first, a forward reliability simulation flow supporting statistical static timing analysis (SSTA) is performed to estimate the path failure rates after aging; if the timing constraints are not satisfied, then a backward delay-driven approximate logic synthesis flow will perform approximate local changes on the critical paths to reduce the delay until the reliability requirement is finally satisfied and no aging guardband is needed. The results show that the approximate circuit has a smaller aged delay than the original circuit, so that the path failure rates are significantly decreased. It indicates that the proposed design flow can convert the timing errors that have fatal impact on applications, into negligible error on low-significance bits to improve the resilience of circuits, which provides a new perspective of reliability-enhanced design at nanoscale.

Approximate computing is a promising alternative to improve energy efficiency for IoT devices on the edge. This work proposes an optimally approximated and unbiased floating-point approximate multiplier with runtime configurability. We provide a theoretically sound formulation that turns multiplication approximation to an optimization problem. With the formulation and findings, a multilevel architecture is proposed to easily incorporate runtime configurability and module execution parallelism. Finally, an optimization scheme is applied to improve the area, making it linearly dependent on the precision, instead of quadratically or exponentially as in prior work. In addition to the optimal approximation and configurability, the proposed design has an efficient circuit implementation that uses inversion, shift and addition instead of complex arithmetic operations. When compared to the prior state-of-the-art approximate floating-point multiplier, ApproxLP [30], the proposed design outperforms in all aspects including accuracy, area, and delay. By replacing the regular full-precision multiplier in GPU, the proposed design can improve the energy efficiency for various edge computing tasks. Even with Level 1 approximation, the proposed design improves energy efficiency up to 122× for machine learning on CIFAR-10, with almost negligible accuracy loss.

Stochastic computing (SC) is an emerging paradigm for designing circuits to perform complicated computation with simple circuitry. Although SC circuits have small area and critical-path delay, due to the need of many clock cycles to perform computation, they have a large overall latency and energy consumption. One solution to this problem is to further minimize the circuits. In this work, we explore target function approximation to derive an SC circuit with significantly reduced area and delay. We propose two static methods that first construct a set of functions close to the given target function and then select the best synthesized SC circuit realizing one of these functions. We also propose an efficient dynamic method that simultaneously searches for the best approximated target function and the corresponding minimized SC circuit. The experimental results show that on average, our dynamic method dramatically reduces the area, critical-path delay, and area-delay product of the SC circuits by 80%, 59%, and 91%, respectively, over the state-of-the-art Maclaurin polynomial-based method for a given error bound of 2%. The code of our methods is made open-source.

Recently, due to the high fault tolerance and low hardware cost, stochastic computing (SC)-based neural network (NN) accelerators have been widely studied. One big challenge of it is the implementation of accumulation and activation function. The existing designs have problems of low accuracy and high energy consumption. In this paper, based on a special type of stochastic encoding, the parallel thermometer coding, we propose an accurate design for the combination of the accumulation and non-linear function, which is called a non-linear adder. Dedicated designs for the non-linear adders with the common activation functions such as hyperbolic tangent (tanh), logistic (or sigmoid), and rectified linear unit (ReLU) are proposed using the bitonic sorting network and the selective interconnect. The experimental results show that, at the cost of the area, the proposed nonlinear adder achieves more than three orders of magnitude improvement in accuracy and at least 44.5× energy consumption reduction compared with the traditional designs.

Recently, much attention has been paid to approximate computing, a novel design paradigm for error-tolerant applications. It can significantly reduce area, power, and delay of circuits by introducing an acceptable amount of error. In this paper, we propose a new heuristic method for two-level approximate logic synthesis. The problem is to identify an approximate sum-of-product (SOP) expression under a given error rate (ER) constraint so that it has the fewest literals. The basic idea of our method is to find an optimal set of input combinations for 0-to-1 output complement (SICC). For this purpose, we first identify all prime SICCs, which are fundamental SICCs in the sense that the optimal SICC is very likely to be a union of a subset of the prime SICCs. Then, we search among all subsets of the prime SICCs the optimal subset, which leads to a final good approximate SOP. We further propose four speed-up techniques. The experiments on benchmarks showed that our method is better than the previous state-of-the-art method and our speed-up techniques are effective. For an ER threshold of 0.8%, our method can reduce 15.8% literals on average.

Approximate computing is an emerging design paradigm targeting at error-tolerant applications. It trades off accuracy for improvement in hardware cost and energy efficiency. In this paper, we propose ALFANS, a novel multilevel approximate logic synthesis framework by approximate node simplification. ALFANS works on the Boolean network representation of circuits. Its basic operation is to perform approximate simplification to nodes in a Boolean network. Based on this framework, we propose three different algorithms for three different types of error constraints. The first algorithm, ALFANSER, handles error rate (ER) constraint only. The second one, ALFANS-ER-MEM, handles a combination of ER and maximum error magnitude (EM) constraint. The third one, ALFANS-ERAEM, handles a combination of ER and average EM constraint. All these three algorithms repeatedly pick the single most effective node to simplify in each iteration. When only the ER is constrained, we also propose an accelerated version, ALFANSER-Fast, which formulates a knapsack problem to pick multiple nodes for simplification simultaneously in each iteration. It significantly improves the runtime over ALFANS-ER with almost the same circuit area. Compared to the respective state-of-the-art approaches handling the same type of error constraint, ALFANSER-Fast and ALFANS-ER-MEM reduce circuit area by 1.3% and 19.5%, respectively. A salient feature of ALFANS-ER-Fast is its run-time efficiency: it has a speedup of 5.9× over the state-of-the-art method.

Adders are key building blocks of many error-tolerant applications. Recently, a number of approximate adders were proposed. Many of them are block-based approximate adders. For approximate circuits, besides normal metrics such as area and delay, the other important design metrics are the various error statistics, such as error rate (ER), mean error distance (MED), and mean square error (MSE). Given the popularity of block-based approximate adders, in this work, we propose an efficient method to obtain their error statistics. We first show how to calculate the ER. Then, we demonstrate an approach to get the error distribution, which can be used to calculate other metrics, such as MED and MSE. Our method is applicable to an arbitrary block-based approximate adder. It is accurate for the uniformly distributed inputs. Experimental results also demonstrated that it produces error metrics close to the accurate ones for various types of non-uniform input distributions. Compared to the state-of-the-art algorithm for obtaining the error distributions of block-based approximate adders, for the uniform input distribution, our method improves the runtime by up to$4.8\times 10^4$times with the same accuracy; for non-uniform input distributions, it achieves a speed-up of up to 400 times with very similar accuracy.

Stochastic computing (SC) is an unconventional computing technique using digital circuits. It performs arithmetic computation on stochastic bit streams (SBSs), which encode real values through the ratios of ones in the streams. Despite its advantages such as simple arithmetic units and strong error tolerance, SC faces two big challenges: 1) long computation latency and 2) large hardware overhead to generate independent SBSs. A recent work proposes to insert D flip-flops (DFFs) into the stochastic circuit to reduce the overhead to generate SBSs. In this paper, observing that DFFs can also be exploited to reduce circuit delay, we propose a novel method to insert DFFs into a stochastic circuit to simultaneously reduce the computation latency of the circuit and the overhead of generating SBSs, thus addressing both challenges at the same time. Experimental results showed that compared to the state-of-the-art method in optimizing stochastic circuits with DFF insertion, our method can reduce the computation latency by 14.3% and the number of DFFs by 48.1%.

Approximate computing is an emerging energy-efficient paradigm for error-resilient applications. Approximate logic synthesis (ALS) is an important field of it. To improve the existing ALS flows, one key issue is to derive a more accurate and efficient batch error estimation technique for all approximate transformations under consideration. In this work, we propose a novel batch error estimation method based on Monte Carlo simulation and local change propagation. It is generally applicable to any statistical error measurement such as error rate and average error magnitude. We applied the technique to an existing state-of-the-art ALS approach and demonstrated its effectiveness in deriving better approximate circuits.

Polar code is increasing its popularity recently for its capacity-achieving property for B-DMCs. However, when designing decoders for polar code, it has always been an inevitable concern for us to balance the decoding performance and the hardware consumption. In this paper, we propose an approximate belief propagation (BP) decoder for polar code for the first time. By introducing the approximate computation schemes, we reduced the critical path delay (CPD) and the hardware consumption of the conventional BP decoders. Simulation results show that the proposed approximate BP decoder achieves nearly the same decoding performance as the conventional one. Advantages of the proposed decoder has been verified by FPGA implementation.

Approximate computing is an emerging paradigm for error-tolerant applications. By introducing a reasonable amount of inaccuracy, both the area and delay of a circuit can be reduced significantly. To synthesize approximate circuits automatically, many approximate logic synthesis (ALS) algorithms have been proposed. However, they mainly focus on area reduction and are not optimal in reducing the delay of the circuits. In this paper, we propose DALS, a delay-driven ALS framework. DALS works on the AND-inverter graph (AIG) representation of a circuit. It supports a wide range of approximate local changes and some commonly-used error metrics, including error rate and mean error distance. In order to select an optimal set of nodes in the AIG to apply approximate local changes, DALS establishes a critical error network (CEN) from the AIG and formulates a maximum flow problem on the CEN. Our experimental results on a wide range of benchmarks show that DALS produces approximate circuits with significantly reduced delays.

The RAID-6 configuration is more tolerant of disk failures than other RAID levels because of its ability to tolerate two disk failures. However, previous RAID-6 codes suffer from two major overheads - the time of encoding or decoding processes plus the need to access multiple blocks when updating parities or recovering failed blocks. For example, the PS and Reed-Solomon codes do not have optimal computation complexity, while P-code, X-code and RDP-code must access multiple blocks to update parities during write operations. This work proposes a new XOR- based RAID-6 code, called Tier-code, which not only achieves the optimal parity computation complexity, but also increases the write and degraded-mode read performance compared to previous codes. It uses two tiers of coding, one at the block level and the other at the chunk level. Experimental results of software testing, simulation and ASIC synthesis for this new hierarchical code demonstrate that Tier-code can outperform the previous RAID-6 codes in both write performance and degraded-mode read performance while maintaining the optimal computation complexity in both hardware and software implementations.

Stochastic computing (SC) is an unconventional method of computation that treats data as probabilities. Typically, each bit of an N-bit stochastic number (SN) Xis randomly chosen to be 1 with some probability pX, and X is generated and processed by conventional logic circuits. For instance, a single AND gate performs multiplication. The value X of an SN is measured by the density of 1 s in it, an information-coding scheme also found in biological neural systems. SC has uses in massively parallel systems and is very tolerant of soft errors. Its drawbacks include low accuracy, slow processing, and complex design needs. Its ability to efficiently perform tasks like communication decoding and neural network inference has rekindled interest in the field. Many challenges remain to be overcome, however, before SC becomes widespread. In this paper, we discuss the evolution of SC, mostly focusing on recent developments. We highlight the main challenges and discuss potential methods of overcoming them.

Stochastic computing (SC) is an unconventional computation paradigm, in which digital circuits are adopted to compute on stochastic bit streams. The value represented by a stochastic bit stream is the probability of obtaining a one in the stream. Stochastic circuits are highly tolerant to bit flip errors. Compared to the conventional binary computing, SC can perform complicated arithmetic computations with simple circuits. With such advantages, SC has been applied in a number of applications. This raises recent interests in developing general methods to automatically synthesize stochastic circuits. However, the synthesis problem is different from and more complicated than the traditional logic synthesis, due to the special solution space of the problem. In this paper, we propose a novel method to synthesize a high-quality stochastic circuit. Our method is based on assigning cubes (i.e., product terms) to the on-set of the Boolean function. A heuristic breadth-first search algorithm is proposed to search for a good stochastic circuit in the solution space. Our experimental results showed that the proposed method can produce better circuits than the state-of-the-art methods.

Smoking is the major cause of lung cancer and the leading cause of cancer-related death in the world. The most current view about lung cancer is no longer limited to individual genes being mutated by any carcinogenic insults from smoking. Instead, tumorigenesis is a phenotype conferred by many systematic and global alterations, leading to extensive heterogeneity and variation for both the genotypes and phenotypes of individual cancer cells. Thus, strategically it is foremost important to develop a methodology to capture any consistent and global alterations presumably shared by most of the cancerous cells for a given population. This is particularly true that almost all of the data collected from solid cancers (including lung cancers) are usually distant apart over a large span of temporal or even spatial contexts. Here, we report a multiple non-Gaussian graphical model to reconstruct the gene interaction network using two previously published gene expression datasets. Our graphical model aims to selectively detect gross structural changes at the level of gene interaction networks. Our methodology is extensively validated, demonstrating good robustness, as well as the selectivity and specificity expected based on our biological insights. In summary, gene regulatory networks are still relatively stable during presumably the early stage of neoplastic transformation. But drastic structural differences can be found between lung cancer and its normal control, including the gain of functional modules for cellular proliferations such as EGFR and PDGFRA, as well as the lost of the important IL6 module, supporting their roles as potential drug targets. Interestingly, our method can also detect early modular changes, with the ALDH3A1 and its associated interactions being strongly implicated as a potential early marker, whose activations appear to alter LCN2 module as well as its interactions with the important TP53-MDM2 circuitry. Our strategy using the graphical model to reconstruct gene interaction work with biologically-inspired constraints exemplifies the importance and beauty of biology in developing any bio-computational approach.

As the conventional silicon-based CMOS technology marches toward the sub-10nm region, the problem of high power density becomes increasingly serious. Under this circumstance, the carbon-nanotube field effect transistors (CNFETs) emerge as a promising alternative to the conventional silicon-based CMOS devices. However, they experience a much larger variation than the silicon-based CMOS devices, which results in a large circuit delay variation and hence, a significant timing yield loss. One of the main variation sources is the carbon-nanotube (CNT) density variation. However, it shows a special property not existing for silicon-based CMOS devices, namely the asymmetric spatial correlation. In this work, we propose novel global placement algorithms to reduce the timing yield loss caused by the CNT density variation. To effectively reduce the statistical circuit delay, we first develop a statistical delay measure for a segment of gates. Based on this measure, we further develop a segment-based strategy and a path-based placement strategy to reduce the delays of the statistically critical paths. Experimental results demonstrated that both of our approaches effectively improve the timing yield.

Approximate computing is a new design paradigm targeting at error-tolerant applications. By allowing a little amount of inaccuracy in the computation, it could significantly reduce circuit area and power consumption. Several logic synthesis methods for approximate computing were proposed recently. However, these methods are mainly aimed at ASIC designs. In this work, we propose a novel approximate logic synthesis method targeting at the FPGA design. We exploit the flexibility of lookup tables and propose a method that combines wire removal and local function change. The experimental results showed that our method produces better results than the state-of-the-art approximate logic synthesis method adapted to FPGA designs. Moreover, it can be combined with the state-of-the-art method to further improve the design quality.

Stochastic computing (SC) is an unconventional computing paradigm that operates on stochastic bit streams. It has gained attention recently because of the very low area and power needs of its computing core. SC relies on stochastic number generators (SNGs) to map input binary numbers to stochastic bit streams. A conventional SNG comprises a random number source (RNS), typically an LFSR, and a comparator. It needs far more area and power than the SC core, offsetting the latter's main advantages. To mitigate this problem, SNGs employing emerging nanoscale devices such as memristors and spintronic devices have been proposed. However, these devices tend to have large errors in their output probabilities due to unpredictable variations in their fabrication processes and noise in their control signals. We present a novel method of exploiting such devices to design a highly accurate SNG. It is built around an RNS that generates uniformly distributed random numbers under ideal (nominal) conditions. It also has a novel error-cancelling probability conversion circuit (ECPCC) that guarantees very high accuracy in the output probability under realistic conditions when the RNS is subject to errors. An ECPCC can also be used to generate maximally correlated stochastic streams, a useful property for some applications.

Approximate computing is an emerging design paradigm targeting at error-tolerant applications. The area, delay, and power consumption of a circuit can be improved by sacrificing a reasonable amount of accuracy. Approximate logic synthesis (ALS) aims at automatically synthesizing an approximate circuit for a given target circuit. In this paper, we propose to approximate a target function by a maximally disjoint bi-decomposable function, which can significantly reduce the implementation cost. We propose novel techniques to effectively generate such an approximation with low error rate. We further integrate this approximation technique into a systematic ALS flow. Experiment results show the effectiveness of our proposed ALS flow in producing approximate circuits with reduced areas.

Computations based on stochastic bit streams have several advantages compared to deterministic binary radix computations, including low power consumption, low hardware cost, high fault tolerance, and skew tolerance. To take advantage of this computing technique, previous work proposed a combinational logic-based reconfigurable architecture to perform complex arithmetic operations on stochastic streams of bits. The long execution time and the cost of converting between binary and stochastic representations, however, make the stochastic architectures less energy efficient than the deterministic binary implementations. This article introduces a methodology for synthesizing a given target function stochastically using finite-state machines (FSMs), and enhances and extends the reconfigurable architecture using sequential logic. Compared to the previous approach, the proposed reconfigurable architecture can save hardware area and energy consumption by up to 30% and 40%, respectively, while achieving a higher processing speed. Both stochastic reconfigurable architectures are much more tolerant of soft errors (bit flips) than the deterministic binary radix implementations, and their fault tolerance scales gracefully to very large numbers of errors.

Approximate computing is an emerging design paradigm targeting at error-tolerant applications. It trades off accuracy for improvement in hardware cost and energy efficiency. In this paper, we propose a novel approach for multi-level approximate logic synthesis under error rate constraint. The basic idea of our approach is to pick nodes in a Boolean network and shrink them by approximating their factored-form expressions. We propose two different algorithms to implement the basic idea. The first algorithm iteratively picks the most effective node at present to shrink. Its drawback lies in that it may need a large number of iterations. To overcome this drawback, the second algorithm formulates a knapsack problem to pick multiple nodes for shrinking simultaneously. It is still iterative, but the number of iterations is greatly reduced. We apply the two algorithms to MCNC benchmarks and arithmetic circuits including adders and multipliers. The experimental results demonstrated that our algorithms perform better in area saving and are 1.7 and 5.9 times faster, respectively, compared with the state-of-the-art approach.

The traditional FPGA technology mapping flow is very time-consuming as modern FPGA designs become larger. To speed up this procedure, this paper proposes a new approach based on circuit partition to parallelize it. The idea is to split the original circuit into several sub-circuits and assign each one to a core of a multi-core processor for simultaneous technology mapping. Compared to other existing parallelization methods, our method has the benefit of being independent of the detailed mapping algorithm. Our proposed partition method is able to minimize the quality loss caused by the partitioning. We have successfully integrated the proposed approach into an industrial FPGA mapping platform. The proposed flow gains a speed-up of 1.6X on average on a quad-core processor with negligible influence on the LUT count and the critical path length.

Approximate computing is an emerging design technique for error-tolerant applications. As adders are the key building blocks in many applications, approximate adders have been widely studied recently. However, existing approximate adders may introduce sign bit error when doing two's complement signed addition, which is not tolerable for some applications. In this work, we propose a scheme that can correct sign bit error with low area and delay overhead. It is a general design applicable to many block-based approximate adders. This design not only can correct the sign bit error when it occurs, but also can fix some errors in the most significant bits even if there is no sign bit error. Experimental results on a real application, namely edge detection, showed that the approximate adders with our sign bit error correction module were up to 5.5 times better in peak signal-to-noise ratio than the original approximate adders, while the area and delay overhead is small.

Stochastic computation is a non-conventional computation paradigm, which uses digital circuits to operate on stochastic bit streams. Although it has advantages such as strong fault tolerance and low hardware cost, its drawback is its long computation time. In this work, we target at stochastic computation used in binary classification applications, such as image segmentation and pattern classification, and propose a novel accelerating module. We study how the design parameters affect the error rate and computation time. We further propose how to find the optimal design parameters. A case study on an image segmentation algorithm shows the effectiveness of our proposed solution.

The wide application of omics research has produced a burst of biological data in recent years, which has in turn increased the need to infer biological networks from data. Learning biological networks from experimental data can help detect and analyze aberrant signaling pathways, which can be used in diagnosis of diseases at an early stage. Most networks can be modeled as Bayesian networks (BNs). However, because of its combinatorial nature, computational learning of dependent relationships underlying complex networks is NP-complete. To reduce the complexity, researchers have proposed to use Markov chain Monte Carlo (MCMC) methods to sample the solution space. MCMC methods guarantee convergence and traversability. However, MCMC is not scalable for networks with more than 40 nodes because of the computational complexity. In this work, we optimize an MCMC-based learning algorithm and implement it on a general-purpose graphics processing unit (GPGPU). We achieve a 2.46× speedup by optimizing the algorithm and an additional 58-fold acceleration by implementing it on a GPU. In total, we speed up the algorithm by 143×. As a result, we can apply this system to networks with up to 125 nodes, a size that is of interest to many biologists. Furthermore, we add artificial interventions to the scores in order to incorporate prior knowledge of interactions into the Bayesian inference, which increases the accuracy of the results. Our system provides biologists with a more computational efficient tool at a lower cost than previous works.

Stochastic computation is an unconventional computational paradigm that uses ordinary digital circuits to operate on stochastic bit streams, where signal value is encoded as the probability of ones in a stream. It is highly tolerant of soft errors and enables complex arithmetic operations to be implemented with simple circuitry. Prior research has proposed a method to synthesize stochastic computing circuits to implement arbitrary arithmetic functions by approximating them via Bernstein polynomials. However, for some functions, the method cannot find Bernstein polynomials that approximate them closely enough, thus causing a large computation error.

Stochastic computing is a paradigm that performs computation on stochastic bit streams using conventional digital circuits. A general design for stochastic computing is a MUX-based architecture, which needs multiple constant probabilities as inputs. Previous approaches generate these probabilities by separate combinational circuits. The resulting designs are not area-efficient. In this work, we use the fact that these constant probabilities to the MUX can have correlation and propose two novel algorithms that produce low-cost circuits for generating these probabilities. Experimental results showed that our method greatly reduces the cost of generating constant probabilities for the MUX-based stochastic computing architecture.

Single-electron transistor (SET) is an ultra-low power device, which has been demonstrated as a promising alternative for CMOS devices in reducing power consumption. A suitable structure for realizing logic function using SET is a binary decision diagram (BDD)-based SET array. Previous works proposed product term-based automated synthesis methods to map a given logic function onto an SET array. In this work, we propose a novel BDD-based synthesis method that exploits the structure similarity between an SET array and a BDD. Our method transforms a BDD of a Boolean function into a planar graph and further maps the graph onto an SET array. Experiment results showed that compared to the state-of-the-art synthesis method, our method saves 51% in area on average and is more than 16 times faster.

Most digital systems operate on a positional representation of data, such as binary radix. An alternative is to operate on random bit streams where the signal value is encoded by the probability of obtaining a one versus a zero. This representation is much less compact than binary radix. However, complex operations can be performed with very simple logic. Furthermore, since the representation is uniform, with all bits weighted equally, it is highly tolerant of soft errors (i.e., bit flips). Both combinational and sequential constructs have been proposed for operating on stochastic bit streams. Prior work has shown that combinational logic can implement multiplication and scaled addition effectively while linear finite-state machines (FSMs) can implement complex functions such as exponentiation and tanh effectively. Prior work on stochastic computation has largely been validated empirically.This paper provides a rigorous mathematical treatment of stochastic implementation of complex functions such as exponentiation and tanh implemented using linear FSMs. It presents two new functions, an absolute value function and exponentiation based on an absolute value, motivated by specific applications. Experimental results show that the linear FSM-based constructs for these functions have smaller area-delay products than the corresponding deterministic constructs. They also are much more tolerant of soft errors.

Maintaining the reliability of integrated circuits as transistor sizes continue to shrink to nanoscale dimensions is a significant looming challenge for the industry. Computation on stochastic bit streams, which could replace conventional deterministic computation based on a binary radix, allows similar computation to be performed more reliably and often with less hardware area. Prior work discussed a variety of specific stochastic computational elements (SCEs) for applications such as artificial neural networks and control systems. Recently, very promising new SCEs have been developed based on finite-state machines (FSMs). In this paper, we introduce new SCEs based on FSMs for the task of digital image processing. We present five digital image processing algorithms as case studies of practical applications of the technique. We compare the error tolerance, hardware area, and latency of stochastic implementations to those of conventional deterministic implementations using binary radix encoding. We also provide a rigorous analysis of a particular function, namely the stochastic linear gain function, which had only been validated experimentally in prior work.

Random bits are an important construct in many applications, such as hardware-based implementation of probabilistic algorithms and weighted random testing. One approach in generating random bits with required probabilities is to synthesize combinational circuits that transform a set of source probabilities into target probabilities. In [1], the authors proposed a greedy algorithm that synthesizes circuits in the form of a gate chain to approximate target probabilities. However, since this approach only considers circuits of such a special form, the resulting circuits are not satisfactory both in terms of the approximation error and the circuit depth. In this paper, we propose a new algorithm to synthesize combinational circuits for generating random bits. Compared to the previous one, our approach greatly enlarges the search space. Also, we apply a linear property of probabilistic logic computation and an iterative local search method to increase the efficiency of our algorithm. Experimental results comparing the approximation errors and the depths of the circuits synthesized by our method to those of the circuits synthesized by the previous approach demonstrate the superiority of our method.

Digital computation on stochastic bit streams is a non-conventional type of computation, which uses digital circuits to process probabilistic inputs. In this paradigm, digital circuits compute on the probability values. This leads to extremely simple digital implementations for complex arithmetic operations. The combinational logic-based designs can be implemented in parallel to realize fast computation by trading off silicon area with delay. However, it is impossible to implement the current sequential logic-based designs in parallel to reduce delay, since they need to compute for a large number of clock cycles to obtain the result. In this work, we propose a novel design methodology for synthesizing sequential circuits that compute on stochastic bit streams, which does not require a long computation delay. We further demonstrate a parallel implementation based on our design, which provides ultra-fast arithmetic computation.

The Stochastic Computational Element (SCE) uses streams of random bits (stochastic bits streams) to perform computation with conventional digital logic gates. It can guarantee reliable computation using unreliable devices. In stochastic computing, the linear Finite State Machine (FSM) can be used to implement some sophisticated functions, such as the exponentiation and tanh functions, more efficiently than combinational logic. However, a general approach about how to synthesize a linear FSM-based SCE for a target function has not been available. In this paper, we will introduce three properties of the linear FSM used in stochastic computing and demonstrate a general approach to synthesize a linear FSM-based SCE for a target function. Experimental results show that our approach produces circuits that are much more tolerant of soft errors than deterministic implementations, while the area-delay product of the circuits are less than that of deterministic implementations.

The paradigm of logical computation on stochastic bit streams has several key advantages compared to deterministic computation based on binary radix, including error-tolerance and low hardware area cost. Prior research has shown that sequential logic operating on stochastic bit streams can compute non-polynomial functions, such as the tanh function, with less energy than conventional implementations. However, the functions that can be computed in this way are quite limited. For example, high order polynomials and non-polynomial functions cannot be computed using prior approaches. This paper proposes a new finite-state machine (FSM) topology for complex arithmetic computation on stochastic bit streams. It describes a general methodology for synthesizing such FSMs. Experimental results show that these FSM-based implementations are more tolerant of soft errors and less costly in terms of the area-time product that conventional implementations.

Numerical integration is a widely used approach for computing an approximate result of a definite integral. Conventional digital implementations of numerical integration using binary radix encoding are costly in terms of hardware and have long computational delay. This work proposes a novel method for performing numerical integration based on the paradigm of logical computation on stochastic bit streams. In this paradigm, ordinary digital circuits are employed but they operate on stochastic bit streams instead of deterministic values; the signal value is encoded by the probability of obtaining a one versus a zero in the streams. With this type of computation, complex arithmetic operations can be implemented with very simple circuitry. However, typically, such stochastic implementations have long computational delay, since long bit streams are required to encode precise values. This paper proposes a stochastic design for numerical integration characterized by both small area and short delay -- so, in contrast to previous applications, a win on both metrics. The design is based on mathematical analysis that demonstrates that the summation of a large number of terms in the numerical integration could lead to a significant delay reduction. An architecture is proposed for this task. Experiments confirm that the stochastic implementation has smaller area and shorter delay than conventional implementations.

Computation performed on stochastic bit streams is less efficient than that based on a binary radix because of its long latency. However, for certain complex arithmetic operations, computation on stochastic bit streams can consume less energy and tolerate more soft errors. In addition, the latency issue could be solved by using a faster clock frequency or in combination with a parallel processing approach. To take advantage of this computing technique, previous work proposed a combinational logic-based reconfigurable architecture to perform complex arithmetic operations on stochastic streams of bits. In this paper, we enhance and extend this reconfigurable architecture using sequential logic. Compared to the previous approach, the proposed reconfigurable architecture takes less hardware area and consumes less energy, while achieving the same performance in terms of processing time and fault-tolerance.

Mounting concerns over variability, defects, and noise motivate a new approach for digital circuitry: stochastic logic, that is to say, logic that operates on probabilistic signals and so can cope with errors and uncertainty. Techniques for probabilistic analysis of circuits and systems are well established. We advocate a strategy for synthesis. In prior work, we described a methodology for synthesizing stochastic logic, that is to say logic that operates on probabilistic bit streams. In this paper, we apply the concept of stochastic logic to a reconfigurable architecture that implements processing operations on a datapath. We analyze cost as well as the sources of error: approximation, quantization, and random fluctuations. We study the effectiveness of the architecture on a collection of benchmarks for image processing. The stochastic architecture requires less area than conventional hardware implementations. Moreover, it is much more tolerant of soft errors (bit flips) than these deterministic implementations. This fault tolerance scales gracefully to very large numbers of errors.

Schemes for probabilistic computation can exploit physical sources to generate random values in the form of bit streams. Generally, each source has a fixed bias and so provides bits with a specific probability of being one. If many different probability values are required, it can be expensive to generate all of these directly from physical sources. This paper demonstrates novel techniques for synthesizing combinational logic that transforms source probabilities into different target probabilities. We consider three scenarios in terms of whether the source probabilities are specified and whether they can be duplicated. In the case that the source probabilities are not specified and can be duplicated, we provide a specific choice, the set {0.4, 0.5} ; we show how to synthesize logic that transforms probabilities from this set into arbitrary decimal probabilities. Further, we show that for any integern≥ 2, there exists a single probability that can be transformed into arbitrary base-nfractional probabilities. In the case that the source probabilities are specified and cannot be duplicated, we provide two methods for synthesizing logic to transform them into target probabilities. In the case that the source probabilities are not specified, but once chosen cannot be duplicated, we provide an optimal choice.

Mounting concerns over variability, defects and noise motivate a new approach for integrated circuits: the design of stochastic logic, that is to say, digital circuitry that operates on probabilistic signals, and so can cope with errors and uncertainty. Techniques for probabilistic analysis are well established. We advocate a strategy for synthesis. In this paper, we present a reconfigurable architecture that implements the computation of arbitrary continuous functions with stochastic logic. We analyze the sources of error: approximation, quantization, and random fluctuations. We demonstrate the effectiveness of our method on a collection of benchmarks for image processing. Synthesis trials show that our stochastic architecture requires less area than conventional hardware implementations. It achieves a large speed up compared to software conventional implementations. Most importantly, it is much more tolerant of soft errors (bit flips) than these deterministic implementations.

As CMOS devices are scaled down into the nanometer regime, concerns about reliability are mounting. Instead of viewing nano-scale characteristics as an impediment, technologies such as PCMOS exploit them as a source of randomness. The technology generates random numbers that are used in probabilistic algorithms. With the PCMOS approach, different voltage levels are used to generate different probability values. If many different probability values are required, this approach becomes prohibitively expensive.

As integrated circuit technology plumbs ever greater depths in the scaling of feature sizes, maintaining the paradigm of deterministic Boolean computation is increasingly challenging. Indeed, mounting concerns over noise and uncertainty in signal values motivate a new approach: the design of stochastic logic, that is to say, digital circuitry that processes signals probabilistically, and so can cope with errors and uncertainty. In this paper, we present a general methodology for synthesizing stochastic logic for the computation of polynomial arithmetic functions, a category that is important for applications such as digital signal processing. The method is based on converting polynomials into a particular mathematical form --- Bernstein polynomials --- and then implementing the computation with stochastic logic. The resulting logic processes serial or parallel streams that are random at the bit level. In the aggregate, the computation becomes accurate, since the results depend only on the precision of the statistics. Experiments show that our method produces circuits that are highly tolerant of errors in the input stream, while the area-delay product of the circuit is comparable to that of deterministic implementations.