The Experts below are selected from a list of 1893 Experts worldwide ranked by ideXlab platform
Luis Entrena - One of the best experts on this subject based on the ideXlab platform.
-
Combining retiming and sequential redundancy addition and removal for sequential Logic Optimization
2006Co-Authors: Enrique San Millan, Luis Entrena, Luis Mengibar, Michael GarcíaAbstract:In this paper a new Logic Optimization method for sequential synchronous circuits is introduced. For this purpose the current main approaches, "Retiming and Resynthesis" and "Redundancy Addition and Removal" are considered. These techniques have some advantages and limitations that have been theoretically proven by several authors. The goal of the new Optimization method is to combine these two techniques to get the best of each one. In particular the paper is focused on area Optimization. The algorithm proposed in this paper is efficient and delivers interesting Optimization results.
-
DSD - On the Optimization power of redundancy addition and removal for sequential Logic Optimization
Proceedings Euromicro Symposium on Digital Systems Design, 2001Co-Authors: Enrique San Millan, Luis Entrena, J.a. EspejoAbstract:The paper attempts to determine the capabilities of existing redundancy addition and removal (SRAR) techniques for Logic Optimization of sequential circuits. To this purpose, we compare this method with the retiming and resynthesis (RaR) techniques. For the RaR case the set of possible transformations has been established by relating them to STG transformations by other authors. Following these works, we first formally demonstrate that Logic transformations provided by RaR are covered by SRAR as well. Then we also show that SRAR is able to identify transformations that cannot be found by RaR. This way we prove the higher potential of the sequential redundancy addition and removal over the retiming and resynthesis techniques.
-
IOLTW - Logic Optimization of unidirectional circuits with structural methods
Proceedings Seventh International On-Line Testing Workshop, 2001Co-Authors: Luis Entrena, Celia López, E. Olias, E. San Millan, J.a. EspejoAbstract:Self-checking design based on unordered codes requires that the target circuit is transformed into a unidirectional circuit. Techniques for the design of unidirectional circuits have been proposed. However, in general, multilevel Logic Optimization techniques cannot be directly applied because they do not guarantee the unidirectional property is preserved. In this paper we show how structural Logic Optimization methods can be successfully constrained for the Optimization of unidirectional circuits. Experimental results show that the area overhead produced by making a circuit unidirectional can be largely reduced and the circuits can be optimized to a smaller area than the original non-unidirectional benchmarks, on average.
-
DATE - Generalized reasoning scheme for redundancy addition and removal Logic Optimization
Proceedings Design Automation and Test in Europe. Conference and Exhibition 2001, 2001Co-Authors: J.a. Espejo, Luis Entrena, E. San Millan, E. OliasAbstract:In this work a generalization of the structural Redundancy Addition and Removal (RAR) Logic Optimization method is presented. New concepts based on the functional description of the nodes in the network are introduced to support this generalization. Necessary and sufficient conditions to identify all the possible structural expansions are given for the general case of multiple variable expansion. Basic nodes are no longer restricted to simple gates and can be any function of any size. With this generalization, an incremental mechanism to perform structural transformations involving any number of variables can be applied in a very efficient manner. Experimental results are presented that illustrate the efficiency of our scheme.
-
ASP-DAC - Functional extension of structural Logic Optimization techniques
Proceedings of the 2001 conference on Asia South Pacific design automation - ASP-DAC '01, 2001Co-Authors: J.a. Espejo, Luis Entrena, Enrique San Millan, E. OliasAbstract:This work provides a generalization of structural Logic Optimization methods to general Boolean networks. With this generalization, the nodes of the network are no longer restricted to simple gates and can be functions of any size. Within this framework, we present necessary and sufficient conditions to identify all the possible functional expansions of a node that allow one to eliminate a wire elsewhere in the network. These conditions are also given for the case of multiple variable expansion, providing an incremental mechanism to perform functional transformations involving any number of variables that can be applied in a very efficient manner. On the other band, we will show in this paper that relevant simplifications can be obtained when this framework is applied to the particular case of AND-OR-NOT networks, resulting in important savings in the computational effort. When compared to previous approaches, the experimental results show an important reduction in the number of computations required.
Kwangting Cheng - One of the best experts on this subject based on the ideXlab platform.
-
ASP-DAC - Logic Optimization by an improved sequential redundancy addition and removal techniques
Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM) - ASP-DAC '95, 1995Co-Authors: Uwe Glässer, Kwangting ChengAbstract:Logic Optimization methods using automatic test pattern generation (ATPG) techniques such as redundancy addition and removal have recently been proposed. We generalize this approach for synchronous sequential circuits. We proposed several new sequential transformations which can be efficiently identified and used for optimizing large designs. One of the new transformations involves adding redundancies across time frames in a sequential circuit. We also suggest a new transformation which involves adding redundancies to block initialization of other wires. We use efficient sequential ATPG techniques to identify more sequential redundancies for either addition or removal. We have implemented a sequential Logic Optimization system based upon this approach. We show experimental results to demonstrate that this approach is both CPU time efficient and memory efficient and can optimize large sequential designs significantly.
-
combinational and sequential Logic Optimization by redundancy addition and removal
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1995Co-Authors: Luis Entrena, Kwangting ChengAbstract:This paper presents a method for multilevel Logic Optimization for combinational and synchronous sequential circuits. The circuits are optimized through iterative addition and removal of redundancies. Adding redundant wires to a circuit may cause one or many existing irredundant wires and/or gates to become redundant. If the amount of added redundancies is less than the amount of created redundancies, the transformation of adding followed by removing redundancies will result in a smaller circuit. Based upon the Automatic Test Pattern Generation (ATPG) techniques, the proposed method can efficiently identify those wires for addition that would create more redundancies elsewhere in the network. Experiments on ISCAS-85 combinational benchmark circuits show that best results are obtained for most of them. For sequential circuits, experimental results on MCNC FSM benchmarks and ISCAS-89 sequential benchmark circuits show that a significant amount of area reduction can be achieved beyond combinational Optimization and sequential redundancy removal. >
-
sequential Logic Optimization by redundancy addition and removal
International Conference on Computer Aided Design, 1993Co-Authors: Luis Entrena, Kwangting ChengAbstract:This paper presents a method of multi-level Logic Optimization for combinational and synchronous sequential Logic. The circuits are optimized through iterative addition and removal of redundancies. Among the large number of possible connections that can be added, the proposed method can efficiently identify those connections that would create more redundancies and, thus, would result in a smaller network. This is done with the use of combinational and sequential ATPG techniques based up the concept of mandatory assignments. Experiments on ISCAS-85 combinational benchmark circuits show that best results are obtained for most of them. For sequential circuits, experimental results on MCNC FSM benchmarks and ISCAS-89 sequential benchmark circuits show that a significant amount of area reduction can be achieved beyond combinational Optimization and sequential redundancy removal.
-
ICCAD - Sequential Logic Optimization by redundancy addition and removal
Proceedings of 1993 International Conference on Computer Aided Design (ICCAD), 1993Co-Authors: Luis Entrena, Kwangting ChengAbstract:This paper presents a method of multi-level Logic Optimization for combinational and synchronous sequential Logic. The circuits are optimized through iterative addition and removal of redundancies. Among the large number of possible connections that can be added, the proposed method can efficiently identify those connections that would create more redundancies and, thus, would result in a smaller network. This is done with the use of combinational and sequential ATPG techniques based up the concept of mandatory assignments. Experiments on ISCAS-85 combinational benchmark circuits show that best results are obtained for most of them. For sequential circuits, experimental results on MCNC FSM benchmarks and ISCAS-89 sequential benchmark circuits show that a significant amount of area reduction can be achieved beyond combinational Optimization and sequential redundancy removal.
-
multi level Logic Optimization by redundancy addition and removal
European Design Automation Conference, 1993Co-Authors: Kwangting Cheng, Luis EntrenaAbstract:A multilevel Logic Optimization technique is presented that is a generalization of redundancy removal and Boolean resubstitution. The network is optimized through iterative addition and deletion of redundant connections. With the use of the connection fault model, the problem of identifying connections that can be made without affecting the network's functionality is converted into the problem of identifying redundant connection faults. Efficient test generation algorithms can thus be applied directly. Techniques that can efficiently locate redundant wires and/or nodes after adding a redundant wire are also proposed. Experiment results on MCNC benchmark circuits show that, on average, a 16% reduction in gate count and a 20% reduction in connection count can be achieved at a low computational cost. The suggested technique can also be applied for timing Optimization. >
Alberto Sangiovannivincentelli - One of the best experts on this subject based on the ideXlab platform.
-
synthesis of finite state machines Logic Optimization
1997Co-Authors: Tiziano Villa, Robert K Brayton, Alberto SangiovannivincentelliAbstract:Synthesis of Finite State Machines: Logic Optimization is the second in a set of two monographs devoted to the synthesis of Finite State Machines (FSMs). The first volume, Synthesis of Finite State Machines: Functional Optimization, addresses functional Optimization, whereas this one addresses Logic Optimization. The result of functional Optimization is a symbolic description of an FSM which represents a sequential function chosen from a collection of permissible candidates. Logic Optimization is the body of techniques for converting a symbolic description of an FSM into a hardware implementation. The mapping of a given symbolic representation into a two-valued Logic implementation is called state encoding (or state assignment) and it impacts heavily area, speed, testability and power consumption of the realized circuit. The first part of the book introduces the relevant background, presents results previously scattered in the literature on the computational complexity of encoding problems, and surveys in depth old and new approaches to encoding in Logic synthesis. The second part of the book presents two main results about symbolic minimization; a new procedure to find minimal two-level symbolic covers, under face, dominance and disjunctive constraints, and a unified frame to check encodability of encoding constraints and find codes of minimum length that satisfy them. The third part of the book introduces generalized prime implicants (GPIs), which are the counterpart, in symbolic minimization of two-level Logic, to prime implicants in two-valued two-level minimization. GPIs enable the design of an exact procedure for two-level symbolic minimization, based on a covering step which is complicated by the need to guarantee encodability of the final cover. A new efficient algorithm to verify encodability of a selected cover is presented. If a cover is not encodable, it is shown how to augment it minimally until an encodable superset of GPIs is determined. To handle encodability the authors have extended the frame to satisfy encoding constraints presented in the second part. The covering problems generated in the minimization of GPIs tend to be very large. Recently large covering problems have been attacked successfully by representing the covering table with binary decision diagrams (BDD). In the fourth part of the book the authors introduce such techniques and extend them to the case of the implicit minimization of GPIs, where the encodability and augmentation steps are also performed implicitly. Synthesis of Finite State Machines: Logic Optimization will be of interest to researchers and professional engineers who work in the area of computer-aided design of integrated circuits.
-
irredundant sequential machines via optimal Logic synthesis
Hawaii International Conference on System Sciences, 1990Co-Authors: Srinivas Devadas, A.r. Newton, H K T, Alberto SangiovannivincentelliAbstract:It is shown that optimal sequential Logic synthesis can produce irredundant, fully testable finite-state machines. Synthesizing a sequential circuit from a state-transition-graph description involves the steps of state minimization, state assignment, and Logic Optimization. It is also shown that 100% testability can be ensured without the addition of extra Logic and without constraints on the state assignment and Logic Optimization. There is no area/performance penalty associated with this approach. This technique can be used in conjunction with previous approaches to ensure that the synthesized machine is easily testable. Given a state-transition-graph specification, a Logic-level automation that is fully testable for all single stuck-at faults in the combinational Logic without access to the memory elements can be synthesized. These procedures represent an alternative to a scan-design methodology, without the latter's usual area and performance penalty. >
-
irredundant sequential machines via optimal Logic synthesis
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1990Co-Authors: Srinivas Devadas, A.r. Newton, H K T, Alberto SangiovannivincentelliAbstract:It is shown that optimal sequential Logic synthesis can produce irredundant, fully testable finite-state machines. Synthesizing a sequential circuit from a state transition graph description involves the steps of state minimization, state assignment, and Logic Optimization. Previous approaches to producing fully and easily testable sequential circuits have involved the use of extra Logic and constraints on state assignments and Logic Optimization. Here it is shown that 100% testability can be ensured without the addition of extra Logic and without constraints on the state assignment and Logic Optimization. Unlike previous synthesis approaches to ensuring fully testable machines, there is no area/performance penalty associated with this approach. This technique can be used in conjunction with previous approaches to ensure that the synthesized machine is easily testable. Given a state-transition-graph specification, a Logic-level automaton that is fully testable for all single stuck-at faults in the combinational Logic without access to the memory elements is synthesized. >
Srinivas Devadas - One of the best experts on this subject based on the ideXlab platform.
-
Sequential Logic Optimization for Low Power Using
1998Co-Authors: Input-disabling Precomputation Architectures, Srinivas Devadas, A. GhoshAbstract:Precomputation is a recently proposed Logic Optimization technique which selectively disables the inputs of a Logic circuit, thereby reducing switching activity and power dissipation, without changing Logic functionality. In sequential precomputation, output values required in a particular clock cycle are selectively precomputed one clock cycle earlier, and the original Logic circuit is "turned off" in the succeeding clock cycle. We target a general precomputation architecture for sequential Logic circuits, and show that it is significantly more powerful than the architecture previously treated in the literature. The very power of this architecture makes the synthesis of precomputation Logic a challenging problem. We present a method to automatically synthesize precomputa- tion Logic for this architecture. Up to 66% reduction in power dissipation is possible using the proposed architecture. For many examples, the proposed architecture result in significantly less power dissipation than previously developed methods.
-
Sequential Logic Optimization for low power using input-disabling precomputation architectures
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998Co-Authors: José Monteiro, Srinivas Devadas, A. GhoshAbstract:Precomputation is a recently proposed Logic Optimization technique which selectively disables the inputs of a Logic circuit, thereby reducing switching activity and power dissipation, without changing Logic functionality. In sequential precomputation, output values required in a particular clock cycle are selectively precomputed one clock cycle earlier, and the original Logic circuit is "turned off" in the succeeding clock cycle. We target a general precomputation architecture for sequential Logic circuits, and show that it is significantly more powerful than the architecture previously treated in the literature. The very power of this architecture makes the synthesis of precomputation Logic a challenging problem. We present a method to automatically synthesize precomputation Logic for this architecture. Up to 66% reduction in power dissipation is possible using the proposed architecture. For many examples, the proposed architecture result in significantly less power dissipation than previously developed methods.
-
precomputation based sequential Logic Optimization for low power
IEEE Transactions on Very Large Scale Integration Systems, 1994Co-Authors: Mazhar Alidina, José Monteiro, Srinivas Devadas, A. Ghosh, Marios C PapaefthymiouAbstract:We address the problem of optimizing Logic-level sequential circuits for low power. We present a powerful sequential Logic Optimization method that is based on selectively precomputing the output Logic values of the circuit one clock cycle before they are required, and using the precomputed values to reduce internal switching activity in the succeeding clock cycle. We present two different precomputation architectures which exploit this observation. The primary Optimization step is the synthesis of the precomputation Logic, which computes the output values for a subset of input conditions. If the output values can be precomputed, the original Logic circuit can be "turned off" in the next clock cycle and will have substantially reduced switching activity. The size of the precomputation Logic determines the power dissipation reduction, area increase and delay increase relative to the original circuit. Given a Logic-level sequential circuit, we present an automatic method of synthesizing precomputation Logic so as to achieve maximal reductions in power dissipation. We present experimental results on various sequential circuits. Up to 75% reductions in average switching activity and power dissipation are possible with marginal increases in circuit area and delay. >
-
precomputation based sequential Logic Optimization for low power
International Conference on Computer Aided Design, 1994Co-Authors: Mazhar Alidina, José Monteiro, Srinivas Devadas, A. Ghosh, Marios C PapaefthymiouAbstract:We address the problem of optimizing Logic-level sequential circuits for low power. We present a powerful sequential Logic Optimization method that is based on selectively precomputing the output Logic values of the circuit one clock cycle before they are required, and using the precomputed values to reduce internal switching activity in the succeeding clock cycle. We present two different precomputation architectures which exploit this observation. We present an automatic method of synthesizing precomputational Logic so as to achieve maximal reductions in power dissipation. We present experimental results on various sequential circuits. Up to 75% reductions in average switching activity and power dissipation are possible with marginal increases in circuit area and delay.
-
ICCAD - Precomputation-based sequential Logic Optimization for low power
IEEE ACM International Conference on Computer-Aided Design, 1994Co-Authors: Mazhar Alidina, José Monteiro, Srinivas Devadas, A. Ghosh, Marios C PapaefthymiouAbstract:We address the problem of optimizing Logic-level sequential circuits for low power. We present a powerful sequential Logic Optimization method that is based on selectively precomputing the output Logic values of the circuit one clock cycle before they are required, and using the precomputed values to reduce internal switching activity in the succeeding clock cycle. We present two different precomputation architectures which exploit this observation. We present an automatic method of synthesizing precomputational Logic so as to achieve maximal reductions in power dissipation. We present experimental results on various sequential circuits. Up to 75% reductions in average switching activity and power dissipation are possible with marginal increases in circuit area and delay.
J.a. Espejo - One of the best experts on this subject based on the ideXlab platform.
-
DSD - On the Optimization power of redundancy addition and removal for sequential Logic Optimization
Proceedings Euromicro Symposium on Digital Systems Design, 2001Co-Authors: Enrique San Millan, Luis Entrena, J.a. EspejoAbstract:The paper attempts to determine the capabilities of existing redundancy addition and removal (SRAR) techniques for Logic Optimization of sequential circuits. To this purpose, we compare this method with the retiming and resynthesis (RaR) techniques. For the RaR case the set of possible transformations has been established by relating them to STG transformations by other authors. Following these works, we first formally demonstrate that Logic transformations provided by RaR are covered by SRAR as well. Then we also show that SRAR is able to identify transformations that cannot be found by RaR. This way we prove the higher potential of the sequential redundancy addition and removal over the retiming and resynthesis techniques.
-
IOLTW - Logic Optimization of unidirectional circuits with structural methods
Proceedings Seventh International On-Line Testing Workshop, 2001Co-Authors: Luis Entrena, Celia López, E. Olias, E. San Millan, J.a. EspejoAbstract:Self-checking design based on unordered codes requires that the target circuit is transformed into a unidirectional circuit. Techniques for the design of unidirectional circuits have been proposed. However, in general, multilevel Logic Optimization techniques cannot be directly applied because they do not guarantee the unidirectional property is preserved. In this paper we show how structural Logic Optimization methods can be successfully constrained for the Optimization of unidirectional circuits. Experimental results show that the area overhead produced by making a circuit unidirectional can be largely reduced and the circuits can be optimized to a smaller area than the original non-unidirectional benchmarks, on average.
-
DATE - Generalized reasoning scheme for redundancy addition and removal Logic Optimization
Proceedings Design Automation and Test in Europe. Conference and Exhibition 2001, 2001Co-Authors: J.a. Espejo, Luis Entrena, E. San Millan, E. OliasAbstract:In this work a generalization of the structural Redundancy Addition and Removal (RAR) Logic Optimization method is presented. New concepts based on the functional description of the nodes in the network are introduced to support this generalization. Necessary and sufficient conditions to identify all the possible structural expansions are given for the general case of multiple variable expansion. Basic nodes are no longer restricted to simple gates and can be any function of any size. With this generalization, an incremental mechanism to perform structural transformations involving any number of variables can be applied in a very efficient manner. Experimental results are presented that illustrate the efficiency of our scheme.
-
ASP-DAC - Functional extension of structural Logic Optimization techniques
Proceedings of the 2001 conference on Asia South Pacific design automation - ASP-DAC '01, 2001Co-Authors: J.a. Espejo, Luis Entrena, Enrique San Millan, E. OliasAbstract:This work provides a generalization of structural Logic Optimization methods to general Boolean networks. With this generalization, the nodes of the network are no longer restricted to simple gates and can be functions of any size. Within this framework, we present necessary and sufficient conditions to identify all the possible functional expansions of a node that allow one to eliminate a wire elsewhere in the network. These conditions are also given for the case of multiple variable expansion, providing an incremental mechanism to perform functional transformations involving any number of variables that can be applied in a very efficient manner. On the other band, we will show in this paper that relevant simplifications can be obtained when this framework is applied to the particular case of AND-OR-NOT networks, resulting in important savings in the computational effort. When compared to previous approaches, the experimental results show an important reduction in the number of computations required.
-
DATE - Integrating symbolic techniques in ATPG-based sequential Logic Optimization
Proceedings of the conference on Design automation and test in Europe - DATE '99, 1999Co-Authors: Enrique San Millan, Luis Entrena, J.a. Espejo, Silvia Chiusano, Fulvio CornoAbstract:This paper presents a new integrated approach to Logic Optimization for sequential circuits. The approach is based on the redundancy addition and removal algorithm, which is based on automatic test pattern generation (ATPG) techniques, and improves it using symbolic techniques based on BDDs. The advantage of the integrated approach lies in the ability of Symbolic Techniques to provide exact and extensive information about the sequential behavior of the portion of the circuit that is of interest to the Logic Optimization algorithm. Experimental results are provided that show the superiority of the approach to the original ATPG-based Optimization approach.
