2006

 back to the year overview

• Thomas Eschbach, Wolfgang Günther, Bernd Becker
  Orthogonal Hypergraph Drawing for Improved Visibility
  2006 Journal of Graph Algorithms and Applications, volume: 10, issue: 2, pages: 141 - 157
  » show abstract« hide abstract
  Abstract

  Visualization of circuits is an important research area in electronic design automation. One commonly accepted method to visualize a circuit aligns the gates to layers and uses orthogonal lines to connect the gates. In our model we assume that between two consecutive layers every net is allowed to occupy only one track. This avoids unnecessary bends in the wires and helps to improve the clarity of the drawing. Then a crossing reduction step is applied to further improve the readability of the circuit schematics.First we assume that the nodes have already been fixed on alayered hypergraph structure. We consider the problem of assigning the hyperedges between two layers to tracks. The idea is to minimize the total number of hyperedge crossings. We prove that finding the best solution is NP-hard. Then, in contrast to many other approaches which route all the wiring after placing all nodes we focus on a new approach which dynamically reorders the nodes within the layers to further reduce the number of hyperedge crossings.An efficient algorithm is presented that minimizes the hyperedge crossings. Experimental results are provided which show that the drawings can be improved significantly while the run time remains moderate.

2005

 back to the year overview

• Thomas Eschbach, Wolfgang Günther, Bernd Becker
  Orthogonal Circuit Visualization Improved by Merging the Placement and Routing Phases
  2005 Int'l Conf. on VLSI Design, pages: 433 - 438

2004

 back to the year overview

• Thomas Eschbach, Wolfgang Günther, Bernd Becker
  Orthogonal Hypergraph Routing for Improved Visibility
  2004 Great Lakes Symp. on VLSI, pages: 385 - 388

2003

 back to the year overview

• Thomas Eschbach, Wolfgang Günther, Bernd Becker
  Crossing Reduction for Orthogonal Circuit Visualization
  2003 Int'l Conf. on VLSI, CSREA Press, pages: 107 - 113
• Ilia Polian, Wolfgang Günther, Bernd Becker
  Pattern-Based Verification of Connections to Intellectual Property Cores
  2003 INTEGRATION, the VLSI Jour., volume: 35, issue: 1, pages: 25 - 44
  » show abstract« hide abstract
  Abstract

  Verification of designs containing pre-designed cores is a challenging topic in modern IC design, since traditional approaches generally do not use the information that parts of the design (like IP cores) are already verified. The Port Order Fault Model (POF) has recently been introduced for detecting design errors occurring during integration of a core into a System-on-Chip or during test logic insertion. In this work, we generate verification patterns with 100 percent coverage of a sub-class of POF, called 2-POF. We provide theoretical arguments and experimental results backing the efficiency of these patterns also for detecting higher-order POFs. Moreover, verification pattern sets generated by our approach are more compact compared to the results published before.
• Rolf Drechsler, Wolfgang Günther, Thomas Eschbach, L. Linhard, G. Angst
  Recursive Bi-Partitioning of Netlists for Large Number of Partitions
  2003 Journal of Systems Architecture, volume: 49, issue: 12-15, pages: 521 - 528
• Ilia Polian, Wolfgang Günther, Bernd Becker
  The Case For 2-POF
  2003 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”, pages: 164 - 173
  » show abstract« hide abstract
  Abstract

  The Port Order Fault Model (POF) has recently been introduced for detecting design errors occuring during integration of a core into a System-on-Chip or during test logic insertion. In an earlier work, we generated verification vectors with 100 percent coverage of a sub-class of POF, called 2-POF. Demonstrating empirically that these sets of verification vectors also cover an other sub-class of POF, 3-POF, almost completely, we concluded their efficiency also for higher-order POFs. In this paper, we provide theoretical arguments and more empirical results supporting the claim that verification vectors with high coverage of lower-order POFs are very likely to be also efficient in detecting higher-order POFs.
• Ilia Polian, Wolfgang Günther, Bernd Becker
  The Case For 2-POF
  2003 IEEE Design and Diagnostics of Electronic Circuits and Systems, pages: 291 - 292

2002

 back to the year overview

• Thomas Eschbach, Wolfgang Günther, Rolf Drechsler, Bernd Becker
  Crossing Reduction by Windows Optimization
  2002 Int'l Symp. on Graph Drawing, volume: 2528, pages: 285 - 294
• Rolf Drechsler, Wolfgang Günther, Thomas Eschbach, L. Linhard, G. Angst
  Recursive Bi-Partitioning of Netlists for Large Number of Partitions
  2002 Euromicro Conf., pages: 38 - 44

2001

 back to the year overview

• Wolfgang Günther, Andreas Hett, Bernd Becker
  Application of Linearly Transformed BDDs in Sequential Verification
  2001 ASP Design Automation Conf., pages: 91 - 96
  » show abstract« hide abstract
  Abstract

  The computation of the set of reachable states is the key problem of many applications in sequential verification. Binary Decision Diagrams (BDDs) are extensively used in this domain, but tend to blow up for larger instances. To increase the computational power of BDDs, linearly transformed BDDs (LTBDDs) have been proposed. In this paper we show how this concept can be incorporated into the sequential verification domain by restricting dynamic reordering in a way that the relational product can still be carried out efficiently. Experimental results are given to show the efficiency of our approach.
• Ilia Polian, Wolfgang Günther, Bernd Becker
  Efficient Pattern-Based Verification of Connections to Intellectual Property Cores
  2001 IEEE Asian Test Symp., pages: 443 - 448
  » show abstract« hide abstract
  Abstract

  Verification of designs containing pre-designed cores is a challenging topic in modern IC design, since traditional approaches generally do not use the information that parts of the design are already verified (like IP cores). To verify the connectivity between the surrounding design and IP cores, we propose a method that is based on test patterns. Using only those patterns for simulation, in almost all cases 100 percent of the errors can be detected. Existing test access logic is employed for the application of the patterns. A large set of experimental results is given to demonstrate the efficiency of the approach.
• Ilia Polian, Wolfgang Günther, Bernd Becker
  Efficient Pattern-Based Verification of Connections to Intellectual Property Cores
  2001 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”, pages: I:111 - 120
• Bernd Becker, Rolf Drechsler, Thomas Eschbach, Wolfgang Günther
  GREEDY IIP: Partitioning Large Graphs by Greedy Iterative Improvement
  2001 Euromicro Conf., pages: 54 - 60
• Rolf Drechsler, Wolfgang Günther, L. Linhard, G. Angst
  Level Assignment for Displaying Combinational Logic
  2001 Euromicro Conf., page: 148
• Wolfgang Günther, Rolf Drechsler
  Performance Driven Optimization for MUX based FPGAs
  2001 Int'l Conf. on VLSI Design, pages: 311 - 316
  » show abstract« hide abstract
  Abstract

  Logic synthesis and technology mapping for Multiplexor (MUX) based Field Programmable Gate Arrays (FPGAs) have widely been considered. In this paper, an algorithm is proposed that applies techniques from logic synthesis during mapping to minimize the delay. By this, the target technology is considered during the minimization process. Binary Decision Diagrams (BDDs) are used as an underlying data structure for netlists, combining both structural and functional properties. To evaluate a netlist, a fast technology mapper is used. Since most of the changes to a netlist are local, also re-mapping can be done locally, allowing a fast but reliable evaluation after each modification. We give experimental results that show large improvements for most of the instances we considered.
• Frank Schmiedle, Wolfgang Günther, Rolf Drechsler
  Selection of Efficient Re-Ordering Heuristics for MDD Construction
  2001 Int'l Symp. on Multi-Valued Logic, pages: 299 - 304
  » show abstract« hide abstract
  Abstract

  Multi-valued decision diagrams (MDDs) are a generalization of binary decision diagrams (BDDs). They are suitable for several applications in synthesis and verification of integrated circuits since often, functions with multi-valued input variables can be represented efficiently by MDDs. Their sizes counted in number of nodes vary from linear to exponential dependent on the variable ordering used. Therefore sifting, i.e. dynamic variable re-ordering, has to be applied frequently while an MDD is built in order to keep the number of nodes needed during the process small. Often most of the runtime for MDD construction is spent for sifting. We present a new method that speeds up MDD construction and also reduces memory consumption. It is based on the selection of re-ordering heuristics dependent on the history of the construction process. Success of previous re-ordering steps as well as the frequency of sifting calls in the past are used to determine a variation of sifting that is applied next. Experimental results are given to demonstrate that runtimes and memory consumption can be reduced by 30 percent on average when the proposed selection methods are used during MDD construction.
• Rolf Drechsler, Wolfgang Günther, Fabio Somenzi
  Using Lower Bounds during Dynamic BDD Minimization
  2001 IEEE Trans. on CAD, volume: 20, issue: 1, pages: 51 - 57
• Wolfgang Günther, Rolf Drechsler
  lementation of Read-k-times BDDs on top of standard BDD packages
  2001 Int'l Conf. on VLSI Design, pages: 173 - 178
  » show abstract« hide abstract
  Abstract

  Ordered Binary Decision Diagrams (OBDDs) are the state-of-the-art data structure in VLSI CAD for representation and manipulation of Boolean functions. But due to the ordering restriction, many Boolean functions cannot be represented efficiently. As one alternative Read-k-times BDDs have been proposed. They are a generalization of OBDDs in the way that variables may occur up to k times on each path, while they may only occur once in OBDDs. More functions can be represented by Read-k-times BDDs in polynomial space than by OBDDs, while many operations, like synthesis and satisfiability, still have polynomial worst case behavior. In this paper, we present a new technique for implementation of Read-k-times BDD packages on top of standard OBDD implementations. Thus, highly optimized OBDD packages can be used and only few changes in the code are needed, while the new type of decision diagram allows much smaller representations. Experimental results are given to demonstrate the efficiency of the approach.

2000

 back to the year overview

• M. A. Thornton, Rolf Drechsler, Wolfgang Günther
  A Method for Approximate Equivalence Checking
  2000 Int'l Symp. on Multi-Valued Logic, pages: 447 - 452
  » show abstract« hide abstract
  Abstract

  A probabilistic equivalence checking method is developed based on the use of partial Haar Spectral Diagrams (HSDs). Partial HSDs are defined and used to represent a subset of Haar spectral coefficients for two Boolean functions. The resulting coefficients are then used to compute and to iteratively refine the probability that two functions are equivalent. This problem has applications in both logic synthesis and verification. The method described here can be useful for the case where two candidate functions require extreme amounts of memory for a complete BDD representation. Experimental results are provided to validate the effectiveness of this approach.
• Wolfgang Günther, Rolf Drechsler
  ACTion: Combining Logic Synthesis and Technology Mapping for MUX based FPGAs
  2000 Journal of Systems Architecture, volume: 46, issue: 14, pages: 1321 - 1334
  » show abstract« hide abstract
  Abstract

  Technology mapping for Multiplexor (MUX) based Field Programmable Gate Arrays (FPGAs) has widely been considered. Here, a new algorithm is proposed that applies techniques from logic synthesis during technology mapping, i.e. the target technology is considered in the minimization process. Binary Decision Diagrams (BDDs) are used as an underlying data structure combining both structural and functional properties. The algorithm uses local don't cares obtained by a greedy algorithm. To evaluate a netlist, a fast technology mapper is used. Since most of the changes to a netlist are local, also re-mapping can be done locally, allowing a fast but reliable evaluation after each modification. Both area and delay minimization are addressed in this paper. We compare the approach to several previously published algorithms. In most cases these results can be further improved. Compared to SIS, an improvement of 23 percent for area and 18 percent for delay can be observed on average.
• Wolfgang Günther, Rolf Drechsler
  ACTion: Combining Logic Synthesis and Technology Mapping for MUX based FPGAs
  2000 Int'l Workshop on Logic Synth.
• Wolfgang Günther, Rolf Drechsler
  ACTion: Combining Technology Mapping and Logic Synthesis for MUX based FPGAs
  2000 Euromicro Conf., pages: 130 - 137
  » show abstract« hide abstract
  Abstract

  Technology mapping for Multiplexor (MUX) based Field Programmable Gate Arrays (FPGAs) has widely been considered. Here, a new algorithm is proposed that applies techniques from logic synthesis during mapping. By this, the target technology is considered in the minimization process. Binary Decision Diagrams (BDDs) are used as an underlying data structure due to the close relation between BDDs and MUX netlists. The algorithm uses local don't cares obtained by a greedy algorithm. The mapping is sped up by computing signatures. A trade-off quality versus runtime can be specified by the user by setting different parameters. Experimental results comparing the approach to the best known results show improvements of more than 30 percent for area and 40 percent for delay for many instances.
• Frank Schmiedle, Wolfgang Günther, Rolf Drechsler
  Dynamic Re-Encoding During MDD Minimization
  2000 Int'l Symp. on Multi-Valued Logic, pages: 239 - 244
  » show abstract« hide abstract
  Abstract

  Multi-valued decision diagrams (MDDs) are a generalization of binary decision diagrams (BDDs). They often allow efficient representation of functions with multi-valued input variables similar to BDDs in the binary case. Therefore they are suitable for several applications in synthesis and verification of integrated circuits. MDD sizes counted in number of nodes vary from linear to exponential dependent on the variable ordering used. In all these applications, minimization of MDDs is crucial. In many cases, multi-valued variables are composed by a certain number of binary variables, and so the multi-valued inputs arise by grouping binary variables. The selection of these groups, that is, the decision which variables to merge, has enormous impact on MDD sizes. Techniques for finding variable groupings before starting MDD minimization have been proposed recently. In this paper, we present a new method that uses re-encoding, i.e. dynamic variable grouping. We don't choose one fixed variable grouping before minimizing MDDs, but allow to change the binary variables to be considered together during the minimization process. This is possible since MDDs are simulated on top of BDDs. By this, the underlying binary variables remain accessible throughout the minimization process. This technique is described in detail and we also show experimental results that demonstrate the efficiency of our approach.
• Wolfgang Günther, Rolf Drechsler, S. Höreth
  Efficient Dynamic Minimization of Word-Level DDs based on Lower Bound Computation
  2000 Int'l Workshop on Logic Synth.
• Wolfgang Günther, Rolf Drechsler, S. Höreth
  Efficient Dynamic Minimization of Word-Level DDs based on Lower Bound Computation
  2000 Int'l Conf. on Computer Design, pages: 383 - 388
  » show abstract« hide abstract
  Abstract

  Word-Level Decision Diagrams (WLDDs), like *BMDs or K*BMDs, have been introduced to overcome the limitations of Binary Decision Diagrams (BDDs), which are the state-of-the-art data structure to represent and manipulate Boolean functions. However, the size of these graph types largely depends on the variable ordering, i.e. it may vary from linear to exponential. In the meantime, dynamic approaches to find a good variable ordering are also known for WLDDs. In this paper we show how these approaches can be accelerated significantly using a combination of a lower bound computation and synthesis operations. In the experiments it turned out that by this technique, the runtime for dynamic minimization can be reduced by more than 40 percent on average without loss of quality.
• Rolf Drechsler, Wolfgang Günther
  Evolutionary Synthesis of Multiplexor Circuits under Hardware Constraints
  2000 Conf. on Genetic and Evolutionary Computation, pages: 513 - 518
  » show abstract« hide abstract
  Abstract

  Multiplexor based Field Programmable Gate Arrays (FPGAs) are a very popular design style. However, during circuit design only limited hardware resources are available. In this paper we present an approach to multiplexor (MUX) based circuit evolution under hardware constraints. Binary Decision Diagrams (BDDs) are used as the underlying data structure. An evolutionary technique is proposed that allows to stay within given hardware resources while minimizing the error in parallel. Starting from a correct circuit, i.e. a BDD representing the complete function, some parts are removed, based on evolutionary principles, until all constraints are met. The experimental results presented demonstrate the possibility to handle for the first time instances composed of several thousand gates.
• Rolf Drechsler, Nicole Drechsler, Wolfgang Günther
  Fast Exact Minimization of BDDs
  2000 IEEE Trans. on CAD, volume: 19, issue: 3, pages: 384 - 389
  » show abstract« hide abstract
  Abstract

  We present a new exact algorithm for finding the optimal variable ordering for reduced ordered Binary Decision Diagrams (BDDs). The algorithm makes use of a lower bound technique known from VLSI design. Up to now this technique has been used only for theoretical considerations and it is adapted here for our purpose. Furthermore, the algorithm supports symmetry aspects and uses a hashing based data structure. Experimental results are given to demonstrate the efficiency of our approach. We succeeded in minimizing several functions, including adders with up to 64 variables, for which all other previously presented approaches fail.
• Wolfgang Günther, Rolf Drechsler
  Improving EAs for Sequencing Problems
  2000 Conf. on Genetic and Evolutionary Computation, pages: 175 - 180
  » show abstract« hide abstract
  Abstract

  Sequencing problems have to be solved very often in VLSI CAD. To obtain results of high quality, Evolutionary Algorithms (EAs) have been successfully applied in many cases. However, they often suffer from the high CPU time which is necessary for the computation. In this paper we propose three techniques to speed up EAs without loss of quality. We give a case study for the problem of optimizing the variable ordering of Binary Decision Diagrams (BDDs). Experimental results are given to demonstrate the efficiency of the approach.
• Dragan Janković, Wolfgang Günther, Rolf Drechsler
  Lower Bound Sifting for MDDs
  2000 Int'l Symp. on Multi-Valued Logic, pages: 193 - 198
  » show abstract« hide abstract
  Abstract

  Decision Diagrams (DDs) are a data structure for the representation and manipulation of discrete logic functions often applied in VLSI CAD. Common DDs to represent Boolean functions are Binary Decision Diagrams (BDDs). Multiple-valued logic functions can be represented by Multiple-valued Decision Diagrams (MDDs). The efficiency of a DD representation strongly depends on the variable ordering; the size may vary from linear to exponential. Finding a good ordering is an NP-hard problem that has received considerable attention resulting in many minimization methods. Sifting is the most popular heuristic for dynamic DD minimization. In this paper we give lower bounds for sifting of MDDs. Based on them, both lower bound sifting for MDD minimization and lower bound group sifting for BDD minimization are proposed. By the computation of good lower bounds large parts of the search space can be pruned resulting in very fast computations. This is demonstrated by experimental results.
• Wolfgang Günther
  Minimization of Free BDDs using Evolutionary Techniques
  2000 Int'l Workshop on Logic Synth., pages: 167 - 172
• Wolfgang Günther, Rolf Drechsler
  On the Computational Power of Linearly Transformed BDDs
  2000 Information Processing Letters, volume: 75, issue: 3, pages: 119 - 125
  » show abstract« hide abstract
  Abstract

  Binary Decision Diagrams (BDDs) are a powerful tool and are frequently used in many applications in VLSI CAD, like synthesis and verification. However, they are very sensitive to the variable ordering and their size often becomes infeasible. Recently, a new approach for BDD minimization based on linear transformations, i.e. a special type of spectral techniques, has been proposed. In this work we study linear transformations from a theoretical point of view. We prove for a family of Boolean functions that the concept of linear transformations is really more powerful than "pure" BDDs, i.e. there is a class of Boolean functions for which an exponential difference in size exists. Therefore, linear transformations can prevent an exponential blow-up of the BDD.
• Rolf Drechsler, Wolfgang Günther
  Optimization of Sequential Verification by History-Based Dynamic Minimization of BDDs
  2000 IEEE Int'l Symp. on Circuits and Systems, pages: IV:737 - IV:740
  » show abstract« hide abstract
  Abstract

  Binary Decision Diagrams (BDDs) are the state-of-the-art data structure in VLSI CAD, especially in sequential verification tasks, like state-space exploration and image computation. Since their size largely depends on the chosen variable ordering, dynamic variable reordering methods, like sifting, often have to be applied while the BDD is constructed. Usually sifting is called each time a given node limit is reached and it is therefore called frequently during the construction of large BDDs. Often most of the runtime is spent for sifting while the BDD is built. Recently an approach to reduce runtime during BDD construction for combinational circuits by using history-based decision procedures has been proposed. In this paper we show that for sequential circuits different criteria should be used to select the type of sifting that involve knowledge from the sequential domain. The algorithm has been included in VIS. Experimental results show that the overall runtime can be reduced significantly and is also clearly superior to the combinational approach.
• Wolfgang Günther
  Speeding up Dynamic Minimization of Linearly Transformed BDDs
  , issue: 144, 2000
  » show abstract« hide abstract
  Abstract

  Binary Decision Diagrams (BDDs) are frequently used in many applications in VLSI CAD. However, they are very sensitive to the variable ordering and their size often becomes infeasible. To reduce the BDD sizes, Linear Transformations (LTs), a special type of spectral techniques, have been successfully applied in many cases. The most commonly used heuristic to find a good LT, i.e. an LT which leads to a small BDD representation, is called linear sifting. It can be seen as an extension of the widely used dynamic BDD minimization algorithm called sifting by a linear operator. In this paper, we prove lower bounds for Linearly Transformed BDDs (LTBDDs) under certain conditions and show that it is possible to speed up linear sifting significantly using these bounds. Experimental results are given to show the efficiency of our approach.
• Rolf Drechsler, Wolfgang Günther, Bernd Becker
  Testability of Circuits Derived from Lattice Diagrams
  2000 Euromicro Conf., pages: 188 - 192
  » show abstract« hide abstract
  Abstract

  In this paper the testability of circuits derived from BDDs representing totally symmetric functions is analyzed. A test pattern generation technique is presented that has runtime linear in the size of the BDD. The result is directly applicable to circuits derived from lattice diagrams, a new design style that combines the synthesis and the layout step. Experimental results show that complete test generation for functions with more than 500 variables can be done in less than 1 CPU second.
• Rolf Drechsler, Wolfgang Günther, Bernd Becker
  Testability of Circuits Derived from Lattice Diagrams
  2000 Latin-American Test Workshop
• Wolfgang Günther, Nicole Drechsler, Rolf Drechsler, Bernd Becker
  Verification of Designs Containing Black Boxes
  2000 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”
  » show abstract« hide abstract
  Abstract

  Often modern designs contain regions where the implementation of certain components is not (fully) known. These regions are called black boxes in the following. They occur e.g. if different designers work on a project in parallel or if IP cores are used. In this paper an approach based on a symbolic representation of characteristic functions for verifying circuits with black boxes is presented. We show that by this method more faults can be detected than with pure binary simulation and symbolic simulation using BDDs, respectively, only. This results from the formulation of our algorithm that allows implications over the black box. Experimental results are given to show what parts of a design can be proven to be correct, if black boxes are assumed. Of course, the probability for the detection of a fault in general depends on the size of the unknown regions. But fault injection experiments on benchmarks show that for many circuits even up to 90 percent of the faults are detected, even though large parts of the design are unspecified.
• Wolfgang Günther, Nicole Drechsler, Rolf Drechsler, Bernd Becker
  Verification of Designs Containing Black Boxes
  2000 Euromicro Conf., pages: 100 - 105
  » show abstract« hide abstract
  Abstract

  Often modern designs contain regions where the implementation of certain components is not (fully) known. These regions are called black boxes in the following. They occur e.g. if different designers work on a project in parallel or if IP cores are used. In this paper an approach based on a symbolic representation of characteristic functions for verifying circuits with black boxes is presented. We show that by this method more faults can be detected than with pure binary simulation and symbolic simulation using BDDs, respectively, only. This results from the formulation of our algorithm that allows implications over the black box. Experimental results are given to show what parts of a design can be proven to be correct, if black boxes are assumed. Of course, the probability for the detection of a fault in general depends on the size of the unknown regions. But fault injection experiments on benchmarks show that for many circuits even up to 90 percent of the faults are detected, even though large parts of the design are unspecified.
• Wolfgang Günther, R. Schönfeld, Bernd Becker, Paul Molitor
  k-Layer Straightline Crossing Minimization by Speeding up Sifting
  2000 Graph Drawing Conf., Springer Verlag, volume: 1984, pages: 253 - 258
  » show abstract« hide abstract
  Abstract

  =3. In this paper, we present two methods to speed up sifting. First, it is shown how the crossing matrix can be computed and updated efficiently. Then, we study lower bounds which can be incorporated in the sifting algorithm, allowing to prune large parts of the search space. Experimental results show that it is possible to speed up sifting by more than a factor of 20 using the new methods during the minimization process.

1999

 back to the year overview

• Wolfgang Günther, Rolf Drechsler
  Creating Hard Problem Instances in Logic Synthesis using Exact Minimization
  1999 IEEE Int'l Symp. on Circuits and Systems, pages: VI:436 - VI:439
  » show abstract« hide abstract
  Abstract

  To evaluate synthesis algorithms, usually benchmark circuits are used. Since for these circuits no exact synthesis results are known, we propose the use of exact minimization to generate hard problem instances. By this we evaluate a standard synthesis tool on different classes of circuits.
• Wolfgang Günther, Rolf Drechsler
  Efficient Manipulation Algorithms for Linearly Transformed BDDs
  1999 Int'l Conf. on CAD, pages: 50 - 53
  » show abstract« hide abstract
  Abstract

  Binary Decision Diagrams (BDDs) are the state-of-the-art data structure in VLSI CAD. But due to their ordering restriction only exponential sized BDDs exist for many functions of practical relevance. Linear Transformations (LTs) have been proposed as a new concept to minimize the size of BDDs and it is known that in some cases even an exponential reduction can be obtained. In addition to a small representation, the efficient manipulation of a data structure is also important. In this paper we present polynomial time manipulation algorithms that can be used for Linearly Transformed BDDs (LT-BDDs) analogously to BDDs. For some operations, like synthesis algorithms based on ITE, it turns out that the techniques known from BDDs can be directly transferred, while for other operations, like quantification and cofactor computation, completely different algorithms have to be used. Experimental results are given to show the efficiency of the approach.
• Rolf Drechsler, Wolfgang Günther
  History-based Dynamic Minimization during BDD Construction
  1999 IFIP Int'l Conf. on VLSI, pages: 334 - 345
  » show abstract« hide abstract
  Abstract

  Binary Decision Diagrams (BDDs) are the state-of-the-art data structure in VLSI CAD. Since their size largely depends on the chosen variable ordering, dynamic variable reordering methods, like sifting, often have to be applied while the BDD for a given circuit is constructed. Usually sifting is called each time a given node limit is reached and it is therefore called frequently during the construction of large BDDs. Often most of the runtime is spent for sifting while the BDD is built. In this paper we propose an approach to reduce runtime (and space requirement) during BDD construction by using history-based decision procedures. Dependent on the history of the construction process different types of sifting are called. We propose two methods that consider the quality of the hash table and the size reduction of previous sifting runs, respectively. Experimental results show that both approaches reduce the runtime significantly, i.e. by more than 40 percent on average.
• Wolfgang Günther, Rolf Drechsler
  Minimization of BDDs using Linear Transformations based on Evolutionary Techniques
  1999 IEEE Int'l Symp. on Circuits and Systems, pages: I:387 - I:390
  » show abstract« hide abstract
  Abstract

  Binary Decision Diagrams (BDDs) are frequently used in many applications in VLSI CAD. However, they are very sensitive to the variable ordering and their size often becomes infeasible. Recently, a new approach for BDD minimization based on Linear Transformations (LTs), i.e. a special type of spectral techniques, has been proposed. We present an Evolutionary Algorithm (EA) to find an LT for which the BDD becomes small. The genetic operators make use of problem specific knowledge. Experimental results are given to show the efficiency of our approach.
• Wolfgang Günther, Rolf Drechsler
  Minimization of Free BDDs
  1999 ASP Design Automation Conf., pages: 323 - 326
  » show abstract« hide abstract
  Abstract

  Free BDDs (FBDDs) are an extension of ordered BDDs (OBDDs) that allow different orderings along each path. FBDDs allow a more efficient representation, while keeping (nearly) all of the properties of OBDDs. In some cases even an exponential reduction can be observed. In this paper we present for the first time an exact algorithm for finding a minimal FBDD representation for a given Boolean function. To reduce the huge search space, it makes use of a pruning technique. The algorithm also considers symmetries of the function. Since the algorithm is only applicable to small functions we also present a heuristic for FBDD minimization starting from an OBDD. Our experiments show that in many cases significant improvements can be obtained.
• Rolf Drechsler, Wolfgang Günther
  Using Lower Bounds during Dynamic BDD Minimization
  1999 IEEE Design Automation Conference, pages: 29 - 32
  » show abstract« hide abstract
  Abstract

  Ordered Binary Decision Diagrams (BDDs) are a data structure for representation and manipulation of Boolean functions often applied in VLSI CAD. The choice of the variable ordering largely influences the size of the BDD; its size may vary from linear to exponential. The most successful methods for finding good orderings are based on dynamic variable reordering, i.e. exchanging of neighboring variables. This basic operation has been used in various variants, like sifting and window permutation. In this paper we show that lower bounds computed during the minimization process can speed up the computation significantly. First, lower bounds are studied from a theoretical point of view. Then these techniques are incorporated in dynamic minimization algorithms. By the computation of good lower bounds large parts of the search space can be pruned resulting in very fast computations. Experimental results are given to demonstrate the efficiency of our approach.

1998

 back to the year overview

• Wolfgang Günther, Rolf Drechsler
  BDD Minimization by Linear Transformations
  1998 Advanced Computer Systems, pages: 525 - 532
  » show abstract« hide abstract
  Abstract

  Binary Decision Diagrams (BDDs) are a powerful tool and are frequently used in many applications in VLSI CAD, like synthesis and verification. Unfortunately, BDDs are very sensitive to the variable ordering and their size often becomes infeasible. Recently, a new approach for BDD minimization based on linear transformations, i.e. a special type of spectral techniques, has been proposed. In this paper we study this minimization method in more detail. While so far only experimental results are known, we prove for a family of Boolean functions that by linear transformations an exponential blow up of the BDD size can be prevented. Furthermore, we present a heuristic method that allows to significantly reduce the BDD sizes. By experiments we give a comparison to the state-of-the-art method to demonstrate the advantages of our approach.
• Rolf Drechsler, Wolfgang Günther
  Exact Circuit Synthesis
  1998 Int'l Workshop on Logic Synth., pages: 177 - 184
• Rolf Drechsler, Wolfgang Günther
  Exact Circuit Synthesis
  1998 Advanced Computer Systems, pages: 517 - 524
  » show abstract« hide abstract
  Abstract

  In this paper we present an exact algorithm for finding a minimal circuit for a given Boolean function. The algorithm is based on graph enumeration and makes use of several pruning techniques to reduce the huge search space. It can handle not only single output but also multiple output functions. The exact netlists obtained are compared to circuits determined by SIS, a state-of-the-art synthesis tool. It turns out that the results can be improved up to 40% also on small examples.
• Wolfgang Günther, Rolf Drechsler
  Linear Transformations and Exact Minimization of BDDs
  1998 Great Lakes Symp. on VLSI, pages: 325 - 330
  » show abstract« hide abstract
  Abstract

  We present an exact algorithm to find an optimal linear transformation for the variables of a Boolean function to minimize its corresponding ordered Binary Decision Diagram (BDD). To prune the huge search space, techniques known from algorithms for finding the optimal variable ordering are used. This BDD minimization finds direct application in FPGA design. We give experimental results for a large variety of circuits to show the efficiency of our approach.

1997

 back to the year overview

• Rolf Drechsler, Nicole Göckel, Wolfgang Günther
  Fast Exact Minimization of BDDs
  , 1997