Abstract Fully homomorphic encryption (FHE) enables secure data processing without compromising data access. However, its computational cost and slower execution compared to plaintext operations present significant challenges. The increasing interest in FHE-based secure computation underscores the need to accelerate homomorphic computations. Existing research predominantly focuses on reducing the multiplicative depth (MD) of FHE circuits, as a lower MD enhances the execution efficiency of each homomorphic operation. However, this often comes at the expense of increased multiplicative complexity (MC), leading to more homomorphic multiplications — a computationally intensive task. Currently, there is a lack of approaches that effectively balance the trade-off between MD reduction and MC increase, potentially resulting in sub-optimal outcomes. This paper addresses this critical gap with three main contributions: (a) an exact synthesis paradigm for generating optimal FHE circuit implementations, (b) a heuristic circuit optimization algorithm, named MC-aware MD minimization, that leverages the exact synthesis paradigm to optimize FHE circuits efficiently, and (c) an FHE circuit optimization flow that integrates MC-aware MD minimization with existing MD reduction techniques. Experimental results demonstrate a 21.32% average reduction in homomorphic computation time and highlight significantly improved efficiency in circuit optimization.

Sequential logic synthesis expands the solution space compared to combinational logic synthesis by reasoning about the reachable states of memory elements, leading to better Power-Performance-Area (PPA) outcomes. As gate costs continue to rise in advanced technologies, sequential logic synthesis is gaining significant traction within the EDA community as a powerful alternative. This paper introduces a scalable algorithm for don’t-care-based sequential logic synthesis, leveraging sequential k-step induction to perform redundancy removal and resubstitution under Sequential Observability Don’t Cares (SODCs). SODCs generalize Observability Don’t Cares (ODCs) by explicitly considering reachable states, making SODC-based optimization a challenging problem due to dependencies and alignment issues between the base case and inductive case in k-step induction. Our approach overcomes these challenges, fully utilizing the potential of SODCs without limiting the solution space. We rigorously prove the correctness of our approach, discuss some limitations arising from bounded-step induction, and analyze how our approach can effectively be used in practice to exploit obscure optimization opportunities. Implemented as part of an industrial tool, our algorithm achieves an average -6.9% area improvement after technology mapping compared to state-of-the-art sequential synthesis methods, and further provides 3.16% and 1.06% reductions in combinational and sequential areas, respectively, in post place-and-route results. Furthermore, all optimizations are efficiently verified using industrial sequential verification tools.

We address the problem of minimizing the area of circuits mapped to a technology library, with or without delay constraints. While traditional methods optimize first a technology-independent representation and then perform technology mapping to a library, this paper explores the potential for further optimizations through technology-dependent algorithms. We propose an optimization engine for mapped circuits that relies on a database of mapped sub-networks for efficient resynthesis. Experimental results on the EPFL benchmarks after area-oriented optimization and mapping show that the proposed method leads to average area improvements of 5.47% without degrading the delay.

Quantum oracle synthesis involves compiling arbitrary Boolean functions into quantum circuits using specific quantum gates supported by the target quantum computer. The Clifford+T gate library is particularly common in fault-tolerant quantum computing systems. Utilizing XOR-AND-inverter graphs (XAGs) as the logic representation for the target Boolean functions has received extensive attention due to the observed direct correlation between the number of AND nodes in an XAG and the T count and the helper qubit count of the quantum oracle optimally compiled from it. However, to be deployed onto fault-tolerant quantum hardware, quantum gates must be further re-expressed by logical quantum error correction (QEC) code operations, a process known as back-end compilation. This paper enhances the current XAG-based oracle synthesis techniques by establishing a link between the properties of XAGs and quality measures of back-end-compiled quantum oracles. This link unlocks more optimization opportunities---experimental results demonstrate average reductions of 4.49% in T count, 7.00% in logical time steps, and 14.89% in helper qubit count, respectively, on benchmarks optimized by the proposed back-end-aware XAG optimization approaches.

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%.

This paper presents a novel resynthesis engine for minimizing the dynamic power of digital circuits. Traditional logic synthesis methods primarily focus on zero-delay toggles—logic state changes occurring between the start and end of a clock cycle. In contrast, our engine targets both zero-delay toggles and glitches, unintended transitions within a clock cycle caused by path imbalances. Glitches significantly contribute to power consumption in arithmetic circuits, making their minimization a critical challenge in electronic design. The proposed method uses a database of Pareto-optimal netlists to replace sub-networks in the target circuit with power-efficient alternatives. These replacements are guided by a simulation-driven cost function that evaluates workload-independent switching activity and penalizes gates with high fan-out. We call our approach Lazy Man’s Resynthesis because it builds on an algorithm named Lazy Man’s Synthesis, extending it from technology-independent delay optimization to post-mapping power optimization. Applied to the ISCAS and EPFL benchmarks, our method reduces glitching activity by 4.72% and dynamic power by 9.44%, achieving a 7.61% improvement over the state-of-the-art.

This work addresses the synthesis of efficient torus fully homomorphic encryption (TFHE) circuits for private Boolean function evaluation through encoding strategy management. Modern TFHE implementations support multiple plaintext encoding spaces, each offering distinct trade-offs between computational cost and the expressiveness enabled by larger plaintext domains. Smartly switching between encoding strategies to maximize evaluation efficiency remains challenging due to the lack of algorithmic support for determining when and where such transitions should occur. To address this, we propose a synthesis framework that enables encoding-switch-aware TFHE circuit generation. Our approach leverages the structural properties of the exclusive-or sum of products (ESOP) representation to partition Boolean functions into encoding-aligned regions, enabling cost-effective evaluation while minimizing switch overhead. Experimental results demonstrate that our encoding-aware synthesis technique significantly accelerates homomorphic Boolean function evaluation – achieving up to 53.46% and 23.34% average evaluation time reduction on general-purpose Boolean benchmarks – compared to advanced synthesis baselines lacking explicit encoding-switch management. This work lays the groundwork for systematic encoding strategy management in TFHE circuits and highlights the role of logic-level design automation in advancing efficient homomorphic evaluation.

Ashenhurst-Curtis decomposition (ACD) is a decomposition technique used, in particular, to map combinational logic into lookup tables (LUTs) structures when synthesizing hardware designs. However, available implementations of ACD suffer from excessive complexity, search-space restrictions, and slow run time, which limit their applicability and scalability. This article presents a novel fast and versatile technique of ACD suitable for delay optimization. We use this new formulation to compute two-level decompositions into a variable number of LUTs and enhance delay-driven LUT mapping by performing ACD on the fly. Compared to state-of-the-art technology mapping, experiments on heavily optimized benchmarks demonstrate an average delay improvement of 12.39% and area reduction of 2.20% with affordable run time. Additionally, our method improves 4 of the best delay results in the EPFL synthesis competition without employing design-space exploration techniques. Moreover, we use the new formulation to compute exact decompositions into fixed LUT cascade structures of two LUTs, which have efficient implementations in the architecture of AMD field-programmable gate arrays. Compared to the state-of-the-art method, this new formulation leads to an average reduction of 6.22% in delay, 3.82% in area, and 3.09% in the edge count for better run time.

This paper addresses the challenge of reducing the number of nodes in Look-Up Table (LUT) networks with two significant applications. First, Field-Programmable Gate Arrays (FPGAs) can be modelled as networks of LUTs, and minimizing the node count is imperative to meet resource constraints. Second, in area-oriented design space exploration for standard-cell designs, collapsing a circuit into a LUT network, restructuring it, and later remapping to the original representation helps escape local minima. Thus, the development of algorithms for optimizing and restructuring LUT networks holds considerable promise for area-oriented optimization. Substitution (also called resubstitution) is a powerful logic minimization method that can identify non-local logic dependencies and exploit them for logic minimization. State-of-the-art substitution algorithms for LUT networks rely heavily on SAT solving, limiting the number of optimization attempts and the size of the substitution sub-networks to one node mishchenko2011scalable. Conversely, our method relies on circuit simulation to increase the number of substitution candidates and enables substitutions with more than one node. The experimental results show that the proposed method identifies optimization opportunities overlooked by other methods, improving 11 out of 23 best-known results in the EPFL synthesis competition and yielding a 3.46% area reduction compared to the state-of-the-art.

Adiabatic quantum-flux parametron (AQFP) is an energy-efficient superconducting technology. Before physical design can be performed, AQFP technology mapping involves not only mapping logic into supported gate types but also legalizing the circuit to fulfill the technology-imposed constraints on path balancing and fanout branching by inserting buffer and splitter cells. These cells account for a significant amount of the circuit’s area, delay, as well as for increasing energy consumption. In this paper, we (a) identify that the AQFP legalization problem is a scheduling problem; (b) propose linear-time depth-optimal scheduling and irredundant buffer insertion algorithms; (c) present heuristic optimization algorithms to further reduce buffer count; and (d) suggest an unsupervised design space exploration approach for AQFP technology mapping, mixing and interleaving logic optimization and technology legalization. Experimental results show that our design space exploration, utilizing the proposed technology legalization and optimization flow, achieves 44% improvement on the energy-delay product compared to the state of the art.

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.

It is envisaged that spintronic logic devices will ultimately be utilized in hybrid CMOS-spintronic systems where signal interconversion between magnetic and electrical domains via transducers takes place. This underscores the vital role of transducers in influencing the overall performance of such hybrid systems. This paper addresses the question: Can spintronic circuits based on Magnetic Tunnel Junction (MTJ) transducers outperform their state-of-the-art CMOS counterparts? To this end, we use the EPFL (École Polytechnique Fédérale de Lausanne) combinational benchmark sets, synthesize them in 7 nm CMOS and in MTJ transducer based spintronic technologies, and compare the two implementation methods in terms of Energy-Delay-Product (EDP). To fully utilize the technologies’ potential, CMOS and spintronic implementations are built upon standard Boolean and Majority Gates, respectively. For the spintronic circuits, we assumed that domain conversion (electric/magnetic to magnetic/electric) is performed by means of MTJs and the computation is accomplished by domain wall (DW)-based majority gates, and considered two EDP estimation scenarios: (i) Uniform Benchmarking, which ignores the circuit’s internal structure and only includes domain transducers’ power and delay contributions into the calculations, and (ii) Majority-Inverter-Graph Benchmarking, which also embeds the circuit structure, the associated critical path delay and energy consumption by DW propagation. Our results indicate that, for the uniform case, the spintronic route is better suited for the implementation of complex circuits with few inputs and outputs. On the other hand, when the circuit structure is also considered via majority and inverter synthesis, our analysis clearly indicates that in order to match and eventually outperform CMOS performance, MTJ transducers’ efficiency has to be improved by 3-4 orders of magnitude. While it is clear that for the time being the MTJ-based-spintronic way cannot compete with CMOS, further technological transducer developments may tip the balance, which, when combined with information non-volatility, may make spintronic implementation for certain applications that require a large number of calculations and have a rather limited amount of interaction with the environment.

Rapid single-flux quantum (RSFQ) is one of the most advanced superconductive electronics technologies. SFQ systems operate at tens of gigahertz with up to three orders of magnitude smaller power as compared to CMOS. In conventional SFQ systems, most gates require clock signal. Each gate should have the fanins with equal logic depth, necessitating insertion of path-balancing (PB) DFFs, incurring prohibitive area penalty.Multiphase clocking is the effective method for reducing the path-balancing overhead at the cost of reduced throughput. However, existing tools are not directly applicable for technology mapping of multiphase systems. To overcome this limitation, in this work, we propose a technology mapping tool for multiphase systems. Our contribution is threefold. First, we formulate a phase assignment as a Constraint Programming with Satisfiability (CP-SAT) problem, to determine the phase of each element within the network. Second, we formulate the path balancing problem as a CP-SAT to optimize the number of DFFs within an asynchronous datapath. Finally, we integrate these methods into a technology mapping flow to convert a logic network into a multiphase SFQ circuit. In our case studies, by using seven phases, the size of the circuit (expressed as the number of Josephson junctions) is reduced, on average, by 59.94 % as compared to the dual (fast-slow) clocking method, while outperforming the state-of-the-art single-phase SFQ mapping tools.

Rapid single-flux quantum (RSFQ) is one of the most advanced and promising superconducting logic families, offering exceptional energy efficiency and speed. RSFQ technology requires delay registers (DFFs) and splitter cells to satisfy the path-balancing and driving-capacity constraints. In this paper, we present a comprehensive exploration of methods for synthesizing and optimizing SFQ circuits. Our approach includes algebraic and Boolean optimization techniques that work on the xor-and graph (XAG) representation of combinational logic. Additionally, we introduce a technology mapping method to satisfy the path-balancing and fanout constraints while minimizing the area. Finally, we propose a synthesis flow for SFQ circuits. In the experimental results, we show an average reduction in the area and delay of 43% and 34%, respectively, compared to the state-of-the-art.

Technology mapping transforms a technology-independent representation into a technology-dependent one given a library of cells. This process is performed by means of local replacements that are extracted by matching sections of the subject graph to library cells. Matching techniques are classified mainly into pattern and Boolean. These two techniques differ in quality and number of generated matches, scalability, and run time. This paper proposes hybrid matching, a new methodology that integrates both techniques in a technology mapping algorithm. In particular, pattern matching is used to speed up the matching phase and support large cells. Boolean matching is used to increase the number of matches and quality. Compared to Boolean matching, we show that hybrid matching yields an average reduction in the area and run time by 6% and 25%, respectively, with similar delay.

Rapid single-flux quantum (RSFQ) is one of the most advanced cryogenic superconductive electronics technologies. With orders of magnitude smaller power dissipation, RSFQ is an attractive technology for cloud computing, aerospace electronics, and high-speed interfacing with quantum computing systems. Technological challenges however greatly complicate the realization of VLSI-complexity RSFQ systems. For example, gate-level pipelining in SFQ systems incurs a significant area overhead due to the need for path balancing. This issue is particularly detrimental to SFQ systems due to the limited layout density of RSFQ systems.

The majority-inverter graph (MIG) is a homogeneous logic network widely used in logic synthesis for majority-based emerging technologies. Many logic optimization algorithms have been proposed for MIGs, including rewriting, resubstitution, and graph mapping. However, unlike AIGs, research on optimization flows for MIGs is limited. In this paper, we explore combinations of well-developed MIG optimization algorithms using an on-the-fly design space exploration strategy and present the latest best results on MIG size minimization of EPFL benchmarks. Significant reductions (of 88% and 79%) are observed for two specific benchmarks and an average of 14% improvement is achieved compared to the state-of-the-art flow.

Superconducting electronics provide us with cryogenic digital circuits that can rival established technologies in performance and energy consumption. Today, the lack of tools for the design of large-scale integrated superconducting circuits is a major obstacle to their deployment. Few research institutions and companies have contributed to making such tools available. This review focuses on methods, algorithms, and open-source design tools for logic synthesis of superconducting circuits in two major families: single-flux quantum (SFQ) circuits and adiabatic quantum flux parametron (AQFP).

Rapid single-flux quantum (RSFQ), a leading cryogenic superconductive electronics (SCE) technology, offers extremely low power dissipation and high speed. However, implementing RSFQ systems at VLSI complexity faces challenges, such as substantial area overhead from gate-level pipelining and path balancing, exacerbated by RSFQ's limited layout density. T1 flip-flop (T1-FF) is an RSFQ logic cell operating as a pulse counter. Using T1-FF the full adder function can be realized with only 40% of the area required by the conventional realization. This cell however imposes complex constraints on input signal timing, complicating its use. Multiphase clocking has been recently proposed to alleviate gate-level pipelining overhead. The fanin signals can be efficiently controlled using multiphase clocking. We present the novel two-stage SFQ technology mapping methodology supporting the T1-FF. Compatible parts of the SFQ network are first replaced by the efficient T1-FFs. Multiphase retiming is next applied to assign clock phases to each logic gate and insert DFFs to satisfy the input timing. Using our flow, the area of the SFQ networks is reduced, on average, by 6% with up to 25% reduction in optimizing the 128-bit adder.

Logic rewriting is a powerful optimization technique that replaces small sections of a Boolean network with better implementations. Typically, exact synthesis is used to compute optimum replacement on-the-fly, with possible support for Boolean don't cares. However, exact synthesis is computationally expen-sive, rendering it impractical in industrial tools. For this reason, optimum structures are typically pre-computed and stored in a database, commonly limited to 4-inputs. Nevertheless, this method does not support the use of don't cares. In this paper, we propose a technique to enable the usage of don't cares in pre-computed databases. We show how to process the database and perform Boolean matching with Boolean don't cares, with negligible run time overhead. Logic rewriting techniques are typically very effective at optimizing majority-inverter graphs (MIGs). In the experiments, we show that the usage of don't cares in logic rewriting on MIGs offers an average size improvement of 4.31 % and up to 14.32% compared to state-of-the-art synthesis flow.

Sequential logic synthesis can provide better Power-Performance-Area (PPA) than combinational logic synthesis since it explores a larger solution space. As the gate cost in advanced technologies keeps rising, sequential logic synthesis provides a powerful alternative that is gaining momentum in the EDA community. In this work, we present a new scalable algorithm for don't-care-based sequential logic synthesis. Our new approach is based on sequential k-step induction and can apply both redundancy removal and resubstitution transformations under Sequential Observability Don't Cares (SODCs). Using SODC-based optimizations with induction is a challenging problem due to dependencies and alignment of don't cares among the base case and the inductive case. We propose a new approach utilizing the full power of SODCs without limiting the solution space. Our algorithm is implemented as part of an industrial tool and achieves a 6.9% average area improvement after technology mapping when compared to state-of-the-art sequential synthesis methods. Moreover, all the new sequential optimizations can be verified using state-of-the-art sequential verification tools.

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.

Minimizing the use of CNOT gates in quantum state preparation is a crucial step in quantum compilation, as they introduce coupling constraints and more noise than single-qubit gates. Reducing the number of CNOT gates can lead to more efficient and accurate quantum computations. However, the attainment of optimal solutions is hindered by the complexity of modeling superposition and entanglement. In this paper, we propose an effective state preparation algorithm using an exact CNOT synthesis formulation. Our method represents a milestone as the first design automation algorithm to surpass manual design, reducing the best CNOT count to prepare a Dicke state by 2x. For general states with up to 20 qubits, our method reduces the CNOT count by 9% and 32% for dense and sparse states, respectively, on average, compared to the latest algorithms.

Hardware Trojan (HT) poses a critical security threat to integrated circuits, which can change circuit functionality or leak sensitive data. HTs are typically activated under low-probability conditions by exploiting "rare signals" in logic circuits. In this paper, we propose RareLS, rarity-reducing logic synthesis for mitigating HT threats. Specifically, RareLS reduces the number of rare signals through rarity-oriented technology-independent optimization and technology mapping. Experimental results show that RareLS reduces rare signals by 63.4% on average, with a small overhead of 4.0% in area, 1.9% in delay, and 6.2% in power. Moreover, RareLS complicates HT insertion for attackers by reducing HT trigger logic by 92.94%, and aids defenders in detecting HTs by shortening the test length by more than 80.83%.

Logic synthesis is an ensemble of algorithms that optimizes digital circuit representations and maps them to a chosen technology. Minimizing the number of gates is essential to reduce area occupation and power consumption. As the problem is intractable, heuristic logic transformations are used. In particular, resubstitution attempts to express the function of a node using other nodes already present in the network. State-of-the-art resubstitution engines can only identify new implementations with support of up to three inputs or being simply decomposable. This work aims at extending resubstitution to non-decomposable functions with more than three inputs and it outperforms previous methods. We apply our method on highly optimized designs from the ISCAS and EPFL benchmarks, achieving additional average improvements of 18.50% and 8.36%.

In logic circuits, the number of fanouts a gate can drive is limited, and such limits are tighter in emerging technologies such as superconducting electronic circuits. Moreover, some such technologies, e.g., adiabatic quantum-flux-parametron (AQFP), pose additional constraints such as the need for balanced input-to-output paths to ensure proper signal propagation. In this work, targeting emerging technologies, we study the problem of re-synthesizing a logic network with bounded-fanout gates while minimizing area for a given depth. Namely, we 1) formulate the fanout-bounded synthesis (FBS) problem for a fixed target logic depth as an integer linear program (ILP), 2) propose a scalable top-down approach to construct a feasible solution to the ILP, and 3) extend both the exact and the heuristic approaches to the setting of path-balanced networks. Using our ILP, we obtain the global optimum solutions for a number of benchmarks that serve as ground truth for evaluating heuristic algorithms in both general and path-balanced FBS. Our heuristic algorithm for general FBS achieves an 11.82% better area than the state of the art with matching or better delays while attaining the optimum/near-optimum area for several considered benchmarks. For the path-balanced setting, our heuristic approach achieves 8.76% better delay on average with an average area improvement of 0.5% when using AQFP as the exemplar technology, while achieving more than 17% better delays on several benchmarks.

The Adiabatic Quantum-Flux Parametron (AQFP) is an energy-efficient superconducting logic family. AQFP technology requires buffer and splitting elements (B/S) to be inserted to satisfy path-balancing and fanout-branching constraints. B/S insertion policies and optimization strategies have been recently proposed to minimize the number of buffers and splitters needed in an AQFP circuit. In this work, we study the B/S insertion and optimization methods. In particular, the paper proposes: i) an algorithm for B/S insertion that guarantees global depth optimality; ii) a new approach for B/S optimization based on minimum register retiming; iii) a B/S optimization flow based on (i), (ii), and existing work. We show that our approach reduces the number of B/S up to 20% while guaranteeing optimal depth and providing a 55X speed-up in run time compared to the state-of-the-art.

Factored form is a powerful multi-level representation of a Boolean function that readily translates into an implementation of the function in CMOS technology. In particular, the number of literals in a factored form correlates strongly with the number of transistors in the CMOS implementation. This paper develops novel methods for optimizing factored forms while working on the efficient and-inverter graph (AIG) representation of combinational logic. This is in contrast to the traditional logic synthesis based on logic networks, and other AIG-based methods that minimize the AIG nodes count. Experiments show that applying these methods helps to reduce the area after technology mapping by an additional 2.8% on average, compared to a high-effort area-oriented baseline. It is expected that deploying these methods as part of an industrial standard-cell design flow will reduce design costs and power consumption. Additionally, this work enables efficient transistor-level logic synthesis of large designs with various applications in design automation.

In logic circuits, the number of fanouts a gate can drive is limited, and such limits are tighter in emerging technologies such as superconducting electronic circuits. In this work, we study the problem of resynthesizing a logic network with bounded-fanout gates while minimizing area. We 1) formulate this problem for a fixed target logic depth as an integer linear program (ILP) and present exact solutions for small logic networks, and 2) propose a top-down approach to construct a feasible solution to the ILP which yields an efficient algorithm for fanout bounded synthesis. When using the minimum depth achievable with unbounded fanouts as the target logic depth, our top-down approach achieves 11.82% better area as compared to the state-of-the-art with matching or better delays.

Superconductive electronics is a promising candidate for supplementing or replacing existing CMOS VLSI systems. Rapid single-flux quantum (RSFQ) is one of the most advanced superconductive technologies operating at tens of gigahertz while reducing the operating power by up to three orders of magnitude as compared to conventional semiconductor systems. Achieving VLSI complexity of RSFQ integrated systems, however remains an elusive task due to fundamental differences between RSFQ and CMOS technologies. Most RSFQ logic gates, such as NOT and XOR are sequential in nature. Compared to CMOS, the number of logical pipeline stages is prohibitively large, greatly complicating the design of complex systems. Furthermore, additional circuitry, such as splitters and path balancing flip flops, constitute a major overhead. In this paper, a gate compounding technique is presented to maximize the functionality achievable within a single clock cycle. The logic gates are decomposed into primitives that can be efficiently combined to evaluate complex expressions in a single clock cycle. Structures generated by gate compounding are not sensitive to signal arrival time, simplifying the system design process. The expressive power of SFQ logic is increased, allowing any two-input truth table to be implemented within a single clock cycle. A 4-bit carry lookahead adder (CLA) is implemented using compound gates, demonstrating smaller area, pipeline depth, and clock tree size.

Technology mapping transforms a technology-independent representation into a technology-dependent one given a library of cells. Even if technology libraries contain multi-output cells, state-of-the-art techniques fully exploit single-output cells only. Multi-output cells have limited support in logic synthesis and are typically handled as white boxes once identified. This paper presents a scalable method to increase the support of multi-output library cells in technology mapping. Our contributions include 1) an approach to detect multi-output cells, 2) a fast Boolean matching methodology, and 3) a technology mapping algorithm that supports multi-output cells. Unlike previous work, we address the mapping problem over the whole network. This has the advantage of optimizing area and delay without requiring many incremental steps. The experiments show that full adders and half adders are efficiently detected and mapped with an average area improvement of 7.48% when mapping for minimal delay compared to the default mapper in ABC. Moreover, our method improves the area of the synthesis flow in Yosys, which treats multi-output cells as white boxes, by 5 % on average with a limited run time overhead.

Garbled circuit (GC) is one of the few promising protocols to realize general-purpose secure computation. The target computation is represented by a Boolean circuit that is subsequently transformed into a network of encrypted tables for execution. The need of distributing GCs among parties however requires excessive data communication, called garbling cost, which bottlenecks system performance. Due to the zero garbling cost of XOR operations, existing works reduce garbling cost by representing the target computation as the XOR-AND graph (XAG) with minimum multiplicative complexity. Recently, an XOR-OneHot graph (X1G) has been proposed as an efficient GC representation. However, there is a lack of formal proof of X1G performance in the literature. In this paper, we prove that starting from any XAG, there exists an X1G implementation with equal or lower garbling cost. Based on our findings, we propose (a) an affine function classification-based database generation method, which decouples time-consuming on-the-fly exact syn-thesis from Boolean rewriting; (b) a novel optimal X1G synthesis approach to accelerate the database generation procedure. The proposals jointly facilitate a performant Boolean rewriting-based X1G optimization method. Experimental evaluations show significant improvement in both garbling cost and runtime: with a 2273.63× speed-up achieved on average, the proposed method realized an up-to 8.20% improvement in garbling cost reduction compared to the state-of-the-art.

Rapid single-flux quantum (RSFQ) is one of the most advanced superconducting technologies with the potential to supplement or replace conventional VLSI systems. However, scaling RSFQ systems up to VLSI complexity is challenging due to fundamental differences between RSFQ and CMOS technologies. Due to the pulse-based nature of the technology, RSFQ systems require gate-level pipelining. Moreover, logic gates have an extremely limited driving capacity. Path balancing and clock distribution constitute a major overhead, often doubling the size of circuits. Gate compounding is a novel technique that substantially enriches the functionality realizable within a single clock cycle. However, standard logic synthesis tools do not support its specific synchronization constraints. In this paper, we build first a database of minimum-area compound gates covering all the Boolean functions up to 4 variables and all possible input arrival patterns. Then, we propose a technology mapping method for RSFQ circuits that exploits compound gates using the database as a cell library. We evaluate our framework over the EPFL and ISCAS benchmark circuits. Our results show, on average, a 33% lower logic depth with 24% smaller area, as compared to the state of the art.

Logic Synthesis From Partial Specifications (LSFPS) is the problem of finding the hardware implementation of a Boolean function from a partial knowledge of its care set. The elements missing from the specifications are named don’t knows. The exact solution of LSFPS is the minimum size circuit of the corresponding problem in which the don’t knows set is void. Hence, in addition to the traditional objective of size minimization, the goal is to maximize the test accuracy, i.e., the accuracy of the circuit when evaluated over a subset of the don’t knows. This problem is relevant because efficient solutions can lead to hardware friendly machine learning models, not relying on black-box approaches. Indeed, LSFPS maps directly to the problem of the automatic generation of optimized topologies for Binarized Neural Networks. Furthermore, combining the exact solution with modern logic synthesis techniques would unlock unprecedented optimization capabilities. Previous works proved the effectiveness of approximate logic synthesis (ALS) for designing circuits with high test accuracy. Nonetheless, these methods sacrifice accuracy on the specifications, which banishes them from the legitimate candidates for LSFPS. In this paper, we propose accuracy recovery, a procedure to map an approximate version of the circuit to a new one that satisfies the exact functionality of the specifications. The proposed approach relies on an extension of a disjoint support decomposition algorithm. Relative experiments on the IWLS2020 benchmarks show that, on average, the addition of the designed decomposition to a synthesis flow reduces by 17.38% the number of gates and by 12.02% the depth. The usage of accuracy recovery, based on such a decomposition, yields a 95.73% accuracy in the binary MNIST problem, beating the state-of-the-art in ALS of 92.76%.

Logic resynthesis is one of the core problems in modern peephole logic optimization algorithms. Given a target function and a set of existing functions, logic resynthesis asks for a circuit reusing some of the existing functions and generating the target. While exact methods such as enumeration and SATbased synthesis guarantee optimal solutions, limitations on the problem size are inevitable due to scalability concerns. In this work, we propose heuristic resynthesis algorithms for ANDbased, majority-based, and multiplexer-based circuits, which are scalable in all aspects. Used as the core of high-effort optimization, our heuristic resynthesis algorithms play a key role in enabling 2-3% further size reduction on benchmarks that are already processed by state-of-the-art optimization flows.

Individual transistors based on emerging reconfigurable nanotechnologies exhibit electrical conduction for both types of charge carriers. These transistors [referred to as reconfigurable field-effect transistors (RFETs)] enable dynamic reconfiguration to demonstrate either a p- or an n-type functionality. This duality of functionality at the transistor level is efficiently abstracted as a self-dual Boolean logic, that can be physically realized with fewer RFET transistors compared to the contemporary CMOS technology. Consequently, to achieve better area reduction for RFET-based circuits, the self-duality of a given circuit should be preserved during logic optimization and technology mapping. In this article, we specifically aim to preserve self-duality by using Xor-majority graphs (XMGs) as the logic representation during logic synthesis and technology mapping. We propose a synthesis flow that uses new restructuring techniques, called rewriting and resubstitution for XMGs to preserve self-duality during technology-independent logic synthesis. For technology mapping, we use a novel open-source and a logic-representation agnostic mapping tool. Using the above-proposed XMG-based flow, we demonstrate its benefits by comparing post-mapping areas for synthetic and cryptographic benchmarks with three different synthesis flows: 1) AIG-based optimization and AIG-based mapping; 2) XMG-based optimization with AIG-based mapping; and 3) AIG-based optimization with logic-representation agnostic mapping. Our experiments show that the proposed XMG-based flow efficiently preserves self-duality and achieves the best area results for RFET-based circuits (up to 12.36% area reduction) with respect to the baseline.

This paper proposes a versatile mapping approach that has three objectives: i) it can map from one technology-independent graph representation to another; ii) it can map to a cell library; iii) it supports logic rewriting. The method is cut-based, mitigates logic-sharing issues of previous graph mapping approaches, and exploits structural hashing. The mapper is the first one of its kind to support remapping among various graph representations, thus enabling specialized mapping to emerging technologies (such as AQFP) and for security applications (such as XAG-based design). We show that mapping to MIGs improves area by 10% as compared to the state of the art, and that technology mapping is 18% faster than ABC with slightly better results.

Universal quantum algorithms that prepare arbitrary n-qubit quantum states require${O\left(2^{n}\right)}$gate complexity. The complexity can be reduced by considering specific families of quantum states depending on the task at hand. In particular, multipartite quantum states that are invariant under permutations, e.g. Dicke states, have intriguing properties. In this paper, we consider states invariant under cyclic permutations, which we call cyclic states. We present a quantum algorithm that deterministically prepares cyclic states with gate complexity${O\left(n\right)}$without requiring any ancillary qubit. Through both analytical and numerical analyses, we show that our algorithm is more efficient than existing ones.

The paper presents a novel DAG-aware Boolean rewriting algorithm for restructuring combinational logic before technology mapping. The algorithm, called window rewriting, repeatedly selects small parts of the logic and replaces them with more compact implementations. Window rewriting combines small-scale windowing with a fast heuristic Boolean resynthesis. The former uses sophisticated structural analysis to capture reconvergent paths in a multi-output window. The latter re-expresses the multi-output Boolean function of the window using fewer gates if possible. Experiments on the EPFL benchmarks show that a single iteration of window rewriting outperforms state-of-the-art AIG rewriting repeated until convergence in both quality and runtime.

Adiabatic quantum-flux parametron (AQFP) is an energy-efficient superconducting technology. Buffer and splitter (B/S) cells must be inserted to an AQFP circuit to meet the technology-imposed constraints on path balancing and fanout branching. These cells account for a significant amount of the circuit's area and delay. In this paper, we identify that B/S insertion is a scheduling problem, and propose (a) a linear-time algorithm for locally optimal B/S insertion subject to a given schedule; (b) an SMT formulation to find the global optimum; and (c) an efficient heuristic for global B/S optimization. Experimental results show a reduction of 4% on the B/S cost and 124X speed-up compared to the state-of-the-art algorithm, and capability to scale to a magnitude larger benchmarks.

Adiabatic superconducting devices are promising candidates to develop high-speed/low-power electronics. Advances in physical technology must be matched with a systematic development of comprehensive design and simulation tools to bring superconducting electronics to a commercially viable state. Being the technology fundamentally different from CMOS, new challenges are posed to design automation tools: library cells are controlled by multi-phase clocks, they implement the majority logic function, and they have limited fanout. We present a product-level RTL-to-GDSII flow for the design of Adiabatic Quantum-Flux-Parametron (AQFP) electronic circuits, with a focus on the special techniques used to comply with these challenges. In addition, we demonstrate new optimization opportunities for graph matching, resynthesis, and buffer/splitter insertion, improving the state-of-the-art.

This work presents tweedledum-an extensible open-source library aiming at narrowing the gap between high-level algorithms and physical devices by enhancing the expressive power of existing frameworks. For example, it allows designers to insert classical logic (defined at a high abstraction level, e.g., a Python function) directly into quantum circuits. We describe its design principles, concrete implementation, and, in particular, the library's core: An intuitive and flexible intermediate representation (IR) that supports different abstraction levels across the same circuit structure.

Quantum electronic circuits where the logic information is processed and stored in single flux quanta promise efficient computation in a performance/power metric, and thus are of utmost interest as possible replacement or enhancement of CMOS. Several electronic device families leverage superconducting materials and transitions between resistive and superconducting states. Information is coded into bits with deterministic values - as opposed to qubits used in quantum computing. As an example, information can be coded into pulses. Logic gates can be modeled as finite-state machines, that emit logic outputs in response to inputs. The most natural realization of such circuits is through synchronous implementations, where a clock stimulus is transmitted to every logic gate and where logic depth is balanced at every input to achieve full synchrony. Novel superconducting realization families try to go beyond the limitations of synchronous logic with approaches reminiscent of asynchronous design style and leveraging information coding. Moreover, some superconducting families exploit adiabatic operation, in the search for minimizing energy consumption. Design automation for quantum electronic logic families is still in its infancy, but important results have been achieved in terms of automatic balancing and fanout management. The combination of these problems with logic restructuring poses new challenges, as the overall problem is more complex as compared to CMOS and algorithms and tools cannot be just adapted. This presentation will cover recent advancement in design automation for superconducting electronic circuits as well as address future developments in the field.

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.

Adiabatic quantum-flux-parametron (AQFP) circuits are a family of superconducting electronic (SCE) circuits that have recently gained growing interest due to their low-energy consumption, and may serve as alternative technology to overcome the down-scaling limitations of CMOS. AQFP logic design differs from classic digital design because logic cells are natively abstracted by the majority function, require data and clocking in specific timing windows, and have fan-out limitations. We describe here a novel majority-based logic synthesis flow addressing AQFP technology. In particular, we present both algebraic and Boolean methods over majority-inverter graphs (MIGs) aiming at optimizing size and depth of logic circuits. The technology limitations and constraints of the AQFP technology (e.g., path balancing and maximum fanout) are considered during optimization. The experimental results show that our flow reduces both size and depth of MIGs, while meeting the constraint of the AQFP technology. Further, we show an improvement for both area and delay when the MIGs are mapped into the AQFP technology.

Look-up Table (LUT) mapping and optimization is an important step in Field Programmable Gate Arrays (FPGAs) design. The effectiveness of LUT synthesis improved dramatically in the last decades, thanks to optimization and mapping innovations naturally tailored for FPGAs. In this paper, we develop a new LUT-based optimization flow that is tailored for the synthesis of Application-Specific Integrated Circuits (ASICs) rather than FPGAs. We enhance LUT mapping to consider the literal/AIG cost of LUT nodes. We extend traditional Boolean methods to simplify and re-shape LUT-networks, targeting the best AIG/mapped-network implementation, after decomposition. Intuitively, literal-driven LUT packing behaves as a powerful fanin-bound node elimination, unveiling higher-order Boolean simplification opportunities. We embed our proposed LUT-based optimization flow, area oriented, in a commercial synthesis tool. Using our methodology, we improve 12 of the best area results in the EPFL synthesis competition. Employed in a commercial EDA flow for ASICs, our LUT optimization reduces area by 1.80%, total negative slack by 0.39%, and switching power by 1.72%, after physical implementation, at 5% runtime cost.

Emerging reconfigurable nanotechnologies allow the implementation of self-dual functions with a fewer number of transistors as compared to traditional CMOS technologies. To achieve better area results for Reconfigurable Field-Effect Transistors (RFET)-based circuits, a large portion of a logic representation must be mapped to self-dual logic gates. This, in turn, depends upon how self-duality is preserved in the logic representation during logic optimization and technology mapping. In the present work, we develop Boolean size-optimization methods-a rewriting and a resubstitution algorithm using Xor-Majority Graphs (XMGs) as a logic representation aiming at better preserving self-duality during logic optimization. XMGs are more compact for both unate and binate logic functions as compared to conventional logic representations such as And-Inverter Graphs (AIGs) or Majority-Inverter Graphs (MIGs). We evaluate the proposed algorithm over crafted benchmarks (with various levels of self-duality) and cryptographic benchmarks. For cryptographic benchmarks with a high self-duality ratio, the XMG-based logic optimisation flow can achieve an area reduction of up to 17% when compared to AIG-based optimization flows implemented in the academic logic synthesis tool ABC.

We present a flow for synthesizing quantum operations that are defined by classical combinational functions. The discussion will focus on out-of-place computation, i.e.,$U_{f}$:$\vert x\rangle\vert y\rangle\vert 0\rangle^{k}\rightarrow\vert x\rangle\vert y\oplus f(x)\rangle\vert 0\rangle^{k}$. Our flow allows users to express this function at a high level of abstraction. At its core, there is an improved version of the current state-of-the-art algorithm for synthesizing oracles [1]. As a result, our synthesized circuits use up to 25 % fewer qubits and up to 43 % fewer Clifford gates. Crucially, these improvements are possible without increasing the number of$T$gates nor the execution time.

We propose a flow for automated quantum compilation. Our flow takes a Boolean function implemented in Python as input and translates it into a format appropriate for reversible logic synthesis. We focus on two quantum compilation tasks: uniform state preparation and oracle synthesis. To illustrate the use of our flow, we solve IBM's virtual hackathon challenge of 2019, called the Zed city problem, an instance of vertex coloring, by using quantum search algorithms. The expressiveness of Python in combination with automated compilation algorithms allows us to express quantum algorithms at a high level of abstraction, which reduces the effort to implement them, and leads to better and more flexible implementations. We show that our proposed flow generates a lower-cost circuit implementation of the oracle needed to solve IBM's challenge when compared to the winning submission.

Logic resynthesis is the problem of finding a dependency function to re-express a given Boolean function in terms of a given set of divisor functions. In this paper, we study logic resynthesis of majority-based circuits, which is motivated by the increasing interest in majority logic optimization due to the recent development of beyond-CMOS technologies. To meet the need for an efficient majority resynthesis heuristic, we propose a top-down decomposition algorithm, whose complexity is linear to both n and m, where n is the number of divisors and m is the number of majority operations in the dependency function. We evaluate the resynthesis algorithms by using them in a resubstitution run applied on the EPFL benchmark suite. The experimental results show that, comparing to the state-of-the-art enumeration algorithm whose complexity grows exponentially with m, using the proposed decomposition Algorithm leads to 1.5% more circuit size reduction by lifting the limitation on m, within comparable runtime.

Most logic synthesis algorithms work on graph representations of logic functions with nodes associated with arbitrary logic expressions or simple logic functions and iteratively optimize such graphs. While recent multilevel logic synthesis efforts focused primarily on graphs with 2-input nodes such as AND and OR gates, the recently proposed paradigm of Majority-Inverter Graphs (MIGs) instead uses the 3-input Majority gate as the node function. As this technique proved to be a success, it is natural to ask: are there other 3-input gates better suited for logic synthesis? Motivated by this question, we investigate the relative advantages of 3-input gates as constituents of logic networks. We consider representative gates from each of the ten nondegenerate 3-input NPN classes and study how powerful they are at representing Boolean functions. Using SAT-based exact synthesis, we evaluate each 3-input gate using the minimum number of such gates (together with inverters) needed to synthesize all 4-input Boolean functions and a subset of frequent 5-input and 6-input Boolean functions. We show that the logic gate Dot(x,y,z) \mathrel \mathrel \mathop:= x ⊕(z Vxy) outperforms the rest in terms of expressive power. We further confirm this observation by showing that Dot-Inverter Graph representations are more than 14% smaller as compared to MIG representations of EPFL benchmarks.

SAT-sweeping is a powerful method for simplifying logic networks. It consists of merging gates that are proven equivalent (up to complementation) by running simulation and SAT solving in synergy. SAT-sweeping is used in both verification and synthesis applications within EDA. In this paper, we focus on the development of a highly efficient, synthesis-oriented, SAT-sweeping engine. We introduce a new algorithm to guide initial simulation, which strongly reduces the number of false candidates for merge, thus increasing the computational efficiency of the sweeper. We revisit the SAT-sweeping flow in light of practical considerations for synthesis, with the aim of proving all valid merges and ensuring fast execution. Experimental results confirm remarkable speedup deriving from our methodology, up to 10× for large combinational networks, and better QoR as compared to previous SAT-sweeping implementation. Embedded in a commercial synthesis flow, our proposes SAT-sweeper enables area and power savings of 1.98% and 1.81%, respectively, with neutral timing at negligible runtime overhead, over 36 testcases.

Emerging technologies such as plasmonics and photonics are promising alternatives to CMOS for high throughput applications, thanks to their waveguide's low power consumption and high speed of computation. Besides these qualities, these novel technologies also implement logic functionalities uncommon to traditional technologies that can be beneficial to existing CMOS architectures. In this work, we study how plasmonic-based devices can complement CMOS technology to achieve a more efficient implementation of multiplier architectures, which are the core of state-of-the-art data- and signal-processing circuits. A critical part of modern multipliers is the partial-product reduction step, used to reduce the partial product tree into a 2-input addition. In CMOS technology, this step is achieved by using compact and fast counters. On the other hand, the proposed plasmonic cells naturally implement counters of 3-, 9- and 27-inputs within a few logic levels at ultra-high speed. Thus, we present novel multiplier architectures, which take advantage of large plasmonic-based counters to reduce the number of cells and logic levels in the partial product reduction step of the multiplication. Our experimental results show that 3 levels and 30 counters are needed when 27-input cells are used. On the other side, 6 levels and 72 counters are employed with 9-input cells. Finally, we present various 16 × 16 multiplier implementations mixing 9- and 27-input cells, focusing on the trade-off in the number of counters, levels, and area of each architecture.

Logic synthesis is a fundamental step in the realization of modern integrated circuits. It has traditionally been employed for the optimization of CMOS-based designs, as well as for emerging technologies and quantum computing. Recently, it found application in minimizing the number of AND gates in cryptography benchmarks represented as xor-and graphs (XAGs). The number of AND gates in an XAG, which is called the logic network's multiplicative complexity, plays a critical role in various cryptography and security protocols such as fully homomorphic encryption (FHE) and secure multi-party computation (MPC). Further, the number of AND gates is also important to assess the degree of vulnerability of a Boolean function, and influences the cost of techniques to protect against side-channel attacks. However, so far a complete logic synthesis flow for reducing the multiplicative complexity in logic networks did not exist or relied heavily on manual manipulations. In this paper, we present a logic synthesis toolbox for cryptography and security applications. The proposed tool consists of powerful transformations, namely resubstitution, refactoring, and rewriting, specifically designed to minimize the multiplicative complexity of an XAG. Our flow is fully automatic and achieves significant results over both EPFL benchmarks and cryptography circuits. We improve the best-known results for cryptography up to 59%, resulting in a normalized geometric mean of 0.82.

Multi-ion potentiometric sensing becomes challenging for mixed-ion samples in which interfering electrolytes significantly alter the response of each single sensor. Therefore, an emulator based on the phase-boundary potential model is proposed to simulate multi-ion sensing in presence of interference. It serves as investigation tool for understanding the impact of sensor selectivity and interferent ions in the sensor response. Moreover, the emulator is used to design mixed-ion synthetic dataset, following a multi-factorial design of ion mixtures with orthogonal arrays. Such large dataset is suitable for data-intensive learning algorithms used in multivariate calibration of potentiometric sensor arrays.

This work targets fault-tolerant quantum computing and focuses on the problem of mapping reversible circuits into the Clifford+T quantum gate library. We present an automatically-generated database containing minimal-cost quantum circuits for Boolean functions up to 5 inputs. The database contains three circuits for each spectral-equivalent class representative, which are respectively optimized for the T-count, the T-depth, and the number of qubits. We show that any Boolean function can be derived from the implementation of its class representative without increasing any of the stated cost functions.

The articles in this month’s special issue provide insight into future computing technologies such as novel architectures, spintronic memories, and quantum computing.

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.

Exact synthesis is a versatile logic synthesis technique with applications to logic optimization, technology mapping, synthesis for emerging technologies, and cryptography. In recent years, advances in SAT solving have led to a heightened research effort into SAT-based exact synthesis. Advantages of exact synthesis include the use of various constraints (e.g., synthesis of emerging technology circuits). However, although progress has been made, its runtime remains unpredictable. This paper identifies two key points as hurdles to further progress. First, there are open questions regarding the design and implementation of exact synthesis systems, due to the many degrees of freedom. For example, there are different CNF encodings, different symmetry breaks to choose from, and different encodings may be suitable for different domains. Second, SAT-based exact synthesis is difficult to parallelize. Indeed, this is a common drawback of logic synthesis algorithms. This paper proposes four ways to close some open questions and to reduce runtime: 1) quantifying differences between CNF encoding schemes and their impacts on runtime; 2) demonstrating impact of symmetry breaking constraints; 3) showing how directed acyclic graph topology information can be used to decrease runtime; and 4) showing how topology information can be used to leverage parallelism.

In this paper, we present a structural rewriting method for a recently proposed XOR-Majority graph (XMG), which has exclusive-OR (XOR), majority-of-three (MAJ), and inverters as primitives. XMGs are an extension of Majority-Inverter Graphs (MIGs). Previous work presented an axiomatic system, Ω, and its derived transformation rules for manipulation of MIGs. By additionally introducing XOR primitive, the identities of MAJ-XOR operations should be exploited to enable powerful logic rewriting in XMGs. We first proposed two MAJ-XOR identities and exploit its potential optimization opportunities during structural rewriting. Then, we discuss the rewriting rules that can be used for different operations. Finally, we also address structural XOR detection problem in MIG. The experimental results on EPFL benchmark suites show that the proposed method can optimize the size/depth product of XMGs and its mapped look-up tables (LUTs), which in turn benefits the quantum circuit synthesis that using XMG as the underlying logic representations.

This paper proposes a novel methodology for multi-level logic synthesis that is independent from a specific graph data-structure, but formulates synthesis procedures using an abstract concept definition of a logic representation. The idea is to capture the essence of optimisations in a general manner and tailor only small performance-critical sections to the underlying logic representation. This generic, yet scalable approach, saves many man-months of development time and enables logic synthesis and technology-mapping procedures parameterised in a logic representation. We present the generic design methodology and demonstrate its practicality by providing a complete state-of-the-art logic synthesis flow.

Reducing the number of AND gates plays a central role in many cryptography and security applications. We propose a logic synthesis algorithm and tool to minimize the number of AND gates in a logic network composed of AND, XOR, and inverter gates. Our approach is fully automatic and exploits cut enumeration algorithms to explore optimization potentials in local subcircuits. The experimental results show that our approach can reduce the number of AND gates by 34% on average compared to generic size optimization algorithms. Further, we are able to reduce the number of AND gates up to 76% in best-known benchmarks from the cryptography community.

Quantum memory management is becoming a pressing problem, especially given the recent research effort to develop new and more complex quantum algorithms. The only existing automatic method for quantum states clean-up relies on the availability of many extra resources. In this work, we propose an automatic tool for quantum memory management. We show how this problem exactly matches the reversible pebbling game. Based on that, we develop a SAT-based algorithm that returns a valid clean-up strategy, taking the limitations of the quantum hardware into account. The developed tool empowers the designer with the flexibility required to explore the trade-off between memory resources and number of operations. We present two show-cases to prove the validity of our approach. First, we apply the algorithm to straight-line programs, widely used in cryptographic applications. Second, we perform a comparison with the existing approach, showing an average improvement of 52.77%.

The paper presents a generalization of DAG-aware AIG rewriting for k-feasible Boolean networks, whose nodes are k-input lookup tables (k-LUTs). We introduce a high-effort DAG-aware rewriting algorithm, called cut rewriting, which uses exact synthesis to compute replacements on the fly, with support for Boolean don't cares. Cut rewriting pre-computes a large number of possible replacement candidates, but instead of eagerly rewriting the Boolean network, stores the replacements in a conflict graph. Heuristic optimization is used to derive a best, maximal subset of replacements that can be simultaneously applied to the Boolean network from the conflict graph. We optimize LUT mapped Boolean networks obtained from the ISCAS and EPFL combinational benchmark suites. For 3-LUT networks, experiments show that we achieve an average size improvement of 5.58% and up to 40.19% after state-of-the-art Boolean rewriting techniques were applied until saturation. Similarly, for 4-LUT networks, we obtain an average improvement of 4.04% and up to 12.60%.

In this paper we consider the compilation of quantum state permutations into quantum gates for physical quantum computers. A sequence of generic single-target gates, which realize the input permutation, are extracted using a decomposition based reversible logic synthesis algorithm. We present a compilation algorithm that translates single-target gates into a quantum circuit composed of the elementary quantum gate sets that are supported by IBM's 5-qubit and 16-qubit, and Rigetti's 8-qubit and 19-qubit superconducting transmon QPUs. Compared to generic state-of-the-art compilation techniques, our technique improves gate volume and gate depth by up to 59% and 53%, respectively.

With the continuous push to improve Quality of Results (QoR) in EDA, Boolean methods in logic synthesis have been recently drawing the attention of researchers. Boolean methods achieve better QoR than algebraic methods but require higher computational cost. In this paper, we introduce the Scalable Boolean Method (SBM) framework. The SBM consists of 4 optimization engines designed to be scalable in a modern synthesis flow. The first presented engine is a generalized resubstitution framework based on computing, and implementing, the Boolean difference between two nodes. The second consists of a gradient-based AIG optimization, while the third one is based on heterogeneous elimination for kerneling. The last proposed engine is a revisiting of maximum set of permissible functions computation with BDDs. Altogether, the SBM framework enables significant synthesis results. We improve 12 of the best known area results in the EPFL synthesis competition. Embedded in a commercial EDA flow, the new Boolean methods enable -2.20% combinational area savings and -5.99% total negative slack reduction, after physical implementation, at contained runtime cost.

We present a constructive method to create quantum circuits that implement oracles |x〉|y〉|0〉k→|x〉|y⊕f(x)〉|0〉kfor n-variable Boolean functions f with low T-count. In our method f is given as a 2-regular Boolean logic network over the gate basis {∧, ⊕, 1}. Our construction leads to circuits with a T-count that is at most four times the number of AND nodes in the network. In addition, we propose a SAT-based method that allows us to trade qubits for T gates, and explore the space/complexity trade-off of quantum circuits. Our constructive method suggests a new upper bound for the number of T gates and ancilla qubits based on the multiplicative complexity c∧(f) of the oracle function f, which is the minimum number of AND gates that is required to realize f over the gate basis {∧, ⊕, 1}. There exists a quantum circuit computing f with at most 4c∧(f)T gates using k=c∧(f) ancillae. Results known for the multiplicative complexity of Boolean functions can be transferred. We verify our method by comparing it to different state-of-the-art compilers. Finally, we present our synthesis results for Boolean functions used in quantum cryptoanalysis.

Recent studies show that majority-based logic synthesis is beneficial for both traditional and nanotechnology digital designs. However, most of the existing synthesis algorithms for majority logic generate majority-of-three (M3) networks. The optimization opportunity for majority logic by using an arbitrary number of odd inputs still requires a large research effort. In this paper, we present an exact synthesis approach for computing Boolean functions in majority-of-five (M5) forms with a minimum number of operations using Boolean satisfiability. By exploiting the symmetry properties of majority operators, we make use of symbolic encoding method to represent the node functionality and to reduce the number of variables. Moreover, we represent the M5forms by M5-inverter graphs (M5IGs) for manipulation, which is an extension of majority-inverter graphs (MIGs). The experimental results on EPFL benchmark suites indicate the proposed method achieves 10.4% improvement on size and 11.4% on depth compared to the state-of-the-art exact synthesis method.

In this work, a complete study is carried out for the optimised, direct and catalyst-free growth of vertically-stacked graphene-based structures targeting at improved performance drug monitoring. The nanostructures, ultimately forming a honeycomb network on the substrate, are fabricated by the implementation and comparison of seven combinations of growth conditions on both Si and SiO2substrates. Pivotal features characterising the nanostructures i.e. layer thickness, sheet resistance, surface morphology and sensing performance are considered for verifying the quality and properties of the resulted graphene-based electrodes. The graphene-based sensing platform demonstrating optimum structural and electrochemical performance is finally implemented for drug screening showing high efficiency for the detection of a chemotherapeutic compound at low concentrations.

The future of computing is at crossroads. The technological advances that have sustained the exponential growth of computing performance over the last several decades are slowing and the roadmap for future advances is uncertain. The phenomenal expansion of computing power has made computers ubiquitous, spawned a $300 billion semiconductor industry, enabled unprecedented global economic growth, and transformed many aspects of society at large. Emerging technologies are placing an ever-growing and changing demand on computing, especially the profusion of data from the Internet of Things, large-scale scientific experiments (high-energy physics, astronomy, and genomics), autonomous vehicles, social media (including video), national security systems, and the finance sector. Transmitting, storing, processing, and analyzing this data explosion with the requisite speed and performance—and enabling significant processing and analysis to occur locally or at network nodes (i.e., edge computing)—may require a radical departure from the traditional computing paradigm of von Neumann computing architectures running on CMOS-based digital logic. New paradigms will likely require a range of new devices, software, design and simulation tools, and benchmarking, and may ultimately require rethinking the tasks that computing machines undertake. Recently, government, industry, and academia collectively have recognized that the future of computing requires a new, multidisciplinary research and development agenda.

Logic synthesis is an enabling technology to realize integrated computing systems, and it entails solving computationally intractable problems through a plurality of heuristic techniques. A recent push toward further formalization of synthesis problems has shown to be very useful toward both attempting to solve some logic problems exactly-which is computationally possible for instances of limited size today-as well as creating new and more powerful heuristics based on problem decomposition. Moreover, technological advances including nanodevices, optical computing, and quantum and quantum cellular computing require new and specific synthesis flows to assess feasibility and scalability. This review highlights recent progress in logic synthesis and optimization, describing models, data structures, and algorithms, with specific emphasis on both design quality and emerging technologies. Example applications and results of novel techniques to established and emerging technologies are reported.

We consider the problem of decomposing monotone Boolean functions into majority-of-three operations, with a particular focus on decomposing the majority-$n$n function. When targeting monotone Boolean functions, Shannon's expansion can be expressed by a single majority-of-three operation. We exploit this property to transform binary decision diagrams (BDDs) for monotone functions into majority-inverter graphs (MIGs), using a simple one-to-one mapping. This process highlights desirable properties for further majority graph optimization, e.g., symmetries between the inputs of primitive operations, which are not apparent from BDDs. Although our construction yields a quadratic upper bound on the number of majority-3 operations required to realize majority-$n$n, for small $n$n the concrete values are much smaller compared to those obtained from previous constructions which have linear and quasi-linear asymptotic upper bounds. Further, we demonstrate that minimum size MIGs, for the monotone functions majority-5 and majority-7, can be obtained applying a small number of algebraic transformations to the BDD.

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.

Here, we review the most recent developments in the field of 2-D electronics. We focus first on the synthesis of 2-D materials, discussing the different growth techniques currently available and assessing their strengths and weaknesses. Moreover, we describe a possible roadmap to enable CMOS compatible integration of 2-D materials. We then shift our attention to 2-D devices and circuits and review the state of the art. Among the plethora of device concepts, we look closely at 2-D tunnel FETs (TFETs) and negative-capacitance FETs (NC-FETs) for low-power applications. We also put a particular emphasis on doping-free polarity-controllable systems that use electrostatic doping to eliminate the need for physical or chemical doping. We conclude with an analysis of simulations of scaled devices and discuss the possibilities enabled at circuit level by 2-D electronics.

In this paper, we developed a simulation-based architecture evaluation framework for field-programmable gate arrays (FPGAs), called FPGA-SPICE, which enables automatic layout-level estimation and electrical simulations of FPGA architectures. FPGA-SPICE can automatically generate Verilog and SPICE netlists based on realistic FPGA configurations and a high-level eTtensible Markup Language-based FPGA architectural description language. The outputted Verilog netlists can be used to generate layouts of full FPGA fabrics through a semicustom design flow. SPICE simulation decks can be generated at three levels of complexity, namely, full-chip-level, grid-level, and component-level, providing different tradeoff between accuracy and simulation time. In order to enable such level of analysis, we presented two SPICE netlist partitioning techniques: loads extraction and parasitic net activity estimation. Electrical simulations showed that averaged over the selected benchmarks, the grid-/component-level approach can achieve 6.1×/7.5× execution speed-up with 9.9%/8.3% accuracy loss, respectively, compared to the full-chip level simulation. FPGA-SPICE was showcased through three different case studies: (1) an area breakdown analysis for static random access memory-based FPGAs, showing that configuration memories are a dominant factor; (2) a power breakdown comparison to analytical models, analyzing the source of accuracy loss; and (3) a robustness evaluation against process corners, studying their impact on energy consumption of full FPGA fabrics.

Typical operators for the decomposition of Boolean functions in state-of-the-art algorithms are AND, exclusive-OR (XOR), and a 2-to-1 multiplexer (MUX). We propose a logic decomposition algorithm that uses the majority-of-three (MAJ) operation. Such decomposition can extend the capabilities of current logic decomposition, but only found limited attention in previous work. Our algorithm makes 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 (i) exact synthesis aware rewriting, (ii) pre-optimization for 6-LUT mapping, and (iii) synthesis of quantum networks. An experimental evaluation shows that our algorithm leads to better XMGs compared to state-of-the-art algorithms, which positively affect all these three applications. As one example, our experiments show that the proposed method achieves up to 37.1% with a average of 9.6% reduction on the look-up tables (LUT) size/depth product applied to the EPFL arithmetic benchmarks after technology mapping.

Currently, there is a large research interest and a significant economical effort to build the first practical quantum computer. Such quantum computers promise to exceed the capabilities of conventional computers in fields such as computational chemistry, machine learning and cryptanalysis. Automated methods to map logic designs to quantum networks are crucial to fully realizing this dream, however, existing methods can be expensive both in computational time as well as in the size of the resultant quantum networks. This work introduces an efficient method to map reversible single-target gates into a universal set of quantum gates (Clifford+T). This mapping method is called best-fit mapping and aims at reducing the cost of the resulting quantum network. It exploits fc-LUT mapping and the existence of clean ancilla qubits to decompose a large single-target gate into a set of smaller single-target gates. In addition this work proposes a post-synthesis optimization method to reduce the cost of the final quantum network, based on two cost-minimization properties. Results show a cost reduction for the synthesized EPFL benchmark up to 53% in the number T gates.

SAT based exact synthesis is a powerful technique, with applications in logic optimization, technology mapping, and synthesis for emerging technologies. However, its runtime behavior can be unpredictable and slow. In this paper, we propose to add a new type of constraint based on families of DAG topologies. Such families restrict the search space considerably and let us partition the synthesis problem in a natural way. Our approach shows significant reductions in runtime as compared to state-of-the-art implementations, by up to 63.43%. Moreover, our implementation has significantly fewer timeouts compared to baseline and reference implementations, and reduces this number by up to 61%. In fact, our topology based implementation dominates the others with respect to the number of solved instances: given a runtime bound, it solves at least as many instances as any other implementation.

Design flows are the explicit combinations of design transformations, primarily involved in synthesis, placement and routing processes, to accomplish the design of Integrated Circuits (ICs) and System-on-Chip (SoC). Mostly, the flows are developed based on the knowledge of the experts. However, due to the large search space of design flows and the increasing design complexity, developing Intellectual Property (IP)-specific synthesis flows providing high Quality of Result (QoR) is extremely challenging. This work presents a fully autonomous framework that artificially produces design-specific synthesis flows without human guidance and baseline flows, using Convolutional Neural Network (CNN). The demonstrations are made by successfully designing logic synthesis flows of three large scaled designs.

In electronic design automation Boolean resynthesis techniques are increasingly used to improve the quality of results where algebraic methods hit local minima. Boolean methods rely on complete functional properties of a logic circuit, preferably including don't care information. Computationally expensive engines such as truth tables, SAT and binary decision diagrams are required to gather such properties. The choice of the engine determines the scalability of Boolean resynthesis. In this paper, we present improvements to Boolean resynthesis, enabling more optimization opportunities to be found at the same or smaller runtime cost as compared to state-of-the-art methods. Our contributions include (i) a theory of Boolean filtering to drastically reduce the number of gates processed and still retain all possible optimization opportunities, (ii) a weaker notion of maximum set of permissible functions, which can be computed efficiently via truth tables, (iii) a generalized refactoring engine that supports multiple representation forms, and (iv) a practical Boolean resynthesis flow, which combines the techniques proposed so far. Using our Boolean resynthesis on the EPFL benchmarks, we improve 10 of the best known area results in the synthesis competition. Embedded in a commercial EDA flow for ASICs, the Boolean resynthesis flow reduces the area by -2.67% and total negative slack by -5.48%, after physical implementation, at negligible runtime cost.

As scaling of conventional silicon-based electronics is reaching its ultimate limit, two-dimensional semiconducting materials of the transition-metal-dichalcogenides family, such as MoS2 and WSe2, are considered as viable candidates for next-generation electronic devices. Fully relying on electrostatic doping, polarity-controllable devices, that use additional gate terminals to modulate the Schottky barriers at source and drain, can strongly take advantages of 2D materials to achieve high on/off ratio and low leakage floor. Here, we provide an overview of the latest advances in 2D material processes and growth. Then, we report on the experimental demonstration of polarity-controllable devices fabricated on 2D-WSe2 and study the scaling trends of such devices using ballistic self-consistent quantum simulations. Finally, we discuss the circuit-level opportunities of such technology.

The majority function $\langle xyz\rangle$ evaluates to true, if at least two of its Boolean inputs evaluate to true. The majority function has frequently been studied as a central primitive in logic synthesis applications for many decades. Knuth refers to the majority function in the last volume of his seminal The Art of Computer Programming as “probably the most important ternary operation in the entire universe.” Majority logic sythesis has recently regained signficant interest in the design automation community due to nanoemerging technologies which operate based on the majority function. In addition, majority logic synthesis has successfully been employed in CMOS-based applications such as standard cell or FPGA mapping. This tutorial gives a broad introduction into the field of majority logic synthesis. It will review fundamental results and describe recent contributions from theory, practice, and applications.

The slowing down of Moore's law and the emergence of new technologies puts an increasing pressure on the field of EDA. There is a constant need to improve optimization algorithms. However, finding and implementing such algorithms is a difficult task, especially with the novel logic primitives and potentially unconventional requirements of emerging technologies. In this paper, we cast logic optimization as a deterministic Markov decision process (MDP). We then take advantage of recent advances in deep reinforcement learning to build a system that learns how to navigate this process. Our design has a number of desirable properties. It is autonomous because it learns automatically and does not require human intervention. It generalizes to large functions after training on small examples. Additionally, it intrinsically supports both single- and multi-output functions, without the need to handle special cases. Finally, it is generic because the same algorithm can be used to achieve different optimization objectives, e.g., size and depth.

Memristive biosensors have been proved as excellent candidates for ultrasensitive biosensing. In this work, a novel portable bio-detection system based on memristive biosensors is designed, developed and tested for providing a significantly fast, automatic and simultaneous sensing output of multiple memristive biosensors on a single chip. The suggested compact and independent bio-sensing prototype is achieved through the realization of an electronic board designed for addressing the specifications of the memristive biosensor signal acquisition. Memristive bio-sensing-chips are specially designed and fabricated as well. The system was tested for successfully sensing of Prostate Specific Antigen, one of the main biomarkers of prostate cancer, at fM concentrations. Overall, this novel scheme resembles to a memristive-biosensing-kit approach, paving the way for fast and ultrasensitive PoC (point-of-care) devices.

The broad application of NoCs in IC design has been enabled by NoC synthesis tools that evolved from university prototypes to full commercial synthesis flows. NoC embodiments are ubiquitously present in circuits and systems. As systems evolve to include new components and features, NoCs will play even a more important role as the smart connect that can enable heterogeneity. Thus this field will both evolve in diversity of implementations as well in the search of both higher performance and lower power solutions.

In this paper, we study exact multi-level logic benchmarks. We refer to an exact logic benchmark, or exact benchmark in short, as the optimal implementation of a given Boolean function, in terms of minimum number of logic levels and/or nodes. Exact benchmarks are of paramount importance to design automation because they allow engineers to test the efficiency of heuristic techniques used in practice. When dealing with two-level logic circuits, tools to generate exact benchmarks are available, e.g., espresso-exact, and scale up to relatively large size. However, when moving to modern multi-level logic circuits, the problem of deriving exact benchmarks is inherently more complex. Indeed, few solutions are known. In this paper, we present a scalable method to generate exact multi-level benchmarks with the optimum, or provably close to the optimum, number of logic levels. Our technique involves concepts from graph theory and joint support decomposition. Experimental results show an asymptotic exponential gap between state-of-the-art synthesis techniques and our exact results. Our findings underline the need for strong new research in logic synthesis.

Given a set of logic primitives and a Boolean function, exact synthesis finds the optimum representation (e.g., depth or size) of the function in terms of the primitives. Due to its high computational complexity, the use of exact synthesis is limited to small networks. Some logic rewriting algorithms use exact synthesis to replace small subnetworks by their optimum representations. However, conventional approaches have two major drawbacks. First, their scalability is limited, as Boolean functions are enumerated to precompute their optimum representations. Second, the strategies used to replace subnetworks are not satisfactory. We show how the use of exact synthesis for logic rewriting can be improved. To this end, we propose a novel method that includes various improvements over conventional approaches: (i) we improve the subnetwork selection strategy, (ii) we show how enumeration can be avoided, allowing our method to scale to larger subnetworks, and (iii) we introduce XOR Majority Graphs (XMGs) as compact logic representations that make exact synthesis more efficient. We show a 45.8% geometric mean reduction (taken over size, depth, and switching activity), a 6.5% size reduction, and depth · size reductions of 8.6%, compared to the academic state-of-the-art. Finally, we outperform 3 over 9 of the best known size results for the EPFL benchmark suite, reducing size by up to 11.5% and depth up to 46.7%.

Today's rapid advances in the physical implementation of quantum computers demand for scalable synthesis methods in order to map practical logic designs to quantum architectures. We present a synthesis algorithm for quantum computing based on k-LUT networks, which can be derived from Verilog netlists using state-of-the-art and off-the-shelf mapping algorithms. We demonstrate the effectiveness of our method in automatically synthesizing several floating point networks up to double precision. As many quantum algorithms target scientific simulation applications, they can make rich use of floating point arithmetic components. But due to the lack of quantum circuit descriptions for those components, it is not possible to find a realistic cost estimation for the algorithms. Our synthesized benchmarks provide cost estimates that allow quantum algorithm designers to provide the first complete cost estimates for a host of quantum algorithms. This is an essential step towards the goal of understanding which quantum algorithms will be practical in the first generations of quantum computers.

3D ultrasound, an emerging medical imaging technique that is presently only used in hospitals, has the potential to enable breakthrough telemedicine applications, provided that its cost and power dissipation can be minimized. In this paper, we present an FPGA architecture suitable for a portable medical 3D ultrasound device. We show an optimized design for the digital part of the imager, including the delay calculation block, which is its most critical part. Our computationally efficient approach requires a single FPGA for 3D imaging, which is unprecedented. The design is scalable; a configuration supporting a 32×32-channel probe, which enables high-quality imaging, consumes only about 5W.

Resistive Random Access Memory (RRAM) is a promising non-volatile memory technology which enables modern in-memory computing architectures. Although RRAMs are known to be superior to conventional memories in many aspects, they suffer from a low write endurance. In this paper, we focus on balancing memory write traffic as a solution to extend the lifetime of resistive crossbar architectures. As a case study, we monitor the write traffic in a Programmable Logic-in-Memory (PLiM) architecture, and propose an endurance management scheme for it. The proposed endurance-aware compilation is capable of handling different trade-offs between write balance, latency, and area of the resulting PLiM implementations. Experimental evaluations on a set of benchmarks including large arithmetic and control functions show that the standard deviation of writes can be reduced by 86.65% on average compared to a naive compiler, while the average number of instructions and RRAM devices also decreases by 36.45% and 13.67%, respectively.

Boolean SAT solving can be used to find a minimum-size logic network for a given small Boolean function. This paper extends the SAT formulation to find a minimum-size network under delay constraints. Delay constraints are given in terms of input arrival times and the maximum depth. After integration into a depth-optimizing mapping algorithm, the proposed SAT formulation can be used to perform logic rewriting to reduce the logic depth of a network. It is shown that to be effective the logic rewriting algorithm requires (i) a fast SAT formulation and (ii) heuristics to quickly determine whether the given delay constraints are feasible for a given function. The proposed algorithm is more versatile than previous algorithms, which is confirmed by the experimental results.

A major hurdle to the deployment of quantum linear systems algorithms and recent quantum simulation algorithms lies in the difficulty to find inexpensive reversible circuits for arithmetic using existing hand coded methods. Motivated by recent advances in reversible logic synthesis, we synthesize arithmetic circuits using classical design automation flows and tools. The combination of classical and reversible logic synthesis enables the automatic design of large components in reversible logic starting from well-known hardware description languages such as Verilog. As a prototype example for our approach we automatically generate high quality networks for the reciprocal 1/x, which is necessary for quantum linear systems algorithms.

The performance of some emerging nanotechnologies benefits from wave pipelining. The design of such circuits requires new models and algorithms. Thus we show how Majority-Inverter Graphs (MIG) can be used for this purpose and we extend the related optimization algorithms. The resulting designs have increased throughput, something that has traditionally been a weak point for the majority of non-charge-based technologies. We benchmark the algorithm on MIG netlists with three different technologies, Spin Wave Devices (SWD), Quantum-dot Cellular Automata (QCA), and NanoMagnetic Logic (NML). We find that the wave pipelined version of the netlists have an improvement in throughput over power of 23×, 13×, and 5× for SWD, QCA, and NML, respectively. In terms of throughput over area ratio, the improvement is 5×, 8×, and 3×, respectively.

Hard-wired carry chains in FPGAs are designed to improve efficiency of important arithmetic primitives. Although they are proven to be effective for arithmetic-rich functions, there are very few studies on the optimization opportunities of carry chains for general logic that is poor in arithmetic operations. Recently, Majority-Inverter Graphs (MIGs) were proposed for efficient Boolean logic optimization. MIGs open an opportunity for efficient mapping of critical paths onto hard carry chains, as the carry logic of a full adder is naturally a majority (MAJ) gate. In this paper, we propose an MIG-based synthesis method to exploit hard adders in FPGAs for the mapping of general logic. The proposed heuristic algorithm selects MAJ nodes to be mapped on the carry chains and the associated LUTs; then, the efficiency of carry chain mapping is examined theoretically for efficient LUT utilization. The experimental results show that, compared to traditional design flow Verilog-to-Routing (VTR 7.0), the proposed approach can improve delay by up to 25% with an average of 8%, while the channel width is reduced by up to 20% with an average of 6%.

Given (i) a Boolean function, (ii) a set of arrival times at the inputs, and (iii) a gate library with associated delay values, the exact delay synthesis problem asks for a circuit implementation which minimizes the arrival time at the output(s). The exact delay synthesis problem, with given input arrival times, relates to computing the communication complexity of a Boolean function, which is an intractable problem. Input arrival times are variable and can take any value, thereby making the exact delay synthesis search space infinite. This paper presents theory and algorithms for exact delay synthesis. We introduce the theory of equioptimizable arrival times, which allows us to partition all arrival time patterns into a finite set of equivalence classes. Thanks to this new theory, we create for the first time exact delay circuit databases covering all Boolean functions up to 5 variables and all possible arrival time patterns. We describe further arrival time compression techniques which enable the creation of larger databases. We propose an enhanced delay synthesis flow capable of dealing with large circuits, combining exact delay logic rewriting and Boolean optimization techniques, attaining unprecedented results. We improve 9/10 of the best known results in the EPFL arithmetic delay synthesis competition, outperforming previous best results up to 3x. Embedded in a commercial EDA flow for ASICs, our exact delay synthesis techniques reduce the total negative slack by 12.17%, after physical implementation, at negligible area and runtime costs.

Reducing sensing time is one major concern in clinical diagnostics. In the present work, a robust measurement system is developed aiming at the faster and easier signal acquisition of memristive biosensors. Sensing chips consisting of nanofabricated silicon wires exhibiting memristive electrical response and metallic extension electrodes allowing an integrated measurement procedure are designed and fabricated. Furthermore, the electrical response of these particular nanofabricated structures is for the first time acquired using an embedded-system-based measurement front-end. The suggested prototype significantly simplifies the measurement procedure and provides conveniently the response signal of the devices. Such optimized co-design of memristive biosensors with electronic platforms hold great promise for PoC (point-of-care) applications.

In-memory computing devices, such as resistive RAMs, natively implement material implication or a variant of the majority-of-three operation called RM3. This operation generalizes material implication and has been used as target operation in several logic synthesis algorithms for in-memory computing applications. In this work, we investigate a homogeneous logic network data structure that uses RM3as only logic operation. Such a data structure makes an ideal fit for the use in design automation algorithms for in-memory computing. We show how to derive RM3networks from well-known logic synthesis data structures and a technique how to obtain such networks using technology mapping.

Resistive Random Access Memory(RRAM) technology opens the opportunity for granting both high-performance and low-power features to routing multiplexers. In this paper, we study the physical design considerations related to RRAM-based routing multiplexers and particularly the integration of 4T(ransistor)1R(RAM) programming structures within their routing tree. We first analyze the limitations in the physical design of a naive one-level 4T1R-based multiplexer, such as co-integration of low-voltage nominal power supply and high voltage programming supply, as well as the use of long metal wires across different isolating wells. To address the limitations, we improve the one-level 4T1R-based multiplexer by re-arranging the nominal and programming voltage domains, and also study the optimal location of RRAMs in terms of performance. The improved design can effectively reduce the length of long metal wires by 50%. Electrical simulations show that using a 7nm FinFET transistor technology, the improved 4T1R-based multiplexers improve delay by 69% as compared to the basic design. At nominal working voltage, considering an input size ranging from 2 to 32, the improved 4T1R-based multiplexers outperform the best CMOS multiplexers in area by 1.4x, delay by 2x and power by 2x respectively. The improved 4T1R-based multiplexers operating at near-Vt regime can improve Power-Delay Product by up to 5.8x when compare to the best CMOS multiplexers working at nominal voltage.

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.

We study the logic synthesis of emerging nanotechnologies whose elementary devices abstraction is a majority voter. We argue that synthesis tools, natively supporting the majority logic abstraction, are the technology enablers. This is because they allow designers to validate majority-based nanotechnologies on large-scale benchmarks. We describe models and data-structures for logic design with majority-based nanotechnologies and we show results of applying new synthesis algorithms and tools. We conclude that new logic synthesis methods are required to achieve a fair assessment on emerging nanotechnologies.

Resistive memories have gained high research attention for enabling design of in-memory computing circuits and systems. We propose for the first time an automatic compilation methodology suited to a recently proposed computer architecture solely based on resistive memory arrays. Our approach uses Majority-Inverter Graphs (MIGs) to manage the computational operations. In order to obtain a performance and resource efficient program, we employ optimization techniques both to the underlying MIG as well as to the compilation procedure itself. In addition, our proposed approach optimizes the program with respect to memory endurance constraints which is of particular importance for in-memory computing architectures.

Reconfigurable systems employ highly-routable local routing architecture to interconnect generic fine-grain logic blocks. Commercial FPGAs employ 50% sparse crossbars rather than fully-connected crossbars in their local routing architecture to trade off between the area and routability of the Logic Blocks (LBs). While the input crossbar provides good routability and logic equivalence for the inputs of the LB, the outputs of the LBs are typically assigned to a physical location. This lack of flexibility brings strong constraints to the global net router. Here, we propose a novel local routing architecture that guarantees full logic equivalence on all input and output pins of the LBs. First, we introduce full-capacity crossbars to interconnect the outputs of the fine-grain Logic Elements (LEs) to the output pins of the LBs. Second, in the local routing, we use a combination of fully-connected and full-capacity crossbars. The full-capacity crossbars are used for the feedback connections in place of the standard fully-connected crossbars to ensure a full routability while reducing the area footprint. Fully-connected crossbars are still employed for the input connections to maintain the logic equivalence of the inputs. As a result, the novel local routing architecture enhances the routability of the LB clusters without any area overhead. By granting the outputs with logic equivalence, the proposed local routing architecture unlocks the full optimization potential of FPGA routers. Architectural simulations show that without any modification on Verilog-to-Routing (VTR) tool suites, when a commercial FPGA architecture is considered and over a wide set of benchmarks, the novel local routing architecture can reduce 10% channel width and 11% routing area with 10% less area×delay×power on average. Therefore, the novel local routing architecture enhances the routability of FPGA, and brings opportunities in realizing larger implementations on a single FPGA chip.

Classifying functions according to some common properties into libraries of functions is an important step in many logic synthesis and technology mapping algorithms used in FPGA design flows. NPN classification is one of the frequently used classifications. Existing algorithms for NPN classification perform a sequence of steps to derive the resulting NPN class, but discard the intermediate results produced at the end of each step. The hierarchical method introduced in this paper uses the same sequence of steps, but it saves the intermediate results at each step and reuses them when classifying other functions. It is, on average, 3.7 times faster compared to a state-of-the-art non-hierarchical method, at the cost of a modest increase in memory needed to save the class hierarchy. The hierarchical approach enables a rapid exact NPN classification for functions up to 10 inputs-it exactly classifies one million 6-input functions in the same time as the heuristic state-of-the-art algorithm.

We present an efficient FPGA architecture suitable for a medical 3D ultrasound beamformer. We tackle the delay calculation bottleneck, which is the heart and the most critical part of the beamformer, by proposing a computationally efficient design that is able to perform volumetric real-time beamforming on a single-chip FPGA. The design has been demonstrated for a 32×32-channel receive probe, and we extrapolated the requirements of the architecture for 80×80 channels.

In medical diagnosis, ultrasound (US) imaging is one of the most common, safe, and powerful techniques. Volumetric (3D) US imaging, an emerging technique, is even more attractive than standard 2D imaging, as it allows for imaging without the local presence of a trained sonographer finely positioning the probe. This would be particularly useful in rescue operations, remote areas and developing countries. Unfortunately, present-day 3D imagers are expensive, bulky and power-hungry, confining them to hospitals. There is therefore a strong motivation to develop efficient electronics to enable a portable US platform that is small, cheap, and battery-operated. Beamforming (BF) is the most computationally expensive of 3D imaging. Both commercial [1] and research [2] imagers have dealt with the challenge by reducing the number of receive channels, hence simplifying the computation through the usage of far fewer elements. This comes at the cost of image quality, and the resulting machines are nonetheless still non-portable and expensive. In turn, the bottleneck of the BF process is the calculation of acoustic delays, which requires up to trillions of square roots per second. We propose a drastically more efficient architecture [3]. With geometric considerations, each delay is calculated from a small set of square roots (mapped onto CORDICs), plus two additions. In this demo, we will show the reconstruction of a 2.5M-voxel volume, supporting a transducer with 32×32 receive channels. We have fitted the architecture into a single Kintex UltraScale KU040 [4], which is unprecedented. We also extrapolated the utilization of a 80×80 instance on a Virtex UltraScale XCVU190 [4]. Table I shows the implementation results. Fig. 1 shows our beamformer custom block connected to the other FPGA subsystems. The delay calculation architecture is shown in Fig. 2. The demo setup is presented in Fig. 3, where the 3D beamformer is implemented on the FPGA, while the pre- and post-processing stages are currently performed on Matlab.

Lexicographic Boolean satisfiability (LEXSAT) is a variation of the Boolean satisfiability problem (SAT). Given a variable order, LEXSAT finds a satisfying assignment whose integer value under the given variable order is minimum (maximum) among all satisfiable assignments. If the formula has no satisfying assignments, LEXSAT proves it unsatisfiable, as does the traditional SAT. The paper proposes an efficient algorithm for LEXSAT by combining incremental SAT solving with binary search. It also proposes methods that use the lexicographic properties of the assignments to further improve the runtime when generating consecutive satisfying assignments in lexicographic order. The proposed algorithm outperforms the state-of-the-art LEXSAT algorithm—on average, it is 2.4 times faster when generating a single LEXSAT assignment, and it is 6.3 times faster when generating multiple consecutive assignments.

A fully-integrated differential biosensing platform on CMOS is presented for miniaturized enzyme-based electrochemical sensing. It enables sensor background current elimination and consists of a differential sensor array and a differential readout IC (DiRIC). The sensor array includes a four-electrode sensor for amperometric electrochemical sensing, as well as a differential ISFET-based pH sensor to calibrate the biosensors. The ISFET is biased in weak inversion and co-designed with DiRIC to enable pH measurements from 1 to 14 with resolution of 0.1 pH. DiRIC enables differential current measurement in the range of ±100 μA with more than 120dB dynamic range.

As metabolic pathways are highly variable among different patients, then an accurate and continuous monitoring of the personal response to drug treatments is essential especially with critical medications, e.g. anesthetic and anti-cancer cocktails. Currently, for anesthesia monitoring, there are no fully mature point-of-care bio-sensing systems. Indeed, it is still evaluated by mathematical models and with indirect parameters like Bispectral Index, which can not provide the actual concentration in blood. The aim of this paper is to investigate solutions for developing a portable system able to monitor simultaneously several different drugs. For this purpose, Cyclic Voltammetries with an anesthetic product and therapeutic compounds were performed for the validation of the system. A multichannel potentiostat has been realized with Off-The-Shelf Components (COTS). Then, results from electrochemical acquisitions on GC SPEs show that the proposed circuitry is suitable for this aim and they prove its high flexibility to develop portable systems for continuous monitoring of anesthetics and therapeutic compounds.

Integration of nanowire structures in more complex platforms combining microfluidics and multiplexing aspects may complex the electrical readout process. In the present work, fabrication of Aluminium (Al) lines for electrical connections is attempted followed by their integration to nanofabricated Memristive Biosensors that target at the label-free detection of cancer biomarkers. In addition a computational study is carried out investigating the impact of the resistance introduced by the additional Al connections to the electrical response of the Memristive Biosensors. Overall, the present study explores the restrictions and the possibilities of the Memristive Biosensors' integration with additional elements that would allow effective readout in more complex configurations.

Hardware security concerns such as intellectual property (IP) piracy and hardware Trojans have triggered research into circuit protection and malicious logic detection from various design perspectives. In this article, emerging technologies are investigated by leveraging their unique properties for applications in the hardware security domain. Security, for the first time, will be treated as one design metric for emerging nano-architecture. Five example circuit structures including camouflaging gates, polymorphic gates, current/voltage-based circuit protectors, and current-based XOR logic are designed to show the high efficiency of silicon nanowire FETs and graphene SymFET in applications such as circuit protection and IP piracy prevention. Simulation results indicate that highly efficient and secure circuit structures can be achieved via the use of non-CMOS devices.

This article first explores the effects of faults on circuits implemented with controllable-polarity transistors. We propose a new fault model that suits the characteristics of these devices, and we report the results of a SPICE-based analysis of the effects of faults on the behavior of some basic gates implemented with them. Hence, we show that the considered devices are able to intrinsically tolerate a rather high number of faults. We finally exploit this property to build a robust and scalable adder whose area, performance, and leakage power characteristics are improved by 15%, 18%, and 12%;, respectively, when compared to an equivalent FinFET solution at 22nm technology node.

Manipulating logic functions via majority operators recently drew the attention of researchers in computer science. For example, circuit optimization based on majority operators enables superior results as compared to traditional synthesis tools. Also, the Boolean satisfiability problem finds new solution approaches when described in terms of majority decisions. To support computer logic applications based on majority, a sound and complete set of axioms is required. Most of the recent advances in majority logic deal only with ternary majority (MAJ-3) operators because the axiomatization with solely MAJ-3 and complementation operators is well understood. However, it is of interest extending such axiomatization to$n$-ary majority operators (MAJ-$n$) from both the theoretical and practical perspective. In this work, we address this issue by introducing a sound and complete axiomatization of MAJ-$n$logic. Our axiomatization naturally includes existing MAJ-3 and MAJ-5 axiomatic systems. Based on this general set of axioms, computer applications can now fully exploit the expressive power of majority logic.

In this paper, we propose a paradigm shift in representing and optimizing logic by using only majority (MAJ) and inversion (INV) functions as basic operations. We represent logic functions by majority-inverter graph (MIG): a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. We optimize MIGs via a new Boolean algebra, based exclusively on majority and inversion operations, that we formally axiomatize in this paper. As a complement to MIG algebraic optimization, we develop powerful Boolean methods exploiting global properties of MIGs, such as bit-error masking. MIG algebraic and Boolean methods together attain very high optimization quality. Considering the set of IWLS'05 benchmarks, our MIG optimizer (MIGhty) enables a 7% depth reduction in LUT-6 circuits mapped by ABC while also reducing size and power activity, with respect to similar and-inverter graph (AIG) optimization. Focusing on arithmetic intensive benchmarks instead, MIGhty enables a 16% depth reduction in LUT-6 circuits mapped by ABC, again with respect to similar AIG optimization. Employed as front-end to a delay-critical 22-nm application-specified integrated circuit flow (logic synthesis + physical design) MIGhty reduces the average delay/area/power by 13%/4%/3%, respectively, over 31 academic and industrial benchmarks. We also demonstrate delay/area/power improvements by 10%/10%/5% for a commercial FPGA flow.

With the growing number of process variation (PV) sources in deeply nano-scaled technologies, parameterized device and circuit modeling is becoming very important for chip design and verification. However, the high dimensionality of parameter space, for PV analysis, is a serious modeling challenge for emerging VLSI technologies. These parameters correspond to various interdie and intradie variations, and considerably increase the difficulties of design validation. Today's response surface models and most commonly used parameter reduction methods, such as principal component analysis and independent component analysis, limit parameter reduction to linear or quadratic form and they do not address the higher order of nonlinearity among process and performance parameters. In this paper, we propose and validate a feature selection method to reduce the circuit modeling complexity associated with high parameter dimensionality. This method relies on a learning-based nonlinear sparse regression, and performs a parameter selection in the input space rather than creating a new space. This method is capable of dealing with mixed Gaussian and non-Gaussian parameters and results in a more precise parameter selection considering statistical nonlinear dependencies among input and output parameters. The application of this method is demonstrated in digital circuit timing analysis in both FinFET and Silicon Nanowire technologies. The results confirm the efficiency of this method to significantly reduce the number of required simulations while keeping estimation error small.

Multiple Independent Gate Field Effect Transistors (MIGFETs) are expected to push FET technology further into the semiconductor roadmap. In a MIGFET, supplementary gates either provide (i) enhanced conduction properties or (ii) more intelligent switching functions. In general, each additional gate also introduces a side implementation cost. To enable more efficient digital systems, MIGFETs must leverage their expressive power to realize complex logic circuits with few physical resources. Researchers face then the question: How many gates do we need? In this paper, we address the logic side of this question. We determine whether or not an increasing number of gates leads to more compact logic implementations. For this purpose, we develop a logic synthesis flow that intrinsically exploits a MIGFET switching function. Using simplified design assumptions and device/interconnect models, we synthesize MCNC benchmarks on 5 promising MIGFET devices, with number of gates ranging from 1 to 7. Experimental results evidence nontrivial area/delay/energy minima, located between 1 and 4 gates, depending on a MIGFET switching function and device/interconnect technology.

Nowadays, Field Programmable Gate Arrays (FPGA) exploit Look-Up Tables (LUTs) to generate logic functions. A K-input LUT can implement any Boolean functions with K inputs. Thanks to this flexibility, LUTs remained conceptually unchanged in FPGAs, only the number of inputs increased in time. Unfortunately, the flexibility does not come for free and LUTs have non-negligible costs in both circuit-level performances (large number of memories, area or delay penalties) and logic-level capabilities (limited fan-out). Here, we propose an FPGA fabric based on two novel logic blocks. First, we introduce a new LUT design showing reduced power consumption with no sacrifice in the logic flexibility. Then, we present a block suited to arithmetic functions but preserving enough versatility to implement general logic functions. The two blocks are supported by a recently introduced logic representation called Biconditional Binary Decision Diagrams (BBDDs). Using architectural-level benchmarking, we showed that an FPGA architecture exploiting the novel blocks performs significantly better than current state-of-the-art FPGA architectures at 40nm technological node over a large set of test circuits. While reducing the power consumption of MCNC big20 benchmarks by 29%, the proposed architecture is able to efficiently implement arithmetic circuits as compared to its traditional LUT-based FPGA counterpart. For instance, a 256-bit adder can be realized with a 43% gain in area×delay product. While considering large general and arithmetic logic benchmarks, we observe, on average, 4%, 3% and 10% improvements in area, delay and power respectively.

Resistive Random Access Memory (RRAM)-based FPGA architectures employ RRAMs not only as memories to store the configuration but embed them in the datapaths of programmable routing resources to propagate signals with improved performances. Sources of power consumption have been intensively studied for conventional Static Random Access Memories (SRAM)-based FPGAs. However, very limited works focused so far on studying the power characteristics of RRAM-based FPGAs. In this paper, we first analyze the power characteristics of RRAM-based multiplexer at circuit level and then use electrical simulations to study power consumption of RRAM-based FPGA architectures. Experimental results show that RRAM-based FPGAs achieve a Power-Delay Product reduced by 50% compared to SRAM-based FPGA at nominal voltage and 20% compared to near-VtSRAM-based FPGA, respectively.

As an answer to the new electronics market demands, semiconductor industry is looking for different materials, new process technologies and alternative design solutions that can support Silicon replacement in the VLSI domain. The recent introduction of graphene, together with the option of electrostatically controlling its doping profile, has shown a possible way to implement fast and power efficient Reconfigurable Gates (RGs). Also, and this is the most important feature considered in this work, those graphene RGs show higher expressive power, i.e., they implement more complex functions, like Majority, MUX, XOR, with less area w.r.t. CMOS counterparts. Unfortunately, state-of-the-art synthesis tools, which have been customized for standard NAND/NOR CMOS gates, do not exploit the aforementioned feature of graphene RGs.

Mainstream Field Programmable Gate Array (FPGA) power estimation tools are based on probabilistic activity estimation and analytical power models. The power consumption of the programmable resources of FPGAs is highly sensitive to their configurations. Due to their highly flexible nature, the configurations of FPGAs routing multiplexers or Look Up Tables (LUTs) are really different from a design to another but current analytical power models cannot accurately capture the associated power differences. In this paper, we introduce a simulation-based power estimation framework for FPGAs, called FPGA-SPICE, which supports any FPGA architecture that can be described with an architectural description language. Our power estimation engine automatically generates accurate SPICE netlists according to the FPGA configurations and enables precise power analysis of FPGA architectures. SPICE testbenches can be generated at different level of complexity, denoted as full-chip-level, grid-level and component-level testbenches. Full-chip-level testbenches dump the netlists associated with the complete FPGA fabric. To reduce simulation time, FPGA-SPICE can split the full-chip-level testbenches into grid-level testbenches, each of which consisting of a complete logic block netlist, or component-level testbenches, which consider individual circuit elements, i.e., multiplexers, LUTs, flip-flops, etc., separately. We show that the grid/component-level approach can achieve 14 × speed-up with a moderate 14% accuracy loss, compared to the full-chip level. We also use FPGA-SPICE to study the power characteristics of a commercial FPGA architecture at different technology nodes. Experimental results show that the global routing architecture consumes 50% of the total power, the local routing architecture claims for 40% of the total power, and the remaining 10% comes from the LUTs and flip-flops.

The development of fast and mobile drug detection is an important aspect of personalized medicine. It enables the quick assessment of inter-individual differences in drug metabolism and corresponding adjustments of the dose. Recent developments of amperometric biosensors using cytochrome P450 (CYP) show great promise, by lowering the detection limit to physiological range for several drugs via the usage of Multi Walled Carbon Nanotubes (MWCNT). The next challenge is to develop algorithms for processing the resulting sensor data compatible with low-power hardware, which would allow the development of portable battery-powered devices. In this work we pursue a novel approach to this problem. Here we provide a proof of principle by demonstrating how sensor data could be analyzed using a conventional multi-layer perceptron network with error-backpropagation.

A full remotely powered system for metabolism monitoring of free-moving mice is presented here. The fully implantable sensing platform hosts two ASICs, one off-the-shelf micro-controller, four biosensors, two other sensors, a coil to receive power, and an antenna to transmit data. Proper enzymes ensure specificity for animal metabolites while Multi-Walled Carbon Nanotubes ensure the due sensitivity. The remote powering is indeed provided by inductive coils located under the floor of the mouse' cage. Two different approaches where investigated to ensure freedom of movement to the animal. The application to studies for personalized medicine is demonstrated by showing continuous monitoring of both glucose and paracetamol.

Nowadays, power consumption is one of the main limitations of electronic systems. In this context, novel and emerging devices provide new opportunities to extend the trend toward low-power design. In this survey article, we present a transversal survey on energy-efficient techniques ranging from devices to architectures. The actual trends of device research, with fully depleted planar devices, tri-gate geometries, and gate-all-around structures, allows us to reach an increasingly higher level of performance while reducing the associated power. In addition, beyond the simple device property enhancements, emerging devices also lead to innovations at the circuit and architectural levels. In particular, devices whose properties can be tuned through additional terminals enable a fine and dynamic control of device threshold. They also enable designers to realize logic gates and to implement power-related techniques in a compact way unreachable to standard technologies. These innovations reduce power consumption at the gate level and unlock new means of actuation in architectural solutions like adaptive voltage and frequency scaling.

Nanoelectronics comprises a variety of devices whose electrical properties are more complex as compared to CMOS, thus enabling new computational paradigms. The potentially large space for innovation has to be explored in the search for technologies that can support large-scale and high-performance circuit design. Within this space, we analyze a set of emerging technologies characterized by a similar computational abstraction at the design level, i.e., a binary comparator or a majority voter. We demonstrate that new logic synthesis techniques, natively supporting this abstraction, are the technology enablers. We describe models and data-structures for logic design using emerging technologies and we show results of applying new synthesis algorithms and tools. We conclude that new logic synthesis methods are required to both evaluate emerging technologies and to achieve the best results in terms of area, power and performance.

As we advance into the era of nanotechnology, semiconductor devices are scaled down to their physical limits, thereby opening up venues for new transistor channel materials based on nanowires and nanotubes. Transistors based on nanowires and nanotubes inherently exhibit ambipolar behavior. While technologists aim to suppress ambipolar behavior of these transistors, new design methodologies are proposed by exploiting the phenomenon of controllable polarity. In this paper, we propose regular layout fabrics, with an emphasis on silicon nanowires (SiNWs) as the candidate technology. A double-gate ambipolar SiNW field-effect transistor operates as p-type or n-type by electrically controlling the polarity of the second gate. We propose layout techniques to address gate-level routing congestion, as every transistor has two gates to route. Novel symbolic layouts, which are technology independent, are proposed for ambipolar circuits. In the second part of this paper, we present an approach for designing an efficient regular layout called sea-of-tiles (SoTs). A logic tile is essentially an array of prefabricated transistor-pairs grouped together. We design four logic tiles, which form the basic building block of the SoT fabric. We run extensive comparisons of mapping standard benchmarks onto the SoT fabric to find the optimum tile. This paper shows that SoT with TileG2and TileG1h2, on an average, outperforms the one with TileG1by 16% and 14% in area utilization, respectively.

In this paper, we investigate the opportunity brought by controllable-polarity transistors to design efficient reconfigurable circuits. Controllable-polarity transistors are devices whose polarity can be electrostatically programmed to be either n- or p-type. Such devices are used to build ultrafine grain computation cells. These cells are arranged into regular matrices, called MClusters, with a fixed and incomplete interconnection pattern, employed to minimize the reconfigurable interconnection overhead. We subsequently use them into field-programmable gate arrays (FPGAs). To assess this architectural scheme in an efficient and objective manner, we present a complete benchmarking tool flow and focus on the packing algorithm developed to handle the architecture. We finally perform the evaluation with widely used benchmark circuits. Leveraging the ultrafine grain cells compactness from a system-level perspective, we show that FPGAs exploiting MClusters demonstrate average savings of 43% and 23% in area and delay, respectively, as compared with the CMOS lookup table FPGA counterpart at 22-nm technological node.

3-D integrated circuits (3-D ICs) offer a promising solution to overcome the scaling limitations of 2-D ICs. However, using too many through-silicon-vias (TSVs) pose a negative impact on 3-D ICs due to the large overhead of TSV (e.g., large footprint and low yield). In this paper, we propose a new TSV sharing method for a circuit-switched 3-D mesh-of-tree (MoT) interconnect, which supports high-throughput and lowlatency communication between processing cores and 3-D stacked multibanked L2 scratchpad memory. The proposed method supports traffic balancing and TSV-failure tolerant routing. The proposed method advocates a modular design strategy to allow stacking multiple identical memory dies without the need for different masks for dies at different levels in the memory stack. We also investigate various parameters of 3-D memory stacking (e.g., fabrication technology, TSV bonding technique, number of memory tiers, and TSV sharing scheme) that affect interconnect latency, system performance, and fabrication cost. Compared to conventional MoT interconnect [6] that is straightforwardly adapted to 3-D integration, the proposed method yields up to ×2.11 and ×1.11 improvements in terms of cost efficiency (i.e., performance/cost) for microbump TSV bonding and direct Cu-Cu TSV bonding techniques, respectively.

Nowadays, most software and hardware applications are committed to reduce the footprint and resource usage of data. In this general context, lossless data compression is a beneficial technique that encodes information using fewer (or at most equal number of) bits as compared to the original representation. A traditional compression flow consists of two phases: data decorrelation and entropy encoding. Data decorrelation, also called entropy reduction, aims at reducing the autocorrelation of the input data stream to be compressed in order to enhance the efficiency of entropy encoding. Entropy encoding reduces the size of the previously decorrelated data by using techniques such as Huffman coding, arithmetic coding, and others. When the data decorrelation is optimal, entropy encoding produces the strongest lossless compression possible. While efficient solutions for entropy encoding exist, data decorrelation is still a challenging problem limiting ultimate lossless compression opportunities. In this paper, we use logic synthesis to remove redundancy in binary data aiming to unlock the full potential of lossless compression. Embedded in a complete lossless compression flow, our logic synthesis based methodology is capable to identify the underlying function correlating a data set. Experimental results on data sets deriving from different causal processes show that the proposed approach achieves the highest compression ratio compared to state-of-art compression tools such as ZIP, bzip2 and 7zip.

Poor adherence to medical regimen causes approximately 33% to 69% of medication-related hospitalizations and accounts for $100 billion in annual health care costs. In this paper we address the problem of unintentional non adherence, when patient fails to take a medication due to forgetfulness or carelessness. We present the safe approach to software implementation of a portable reminder device with enabled personalization of medical regimen. The presented prototype is designed for imatinib administration, a drug used to treat Chronic Myeloid Leukemia (CML). However, thanks to the component-based structure of the software, the method can be applied to other cases by replacing implementation of certain components.

In this paper, we present Majority-Inverter Graph (MIG), a novel logic representation structure for efficient optimization of Boolean functions. An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. We show that MIGs include any AND/OR/Inverter Graphs (AOIGs), containing also the well-known AIGs. In order to support the natural manipulation of MIGs, we introduce a new Boolean algebra, based exclusively on majority and inverter operations, with a complete axiomatic system. Theoretical results show that it is possible to explore the entire MIG representation space by using only five primitive transformation rules. Such feature opens up a great opportunity for logic optimization and synthesis. We showcase the MIG potential by proposing a delay-oriented optimization technique. Experimental results over MCNC benchmarks show that MIG optimization reduces the number of logic levels by 18%, on average, with respect to AIG optimization performed by ABC academic tool. Employed in a traditional optimization-mapping circuit synthesis flow, MIG optimization enables an average reduction of {22%, 14%, 11%} in the estimated {delay, area, power} metrics, before physical design, as compared to academic/commercial synthesis flows.

Biconditional Binary Decision Diagrams (BBDDs) are a novel class of binary decision diagrams where the branching condition, and its associated logic expansion, is biconditional on two variables. Reduced and ordered BBDDs are remarkably compact and unique for a given Boolean function. In order to exploit BBDDs in Electronic Design Automation (EDA) applications, efficient manipulation algorithms must be developed and integrated in a software package. In this paper, we present the theory for efficient BBDD manipulation and its practical software implementation. The key features of the proposed approach are strong canonical form pre-conditioning of stored BBDD nodes, recursive formulation of Boolean operations in terms of biconditional expansions, performance-oriented memory management and dedicated BBDD re-ordering techniques. Experimental results show that the developed BBDD package achieves an average node count reduction of 19.48% and a speed-up factor of 1.63x with respect to a state-of-art decision diagram manipulation package. Employed in the synthesis of datapath circuits, the BBDD manipulation package is capable to advantageously restructure arithmetic operations producing 11.02% smaller and 32.29% faster circuits as compared to a commercial synthesis flow.

Crossroads have always been challenging: they require a decision; in Egyptian and Greek mythology they were often guarded by two sphinxes trying to cheat the traveler with their riddles. The two sphinxes, the knight and the knave, the lady and the tiger, are just few instances of difficult puzzles that have kept logicians and mathematicians busy for the last 5,000 years. Today, you are walking down Moore's Law road when you come to a crossroads: one road brings you into the land of emerging technologies: 14, 10 and 7 nanometer, FDSOI, FinFET, 3D-IC,… beyond and below; the other road holds you into the land of established technologies: 28, 40, 65, and 90 nanometers, possibly even above, A&M/S, MEMS,… Choosing the right road is critical to lead your project and your company to success, but making the right decision is increasingly difficult, as it encompasses complex technical and economic considerations. However, unlike the mythological traveler, you won't run into the sphinxes but, rather, into some of our industry best experts; unlike the sphinxes, they will strive to provide you with honest advice about the “road conditions”, and you are allowed to ask multiple questions to them to figure out which road is the best for you.

Field-Effect Transistors (FETs) with on-line controllable-polarity are promising candidates to support next generation System-on-Chip (SoC). Thanks to their enhanced functionality, controllable-polarity FETs enable a superior design of critical components in a SoC, such as processing units and memories, while also providing native solutions to control power consumption. In this paper, we present the efficient design of a SoC core with controllable-polarity FET. Processing units are speeded-up at the datapath level, as arithmetic operations require fewer physical resources than in standard CMOS. Power consumption is decreased via embedded power-gating techniques and tunable high-performance/low-power devices operation. Memory cells are made smaller by merging the access interface with the storage circuitry. We foresee the advantages deriving from these techniques, by evaluating their impact on the design of SoC for a contemporary telecommunication application. Using a 22-nm vertically-stacked silicon nanowire technology, a coarse-grain evaluation at the block level estimates a delay and power reduction of 20% and 19% respectively, at a cost of a moderate area overhead of 15%, with respect to a state-of-art FinFET technology.

Spin Wave Devices (SWDs) are promising beyond-CMOS candidates. Unlike traditional charge-based technologies, SWDs use spin as information carrier that propagates in waves. In this scenario, the logic primitive for computation is the majority gate. The majority gate has a greater expressive power than standard NAND/NOR gates, allowing SWD circuits to be more compact than CMOS, already at the logic level. Also, because there is not charge carrier transport, SWDs are estimated to have ultra-low power consumption. However, in order to exploit this opportunity, a native majority synthesis methodology is needed to fit the SWD technology needs. In this paper, we employ Majority-Inverter Graphs (MIGs) to naturally represent and synthesize SWD circuits. Thanks to the correspondence between the functionality of SWD primitive gates and MIG elements, MIG optimization intrinsically aims at minimum cost SWD implementations. Experimental results over MCNC benchmarks validate the efficiency of MIGs in SWD synthesis. As compared to traditional AND-Inverter Graph (AIG) synthesis, MIGs generate, on average, SWD circuits with 1.30X smaller area-delay-power product (ADP), improving their delay performance by 18%.

Nowadays, Field Programmable Gate Arrays (FPGA) implement arithmetic functions using specific circuits at the logic block level, such as the carry paths, or at the structure level adopting Digital Signal Processing (DSP) blocks. Nevertheless, all these approaches, introduced to ease the realization of specific functions, are lacking of generality. In this paper, we introduce a new logic block that natively realizes arithmetic functions while preserving the versatility to implement general logic functions. It consists of a partially interconnected matrix of signal routers driven by comparators. We demonstrate that this structure can realize (i) any 2-output 2-input logic function or (ii) any single-output 3-input logic function or (iii) specific logic, such as arithmetic functions, with up to 4-output and 8-inputs. As compared to a standard 6-input Look Up Table (LUT), the proposed block requires roughly the same area but is 35.3% faster. Even though the proposed block has not the same exhaustive configurability of a 6-input LUT, there are arithmetic functions realizable in a single block that do not fit in one, or even more, 6-input LUT. For example, a single block inherently implements an entire 3-bit adder that requires 3× more resources with LUTs plus also custom circuitry. From a system level perspective, we show that a 256-bit adder is implemented with a gain on area×delay product of 31% as compared to its traditional LUT-based counterpart.

In classical FPGA, LUTs and DFFs are pre-packed into BLEs and then BLEs are grouped into logic blocks. We propose a novel logic block architecture with fast combinational paths between LUTs, called pattern-based logic blocks. A new clustering algorithm is developed to release the potential of pattern-based logic blocks. Experimental results show that the novel architecture and the associated clustering algorithm lead to a 14% performance gain and a 8% wirelength reduction with a 3% area overhead compared to conventional architecture in large control-instensive benchmarks.

The routing architecture, heavily using programmable switches, dominates the area, delay and power of Field Programmable Gate Arrays (FPGAs). Resistive Random Access Memories (RRAMs) enable high-performance routing architectures through the replacement of Static Random Access Memory (SRAM)-based programming switches. Exploiting the very low on-resistance state achievable by RRAMs, RRAM-based routing multiplexers can be used to significantly reduce the FPGA routing delays. In addition, RRAM-based routing architectures are less sensitive to supply voltage reductions and show promises in low-power FPGA designs. In this paper, we propose a near-Vt low-power RRAM-based FPGA where both delay and power reductions are achieved. Experimental results demonstrate that a near-Vi RRAM-based FPGA design leads to a 15% area shrink, a 10% delay reduction, and a 65% power improvement, compared to a conventional FPGA design for a given technology node. To achieve low on-resistance values, RRAMs typically require high programming currents. In other word, they need relatively large programming transistors, potentially resulting in area, delay and power inefficiencies. We also present a design methodology to properly size the programming transistors of RRAMs in order to further improve the area-efficiency. Experimental results show that a correct programming transistor sizing strategy contributes to further 18% area and 2% delay shrink, compared to the initial near-Vi RRAM-based FPGA.

State-of-the-art techniques for measuring and monitoring gene level expression rely on messenger RNA (mRNA) extraction and quantification, usually based on the concept of reverse transcription polymerase chain reaction. In this paper, we take advantage of capabilities of image segmentation algorithms for monitoring target cell surface biomarkers using immunofluorescence microscopy. As a case study, we are looking at the expression level of toll-like receptor 2 (TLR2) proteins on Caco-2 intestinal cells after stimulation with lipopolysaccharide. The goal of this paper is to identify the segmentation algorithm which provides the best correlation between the pixel intensities of fluorescent images and quantified TLR2 mRNA. Three image segmentation algorithms are considered in this study for processing the fluorescent images acquired using a low-cost CMOS sensor. We conclusively show the existence of a proper segmentation algorithm from which we can extract results that are heavily correlated with TLR2 mRNA quantifications. The obtained results open possibilities for cost-effective and real-time monitoring of biomarkers with applications in embedded or lab-on-chip systems.

In this paper we propose CMOS-compatible Memristive-Biosensors as label-free, highly sensitive sensors for in-air detection of Vascular Endothelial Growth Factor (VEGF) molecules. The memristive behavior of the fabricated devices is strongly affected by molecules in proximity of the wire surface. In this paper, we demonstrate the reproducibility of the measurement based on the memristive voltage gap. We also show the successful sensing of femto-molar amounts of VEGF. Specifically, we demonstrate a correlation between the decreasing behavior of the voltage gap and the increasing concentrations of VEGF. The voltage gap dependence on the pH of the initial solution is also shown as a further proof of the ionic interactions occurring at the SiNW surface. All measurements are performed in air, under controlled humidity; this makes our approach more sensitive thanks to the lowered Debye screening effect of counterions.

True Single-Phase Clock (TSPC) Flip-Flops, based on dynamic logic implementation, are area-saving and high-speed compared to standard static flip-flops. Furthermore, logic gates can be embedded into TSPC flip-flops which significantly improves performance. As a promising approach to keep the pace of Moore's Law, functionality-enhanced devices with multiple independent gates have drown many recent interests. In particular, Three-Independent-Gate Silicon Nanowire FETs (TIG SiNWFETs) can realize the functionality of two serial transistors in a single device. Therefore, they open new opportunities to compact designs in both arithmetic and control circuits. In this paper, we propose TSPC flip-flop implementation with asynchronous set and reset using the compactness of TIG SiNWFET. Electrical simulations show that TIG SiNWFET-based TSPC flip-flop improves nearly 20%, 30% and 7% in area, delay and leakage power respectively as compared to its LSTP FinFET counterpart at 22nm.

Polarity-controllable transistors have emerged in the last few years as an adequate successor of current CMOS FinFETs. Due to the additional polarity terminal, novel physical design techniques are required. We present a novel grid-based power routing scheme able to mitigate the polarity terminal impact. The logic cells are organized in regular arrangements and easily configured using the novel power routing scheme. The impact of the placement and routing techniques used is gauged in terms of routing metal distribution, speed and area performance. Benchmark circuits are synthesized, placed and routed using commercial tools and performances are extracted. Post place and route results show 28% faster circuits compared to 22nm FinFET regular layout-based designs.

The quest for technologies with superior device characteristics has showcased Carbon-Nanotube Field-Effect Transistors (CNFET) into limelight. In this work we present physical design techniques to improve the yield of CNFET circuits in the presence of Carbon Nanotube (CNT) imperfections. Various layout schemes are studied for enhancing the yield of CNFET standard cell library. With the help of existing ASIC design flow, we perform system-level benchmarking of CNFET circuits and compare them to CMOS circuits at various technology nodes. With CNFET technology, we observe maximum performance gains for circuits with gate-dominated delays. Averaged across various benchmarks at 16 nm, we report 8× improvement in Energy-Delay-Product (EDP) with CNFET circuits when compared to CMOS counterpart. We also study the performance of a complete OpenRISC processor, where we see 1.5× improvement in EDP over CMOS at 16 nm technology node. Voltage scaling enabled by CNFETs can be explored in the future for further performance benefits.

We present a new logic synthesis methodology, called MIXSyn, that produces area-efficient results for mixed XOR-AND/OR dominated logic functions. MIXSyn is a two step synthesis process. The first step is a hybrid logic optimization that enables selective and distinct optimization of AND/OR and XOR-intensive portions of the logic circuit. The second step is a library-free technology mapping that enhances design flexibility with a tractable computational cost. MIXSyn has been tested on a set of large MCNC benchmarks. Experimental results indicate that MIXSyn produces CMOS circuits with 18.0% and 9.2% fewer devices, on the average, with respect to state-of-art academic and commercial synthesis tools, respectively. MIXSyn is also capable to exploit the opportunity of novel XOR implementations offered by the use of double-gate ambipolar devices. Experimental results show that MIXSyn can reduce the number of ambipolar transistors by 20.9% and 15.3%, on the average, with respect to state-of-art academic and commercial synthesis tools, respectively.

Despite the impressive advance of logic synthesis during the past decades, a general methodology capable of efficiently synthesizing both control and datapath logic is still missing. Indeed, while synthesis techniques for random control logic (AND/OR-intensive) are well established, no dominant method for automated synthesis of datapath logic (XOR/MAJ-intensive) has yet emerged. Recently, Binary Decision Diagrams (BDDs) have been adopted to create an optimization system, named BDS, that supports integrated synthesis of both AND/OR- and XOR-intensive functions through functional logic decomposition on the BDD structure. However, it does not support direct decomposition and manipulation of majority logic which, instead, is widely used in datapath circuits. In this paper, we present the first BDD-based majority logic decomposition method and a logic decomposition system, BDS-MAJ, that enables efficient logic synthesis for both random control and datapath circuits. Experimental results show that logic synthesis based on BDS-MAJ produces CMOS circuits having on average 28.8% and 26.4% less area and, at the same time, 12.8% and 20.9% smaller delay with respect to academic ABC and BDS synthesis tools. Compared to commercial Synopsys Design Compiler synthesis tool, BDS-MAJ reduces on average the circuit area by 6.0% and decreases the delay by 7.8%.

In addition to scaling semiconductor devices down to their physical limit, novel devices show enhanced functionality compared to conventional CMOS. At advanced technology nodes, many devices exhibit ambipolar behavior, i.e., they show n- and p-type characteristics simultaneously. This phenomenon can be tamed using double-gate structures. In this paper, we present a complete framework relying on Double-Gate-all-around Vertically stacked NanoWire FETs (DG-NWFETs). Such device enables a compact realization of arithmetic logic functions and presents unprecedented interest for structured ASIC applications.

We present a novel class of decision diagrams, called Biconditional Binary Decision Diagrams (BBDDs), that enable efficient logic synthesis for XOR-rich circuits. BBDDs are binary decision diagrams where the Shannon's expansion is replaced by the biconditional expansion. Since the biconditional expansion is based on the XOR/XNOR operations, XOR-rich logic circuits are efficiently represented and manipulated with canonical Reduced and Ordered BBDDs (ROBBDDs). Experimental results show that ROBBDDs have 37% fewer nodes on average compared to traditional ROBDDs. To exploit this opportunity in logic synthesis for XOR-rich circuits, we developed a BBDD-based One-Pass Synthesis (OPS) methodology. The BBDD-based OPS is capable to harness the potential of novel XOR-efficient devices, such as ambipolar transistors. Experimental results show that our logic synthesis methodology reduces the number of ambipolar transistors by 49.7% on average with respect to state-of-art commercial logic synthesis tool. Considering CMOS technology, the BBBD-based OPS reduces the device count by 31.5% on average compared to commercial synthesis tool.

Vertically stacked nanowire FETs (NWFETs) with gate-all-around structure are the natural and most advanced extension of FinFETs. At advanced technology nodes, many devices exhibit ambipolar behavior, i.e., the device shows n- and p-type characteristics simultaneously. In this paper, we show that, by engineering of the contacts and by constructing independent double-gate structures, the device polarity can be electrostatically programmed to be either n- or p-type. Such a device enables a compact realization of XOR-based logic functions at the cost of a denser interconnect. To mitigate the added area/routing overhead caused by the additional gate, an approach for designing an efficient regular layout, called Sea-of-Tiles is presented. Then, specific logic synthesis techniques, supporting the higher expressive power provided by this technology, are introduced and used to showcase the performance of the controllable-polarity NWFETs circuits in comparison with traditional CMOS circuits.

A power delivery system for implantable biosensors is presented. The system, embedded into a skin patch and located directly over the implantation area, is able to transfer up to 15 mW wirelessly through the body tissues by means of an inductive link. The inductive link is also used to achieve bidirectional data communication with the implanted device. Downlink communication (ASK) is performed at 100 kbps; uplink communication (LSK) is performed at 66.6 kbps. The received power is managed by an integrated system including a voltage rectifier, an amplitude demodulator and a load modulator. The power management system is presented and evaluated by means of simulations.

Two diverse manufacturing techniques for building 3-D integrated systems are vertical integration with Through-Silicon-Vias (TSVs), also referred as 3-D TSV integration, and 3D monolithic integration. In this paper, we present a hybrid integration scheme that combines these two approaches, taking into account their existing technology limits, into a disruptive paradigm called 3.5-D integration. Our novel integration supports circuit-partitioning both at the gate and block level with unprecedented benefits in cost. To demonstrate the effectiveness of 3.5-D integration, we chose as case study a 288-core MPSoC and we made hypothesis on the manufacturing and test cost. We argue a potential 20% decrease in the manufacturing cost and 30% decrease in the test cost when compared to 3-D TSV integration. In order to study the performance improvement of the MPSoC, we benchmarked various blocks of the core and the on-chip interconnection network, connecting all the cores. Our study shows large improvement in performance of the core (average of 11.5%) and latency (average of 24%) of the Network-on-Chip (NoC) for the 3.5-D integration when compared to the corresponding 3-D TSV implementation.

High quality CMOS image sensors are of great importance for LoC - Lab-on-Chip devices based on optical measurements. The main target in these devices is to minimize the cost and area while achieving a good resolution. The performance parameters of image sensor pixels and CMOS compatible photodiodes depend on the size, type and the geometry of the photodiode layout and varies for each technology. In this study, we present a comparative analysis of CMOS compatible photodiode types at different areas. The results have shown n-well/p-sub type photodiode with 5×5 μm2diffusion area achieves the highest sensitivity (69.81 × 1012V.s-1.cm-2/W.cm-2) and with 40 × 40 μm2diffusion area, highest SNR - Signal-to-Noise Ratio (72.26dB) at 630 nm, while the p+/n-well/p-sub type photodiode with 40 × 40 μm2diffusion area results in highest responsivity (0.466 A. cm-2/W.cm-2) at the same wavelength.

For the rapid adoption of new and aggressive technologies such as ambipolar Silicon NanoWire (SiNW), addressing fault-tolerance is necessary. Traditionally, transient fault detection implies large hardware overhead or performance decrease compared to permanent fault detection. In this paper, we focus on on-line testing and its application to ambipolar SiNW. We demonstrate on self-checking ripple-carry adder how ambipolar design style can help reduce the hardware overhead. When compared with equivalent CMOS process, ambipolar SiNW design shows a reduction in area of at least 56% (28%) with a decreased delay of 62% (6%) for Static (Transmission Gate) design style.

We extend ambipolar silicon nanowire transistors by using three independent gates and show an efficient approach to implement dual-threshold-voltage configurable circuits. Polarity and threshold voltage of uncommitted devices are determined by applying different bias patterns to the three gates. Uncommitted logic gates can thus be configured to implement different logic functions for dual-threshold-voltage design using a wiring scheme, to target either high-performance or low-leakage applications. Synthesis of benchmark circuits with these devices shows comparable performance and 54% reduction of leakage power consumption compared to low-standby-power FinFET technology.

3D Monolithic Integration (3DMI), also termed as sequential integration, is a potential technology for future gigascale circuits. In 3DMI technology the 3D contacts, connecting different active layers, are in the order of few 100nm. Given the advantage of such small contacts, 3DMI enables fine-grain (gate-level) partitioning of circuits. In this work we present three cell transformation techniques for standard cell-based ICs with 3DMI technology. As a major contribution of this work, we propose a design flow comprising of a cell transformation technique,cell-on-cell stacking, and a physical design technique (CELONCELPD) aimed at placing cells transformed withcell-on-cellstacking. We analyze and compare various cell transformation techniques for 3DMI technology without disrupting the regularity of the IC design flow. Our experiments demonstrate the effectiveness of CELONCEL design technique, yielding us an area reduction of 37.5%, 16.2% average reduction in wirelength, and 6.2% average improvement in overall delay, compared with a 2D case when benchmarked across various designs in 45nm technology node.

Real-time (RT) communication support is a critical requirement for many complex embedded applications which are currently targeted to Network-on-chip (NoC) platforms. In this paper, we present novel methods to efficiently calculate worst case bandwidth and latency bounds for RT traffic streams on wormhole-switched NoCs with arbitrary topology. The proposed methods apply to best-effort NoC architectures, with no extra hardware dedicated to RT traffic support. By applying our methods to several realistic NoC designs, we show substantial improvements (more than 30 percent in bandwidth and 50 percent in latency, on average) in bound tightness with respect to existing approaches.

Many classes of applications require Quality of Service (QoS) guarantees from the system interconnect. In Networks-on-Chip (NoC) QoS guarantees usually translate into bandwidth and latency constraints for the traffic flows and require hardware support in the NoC fabric and its interfaces. In this article we present a novel NoC synthesis framework to automatically build networks that meet hard latency constraints of end-to-end traffic streams without requiring specialized hardware for the network components. The hard latency constraints are met by carefully designing the NoC topology and selecting the appropriate routes for flow using lean best-effort network components. We perform experiments on several System on Chip (SoC) benchmarks. We compared against a topology synthesis method with no support for real-time constraints and we show that the proposed method can produce topologies that can meet significantly tighter worst case latency constraints (on average 44%). We also show that the tightest worst case latency can be provided with little overhead on power consumption (on average 8.5%).

Reconfigurable parallel computing is required to provide high-performance embedded computing, hide hardware complexity, boost software development, and manage multiple workloads when multiple applications are running simultaneously on the emerging network-on-chip (NoC)-based multiprocessor systems-on-chip (MPSoCs) platforms. In these type of systems, the overall system performance may be affected due to congestion, and therefore parallel programming stacks must be assisted by quality-of-service (QoS) support to meet application requirements and to deal with application dynamism. In this paper, we present a hardware-software QoS-driven reconfigurable parallel computing framework, i.e., the NoC services, the runtime QoS middleware API and our ocMPI library and its tracing support which has been tailored for a distributed-shared memory ARM clustered NoC-based MPSoC platform. The experimental results show the efficiency of our software stack under a broad range of parallel kernels and benchmarks, in terms of low-latency interprocess communication, good application scalability, and most important, they demonstrate the ability to enable runtime reconfiguration to manage workloads in message-passing parallel applications.

Clock distribution networks are affected by different sources of variations. The resulting clock uncertainty significantly affects the frequency of a circuit. To support this analysis, a statistical model of skitter, which consists of clock skew and jitter, for 3-D clock trees is introduced. The effect of skitter on both the setup and hold time slacks is modeled. The variation of skitter is shown to be underestimated up to 36% if process variations and dynamic power supply noise are considered separately, which highlights the importance of this unified treatment. Potential scenarios of supply noise in 3-D integrated circuits (ICs) are investigated. 3-D circuits generated from industrial benchmarks are simulated to show the skitter under these scenarios. The mean and standard deviation of skitter can vary up to 60% and 51%, respectively, due to the different amplitudes and phases of supply noise. The tradeoff between skitter and the power consumed by clock trees is also shown. A set of guidelines are presented to decrease skitter in 3-D ICs. By applying these guidelines to industrial benchmarks, simulations show a decrease in the mean skitter up to 31%.

Several important societal and economic world problems can be addressed by the smart use of technology. The last forty years have witnessed the realization of computational systems and networks, rooted in our ability of crafting complex integrated circuits out of billions of transistors. Nowadays, the ability of mastering materials at the molecular level and their interaction with living matter opens up unforeseeable horizons. Networking biological sensors through body-area, ad hoc and standard communication networks boosts the intrinsic power of local measurements, and allows us to reach new standards in health and environment management, with positive fallout on security of individuals and communities. This article reviews the Nano-Tera.ch research program, addressing the enabling and disruptive technologies that stem from the combination of nanotechnology with large (tera) -scale information and communication systems.

Nowadays medical software is tightly coupled with medical devices that perform patient state monitoring and lately even some basic treatment procedures. Medical guidelines (GLs) can be seen as specification of a medical system that includes both software and electronic devices. However, often medical GLs suffer from structural problems, such as incompleteness, inconsistencies, ambiguity and redundancy. Formal representation of GLs would enable the validation of GLs structural, real-time and life-cycle properties. Several GLs formal representation methods have been presented recently. Only some of them enable automatic formal verification by introducing an additional translation path to the existing model checking environments. However, if a verified property fails it is difficult to trace back the result needed to change the model. Moreover, these formalisms provide the notion of time mostly in terms of actions order. In this paper we preset a novel approach based on Timed Automata extended with Tasks (TAT) for the medical protocol formal representation using the TIMES toolbox. We discuss the verification issues with the help of the Imatinib case study.

We have designed and fabricated double-gate ambipolar field-effect transistors, which exhibit p-type and n-type characteristics by controlling the polarity of the second gate. In this work, we present an approach for designing an efficient regular layout, called Sea-of-Tiles (SoTs). First, we address gate-level routing congestion by proposing compact layout techniques and novel symbolic-layout styles. Second, we design four logic tiles, which form the basic building block of the SoT fabric. We run extensive comparisons of mapping standard benchmarks on the SoT. Our study shows that SoT with TileG2 and TileG1h2, on an average, outperforms the one with TileG1 and TileG3 by 16% and 10% in area utilization, respectively.

Biosensors are heterogenous devices, incorporating biological structures combined with electronics, optical or other readout systems. They have been developed for detecting different biomolecules and/or pathogens and represent a key technology for advanced and point-of-care diagnostics as well as patient monitoring. In this paper we present a systematic classification of biosensors described in literature, particularly focusing on nanotechnology-based sensing. Then, we present our approach to develop electrochemical biosensors for measuring metabolites and anticancer drugs, based on a platform for multiple target detection. This platform is modular and achieves a clear separation between the chemical and the electrical components, thus easing design and manufacturing. It shows superior performance thanks to the excellent properties of electron transfer and selectivity showed by enzymes immobilized on carbon nanotubes.

Power grid analysis is a challenging problem for modern integrated circuits. For 3-D systems fabricated using stacked tiers with TSVs, traditional power grid analysis methods for planar (2-D) circuits do not demonstrate the same performance. An efficient IR drop analysis method for 3-D large-scale circuits, called 3-D voltage propagation method, is proposed in this paper. This method is compared with another widely used power grid analysis method, with preconditioned conjugated gradients. Simulation results demonstrate that the proposed method is more efficient for the IR drop analysis of large size 3-D power grids. Speedups between 10× to 20× over the preconditioned conjugated gradients method are shown.

Summary form only given. Pre-bond test has been identified as a vital step for the wafer level integration of 3-D ICs. The data obtained during this step can guide the subsequent manufacturing stages to improve the functional or parametric yield of the 3-D stack. The existing methods, however, do not relate directly the performance of the resulting circuits with sales revenues. More importantly, methods that consider the distribution of speed of the assembled 3-D stacks neglect the partition of the critical path delay across the layers of the stack. In other words, a physical layer that does not include any critical path does not primarily determine the performance of the system. Consequently, for a method that aims at maximizing the profit that can be made from a 3-D system, this layer should be treated differently.

In biological applications and systems where even the smallest details have a meaning, CCD cameras are mostly preferred and they hold most of the market share despite their high costs. In this paper, we propose a custom-designed CMOS camera to compete with the default CCD camera of an inverted microscope for fluorescence imaging. The custom-designed camera includes a commercially available mid-performance CMOS image sensor and a Field-Programmable Gate Array (FPGA) based hardware platform (FPGA4U). The high cost CCD camera of the microscope is replaced by the custom-designed CMOS camera and the two are quantitatively compared for a specific application where an Estrogen Reception (ER) expression in breast cancer diagnostic samples that emits light at 665nm has been imaged by both cameras. The gray-scale images collected by both cameras show a very similar intensity distribution. In addition, normalized white pixels after thresholding resulted in 4.96% for CCD and 3.38% for CMOS. The results and images after thresholding show that depending on the application even a mid-performance CMOS camera can provide enough image quality when the target is localization of fluorescent stained biological details. Therefore the cost of the cameras can be drastically reduced while benefiting from the inherent advantages of CMOS devices plus adding more features and flexibility to the camera systems with FPGAs.

Many core chips are emerging as the architecture of choice to provide power efficiency and improve performance, while riding Moore's Law. In these architectures, on-chip inter-connects play a pivotal role in ensuring power and performance scalability. As supply voltages begin to level off in future technologies, chip designs in general and interconnects in particular will require specialization to meet power and performance objectives. In this work, we make the observation that cache-coherent many core server chips exhibit a duality in on-chip network traffic. Request traffic largely consists of simple control messages, while response traffic often carries cache-block-sized payloads. We present Cache-Coherence Network-on-Chip (CCNoC), a design that specializes the NoC to fit the demands of server workloads via a pair of asymmetric networks tuned to the type of traffic traversing them. The networks differ in their data path width, router micro architecture, flow control strategy, and delay. The resulting heterogeneous CCNoC architecture enables significant gains in power efficiency over conventional NoC designs at similar performance levels. Our evaluation reveals that a 4×4 mesh-based chip multiprocessor with the proposed CCNoC organization running commercial server workloads is 15-28% more energy efficient than various state-of-the-art single- and dual-network organizations.

Abstract—Shared L1 memories are of interest for tightlycoupled processor clusters in programmable accelerators as they provide a convenient shared memory abstraction while avoiding cache coherence overheads. The performance of a shared-L1 memory critically depends on the architecture of the low-latency interconnect between processors and memory banks, which needs to provide ultra-fast access to the largest possible L1 working set. The advent of 3D technology provides new opportunities to improve the interconnect delay and the form factor. In this paper we propose a network architecture, 3D-LIN, based on 3D integration technology. The network can be configured based on user specifications and technology constraints to provide fast access to L1 memories on multiple stacked dies. The extracted results from the physical synthesis of 3D-LIN permit to explore trade-offs between memory size and network latency from a planar design to multiple memory layers stacked on top of logic. In the case where the system memory requirements lead to a memory area that occupies 60 % of the chip, the form factor can be reduced by more than 60 % by stacking 2 memory layers on the logic. Latency reduction is also promising: the network itself, configured for connecting 16 processing elements to 128 memory banks on 2 memory layers is 24 % faster than the planar system. I.

The invention of the memristor enables new possibilities for computation and non-volatile memory storage. In this paper we propose a Generic Memristive Structure (GMS) for 3-D FPGA applications. The GMS cell is demonstrated to be utilized for steering logic useful for multiplexing signals, thus replacing the traditional pass-gates in FPGAs. Moreover, the same GMS cell can be utilized for programmable memories as a replacement for the SRAMs employed in the look-up tables of FPGAs. A fabricated GMS cell is presented and its use in FPGA architecture is demonstrated by the area and delay improvement for several architectural benchmarks.

Abstract — The performance of most digital systems today is limited by the interconnect latency between logic and memory, rather than by the performance of logic or memory itself. Threedimensional (3-D) integration using through-silicon-vias (TSVs) may provide a solution to overcome the scaling limitations by stacking multiple memory dies on top of a many-core die. In this paper, we propose a Mesh-of-Trees (MoT) network to support high-throughput and low-latency communication between processing cores and 3-D stacked multi-banked shared L2 data memory. Compared to conventional MoT network [5] that is straightforwardly adapted to 3-D integration, the experimental results show that the proposed network significantly improves the number of operations per second. We also investigate the architecture parameters of 3-D memory stacking (e.g., number of tiers to be stacked, TSV sharing, etc.) that affect the interconnection network as well as the system performance and fabrication cost, which permits to explore trade-offs among different 3-D memory stacking architectures. I.

In three-dimensional (3D) integrated circuits, the effect of process variations on clock skew differs from 2D circuits. The combined effect of inter-die and intra-die process variations on the design of 3D clock distribution networks is considered in this article. A statistical clock skew model incorporating both the systematic and random components of process variations is employed to describe this effect. Two regular 3D clock tree topologies are investigated and compared in terms of clock skew variation. The statistical skew model used to describe clock skew variations is verified through Monte-Carlo simulations. The clock skew is shown to change in different ways with the number of planes forming the 3D IC and the clock network architecture. Simulations based on a 45-nm CMOS technology show that the maximum standard deviation of clock skew can vary from 15 ps to 77 ps. Results indicate that simply increasing the number of planes of a 3D IC does not necessarily lead to lower skew variation and higher operating frequencies. A multigroup 3D clock tree topology is proposed to effectively mitigate the variability of clock skew. Tradeoffs between the investigated 3D clock distribution networks and the number of planes comprising a 3D circuit are discussed and related design guidelines are offered. The skew variation in 3D clock trees is also compared with the skew variation of clock grids.

Memristive devices have the potential for a complete renewal of the electron devices landscape, including memory, logic, and sensing applications. This is especially true when considering that the memristive functionality is not limited to two-terminal devices, whose practical realization has been demonstrated within a broad range of different technologies. For electron devices, the memristive functionality can be generally attributed to a material state modification, whose dynamics can be engineered to target a specific application. In this review paper, we show that trap charging dynamics can explain some of the memristive effects previously reported for Schottky-barrier field-effect Si nanowire transistors (SB SiNW FETs). Moreover, the SB SiNW FETs do show additional memristive functionality due to trap charging at the metal/semiconductor surface. The combination of these two memristive effects into multiterminal metal-oxide-semiconductor field-effect transistor (MOSFET) devices gives rise to new opportunities for both memory and logic applications as well as new sensors based on the physical mechanism that originate memristance. In the special case of four-terminal memristive Si nanowire devices, which are presented for the first time in this paper, enhanced functionality is demonstrated. Finally, the multiterminal memristive devices presented here have the potential of a very high integration density, and they are suitable for hybrid complementary metal-oxide-semiconductor (CMOS) cofabrication with a CMOS-compatible process.

With technological advances, the number of cores integrated on a chip is increasing. This in turn is leading to thermal constraints and thermal design challenges. Temperature gradients and hotspots not only affect the performance of the system but also lead to unreliable circuit operation and affect the lifetime of the chip. Meeting temperature constraints and reducing hotspots are critical for achieving reliable and efficient operation of complex multi-core systems. In this article, we analyze the use of four of the most promising families of online control techniques for thermal management of multiprocessors system-on-chip (MPSoC). In particular, in our exploration, we aim at achieving an online smooth thermal control action that minimizes the performance loss as well as the computational and hardware overhead of embedding a thermal management system inside the MPSoC. The definition of the optimization problem to tackle in this work considers the thermal profile of the system, its evolution over time, and current time-varying workload requirements. Thus, this problem is formulated as a finite-horizon optimal control problem, and we analyze the control features of different online thermal control approaches. In addition, we implemented the policies on an MPSoC hardware simulation platform and performed experiments on a cycle-accurate model of the eight-core Niagara multi-core architecture using benchmarks ranging from Web-accessing to playing multimedia. Results show different trade-offs among the analyzed techniques regarding the thermal profile, the frequency setting, the power consumption, and the implementation complexity.

3-D monolithic integration (3DMI), also termed as sequential integration, is a potential technology for future gigascale circuits. Since the device layers are processed in sequential order, the size of the vertical contacts is similar to traditional contacts unlike in the case of parallel 3-D integration with through silicon vias (TSVs). Given the advantage of such small contacts, 3DMI enables manufacturing multiple active layers very close to each other. In this work we propose two different strategies of stacking standard cells in 3-D without breaking the regularity of the conventional design flow: a) Vertical stacking of diffusion areas (Intra-Cell stacking) that supports complete reuse of 2-D physical design tools and b) vertical stacking of cells over others (Cell-on-Cell stacking). A placement tool (CELONCEL-placer) targeting the Cell-on-Cell placement problem is proposed to allow high quality 3-D layout generation. Our experiments demonstrate the effectiveness of CELONCEL technique, fetching us an area gain of 37.5%, 15.51% reduction in wirelength, and 13.49% improvement in overall delay, compared with a 2-D case when benchmarked across an interconnect dominated low-density-parity-check (LDPC) decoder at 45nm technology node.

Virtually all current integrated circuits and systems would not exist without the use of logic synthesis and physical design tools. These design technologies were developed in the last fifty years and it is hard to say if they have come to full maturity. Physical design evolved from methods used for printed-circuit boards, where the classic problems of placement and routing surfaced for the first time. Logic synthesis evolved in a different trajectory, starting from the classic works on switching theory, but took a sharp turn in the eighties when multi-level logic synthesis, coupled to semicustom technologies, provided designers with a means to map models in hardware description languages into netlists ready for physical design. The clear separation between logic and physical design tasks enabled the development of effective design tool flows, where signoff could be done at the netlist level. Nevertheless, the relentless downscaling of semiconductor technologies forced this separation to disappear, once circuit delays became interconnect-dominated. Since the nineties, design flows combined logic and physical design tools to address the so-called timing closure problem, i.e., to reduce the designer effort to synthesize a design that satisfies all timing constraints. Despite many efforts in various directions, most notably with the use of the fixed timing methodology, this problem is not completely solved yet. The complexity of integrated logic and physical tool flows, as well as the decrease in design starts of large ASICs, limits the development of these flows to a few EDA companies.

The objective of this work is the systematic study of the use of electrochemical readout for advanced diagnosis and drug monitoring. Whereas to date various electrochemical principles have been studied and successfully tested, they typically operate on a single target molecule and are not integrated in a full data analysis chain. The present work aims to view various sensing approaches and explore the design space for integrated realization of multi-target sensors and sensor arrays.

Thermal issues are one of the primary challenges in 3-D integrated circuits. Thermal through-silicon vias (TTSVs) are considered an effective means to reduce the temperature of 3-D ICs. The effect of the physical and technological parameters of TTSVs on the heat transfer process within 3-D ICs is investigated. Two resistive networks are utilized to model the physical behavior of TTSVs. Based on these models, closed-form expressions are provided describing the flow of heat through TTSVs within a 3-D IC. The accuracy of these models is compared with results from a commercial FEM tool. For an investigated three-plane circuit, the average error of the first and second models is 2% and 4%, respectively. The effect of the physical parameters of TTSVs on the resulting temperature is described through the proposed models. For example, the temperature changes non-monotonically with the thickness of the silicon substrate. This behavior is not described by the traditional single thermal resistance model. The proposed models are used for the thermal analysis of a 3-D DRAM-μP system where the conventional model is shown to considerably overestimate the temperature of the system.

Next generation logic switch devices are expected to rely on radically new technologies mainly due to the increasing difficulties and limitations of state-of-the-art CMOS switches, which, in turn, will also require innovative design methodologies that are distinctly different from those used for CMOS technologies. In this paper, three alternative emerging technologies are showcased in terms of their requirements for design implementation and in terms of potential advantages. First, a CMOS evolutionary approach based on vertically-stacked gate-all-around Si nanowire FETs is discussed. Next, an alternative design methodology based on ambipolar carbon nanotube FETs is presented. Finally, a novel approach based on the recently discovered memristive devices is presented, offering the possibility of combining memory and logic functions.

The effect of process variations on the clock skew in three dimensional (3-D) circuits with multiple clock domains is investigated. In 3-D ICs, the combined effect of inter-die and intra-die process variations should be considered in the design of clock distribution networks. A statistical clock skew model incorporating spatially correlated intra-die process variations is employed to describe this effect. The clock skew is shown to change in different ways with the allocation of the clock domains within the 3-D circuit. Various schemes to assign the clock domains are investigated. Different scenarios of inter-die and intra-die process variations and an intra-die spatial correlation model are applied to these schemes. An approach where each physical plane corresponds to a single clock domain is shown to be inferior to other clocking schemes for specific variation scenarios. Tradeoffs between the number of clock domains within a physical plane and the number of planes a clock tree spans are discussed and related design guidelines are offered.

Multi-Processor Systems-on-Chip (MPSoCs) are penetrating the electronics market as a powerful, yet commercially viable, solution to answer the strong and steadily growing demand for scalable and high performance systems, at limited design complexity. However, it is critical to develop dedicated system-level design methodologies for multi-core architectures that seamlessly address their thermal modeling, analysis and management. In this work, we first formulate the problem of system-level thermal modeling and link it to produce a global thermal management formulation as a discrete-time optimal control problem, which can be solved using finite-horizon model-predictive control (MPC) techniques, while adapting to the actual time-varying unbalanced MPSoC workload requirements. Finally, we compare the system-level MPC-based thermal modeling and management approaches on an industrial 8-core MPSoC design and show their different trade-offs regarding performance while respecting operating temperature bounds.

Recently, several emerging technologies have been reported as potential candidates for controllable ambipolar devices. Controllable ambipolarity is a desirable property that enables the on-line configurability of n-type and p-type device polarity. In this paper, we introduce a new design methodology for logic gates based on controllable ambipolar devices, with an emphasis on carbon nanotubes as the candidate technology. Our technique results in ambipolar gates with a higher expressive power than conventional complementary metal-oxidesemiconductor (CMOS) libraries. We propose a library of static ambipolar carbon nanotube field effect transistor (CNTFET) gates based on generalized NOR-NAND-AOI-OAI primitives, which efficiently implements XOR-based functions. Technology mapping of several multi-level logic benchmarks that extensively use the XOR function, including multipliers, adders, and linear circuits, with ambipolar CNTFET logic gates indicates that on average, it is possible to reduce the number of logic levels by 42%, the delay by 26%, and the power consumption by 32%, resulting in a energy-delay-product (EDP) reduction of 59 % over the same circuits mapped with unipolar CNTFET logic gates. Based on the projections in [1], where it is stated that defectfree CNTFETs will provide a 5x performance improvement over metal-oxide-semiconductor field effect transistors, the ambipolar library provides a performance improvement of 7x, a 57% reduction in power consumption, and a 20x improvement in EDP over the CMOS library.

Three-dimensional integrated circuits, where multiple silicon layers are stacked vertically have emerged recently. The 3DICs have smaller form factor, shorter and efficient use of wires and allow integration of diverse technologies in the same device. The use of Networks on Chips (NoCs) to connect components in a 3D chip is a necessity. In this short paper, we present an outline on designing application-specific NoCs for 3D ICs.

Recent advances in biosensing technologies have led to applications of biosensor probe arrays for rapid identification of biological agents such as drugs, gene expressions, proteins, cholesterol and fats in an input sample. However, monitoring the simultaneous presence of multiple agents in a sample is still a challenging task. Multiple agents may often attach to the same probes, leading to low specificity. By using microarrays as a specific example, we introduce two methods based on conditional deduction and non-unique probes to detect multiple targets. We introduce three quality metrics, namely: effectiveness, cost and reliability to evaluate different designs of microarrays and propose two ILP/Pseudo-Boolean models for optimizing on these metrics. By applying on various synthetic and real datasets, we demonstrate the importance of these quality metrics in designing microarrays for multiple target detections.

Research on Networks on Chips (NoCs) has spanned over a decade and its results are now visible in some products. Thus the seminal idea of using networking technology to address the chip-level interconnect problem has been shown to be correct. Moreover, as technology scales down in geometry and chips scale up in complexity, NoCs become the essential element to achieve the desired levels of performance and quality of service while curbing power consumption levels. Design and timing closure can only be achieved by a sophisticated set of tools that address NoC synthesis, optimization and validation.

Carbon Nanotubes (CNTs) are grown using chemical synthesis, and the exact positioning and chirality of CNTs are very difficult to control. As a result, "small-width" Carbon Nanotube Field-Effect Transistors (CNFETs) can have a high probability of containing no semiconducting CNTs, resulting in CNFET failures. Upsizing these vulnerable small-width CNFETs is an expensive design choice since it can result in substantial area/power penalties. This paper introduces a processing/design co-optimization approach to reduce probability of CNFET failures at the chip-level. Large degree of spatial correlation observed in directional CNT growth presents a unique opportunity for such optimization. Maximum benefits from such correlation can be realized by enforcing the active regions of CNFETs to be aligned with each other. This approach relaxes the device-level failure probability requirement by 350X at the 45nm technology node, leading to significantly reduced costs associated with upsizing the small-width CNFETs.

Ambipolar devices have been reported in many technologies, including carbon nanotube field effect transistors (CNTFETs). The ambipolarity can be in-field controlled with a second gate, enabling the design of generalized logic gates with a high expressive power, i.e., the ability to implement more functions with fewer physical resources. Reported circuit design techniques using generalized logic gates show an improvement in terms of area and delay with respect to conventional CMOS circuits. In this paper, we characterize and study the power dissipation of generalized logic gates based on am-bipolar CNTFETs. Our results show that the logic gates in the generalized CNTFET library dissipate 28% less power on average than a library of conventional CMOS gates. Further, we also perform logic synthesis and technology mapping, demonstrating that synthesized circuits mapped with the library of ambipolar logic gates dissipate 57% less power than CMOS circuits. By combining the benefits coming from the expressive power of generalized logic and from the CNTFET technology, we demonstrate that we can reduce the energy-delay-product by a factor of 20× using the ambipolar CNTFET technology.

Networks-on-Chip (NoCs) are a promising interconnect paradigm to address the communication bottleneck of Systems-on-Chip (SoCs). Wormhole flow control is widely used as the transmission protocol in NoCs, as it offers high throughput and low latency. To match the application characteristics, customized irregular topologies and routing functions are used. With wormhole flow control and custom irregular NoC topologies, deadlocks can occur during system operation. Ensuring a deadlock free operation of custom NoCs is a major challenge. In this paper, we address this important issue and present a method to remove deadlocks in application-specific NoCs. Our method can be applied to any NoC topology and routing function, and the potential deadlocks are removed by adding minimal number of virtual or physical channels. Experiments on a variety of realistic benchmarks show that our method results in a large reduction in the number of resources needed (88% on average) and NoC power consumption, area reduction (66% area savings on average) when compared to the state-of-the-art deadlock removal methods.

Meeting the temperature constraints and reducing the hot-spots are critical for achieving reliable and efficient operation of complex multi-core systems. The goal of thermal management is to meet maximum operating temperature constraints, while tracking timevarying performance requirements. Current approaches avoid thermal violations by forcing abrupt operating points changes, which cause sharp performance degradation. In this paper we aim at achieving an online smooth thermal control action, that minimizes the tracking error. We formulate this problem as a discrete-time optimal control problem, which can be solved via online by using an embedded convex optimization solver using a receding horizon approach. The optimization problem considers the thermal profile of the system, its evolution over time, current and past time-varying workload requirements. We perform experiments on a model of the 8-core Niagara-1 multicore architecture, which show that the proposed method outperforms state-of-the-art thermal management approaches by enabling performance speed-ups of up to 2:5£ and improvements up to 12x and 3.4x in relation to frequency and temperature variations over time, respectively.

Memristors are passive circuit elements that behave as resistors with memory. The recently illustrated experimental realization of memristive behaviour of Polysilicon Nanowires has triggered interest in this concept, which is promising to a wide variety of application areas that include neuromorphic circuits. In order to progress with practical implementations that use this technology we need to expand our understanding of the conduction mechanisms in these structures and of the underlying relationship between device behavior and process manufacturing parameters. In this paper we explore these mechanisms through detailed simulation, which includes model calibration and correlation with experimental results. Through fitting of the test results we identify a unique set of density of states that characterize the particular technology implemented.

Bio-detection specially dedicated to distributed diagnostics is emerging as a quite important application for Nano-bioelectronics. Bio-detection is required to be highly sensitive in order to succeed in sensing small amount of bio-markers in patient's blood sample. Carbon Nanotubes (CNTs) provides devices in the scale of the target molecules, thereby opening up possibilities to sense few bio-markers. Moreover, bio-detection is also required to be highly specific in order to succeed in disease discrimination. FET technology provides control in multi-panel biochip to enhance specificity. The aim of the present paper is to design an array of Carbon Nanotube Field Effect Transistors (CNFETs) to provide nano-biosensing based on cytochromes P450. In particular, a novel CNFET biosensor array design is proposed which is robust to the imperfections in the CNTs thereby achieving high level of sensitivity. The proposed CNFET based design assures the improved specificity by means of a multi-gate controller at the nano-scale. The proposed application in distributed diagnostics is on detection of drugs in multi-components samples by multiplexing different P450 probes.

This paper reports on the memory and memristive effects of Schottky barrier field effect transistors (SBFET) with gate-all-around (GAA) configuration and Si nanowire (SiNW) channel. Similar behavior has also been investigated for SBFETs with poly-Si nanowire (poly-SiNW) channel in back-gate configuration. The memristive devices presented here have the potential of a very high integration density, and they are suitable for hybrid CMOS co-fabrication with a CMOS-compatible process. We show that 2 different regimes are possible, making these devices suitable either for volatile ambipolar memory or resistive random access memory (RRAM) applications. In addition, frequency- and amplitude- dependence of the memristive behavior are reported.

This paper discusses the newly introduced vertically-stacked silicon nanowire gate-all-around field-effect-transistor technology and its advantages for higher density layout design. The vertical nanowire stacking technology allows very-high density arrangement of nanowire transistors with near-ideal characteristics, and opens the possibility for design optimization by adjusting the number of nanowire stacks without affecting the footprint area of the device. Several libraries for combinational logic synthesis have been designed and implemented for the synthesis of carry-lookahead adders, using the vertically-stacked nanowire technology. The reduction in silicon active area occupancy of vertically-stacked gates are envisaged of great significance for regular cell mapping, in disruptive future applications based on nanowire transistor arrays.

Modern high-performance processors employ thermal management systems, which rely on accurate readings of on-die thermal sensors. Systematic tools for analysis and determination of best allocation and placement of thermal sensors is therefore a highly relevant problem. This paper proposes a novel technique for determining the placement of temperature sensors on complex Multi-Processor Systems-on-Chips (MPSoCs) floorplans. The proposed method first analyzes the observability of the system for all the possible sensor placement configurations. Minimum sensors placements ensuring the observability of the portion of the MPSoC system that is relevant to the designer are then compared with simulation-based data coming from a wide set of benchmarks. Pareto points identifying the best configurations are than stored. According to user designer needs the best configuration is selected and a specific location is assigned to each sensor. We compared the proposed method with state-of-the-art approaches. Results show a reduction up to 4.5× in the number of required sensors.

Meeting temperature constraints and reducing the hot-spots are critical for achieving reliable and efficient operation of complex multi-core systems. In this paper we aim at achieving an online smooth thermal control action that minimizes the performance loss as well as the computational and hardware overhead of embedding a thermal management system inside the MPSoC. The optimization problem considers the thermal profile of the system, its evolution over time and current time-varying workload requirements. We formulate this problem as a discrete-time control problem using model predictive control. The solution is computed off-line and partially on-line using an explicit approximate algorithm. This proposed method, compared with the optimum approach provides a significant reduction in hardware requirements and computational cost at the expense of a small loss in accuracy. We perform experiments on a model of the 8-core Niagara-1 multicore architecture using benchmarks ranging from web-accessing to playing multimedia. Results show that the proposed method provides comparable performance(loss up to 2.7%) versus the optimum solution with a reduction up to 72.5× in the the computational complexity.

Three-dimensional integrated circuits (3D-ICs) are a promising approach to address the integration challenges faced by current systems on chips (SoCs). Designing an efficient network on chip (NoC) interconnect for a 3-D SoC that meets not only the application performance constraints but also the constraints imposed by the 3-D technology is a significant challenge. In this paper, we present a design tool, SunFloor 3D, to synthesize application-specific 3-D NoCs. The proposed tool determines the best NoC topology for the application, finds paths for the communication flows, assigns the network components to the 3-D layers, and places them in each layer. We perform experiments on several SoC benchmarks and present a comparative study between 3-D and 2-D NoC designs. Our studies show large improvements in interconnect power consumption (average of 38%) and delay (average of 13%) for the 3-D NoC when compared to the corresponding 2-D implementation. Our studies also show that the synthesized topologies result in large power (average of 54%) and delay savings (average of 21%) when compared to standard topologies.

The use of nanowire crossbars to build devices with large storage capabilities is a very promising architectural paradigm for forthcoming nanoscale memory devices. However, this new type of memory devices raises questions regarding how to test their correct operation. In particular, the variability affecting the decoder is expected to make very complex the test of these new devices. In this paper we present a method to simplify the test of these new devices by using a current thresholder to detect badly addressed nanowires. In the proposed method, the thresholder design is based on a stochastic and perturbative model of the current through the nanowires. Thus, the calculated thresholder parameters are robust against technology variation. As our experimental results indicate, the thresholder error probability is initially only ~ 10-4, which can be also reduced further (up to ~ 60×) by trading-off only ~ 35% area overhead in the memory.

Three-dimensional stacking of silicon layers is emerging as a promising solution to handle the design complexity and heterogeneity of Systems on Chips (SoCs). Networks on Chips (NoCs) are necessary to efficiently handle the 3D interconnect complexity. Designing power efficient NoCs for 3D SoCs that satisfy the application performance requirements, while satisfying the 3D technology constraints is a big challenge. In this work, we address this problem and present a synthesis approach for designing power-performance efficient 3D NoCs. We present methods to determine the best topology, compute paths and perform placement of the NoC components in each 3D layer. We perform experiments on varied, realistic SoC benchmarks to validate the methods and also perform a comparative study of the resulting 3D NoC designs with 3D optimized mesh topologies. The NoCs designed by our synthesis method results in large interconnect power reduction (average of 38%) and latency reduction (average of 25%) when compared to traditional NoC designs.

Thermal balancing and reducing hot-spots are two important challenges facing the MPSoC designers. In this work, we model the thermal behavior of a MPSoC as a control theory problem which enables the design of an optimum frequency controller without depending on the thermal profile of the chip. The optimization performed by the controller is targeted to achieve thermal balancing on the MPSoC thermal profile to avoid hotspots and improve its reliability. The proposed system is able to perform an on-line minimization of chip thermal gradients based on both scheduler requirements and the chip thermal profile. We compare this with state of the art thermal management approaches. Our comparison shows that the proposed system offers a better both thermal profile (temperature differences higher than 4deg C have been reduced from 27.9% to 0.45%) and performance (up to 32% task waiting time reduction).

Nanowire crossbar circuits are an emerging architectural paradigm that promises a higher integration density and an improved fault-tolerance due to its reconfigurability. In this paper, we propose for the first time the utilization of the multi-spacer patterning technique to fabricate nanowire crossbars with a high cross-point density up to 1010 cm−2. We propose a novel decoder fabrication method that can be included in a process dedicated to the multi-spacer patterning technique. We address the technology problems consisting in the variability and fabrication complexity at the design level by optimizing the encoding scheme. We show an overall reduction of the variability by 18% and a cancelation of the fabrication complexity overhead.

Silicon nanowires are a promising solution to address the increasing challenges of fabrication and design at the future nodes of the Complementary Metal-Oxide-Semiconductor (CMOS) Technology roadmap. Despite the attractive opportunity that offers their organization onto regular crossbars, the problem of designing the nano-wire decoder is still challenging and highly dependent on the nanowire fabrication technology. In this paper, we introduce a novel design style and encoding scheme for decoding nanowires fabricated with the Multi-Spacer-Patterning Technique (MSPT); and we present a method based on Gray codes that reduces the fabrication cost and improves the decoder reliability. We show that by arranging the code in a Gray code fashion, we decrease the fabrication complexity by 17% and the variability by 18% on average. By optimizing the decoder parameters, the simulations showed an improvement of the crossbar yield by 40% and a reduction of the effective bit area by 51% to 169 nm2.

In many Systems on Chips (SoCs), the cores are clustered in to voltage islands. When cores in an island are unused, the entire island can be shutdown to reduce the leakage power consumption. However, today, the interconnect architecture is a bottleneck in allowing the shutdown of the islands. In this paper, we present a synthesis approach to obtain customized application-specific Networks on Chips (NoCs) that can support the shutdown of voltage islands. Our results on realistic SoC benchmarks show that the resulting NoC designs only have a negligible overhead in SoC active power consumption (average of 3%) and area (average of 0.5%) to support the shutdown of islands. The shutdown support provided can lead to a significant leakage and hence total power savings.

The quest for technologies with superior device characteristics has showcased Carbon Nanotube Field Effect Transistors (CNFETs) into limelight. Among the several design aspects necessary for today's grail in CNFET technology, achieving functional immunity to Carbon Nanotube (CNT) manufacturing issues (such as mispositioned CNTs and metallic CNTs) is of paramount importance. In this work we present a new design technique to build compact layouts while ensuring 100% functional immunity to mispositioned CNTs. Then, as second contribution of this work, we have developed a CNFET Design Kit (DK) to realize a complete design flow from logic-to-GDSII traversing the conventional CMOS design flow. This flow enables a framework that allows accurate comparison between CMOS and CNFET-based circuits. This paper also presents simulation results to illustrate such analysis, namely, a CNFET-based inverter can achieve gains, with respect to the Energy-Delay Product (EDP) metric, of more than 4× in delay, 2× in energy/cycle and significant area savings (more than 30%) when compared to a corresponding CMOS inverter benchmarked with an industrial 65nm technology.

This paper exploits the unique in-field controllability of the device polarity of ambipolar carbon nanotube field effect transistors (CNTFETs) to design a technology library with higher expressive power than conventional CMOS libraries. Based on generalized NOR-NAND-AOI-OAI primitives, the proposed library of static ambipolar CNTFET gates efficiently implements XOR functions, provides full-swing outputs, and is extensible to alternate forms with area-performance tradeoffs. Since the design of the gates can be regularized, the ability to functionalize them in-field opens opportunities for novel regular fabrics based on ambipolar CNTFETs. Technology mapping of several multi-level logic benchmarks - including multipliers, adders, and linear circuits-indicates that on average, it is possible to reduce both the number of gates and area by ~ 38% while also improving performance by 6.9times.

Nanometer CMOS scaling has resulted in greatly increased circuit variability, with extremely adverse consequences on design predictability and yield. A number of recent works have focused on adaptive post-fabrication tuning approaches to mitigate this problem. Adaptive Body Bias (ABB) is one of the most successful tuning ldquoknobsrdquo in use today in high-performance custom design. Through forward body bias (FBB), the threshold voltage of the CMOS devices can be reduced after fabrication to bring the slow dies back to within the range of acceptable specs. FBB is usually applied with a very coarse core-level granularity at the price of a significantly increased leakage power. In this paper, we propose a novel, physically clustered FBB scheme on row-based standard-cell layout style that enables selective forward body biasing of only of the rows that contain most timing critical gates, thereby reducing leakage power overhead. We propose exact and heuristic algorithms to partition the design and allocate optimal body bias voltages to achieve minimum leakage power overhead. This style is fully compatible with state-of-the-art commercial physical design flows and imposes minimal area blowup. Benchmark results show large leakage power savings with a maximum savings of 30% in case of 5% compensation and 47.6% in case of 10% compensation with respect to block-level FBB and minimal implementation area overhead.

Three-dimensional integrated circuits are a promising approach to address the integration challenges faced by current Systems on Chips (SoCs). Designing an efficient Network on Chip (NoC) interconnect for a 3D SoC that not only meets the application performance constraints, but also the constraints imposed by the 3D technology, is a significant challenge. In this work we present a design tool, SunFloor 3D, to synthesize application-specific 3D NoCs. The proposed tool determines the best NoC topology for the application, finds paths for the communication flows, assigns the network components on to the 3D layers and performs a placement of them in each layer. We perform experiments on several SoC benchmarks and present a comparative study between 3D and 2D NoC designs. Our studies show large improvements in interconnect power consumption (average of 38%) and delay (average of 13%) for the 3D NoC when compared to the corresponding 2D implementation. Our studies also show that the synthesized topologies result in large power (average of 54%) and delay savings (average of 21%) when compared to standard topologies.

Distributing power and ground to a vertically integrated system is a complex and difficult task. Interplane communication and power delivery are achieved by through silicon vias (TSVs) in most of the manufacturing techniques for three-dimensional (3-D) circuits. As shown in this paper, these vertical interconnects provide additional low impedance paths for distributing power and ground within a 3-D circuit. These paths, however, have not been considered in the design process of 3-D power and ground distribution networks. By exploiting these additional paths, the IR drop within each plane is reduced. Alternatively, the routing congestion caused by the TSVs can be decreased by removing stacks of metal vias that are used within a power distribution network. Additionally, the required decoupling capacitance for a circuit can be reduced, resulting in significant savings in area. Case studies of power grids demonstrate a significant reduction of 22% in the number of intraplane vias. Alternatively, a 25% decrease in the decoupling capacitance can be achieved.

The IEEE 802.15.4 standard is poised to become the global standard for low data rate, low energy consumption wireless sensor networks (WSN). By assigning the same sets of contention access parameters for all data frames and nodes, the contention access period (CAP) of the slotted IEEE 802.15.4 medium access control (MAC) currently provides a priority-independent channel access functionality and no service differentiation. Several recent WSN applications such as wireless body sensor networks, however, may require service differentiation and traffic prioritization support to accommodate potential high-priority traffic (e.g., alarms or emergency alerts). By allowing different sets of access parameters and data frame lengths for different priority classes, this paper develops a Markov-chain-based analytical model of the CAP of the IEEE 802.15.4 MAC with service differentiation, under unsaturated traffic conditions. In particular, given two priority classes, our analytical model is used to evaluate the performance of a simple, yet effective, contention-window-based service differentiation strategy, in terms of the resulting throughput, average frame service time and access priority for each priority class. The accuracy of the analytical model is validated by extensive ns-2 simulation.

Many Networks-on-Chip (NoC) applications exhibit one or \nmore critical traffic flows that require hard Quality of Service \n(QoS). Guaranteeing bandwidth and latency for such real time \nflows is crucial. In this paper, we present novel methods to \nefficiently calculate worst-case bandwidth and latency bounds \nand thereby provide hard QoS guarantees. Importantly, the \nproposed methods apply even to best-effort NoC architectures, \nwith no extra hardware dedicated to QoS support. By applying \nour methods to several realistic NoC designs, we show \nsubstantial improvements (on average, more than 30% in \nbandwidth and 50% in latency) in bound tightness with respect \nto existing approaches.1

MOTIVATION: Understanding gene regulation in biological processes and modeling the robustness of underlying regulatory networks is an important problem that is currently being addressed by computational systems biologists. Lately, there has been a renewed interest in Boolean modeling techniques for gene regulatory networks (GRNs). However, due to their deterministic nature, it is often difficult to identify whether these modeling approaches are robust to the addition of stochastic noise that is widespread in gene regulatory processes. Stochasticity in Boolean models of GRNs has been addressed relatively sparingly in the past, mainly by flipping the expression of genes between different expression levels with a predefined probability. This stochasticity in nodes (SIN) model leads to over representation of noise in GRNs and hence non-correspondence with biological observations. RESULTS: In this article, we introduce the stochasticity in functions (SIF) model for simulating stochasticity in Boolean models of GRNs. By providing biological motivation behind the use of the SIF model and applying it to the T-helper and T-cell activation networks, we show that the SIF model provides more biologically robust results than the existing SIN model of stochasticity in GRNs. AVAILABILITY: Algorithms are made available under our Boolean modeling toolbox, GenYsis. The software binaries can be downloaded from http://si2.epfl.ch/ approximately garg/genysis.html.

The economic and social demand for ubiquitous and multifaceted electronic systems-in combination with the unprecedented opportunities provided by the integration of various manufacturing technologies-is paving the way to a new class of heterogeneous integrated systems, with increased performance and connectedness and providing us with gateways to the living world. This paper surveys design requirements and solutions for heterogeneous systems and addresses design technologies for realizing them.

Die-temperature control to avoid hotspots is increasingly critical in multiprocessor systems-on-chip (MPSoCs) for stream computing. In this context, thermal balancing policies based on task migration are a promising approach to redistribute power dissipation and even out temperature gradients. Since stream computing applications require strict quality of service and timing constraints, the real-time performance impact of thermal balancing policies must be carefully evaluated. In this paper, we present the design of a lightweight thermal balancing policy MiGra, which bounds on-chip temperature gradients via task migration. The proposed policy exploits run-time temperature as well as workload information of streaming applications to define suitable run-time thermal migration patterns, which minimize the number of deadline misses. Furthermore, we have experimentally assessed the effectiveness of our thermal balancing policy using a complete field-programmable-gate-array-based emulation of an actual three-core MPSoC streaming platform coupled with a thermal simulator. Our results indicate that MiGra achieves significantly better thermal balancing than state-of-the-art thermal management solutions while keeping the number of migrations bounded.

Continuous transistor scaling due to improvements in CMOS devices and manufacturing technologies is increasing processor power densities and temperatures; thus, creating challenges to maintain manufacturing yield rates and reliable devices in their expected lifetimes for latest nanometer-scale dimensions. In fact, new system and processor microarchitectures require new reliability-aware design methods and exploration tools that can face these challenges without significantly increasing manufacturing cost, reducing system performance or imposing large area overheads due to redundancy. In this paper we overview the latest approaches in reliability modeling and variability-tolerant design for latest technology nodes, and advocate the need of reliability- aware design for forthcoming consumer electronics. Moreover, we illustrate with a case study of an embedded processor that effective reliability-aware design can be achieved in nanometer-scale devices through integral design approaches that covers modeling and exploration of reliability effects, and hardware-software architectural techniques to provide reliability-enhanced solutions at both microarchitectural- and system-level.

Recently, it was demonstrated that the polarity of carbon nanotube field effect transistors can be electrically controlled. In this paper we show how Programmable Logic Arrays (PLA) can be built out of these devices, and we illustrate how they outperform usual PLA by internal signal inversion. The simulations show an area saving up to approximately 21% and decrease of the delay in PLA-based FPGA by 50%. We also show that this architecture is suitable for high-performance design tools and defect-tolerance approaches.

Summary form only given. The ongoing scaling and hybridisation of manufacturing technologies enables us to attain unprecedented levels performance as well as to integrate electronic and fluidic circuits with sensors and actuators. Smart micro/nano systems will be the building blocks of wearable and ambient systems, that gather and integrate heterogeneous data in real time and operate and communicate in a wireless and ultra low power mode. These systems will foster a revolution in health and environmental management, with the final objective of improving security and quality of life. At the same time, they will create a large market of components and systems, and a renewed perspective for electronic design and manufacturing companies. To accomplish such an ambitious goal, new technologies and architectures must be matched and tailored to the operational environment by solving novel an challenging design and optimisation problems, through the creation of novel design methodologies and tools.

As feature sizes decrease, power dissipation and heat generation density exponentially increase. Thus, temperature gradients in multiprocessor systems on chip (MPSoCs) can seriously impact system performance and reliability. Thermal balancing policies based on task migration have been proposed to modulate power distribution between processing cores to achieve temperature flattening. However, in the context of MPSoC for multimedia streaming computing, where timeliness is critical, the impact of migration on quality of service must be carefully analyzed. In this paper we present the design and implementation of a lightweight thermal balancing policy that reduces on-chip temperature gradients via task migration. This policy exploits run-time temperature and load information to balance the chip temperature. Moreover, we assess the effectiveness of the proposed policy for streaming computing architectures using a cycle-accurate thermal-aware emulation infrastructure. Our results using a real-life software defined radio multitask benchmark show that our policy achieves thermal balancing while keeping migration costs bounded.

With technology advances, the number of cores integrated on a chip and their speed of operation is increasing. This, in turn is leading to a significant increase in chip temperature. Temperature gradients and hot-spots not only affect the performance of the system, but also lead to unreliable circuit operation and affect the life-time of the chip. Meeting the temperature constraints and reducing the hot-spots are critical for achieving reliable and efficient operation of complex multi-core systems. In this work, we present Pro-Temp, a convex optimization based method that pro-actively controls the temperature of the cores, while minimizing the power consumption and satisfying application performance constraints. The method guarantees that the temperature of the cores are below a user- defined threshold at all instances of operation, while also reducing the hot-spots. We perform experiments on several realistic multi-core benchmarks, which show that the proposed method guarantees that the cores never exceed the maximum temperature limit, while matching the application performance requirements. We compare this to traditional methods, where we find several temperature violations during the operation of the system.

Accurate power and performance figures are critical to assess the effective design of possible sensor node architectures in body area networks (BANs) since they operate on limited energy storage. Therefore, accurate power models and simulation tools that can model real-life working conditions need to be developed and validated with real platforms. In this paper we propose a sensor node platform designed for health-care applications and a validated simulation model based on event-driven operating system simulation that can be used to accurately analyze performance and power consumption in BANs composed of multiple nodes. Thus, this model can be employed to tune the node architecture and communication layer for different working conditions, applications and topologies of BANs. In this paper we validate the proposed simulation model on different real-life applications and working conditions. Our results show variations of less than 4% between the presented simulation framework and measurements in the final platforms.

MOTIVATION: In silico modeling of gene regulatory networks has gained some momentum recently due to increased interest in analyzing the dynamics of biological systems. This has been further facilitated by the increasing availability of experimental data on gene-gene, protein-protein and gene-protein interactions. The two dynamical properties that are often experimentally testable are perturbations and stable steady states. Although a lot of work has been done on the identification of steady states, not much work has been reported on in silico modeling of cellular differentiation processes. RESULTS: In this manuscript, we provide algorithms based on reduced ordered binary decision diagrams (ROBDDs) for Boolean modeling of gene regulatory networks. Algorithms for synchronous and asynchronous transition models have been proposed and their corresponding computational properties have been analyzed. These algorithms allow users to compute cyclic attractors of large networks that are currently not feasible using existing software. Hereby we provide a framework to analyze the effect of multiple gene perturbation protocols, and their effect on cell differentiation processes. These algorithms were validated on the T-helper model showing the correct steady state identification and Th1-Th2 cellular differentiation process. AVAILABILITY: The software binaries for Windows and Linux platforms can be downloaded from http://si2.epfl.ch/~garg/genysis.html.

The fabrication of crossbar memories with sublithographic features is expected to be feasible within several emerging technologies; in all of them, the nanowire (NW) decoder is a critical part since it bridges the sublithographic wires to the outer circuitry that is defined on the lithography scale. In this paper, we evaluate the addressing scheme of the decoder circuit for NW crossbar arrays, based on the existing technological solutions for threshold voltage differentiation of NW devices. This is equivalent to using a multivalued logic addressing scheme. With this approach, it is possible to reduce the decoder size and keep it defect tolerant. We formally define two types of multivalued codes (i.e., hot and reflexive codes), and we estimate their yield under high variability conditions. Multivalued hot decoders yield better area saving thann-ary reflexive codes, and under severe conditions, reflexive codes enable a nonvanishing part of the code space to randomly recover. The choice of the optimal combination of decoder type and logic level saves area up to 24%. We also show that the precision of the addressing voltages when a high variability affects the threshold voltages is a crucial parameter for the decoder design and permits large savings in memory area. Moreover, a precise knowledge about the variability level improves the design of memory decoders by giving the right optimal code.

Several alternative building blocks have been proposed to replace planar transistors, among which a prominent spot belongs to nanometric filaments such as silicon nanowires (SiNWs) and carbon nanotubes (CNTs). However, chips leveraging these nanoscale structures are expected to be affected by a large amount of manufacturing faults, way beyond what chip architects have learned to counter. In this paper, the authors show a design flow, based on software mapping algorithms, to improve the yield of nanometric programmable logic arrays (PLAs). While further improvements to the manufacturing technology will be needed to make these devices fully usable, our flow can significantly shrink the gap between current and desired yield levels. Also, the approach does not need post-fabrication functional analysis and mapping, therefore dramatically cutting on verification costs. The authors check PLA yields by means of an accurate analyzer after Monte Carlo fault injection. The authors show that, compared to a baseline policy of wire replication, they achieve equal or better yields (8% over a set of designs) depending on the underlying defect assumptions

Multi-Processor System-On-Chip (MPSoC) can provide the performance levels required by high-end embedded applications. However, they do so at the price of an increasing power density, which may lead to thermal runaway if coupled with low-cost packaging and cooling. Hence, mechanisms to efficiently evaluate the effectiveness of advanced thermal-aware operating-system (OS) strategies (e.g. task migration) onto the available MPSoC hardware are needed. In this paper, we propose a new MPSoC OS emulation framework that enables the study of thermal management strategies at the architectural- and OS-levels with the help of a standard FPGA. This framework includes the hardware and software components needed to accurately model complex MPSoCs architectures, and to test the effects of run-time thermal management strategies at the OS/middleware level with real-life inputs. Our results show that migration overhead is negligible w.r.t. temperature timings, enabling the development of thermal-aware migration strategies. Moreover, the effectiveness of the monitoring and feedback mechanism provides an emulation performance only ten times slower than real time.

Several technologies with sub-lithographic features are targeting the fabrication of crossbar memories in which the nanowire decoder is playing a major role. In this paper, we suggest a way to reduce the decoder size and keep it defect tolerant by using multiple threshold voltages (VT), which is enabled by our underlying technology. We define two types of multi-valued decoders and model the defects they undergo due to the VT variation. Multi-valued hot decoders yield better area saving than n-ary reflexive codes (NRC), and under severe conditions, NRC enables a non-vanishing part of the code space to recover. There are many combinations of decoder type and number of VT’s yielding equal effective memory capacities. The optimal choice saves area up to 24%. We also show that the precision of the addressing voltages for decoders with unreliable VT’s is a crucial parameter for the decoder design and permits large savings in memory area.

Process variation in future technologies can cause severe performance degradation since different parts of the shared register file (RF) in VLIW processors may operate at various speeds. In this paper we present a complete approach that handles speed variability of the RF proposing different compile-time and run-time design alternatives. The first alternative extends current RF architectures and uses a compile-time variability-aware register assignment algorithm. The second alternative presents a fully-adjustable pure run-time approach, which overcomes the variability loss as well, but at the extra cost of cycles and area. However, the savings achieved and the run-time management of the register delay variations without any support from the user, show a very promising application field. Our results in embedded system benchmarks show that variability can be tackled without significant performance penalty, and trade-offs between performance and area are possible thanks to the whole design spectrum provided by the two presented alternatives.

Summary form only given. Networks on chips provide structured solutions for fast and low-power interconnect, but need to be adapted to the performance and physical design requirements of the host chip. Efficient and optimal design of such networks is an error-prone, tedious and time-consuming task. Thus, NoCs require design environments in which the network can be instantiated and tuned automatically, and where the designer steers the design by providing high level models of requirements and constraints. This talk would survey the state of the art in design automation for NoCs

As embedded computing evolves towards ever more powerful architectures, the challenge of properly interconnecting large numbers of on-chip computation blocks is becoming prominent. Networks-on-chip (NoCs) have been proposed as a scalable solution to both physical design issues and increasing bandwidth demands. However, this claim has not been fully validated yet, since the design properties and tradeoffs of NoCs have not been studied in detail below the 100 nm threshold. This work is aimed at shedding light on the opportunities and challenges, both expected and unexpected, of NoC design in nanometer CMOS. We present fully working 65 nm NoC designs, a complete NoC synthesis flow and detailed scalability analysis

BACKGROUND: The ambition of most molecular biologists is the understanding of the intricate network of molecular interactions that control biological systems. As scientists uncover the components and the connectivity of these networks, it becomes possible to study their dynamical behavior as a whole and discover what is the specific role of each of their components. Since the behavior of a network is by no means intuitive, it becomes necessary to use computational models to understand its behavior and to be able to make predictions about it. Unfortunately, most current computational models describe small networks due to the scarcity of kinetic data available. To overcome this problem, we previously published a methodology to convert a signaling network into a dynamical system, even in the total absence of kinetic information. In this paper we present a software implementation of such methodology. RESULTS: We developed SQUAD, a software for the dynamic simulation of signaling networks using the standardized qualitative dynamical systems approach. SQUAD converts the network into a discrete dynamical system, and it uses a binary decision diagram algorithm to identify all the steady states of the system. Then, the software creates a continuous dynamical system and localizes its steady states which are located near the steady states of the discrete system. The software permits to make simulations on the continuous system, allowing for the modification of several parameters. Importantly, SQUAD includes a framework for perturbing networks in a manner similar to what is performed in experimental laboratory protocols, for example by activating receptors or knocking out molecular components. Using this software we have been able to successfully reproduce the behavior of the regulatory network implicated in T-helper cell differentiation. CONCLUSION: The simulation of regulatory networks aims at predicting the behavior of a whole system when subject to stimuli, such as drugs, or determine the role of specific components within the network. The predictions can then be used to interpret and/or drive laboratory experiments. SQUAD provides a user-friendly graphical interface, accessible to both computational and experimental biologists for the fast qualitative simulation of large regulatory networks for which kinetic data is not necessarily available.

BACKGROUND: Structural genomics initiatives are producing increasing numbers of three-dimensional (3D) structures for which there is little functional information. Structure-based annotation of molecular function is therefore becoming critical. We previously presented FEATURE, a method for describing microenvironments around functional sites in proteins. However, FEATURE uses supervised machine learning and so is limited to building models for sites of known importance and location. We hypothesized that there are a large number of sites in proteins that are associated with function that have not yet been recognized. Toward that end, we have developed a method for clustering protein microenvironments in order to evaluate the potential for discovering novel sites that have not been previously identified. RESULTS: We have prototyped a computational method for rapid clustering of millions of microenvironments in order to discover residues whose surrounding environments are similar and which may therefore share a functional or structural role. We clustered nearly 2,000,000 environments from 9,600 protein chains and defined 4,550 clusters. As a preliminary validation, we asked whether known 3D environments associated with PROSITE motifs were "rediscovered". We found examples of clusters highly enriched for residues that share PROSITE sequence motifs. CONCLUSION: Our results demonstrate that we can cluster protein environments successfully using a simplified representation and K-means clustering algorithm. The rediscovery of known 3D motifs allows us to calibrate the size and intercluster distances that characterize useful clusters. This information will then allow us to find new clusters with similar characteristics that represent novel structural or functional sites.

Designing a power-efficient interconnection architecture for multiprocessor systems-on-chips (MPSoCs) satisfying the application performance constraints is a nontrivial task. In order to meet the tight time-to-market constraints and to effectively handle the design complexity, it is essential to provide a computer-aided design tool support for automating this task. In this paper, we address the issue of ldquoapplication-specific design of optimal crossbar architecturerdquo satisfying the performance requirements of the application and optimal binding of the cores onto the crossbar resources. We present a simulation-based design approach that is based on the analysis of the actual traffic trace of the application, considering local variations in traffic rates, temporal overlap among traffic streams, and criticality of traffic streams. Our approach is physical design aware, where the wiring complexity of the crossbar architecture is also considered during the design process. This leads to detecting timing violations on the wires early in the design cycle and to having accurate estimates of the power consumption on the wires. We apply our methodology onto several MPSoC designs, and the synthesized crossbar platforms are validated for performance by cycle-accurate SystemC simulation of the designs. The crossbar matrix power consumption values are based on the synthesis of the register transfer level models of the designs, obtained using industry standard tools. The experimental case studies show large reduction in communication architecture power consumption (45.3% on average) and total wirelength (38% on average) for the MPSoC designs when compared with traditional design approaches. The synthesized crossbar designs also lead to large reduction in transaction latencies (up to 7 ) when compared with the existing design approaches.

With technology scaling, the wire delay as a fraction of the total delay is increasing, and the communication architecture is becoming a major bottleneck for system performance in systems on chip (SoCs). A communication-centric design paradigm, networks on chip (NoCs), has been proposed recently to address the communication issues of SoCs. As the geometries of devices approach the physical limits of operation, NoCs will be susceptible to various noise sources such as crosstalk, coupling noise, process variations, etc. Designing systems under such uncertain conditions become a challenge, as it is harder to predict the timing behavior of the system. The use of conservative design methodologies that consider all possible delay variations due to the noise sources, targeting safe system operation under all conditions will result in poor system performance. An aggressive design approach that provides resilience against such timing errors is required for maximizing system performance. In this paper, we present T-error, which is a timing-error-tolerant aggressive design method to design the individual components of the NoC (such as switches, links, and network interfaces), so that the communication subsystem can be clocked at a much higher frequency than a traditional conservative design (up to 1.5x increase in frequency). The NoC is designed to tolerate timing errors that arise from overclocking without substantially affecting the latency for communication. We also present a way to dynamically configure the NoC between the overclocked mode and the normal mode, where the frequency of operation is lower than or equal to the traditional design's frequency, so that the error recovery penalty is completely hidden under normal operation. Experiments on several benchmark applications show large performance improvement (up to 33% reduction in average packet latency) for the proposed system when compared to traditional systems.

Co-clustering has not been much exploited in biomedical informatics, despite its success in other domains. Most of the previous applications were limited to analyzing gene expression data. We performed co-clustering analysis on other types of data and obtained promising results, as summarized in this paper.

New tendencies envisage multiprocessor systems-on-chips (MPSoCs) as a promising solution for the consumer electronics market. MPSoCs are complex to design, as they must execute multiple applications (games, video) while meeting additional design constraints (energy consumption, time-to-market). Moreover, the rise of temperature in the die for MPSoCs can seriously affect their final performance and reliability. In this article, we present a new hardware-software emulation framework that allows designers a complete exploration of the thermal behavior of final MPSoC designs early in the design flow. The proposed framework uses FPGA emulation as the key element to model hardware components of the considered MPSoC platform at multimegahertz speeds. It automatically extracts detailed system statistics that are used as input to our software thermal library running in a host computer. This library calculates at runtime the temperature of on-chip components, based on the collected statistics from the emulated system and final floorplan of the MPSoC. This enables fast testing of various thermal management techniques. Our results show speedups of three orders of magnitude compared to cycle-accurate MPSoC simulators.

Today, chip multiprocessors (CMPs) that accommodate multiple processor cores on the same chip have become a reality. As the communication complexity of such multicore systems is rapidly increasing, designing an interconnect architecture with predictable behavior is essential for proper system operation. In CMPs, general-purpose processor cores are used to run software tasks of different applications and the communication between the cores cannot be precharacterized. Designing an efficient network-on-chip (NoC)-based interconnect with predictable performance is thus a challenging task. In this paper, we address the important design issue of synthesizing the most power efficient NoC interconnect for CMPs, providing guaranteed optimum throughput and predictable performance for any application to be executed on the CMP. In our synthesis approach, we use accurate delay and power models for the network components (switches and links) that are obtained from layouts of the components using industry standard tools. The synthesis approach utilizes the floorplan knowledge of the NoC to detect timing violations on the NoC links early in the design cycle. This leads to a faster design cycle and quicker design convergence across the high-level synthesis approach and the physical implementation of the design. We validate the design flow predictability of our proposed approach by performing a layout of the NoC synthesized for a 25-core CMP. Our approach maintains the regular and predictable structure of the NoC and is applicable in practice to existing NoC architectures.

Today's embedded systems integrate multiple IP cores for processing, communication, and sensing on a single die as systems-on-chip (SoCs). Aggressive transistor scaling, decreased voltage margins and increased processor power and temperature have made reliability assessment a much more significant issue. Although reliability of devices and interconnect has been broadly studied, in this work, we study a tradeoff between reliability and power consumption for component-based SoC designs. We specifically focus on hard error rates as they cause a device to permanently stop operating. We also present a joint reliability and power management optimization problem whose solution is an optimal management policy. When careful joint policy optimization is performed, we obtain a significant improvement in energy consumption (40%) in tandem with meeting a reliability constraint for all SoC operating temperatures

To provide a scalable communication infrastructure for systems on chips (SoCs), networks on chips (NoCs), a communication centric design paradigm is needed. To be cost effective, SoCs are often programmable and integrate several different applications or use-cases on to the same chip. For the SoC platform to support the different use-cases, the NoC architecture should satisfy the performance constraints of each individual use-case. In this work we motivate the need to consider multiple use-cases during the NoC design process. We present a method to efficiently map the applications on to the NoC architecture, satisfying the design constraints of each individual use-case. We also present novel ways to dynamically reconfigure the network across the different use-cases and explore the possibility of integrating dynamic voltage and frequency scaling (DVS/DFS) techniques with the use-case centric NoC design methodology. We validate the performance of the design methodology on several SoC applications. The dynamic reconfiguration of the NoC integrated with DVS/DFS schemes results in large power savings for the resulting NoC systems

This work presents the first fully-automated computer-aided analysis approach to the quantification of the expression of receptors for the non-small cell lung carcinoma. This immunohistochemical analysis is usually performed by pathologists via visual inspection of tissue samples images. Our techniques streamlines this error-prone and time-consuming process, thereby facilitating analysis and diagnosis. Experimental results on several real-life datasets demonstrate the high quantitative precision of our approach

With the growing complexity in consumer embedded products and the improvements in process technology, Multi-Processor System-On-Chip (MPSoC) architectures have become widespread. These new systems are complex to design as they must execute multiple complex applications (e.g. video processing, 3D games), while meeting additional design constraints (e.g. energy consumption or time-to-market). Moreover, the rise of temperature in the die for MPSoC components can seriously affect their final performance and reliability. Therefore, mechanisms to efficiently evaluate complete HW/SW MPSoC designs in terms of energy consumption, temperature, performance and other key metrics are needed. In this paper, we present a new HW/SW FPGA-based emulation framework that allows designers to rapidly extract a number of critical statistics from processing cores, memories and interconnection systems being emulated on a FPGA. This information is then used to interact in real-time with a SW thermal model running on a host computer via an Ethernet port. The results show speed-ups of three orders of magnitude compared to cycle-accurate MPSoC simulators, which enable a very fast exploration of a large range of MPSoC design alternatives at the cycle-accurate level. Finally, our HW/SW framework allows designers to test run-time thermal management strategies with real-life inputs without any loss in the performance of the emulated system.

In this work we present a multi-path routing strategy that guaran-tees in-order packet delivery for Networks on Chips (NoCs). We present a design methodology that uses the routing strategy to opti-mally spread the traffic in the NoC to minimize the network band-width needs and power consumption. We also integrate support for tolerance against transient and permanent failures in the NoC links in the methodology by utilizing spatial and temporal redundancy for transporting packets. Our experimental studies show large re-duction in network bandwidth requirements (36.86% on average) and power consumption (30.51% on average) compared to single-path systems. The area overhead of the proposed scheme is small (a modest 5% increase in network area). Hence, it is practical to be used in the on-chip domain.

A communication-centric design approach, networks on chips (NoCs), has emerged as the design paradigm for designing a scalable communication infrastructure for future systems on chips (SoCs). As technology advances, the number of applications or use-cases integrated on a single chip increases rapidly. The different use-cases of the SoC have different communication requirements (such as different bandwidth, latency constraints) and traffic patterns. The underlying NoC architecture has to satisfy the constraints of all the use-cases. In this work, we present a methodology to map multiple use-cases onto the NoC architecture, satisfying the constraints of each use-case. We present dynamic re-configuration mechanisms that match the NoC configuration to the communication characteristics of each use-case, also accounting for use-cases that can run in parallel. The methodology is applied to several real and synthetic SoC benchmarks, which result in a large reduction in NoC area (an average of 80%) and power consumption (an average of 54%) compared to traditional design approaches

Reliability has become a significant challenge for system design in new process technologies. Higher integration levels dramatically increase power densities, which leads to higher temperature and adverse effects on reliability. In this paper, we introduce a simulation methodology to analyze reliability of multi-core SoCs. The proposed simulator is the first to provide system-on-chip level fine-grained reliability analysis. We use our simulation methodology to study the reliability effects of design choices such as thermal packaging and placement, as well as runtime events such as power management policies and workload distributions.

With increasing communication demands of processor and memory cores in Systems on Chips (SoCs), scalable Networks on Chips (NoCs) are needed to interconnect the cores. For the use of NoCs to be feasible in today's industrial designs, a custom-tailored, application-specific NoC that satisfies the design objectives and constraints of the targeted application domain is required. In this work, we present a design methodology that automates the synthesis of such application-specific NoC architectures. We present a floorplan aware design method that considers the wiring complexity of the NoC during the topology synthesis process. This leads to detecting timing violations on the NoC links early in the design cycle and to have accurate power estimations of the interconnect. We incorporate mechanisms to prevent deadlocks during routing, which is critical for proper operation of NoCs. We integrate the NoC synthesis method with an existing design flow, automating NoC synthesis, generation, simulation and physical design processes. We also present ways to ensure design convergence across the levels. Experiments on several SoC benchmarks are presented, which show that the synthesized topologies provide a large reduction in network power consumption (2.78x on average) and improvement in performance (1.59x on average) over the best mesh and mesh-based custom topologies. An actual layout of a multimedia SoC with the NoC designed using our methodology is presented, which shows that the designed NoC supports the required frequency of operation (close to 900 MHz) without any timing violations. We could design the NoC from input specifications to layout in 4 hours, a process that usually takes several weeks.

As the geometries of the transistors reach the physical limits of operation, one of the main design challenges of systems-on-chips (SoCs) will be to provide dynamic (run-time) support against permanent and intermittent faults that can occur in the system. One of the most critical elements that affect the correct behavior of the system is the unreliable operation of on-chip memories. In this paper we present a novel solution to enable fault tolerant on-chip memory design at the system level for multimedia applications, based on the network-on-chip (NoC) interconnection paradigm. We transparently keep backup copies of critical data on a reliable memory; upon a fault event, data is fetched from the backup copy in hardware, without any software intervention. The use of a NoC backbone enables an efficient design which is modular, scalable and efficient. We proceed to demonstrating its effectiveness with two real-life application case studies, and explore the performance under varying architectural configurations. The overhead to support the proposed approach is very small compared to non-fault tolerant systems, i.e. no negative performance impact and an area increase dominated by that of just the backup storage itself.

In recent years, the development of high throughput devices for the massive parallel analyses of genomic data has lead to the generation of large amount of new biological evidences and has triggered the proliferation of data mining algorithms for the extraction of meaningful information. Microarrays for gene expression analyses are part of this revolution and provide important insight in molecular biology often in the form of coherent sets of genes representing previously uncharacterized processes. Large amount of data are continuously produced in this form, and computational approaches can significantly improve the efficient use of these results, since comparison among numbers of genes sets can give new meaningful information at no cost from the experimental biology point of view. To address this opportunity we designed and implemented FIT, a scalable, unsupervised algorithm that quantitatively compares different populations of gene sets using two distinct measures of similarity between any two gene sets. These measures are then used to obtain a summary statistic that describes the tightness of fit between sets belonging to two distinct populations of gene sets. We present the results of FIT on two data sets for the study of Lymphoma and Acute Lymphoblastic Leukemia. In both cases FIT was able to recapitulate the previous analyses on these datasets, to extend the results and to extract information likely to offer potential insights into the underlying biology.

Networks on chip (NoC) has emerged as the paradigm for designing scalable communication architecture for systems on chips (SoCs). Avoiding the conditions that can lead to deadlocks in the network is critical for using NoCs in real designs. Methods that can lead to deadlock-free operation with minimum power and area overhead are important for designing application-specific NoCs. A major class of deadlocks that occur in NoCs are due to the dependencies among the resources shared by different message types. In this work, we consider the problem of avoiding message-dependent deadlocks during the NoC topology synthesis phase. We show that by considering this issue during topology synthesis, we can obtain a significantly better NoC design than traditional methods, where the deadlock avoidance issue is dealt with separately. Our experiments on several SoC benchmarks show that our proposed scheme provides large reduction in NoC power consumption (an average of 38.5%) and NoC area (an average of 30.7%) when compared to traditional approaches

With the growing complexity in consumer embedded products and the improvements in process technology, multiprocessor system-on-chip (MPSoC) architectures have become widespread. These new systems are very complex to design as they must execute multiple complex real-time applications (e.g. video processing, or videogames), while meeting several additional design constraints (e.g. energy consumption or time-to-market). Therefore, mechanisms to efficiently explore the different possible HW-SW design interactions in complete MPSoC systems are in great need. In this paper, we present a new FPGA-based emulation framework that allows designers to rapidly explore a large range of MPSoC design alternatives at the cycle-accurate level. Our results show that the proposed framework is able to extract a number of critical statistics from processing cores, memory and interconnection systems, with a speed-up of three orders of magnitude compared to cycle-accurate MPSoC simulators

Biochips are emerging as a useful tool for high-throughput acquisition of biological data and continue to grow in information quality and in discovering new applications. Recent advances include CMOS-based integrated biosensor arrays for deoxyribonucleic acid (DNA) expression analysis (Hassibi and Lee, 2005), (Schienle , 2004), and active research is ongoing for the miniaturization and integration of protein microarrays (Kiyonaka , 2004), (Rubina , 2003), (Scrivener , 2003), tissue microarrays (TMAs), (Chen , 2004), (Shergill , 2004), and fluorescence-based multiplexed cytokine immunoassays (Wang , 2002). The main advantages of microfluidic lab-on-a-chip include ease of use, speed of analysis, low sample and reagent consumption, and high reproducibility due to standardization and automation. Without effective data-analysis methods, however, the merit of acquiring massive data through biochips will be marginal. The high-dimensional nature of such data requires novel techniques that can cope with the curse of dimensionality better than conventional data-analysis approaches. In this paper, the authors proposed a pattern-mining method to analyze large-scale biological data obtained from high-throughput biochip experiments. In particular, when a data set is given as a matrix, the method can find patterns appearing in the form of (possibly overlapping) submatrices of the input matrix. The method exploits the techniques developed for the symbolic manipulation of Boolean functions. Leveraged by this approach, the method can find, given a data matrix, all patterns that satisfy specific input parameters. The authors tested the method with several large-scale biochip data and observed that the proposed method outperforms the alternatives in terms of efficiency and the number of patterns discovered.

Networks on Chips (NoCs) have evolved as the communication design paradigm of future Systems on Chips (SoCs). In this work we target the NoC design of complex SoCs with heterogeneous processor/memory cores, providing Quality-of-Service (QoS) for the application. We present an integrated approach to mapping of cores onto NoC topologies and physical planning of NoCs, where the position and size of the cores and network components are computed. Our design methodology automates NoC mapping, physical planning, topology selection, topology optimization and instantiation, bridging an important design gap in building application specific NoCs. We also present a methodology to guarantee QoS for the application during the mapping-physical planning process by satisfying the delay/jitter constraints and real-time constraints of the traffic streams. Experimental studies show large area savings (up to 2x), bandwidth savings (up to 5x) and network component savings (up to 2.2x in buffer count, 3.8x in number of wires, 1.6x in switch ports) compared to traditional design approaches.

With decreasing feature size of transistors, the interconnect wire delay is becoming a major bottleneck in current Systems on Chips (SoCs). Another effect of shrinking feature size is that the wires are becoming unreliable as they are increasingly susceptible to various noise sources such as cross-talk, coupling noise, soft errors etc. Increasing importance of wire delay and reliability has lead to a communication centric design approach, Networks on Chip (NoC), for building complex SoCs. Current NoC communication design methodologies are based on conservative design approaches and consider worst case operating conditions for link design, resulting in large latency penalty for data transmission. In order to sub-stantially decrease the link delay and thereby increase system performance an aggressive design approach is needed. In this work we present Terror, timing error tolerant communication system, for aggressively designing the links of NoCs. In our methodology, instead of avoiding timing errors by a worst-case design, we do aggressive design by tolerating timing errors. Simulation results show large latency savings (up to 35%) for the Terror based system compared to traditional design methodology.

Current systems-on-chip (SoC) execute applications that demand extensive parallel processing. Networks-on-chip (NoC) provide a structured way of realizing interconnections on silicon, and obviate the limitations of bus-based solutions. NoC can have regular or ad hoc topologies, and functional validation is essential to assess their correctness and performance. In this paper, we present a flexible emulation environment implemented on an FPGA that is suitable to explore, evaluate and compare a wide range of NoC solutions with a very limited effort. Our experimental results show a speed-up of four orders of magnitude with respect to cycle-accurate HDL simulation, while retaining cycle accuracy. With our emulation framework, designers can explore and optimize a various range of solutions, as well as characterize quickly performance figures.

As the communication requirements of current and future Multiprocessor Systems on Chips (MPSoCs) continue to increase, scalable communication architectures are needed to support the heavy communication demands of the system. This is reflected in the recent trend that many of the standard bus products such as STbus, have now introduced the capability of designing a crossbar with multiple buses operating in parallel. The crossbar configuration should be designed to closely match the application traffic characteristics and performance requirements. In this work we address this issue of application-specific design of optimal crossbar (using STbus crossbar architecture), satisfying the performance requirements of the application and optimal binding of cores onto the crossbar resources. We present a simulation based design approach that is based on analysis of actual traffic trace of the application, considering local variations in traffic rates, temporal overlap among traffic streams and criticality of traffic streams. Our methodology is applied to several MPSoC designs and the resulting crossbar platforms are validated for performance by cycle-accurate SystemC simulation of the designs. The experimental case studies show large reduction in packet latencies (up to 7×) and large crossbar component savings (up to 3.5×) compared to traditional design approaches.

The limited scalability of current bus topologies for systems on chips (SoCs) dictates the adoption of networks on chips (NoCs) as a scalable interconnection scheme. Current SoCs are highly heterogeneous in nature, denoting homogeneous, preconfigured NoCs as inefficient drop-in alternatives. While highly parametric, fully synthesizeable (soft) NoC building blocks appear as a good match for heterogeneous MPSoC architectures, the impact of instantiation-time flexibility on performance, power and silicon cost has not yet been quantified. The paper details /spl times/pipes Lite, a design flow for automatic generation of heterogeneous NoCs. /spl times/pipes Lite is based on highly customizable, high frequency and low latency NoC modules, that are fully synthesizeable. Synthesis results provide modules that are directly comparable, if not better, than the current published state-of-the-art NoCs in terms of area, power latency and target operating frequency measurements.

On-chip interconnection networks for future systems on chip (SoC) will have to deal with the increasing sensitivity of global wires to noise sources such as crosstalk or power supply noise. Hence, transient delay and logic faults are likely to reduce the reliability of across-chip communication. Given the reduced power budgets for SoCs, in this paper, we develop solutions for combined energy minimization and communication reliability control. Redundant bus coding is proved to be an effective technique for trading off energy against reliability, so that the most efficient scheme can be selected to meet predefined reliability requirements in a low signal-to-noise ratio regime. We model on-chip interconnects as noisy channels and evaluate the impact of two error recovery schemes on energy efficiency: correction at the receiver stage versus retransmission of corrupted data. The analysis is performed in a realistic SoC setting, and holds both for shared communication resources and for peer-to-peer links in a network of interconnects. We provide SoC designers with guidelines for the selection of energy efficient error-control schemes for communication architectures.

The biclustering method can be a very useful analysis tool when some genes have multiple functions and experimental conditions are diverse in gene expression measurement. This is because the biclustering approach, in contrast to the conventional clustering techniques, focuses on finding a subset of the genes and a subset of the experimental conditions that together exhibit coherent behavior. However, the biclustering problem is inherently intractable, and it is often computationally costly to find biclusters with high levels of coherence. In this work, we propose a novel biclustering algorithm that exploits the zero-suppressedbinary decision diagrams (ZBDDs) data structure to cope with the computational challenges. Our method can find all biclusters that satisfy specific input conditions, and it is scalable to practical gene expression data. We also present experimental results confirming the effectiveness of our approach.

The growing complexity of customizable single-chip multiprocessors is requiring communication resources that can only be provided by a highly-scalable communication infrastructure. This trend is exemplified by the growing number of network-on-chip (NoC) architectures that have been proposed recently for system-on-chip (SoC) integration. Developing NoC-based systems tailored to a particular application domain is crucial for achieving high-performance, energy-efficient customized solutions. The effectiveness of this approach largely depends on the availability of an ad hoc design methodology that, starting from a high-level application specification, derives an optimized NoC configuration with respect to different design objectives and instantiates the selected application specific on-chip micronetwork. Automatic execution of these design steps is highly desirable to increase SoC design productivity. This work illustrates a complete synthesis flow, called Netchip, for customized NoC architectures, that partitions the development work into major steps (topology mapping, selection, and generation) and provides proper tools for their automatic execution (SUNMAP, xpipescompiler). The entire flow leverages the flexibility of a fully reusable and scalable network components library called xpipes, consisting of highly-parameterizable network building blocks (network interface, switches, switch-to-switch links) that are design-time tunable and composable to achieve arbitrary topologies and customized domain-specific NoC architectures. Several experimental case studies are presented In the work, showing the powerful design space exploration capabilities of the proposed methodology and tools.

Systems-on-Chip (SoC) design involves several challenges, stemming from the extreme miniaturization of the physical features and from the large number of devices and wires on a chip. Since most SoCs are used within embedded systems, specific concerns are increasingly related to correct, reliable, and robust operation. We believe that in the future most SoCs will be assembled by using large-scale macro-cells and interconnected by means of on-chip networks. We examine some physical properties of on-chip interconnect busses, with the goal of achieving fast, reliable, and low-energy communication. These objectives are reached by dynamically scaling down the voltage swing, while ensuring data integrity-in spite of the decreased signal to noise ratio-by means of encoding and retransmission schemes. In particular, we describe a closed-loop voltage swing controller that samples the error retransmission rate to determine the operational voltage swing. We present a control policy which achieves our goals with minimal complexity; such simplicity is demonstrated by implementing the policy in a synthesizable controller. Such a controller is an embodiment of a self-calibrating circuit that compensates for significant manufacturing parameter deviations and environmental variations. Experimental results show that energy savings amount up to 42%, while at the same time meeting performance requirements.

Clustering has been one of the most popular methods to discover useful biological insights from DNA microarray. An interesting paradigm is simultaneous clustering of both genes and experiments. This "biclustering" paradigm aims at discovering clusters that consist of a subset of the genes showing a coherent expression pattern over a subset of conditions. The pClustering approach is a technique that belongs to this paradigm. Despite many theoretical advantages, this technique has been rarely applied to actual gene expression data analysis. Possible reasons include the worst-case complexity of the clustering algorithm and the difficulty in interpreting clustering results. In this paper, we propose an enhanced framework for performing pClustering on actual gene expression analysis. Our new framework includes an effective data preparation method, highly scalable clustering strategies, and an intuitive result interpretation scheme. The experimental result confirms the effectiveness of our approach.

System on Chip (SoC) design faces several challenges which are due to the extremely small nature of electronic devices and the consequent opportunity to realize multi-processing systems of extremely high complexity. To manage large scale design, SoCs are assembled out of complex standard parts, such as programmable cores and memory arrays. Thus, the major design challenge is to provide correct and reliable operation of the interconnected components. Top-down correct component interconnection will become increasingly harder to succeed, because the interface features of components will also scale-up in complexity. New design methodologies will need to leverage component self-configuration and adaptation to the underlying communication fabric.

Increasing communication demands of processor and memory cores in Systems on Chips (SoCs) necessitate the use of Networks on Chip (NoC) to interconnect the cores. An important phase in the design of NoCs is he mapping of cores onto the most suitable opology for a given application. In this paper, we present SUNMAP a tool for automatically selecting he best topology for a given application and producing a mapping of cores onto that topology. SUNMAP explores various design objectives such as minimizing average communication delay, area, power dissipation subject to bandwidth and area constraints. The tool supports different routing functions (dimension ordered, minimum-path, traffic splitting) and uses floorplanning information early in the topology selection process to provide feasible mappings. The network components of the chosen NoC are automatically generated using cycle-accurate SystemC soft macros from X-pipes architecture. SUNMAP automates NoC selection and generation, bridging an important design gap in building NoCs. Several experimental case studies are presented in the paper, which show the rich design space exploration capabilities of SUNMAP.

Future systems on chips (SoCs) will integrate a large number of processor and storage cores onto a single chip and require networks on chip (NoC) to support the heavy communication demands of the system. The individual components of the SoCs will be heterogeneous in nature with widely varying functionality and communication requirements. The communication infrastructure should optimally match communication patterns among these components accounting for the individual component needs. In this paper we present /spl times/pipesCompiler, a tool for automatically instantiating an application-specific NoC for heterogeneous multi-processor SoCs. The /spl times/pipesCompiler instantiates a network of building blocks from a library of composable soft macros (switches, network interfaces and links) described in SystemC at the cycle-accurate level. The network components are optimized for that particular network and support reliable, latency-insensitive operation. Example systems with application-specific NoCs built using the /spl times/pipesCompiler show large savings in area (factor of 6.5), power (factor of 2.4) and latency (factor of 1.42) when compared to a general-purpose mesh-based NoC architecture.

We address the design of complex monolithic systems, where processing cores generate and consume a varying and large amount of data, thus bringing the communication links to the edge of congestion. Typical applications are in the area of multi-media processing. We consider a mesh-based networks on chip (NoC) architecture, and we explore the assignment of cores to mesh cross-points so that the traffic on links satisfies bandwidth constraints. A single-path deterministic routing between the cores places high bandwidth demands on the links. The bandwidth requirements can be significantly reduced by splitting the traffic between the cores across multiple paths. In this paper, we present NMAP, a fast algorithm that maps the cores onto a mesh NoC architecture under bandwidth constraints, minimizing the average communication delay. The NMAP algorithm is presented for both single minimum-path routing and split-traffic routing. The algorithm is applied to a benchmark DSP design and the resulting NoC is built and simulated at cycle accurate level in SystemC using macros from the /spl times/pipes library. Also, experiments with six video processing applications show significant savings in bandwidth and communication cost for NMAP algorithm when compared to existing algorithms.

A new approach for dynamic reliability and power management of integrated systems, such as systems on chips (SoCs) and networks in chips (NoCs) is presented. With aggressive transistor scaling, decreased voltage margins, and increased processor power and temperature, reliability assessment has become a significant issue in design. Our work combines for the first time dynamic power management with reliability models. The joint model is used to determine system level reliability as a function of failure rates, system configuration and power management policies. We show that the overall system reliability is strongly affected by reliability network topology and power management policy.

Dynamic power management encompasses several techniques for reducing energy dissipation in electronic systems by selective slowdown or shutdown of components. We present a theoretical framework for explaining and classifying different approaches to power management. Within this framework, we model power-manageable components, workloads, and controllers as discrete-event systems (DESs). The structure of these DESs is specified in terms of physical states (representing operation modes) and events (triggering state transitions), while system behavior is specified in terms of next-event and next-state functions. In particular, nondeterministic next-event and next-state functions are modeled by conditional probability distributions, according to generalized semi-Markov processes (GSMPs). The modeling framework provides a general denotational model for system specification and a rigorous execution semantics that enables event-driven simulation. We introduce a modeling framework, built on top of MathWork's Simulink, supporting the specification and execution of our model. In particular, we present templates for the Simulink simulator to execute GSMP models, and we describe how to use such templates for specifying, analyzing, and optimizing dynamic power-managed systems. Finally, we demonstrate the expressive power and versatility of the proposed approach by using the modeling framework and the simulator for the analysis of representative real-life case studies, including the Intel Xscale processor architecture, a multitasking real-time system, and a sensor network.

There is a growing demand for application-specific embedded processors in system-on-a-chip designs. Current tools and design methodologies often require designers to manually specialize the processor based on an application. Moreover, the use of the new complex instructions added to the processor is often left to designers' ingenuity. We present a solution that automatically groups dataflow operations in the application software as potential new complex instructions. The set of possible instructions is then automatically used for code generation combined with high-level arithmetic optimizations using symbolic algebra. Symbolic arithmetic manipulations provide a novel and effective method for instruction selection that is necessary due to the complexity of the automatically identified instructions. We have used our methodology to automatically add new instructions to Tensilica processors for a set of examples. Our results show that our tools improve designers productivity and efficiently specialize an embedded processor for the given application such that the execution time is greatly improved.

On-chip implementation of multiprocessor systems requires the planarization of the interconnect network onto the silicon floorplan. Manual floorplanning approaches will become increasingly more difficult and ineffective as multiprocessor complexity increases. Compared with traditional ASIC architectures, multiprocessors have homogeneous processing elements and regular network topologies. Therefore, traditional ASIC floorplanning methodologies based on macro placement are not effective in this domain. We propose an automated physical planning tool, called REGULAY, which can generate floorplans for different topologies under different design constraints. Compared with traditional floorplanning approaches, REGULAY shows significant advantages in reducing the total interconnect wire-length while preserving the regularity and hierarchy of the network topology.

Interconnect networks play a critical role in shared memory multi-processor systems-on-chip (MPSoC) designs. MPSoC performance and power consumption are greatly affected by the packet dataflows that are transported on the network. In this paper, by introducing a packetized on-chip communication power model, we discuss the packetization impact on MPSoC performance and power consumption. Particularly, we propose a quantitative analysis method to evaluate the relationship between different design options (cache, memory, packetization scheme, etc.) at the architectural level. From the benchmark experiments, we show that optimal performance and power tradeoff can be achieved by the selection of appropriate packet sizes.

New opportunities and challenges in system design are direct consequences of the progress in semiconductor technologies, and are due to the extremely small nature of electronic devices, the extremely large complexity of systems, and the new, unchartered territory set by novel technologies. Reliable on-chip communication will require viewing routing wires as information channels, and systems as micro-networks of components. Signal transmission will face an increasingly more noisy environment, where noise abstracts undesirable effects such as timing variations, cross-talk and interference. Techniques borrowed from networking will be applicable at the chip level, to provide reliable communication over unreliable physical channels. Information encoding, packetization and routing will provide us with a new facet of design, to support reliable data transfer in a noisy environment.

The growing market of multimedia applications has required the development of complex application-specified integrated circuits with significant data-path portions. Unfortunately, most high-level synthesis tools and methods cannot automatically synthesize data paths such that complex arithmetic library blocks are intelligently used. Namely, most arithmetic-level optimizations are not supported and they are left to the designer's ingenuity. In this paper, we show how symbolic algebra can be used to construct arithmetic-level decomposition algorithms. We introduce our tool, SymSyn, that optimizes and maps data flow descriptions into data paths using complex arithmetic components. SymSyn uses two new algorithms to find either minimal component mapping or minimal critical path delay (CPD) mapping of the data flow. In this paper, we give an overview of the proposed algorithms. We also show how symbolic manipulations such as tree-height-reduction, factorization, expansion, and Horner transformation are incorporated in the preprocessing step. Such manipulations are used as guidelines in initial library element selection to accelerate the proposed algorithms. Furthermore, we demonstrate how substitution can be used for multiexpression component sharing and CPD optimization.

With growing demand for embedded multimedia applications, time to market of embedded software has become a crucial issue. As a result, embedded software designers often use libraries that have been preoptimized for a given processor to achieve higher code quality. Unfortunately, current software design methodology often leaves high-level arithmetic optimizations and the use of complex library elements up to the designer's ingenuity. In this paper, we present a tool flow and a methodology, SymSoft, that automates the use of complex processor instructions and preoptimized software library routines using symbolic algebraic techniques. We use SymSoft to optimize a set of examples for the SmartBadgeIV (Maguire et al., 1998) portable embedded system running the Linux embedded operating system. The results of these optimizations show that by using SymSoft we can map the critical basic blocks of the benchmark examples to the StrongARM SA-1110 instruction set much more efficiently than the commercial StrongARM compiler. SymSoft is also used to map critical code sections to commercially available software libraries with complex mathematical elements such as exp or the inverse discrete cosine transform routine. Our measurements on SmartBadgeIV show that even higher performance improvements and energy savings are achieved by using these library elements. For example, the final optimized MP3 audio decoder runs four times faster than real-time playback while consuming four times less energy. Since the decoder executes faster than real-time playback, additional energy savings are now possible by using processor frequency and voltage scaling.

Embedded software designers often use libraries that have been pre-optimized for a given processor to achieve higher code quality. However, using such libraries in legacy code optimization is nontrivial and typically requires manual intervention. This paper presents a methodology that maps algorithmic constructs of the software specification to a library of complex software elements. This library-mapping step is automated by using symbolic algebra techniques. We illustrate the advantages of our methodology by optimizing an algorithmic level description of MPEG Layer III (MP3) audio decoder for the Badge4 [2] portable embedded system. During the optimization process we use commercially available libraries with complex elements ranging from simple mathematical functions such as exp to the IDCT routine. We implemented and measured the performance and energy consumption of the MP3 decoder software on Badge4 running embedded Linux operating system. The optimized MP3 audio decoder runs 300 times faster than the original code obtained from the standards body while consuming 400 times less energy. Since our optimized MP3 decoder runs 3.5 times faster than real-time, additional energy can be saved by using processor frequency and voltage scaling.

In this paper, we introduce a framework to estimate the power consumption on switch fabrics in network routers. We propose different modeling methodologies for node switches, internal buffers and interconnect wires inside switch fabric architectures. A simulation platform is also implemented to trace the dynamic power consumption with bit-level accuracy. Using this framework, four switch fabric architectures are analyzed under different traffic throughput and different numbers of ingress/egress ports. This framework and analysis can be applied to the architectural exploration for low power high performance network router designs.

As technology scales toward deep submicron, on-chip interconnects are becoming more and more sensitive to noise sources such as power supply noise, crosstalk, radiation induced effects, etc. Transient delay and logic faults are likely to reduce the reliability of data transfers across data-path bus lines. This paper investigates how to deal with these errors in an energy efficient way. We could opt for error correction, which exhibits larger decoding overhead, or for the retransmission of the incorrectly received data word. Provided the timing penalty associated with this latter technique can be tolerated, we show that retransmission strategies are more effective than correction ones from an energy viewpoint, both for the larger detection capability and for the minor decoding complexity. The analysis wits performed by implementing several variants of a Hamming code in the VHDL model of a processor based on the Sparc V8 architecture, and exploiting the characteristics of AMBA bus slave response cycles to carry out retransmissions in a way fully compliant with this standard on-chip bus specification.

This paper is meant to be a short introduction to a new paradigm for systems on chip (SoC) design. The premises are that a component-based design methodology will prevail in the future, to support component re-use in a plug-and-play fashion. At the same time, SoCs will have to provide a functionally-correct, reliable operation of the interacting components. The physical interconnections on chip will be a limiting factor for performance and energy consumption.

The market demand for portable multimedia applications has exploded in recent years. Unfortunately for such applications, current compilers and software optimization methods often require designers to do part of the optimization manually. Specifically, the high-level arithmetic optimizations and the use of complex instructions are left to the designers' ingenuity. In this paper, we present a tool flow, SymSoft, that automates the optimization of power-intensive algorithmic constructs using symbolic algebra techniques combined with energy profiling. SymSoft is used to optimize and tune the algorithmic level description of an MPEG Layer III (MP3) audio decoder for the SmartBadge (Maguire et al, 1998) portable embedded system. We show that our tool lowers the number of instructions and memory accesses and thus lowers the system power consumption. The optimized MP3 audio decoder software meets real-time constraints on the SmartBadge system with low energy consumption. Furthermore, the performance improves by a factor of 7.27 and the energy consumption decreases by a factor of 4.45 over the original executable specification.

This paper presents a new concept of DVS (Dynamic Voltage Scaling) for multimedia applications. Many multimedia applications have a periodic property, but each period shows a large variation in terms of its execution time. Exact estimation of such variation is a crucial factor for low energy software execution with DVS technique. Previous DVS techniques focused only on end users (client sites) and their quality heavily depends on the accurateness of the worst case execution time estimation. This paper proposes that contents providers (server sites) supply the information of the execution time variations in addition to the content itself. This makes it possible to perform DVS independent to worst case execution time estimation. The extra work required to the contents provider for this purpose is fully compensated by the benefits for the end users because single content is often provided to many users. Experimental results show that our method greatly reduces the energy consumption of client systems compared to previous DVS techniques.

Dynamic power management (DPM) is a design methodology aimed at reducing power consumption of electronic systems by performing selective shutdown of idle system resources. The effectiveness of a power management scheme depends critically on accurate modeling of service requests and on computation of the control policy. In this work, we present an online adaptive DPM scheme for systems that can be modeled as finite-state Markov chains. Online adaptation is required to deal with initially unknown or nonstationary workloads, which are very common in real-life systems. Our approach moves from exact policy optimization techniques in a known and stationary stochastic environment and extends optimum stationary control policies to handle the unknown and nonstationary stochastic environment for practical applications. We introduce two workload learning techniques based on sliding windows and study their properties. Furthermore, a two-dimensional interpolation technique is introduced to obtain adaptive policies from a precomputed look-up table of optimum stationary policies. The effectiveness of our approach is demonstrated by a complete DPM implementation on a laptop computer with a power-manageable hard disk that compares very favorably with existing DPM schemes.

The objective of this work is to create a framework for the optimization of embedded software. We present algorithms and a tool flow to reduce the computational effort of programs, using value profiling and partial evaluation. Such a reduction translates into both energy savings and average-case performance improvement, while preserving a tolerable increase of worst case performance and code size. Our tool reduces the computational effort by specializing frequently executed procedures for the most common values of their parameters. The most effective specializations are automatically searched and identified, and the code is transformed through partial evaluation. Experimental results show that their technique improves both energy consumption and performance of the source code up to more than a factor of two, in average about 35% over the original program. Also, their automatic search engine greatly reduces code optimization time with respect to exhaustive search.

This paper presents a method to reduce the energy of interactive systems for mixed workloads: multimedia applications that require constant output rates and sporadic jobs that need prompt responses. The authors' method divides multimedia programs into stages and inserts data buffers between them. Data buffering has three purposes: (1) to support constant output rates; (2) to allow frequency scaling for energy reduction; and (3) to shorten the response times of sporadic jobs. The authors construct frequency-assignment graphs. Each vertex represents the current state of the buffers and the frequencies of the processor. The authors develop an efficient graph-walk algorithm that assigns frequencies to reduce energy. The same method. can be applied to perform voltage scaling and the combination of frequency and voltage scaling. The authors' experimental results on a Strong-ARM-based computer show that four discrete frequencies are sufficient to achieve nearly maximum energy saving. The method reduces the power consumption of an MPEG program by 46%. The authors also demonstrate a case that shortens the response time of a sporadic job by 55%.

Many portable systems deploy operating systems (OS) to support versatile functionality and to manage resources, including power. This paper presents a new approach for using OS to reduce the power consumption of I/O devices in interactive systems. Low-power OS observes the relationship between hardware devices and processes. The OS kernel estimates the utilization of a device from each process. If a device is not used by any running process, the OS puts it into a low-power state. This paper also explains how scheduling can facilitate power management. When processes are properly scheduled, power reduction can be achieved without degrading performance. We implemented a prototype on Linux to control two devices; experimental results showed nearly 70% power saving on a network card and a hard disk drive.

Current multimedia applications require the design of data-path intensive circuits. Unfortunately, current design tools and methods support design abstraction at a level that is inferior to the expectation of designers. Namely, most arithmetic-level optimizations are not supported and they are left to the designers' ingenuity. In this paper, we show how symbolic algebra can be used to construct an arithmetic-level decomposition algorithm. We also introduce our tool, SymSyn, that performs arithmetic library mapping and optimization of data-flow descriptions into data paths using arithmetic components.

Portable systems require long battery lifetime while still delivering high performance. Dynamic voltage scaling (DVS) algorithms reduce energy consumption by changing processor speed and voltage at run-time depending on the needs of the applications running. Dynamic power management (DPM) policies trade off the performance for the power consumption by selectively placing components into low-power states. In this work we extend the DPM model presented in [2, 3] with a DVS algorithm, thus enabling larger power savings. We test our approach on MPEG video and MP3 audio algorithms running on the SmartBadge portable device [1]. Our results show savings of a factor of three in energy consumption for combined DVS and DPM approaches.

Intellectual Property (IP) reuse is one of the most promising techniques addressing the design complexity problem. IP reuse assumes that pre-designed components can be integrated into the design under development, thereby reducing design complexity and time. On the other hand, as the number of IP providers increases, the selection of the best IP block for a given design becomes more challenging and time-consuming. In this paper, we present an IP component matching system targeting automatic component searching and matching across the Internet. The system is based on Extensible Markup Language (XML) specification both for IP libraries (a repository of pre-designed IP components indexed by their corresponding specifications) and IP user queries (specifications with incomplete/uncertain attributes). An IP query is parsed into a document object model (DOM) and the DOM is transformed to an internal tree-structured model. Fuzzy logic scoring and aggregation algorithms are applied to the internal tree structure to provide a set of candidate approximate matches ranked by proximity between the query and IP specification.

The growing market of multi-media applications has required the development of complex ASICs with significant data-path portions. Unfortunately, most high-level synthesis tools and methods cannot automatically synthesize data paths such that complex arithmetic library blocks are intelligently used. Symbolic computer algebra has been previously used to automate mapping data flow into a minimal set of complex arithmetic components. In this paper, we present extensions to the previous methods in order to find the minimal critical path delay (CPD) mapping. A new algorithm is proposed that incorporates symbolic manipulations such as tree-height-reduction, factorization, expansion, and Horner transformation. Such manipulations are used as guidelines in initial library element selection. Furthermore, we demonstrate how substitution can be used for multi-expression component sharing and critical path delay optimization.

This paper presents a framework to reduce the computational eort of software programs, using value pro ling and partial evaluation. Our tool reduces computational eort by specializing a program for highly expected situations and such a reduction translates into both energy and performance improvement. Procedure calls executed frequently with same parameter values are de ned as highly expected situations (common cases). The choice of the best transformation of common cases is achieved by solving three search problems. The rst identi es eective common cases to be specialized, the second searches for an optimal solution for eective common case, and the third examines the interplay among the specialized cases. Our technique improves both energy consumption and performance of the source code up to more than twice and in average about 25% over the original program. Also, our pruning techniques reduce the searching time by 80% compared to exhaustive approach.

This paper introduces a power optimization paradigm for sequential components based on the concept of computational kernel, a highly simplified logic block whose behavior mimics the steady-state behavior of the original specification. We present a flexible framework that supports a number of algorithmic options for carrying out kernel extraction. We first describe an exact symbolic procedure that is applicable to components for which only a functional specification (i.e., the state transition graph) is available. Due to its computational complexity, this procedure is mainly of theoretical interest and it is not usable for large circuits. We then propose two approximate algorithms that can be adopted in practical situations. The first one is simulation-based and it is suitable to cases where input data streams representing typical operation of the component are available. The second approach performs kernel extraction by iteratively refining a structural representation of the component obtained through synthesis. The impact of the power optimization paradigm based on kernel extraction is demonstrated by the results of extensive experimentation carried out on a number of benchmarks of different characteristics and nature.

As designers may model mixed hardware-software systems using a subset of C or C++, we present SpC, a solution to synthesize and optimize hardware C models with pointers. In hardware, a pointer is not only the address of data in memory, but it may also reference data mapped to registers, ports, or wires. Pointer analysis is used to find the set of locations each pointer may reference in a program at compile time. In this paper, we address the problem of synthesizing and optimizing pointers to multiple variables or array elements. The value of the pointers are encoded and branching statements are used to dynamically access data referenced by pointers. A heuristic is used to efficiently encode the values of the pointers. Compiler techniques are also used to reduce storage before loads and stores. An implementation using the SUIF framework (Wilson et al., 1994; SUIF Compiler Framework) is presented, followed by some case studies and experimental results.

Energy consumption of electronic devices has become a serious concern in recent years. Power management (PM) algorithms aim at reducing energy consumption at the system-level by selectively placing components into low-power states. Formerly, two classes of heuristic algorithms have been proposed for PM: timeout and predictive. Later, a category of algorithms based on stochastic control was proposed for PM. These algorithms guarantee optimal results as long as the system that is power managed can be modeled well with exponential distributions. We show that there is a large mismatch between measurements and simulation results if the exponential distribution is used to model all user request arrivals. We develop two new approaches that better model system behavior for general user request distributions. Our approaches are event-driven and give optimal results verified by measurements. The first approach we present is based on renewal theory. This model assumes that the decision to transition to low-power state can be made in only one state. Another method we developed is based on the time-indexed semi-Markov decision process (TISMDP) model. This model has wider applicability because it assumes that a decision to transition into a lower-power state can be made upon each event occurrence from any number of states. This model allows for transitions into low-power states from any state, but it is also more complex than our other approach. It is important to note that the results obtained by renewal model are guaranteed to match results obtained by TISMDP model, as both approaches give globally optimal solutions. We implemented our PM algorithms on two different classes of devices: two different hard disks and client-server wireless local area network systems such as the SmartBadge or a laptop. The measurement results show power savings ranging from a factor of 1.7 up to 5.0 with insignificant variation in performance.

One of the greatest challenges in a C/C++-based design methodology is efficiently mapping C/C++ models into hardware. Many networking and multimedia applications implemented in hardware or mixed hardware/software systems now use complex data structures stored in multiple memories, so many C/C++ features that were originally designed for software applications are now making their way into hardware. Such features include dynamic memory allocation and pointers for managing data. We present a solution for efficiently mapping arbitrary C code with pointers and malloc/free into hardware. Our solution, which fits current memory management methodologies, instantiates an application-specific hardware memory allocator coupled with a memory architecture. Our work also supports the resolution of pointers without restriction on the data structures. We present an implementation based on the SUIF framework along with case studies such as the realization of a video filter and an ATM segmentation engine.

Energy-efficient design of battery-powered systems demands optimizations in both hardware and software. We present a modular approach for enhancing instruction level simulators with cycle-accurate simulation of energy dissipation in embedded systems. Our methodology has tightly coupled component models thus making our approach more accurate. Performance and energy computed by our simulator are within a 5% tolerance of hardware measurements on the SmartBadge. We show how the simulation methodology can be used for hardware design exploration aimed at enhancing the SmartBadge with real-time MPEG video feature. In addition, we present a profiler that relates energy consumption to the source code. Using the profiler we can quickly and easily redesign the MP3 audio decoder software to run in real time on the SmartBadge with low energy consumption. Performance increase of 92% and energy consumption decrease of 77% over the original executable specification have been achieved.

Design reuse requires engineers to determine whether or not an existing block implements desired functionality. If a common high-level circuit model is used to represent components that are described at multiple levels of abstraction, comparisons between circuit specifications and a library of potential implementations can be performed accurately and quickly. A mechanism is presented for compactly specifying circuit functionality as polynomials at the word level. Polynomials can be used to represent circuits that are described at the bit level or arithmetically. Furthermore, in representing components as polynomials, differences in precision between potential implementations can be detected and quantified. We present a mechanism for constructing polynomial models for combinational and sequential circuits. Furthermore, we derive a means of approximating the functionality of nonpolynomial functions and determining a bound on the error of this approximation. These methods have been implemented in the POLYSYS synthesis tool and used to synthesize a JPEG encode block and infinite impulse response filter from a library of complex elements.

Dynamic power management saves power by shutting down idle devices. Several management algorithms have been proposed and demonstrated to be effective in certain applications. We quantitatively compare the power saving and performance impact of these algorithms on hard disks of a desktop and notebook computers. This paper has three contributions. First, we build a framework in Windows NT to implement power managers running realistic workloads and directly interacting with users. Second, we define performance degradation that reflects user perception. Finally, we compare power saving and performance of existing algorithms and analyze the difference.

One of the greatest challenges in C/C++-based design methodology is to efficiently map C/C++ models into hardware. Many of the networking and multimedia applications implemented in hardware or mixed hardware/software systems are making use of complex data structures stored in one or multiple memories. As a result, many of the C/C++ features which were originally designed for software applications are now making their way into hardware. Such features include dynamic memory allocation and pointers used to manage data. We present a solution for efficiently mapping arbitrary C code with pointers and malloc/free into hardware. Our solution fits current memory management methodologies. It consists of instantiating a hardware allocator tailored to an application and a memory architecture. Our work also supports the resolution of pointers without restriction on the data structures. An implementation using the SUIF framework is presented, followed by some case studies such as the realization of a video filter.

Summary form only given. Optimal power management policies for a laptop hard disk are obtained with a system model that can handle non-exponential interarrival times in the idle and the sleep states. the measurement results on a Sony Vaio laptop show that our policy has 1.7 times less power consumption as compared to the default Windows timeout policy with still high performance.

As more data processing functions are integrated into systems-on-chip, data path is becoming a critical part of the whole VLSI design. However, traditional physical design methodology can not satisfy the data path performance requirement because it has no knowledge of the data path bit-sliced structure. In this paper, an Abstract Physical Model (APM) is proposed to extract bit-slice regularity information from Data Flow Graph (DFG) and it is used for interconnect and congestion planning. A two step heuristic algorithm is introduced to optimize the linear placement of APM to satisfy both the wire length and routing track budget.

this paper presents a new approach for power reduction by taking a global, software-centric view. It analyzes the sources of power consumption: tasks that require services from hardware components. When a component is not used by any task, it can enter a sleeping state to save power. Operating systems have detailed information about tasks; therefore, OS is the best place for identifying hardware idleness and shutting down unused components. We implement this technique in Linux and show that it can save more than 50% power compared to traditional hardware-centric shutdown techniques.

No abstract available.

Portable wireless systems require long battery lifetime while still delivering high performance. The major contribution of this work is combining new it power management(PM) and it power control (PC) algorithms to trade off performance for power consumption at the system level in portable devices. First we present the formulation for the solution of the PM policy optimization based on renewaltheory. Next we present the formulation for power control (PC) of the wireless link that enables us to obtain further energy savings when thesystem is active. Finally, we discuss the measurements obtained for a set of PM and PC algorithms implemented for the WLAN card on a laptop. The PM policy we developed based on our renewal model consumes three times less power as compared to the default PM policy for the WLAN card with still high performance. Power control saves additional 53% in energy at same bit error rate. With both power control and power management algorithms in place, we observe on average a factor of six in power savings.

Portable systems require long battery lifetime while still delivering high performance. Dynamic power management (DPM) policies trade off the performance for the power consumption at the system level in portable devices. In this work we present the time-indexed SMDP model (TISMDP) that we use to derive optimal policy for DPM in portable systems. TISMDP model is needed to handle the non-exponential user request interarrival times we observed in practice. We use our policy to control power consumption on three different devices: the SmartBadge portable device [18], the Sony Vaio laptop hard disk and WLAN card. Simulation results show large savings for all three devices when using our algorithm. In addition, we measured the power consumption and performance of our algorithm and compared it with other DPM algorithms for laptop hard disk and WLAN card. The algorithm based on our TISMDP model has 1.7 times less power consumption as compared to the default Windows timeout policy for the hard disk and three times less power consumption as compared to the default algorithm for the WLAN card.

Power estimation for validation and sign-off is a critical step in the design process. In this phase, accuracy is a key requirement, but there are hard constraints on the time that can be dedicated to power estimation. Moreover, it is important to estimate the power dissipated by the system while running typical applications, i.e., extremely long streams of validation patterns provided by the designer. The power dissipated by digital systems under realistic input stimuli is not accurately described by a single average value, but by a waveform that shows how power consumption varies over time as the system responds to the inputs. In this paper, we face the problem of obtaining accurate power waveforms for combinational and sequential circuits under typical usage patterns. We propose a multilevel simulation engine that achieves high accuracy in estimating the time-domain power waveform, as well as the average power with high computational efficiency.

This tutorial surveys design methods for energy-efficient system-level design. We consider electronic sytems consisting of a hardware platform and software layers. We consider the three major constituents of hardware that consume energy, namely computation, communication, and storage units, and we review methods of reducing their energy consumption. We also study models for analyzing the energy cost of software, and methods for energy-efficient software design and compilation. This survery is organized around three main phases of a system design: conceptualization and modeling design and implementation, and runtime management. For each phase, we review recent techniques for energy-efficient design of both hardware and software.

We propose a technique for synthesizing low-power systems from behavioral specifications. We analyze the control flow of the specification model to detect mutually exclusive sections of the computation. A selectively-clocked interconnection of interacting FSMs is automatically generated and optimized, where each FSM controls the execution of one section of computation. Only one of the interacting FSMs is active for a high fraction of the operation time, while the others are idle and their clocks are stopped. Periodically, the active machine releases the control of the system to another FSM and stops. Our interacting FSM implementation achieves consistently lower power dissipation than the functionally equivalent monolithic implementation. On average, 37% power savings and 12% speedup are obtained, despite a 30% area overhead.

Register-transfer level (RTL) power estimation is a key feature for synthesis-based design flows. The main challenge in establishing a sound RTL power estimation methodology is the construction of accurate, yet efficient, models of the power dissipation of functional macros. Such models should be automatically built, and should produce reliable average power estimates. In this paper we propose a general methodology for building and tuning RTL power models. We address both hard macros (presynthesized functional blocks)and soft macros (functional units for which only a synthesizable HDL description is provided). We exploit linear regression and its nonparametric extensions to express the dependency of power dissipation on input and output activity. Bottom-up off-line characterization of regression-based power macromodels is discussed in detail. Moreover, we introduce a low overhead on-line characterization method for enhancing the accuracy of off-line characterization.

Dynamic power management (DPM) is a design methodology for dynamically reconfiguring systems to provide the requested services and performance levels with a minimum number of active components or a minimum load on such components. DPM encompasses a set of techniques that achieves energy-efficient computation by selectively turning off (or reducing the performance of) system components when they are idle (or partially unexploited). In this paper, we survey several approaches to system-level dynamic power management. We first describe how systems employ power-manageable components and how the use of dynamic reconfiguration can impact the overall power consumption. We then analyze DPM implementation issues in electronic systems, and we survey recent initiatives in standardizing the hardware/software interface to enable software-controlled power management of hardware components.

This paper presents a technique for glitch power minimization in combinational circuits. The total number of glitches is reduced by replacing some existing gates with functionally equivalent ones (called F-Gates) that can be "frozen" by asserting a control signal. A frozen gate cannot propagate glitches to its output. Algorithms for gate selection and clustering that maximize the percentage of filtered glitches and reduce the overhead for generating the control signals are introduced. A power-efficient CMOS implementation of F-Gates is also described. An important feature of the proposed method is that it can be applied in place directly to layout-level descriptions; therefore, it guarantees very predictable results and minimizes the impact of the transformation on circuit size and speed.

Article Free Access Share on Kernel-based power optimization of RTL components: exact and approximate extraction algorithms Authors: L. Benini Università di Bologna, Bologna, Italy 40136 Università di Bologna, Bologna, Italy 40136View Profile , G. De Micheli Stanford University, Stanford, CA Stanford University, Stanford, CAView Profile , E. Macii Politecnico di Torino, Torino, Italay 10129 Politecnico di Torino, Torino, Italay 10129View Profile , G. Odasso Politecnico di Torino, Torino, Italy 10129 Politecnico di Torino, Torino, Italy 10129View Profile , M. Poncino Politecnico di Torino, Torino, Italy 10129 Politecnico di Torino, Torino, Italy 10129View Profile Authors Info & Claims DAC '99: Proceedings of the 36th annual ACM/IEEE Design Automation ConferenceJune 1999 Pages 247–252https://doi.org/10.1145/309847.309922Published:01 June 1999Publication History 0citation244DownloadsMetricsTotal Citations0Total Downloads244Last 12 Months6Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper presents a methodology for cycle-accurate simulation of energy dissipation in embedded systems.The ARM Ltd. [l] instruction-level cycle-accurate simulator is extended with energy models for the processor, the L2 cache, the memory, the interconnect and the DC-DC converter.A SmartBadge, which can be seen as an embedded system consisting of StrongARM-processor, memory and the DC-DC converter, is used to evaluate the methodology with the Dhrystone benchmark.We compared performance and energy computed by our simulator with measurements in hardware and found them in agreement within a 5% tolerance.The simulation methodology was applied to design exploration for enhancing a SmartBadge with real-time MPEG feature.

This paper presents a technique for glitch power minimization in combinational circuits. The total number of glitches is reduced by replacing some existing gates with functionally equivalent ones (called F-gates) that can be "frozen" by asserting a control signal. A frozen gate cannot propagate glitches to its output. An important feature of the proposed method is that it can be applied in-place directly to layout-level descriptions; therefore, it guarantees very predictable results and minimizes the impact of the transformation on circuit size and speed.

Dynamic power management is a design methodology aiming at reducing power consumption of electronic systems, by performing selective shutdown of the idle system resources. The effectiveness of a power management scheme depends critically on an accurate modeling of the environment, and on the computation of the control policy. This paper presents two methods for characterizing nonstationary service requests by means of a prediction scheme based on sliding windows. Moreover; it describes how control policies for nonstationary models can be derived.

Software programming languages, such as C/C++, have been used as means for specifying hardware for quite a while. Different design methodologies have exploited the advantages of flexibility and fast simulation of models described with programming languages. At the same time, the mismatch (of software languages) in expressing power (for hardware systems) has caused several difficulties. In the recent past, novel approaches have helped in reducing the semantic gap, and in easing the creation of design flows that support system-level specifications in C/C++.

Methods for performing component matching by expressing an arithmetic specification and a bit-level description of an implementation as word-level polynomials have been demonstrated for combinational circuits. This representation allows the functionality of a specification and existing implementation to be compared. We present extensions to this basic method that allow polynomial models to be constructed for circuits that employ sequential elements as well as feedback. Furthermore, we derive a means of approximating the functionality of nonpolynomial functions and determining a bound on the error of this approximation. These methods are used to synthesize an infinite impulse response filter from a library of potential implementations.

Dynamic power management can be effective for designing low-power systems. In many systems, requests are clustered into sessions. This paper proposes an adaptive algorithm that can predict session lengths and shut down components between sessions to save power. Compared to other approaches, simulations show that this algorithm can reduce power consumption in hard disks with less impact on performance or reliability.

Dynamic power management (DPM) is a technique to reduce the power consumption of electronic systems by selectively shutting down idle components. The quality of the shutdown control algorithm (the power management policy) mostly depends on knowledge of the user's behavior, which in many cases is initially unknown or non-stationary. For this reason, DPM policies should be capable of adapting to changes in user behavior. In this paper, we present a novel DPM scheme based on idle period clustering and adaptive learning trees. We also provide a design guide for applying our technique to components with multiple sleep states. Experimental results show that our technique outperforms other advanced DPM schemes as well as simple time-out policies. The proposed approach shows little deviation of efficiency for various workloads having different characteristics, while other policies show that their efficiency changes drastically depending on the trace data characteristics. Furthermore, experimental evidence indicates that our workload learning algorithm is stable and has fast convergence.

Article Free Access Share on System-level power optimization: techniques and tools Authors: Luca Benini Universitá di Bologna, Dip. Elettronica Informatica Sistemistica Bologna, Italy 40136 Universitá di Bologna, Dip. Elettronica Informatica Sistemistica Bologna, Italy 40136View Profile , Giovanni De Micheli Stanford University, Computer Systems Laboratory, Stanford, CA Stanford University, Computer Systems Laboratory, Stanford, CAView Profile Authors Info & Claims ISLPED '99: Proceedings of the 1999 international symposium on Low power electronics and designAugust 1999 Pages 288–293https://doi.org/10.1145/313817.313957Published:17 August 1999Publication History 46citation847DownloadsMetricsTotal Citations46Total Downloads847Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this work we propose an exact technique for efficient computation of signal statistics during high-level synthesis for low-power of general control-dominated designs. Our approach does not require iterative simulation: simulation is performed once for all to collect boundary information that will be repeatedly exploited for computing signal statistics for alternative implementations.

Energy-ecient design of battery-powered embedded sys tems demands optimizations in both hardware and software In this work we leverage cycleaccurate energy consumption models to explore compiler and source code optimizations aimed at reducing energy consumption In addition we extend cycleaccurate architectural power simulation with battery models that provide battery lifetime estmates The enhanced simulator and software optimizations are used to study and optimize the power dissipation of Smart Badge a wearable system based on the ARM microproces sor developed by HP Laboratories We found that standart compiler optimizations give less than energy savings Source code optimizations are capable of up to \t energy savings In addition our analysis of battery lifetime for the

In high-performance systems, variable-latency units are often employed to improve the average throughput when the worst-case delay exceeds the cycle time. Traditionally, units of this type have been hand-designed. In this paper, we propose a technique for the automatic synthesis of variable-latency units that is applicable to large data-path modules. We define and study an optimization problem, timed supersetting, whose solution is at the kernel of the procedure for automatic generation of variable-latency units. We contribute a new algorithm for solving timed supersetting in the most difficult case, that is, when the timing behavior of the circuit is expressed through an accurate delay model. The proposed solution overcomes the computational limitations of previous approaches and its robustness is experimentally demonstrated by obtaining high-throughput, variable-latency implementations for all the largest circuits in the Iscas '85 and Iscas '89 benchmark suites, as well as for some realistic, high-performance arithmetic units.

Dynamic power management schemes (also called policies) reduce the power consumption of complex electronic systems by trading off performance for power in a controlled fashion, taking system workload into account. In a power-managed system it is possible to set components into different states, each characterized by performance and power consumption levels. The main function of a power management policy is to decide when to perform component state transitions and which transition should be performed, depending on system history, workload, and performance constraints. In the past, power management policies have been formulated heuristically. The main contribution of this paper is to introduce a finite-state, abstract system model for power-managed systems based on Markov decision processes. Under this model, the problem of finding policies that optimally tradeoff performance for power can be cast as a stochastic optimization problem and solved exactly and efficiently. The applicability and generality of the approach are assessed by formulating the Markov model and optimizing power management policies for several systems.

Recent results have shown that dynamic power management is effective in reducing the total power consumption of sequential circuits. In this paper, we propose a bottom-up approach for the automatic extraction and synthesis of dynamic power management circuitry starting from structural logic-level specifications. Our techniques leverage the compact BDD-based representation of Boolean and pseudo-Boolean functions to detect idle conditions where the clock can be stopped without compromising functional correctness. Moreover, symbolic techniques allow accurate probabilistic computations; in particular, they enable the use of non-equiprobable primary input distributions, a key step in the construction of models that match the behavior of real hardware devices with a high degree of fidelity. The results are encouraging, since power savings of up to 34% have been obtained on standard benchmark circuits.

We introduce a new sequential optimization paradigm based on the extraction of computational kernels, i.e., logic blocks whose behavior mimics the steady-state behavior of the original circuit. We present a procedure for the automatic extraction of such kernels directly from the gate-level description of the design. The advantage of this solution with respect to extraction algorithms based on STG analysis is that it can be applied to large circuits, since it does not require to manipulate the STG specification.

Dynamic power management schemes (also called policies) can be used to control the power consumption levels of electronic systems, by setting their components in different states, each characterized by a performance level and a power consumption. In this paper, we describe power-managed systems using a finite-state, stochastic model. Furthermore, we show that the fundamental problem of finding an optimal policy which maximizes the average performance level of a system, subject to a constraint on the power consumption, can be formulated as a stochastic optimization problem called policy optimization. Policy optimization can be solved exactly in polynomial time (in the number of states of the model). We implemented a policy optimization tool and tested the quality of the optimal policies on a realistic case study.

In order to automate design reuse, methods for composing system components must be developed. The goal of this research is to automate the process of generating interfaces between hardware subsystems. The algorithms presented here can be used to generate a cycle-accurate, synchronous interface between two hardware subsystems given an HDL model of each subsystem. These algorithms have been implemented in the POLARIS hardware composition tool and have been used to generate an interface between a MIPS microprocessor and the SRAM that comprises its secondary cache. Interface generation for the MIPS R4000 is described.

The power dissipated by system-level buses is the largest contribution to the global power of complex VLSI circuits. Therefore, the minimization of the switching activity at the I/O interfaces can provide significant savings on the overall power budget. This paper presents innovative encoding techniques suitable for minimizing the switching activity of system-level address buses. In particular, the schemes illustrated here target the reduction of the average number of bus line transitions per clock cycle. Experimental results, conducted on address streams generated by a real microprocessor, have demonstrated the effectiveness of the proposed methods.

We propose a new approach to RT-level power modeling for combinational macros, that does not require simulation-based characterization. A pattern-dependent power model for a macro is analytically constructed using only structural information about its gate-level implementation. The approach has three main advantages over traditional techniques: (i) it provides models whose accuracy does not depend on input statistics, (ii) it offers a wide range of tradeoff between accuracy and complexity, and (iii) it enables the construction of pattern-dependent conservative upper bounds.

In high-performance systems, variable-latency units are often employed to improve the average throughput when the worst-case delay exceeds the cycle time. Although such units have traditionally been hand-designed, recent results have shown that variable-latency units can be automatically generated. Unfortunately, the existing synthesis procedure has limited applicability due to its computational complexity. In this work, we define and study an optimization problem, timed supersetting, whose solution is at the kernel of the procedure for automatic generation of variable-latency units. We contribute a new algorithm for solving timed supersetting in the most difficult case, that is, when the timing behaviour of the circuits is expressed through an accurate delay model. The proposed solution overcomes the complexity limitation of previous approaches, and its robustness is experimentally demonstrated by obtaining high-throughput, variable-latency implementations for all the largest circuits in the Iscas'85 and Iscas'89 benchmark suites.

With the increased clock frequency of modern, high-performance processors (over 500 MHz, in some cases), limiting the power dissipation has become the most stringent design target. It is thus mandatory for processor engineers to resort to a large variety of optimization techniques to reduce the power requirements in the hot zones of the chip. In this paper, we focus on the power dissipated By the instruction fetch and decode logic, a portion of the processor architecture where a lot of capacitance switching normally takes place. We propose a methodology for determining an encoding of the instruction set that guarantees the minimization of the number of bit transitions occurring inside the registers of the pipeline stages involved in instruction fetching and decoding. The assignment of the binary patterns to the op-codes is driven by the statistics concerning instruction adjacency collected through instruction-level simulation of typical software applications; therefore, the technique is best exploited when applied to encode the instruction set of core processors and microcontrollers, since components of these types ore commonly used to execute fixed portions of machine code within embedded systems. We illustrate the effectiveness of the methodology through the experimental data we have obtained on an existing microprocessor.

4flamiCP0wer ~~asemeflr ~a desisnmethodology airnins at con!rollins pe@or- rnance and power lmek of disital circreiLcand ~stems, with the soul of eztendins Ihe metonomowoperation time of batte~-powered~stems, providing srac~lpefornmnce degradation when supply ener~is limited, and adaptins power dtiipation to sat~em,ironmental constraints.We survg ~stem-level dynarnicpower rnanasement techniques.We$nt analyze idlene~de:ectimr and shutdown mechanti for idle hardware resources and we review industtilsrandarh for operatins~~em-baedpower mnasement.We describe w~tem-l~elstOchastic madekfor thepowerlpefonnance behaviorof~stems.Uk an-al}ze different rrrodelins assumptforrsarrdwe ducu theirvalidi~andseneraliy.tit, we descn,be methohfor detenninins optirnumpmver manasementstratesies andafso describe Vuriou validation metho~that can be empbyed to assess the effecttieness of power-~flaseable architectures andtheuociatedpawer-manasementschews. hhoductionDe5gnmetiodo10~wforene~y-efitient~skm-leveldmign are r~iving aninm~ingly large uttmtion.The motivations for such intertit =e rood in the wfdqrmd use of portableelectronic appfirmm (e.g., cellular phones, laptop mmputers, etc.) and in the concerns about the environment impact of elwtronic systems [21] (whether mobile or not).System-1eveldesign must stike the bdanm between providing high service leveh to the users wbile crstifing power ditipation.frrother words, we n~d to incrmsc the energetic efficiencyof electronic systems, as it has been done, by other mms, with other types of engines.Electronic systems are heteroseneoasin nature, by mmbining dighrdwith rmdog circuitry,using semiconductor(e.g., RAhl, WSH memorfcs)and eIectro-mcchrnrid (e.g., disks) stomge resourw, as well as electr~opticaf (e.g., displays) human interfaces.Power nranfigementmust address al) types of resour% io a system The power brddown for a well-known laptop computer [34] shows shah on avemge, 36% of the toti power is consumed by the di~lay, 18% by the hard-disk dtie @D), 1S% by the wireless local area network ~interfa~7% by nms-cdtfd components @eybomd,mouse etc.), and only 21% by digiti ~1 circuitry, mainly memory and central processing unit (@~.Reducing the power in the digitaf mmponerrtsof this laptop by IOXwould reduce the overcRpower conmmption by l= than 20%.hweringsystem-Iecel pow,erwnmmption, wM1epreservingadequatesemiw and pecforrnanceIevek, is a dif6cu1ttask hd~, reducing system pecfocrnance(e.g., by using lower clock rates) is not a desirable option when considering the incs~ingly more elabomta software apphcatfon programs for camputers and fmturea of portable elecmonicdevices.On the other hand, present systems have seved componentswhich are not uhfized at dl times.\Vben such componentsare idle, they cmrbe put in slmp states with reduced (or null) power consumption, with a firrdtd (or null) impact on perfomrmce.~namicpow.rrnana~ement is a design methodologyaiming at conuol~ng perfomrance and power leirels of digitrd circuits and systerrrs,by exploiting the id!en~ of their components.A system is provided with a power rnanaser that monitors the ovetil system and component stare and controfs state trantitinns.The mntrol pro.cedure is dlcd power magement policy.Power rnsnagera a be implemented in P-ion to make digitrd or hard copi~of aU or part of this work for peramraf or &sroom use fs granted without fee pmvidd that copies m not made or disti~ utd for profit or co~er@ advantage and that copies bear this notice and the M station on the &t page To copy oth-, to repubUsh, to ~t on sesvm or to redfstriiute to fists, r-= prior s@c moss =d/or a fee.ICCAD98.San]osc.~USA t CSL -SWord Universi~ hardwme or in softwar% depending on system architecture and constraints.JVfren considering genemf-pupse computer systems, the most na~implementation of the power nranageris softwme-based.h particular, the operatins ~~esn (OS) is the software layer where the manager a be implementedbmt Operatingsystem disected power management (OSPhO is actively supported by industry-tiven standmdi~tion efforts such as Mcrosoft's OnNowinitiative [39] and the Advmrced Configuration and PowerInte&ace (A~D standard proposed by ktel, hficrosoft and Toshiba [3~.JVebeheve that dynamic power mrmagementis a viable approach to reduce power cnnsumprionof Inrge-sde systems under perforrrranmmnstim, becmrsesignificant power waste is ~ociated with idle r=ourm and because of its geneti appfimbiUty.Note that support for dynarrrfcpower management must be provided by the oved system ocganimtion,and system architec~often envisionsystem partitions that enable power nraoagemenLhloreover,system componentsshould bepower manaseable,i.e., the rmmagersfrouldbeable to control their state nf operation.hfarrageablecomponen~ m be buildbyexploitingseved specifictechniques,such as supplyvoltage,frquency and activity control [1].NcerflN to say, dynamic pmverrnrmagernentshouldbe mmplemenrcdby specific chip-level design technfqua for power reduction at the arcbitectrrd level [9], at the ~, Ingic nod circuit Ievek [20, ~and by custotid devim and implementation Sechnologim[2S]. Howe\rer,in this survey we focus exclusively on dynamic power rnanagemenL\Ve mrtsider 6rst system-level design issues, such as idleness detection and shutdmvn mechanisms for idle resourw.JVe review the OnNow and A~I standmds, as well as previous work in the as= of power msrragemenL NLKLwe review system-level modehng techniques, and introduce stochastic models for the pov~er/pefimmanwbehavior of systems.\Ve nnd~different modefingmsumptiorss and we discuss their vtidfty.\Ve then consider a working model, for which optiti poficiesabecnmputed,aodw)e discuss howpcdfcicsa beimplementedin electrode systems.ht but not IeasGwe describe seved methods for vaffdatingthe pohcies, based on simulation at different abstmction levefs.JVemncludeby stressing the need for ~teak to support rtrodelidentification, pohcy optitition and tidation for dynarzricaflypower-mmagti systems.

Finding disjunct ive decompositions is an important technique to realize compact logic nettvorks.Simple dzsjun cttce decomposition is a b~ic and useful concept, that extracts a single-output subblock function ~vhose input variable set is disjunctive from the other part.This paper presents a method for finding simple disjunct ive decompositions by generating irredundant sum-ofproducts forms and applying factorization.?fre prove that all simple disjunctive decompositions can be extract ed in our method, namely, all possible decompositions are included in the factored logic net;vorks.Experiment al results sho~v that our method can efficiently extract all the simple disjunct ive decompositions of the large-scale functions.Our result clarifies the relationship bet Iveen the functional decomposition method and the t~vo-level logic factorization method.

k designers may model tied software-hardware systems using a subset of C or C++, we prtient SpC, a solution to synth=ize and optimize a C model with pointers.In hardware, a pointer is not ody the address of data in memory, but it may *O reference mtitiple variablw mapped to registers, ports or wire.Pointer anrdysis is used to fid the point-to-set of each pointer in the program.b thii paper, we address the problem of synthesizing and optimizing pointers to multiple variablm and array elements.Temporary variablti are defined to optimize loads and stores by minimizing the number of live variabl=.The combinational logic can *O be reduced by encoding the pointers vdu=.A implementation using the SUE framework is presented, followed by some case studies such as the synthwis of a 2D ~CT.

Component reuse requires designers to determine whether or not an e.risting component implements desired fimctionalip.ff a common structure is used to represent components that are described at multiple levels of abstraction, compan.sonsbetween circuit specifications and a libra~of potential implementations can be peflormed quickly.A mechanism is presented for compactly specifying circuit flmctionality as polynomials at the word level.Polynomials can be used to represent circuits that are described at the bit level or arithmetically.Furthermore, in representing components as polynomials, differences in precision behveen potential implementations can be detected and quanti>ed.

This paper introduces a novel optimization paradigm for increasing the throughput of digital systems. The basic idea consists of transforming fixed-latency units into variable-latency ones that run with a faster clock cycle. The transformation is fully automatic and can be used in conjunction with traditional design techniques to improve the overall performance of speed-critical units. In addition, we introduce procedures for reducing the area overhead of the modified units, and we formulate an algorithm for automatically restructuring the controllers of the data paths in which variable-latency units have been introduced. Results, obtained on a large set of benchmark circuits, show an average throughput improvement exceeding 27%, at the price of a modest area increase (less than 8% on average).

This paper presents an aggressive optimization technique targeting combinational logic circuits. Starting from an initial implementation mapped on a given technology library, the network is optimized by finding optimal replacements to clusters of two or more cells at the same time. We leverage a generalized matching algorithm that finds symbolically all possible matching assignments of library cells to a multioutput network specified by a Boolean relation and automatically selects the minimum cost replacement. The remapping technique can be applied to area minimization under delay constraints, power minimization under delay constraints, and unconstrained delay minimization. Our remapping tool is based on a fully symbolic algorithm geared toward flexibility and robustness. The tool has been tested on a large set of benchmark circuits. The quality of the results proves the practical relevance of the technique. We obtain sizable improvements in (i) speed (6% in average, up to 20.7%), (ii) area under speed constraints (13.7% in average, up to 29.5%), and (iii) power under speed constraints (22.3% in average, up to 38.1%).

This paper presents a solution to the problem of reducing the power dissipated by a digital system containing an intellectual proprietary core processor which repeatedly executes a special-purpose program. The proposed method relies on a novel, application-dependent low-power address bus encoding scheme. The analysis of the execution traces of a given program allows an accurate computation of the correlations that may exist between blocks of bits in consecutive patterns; this information can be successfully exploited to determine an encoding which sensibly reduces the bus transition activity. Experimental results, obtained on a set of special-purpose applications, are very satisfactory; reductions of the bus activity up to 64.8% (41.8% on average) have been achieved over the original address streams. In addition, data concerning the quality and the performance of the automatically synthesized encoding/decoding circuits, as well as the results obtained for a realistic core-based design, indicate the practical usefulness of the proposed power optimization strategy.

In microprocessor-based systems, large power savings can be achieved through reduction of the transition activity of the on- and off-chip buses. This is because the total capacitance being switched when a voltage change occurs on a bus line is usually sensibly larger than the capacitive load that must be charged/discharged when internal nodes toggle. In this paper, we propose an encoding scheme which is suitable for reducing the switching activity on the lines of an address bus. The technique relies on the observation that, in a remarkable number of cases, patterns traveling onto address buses are consecutive. Under this condition it may therefore be possible, for the devices located at the receiving end of the bus, to automatically calculate the address to be received at the next clock cycle; consequently, the transmission of the new pattern can be avoided, resulting in an overall switching activity decrease. We present analytical and experimental analyses showing the improved performance of our encoding scheme when compared to both binary and Gray addressing schemes, the latter being widely accepted as the most efficient method for address bus encoding. We also propose power and timing efficient implementations of the encoding and the decoding logic, and we discuss the applicability of the technique to real microprocessor-based designs.

The power dissipated by digital systems under realistic input stimuli is not accurately described by a single average value, but by a waveform that shows how power consumption varies over time as the system responds to the inputs. We face the problem of obtaining accurate power waveforms for combinational and sequential circuits under typical usage patterns. We propose a multi level simulation engine that achieves high accuracy in estimating the average power as well as the time domain power waveform with high computational efficiency.

We present a tool that performs real time analysis and priority assignment for software tasks in a mixed hardware software system with a custom run time scheduler. The tasks in hardware and software have precedence constraints, resource constraints, relative timing constraints, and a rate constraint. A dynamic programming formulation assigns the static priorities such that a hard real time rate constraint can be predictably met. We describe the task control/data flow extraction, runtime scheduler implementation, real time analysis and priority scheduler template. We show how our approach fits into an overall tool flow and target architecture. Finally, we conclude with a sample application of the system to a design example.

We present a novel approach for post-mapping optimization. We exploit the concept of generalised matching, a technique that finds symbolically all possible matching assignments of library cells to a multi-output network specified by a Boolean relation. Several objectives are targeted: area minimization under delay constraints; power minimization under delay constraints; and unconstrained delay minimization. We describe the theory of generalized matching and the algorithmic optimization required for its efficient and robust implementation. A tool based on generalized matching has been implemented and tested on large examples of the MCNC'91 benchmark suite. We obtain sizable improvements in: speed (6% in average, up to 20.7%); area under speed constraints (13.7% an average, up to 29.5%); and power under speed constraints (22.3% in average, up to 38.1%).

Article Free Access Share on System-level power optimization of special purpose applications: the beach solution Authors: Luca Benini Stanford University, Computer Systems Laboratory, Stanford, CA Stanford University, Computer Systems Laboratory, Stanford, CAView Profile , Giovanni De Micheli Stanford University, Computer Systems Laboratory, Stanford, CA Stanford University, Computer Systems Laboratory, Stanford, CAView Profile , Enrico Macii Politecnico di Torino, Dip. di Automatica e Informatica, Torino, Italy 10129 Politecnico di Torino, Dip. di Automatica e Informatica, Torino, Italy 10129View Profile , Massimo Poncino Politecnico di Torino, Dip. di Automatica e Informatica, Torino, Italy 10129 Politecnico di Torino, Dip. di Automatica e Informatica, Torino, Italy 10129View Profile , Stefano Quer Politecnico di Torino, Dip. di Automatica e Informatica, Torino, Italy 10129 Politecnico di Torino, Dip. di Automatica e Informatica, Torino, Italy 10129View Profile Authors Info & Claims ISLPED '97: Proceedings of the 1997 international symposium on Low power electronics and designAugust 1997 Pages 24–29https://doi.org/10.1145/263272.263277Published:01 August 1997Publication History 33citation259DownloadsMetricsTotal Citations33Total Downloads259Last 12 Months17Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper we propose a novel approach to synthesis for low power under tight timing constraints. Starting from a mapped netlist, we apply a powerful generalized matching algorithm based on Boolean relations that allows us to find reduced-power replacements for clusters of more than one cell. Our approach is robust and scales well with circuit size it has been tested on all largest examples of the MCNC91 benchmark suite. In average, power is reduced by more than 17% with no speed penalty compared to minimum delay implementations. Area is virtually unchanged.

Embedded systems consist of interacting hardware and software components that must deliver a specific functionality under constraints on relative timing of their actions. We describe operation delay and execution rate constraints, that are useful in the context of embedded systems. A delay constraint bounds the operation delay or specifies any of the thirteen possible constraints between the intervals of execution of a pair of operations. A rate constraint bounds the rate of execution of an operation and may be specified relative to the control flow in the system functionality. We present constraint propagation and analysis techniques to determine satisfaction of imposed constraints by a given system implementation. In contrast to previous purely analytical approaches on restricted models or statistical performance estimation based on runtime data, we present a static analysis in presence of conditionals and loops with the help of designer assists. The constraint analysis algorithms presented here have been implemented in a cosynthesis system, VULCAN, that allows the embedded system designer to interactively evaluate the effect of performance constraints on hardware-software implementation tradeoffs for a given functionality. We present examples to demonstrate the application and utility of the proposed techniques.

When binding a logic network to a set of cells, a fundamental problem is recognizing whether a cell can implement a portion of the network. Boolean matching means solving this task using a formalism based on Boolean algebra. In its simplest form, Boolean matching can be posed as a tautology check. We review several approaches to Boolean matching as well as to its generalization to cases involving don't care conditions and its restriction to specific libraries such as those typical of anti-fuse based FPGAs. We then present a general formulation of Boolean matching supporting multiple-output logic cells.

In this paper, we present a new gate-level approach to power and current simulation. We propose a symbolic model of complementary metal-oxide-semiconductor (CMOS) gates to capture the dependence of power consumption and current flows on input patterns and fan-in/fan-out conditions. Library elements are characterized and their models are used during event-driven logic simulation to provide power information and construct time-domain current waveforms. We provide both global and local pattern-dependent estimates of power consumption and current peaks (with accuracy of 6 and 10% from SPICE, respectively), while keeping performance comparable with traditional gate-level simulation with unit delay. We use VERILOG-XL as simulation engine to grant compatibility with design tools based on Verilog HDL. A Web-based user interface allows our simulator (PPP) to be accessed through the Internet using a standard web browser.

We describe a paradigm for integrating EDA tools running on distributed platforms under a common user interface. We focus on interactive remote execution more than on simple information retrieval. Minimum support is required on the user side to access the features offered by a large and diverse set of tools: the user's WWW browser is the interface for all interactions. Integrating new tools in the environment is a straightforward process that does not require any effort from the end users. The learning curve is extremely short because the well-known user interface provided by the WWW browser is exploited. PPP is a prototype we implemented to show the feasibility of WWW-based tool integration. We describe the features of PPP, its architecture and its implementation.

We present a new gate-level approach to current simulation. We use a symbolic model of current pulses that takes accurately into account the dependence on the switching conditions. We then construct current waveforms during event-driven logic simulation by means of pulse composition. We obtain satisfying accuracy on time-domain current waveforms and on peak current estimates, while maintaining performance comparable with traditional gate-level simulation.

The presence of large current peaks on the power and ground lines is a serious concern for designers of synchronous digital circuits. Current peaks are caused by the simultaneous switching of highly loaded clock lines and by the signal propagation through the sequential logic elements. In this work we propose a methodology for reducing the amplitude of the current peaks. This result is obtained by clock skew optimization. We propose an algorithm that determines the clock arrival time at each flip-flop in order to minimize the current peaks while respecting timing constraint. Our results on benchmark circuits show that current peaks can be reduced by more than a factor of two without penalty on cycle time and average power dissipation. Our methodology is therefore well-suited for low-power systems with reduced supply voltage, where low noise margins are a primary concern.

The automatic synthesis of low power finite-state machines (FSM's) with gated clocks relies on efficient algorithms for synthesis and optimization of dedicated clock-stopping circuitry. We describe a new transformation for incompletely specified Mealy-type machines that makes them suitable for gated-clock implementation with a limited increase in complexity. The transformation is probabilistic-driven, and identifies highly-probable idle conditions that will be exploited for the optimal synthesis of the logic block that controls the local clock of the FSM. We formulate and solve a new logic optimization problem, namely, the synthesis of a subfunction of a Boolean function that is minimal in size under a constraint on its probability to be true. We describe the relevance of this problem for the optimal synthesis of gated clocks. A prototype tool has been implemented and its performance, although influenced by the initial structure of the FSM, shows that sizable power reductions can be obtained using our technique.

In this paper, we present a novel modeling style and control synthesis technique for system-level specifications that are better described as a set of concurrent descriptions, their synchronizations, and constraints. The proposed synthesis procedure considers the degrees of freedom introduced by the concurrent models and by the environment in order to satisfy the design constraints. Synthesis is divided into two phases. In the first phase, the original specification is translated into an algebraic system, for which complex control-flow constraints and quantifiers of the design are introduced. In the second phase, we translate the algebraic formulation into a finite-state representation, and we derive an optimal control-unit implementation for each individual concurrent part. In the implementation of the controllers from the finite-state representation, we use flexible objective functions, which allow designers to better control the goals of the synthesis tool, and thus incorporate as much as possible their knowledge about the environment and the design.

We introduce a framework for synthesis of behavioral models in which design information is represented using an automaton model. This model offers the advantage of supporting different constraints (e.g., timing, resource, synchronization, etc.) with a uniform formalism. The set of all feasible execution traces (schedules) is constructed and traversed using efficient BDD-based implicit state-traversal techniques. As an application example of this formalism, we present a novel scheduling/control-generation algorithm under environmental constraints where both the design and constraints are represented using automata. We present an algorithm that generates a minimum-latency schedule and a control unit representation. This approach is able to exploit degrees of freedom among interacting components of a multimodule system during scheduling, and is well suited for system-level design, where component encapsulation and interfacing are important.

This paper presents a set of new techniques for the optimization of multiple-level combinational Boolean networks. We describe first a technique based upon the selection of appropriate multiple-output subnetworks (consisting of so-called compatible gates) whose local functions can be optimized simultaneously. We then generalize the method to optimize larger and more arbitrary subsets of gates, called unate subsets. Because simultaneous optimization of local functions can take place, our methods are more powerful and general than Boolean optimization methods using don't cares, where only single-gate optimization can be performed. In addition, our methods represent a more efficient alternative to Boolean relations-based optimization procedures because the problem can be modeled by a unate covering problem instead of the more difficult binate covering problem. The method is implemented in program ACHILLES and compares favorably to SIS.>

In this paper we present a method for modeling don't cares at high-level in a form that can be used by sequential logic synthesis. Behavior is specified by a set of concurrent, interacting processes. Each process is described formally by its set of execution traces and represented by an /spl omega/-automaton. This type of specification is formally precise and allows the inclusion of don't cares by allowing multiple execution traces for a given input. Moreover, it allows us to cast the synthesis problem into a language containment problem, and to provide a formal description of these don't cares. We have developed a prototype synthesis system based on this framework, targeting the synthesis of the control portion of a circuit. Starting from a hardware description language Hardware, a specification is expressed in terms of a set of interconnected /spl omega/-automata. We demonstrate the feasibility of the approach by showing the possibility of traversing the state space of the specification automata.>

Abstract- Thts paper prmenta a set of new teelmiques for the nptimtzattmr of multiple-level combtnattorud Boolean networks. Such teehntquea are breed on a temporary tmnsfonnatlon of the networ& tnto an internally unste one. We descrtbe tirat a teebnique baaed upon the seleetion of appropriate multiple-output subnetwo~s (consisting of s~c.slled comprztible gates) whose local functions can be opthntzed sttmdtaneoualy. We then generalize the method to larger subsets of tmate gates. Beeauae shntdtaneoua opttmizatton of local functions ean take place, our methods are more powerful and general than Boolean optimization methods using don t cares, where only single-gate opti. ndzatton am be performed. In addttton, our methods rvpmaent a more efficient alternative to Boolean rvlations-b=d opttndzation procedures beeauae the problem can be mndeled by a mate covertng problem tnstead of the more difficult binate eoverhtg problem. The method ts implemented in program achilks and compares favorably to ~S. 1

Article Automatic technology mapping for generalized fundamental-mode asynchronous designs Share on Authors: Polly Siegel View Profile , Giovanni De Micheli View Profile , David Dill View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 61–67https://doi.org/10.1145/157485.164573Online:01 July 1993Publication History 41citation249DownloadsMetricsTotal Citations41Total Downloads249Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Hierarchical descriptions of combinational circuits often contain apparent loops. Since it may be difficult to distinguish apparent loops from actual loops, it is useful to construct models of combinational circuits that can handle cyclic dependencies. We show that Boolean relations are inadequate for this purpose, and define a ternary model that solves the problem. We use the model to characterize exact solutions to a broad class of substitution and rectification problems. The theory cleanly handles network transformations that might introduce cyclic dependencies.

A unified framework for the specification and computation of don't care conditions for combinational and synchronous multiple-level digital circuits is presented. Circuits are characterized in terms of graphs, logic functions and don't care conditions induced by the external and internal interconnections. The replacement of a gate in a synchronous logic network is modeled by a perturbation of the corresponding logic function, and it is shown that the don't care conditions for the gate optimization represent the bound on this perturbation. Algorithms to compute such don't care conditions in both the combinational and synchronous case are presented. The implementation of the algorithms and the experimental results are discussed.>

Algorithms and a computer-aided design tool, called Ceres, for technology mapping of both completely specified and incompletely specified logic networks are introduced. The algorithms are based on Boolean techniques for matching, i.e., for the recognition of the equivalence between a portion of a network and library cells. A novel matching algorithm, using ordered binary decision diagrams, is described. It exploits the notion of symmetry to achieve higher computational efficiency. A matching technique that takes advantage of don't-care conditions by means of a compatibility graph is also described. A strategy for timing-driven technology mapping, based on iterative improvement, is presented. Experimental results indicate that these techniques generate good-quality solutions and require short run times and limited memory space.>

Algorithms to automatically realize delays in combinational logic circuits to achieve wave pipelining are presented. The algorithms adjust gate speeds and insert a minimal number of active delay elements to balance input-output path lengths in a circuit. For both normal and wave-pipelined circuits, the algorithms also optimally minimize power under delay constraints. The authors analyze the algorithms and comment on their implementation. They report experimental results, including the design and testing of a 63-bit population counter in CML bipolar technology. A brief analysis of circuit technologies shows that CML and super-buffered ECL without stacked structures are well suited for wave pipelining because they have uniform delay. Static CMOS and ordinary ECL including stacked structures and emitter-followers do have some delay variations. A high degree of wave pipelining is still possible in those technologies if special design techniques are followed.>

The scope of most high-level synthesis efforts to date has been at the level of a single behavioral model represented as a control/data-flow graph. The communication between concurrently executing processes and its requirements in terms of timing and resources have largely been neglected. This restriction limits the applicability of most existing approaches for complex system designs. This paper describes a methodology for the synthesis of interfaces in concurrent systems under detailed timing constraints. The authors model interprocess communication using blocking and nonblocking messages. They show how the relationship between messages over time can be abstracted as a constraint graph that can be extracted and used during synthesis. They describe a novel technique called interface matching that minimizes the interface cost by scheduling each process with respect to timing information of other processes communicating with it. By scheduling the completion of operations, some blocking communication can be converted to nonblocking while ensuring the communication remains valid. To further reduce hardware costs, the authors describe the synthesis of interfaces on shared physical media. They show how this sharing can be increased through rescheduling and serialization of the communication. In addition to systematically reducing the interface synchronization cost, this approach permits analysis on the timing consistency of interprocess communication.>

For the synthesis of ASIC design that interface with external signals and events, timing constraints and operations with unbounded delays, i.e. delays unknown at compile time, must be considered. The authors present a relative scheduling formulation that supports operations with fixed and unbounded delays. The start time of an operation is specified in terms of offsets from the set of unbounded delay operations called anchors. The authors analyze a property, called well-posedness, of timing constraints. It is used to identify consistency of constraints in the presence of unbounded delay operations. The authors present an algorithm that will transform an ill-posed constraint graph into a minimally serialized well-posed constraint graph, if one exists. The anchors are then checked for redundancy, and they identify the minimum set of anchors that are required in computing the start time. They present an algorithm that schedules the operations relative to the anchors and yields a minimum schedule that satisfies the timing constraints, or detects whether no schedule exists, in polynomial time. They describe the generation of control logic from the resulting relative schedule.>

We describe a new approach for technology mapping of electri-

Article Free Access Share on Control optimization based on resynchronization of operations Authors: David C. Ku Center for Integrated Systems, Stanford University, Stanford, CA Center for Integrated Systems, Stanford University, Stanford, CAView Profile , Dave Filo Center for Integrated Systems, Stanford University, Stanford, CA Center for Integrated Systems, Stanford University, Stanford, CAView Profile , Giovanni De Micheli Center for Integrated Systems, Stanford University, Stanford, CA Center for Integrated Systems, Stanford University, Stanford, CAView Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991 Pages 366–371https://doi.org/10.1145/127601.127696Published:01 June 1991Publication History 6citation123DownloadsMetricsTotal Citations6Total Downloads123Last 12 Months3Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A novel approach to logic synthesis of digital synchronous circuits is presented. A model for synchronous circuits that supports logic transformations aimed at optimizing the circuit performance is presented. Previous synthesis approaches attacked this problem by separating the combinational logic from the registers and by applying circuit transformations to the combinational component only. It is shown how to optimize concurrently the circuit equations and the register position by a set of algorithms based on logic transformations. Experimental results on benchmark circuits are reported.>

Scheduling techniques are used in high-level synthesis of integrated circuits. Traditional scheduling techniques assume fixed execution delays for the operations. For the synthesis of ASIC designs that interface with external signals and events, operations with unbounded delays, i.e. delays unknown at compile time, must also be considered. We present a relative scheduling technique that supports operations with fixed and unbounded delays. The technique satisfies the timing constraints imposed by the user, which places bounds between the activation of operations. We analyze a novel property called well-posedness of timing constraints that is used to identify consistency of constraints in the presence of unbounded delay operations, and present an approach to relative scheduling that yields a minimum schedule that satisfies the constraints, or detects if no schedule exists, in polynomial time.

An algorithm is presented that computes exact or approximate observability don't care (ODC) sets for a multiple-level combinatorial network. The proposed algorithms are efficient because they use only local information. A method for deriving the equivalence classes of a Boolean relation from the ODC sets is then proposed. Experimental results on computing ODC sets are reported.>

A partitioning technique is presented of functional models that are used in conjunction with high-level synthesis of digital synchronous circuits. The partitioning goal is to synthesize multi-chip systems from one behavioral description that satisfy both chip area constraints and an overall latency timing constraint. There are three major advantages to using partitioning techniques at the functional abstraction level. First, scheduling techniques can be applied concurrently to partitioning. Therefore, partitioning under timing constraints, and in particular under latency constraints, can be performed. Second, the functional model captures large hardware systems with fewer objects (than at the logic netlist abstraction level), making the partitioning algorithm more efficient. Third, hardware sharing tradeoffs can be considered. Hardware partitioning is formulated as a hypergraph partitioning problem. Algorithms for hardware partitioning are presented and experimental results are reported.>

Wave pipelining is a technique for pipelining digital systems that can increase the clock frequency without increasing the number of storage elements. Due to limits and variations in fabrication, the clock frequency can be increased by a factor of 2 to 3 by using the best available design methods. The authors present algorithms that will equalize delays automatically by inserting a minimal number of active delay elements to lengthen short paths. This method can be combined with delay balancing by adjusting gate speeds to design wave-pipelined circuits.>

The authors describe a high performance 32-bit binary adder designed at Stanford University. Measurements indicate that the adder computes the sum of two numbers (and a carry) in 2.1 ns and consumes 900 mW, using a power-supply voltage of -4.5 V. The adder is implemented using silicon emitter-coupled-logic circuitry with 0.5-V output swings. The high performance is a result of high-speed logic/technology and a special addition algorithm which results in an adder with a maximum of three levels of logic from any input to any output. The maximum fanout on any signal is eight input loads, the maximum number of inputs on any gate is five, and the maximum number of WIRE-OR outputs is eight.>

A novel algorithm for generating complex CMOS gates from Boolean factored forms is presented. It uses a hierarchical composition of cells corresponding to the subexpressions of a Boolean factored form. Composition rules that allow for constructing the gates in linear time are derived. Cell width/height tradeoffs are made possible to ease pitch-matching. The algorithm has been coded in a pair of programs, called Castor and Pollux. The programs have been used to generate moderately complex layouts, consisting of circuits having up to a few thousand transistors. They can also be used to automatically generate a library of logic gates.>

The quality of the design of large-scale integrated circuits is determined by such figures of merit as silicon area, power consumption, and switching-time performance. We address here the problem of the automatic synthesis of digital circuits with the goal of achieving high-performance designs. We assume we are given an intermediate circuit representation that optimizes area and/or power. We use timing optimization techniques to improve the circuit performance, possibly at the expense of the other figures of merit. We consider general classes of digital circuits, with a given partition into registers, combinational blocks, and I/O ports. Circuit performance is related to the worst-case propagation delay of signals between two register boundaries. In this context, circuit performance optimization is equivalent to minimizing the critical path delay through the combinational circuits. We assume a multiple-level implementation of the combinational logic, by means of an interconnection of logic gates implementing arbitrary multiple-input, single-output logic functions. We consider dynamic CMOS implementation of the logic gates, operating in the domino mode. We present a global approach to timing performance optimization, which involves operations at the logic, topological, and physical level of abstraction of the circuit. In particular, at the logic level, we look for optimal structures of multiple-level combinational networks. At the topological level, we search for the optimal positions of gates or groups of gates. At the physical design level, we optimize MOS device sizes. The algorithms are described, together with their implementation and the interface to the Yorktown Silicon Compiler system, which is an automated synthesis system described in [7]. The results of applying timing-performance optimization to a 32-bit microprocessor design are reported.

This paper presents a method for the optimal synthesis of combinational and sequential circuits implemented by two-level logic macros, such as programmable logic arrays. Optimization consists of finding representations of switching functions corresponding to minimal-area implementations. The design of optimization is based on two steps: symbolic minimization and constrained encoding. Symbolic minimization yields an encoding-independent sum of products representation of a switching function which is minimal in the number of product terms. The minimal symbolic representation is then encoded into a compatible Boolean representation. The algorithms for symbolic minimization and the related encoding problems are described. The computer implementation and the experimental results are then presented.

In the above paper, a misprint in a figure made a critical example incomprehensible.

Computer-Aided synthesis of sequential functions of VLSI systems, such as microprocessor control units, must include design optimization procedures to yield area-effective circuits. We model sequential functions as deterministic synchronous Finite State Machines (FSM's), and we consider a regular and structured implementation by means of Programmable Logic Arrays (PLA's) and feedback registers. State assignment, i.e., binary encoding of the internal states of the finite state machine, affects substantially the silicon area taken by such an implementation. Several state assignment techniques have been proposed in the past. However, to the best of our knowledge, no Computer-Aided Design tool is in use today for an efficient encoding of control logic. We propose an algorithm for optimal state assignment. Optimal state assignment is based on an innovative strategy: logic minimization of the combinational component of the finite state machine is applied before state encoding. Logic minimization is performed on a symbolic (code independent) description of the finite state machine. The minimal symbolic representation defines the constraints of a new encoding problem, whose solutions are the state assignments that allow the implementation of the PLA with at most as many product-terms as the cardinality of the minimal symbolic representation. In this class, an optimal encoding is one of minimal length satisfying these constraints. A heuristic algorithm constructs a solution to the constrained encoding problem. The algorithm has been coded in a computer program, KISS, and tested on several examples of finite state machines. Experimental results have shown that the method is an effective tool for designing finite state machines.

In the above-named paper [ibid., vol. CAD-2, pp. 151-167, July 1983], a misprint makes the correct understanding of the constrained multiple folding problem and its solutions almost impossible. In page 162, the lines between the 23rd row from the top and the 6th from the bottom (We state the column folding with ordered connection-row . ... and the ordered folding set O = {(C8, C9)}. should be moved to page 163 immediately after Example 5.3.1 and before Remark 5.3. In addition, Fig. 17 in Example 5.3.2 should be replaced by Fig. 16 and Fig. 16 of Example 5.3.1 should be replaced by Fig. 17.