Search

Topological quantum error correction (TQEC) is promising for scalable fault-tolerant quantum computation. The required resource of a TQEC circuit can be modeled as its space-time volume of a three-dimensional geometric description. Implementing a quantum algorithm with a reasonable physical qubit number and computation time is challenging for large-scale complex problems. Therefore, it is desirable to minimize the space-time volume for large-scale TQEC circuits. Previous work proposed bridge compression, which can significantly compress a TQEC circuit, but it was performed manually. This article presents the first automated tool that can perform bridge compression on a large-scale TQEC circuit. Our proposed algorithm applies the bridge compression technique to compactify TQEC circuits with modularization. Besides, we offer a time-ordering-aware 2.5-D placement for compacting TQEC circuits and satisfying time-ordered measurement constraints. On the other hand, we suggest friend net-aware routing to effectively reduce the required routing resource under topological deformation. Compared with the state-of-the-art work, experimental results show that our proposed algorithm can averagely reduce space-time volumes by 84%. [ABSTRACT FROM AUTHOR]

With the emergence of the multicore architecture and the increase of chip operating frequency, power optimization has become a key step of circuit logic synthesis. Aiming at the XNOR/OR circuits, with the goal of minimizing power, construct the optimal polarity fixed-polarity Reed–Muller (FPRM) circuits power optimization scheme. However, the power optimization for FPRM circuits is a multipeak combinatorial optimization problem, we first propose a metaheuristic optimization algorithm (MOA), which includes the global exploration optimizer, local deep exploitation optimizer, and initial population and uses the proposed differential evolution optimization, fierce wolf siege algorithm-based tabu search, and improved skew tent map to make the population evolve. Based on the proposed Huffman tree construction algorithm and MOA, we propose an efficient power optimization approach (EPOA) to find the minimum power FPRM circuit. Experimental results on the benchmark circuits confirm the effectiveness of EPOA. [ABSTRACT FROM AUTHOR]

In digital circuit designs, sequential components such as flip-flops are used to synchronize signal propagations. Logic computations are aligned at and thus isolated by flip-flop stages. Although this fully synchronous style can reduce design efforts significantly, it may affect circuit performance negatively, because sequential components can only introduce delays into signal propagations but never accelerate them. In this article, we propose a new timing model, VirtualSync+, in which signals, specially those along critical paths, are allowed to propagate through several sequential stages without flip-flops. Timing constraints are still satisfied at the boundary of the optimized circuit to maintain a consistent interface with existing designs. By removing clock-to-q delays and setup time requirements of flip-flops on critical paths, the performance of a circuit can be pushed even beyond the limit of traditional sequential designs. In addition, we further enhance the optimization with VirtualSync+ by fine-tuning with commercial design tools, e.g., design compiler from Synopsys, to achieve more accurate result. To achieve this fine-tuning, we first optimize the circuits by reallocating sequential components with sequential and combinational components as delay units. Afterward, the removal locations of flip-flops with respect to the circuits under optimization are extracted and the corresponding wave-pipelining timing constraints compatible with commercial design tools are established. These timing constraints are then incorporated into the optimization flow of commercial tools to generate the optimized circuits. The experimental results demonstrate that circuit performance can be improved by up to 4% (average 1.5%) compared with that after extreme retiming and sizing, while the increase of area is still negligible. This timing performance is enhanced beyond the limit of traditional sequential designs. It also demonstrates that compared with those after retiming and sizing, the circuits with VirtualSync+ can achieve better timing performance under the same area cost or smaller area cost under the same clock period, respectively. [ABSTRACT FROM AUTHOR]

This article proposes a new logic synthesis and verification paradigm based on circuit simulation. In this paradigm, high quality, expressive simulation patterns are pregenerated to be reused in multiple runs of optimization and verification algorithms, resulting in reduced time-consuming Boolean computations such as satisfiability (SAT) solving. Methods to generate expressive simulation patterns are presented and compared, and a bit-packing technique to compress them is integrated into the implementation. The generated patterns are shown to be reusable across different algorithms and after network function modifications. A logic synthesis algorithm, Boolean resubstitution, and a verification algorithm, combinational equivalence checking, are two examples of using this paradigm. In simulation-guided Boolean resubstitution, simulation patterns are used for efficient filtering of optimization choices, leading to a lower cost in expanding the search space. By adopting the proposed paradigm, we achieve a 5.9% reduction in the number of AIG nodes, compared to 3.7% by a state-of-the-art resubstitution algorithm, within comparable runtime. In simulation-guided equivalence checking, the number of SAT solver calls is reduced by 9.5% with the use of the expressive simulation patterns accumulated in earlier logic synthesis stages. [ABSTRACT FROM AUTHOR]

Deep neural networks have achieved remarkable advancement in various intelligence tasks. However, the massive computation and storage consumption limit applications on resource-constrained devices. While channel pruning has been widely applied to compress models, it is challenging to reach very deep compressions for such a coarse-grained pruning structure without significant performance degradation. In this article, we propose an acceleration-aware fine-grained channel pruning (AFCP) framework for accelerating neural networks, which optimizes trainable gate parameters by estimating residual errors between pruned and original channels with hardware characteristics. Our fine-grained concept consists of both algorithm and structure levels. Different from existing methods that leverage a predefined pruning criterion, AFCP explicitly considers both zero-out and similar criteria for each channel, and adaptively selects the suitable one via residual gate parameters. For structure level, AFCP adopts a fine-grained channel pruning strategy for residual neural networks and a decomposition-based structure, which further extends the pruning optimization space. Moreover, instead of using theoretical computation costs, such as floating-point operations, we propose the hardware predictor that bridges the gap between realistic acceleration and pruning procedure to guide the learning of pruning, which improves the efficiency of model pruning when deployed on accelerators. Extensive evaluation results demonstrate that AFCP outperforms state-of-the-art methods, and achieves a favorable balance between model performance and computation cost. [ABSTRACT FROM AUTHOR]

Threshold logic has been attracting great attention from researchers due to the rapid development in nanotechnology-based devices. In the state-of-the-art approach to the threshold logic network (TLN) synthesis using don’t cares, we observed that not all the computed don’t cares contribute to the cost minimization of threshold logic gate (TLG). Therefore, in this work, we focus on computing the don’t cares that effectively provide the opportunities for cost minimization. Furthermore, De Morgan’s law for TLGs is applied such that global TLN optimization considering the cost and the number of inverters can be achieved. The experimental results show that the proposed approach is capable of obtaining efficiently a smaller cost and fewer inverters for a set of TLN benchmarks. [ABSTRACT FROM AUTHOR]

Quantum-dot cellular automata (QCA) is considered as a promising emerging technology due to its low power dissipation and high device density. Since the majority function is the main operation in QCA circuits, minimizing the number of majority gates in QCA circuits is crucial to the corresponding QCA circuit minimization. A previous work used the node-merging technique to replace one target node with an existing substitute node in majority circuits for optimization. However, this technique may fail when no substitute nodes exist for a target node. In this article, we propose an enhanced optimization technique for majority circuits by adding a new node into the circuits and removing the target node and its fanin nodes. The experimental results show that this technique improves the results of the node-merging technique on a set of EPFL logic synthesis benchmarks. Additionally, this enhanced technique can work together with other optimization techniques. The circuit size reduction in the integrated approach reaches 1.26 times as compared to the results using the node-merging technique. [ABSTRACT FROM AUTHOR]

Homomorphic encryption (HE) has broad application prospects in the cloud computing security field. Efficient homomorphic computations of primitive circuits are critical for the applications of HE. However, existing implementation methods over plaintext do not fit well with those over ciphertext. To address this issue, a concise evaluation model is proposed to compare different implementation methods, using weighted computational complexity (WCC). The number, depth, and distribution of homomorphic multiplications are considered together in the model for the first time. In addition, two primitive binary circuits on homomorphically encrypted data are optimized by using a unit called dot multiplication (DotMC). A novel comparison circuit based on DotMC is presented, and the number of homomorphic multiplications is reduced from ${O}(n {\mathrm{ log}} ~n)$ to ${O}({n})$ without increasing the multiplicative depth compared with the logarithm comparison, where ${n}$ is the bit length of the operand. The WCC of comparison is reduced from ${O}(n({\mathrm{ log}}~n)^{2})$ to ${O}({n}({\mathrm{ log}} ~{n}))$. The carry-lookahead adder is optimized by moving some DotMCs to levels with smaller weight, which reflects the effect of the distribution of homomorphic multiplications on performance. Finally, the proposed DotMC is accelerated with a single-instruction-multiple-data approach for even one operation; the number of homomorphic multiplication is reduced from ${O}({n})$ to ${O}({\mathrm{ log}}~n)$ compared with other comparison with the same strategy. Various circuits with the size from 4 to 2048 b are implemented with HElib to prove the optimization for comparison and addition, as well as the effectiveness of the proposed model. [ABSTRACT FROM AUTHOR]

Since the first release in 2015, OpenTimer v1 has been used in many industrial and academic projects for analyzing the timing of custom designs. After four-year research and developments, we have announced OpenTimer v2—a major release that efficiently supports: 1) a new task-based parallel incremental timing analysis engine to break through the performance bottleneck of existing loop-based methods; 2) a new application programming interface (API) concept to exploit high degrees of parallelisms; and 3) an enhanced support for industry-standard design formats to improve user experience. Compared with OpenTimer v1, we rearchitect v2 with a modern C++ programming language and advanced parallel computing techniques to largely improve the tool performance and usability. For a particular example, OpenTimer v2 achieved up to 5.33 × speedup over v1 in incremental timing, and scaled higher with increasing cores. Our contributions include both technical innovations and engineering knowledge that are open and accessible to promote timing research in the community. [ABSTRACT FROM AUTHOR]

SAT Attack, CycSAT, and Removal Attack have demonstrated their abilities to break most existing logic locking methods. In this article, we propose a new cyclic logic locking method to invalidate these attacks simultaneously. Our main intention is to create noncombinational cycles to lock a circuit. Specifically, the noncombinational behavior in the noncombinational cycles that is unobservable at the primary outputs (POs) needs to be preserved when the correct key-vector is fed to resist CycSAT, and the noncombinational behavior in the noncombinational cycles affecting POs needs to be preserved when the incorrect key-vector is fed to invalidate SAT Attack. Furthermore, some nodes will be removed when applying our locking method, which is able to defend Removal Attack. The experimental results show the effectiveness and low area overhead of the proposed method. [ABSTRACT FROM AUTHOR]

Timing-driven placement optimization is applied incrementally in various parts of the flow, together with other timing optimization techniques, to achieve timing closure. In this article, we present a generalized approach for Lagrange-relaxation-based timing optimization that is used to iteratively relocate gates, flip-flops, and local clock buffers (LCBs), with the goal being to reduce the timing violations. Cells are allowed to move within an appropriately positioned search window, the location of which is decided by force-like timing vectors covering both late and early timing violations. The magnitude of these timing vectors is determined by the value of the corresponding Lagrange multipliers. The introduced placement optimization is applied in conjunction with a newly proposed flip-flop clustering algorithm that (re)assigns flip-flops to LCBs, to separate flip-flops with incompatible timing profiles and to facilitate the subsequent timing-optimization steps. The proposed approach is tested on the ICCAD-2015 benchmarks, providing the best overall results when compared to state-of-the-art timing-driven placement techniques. [ABSTRACT FROM AUTHOR]

Fully depleted silicon on insulator (FDSOI) is attractive for its low cost and low power; the mixed-Vt and body-bias levers that it affords expand the performance-power solution space. However, in FDSOI, different-Vt (i.e., low Vt and regular Vt) devices must be isolated from each other, which makes realization of fine-grained mixed-Vt/body-biasing in layout extremely challenging. In this article, we study heuristic methods aimed at exploitation of fine-grained mixed-Vt in FDSOI implementation. We propose a novel speed domain partitioning (SDP) problem formulation that comprehends the spatial contiguity restrictions arising from flip-well structure of low Vt regions in popular 28-nm commercial FDSOI offerings. We explore a wide space of implementation flows that include an integer linear programming (ILP)-based approach, and a heuristic (sensitivity-based) optimization. Our experimental studies have been performed across multiple commercial enablements. We observe that outcomes are library- and design-dependent. For implementations using generic library options, up to 20% speed improvement with 54% low Vt region is seen for one out of four testcases studied. For implementations using “rich” library options, up to 7% speed improvement with 26% low Vt region is achieved. We provide a discussion that summarizes root-cause, intrinsic difficulties of fine-grained exploitation of mixed-Vt. Finally, we suggest a “decision tree” to help assess a design’s amenability to fine-grained mixed-Vt implementation, and to help guide design flow selection for better design QoR. [ABSTRACT FROM AUTHOR]

Typical operators for the decomposition of Boolean functions in state-of-the-art algorithms are AND, exclusive-OR (XOR), and the 2-to-1 multiplexer (MUX). We propose a logic decomposition algorithm that uses the majority-of-three (MAJ) operation. Such a decomposition can extend the capabilities of current logic decompositions, but only found limited attention in the previous work. Our algorithm make use of a decomposition rule based on MAJ. Combined with disjoint-support decomposition, the algorithm can factorize XOR-majority graphs (XMGs), a recently proposed data structure which has XOR, MAJ, and inverters as only logic primitives. XMGs have been applied in various applications, including: 1) exact-synthesis-aware rewriting; 2) preoptimization for 6-input look-up table (6-LUT) mapping; and 3) synthesis of quantum circuits. An experimental evaluation shows that our algorithm leads to better XMGs compared to state-of-the-art algorithms based on XMGs, which positively affects all of these three applications. As one example, our experiments show that the proposed method achieves an average of 10% and 26% reduction on the LUTs size/depth product applied to the EPFL arithmetic and random control benchmarks after technology mapping, respectively. [ABSTRACT FROM AUTHOR]

Accurate delay analysis with distributed RC delay can be computationally expensive, and can contribute the majority of the total runtime for gate sizers. Recent works have shown that Lagrangian relaxation (LR)-based gate sizers have produced designs with the lowest power on average. But they are also very slow due to a large number of expensive timing updates spread across several tens of iterations. In this paper, we develop an LR-based discrete gate sizer for fast timing and power reduction. Our gate sizer is multithreaded and is equipped with parallelization enabling techniques, namely mutual exclusion edge (MEE) assignment and directed acyclic graph (DAG)-based netlist traversal (DNT). MEEs are dummy edges assigned to improve load sharing among different threads. DNT facilitates simultaneous resizing of gates belonging to different topological levels. Our Lagrange multiplier update strategy enables rapid convergence of our timing and power recovery algorithms. To reduce the runtime of timing updates, we propose a simple and fast-to-compute effective capacitance model. We further propose mechanisms to calibrate timing models to improve their accuracy. By calibrating the internal timing models only twice, our proposed gate sizing flow facilitates extremely fast design optimization. We benchmark our gate sizer using the ISPD 2012 and 2013 gate sizing contest benchmark suites. Compared to the state-of-the-art gate sizer, our proposed gate sizer is on average $15\times $ faster and the optimized designs have 2.5% higher leakage power. Since we tradeoff timing accuracy for larger runtime speedup, our optimized designs have small timing violations. [ABSTRACT FROM AUTHOR]

In the emerging paradigm of edge computing (EC) for Internet of Things (IoT), data processing is pushed to the edge of the IoT network (e.g., gateways and embedded IoT devices). IoT devices must support multiple operation modes in order to adapt to varying runtime situations, like preserving energy at low battery, while still maintaining some crucial functionality, etc. Adapting the optimal operation mode is a challenge for edge devices given the limited resources at the edge of the network (both bandwidth and processing power of the shared gateway), various constraints (e.g., battery lifetime), etc. This paper proposes a fast and low-overhead scheme to determine and adapt the operation mode of edge devices at runtime and orchestrate devices in a way that the efficiency of IoT devices is optimized with respect to the gateway’s resource constraints. The proposed scheme breaks the optimization problem into several smaller ones (i.e., subproblems) whose solutions are aggregated to find the final solution. We present a novel memoization technique that determines the solution to a range of subproblems based on subproblems that are already solved. In addition, we present a novel pruning technique that reduces the search space and consequently reduces both memory and execution time overhead. The experimental results show up to 50% reduction in memory overhead and $14 \times $ reduction in execution time overhead compared to the state-of-the-art solution which is a major step toward efficient EC for IoT. [ABSTRACT FROM AUTHOR]

We present a synthesis framework to map logic networks into quantum circuits for quantum computing. The synthesis framework is based on lookup-table (LUT) networks, which play a key role in conventional logic synthesis. Establishing a connection between LUTs in an LUT network and reversible single-target gates in a reversible network allows us to bridge conventional logic synthesis with logic synthesis for quantum computing, despite several fundamental differences. We call our synthesis framework LUT-based hierarchical reversible logic synthesis (LHRS). Input to LHRS is a classical logic network representing an arbitrary Boolean combinational operation; output is a quantum network (realized in terms of Clifford+T gates). The framework allows one to account for qubit count requirements imposed by the overlying quantum algorithm or target quantum computing hardware. In a fast first step, an initial network is derived that only consists of single-target gates and already completely determines the number of qubits in the final quantum network. Different methods are then used to map each single-target gate into Clifford+T gates, while aiming at optimally using available resources. We demonstrate the versatility of our method by conducting a design space exploration using different parameters on a set of large combinational benchmarks. On the same benchmarks, we show that our approach can advance over the state-of-the-art hierarchical reversible logic synthesis algorithms. [ABSTRACT FROM AUTHOR]

In the past years, quantum computers more and more have evolved from an academic idea to an upcoming reality. IBM’s project IBM ${Q}$ can be seen as evidence of this progress. Launched in March 2017 with the goal to provide access to quantum computers for a broad audience, this allowed users to conduct quantum experiments on a 5-qubit and, since June 2017, also on a 16-qubit quantum computer (called IBM QX2 and IBM QX3, respectively). Revised versions of these 5- and 16-qubit quantum computers (named IBM QX4 and IBM QX5, respectively) are available since September 2017. In order to use these, the desired quantum functionality (e.g., provided in terms of a quantum circuit) has to be properly mapped so that the underlying physical constraints are satisfied—a complex task. This demands solutions to automatically and efficiently conduct this mapping process. In this paper, we propose a methodology which addresses this problem, i.e., maps the given quantum functionality to a realization which satisfies all constraints given by the architecture and, at the same time, keeps the overhead in terms of additionally required quantum gates minimal. The proposed methodology is generic, can easily be configured for similar future architectures, and is fully integrated into IBM’s SDK. Experimental evaluations show that the proposed approach clearly outperforms IBM’s own mapping solution. In fact, for many quantum circuits, the proposed approach determines a mapping to the IBM architecture within minutes, while IBM’s solution suffers from long runtimes and runs into a timeout of 1 h in several cases. As an additional benefit, the proposed approach yields mapped circuits with smaller costs (i.e., fewer additional gates are required). All implementations of the proposed methodology are publicly available at http://iic.jku.at/eda/research/ibm_qx_mapping. [ABSTRACT FROM AUTHOR]

Intellectual property (IP) cores used in consumer electronics devices mandate protection against reverse engineering (RE) attacks. Functional obfuscation protects the design functionality by enhancing the complexity of RE attacks. This paper proposes a novel low cost (based on power-delay tradeoff) functional obfuscation methodology through employment of robust IP locking technique. In the proposed obfuscation methodology, several strong multipairwise secure IP locking block designs are presented that can only be actuated through application of valid serial key bits. As demonstration, this paper also shows a practical example of a functional obfuscated netlist structure of FIR filter. Proposed obfuscation on comparison with a recent approach for several DSP cores yielded a power reduction of ~10%, design cost reduction ~ 6.5% and security enhancement (strength of obfuscation) of $>\,\,4.29\,\,{e+9}$ times. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This paper presents an incremental timing-driven placement tool, named OWARU. It optimizes timing critical paths through a free space-aware path smoothing: the gates on such paths are relocated to free spaces around the smoothed paths, while incremental static timing analysis is involved to accurately assess timing changes due to the relocation. OWARU is extended to accommodate gate sizing and layer assignment to demonstrate the effectiveness of unified physical synthesis optimizations and incremental placement. The goal is to show that OWARU is an ideal platform for timing closure at later stages of a physical design flow. OWARU is applied on a set of test circuits from 14-nm high-performance commercial microprocessors, which originally failed in timing closure. On average, the worst slack is improved by 63.6%, which corresponds to 5.0% of the clock period; total negative slack is improved by 69.1%. [ABSTRACT FROM AUTHOR]

Quantum computing has raised great interests for its potential to achieve an asymptotic speedup on specific problems. Current quantum devices suffer from noise which needs robust and scalable error-correcting schemes. Topological quantum error correction (TQEC) is among the most promising error-correcting techniques with exponential suppression of error with linear increase of space-time complexity. In this paper, we present the first work to explore space-time optimization between 1-D and 2-D architectures for TQEC circuits. We prove the NP-hardness of the qubit routing problem in the layout synthesis and propose an efficient algorithm to optimize space-time volumes for both 1-D and 2-D qubit architectures with promising experimental results. [ABSTRACT FROM AUTHOR]

Timing resilient designs can remove variation margins by adding error detecting logic (EDL) that detects timing errors when execution completes within a resiliency window. Speeding up near-critical-paths during logic synthesis can reduce the amount of EDL needed but at the cost of increasing logic area. This creates a logic optimization strategy called resynthesis. This paper proposes four alternatives to optimize resilient designs through resynthesis. The first is a brute force approach that explores speeding up all combinations of near-critical paths and produces good results but is computationally impractical for complex circuits. The second is a naive brute-force (BF) approach in which near-critical paths are sped up one end-point at a time. It is much faster than the BF approach because it does not explore the benefits of speeding up multiple end-points simultaneously and thus provides a quick-and-dirty lower bound for the benefits of resynthesis. The third is a geometric program-based iterative algorithm (GPIA) that achieves area reductions that compare favorably across all four approaches. The GPIA algorithm completes within 24 h for all examples and the average area reduction is up to 16%. Because the run-time required to solve this mathematical model can still be long; however, we propose a fourth approach that involves creating a virtual resynthesis cell library that tries to trick the synthesis tool to understand EDL overhead and optimize total area quickly and automatically. This approach obtains an average of approximately two-third of the area reductions of the GPIA approach with fast run times associated with only a single synthesis run. [ABSTRACT FROM PUBLISHER]

This paper proposes a new partial scan approach in which the problem of selecting flip-flops in partial scan designs is converted to the balanced graph transformation problem based on an integer linear programming formulation. The complexity of the problem is analyzed and a scalable approach is proposed to deal with complicated circuits. Experimental results on a set of benchmark circuits show that on average the proposed approach reduces the area overhead by 25% compared with the full scan approach and by 17.8% compared with the existing balanced structure-based partial scan approach. [ABSTRACT FROM PUBLISHER]

Clock network should be optimized to reduce clock power dissipation. The power efficient clock network can be constructed by multibit flip-flop generation and gated clock tree aware flip-flop clumping to pull flip-flops close to the same integrated clock gating cell. It is capable of providing an attractive solution to reduce clock power. This paper considers multicorner and multimode timing constraints for the two combined approach. This proposed method is applied to five industrial digital intellectual property blocks of state-of-the-art mobile system-on-a-chip fabricated in 14-nm CMOS process. Experimental results show that MBFF generation algorithm achieves 22% clock power reduction. Applying a gated clock tree aware flip-flop clumping on top of the MBFF generation further reduces the power to around 32%. [ABSTRACT FROM PUBLISHER]

Energy and temperature are the main constraints for modern high-performance multicore systems. To save power or increase performance, dynamic voltage and frequency scaling (DVFS) is widely applied in literally all computing systems. As CMOS technology continues scaling, FinFET has recently become the common choice for multicore systems. In contrast with planar CMOS, FinFET is characterized by lower delay under higher temperatures in super-threshold voltage region, an effect called temperature effect inversion (TEI). This paper explores TEI-aware performance improvement and energy savings for multicore systems. Our experimental results show that on average 15.70% throughput improvement or 31.26% energy savings can be achieved in steady state by a TEI-aware DVFS policy over a TEI-agnostic one. By further investigation, multiple sweet spots (SSs) resulting from TEI effects are observed. Based on these SS operation regimes, this paper introduces fast algorithms which provide iso-power maximum performance or iso-performance minimum energy consumption. Experimental results confirm the effectiveness of the proposed approach by exhibiting a $45.9 \times $ – $55.3 \times $ speedup when compared to state-of-the-art algorithms while losing only 0.22% or 0.68% in achieved performance or energy, respectively. [ABSTRACT FROM PUBLISHER]

We propose effective algorithms for exact synthesis of Boolean logic networks using satisfiability modulo theories (SMTs) solvers. Since exact synthesis is a difficult problem, it can only be applied efficiently to very small functions, having up to six variables. Key in our approach is to use majority-inverter graphs (MIGs) as underlying logic representation as they are simple (homogeneous logic representation) and expressive (contain AND/OR-inverter graphs) at the same time. This has a positive impact on the problem formulation: it simplifies the encoding as SMT constraints and also allows for various techniques to break symmetries in the search space due to the regular data structure. Our algorithm optimizes with respect to the MIG’s size or depth and uses different ways to encode the problem and several methods to improve solving time, with symmetry breaking techniques being the most effective ones. We discuss several applications of exact synthesis and motivate them by experiments on a set of large arithmetic benchmarks. Using the proposed techniques, we are able to improve both area and delay after lookup table (LUT)-based technology mapping beyond the current results achieved by state-of-the-art logic synthesis algorithms. [ABSTRACT FROM PUBLISHER]

Monolithic 3-D (M3D) integrated circuits (ICs) are an emerging technology that offer much higher integration densities than previous 3-D IC approaches. In this paper, we present a complete netlist-to-layout design flow to design an M3D block, as well as to integrate 2-D and 3-D blocks into an M3D SoC. This design flow is based on commercial tools built for 2-D ICs, and enhanced with our 3-D specific methodologies. We use the OpenSPARC T2 SoC as a case study, implement it in a 28-nm fully depleted silicon on insulator foundry process, and demonstrate that we can achieve up to 12% and 8% power savings for a single block and SoC, respectively, when compared with their 2-D counterparts implemented using commercial tools. [ABSTRACT FROM PUBLISHER]

Double-gate devices, like independent-gate (IG) FinFET, have introduced new possibilities and challenges in synthesis of transistor networks. Existing factorization methods and graph-based optimizations are not actually the most effective way to generate optimized IG FinFET based networks because only reducing the number of literals in a given Boolean expression does not guarantee the minimum transistor count. This paper presents two novel methods aiming the minimization of the number of devices in logic networks. The first contribution is a method for defactoring Boolean expressions able to apply the conventional factorization algorithms together with IG FinFET particularities, so improving it. The second contribution is a novel graph-based method that improves even more transistor arrangements by exploiting enhanced nonseries-parallel associations. Experimental results shown a significant reduction in the size of transistor networks delivered by the proposed methods. [ABSTRACT FROM AUTHOR]

This paper introduces reconditioning: a novel systematic technique for reducing unnecessary power consumption of asynchronous gate-level netlists, which involves the optimal reordering of conditional communication and logic primitives. Our technique is applicable to asynchronous circuits with handshaking protocols that encode data and control together, in particular, quasi delay insensitive and 1-of- N handshaking circuits. Both an optimal integer linear program (ILP) and a fast heuristic algorithm are presented. We show that our ILP is feasible for moderate size circuits and our heuristic algorithm scales to much larger circuits, completing in seconds on circuits with tens of thousands of gates. Our experimental results show power improvement highly depends on the structure of the circuit but can often be above 26% with typically less than 5% area overhead. [ABSTRACT FROM AUTHOR]

Test compaction is an important aspect in the post-production test since it is able to reduce the test data and the test costs, respectively. Current automatic test pattern generation (ATPG) methods treat all faults independently from each other which limits the test compaction capability. We propose a new optimization satisfiability (SAT)-based ATPG for compact test set generation with high fault coverage as well as a new retargeting stage for test set reduction. The ATPG is based on a novel multiple-target test generation formulation using optimization techniques. Robust SAT-based solving algorithms are leveraged to determine compatible fault groups which can be detected by the same test. The proposed technique can be used during initial compact test generation as well as a post-process to increase the compactness of existing test sets, e.g., generated by commercial tools, in an iterative manner. Experimental results show that the proposed SAT-based approach is able to produce highly compacted test sets with high fault coverage for stuck-at as well as transition faults. The approach is able to produce lower pattern counts than a commercial ATPG tool. For one industrial circuit, the test set size can even be reduced down to 26% of the size generated by a commercial ATPG tool. [ABSTRACT FROM PUBLISHER]

Modern systems-on-a-chip and microprocessors, e.g., those in smart phones and laptops, typically have multiple operating conditions, such as video streaming, Web browsing, standby, and so on. They will have different performance targets and run under different supply voltages. Gate sizing (with threshold voltage assignment) is a fundamental step for power/performance optimization. However, conventional gate sizing algorithms only consider one scenario, e.g., the performance-critical operating condition, which may be over-design for other operating conditions. In addition, reliability has become a prime concern in nanometer designs, and gate sizing has been employed to mitigate aging. However: 1) previous aging-affected delay models do not take into account more than one operating condition to estimate the aging impact and 2) earlier aging aware gate sizing algorithms only consider one operating condition at a time. In this paper, we present a new paradigm of aging aware gate sizing, one-size-fits-all (OSFA), which performs power/performance optimizations across multiple operating conditions. The existing delay model for negative bias temperature instability (NBTI) is extended to take into account multiple operating conditions, and incorporated into our OSFA framework. Based on OSFA, we also adjust the supply voltage targeting overall power optimization. A speed-up heuristic is proposed to scale our OSFA design space exploration methodology for higher number of operating conditions. Experimental results on industry-strength benchmarks demonstrate that: 1) compared with conventional approach OSFA could provide an average 6.1% reduction in power without performance loss; 2) NBTI-aware OSFA framework can provide significant improvement in comparison with guard-band based traditional NBTI-aware gate sizing approach; and 3) percentage savings compared to conventional methodology increases with the number of operating conditions. [ABSTRACT FROM AUTHOR]

As CMOS nears the end of the projected scaling roadmap, significant effort has been devoted to the search for new materials and devices that can realize memory and logic. Spintronics, which uses the spin of electrons to represent and manipulate information, is one of the promising directions for the post-CMOS era. While the potential of spintronic memories is relatively well known, realizing logic remains an open and critical challenge. All spin logic (ASL) is a recently proposed logic style that realizes Boolean logic using spin-transfer-torque devices based on the principle of nonlocal spin torque. ASL has advantages such as density, nonvolatility, and low operating voltage. However, it also suffers from drawbacks such as low speed and static power dissipation. Recent work has shown that, in the context of simple arithmetic circuits (adders and multipliers), the efficiency of ASL can be greatly improved using techniques that utilize its unique characteristics. An evaluation of ASL across a broad range of circuits, considering the known optimization techniques, is an important next step in determining its viability. In this paper, we propose a systematic methodology for the synthesis of ASL circuits. Our methodology performs various optimizations that benefit ASL, such as intracycle power gating, stacking of ASL nanomagnets, and fine-grained logic pipelining. We utilize the proposed methodology to evaluate the suitability of ASL implementations for a wide range of benchmarks, viz., random combinational and sequential logic, digital signal processing circuits, and the Leon SPARC3 general-purpose processor. Based on our evaluation, we identify: 1) the large current requirement of nanomagnets at fast switching speeds; 2) the static power dissipation in the all-metallic devices; and 3) the short spin flip length in interconnects as key bottlenecks that limit the competitiveness of ASL. We further evaluate the impact of various potential improvements in device parameters on the efficiency of ASL. [ABSTRACT FROM PUBLISHER]

Traditionally, we expect that circuit designs can be executed without errors. However, for error resilient applications such as image processing, 100% correctness is not necessary. By pursuing less than 100% correctness, power consumption can be significantly reduced. Recently, probabilistic CMOS and probabilistic Boolean circuits (PBCs) have been proposed to deal with power consumption issue. However, to the best of our knowledge, no correctness analysis and power optimization algorithms have been proposed for PBCs. Thus, in this paper, we first propose a statistical approach for evaluating the correctness of PBCs. Then, we propose strategies for power optimization of PBCs. Finally, we integrate these strategies with the correctness analysis as a power optimization algorithm for PBCs. The experimental results show that the proposed correctness analysis method is highly efficient and accurate, and that the power optimization algorithm saves 36% of total power-delay-product on average under a correctness constraint of 90% on a set of International Workshop on Logic and Synthesis (IWLS) 2005 benchmarks. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a design approach to mitigate the hardware overhead of the data completion detection circuit in quasi-delay-insensitive (QDI) asynchronous-logic circuits. In this proposed design approach, three novelties are highlighted. Firstly, a novel microcell-interleaving approach is proposed to reduce the number of completion detection (CD) circuits while retaining the required QDI attribute. Secondly, we analyze the performance of the QDI circuits based on the proposed microcell-interleaving approach graphically in terms of power dissipation, transistor count and delay, and evaluate/determine the upper and lower boundaries of these performance profiles. Thirdly, we propose a microcell-interleaving genetic algorithm (MIGA) to stochastically optimize the proposed microcell-interleaving approach on power dissipation, transistor count, and delay. To validate the proposed design approach, a complete performance profile of ISCAS-85 C499 circuit is investigated on the basis of differential cascode voltage switch logic (DCVSL) and dynamic strong indicating (DSI) microcells. We demonstrate the efficiency of the proposed design approach by benchmarking against the competing DCVSL, null convention logic and DSI designs on five ISCAS-85 circuits. Specifically, the proposed designs, on average, are 1.77\times better in power dissipation, 1.4\times better in area, and 1.58\times better in a composite metric of , and reasonably slower for the lowest power dissipation points. We further demonstrate the practicality of the proposed design approach by implementing an 8-tap 16-bit asynchronous QDI finite impulse response filter. Finally, we demonstrate the {\sim}{10\%} and {\sim}{11\%}$ improved efficiency of the proposed MIGA over the greedy algorithm and dynamic programming, respectively. [ABSTRACT FROM PUBLISHER]

This paper presents a fast and effective approach to gate-version selection and threshold voltage, Vth, assignment. In the proposed flow, first, a solution without slew and load violation is generated. Then, a Lagrangian Relaxation (LR) method is used to reduce leakage power and achieve timing closure while keeping the circuit no or few violations. If the set of gate-versions given by LR produces a circuit with negative slack, a timing recovery method is applied to find near zero positive slack. The solution without negative slack is finally introduced to a power reduction step. For the ISPD 2012 Contest benchmarks, the leakage power of our solutions is, on average, 9.53% smaller than refid="ref1"/ and 12.45% smaller than refid="ref2"/. The sizing produced using our approach achieved the first place in the ISPD 2013 Discrete Gate Sizing Contest with, on average, 8.78% better power results than the second place tool. With new timing calculation applied, this flow can provide, on average, an extra 9.62% power reduction compared to the best Contest results. This flow is also the first gate sizing method to report violation-free solutions for all benchmarks of the ISPD 2013 Contest. [ABSTRACT FROM PUBLISHER]

Due to increasing integrated circuit design complexity, engineering change orders (ECOs) have become a necessary technique to resolve late-found functional errors and/or performance deficiencies. To fix timing violations, gate sizing and buffer insertion are commonly used in postmask ECO. These techniques, however, may not be powerful enough, especially when spare cells are inserted to balance between functional and timing repair capabilities. We propose a postmask ECO technique, called TRECO, to remedy timing violations based on technology remapping, which also supports functional ECO. Unlike conventional technology mapping, TRECO performs technology mapping with respect to a limited set of spare cells and confronts dynamic changes of wiring cost incurred by selection of different spare cells. With a precomputed lookup table of representative circuit templates, TRECO iteratively performs technology remapping to restructure timing critical subcircuits until no timing violation can be further removed. Experimental results on five industrial designs show the effectiveness of TRECO in ECO timing optimization and in timing-aware functional ECO. [ABSTRACT FROM AUTHOR]

Guarded evaluation is a power reduction technique that involves identifying subcircuits (within a larger circuit) whose inputs can be held constant (guarded) at specific times during circuit operation, thereby reducing switching activity and lowering dynamic power. The concept is rooted in the property that under certain conditions, some signals within digital designs are not “observable” at design outputs, making the circuitry that generates such signals a candidate for guarding. Guarded evaluation has been demonstrated successfully for application-specific integrated circuits (ASICs); in this paper, we apply the technique to field-programmable gate arrays (FPGAs). In ASICs, guarded evaluation entails adding additional hardware to the design, increasing silicon area and cost. Here, we apply the technique in a way that imposes minimal area overhead by leveraging existing unused circuitry within the FPGA. The primary challenge in guarded evaluation is in determining the specific conditions under which a subcircuit's inputs can be held constant without impacting the larger circuit's functional correctness. We propose a simple solution to this problem based on discovering gating inputs using “noninverting” and “partial noninverting” paths in a circuit's AND-inverter graph representation. Experimental results show that guarded evaluation can reduce switching activity on average by as much as 32% and 25% for 6-input look-up table (6-LUT) and 4-LUT architectures, respectively. Dynamic power consumption in the FPGA interconnect is reduced on average by as much as 24% and 22% for 6-LUT and 4-LUT architectures, respectively. The impact to critical path delay ranges from 1% to 43%, depending on the guarding scenario and the desired power/delay tradeoff. [ABSTRACT FROM AUTHOR]

This paper presents a logic restructuring technique named node addition and removal (NAR). It works by adding a node into a circuit to replace an existing node and then removing the replaced node. Previous node-merging techniques focus on replacing one node with an existing node in a circuit, but fail to replace a node that has no substitute node. To enhance the node-merging techniques on logic restructuring and optimization, we propose an NAR approach in this paper. We first present two sufficient conditions that state the requirements of added nodes for safely replacing a target node. Then, an NAR approach is proposed to quickly detect the added nodes by performing logic implications based on these conditions. We apply the NAR approach to circuit minimization together with two techniques: redundancy removal and mandatory assignment reuse. We also apply it to satisfiability (SAT)-based bounded sequential equivalence checking (BSEC) to reduce the computation complexity of SAT solving. The experimental results show that our approach can enhance our prior automatic test pattern generation-based node-merging approach. Additionally, our approach has a competitive capability of circuit minimization with 44 times speedup compared to a SAT-based node-merging approach. For BSEC, our approach can work together with other optimization technique to save a total of approximately 39-h verification time for all the benchmarks. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the gate sizing problem and develop techniques for improving the runtime by effectively exploiting the graphics processing unit (GPU) resources. Theoretically, we investigate a randomized cutting plane-based convex optimization technique which is highly parallelizable and can effectively exploit the single instruction multiple data structure imposed by GPUs. In order to further improve the runtime, we also develop GPU-oriented implementation guidelines that exploit the specific structure that convex gate sizing formulations impose. We implemented our method on NVIDIA Tesla 10 GPU and obtain 21\times to 400\times speedup compared to the MOSEK optimization tool implemented on conventional CPU. The quality of solution of our method is very close to that achieved by MOSEK, since both are optimal. [ABSTRACT FROM PUBLISHER]

This paper develops a dynamically adaptive stochastic tunneling (DAST) algorithm to avoid the “freezing” problem commonly found when using simulated annealing for circuit placement on field-programmable gate arrays (FPGAs). The main objective is to reduce the placement runtime and improve the quality of final placement. We achieve this by allowing the DAST placer to tunnel energetically inaccessible regions of the potential solution space, adjusting the stochastic tunneling schedule adaptively by performing detrended fluctuation analysis, and selecting move types dynamically by a multi-modal scheme based on Gibbs sampling. A prototype annealing-based placer, called DAST, was developed as part of this paper. It targets the same computer-aided design flow as the standard versatile placement and routing (VPR) but replaces its original annealer with the DAST algorithm. Our experimental results using the benchmark suite and FPGA architecture file which comes with the Toronto VPR5 software package have shown a 18.3% reduction in runtime and a 7.2% improvement in critical-path delay over that of conventional VPR. [ABSTRACT FROM AUTHOR]

This paper proposes an automatic design flow of datapath-dominated applications which is able to deal with optimization and equivalence checking of multi-output polynomials over Z2. This paper also gives four main contributions: 1) proposing a complete design flow for modular equivalence checking, high level synthesis, and optimization; 2) considering hidden monomials to factorize those polynomials which do not have any common monomials; 3) combining and improving our previous optimization heuristics to eliminate multi-operand common sub-expressions as much as possible; and 4) implementing all algorithms on top of the modular Horner expansion diagram package. Experimental results have shown an average saving of 9.9% and 4.5% in the number of gates and critical path delay, respectively, after applying modular reduction over Z2, while other optimization techniques are not used. Besides, after applying our optimization techniques, experimental comparisons with the state-of-the-art techniques show an average improvement in the area by 19.5% with an average delay decrease of 16.7%. Regarding the comparison with our previous papers, the area and delay are improved by 13.3% and 15.5%, respectively. [ABSTRACT FROM AUTHOR]