Rechnerarchitektur - Universität Freiburg

Name	Wolfgang Günther, Dr.
Adresse	OneSpin Solutions GmbH
eMail	guenther@informatik.uni-freiburg.de
Website	http://ira.informatik.uni-freiburg.de/~guenther/index_d.html

Wolfgang Günther

Jahre: 2006 | 2005 | 2004 | 2003 | 2002 | 2001 | 2000 | 1999 | 1998 | 1997

2006

nach oben zur Jahresübersicht

Thomas Eschbach, Wolfgang Günther, Bernd Becker
Orthogonal Hypergraph Drawing for Improved Visibility
2006 Journal of Graph Algorithms and Applications, Band: 10, Nummer: 2, Seiten: 141 - 157
KurzfassungVisualization 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

nach oben zur Jahresübersicht

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, Seiten: 433 - 438

2004

nach oben zur Jahresübersicht

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

2003

nach oben zur Jahresübersicht

Thomas Eschbach, Wolfgang Günther, Bernd Becker
Crossing Reduction for Orthogonal Circuit Visualization
2003 Int'l Conf. on VLSI, CSREA Press, Seiten: 107 - 113
Ilia Polian, Wolfgang Günther, Bernd Becker
Pattern-Based Verification of Connections to Intellectual Property Cores
2003 INTEGRATION, the VLSI Jour., Band: 35, Nummer: 1, Seiten: 25 - 44
KurzfassungVerification 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, Band: 49, Nummer: 12-15, Seiten: 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”, Seiten: 164 - 173
KurzfassungThe 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, Seiten: 291 - 292

2002

nach oben zur Jahresübersicht

Thomas Eschbach, Wolfgang Günther, Rolf Drechsler, Bernd Becker
Crossing Reduction by Windows Optimization
2002 Int'l Symp. on Graph Drawing, Band: 2528, Seiten: 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., Seiten: 38 - 44

2001

nach oben zur Jahresübersicht

Wolfgang Günther, Andreas Hett, Bernd Becker
Application of Linearly Transformed BDDs in Sequential Verification
2001 ASP Design Automation Conf., Seiten: 91 - 96
KurzfassungThe 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., Seiten: 443 - 448
KurzfassungVerification 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”, Seiten: I:111 - 120
Bernd Becker, Rolf Drechsler, Thomas Eschbach, Wolfgang Günther
GREEDY IIP: Partitioning Large Graphs by Greedy Iterative Improvement
2001 Euromicro Conf., Seiten: 54 - 60
Rolf Drechsler, Wolfgang Günther, L. Linhard, G. Angst
Level Assignment for Displaying Combinational Logic
2001 Euromicro Conf., Seite: 148
Wolfgang Günther, Rolf Drechsler
Performance Driven Optimization for MUX based FPGAs
2001 Int'l Conf. on VLSI Design, Seiten: 311 - 316
KurzfassungLogic 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, Seiten: 299 - 304
KurzfassungMulti-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, Band: 20, Nummer: 1, Seiten: 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, Seiten: 173 - 178
KurzfassungOrdered 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

nach oben zur Jahresübersicht

M. A. Thornton, Rolf Drechsler, Wolfgang Günther
A Method for Approximate Equivalence Checking
2000 Int'l Symp. on Multi-Valued Logic, Seiten: 447 - 452
KurzfassungA 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, Band: 46, Nummer: 14, Seiten: 1321 - 1334
KurzfassungTechnology 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., Seiten: 130 - 137
KurzfassungTechnology 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, Seiten: 239 - 244
KurzfassungMulti-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, Seiten: 383 - 388
KurzfassungWord-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, Seiten: 513 - 518
KurzfassungMultiplexor 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, Band: 19, Nummer: 3, Seiten: 384 - 389
KurzfassungWe 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, Seiten: 175 - 180
KurzfassungSequencing 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, Seiten: 193 - 198
KurzfassungDecision 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., Seiten: 167 - 172
Wolfgang Günther, Rolf Drechsler
On the Computational Power of Linearly Transformed BDDs
2000 Information Processing Letters, Band: 75, Nummer: 3, Seiten: 119 - 125
KurzfassungBinary 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, Seiten: IV:737 - IV:740
KurzfassungBinary 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
, Nummer: 144, 2000
KurzfassungBinary 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., Seiten: 188 - 192
KurzfassungIn 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”
KurzfassungOften 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., Seiten: 100 - 105
KurzfassungOften 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, Band: 1984, Seiten: 253 - 258
Kurzfassung=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

nach oben zur Jahresübersicht

Wolfgang Günther, Rolf Drechsler
Creating Hard Problem Instances in Logic Synthesis using Exact Minimization
1999 IEEE Int'l Symp. on Circuits and Systems, Seiten: VI:436 - VI:439
KurzfassungTo 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, Seiten: 50 - 53
KurzfassungBinary 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, Seiten: 334 - 345
KurzfassungBinary 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, Seiten: I:387 - I:390
KurzfassungBinary 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., Seiten: 323 - 326
KurzfassungFree 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, Seiten: 29 - 32
KurzfassungOrdered 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

nach oben zur Jahresübersicht

Wolfgang Günther, Rolf Drechsler
BDD Minimization by Linear Transformations
1998 Advanced Computer Systems, Seiten: 525 - 532
KurzfassungBinary 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., Seiten: 177 - 184
Rolf Drechsler, Wolfgang Günther
Exact Circuit Synthesis
1998 Advanced Computer Systems, Seiten: 517 - 524
KurzfassungIn 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, Seiten: 325 - 330
KurzfassungWe 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

nach oben zur Jahresübersicht

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