Search

Search Results

• 1. [Article] Fast Heuristic Minimization of Exclusive-Sums-of-Products

  Exclusive-Sums-Of-Products (ESOPs) play an important role in logic synthesis and design-for-test. This paper presents an improved version of the heuristic ESOP minimization procedure proposed in [1,2]. ...

  Citation × Citation Citation Abstract Copy Title: Fast Heuristic Minimization of Exclusive-Sums-of-Products Author: Mishchenko, Alan, Perkowski, Marek Year: 2001 Exclusive-Sums-Of-Products (ESOPs) play an important role in logic synthesis and design-for-test. This paper presents an improved version of the heuristic ESOP minimization procedure proposed in [1,2]. The improvements concern three aspects of the procedure: (1) computation of the starting ESOP cover; (2) increase of the search space for solutions by applying a larger set of cube transformations; (3) development of specialized datastructures for robust manipulation of ESOP covers. Comparison of the new heuristic ESOP minimizer EXORCISM-4 with other minimizers (EXMIN2 [3], MINT [4], EXORCISM-2 [1] and EXORCISM3 [2]) show that, in most cases, EXORCISM-4 produces results of comparable or better quality on average ten times faster. Title: Fast Heuristic Minimization of Exclusive-Sums-of-Products Author: Mishchenko, Alan, Perkowski, Marek Year: 2001 Exclusive-Sums-Of-Products (ESOPs) play an important role in logic synthesis and design-for-test. This paper presents an improved version of the heuristic ESOP minimization procedure proposed in [1,2]. The improvements concern three aspects of the procedure: (1) computation of the starting ESOP cover; (2) increase of the search space for solutions by applying a larger set of cube transformations; (3) development of specialized datastructures for robust manipulation of ESOP covers. Comparison of the new heuristic ESOP minimizer EXORCISM-4 with other minimizers (EXMIN2 [3], MINT [4], EXORCISM-2 [1] and EXORCISM3 [2]) show that, in most cases, EXORCISM-4 produces results of comparable or better quality on average ten times faster. Close

• 2. [Article] A General Decomposition for Reversible Logic

  Logic synthesis for reversible logic differs considerably from standard logic synthesis. The gates are multi-output and the unutilized outputs from these gates are called “garbage”. One of the synthesis ...

  Citation × Citation Citation Abstract Copy Title: A General Decomposition for Reversible Logic Author: Perkowski, Marek, Jozwiak, Lech, Kerntopf, Pawel, Mishchenko, Alan, Al-Rabadi, Anas, Coppola, Alan, Buller, Andrzej, Song, Xiaoyu, Yanushkevich, Svetlana, Shmerko, Vlad P., Chrzanowska-Jeske, Malgorzata, Khan, Mozammel Huq Azad Year: 2001 Logic synthesis for reversible logic differs considerably from standard logic synthesis. The gates are multi-output and the unutilized outputs from these gates are called “garbage”. One of the synthesis tasks is to reduce the number of garbage signals. Previous approaches to reversible logic synthesis minimized either only the garbage or (predominantly) the number of gates. Here we present for the first time a method that minimizes concurrently the number of gates, their total delay and the total garbage. Our method adopts for reversible logic many ideas developed previously for standard logic synthesis (such as Ashenhurst/Curtis Decomposition, Dietmeyer’s Composition, non-linear preprocessing for BDDs), methods created in Reed- Muller Logic (such as Pseudo-Kronecker Decision Diagrams with Complemented Edges, Pseudo-Kronecker Lattice Diagrams and their generalizations) and introduces also new methods specific to reversible logic. Title: A General Decomposition for Reversible Logic Author: Perkowski, Marek, Jozwiak, Lech, Kerntopf, Pawel, Mishchenko, Alan, Al-Rabadi, Anas, Coppola, Alan, Buller, Andrzej, Song, Xiaoyu, Yanushkevich, Svetlana, Shmerko, Vlad P., Chrzanowska-Jeske, Malgorzata, Khan, Mozammel Huq Azad Year: 2001 Logic synthesis for reversible logic differs considerably from standard logic synthesis. The gates are multi-output and the unutilized outputs from these gates are called “garbage”. One of the synthesis tasks is to reduce the number of garbage signals. Previous approaches to reversible logic synthesis minimized either only the garbage or (predominantly) the number of gates. Here we present for the first time a method that minimizes concurrently the number of gates, their total delay and the total garbage. Our method adopts for reversible logic many ideas developed previously for standard logic synthesis (such as Ashenhurst/Curtis Decomposition, Dietmeyer’s Composition, non-linear preprocessing for BDDs), methods created in Reed- Muller Logic (such as Pseudo-Kronecker Decision Diagrams with Complemented Edges, Pseudo-Kronecker Lattice Diagrams and their generalizations) and introduces also new methods specific to reversible logic. Close

• 3. [Article] Implicit Algorithms for Multi-Valued Input Support Manipulation

  We present an implicit approach to solve problems arising in decomposition of incompletely specified multi-valued functions and relations. We introduce a new representation based on binaryencoded multi-valued ...

  Citation × Citation Citation Abstract Copy Title: Implicit Algorithms for Multi-Valued Input Support Manipulation Author: Mishchenko, Alan, Files, Craig, Perkowski, Marek, Steinbach, Bernd, Dorotska, Christina Year: 2001 We present an implicit approach to solve problems arising in decomposition of incompletely specified multi-valued functions and relations. We introduce a new representation based on binaryencoded multi-valued decision diagrams (BEMDDs). This representation shares desirable properties of MDDs, in particular, compactness, and is applicable to weakly-specified relations with a large number of output values. This makes our decomposition approach particularly useful for data mining and machine learning. Using BEMDDs to represent multi-valued relations we have developed two complementary input support minimization algorithms. The first algorithm is efficient when the resulting support contains almost all initial variables; the second is efficient when it contains only a few. We propose a simple heuristic measure to choose which algorithm to use. Numerical results over a set of multi-valued benchmarks provide experimental evidence for the efficiency of our approach. Title: Implicit Algorithms for Multi-Valued Input Support Manipulation Author: Mishchenko, Alan, Files, Craig, Perkowski, Marek, Steinbach, Bernd, Dorotska, Christina Year: 2001 We present an implicit approach to solve problems arising in decomposition of incompletely specified multi-valued functions and relations. We introduce a new representation based on binaryencoded multi-valued decision diagrams (BEMDDs). This representation shares desirable properties of MDDs, in particular, compactness, and is applicable to weakly-specified relations with a large number of output values. This makes our decomposition approach particularly useful for data mining and machine learning. Using BEMDDs to represent multi-valued relations we have developed two complementary input support minimization algorithms. The first algorithm is efficient when the resulting support contains almost all initial variables; the second is efficient when it contains only a few. We propose a simple heuristic measure to choose which algorithm to use. Numerical results over a set of multi-valued benchmarks provide experimental evidence for the efficiency of our approach. Close