No description available.

Energy minimization has become an ever more important concern in the design of very large scale integrated circuits (VLSI). In recent years, approximate computing, which is based on the idea of trading off computational accuracy for improved energy efficiency, has attracted significant attention. Applications that are both compute-intensive and error-tolerant are most suitable to adopt approximation strategies. This includes digital signal processing, data mining, machine learning or search algorithms. Such approximations can be achieved at several design levels, ranging from software, algorithm and architecture, down to logic or transistor levels. This dissertation investigates two research threads for the derivation of approximate digital circuits at the logic level: 1) modeling and synthesis of fundamental arithmetic building blocks; 2) automated techniques for synthesizing arbitrary approximate logic circuits under general error specifications. The first thread investigates elementary arithmetic blocks, such as adders and multipliers, which are at the core of all data processing and often consume most of the energy in a circuit. An optimal strategy is developed to reduce energy consumption in timing-starved adders under voltage over-scaling. This allows a formal demonstration that, under quadratic error measures prevalent in signal processing applications, an adder design strategy that separates the most significant bits (MSBs) from the least significant bits (LSBs) is optimal. An optimal conditional bounding (CB) logic is further proposed for the LSBs, which selectively compensates for the occurrence of errors in the MSB part. There is a rich design space of optimal adders defined by different CB solutions. The other thread considers the problem of approximate logic synthesis (ALS) in two-level form. ALS is concerned with formally synthesizing a minimum-cost approximate Boolean function, whose behavior deviates from a specified exact Boolean function in a well-constrained manner. It is established that the ALS problem un-constrained by the frequency of errors is isomorphic to a Boolean relation (BR) minimization problem, and hence can be efficiently solved by existing BR minimizers. An efficient heuristic is further developed which iteratively refines the magnitude-constrained solution to arrive at a two-level representation also satisfying error frequency constraints. To extend the two-level solution into an approach for multi-level approximate logic synthesis (MALS), Boolean network simplifications allowed by external don't cares (EXDCs) are used. The key contribution is in finding non-trivial EXDCs that can maximally approach the external BR and, when applied to the Boolean network, solve the MALS problem constrained by magnitude only. The algorithm then ensures compliance to error frequency constraints by recovering the correct outputs on the sought number of error-producing inputs while aiming to minimize the network cost increase. Experiments have demonstrated the effectiveness of the proposed techniques in deriving approximate circuits. The approximate adders can save up to 60% energy compared to exact adders for a reasonable accuracy. When used in larger systems implementing image-processing algorithms, energy savings of 40% are possible. The logic synthesis approaches generally can produce approximate Boolean functions or networks with complexity reductions ranging from 30% to 50% under small error constraints. / text

In the quest to understand cell behavior and cure genetic diseases such as cancer, the fundamental approach being taken is undergoing a gradual change. It is becoming more acceptable to view these diseases as an engineering problem, and systems engineering approaches are being deployed to tackle genetic diseases. In this light, we believe that logic synthesis techniques can play a very important role. Several techniques from the field of logic synthesis can be adapted to assist in the arguably huge effort of modeling cell behavior, inferring biological networks, and controlling genetic diseases. Genes interact with other genes in a Gene Regulatory Network (GRN) and can be modeled as a Boolean Network (BN) or equivalently as a Finite State Machine (FSM). As the expression of genes deter- mine cell behavior, important problems include (i) inferring the GRN from observed gene expression data from biological measurements, and (ii) using the inferred GRN to explain how genetic diseases occur and determine the ”best” therapy towards treatment of disease. We report results on the application of logic synthesis techniques that we have developed to address both these problems. In the first technique, we present Boolean Satisfiability (SAT) based approaches to infer the predictor (logical support) of each gene that regulates melanoma, using gene expression data from patients who are suffering from the disease. From the output of such a tool, biologists can construct targeted experiments to understand the logic functions that regulate a particular target gene. Our second technique builds upon the first, in which we use a logic synthesis technique; implemented using SAT, to determine gene regulating functions for predictors and gene expression data. This technique determines a BN (or family of BNs) to describe the GRN and is validated on a synthetic network and the p53 network. The first two techniques assume binary valued gene expression data. In the third technique, we utilize continuous (analog) expression data, and present an algorithm to infer and rank predictors using modified Zhegalkin polynomials. We demonstrate our method to rank predictors for genes in the mutated mammalian and melanoma networks. The final technique assumes that the GRN is known, and uses weighted partial Max-SAT (WPMS) towards cancer therapy. In this technique, the GRN is assumed to be known. Cancer is modeled using a stuck-at fault model, and ATPG techniques are used to characterize genes leading to cancer and select drugs to treat cancer. To steer the GRN state towards a desirable healthy state, the optimal selection of drugs is formulated using WPMS. Our techniques can be used to find a set of drugs with the least side-effects, and is demonstrated in the context of growth factor pathways for colon cancer.

Em portas lógicas CMOS, tanto o atraso de propagação como a curva de saída estão fortemente ligados ao número de dispositivos PMOS e NMOS conectados em série nas redes de carga e descarga, respectivamente. O estilo lógico ‘standard CMOS’ é, em geral, otimizado para um dos planos, apresentando então o arranjo complementar no plano oposto. Consequentemente, o número mínimo de transistores em série não é necessariamente alcançado. Neste trabalho, apresenta-se um método para encontrar o menor número de chaves (transistores) em série necessários para se implementar portas lógicas complexas CMOS. Um novo estilo lógico CMOS, derivado de tal método, é então proposto e comparado ao estilo CMOS convencional através do uso de uma ferramenta de caracterização comercial. A caracterização elétrica de conjuntos de funções de 3 a 6 entradas foi realizada para avaliar o novo método, apresentando significativos ganhos em velocidade, sem perdas em dissipação de potência ou em área. / Both the propagation delay and the output slope in CMOS gates are strongly related to the number of stacked PMOS and NMOS devices in the pull-up and pull-down networks, respectively. The standard CMOS logic style is usually optimized targeting one logic plane, presenting then the complemented topology in the other one. As a consequence, the minimum number of stacked transistors is not necessarily achieved. In this work, a method to find the lower bound of stacked switches (transistors) in CMOS complex gates is presented. A novel CMOS logic style, derived from such method, is then proposed and compared to conventional CMOS style through a commercial cell characterizer. Electrical characterization of sets of 3- to 6-input functions was done in order to evaluate the new method. Significant gains in propagation delay were obtained without penalty in power dissipation or area.

Em portas lógicas CMOS, tanto o atraso de propagação como a curva de saída estão fortemente ligados ao número de dispositivos PMOS e NMOS conectados em série nas redes de carga e descarga, respectivamente. O estilo lógico ‘standard CMOS’ é, em geral, otimizado para um dos planos, apresentando então o arranjo complementar no plano oposto. Consequentemente, o número mínimo de transistores em série não é necessariamente alcançado. Neste trabalho, apresenta-se um método para encontrar o menor número de chaves (transistores) em série necessários para se implementar portas lógicas complexas CMOS. Um novo estilo lógico CMOS, derivado de tal método, é então proposto e comparado ao estilo CMOS convencional através do uso de uma ferramenta de caracterização comercial. A caracterização elétrica de conjuntos de funções de 3 a 6 entradas foi realizada para avaliar o novo método, apresentando significativos ganhos em velocidade, sem perdas em dissipação de potência ou em área. / Both the propagation delay and the output slope in CMOS gates are strongly related to the number of stacked PMOS and NMOS devices in the pull-up and pull-down networks, respectively. The standard CMOS logic style is usually optimized targeting one logic plane, presenting then the complemented topology in the other one. As a consequence, the minimum number of stacked transistors is not necessarily achieved. In this work, a method to find the lower bound of stacked switches (transistors) in CMOS complex gates is presented. A novel CMOS logic style, derived from such method, is then proposed and compared to conventional CMOS style through a commercial cell characterizer. Electrical characterization of sets of 3- to 6-input functions was done in order to evaluate the new method. Significant gains in propagation delay were obtained without penalty in power dissipation or area.

Em portas lógicas CMOS, tanto o atraso de propagação como a curva de saída estão fortemente ligados ao número de dispositivos PMOS e NMOS conectados em série nas redes de carga e descarga, respectivamente. O estilo lógico ‘standard CMOS’ é, em geral, otimizado para um dos planos, apresentando então o arranjo complementar no plano oposto. Consequentemente, o número mínimo de transistores em série não é necessariamente alcançado. Neste trabalho, apresenta-se um método para encontrar o menor número de chaves (transistores) em série necessários para se implementar portas lógicas complexas CMOS. Um novo estilo lógico CMOS, derivado de tal método, é então proposto e comparado ao estilo CMOS convencional através do uso de uma ferramenta de caracterização comercial. A caracterização elétrica de conjuntos de funções de 3 a 6 entradas foi realizada para avaliar o novo método, apresentando significativos ganhos em velocidade, sem perdas em dissipação de potência ou em área. / Both the propagation delay and the output slope in CMOS gates are strongly related to the number of stacked PMOS and NMOS devices in the pull-up and pull-down networks, respectively. The standard CMOS logic style is usually optimized targeting one logic plane, presenting then the complemented topology in the other one. As a consequence, the minimum number of stacked transistors is not necessarily achieved. In this work, a method to find the lower bound of stacked switches (transistors) in CMOS complex gates is presented. A novel CMOS logic style, derived from such method, is then proposed and compared to conventional CMOS style through a commercial cell characterizer. Electrical characterization of sets of 3- to 6-input functions was done in order to evaluate the new method. Significant gains in propagation delay were obtained without penalty in power dissipation or area.

According to Moore's law, Integrated Chips (IC) doubles its capacity every 18 months. This causes an exponential increase of the available area, and hence,the complexity of modern digital designs. This consistent enormous gross challenges different research areas in Electronic Design Automation (EDA). Thus, various EDA applications such as equivalence checking, model checking, Automatic Test Pattern Generation (ATPG), functional Bi-decomposition, and technology mapping need to keep pace with these challenges. In this thesis, we are concerned with improving the quality and performance of different EDA algorithms particularly in area of hardware verification and synthesis. First, we introduce algorithms to manipulate Reduced Ordered Binary Decision Diagrams (ROBDD) on multi-core machines. In order to perform multiple BDD operations concurrently, our algorithm uses a breadth-first search (BFS). As ROBDD algorithms are memory-intensive, maintaining locality of data is an important issue. Therefore, we propose the usage of Hopscotch hashing technique for both Unique Table and BFS Queues to improve the construction time of ROBDD on the parallel platform. Hopscotch hashing technique not only improves the locality of the manipulating data, but also provides a way to cache recently performed BDD operation. Consequently, The time and space usage can be traded off. Secondly, we used static implications to enhance the performance of SAT-based Bounded Model Checking (BMC) problem. we propose a parallel deduction engine to efficiently utilize low-cost off-shelf multi-core processors to compute the implications. With this engine, we can significantly reduce the computational processing time in analyzing the deduced implications. Secondly, we formulate the clause filter problem as an elegant set-covering problem. Thirdly, we propose a novel greedy algorithm based on the Johnson's algorithm to find the optimal set of clauses that would accelerate BMC solution. Thirdly, we proposed a novel synthesis paradigm to achieve timing-closure called Timing-Aware CUt Enumeration (TACUE). In TACUE, optimization is conducted through three aspects: First, we propose a new divide-and-conquer strategy that generates multiple sub-cuts on the critical parts of the circuit. Secondly, cut enumeration have been applied in two cutting strategies. In the topology-aware cutting strategy, we preserve the general topology of the circuit by applying TACUE in only self-contained cuts. Meanwhile, the topology-masking cutting strategy investigates circuit cuts beyond their current topology. Thirdly, we proposed an efficient parallel synthesis framework to reduce computation time for synthesizing TACUE sub-cuts. We conducted experiments on large and difficult industrial benchmarks. Finally, we proposed the first scalable SAT-based approaches for Observability Dont Care (ODC) clock gating. Moreover we intelligently choose those inductive invariants candidates such that their validation will benefit the purpose in clock-gating-based low-power design. / Ph. D.

Indiana University-Purdue University Indianapolis (IUPUI) / In this thesis, we investigated the 7 nm FinFET technology for its delay-power product performance. In our study, we explored the ASAP7 library from Arizona State University, developed in collaboration with ARM Holdings. The FinFET technology was chosen since it has a subthreshold slope of 60mV/decade that enables cells to function at 0.7V supply voltage at the nominal corner. An emphasis was focused on characterizing the Non-Ideal effects, delay variation, and power for the FinFET device. An exhaustive analysis of the INVx1 delay variation for different operating conditions was also included, to assess the robustness. The 7nm FinFET device was then employed into 6T SRAM cells and 16 function ALU. The SRAM cells were approached with advanced multi-corner stability evaluation. The system-level architecture of the ALU has demonstrated an ultra-low power system operating at 1 GHz clock frequency.

No description available.

Functional decomposition aims at finding efficient representations for Boolean functions. It is used in many applications, including multi-level logic synthesis, formal verification, and testing. This dissertation presents novel heuristic algorithms for functional decomposition. These algorithms take advantage of suitable representations of the Boolean functions in order to be efficient. The first two algorithms compute simple-disjoint and disjoint-support decompositions. They are based on representing the target function by a Reduced Ordered Binary Decision Diagram (BDD). Unlike other BDD-based algorithms, the presented ones can deal with larger target functions and produce more decompositions without requiring expensive manipulations of the representation, particularly BDD reordering. The third algorithm also finds disjoint-support decompositions, but it is based on a technique which integrates circuit graph analysis and BDD-based decomposition. The combination of the two approaches results in an algorithm which is more robust than a purely BDD-based one, and that improves both the quality of the results and the running time. The fourth algorithm uses circuit graph analysis to obtain non-disjoint decompositions. We show that the problem of computing non-disjoint decompositions can be reduced to the problem of computing multiple-vertex dominators. We also prove that multiple-vertex dominators can be found in polynomial time. This result is important because there is no known polynomial time algorithm for computing all non-disjoint decompositions of a Boolean function. The fifth algorithm provides an efficient means to decompose a function at the circuit graph level, by using information derived from a BDD representation. This is done without the expensive circuit re-synthesis normally associated with BDD-based decomposition approaches. Finally we present two publications that resulted from the many detours we have taken along the winding path of our research.