2021

 nach oben zur Jahresübersicht

• Pascal Pieper, Ralf Wimmer, Gerhard Angst, Rolf Drechsler
  Minimally Invasive HW/SW Co-debug Live Visualization on Architecture Level
  2021 ACM Press
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  We present a tool that allows developers to debug hard- and software and their interaction in an early design stage. We combine a SystemC virtual prototype (VP) with an easily configurable and interactive graphical user interface and a standard software debugger. The graphical user interface visualizes the internal state of the hardware. At the same time, the software debugger monitors and allows to manipulate the state of the software. This co-visualization supports design understanding and live debugging of the HW/SW interaction. We demonstrate its usefulness with a case-study where we debug an OLED display driver running on a RISC-V VP.

2014

 nach oben zur Jahresübersicht

• Bernd Becker, Rolf Drechsler, Stephan Eggersglüß, Matthias Sauer
  Recent advances in SAT-based ATPG: Non-standard fault models, multi constraints and optimization
  2014 International Conference on Design Technology of Integrated Systems In Nanoscale Era (DTIS)

2004

 nach oben zur Jahresübersicht

• Thomas Eschbach, Rolf Drechsler, Bernd Becker
  Placement and Routing Optimization for Circuits Derived from BDDs
  2004 IEEE Int'l Symp. on Circuits and Systems, Seiten: V229 - V232

2003

 nach oben zur Jahresübersicht

• Frank Schmiedle, Rolf Drechsler, Bernd Becker
  Exact Routing with Search Space Reduction
  2003 IEEE Trans. on Computers, Band: 52, Nummer: 6, Seiten: 815 - 825
• Martin Keim, M. Martin, Bernd Becker, Rolf Drechsler, Paul Molitor
  Polynomial Formal Verification of Multipliers
  2003 Formal Methods in System Design, Band: 22, Nummer: 1, Seiten: 39 - 58
• 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

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
• Klaus-Jürgen Englert, Rolf Drechsler, Bernd Becker
  Verification of HDLs using Symbolic Set Representation
  2002 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”

2001

 nach oben zur Jahresübersicht

• Rolf Drechsler, J. Römmler
  Implementation and Visualization of a BDD Package in JAVA
  , 2001
• Rolf Drechsler
  Educational Software for Computer Engineering: A Case Study of an Interactive BDD Tool
  2001 IEEE Computer Society Learning Technology Task Force, Band: 3, Nummer: 3
• Bernd Becker, Rolf Drechsler, Thomas Eschbach, Wolfgang Günther
  GREEDY IIP: Partitioning Large Graphs by Greedy Iterative Improvement
  2001 Euromicro Conf., Seiten: 54 - 60
• Nicole Drechsler, Frank Schmiedle, Daniel Große, Rolf Drechsler
  Heuristic Learning based on Genetic Programming
  2001 EuroGP, Springer Verlag, Band: 2038, Seiten: 1 - 10
• 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
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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, Nicole Drechsler, Daniel Große, Rolf Drechsler
  Priorities in Multi-Objective Optimization for Genetic Programming
  2001 Conf. on Genetic and Evolutionary Computation, Seiten: 129 - 136
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  A new technique for multi-objective optimization is presented that allows to include priorities. But in contrast to previous techniques they can be included very easily and do not require much user interaction. The new approach is studied from a theoretical and practical point of view. The main differences to existing methods, like relation dominate and favor, are discussed. An experimental study of applying priorities in heuristics learning based on Genetic Programming (GP) is described. The experiments confirm the advantages presented in comparison to several other techniques.
• 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
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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.
• M. Thornton, Rolf Drechsler, D. M. Miller
  Spectral Techniques in VLSI CAD
  Kluwer Academic Publisher, 2001
• Frank Schmiedle, Daniel Große, Rolf Drechsler, Bernd Becker
  Too Much Knowledge Hurts: Acceleration of Genetic Programs for Learning Heuristics
  2001 Int'l Conf. on Computational Intelligence, Band: 2206, Seiten: 479 - 491
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  Among many other applications, evolutionary methods have been used to develop heuristics for several optimization problems in VLSI CAD in recent years. Although learning is performed according to a set of training benchmarks, it is most important to generate heuristics that have a good generalization behaviour and hence are well suited to be applied to unknown examples. Besides large runtimes for learning, the major drawback of these approaches is that they are very sensitive to a variety of parameters for the learning process. In this paper, we study the impact of different parameters, like e.g. stopping conditions, on the quality of the results for learning heuristics for BDD minimization. If learning takes too long, the developed heuristics become too specific for the set of training examples and in that case results of application to unknown problem instances deteriorate. It will be demonstrated here that runtime can be saved while even improving the generalization behaviour of the heuristics.
• 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
• P. Johannsen, Rolf Drechsler
  Utilizing High-Level Information for Formal Hardware Verification (Invited Talk)
  2001 Advanced Computer Systems, Seiten: 419 - 431
• 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
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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

 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
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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, Band: 46, Nummer: 14, Seiten: 1321 - 1334
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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., Seiten: 130 - 137
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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.
• Rolf Drechsler, Nicole Drechsler, Elke Mackensen, Tobias Schubert, Bernd Becker
  Design Reuse by Modularity: A Scalable Dynamical (Re)Configurable Multiprocessor System
  2000 Euromicro Conf., Seiten: 1:425 - 431
• Frank Schmiedle, Wolfgang Günther, Rolf Drechsler
  Dynamic Re-Encoding During MDD Minimization
  2000 Int'l Symp. on Multi-Valued Logic, Seiten: 239 - 244
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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, Seiten: 383 - 388
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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, Seiten: 513 - 518
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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, Band: 19, Nummer: 3, Seiten: 384 - 389
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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.
• Rolf Drechsler
  Formal Verification of Circuits
  Kluwer Academic Publishers, 2000
• Wolfgang Günther, Rolf Drechsler
  Improving EAs for Sequencing Problems
  2000 Conf. on Genetic and Evolutionary Computation, Seiten: 175 - 180
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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, Seiten: 193 - 198
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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, Rolf Drechsler
  On the Computational Power of Linearly Transformed BDDs
  2000 Information Processing Letters, Band: 75, Nummer: 3, Seiten: 119 - 125
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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, Seiten: IV:737 - IV:740
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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.
• Tobias Schubert, Elke Mackensen, Nicole Drechsler, Rolf Drechsler, Bernd Becker
  Specialized Hardware for Implementation of Evolutionary Algorithms
  2000 Int'l Workshop on Boolean Problems, Seiten: 175 - 182
• Tobias Schubert, Elke Mackensen, Nicole Drechsler, Rolf Drechsler, Bernd Becker
  Specialized Hardware for Implementation of Evolutionary Algorithms
  2000 Conf. on Genetic and Evolutionary Computation, Seite: 369
• Rolf Drechsler, Wolfgang Günther, Bernd Becker
  Testability of Circuits Derived from Lattice Diagrams
  2000 Euromicro Conf., Seiten: 188 - 192
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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”
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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., Seiten: 100 - 105
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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.

1999

 nach oben zur Jahresübersicht

• Rolf Drechsler, Marc Herbstritt, Bernd Becker
  Grouping Heuristics for Word-level Decision Diagrams
  1999 IEEE Int'l Symp. on Circuits and Systems, Seiten: 411 - 415
• Rolf Drechsler, Bernd Becker
  Probabilistic IP Verification
  1999 Int'l Workshop on Testing Embedded Core-based System-Chips
• Nicole Drechsler, Rolf Drechsler, Bernd Becker
  A New Model for Multi-Objective Optimization in Evolutionary Algorithms
  1999 Int'l Conf. on Computational Intelligence, Springer Verlag, Band: 1625, Seiten: 108 - 117
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  Many optimization problems consist of several mutually dependent subproblems, where the resulting solutions must satisfy all requirements. We propose a new model for Multi-Objective Optimization (MOO) in Evolutionary Algorithms (EAs). The search space is partitioned into so-called Satisfiability Classes (SC), where each region represents the quality of the optimization criteria. Applying the SCs to individuals in a population a fitness can be assigned during the EA run. The model also allows the handling of infeasible regions and restrictions in the search space. Additionally, different priorities for optimization objectives can be modeled. Advantages of the model over previous approaches are discussed and an application is given that shows the superiority of the method for modeling MOO problems.
• Christoph Scholl, D. Möller, Paul Molitor, Rolf Drechsler
  BDD Minimization Using Symmetries
  1999 IEEE Trans. on CAD, Band: 18, Nummer: 2, Seiten: 81 - 100
• 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
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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, Seiten: 50 - 53
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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.
• Nicole Drechsler, Rolf Drechsler
  Exploiting Don't Cares During Data Sequencing using Genetic Algorithms
  1999 ASP Design Automation Conf., Seiten: 303 - 306
• S. Höreth, Rolf Drechsler
  Formal Verification of Word-Level Specifications
  1999 Conf. on Design, Automation and Test in Europe, Seiten: 52 - 58
• Rolf Drechsler, Marc Herbstritt, Bernd Becker
  Grouping Heuristics for Word-level Decision Diagrams
  1999 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”, Shaker Verlag, Seiten: 41 - 50
• Rolf Drechsler, Wolfgang Günther
  History-based Dynamic Minimization during BDD Construction
  1999 IFIP Int'l Conf. on VLSI, Seiten: 334 - 345
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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, Seiten: I:387 - I:390
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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., Seiten: 323 - 326
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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.
• Y. Ye, K. Roy, Rolf Drechsler
  Power Consumption in XOR-Based Circuits
  1999 ASP Design Automation Conf., Seiten: 299 - 302
• Per Lindgren, Rolf Drechsler, Bernd Becker
  Synthesis of Pseudo Kronecker Lattice Diagrams
  1999 Int'l Conf. on Computer Design, Seiten: 307 - 310
• Rolf Drechsler, Wolfgang Günther
  Using Lower Bounds during Dynamic BDD Minimization
  1999 IEEE Design Automation Conference, Seiten: 29 - 32
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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.
• Rolf Drechsler, Nicole Drechsler
  VLSI CAD and the Integration of Evolutionary Techniques
  CRC Press International Series on Computational Intelligence, 1999

1998

 nach oben zur Jahresübersicht

• Martin Keim, Nicole Göckel, Rolf Drechsler, Bernd Becker
  Combining GAs and Symbolic Methods for High Quality Tests of Sequential Circuits
  , Nummer: 105/98, 1998
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  A symbolic fault simulator is integrated in a Genetic Algorithm (GA) environment to perform {Automatic Test Pattern Generation} (ATPG) for synchronous sequential circuits. In a two phase algorithm test length and fault coverage as well are optimized. However, there are circuits, that are hard to test using random pattern sequences, even if these sequences are genetically optimized. Thus, deterministic aspects are included in the GA environment to improve fault coverage. Experiments demonstrate that both a priori time consuming strategies can be combined at reasonable costs: Tests with higher fault coverages and considerably shorter test sequences than previously presented approaches are obtained.
• Wolfgang Günther, Rolf Drechsler
  BDD Minimization by Linear Transformations
  1998 Advanced Computer Systems, Seiten: 525 - 532
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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, Bernd Becker
  Binary Decision Diagrams - Theory and Implementation
  Kluwer Academic Publishers, 1998
• Martin Keim, Nicole Drechsler, Rolf Drechsler, Bernd Becker
  Combining GAs and Symbolic Methods for High Quality Tests of Sequential Circuits
  1998 European Test Workshop, Seiten: 141 - 142
• S. Höreth, Rolf Drechsler
  Dynamic Minimization of Word-Level Decision Diagrams
  1998 Conf. on Design, Automation and Test in Europe, Seiten: 612 - 617
• G. Lee, Rolf Drechsler
  ETDD-based Generation of Complex Terms for Incompletely Specified Boolean Functions
  1998 ASP Design Automation Conf., Seiten: 75 - 80
• Rolf Drechsler
  Evolutionary Algorithms for VLSI CAD
  Kluwer Academic Publisher, 1998
• 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
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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.
• Rolf Drechsler, Bernd Becker
  Graphenbasierte Funktionsdarstellung
  B.G. Teubner, 1998
• M. Miller, Rolf Drechsler
  Implementing a Multiple-Valued Decision Diagram Package
  1998 Int'l Symp. on Multi-Valued Logic, Seiten: 52 - 57
• Wolfgang Günther, Rolf Drechsler
  Linear Transformations and Exact Minimization of BDDs
  1998 Great Lakes Symp. on VLSI, Seiten: 325 - 330
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  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.
• M. Thornton, Rolf Drechsler
  Output Probability Using AND/OR Graphs
  1998 Research Report, University of Arkansas
• M. Thornton, Rolf Drechsler
  Spectral Methods for Digital Logic Verification
  1998 Research Report, University of Arkansas
• Martin Keim, Nicole Drechsler, Rolf Drechsler, Bernd Becker
  Test Generation for (Sequential) Multi-Valued Logic Networks based on Genetic Algorithm
  1998 Int'l Symp. on Multi-Valued Logic, Seiten: 215 - 220
• Martin Keim, Nicole Göckel, Rolf Drechsler, Bernd Becker
  Test Generation for (Sequential) Multi-Valued Logic Networks based on Genetic Algorithm
  1998 Int'l Symp. on Multi-Valued Logic
• Rolf Drechsler, Martin Sauerhoff, Detlef Sieling
  The Complexity of the Inclusion Operation on OFDDs
  1998 IEEE Trans. on CAD, Band: 17, Nummer: 5, Seiten: 457 - 459
• Rolf Drechsler
  Verifying Integrity of Decision Diagrams
  1998 SAFECOMP, Springer Verlag, Band: 1516, Seiten: 380 - 389

1997

 nach oben zur Jahresübersicht

• Rolf Drechsler, Nicole Göckel
  A Genetic Algorithm for Data Sequencing
  1997 Electronic Letters, Band: 33, Nummer: 10, Seiten: 843 - 845
• Nicole Göckel, Martin Keim, Rolf Drechsler, Bernd Becker
  A Genetic Algorithm for Sequential Circuit Test Generation based on Symbolic Fault Simulation
  1997 GI/ITG Workshop “Testmethoden und Zuverlässigkeit von Schaltungen und Systemen”
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  We present a Genetic Algorithm (GA) for sequential circuit test generation. A Binary Decision Diagram (BDD) based fault simulator, i.e. a fault simulator that uses symbolic methods, is integrated in the GA environment. The fault simulator is used as a more accurate evaluation method. Experiments show that we can generate test patterns for circuits where all previously presented GA approaches fail. Additionally, we reduce the length of the test sequences. A comparison to the pure GA based approach shows the efficiency of this method.
• Nicole Göckel, Martin Keim, Rolf Drechsler, Bernd Becker
  A Genetic Algorithm for Sequential Circuit Test Generation based on Symbolic Fault Simulation
  1997 European Test Workshop
• Nicole Göckel, Rolf Drechsler, Bernd Becker
  A Multi-Layer Detailed Routing Approach based on Evolutionary Algorithms
  1997 Int'l Conf. on Evolutionary Computation, Seiten: 557 - 562
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  In this paper we present an Evolutionary Algorithm (EA) for Detailed Routing Problems (DRPs), like the Channel Routing Problem and the Switchbox Routing Problem. We combine EAs with domain specific knowledge, i.e. the genetic operators make use of the rip-up and reroute technique. The algorithm can work with two-layer and multi-layer problem instances. The efficiency of our algorithm is demonstrated by application to multi-layer channel routing benchmarks. Instances with up to five layers, 130 columns, and more than 60 nets are considered.
• Nicole Göckel, Rolf Drechsler
  An Evolutionary Algorithm for Minimizing BDDs of Incompletely Specified Functions
  1997 Advanced Computer Systems, Seiten: 224 - 231
• Christoph Scholl, D. Möller, Paul Molitor, Rolf Drechsler
  BDD Minimization Using Symmetries
  , 1997
• Rolf Drechsler, Nicole Göckel, Elke Mackensen, Bernd Becker
  BEA: Specialized Hardware for Implementation of Evolutionary Algorithms
  1997 Genetic Programming Conf., Seite: 491
• S. Höreth, Rolf Drechsler
  Compilation of Fast Manipulation Algorithms for K*BMDs
  1997 IFIP WG 10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, Seiten: 187 - 196
• Bernd Becker, Rolf Drechsler
  Decision Diagrams in Synthesis - Algorithms, Applications and Extensions -
  1997 Int'l Conf. on VLSI Design, Seiten: 46 - 50
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  An overview on Decision Diagrams (DDs), the state-of-the-art data structure in computer aided design of integrated circuits, is given. The overview is not complete in the sense that all DDs are considered, but we mention the most important with practical relevance. DDs are widely used and in the meantime have also been integrated in commercial tools. In the following special interest is devoted to the use of DDs in the area of synthesis. We also discuss the influence of DDs in other fields and outline future trends.
• Rolf Drechsler, A. Zuzek
  Efficient Functional Diagnosis for Synchronous Sequential Circuits Based on AND/OR Graphs
  1997 Int'l Symp. on IC Technologies, Systems and Applications, Seiten: 312 - 315
• Rolf Drechsler
  Evolutionary Algorithms for Computer Aided Design of Integrated Circuits
  1997 Int'l Symp. on IC Technologies, Systems and Applications, Seiten: 302 - 311
• S. Höreth, Rolf Drechsler
  Fast Construction of Kronecker Decision Diagrams from Library Based Circuits
  1997 SASIMI, Seiten: 39 - 44
• Rolf Drechsler, Nicole Göckel, Wolfgang Günther
  Fast Exact Minimization of BDDs
  , 1997
• Andreas Hett, Rolf Drechsler, Bernd Becker
  Fast and Efficient Construction of BDDs by reordering based Synthesis
  1997 European Design and Test Conf., Seiten: 168 - 175
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  We present a new approach to symbolic simulation with BDDs. Our method uses Reordering Based Synthesis (RBS) whichallows the integration of dynamic variable ordering (even) within a single synthesis operation (e.g. an AND-operation). Thus huge peak sizes during the construction often can be avoided, and we obtain a method that, with no penalty in runtime, is more memory efficient than traditional ITE operator based symbolic simulation. The results are confirmed by experiments on a large set of benchmarks: We give a comparison to several previously published approaches and also consider some industrial benchmarks which are known to be hard to handle.
• Rolf Drechsler, Martin Keim, Bernd Becker
  Fault Simulation in Sequential Multi-Valued Logic Networks
  1997 Int'l Symp. on Multi-Valued Logic, Seiten: 145 - 150
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  In this paper we present a fault simulator for Sequential Multi-Valued Logic Networks (SMVLN). With this tool we investigate their Random Pattern Testability (RPT). We discuss a unified approach for fault models in SMVLNs and show, that it is possible to describe all static fault models with a global formalism. A large set of experimental results is given that demonstrates the efficiency of our approach. For the first time fault coverages for the Stuck-At Fault Model (SAFM) and Skew Fault Model (SKFM) for large sequential circuits are reported.
• Christoph Scholl, Rolf Drechsler, Bernd Becker
  Functional Simulation using Binary Decision Diagrams
  1997 GI/ITG/GME Workshop “Methoden des Entwurfs und der Verifikation digitaler Systeme”
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  In many verification techniques fast functional evaluation of a Boolean network is needed. We investigate the idea of using Binary Decision Diagrams (BDDs) for functional simulation. The area-time trade-off that results from different minimization techniques of the BDD is discussed. We propose new minimization methods based on dynamic reordering that allow smaller representations with (nearly) no runtime penalty.
• Christoph Scholl, Rolf Drechsler, Bernd Becker
  Functional Simulation using Binary Decision Diagrams
  1997 Int'l Workshop on Logic Synth.
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  In many verification techniques fast functional evaluation of a Boolean network is needed. We investigate the idea of using Binary Decision Diagrams (BDDs) for functional simulation. The area-time trade-off that results from different minimization techniques of the BDD is discussed. We propose new minimization methods based on dynamic reordering that allow smaller representations with (nearly) no runtime penalty.
• Rolf Drechsler, Bernd Becker
  Graphenbasierte Funktionsdarstellung
  B.G. Teubner, 1997
• Nicole Göckel, Rolf Drechsler
  Influencing Parameters of Evolutionary Algorithms for Sequencing Problems
  1997 Int'l Conf. on Evolutionary Computation, Seiten: 575 - 580
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  Several problems in Computer Aided Design (CAD) of Integrated Circuits (ICs) have to solve sequencing problems. For this reason many algorithms for solving these problems have been proposed. Especially, Evolutionary Algorithms (EAs) have been successfully applied in the past in these areas. In this paper we study the influence of different parameters on runtime and quality for one specific problem of large practical importance for CAD of ICs, i.e. finding the optimal variable ordering of Ordered Binary Decision Diagrams (OBDDs). We consider different genetic operators and a problem specific heuristic. Our study shows that the influence of problem specific knowledge is much more significant than finetuning the EA, especially if runtime is also considered as an optimization criterion. Our results directly transfer to other sequencing problems.
• Nicole Göckel, Rolf Drechsler, Bernd Becker
  Learning Heuristics for OKFDD Minimization by Evolutionary Algorithms
  1997 ASP Design Automation Conf., Seiten: 469 - 472
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  Ordered Kronecker Functional Decision Diagrams (OKFDDs) are a data structure for efficient representation and manipulation of Boolean functions. OKFDDs are very sensitive to the chosen variable ordering and the decomposition type list, i.e. the size may vary from linear to exponential. In this paper we present an Evolutionary Algorithm (EA) that learns good heuristics for OKFDD minimization starting from a given set of basic operations. The difference to other previous approaches to OKFDD minimization is that the EA does not solve the problem directly. Rather, it develops strategies for solving the problem. To demonstrate the efficiency of our approach experimental results are given. The newly developed heuristics combine high quality results with reasonable time overhead.
• Rolf Drechsler, Nicole Göckel
  Minimization of BDDs by Evolutionary Algorithms
  1997 Int'l Workshop on Logic Synth.
• Martin Keim, M. Martin, Bernd Becker, Rolf Drechsler, Paul Molitor
  Polynomial Formal Verification of Multipliers
  1997 VLSI Test Symp., Seiten: 150 - 155
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  Until recently, verifying multipliers with formal methods was not feasible, even for small input word sizes. About two years ago, a new data structure, called Multiplicative Binary Moment Diagram (*BMD), was introduced for representing arithmetic functions over Boolean variables. Based on this data structure, methods were proposed by which verification of multipliers with input word sizes of up to 256 bits became now feasible. Only experimental data has been provided for these verification methods until now. In this paper we give a formal proof that logic verification using *BMDs is polynomially bounded in both space and time, when applied to the class of Wallace-tree like multipliers.
• Rolf Drechsler
  Pseudo Kronecker Expressions for Symmetric Functions
  1997 Int'l Conf. on VLSI Design, Seiten: 511 - 513
• Andreas Hett, Rolf Drechsler, Bernd Becker
  Reordering Based Synthesis
  1997 iwrm
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  Reordering Based Synthesis (RBS) as an alternative approach to manipulate Decision Diagrams (DDs) is presented. Based on the concept of operation nodes a single "core" operation, i.e. an extended Level Exchange (LE), is sufficient to perform the usual synthesis operations on several types of DDs. RBS allows the integration of dynamic variable ordering (even) within a single synthesis operation (e.g. an AND-operation) and thus provides the possibility of avoiding huge peak sizes during the construction. The optimization potential is significantly enlarged by allowing LEs even between operation nodes. A large number of experimental results for the
• Rolf Drechsler
  Secure Implementation of Decision Diagrams
  1997 Int'l Workshop on Logic Synth.
• Rolf Drechsler, R. S. Stankovic, T. Sasao
  Spectral Transforms and Word-Level Decision Diagrams
  1997 IFIP WG 10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design
• Rolf Drechsler, R. S. Stankovic, T. Sasao
  Spectral Transforms and Word-Level Decision Diagrams
  1997 SASIMI, Seiten: 33 - 38
• Rolf Drechsler, Harry Hengster, H. Schäfer, J. Hartmann, Bernd Becker
  Testability of 2-Level AND/EXOR Expressions
  1997 European Design and Test Conf., Seiten: 548 - 553
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  It is often stated that AND/EXOR circuits are much easier testable than AND/OR circuits. This statement only holds for restricted classes of AND/EXOR expressions, like positive polarity Reed-Muller expressions and fixed polarity Reed-Muller expressions. For these two classes of circuits good deterministic testability properties are known. In this paper we show that for these circuits also good random pattern testability can be proven. An input probability distribution is given which yields a short expected test length for biased random patterns. This is the first time that theoretical results on random pattern testability are presented for 2-level AND/EXOR circuit realizations of arbitrary Boolean functions. For more general classes of 2-level AND/EXOR circuits analogous results are not proven. We present experimental results that show that in general minimized 2-level AND/OR circuits are as well (or badly) testable as minimized 2-level AND/EXOR circuits.

1996

 nach oben zur Jahresübersicht

• Rolf Drechsler, Nicole Göckel
  A Genetic Algorithm for Data Sequencing
  1996 Online Workshop on Evolutionary Computation
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  In this paper we present a Genetic Algorithm (GA) for the Data Ordering Problem (DOP). The DOP has large application in the area of low power design. By the use of more and more battery driven computers low power is becoming one of the main issues in IC design. Since the power consumption in computers is directly proportional to the switching activity, the sequence in which data words are transmitted is of great importance. We implemented a GA to solve this problem and carried out a large set of experiments. A comparison of our results to previously published demonstrates the efficiency of our approach.
• Rolf Drechsler, Bernd Becker, Nicole Göckel
  A Genetic Algorithm for the Construction of Small and Highly Testable OKFDD Circuits
  1996 Genetic Programming Conf., Seiten: 473 - 478
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  A Genetic Algorithm (GA) is applied to derive circuits that combine area efficiency and testability. These circuits are obtained from Ordered Kronecker Functional Decision Diagrams (OKFDDs). Previously a heuristic approach has been presented. In this paper we show how these results can further be improved by GAs. Finally, we apply our minimization algorithm to technology mapping for FPGAs. We present experimental results to show the efficiency of our approach.
• Nicole Göckel, G. Pudelko, Rolf Drechsler, Bernd Becker
  A Hybrid Genetic Algorithm for the Channel Routing Problem
  1996 IEEE Int'l Symp. on Circuits and Systems, Seiten: IV:675 - IV:678
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  We present a Hybrid Genetic Algorithm (HGA) for the Channel Routing Problem (CRP). To do so we combine a Genetic Algorithm (GA) with domain specific knowledge, i.e. the genetic operators make use of the rip-up and reroute technique. Thereby the execution time of our method is faster than previously presented evolutionary based approaches. Furthermore, concerning space complexity we show by experiments that our HGA can handle large channels (with more than 100 columns).
• Rolf Drechsler, Andreas Hett, Bernd Becker
  A Note on Symbolic Simulation using Desicion Diagrams
  1996 ulsi
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  If Decision Diagrams (DDs) are used for the representation of the logical behaviour of a combinational logic circuit it has to be traversed in topological order. At each gate the corresponding synthesis operation is carried out. This traversal process is called symbolic simulation. Obviously the sequence in which the operations are performed at each gate influences the number of nodes needed during the computation. In this paper we consider different traversal strategies for OBDDs and OMDDs. We compare them by means of experiments.
• Harry Hengster, Rolf Drechsler, S. Eckrich, T. Pfeiffer, Bernd Becker
  AND/EXOR based Synthesis of Testable KFDD-Circuits with Small Depth
  1996 GI/ITG Workshop “Testmethoden und Zuverlässigkeit von Schaltungen und Systemen”
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  Decision diagrams are used in design automation for efficient representation of Boolean functions. But it is also possible to derive circuits directly from decision diagrams. In this paper we present an approach to synthesize circuits from a very general class of decision diagrams, the ordered Kronecker functional decision diagrams. We investigate area, depth and testability of the synthesized circuits and compare them to circuit designs generated by other synthesis tools. Experimental results show that the presented approach is suitable to overcome the trade-off between depth and testability.
• Harry Hengster, Rolf Drechsler, S. Eckrich, T. Pfeiffer, Bernd Becker
  AND/EXOR based Synthesis of Testable KFDD-Circuits with Small Depth
  1996 IEEE Asian Test Symp., Seiten: 148 - 154
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  Decision Diagrams are used in design automation for efficient representation of Boolean functions. It is also possible to directly derive circuits from Decision Diagrams. In this paper we present an approach to synthesize circuits from a very general class of Decision Diagrams, the ordered Kronecker Functional Decision Diagrams. These Decision Diagrams make use of Davio decompositions which are based on exclusive-or operations and therefore allow the use of EXOR gates in the synthesized circuits. We investigate area, depth, and testability of these circuits and compare them to circuit designs generated by other synthesis tools. Experimental results show that the presented approach is suitable to overcome the trade-off between depth and testability at the price of reasonable area overhead.
• Rolf Drechsler, A. Zuzek
  Efficient Functional Diagnosis for Synchronous Sequential Circuits based on AND/OR Graphs
  , 1996
• Bernd Becker, Rolf Drechsler
  Exact Minimization of Kronecker Expressions for Symmetric Functions
  1996 IEEE Int'l Symp. on Circuits and Systems, Seiten: IV:388 - IV:391
• Rolf Drechsler, H. Esbensen, Bernd Becker
  Genetic Algorithms in Computer Aided Design of Integrated Circuits
  1996 Online Workshop on Evolutionary Computation
• Rolf Drechsler, Nicole Göckel, Bernd Becker
  Learning Heuristics for OBDD Minimization by Evolutionary Algorithms
  1996 Parallel Problem Solving from Nature, Springer Verlag, Band: 1141, Seiten: 730 - 739
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  Ordered Binary Decision Diagrams (OBDDs) are the state-of-the-art data structure in CAD for ICs. OBDDs are very sensitive to the chosen variable ordering, i.e. the size may vary from linear to exponential. In this paper we present an Evolutionary Algorithm (EA) that learns good heuristics for OBDD minimization starting from a given set of basic operations. The difference to other previous approaches to OBDD minimization is that the EA does not solve the problem directly. Rather, it developes strategies for solving the problem. To demonstrate the efficiency of our approach experimental results are given. The newly developed heuristics are more efficient than other previously presented methods.
• Andreas Hett, Rolf Drechsler, Bernd Becker
  MORE Optimization Techniques.
  , 1996
• Rolf Drechsler, Bernd Becker
  OKFDDs - Algorithms, Applications and Extensions
  Kluwer Academic Publisher, Seiten: 163 - 190, 1996
• Bernd Becker, Rolf Drechsler, Reinhard Enders
  On the Computational Power of Bit-Level and Word-Level Decision Diagrams
  1996 GI/ITG/GME Workshop “Methoden des Entwurfs und der Verifikation digitaler Systeme”
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  Several types of Decision Diagrams (DDs) have have been proposed in the area of Computer Aided Design (CAD), among them being bit-level DDs like OBDDs, OFDDs and OKFDDs. While the aforementioned types of DDs are suitable for representing Boolean functions at the bit-level and have proved useful for a lot of applications in CAD, recently DDs to represent integer-valued functions, like MTBDDs (=ADDs), EVBDDs, FEVBDDs, (*)BMDs, HDDs (=KBMDs), and K*BMDs, attract more and more interest, e.g., using *BMDs it was for the first time possible to verify multipliers of bit length up to n=256. In this paper we clarify the computational power of these DD classes. Several (inclusion) relations and (exponential) gaps between specific classes differing in the availability of additive and/or multiplicative edge weights and in the choice of decomposition types are shown. It turns out for example, that K(*)BMDs, a generalization of OKFDDs to the word-level, also "include" OBDDs, MTBDDs and (*)BMDs. On the other hand, it is demonstrated that a restriction of the K(*)BMD concept to subclasses, such as OBDDs, MTBDDs, (*)BMDs as well, results in families of functions which lose their efficient representation.
• Rolf Drechsler
  Pseudo Kronecker Expressions for Symmetric Functions
  , 1996
• Rolf Drechsler, Harry Hengster, H. Schäfer, Bernd Becker
  Testability of AND/EXOR Expressions
  1996 European Test Workshop
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  It is often stated that AND/EXOR circuits are much easier testable than AND/OR circuits. In this paper we show that this is not true for all 2-level circuits based on EXOR. The statement only holds for restricted classes of AND/EXOR expressions, like Positive Polarity Reed-Muller Expressions and Fixed Polarity Reed-Muller Expressions. AND/EXOR circuits are studied with respect to deterministic and random pattern testability. We present experimental results that show that in general minimized 2-level AND/OR circuits are as well (or badly) testable as minimized 2-level AND/EXOR circuits.
• Andreas Hett, Rolf Drechsler, Bernd Becker
  The DD Package PUMA - An Online Documentation
  https://ira.informatik.uni-freiburg.de/software/puma/, 1996
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  PUMA is a DD-Package for the efficient representation and manipulation of Boolean Functions with OKFDDs as well as Zero-Suppressed BDDs.
• Rolf Drechsler
  Verification of Multi-Valued Logic Networks
  1996 Int'l Symp. on Multi-Valued Logic, Seiten: 10 - 15
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  In this paper a method for verification of Multi-Valued Logic Networks (MVLNs) using Ordered Multi-Valued Decision Diagrams (OMDDs) is presented. For tree-like MVLNs an upper bound on the OMDD size can be proven. Thus, heuristics known for OBDDs can also be used for OMDDs. A large set of experiments is presented that underlines the efficiency of the approach.

1995

 nach oben zur Jahresübersicht

• Rolf Drechsler, Bernd Becker, Nicole Göckel
  A Genetic Algorithm for 2-Level AND/EXOR Minimization
  1995 SASIMI, Seiten: 49 - 56
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  We show that there is a close relation between Ordered Kronecker Functional Decision Diagrams (OKFDDs) and 2-level AND/EXOR Expressions. This relation together with efficient OKFDD algorithms can be utilized for exact and heuristic minimization of these AND/EXOR expressions, called Reduced Kronecker Expressions (RKROs). We propose several (exact and heuristical) minimization algorithms and demonstrate the efficiency of our approach by experimental results. A Genetic Algorithm (GA) is applied to minimize RKROs. Minimized RKROs are determined for benchmark functions with up to 100 variables. Furthermore, we compare our solutions to results obtainable for other classes of 2-level AND/EXOR forms. In particular, AND/EXOR expressions derived from OKFDDs turn out to be much smaller than the well-known class of Fixed-Polarity Reed-Muller Expressions (FPRMs), although the complexity of the minimization algorithms is comparable. Our GA approach is a practical alternative to the exact algorithm. It produced optimal results for all considered benchmarks, but it is also applicable to functions with more than 20 variables due to its short runtimes.
• Rolf Drechsler, Bernd Becker, Nicole Göckel
  A Genetic Algorithm for Variable Ordering of OBDDs
  1995 Int'l Workshop on Logic Synth., Seiten: 5c:5.55 - 5.64
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  A Genetic Algorithm (GA) is applied to find a variable ordering that minimizes the size of Ordered Binary Decision Diagrams (OBDDs). OBDDs are a data structure for representation and manipulation of Boolean functions often applied in CAD. The choice of the variable ordering largely influences the size of the OBDD, i.e. its size may vary from polynomial to exponential. Dynamic variable ordering is the state-of-the-art method for finding good variable orderings. In this paper we show by experimental results that better sizes can be obtained using GAs. Our GA approach is a practical alternative to the exact algorithm for variable ordering. It produced optimal results for most considered benchmarks, but it is also applicable to functions with more than 20 variables due to its short runtimes.
• Rolf Drechsler, Bernd Becker, Nicole Göckel
  A Genetic Algorithm for Variable Ordering of OBDDs
  , Nummer: 5/95, 1995
• Harry Hengster, Rolf Drechsler, Bernd Becker
  AND/OR/EXOR based Synthesis of KFDD-Circuits with Small Depth
  1995 Reed-Muller Colloquium UK
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  Construction of circuits from Decision Diagrams (DDs) has shown several advantages, e.g. the resulting circuits have nice testability properties. One major drawback of circuits derived from ordered DDs is that their depth is proportional to the number of inputs. In this paper we present an approach to design DD circuits derived from Kronecker Functional DDs (KFDDs) with small depth. Experimental results are given that show the efficiency of our approach.
• Rolf Drechsler, Bernd Becker, S. Ruppertz
  Dynamic Minimization of K*BMDs
  , 1995
• Rolf Drechsler, Bernd Becker
  Dynamic Minimization of OKFDDs
  , Nummer: 5/95, 1995
• Bernd Becker, Rolf Drechsler
  Exact Minimization of Kronecker Expressions for Symmetric Functions
  1995 IFIP WG 10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, Seiten: 240 - 245
• Bernd Becker, Rolf Drechsler, M. Theobald
  OKFDDs versus OBDDs and OFDDs
  1995 ICALP, Springer Verlag, Band: 944, Seiten: 475 - 486
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  Ordered Decision Diagrams (ODDs) as a means for the representation of Boolean functions are used in many applications in CAD. Depending on the decomposition type, various classes of ODDs have been defined, the most important being the Ordered Binary Decision Diagrams (OBDDs), the Ordered Functional Decision Diagrams (OFDDs) and the Ordered Kronecker Functional Decision Diagrams (OKFDDs). In this paper we clarify the computational power of OKFDDs versus OBDDs and OFDDs from a (more) theoretical point of view. We prove several exponential gaps between specific types of ODDs. Combining these results it follows that a restriction of the OKFDD concept to subclasses, such as OBDDs and OFDDs as well, results in families of functions which lose their efficient representation.
• Bernd Becker, Rolf Drechsler, Reinhard Enders
  On the Computational Power of Bit-Level and Word-Level Decision Diagrams
  , 1995
• Bernd Becker, Rolf Drechsler, R. Werchner
  On the Relation Between BDDs and FDDs
  1995 Information and Computation, Band: 123(2), Seiten: 185 - 197
• Rolf Drechsler
  Ordered Kronecker Functional Decision Diagrams und ihre Anwendungen
  Modell Verlag, Ph.D. thesis at J.W. Goethe-Universität, 1995
• Rolf Drechsler, Bernd Becker
  PUMA: An OKFDD-Package and its Implementation
  1995 European Design and Test Conf.
• Bernd Becker, Rolf Drechsler
  Synthesis for Testability: Circuits Derived from Ordered Kronecker Functional Decision Diagrams
  1995 European Design and Test Conf., Seite: 592
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  Testability properties of circuits derived from Ordered Kronecker Functional Decision Diagrams (OKFDDs) are studied with respect to the Stuck-At Fault Model (SAFM) and the Cellular Fault Model (CFM). The computation of complete test sets and of all occuring redundancies can be done easily and efficiently and circuits with high testability can be obtained. The full paper including experimental results can be obtained from the authors.

1994

 nach oben zur Jahresübersicht

• Rolf Drechsler
  BiTeS: A BDD based test pattern generator for strong robust path delay faults
  1994 GI/ITG Workshop “Testmethoden und Zuverlässigkeit von Schaltungen und Systemen”
• Rolf Drechsler
  BiTeS: A BDD based test pattern generator for strong robust path delay faults
  1994 European Design Automation Conf., Seiten: 322 - 327
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  This paper presents an algorithm for generation of test patterns for strong robust path delay faults, i.e. tests that propagate the fault along a single path and additionally are hazard free. The algorithm uses Binary Decision Diagrams (BDDs) for the computation and representation of the test sets. It has been implemented as the program BiTeS. The implementation is very simple, since only BDD operations must be carried out. BiTeS computes the complete set of patterns that lead to a test instead of a single test. Thus, methods for test set compaction can easily be applied. Experimental results are presented to demonstrate the efficiency of BiTeS.
• Rolf Drechsler, M. Theobald, Bernd Becker
  Fast FDD based Minimization of Generalized Reed-Muller Forms
  1994 Workshop über Komplexitätstheorie, Datenstrukturen und effiziente Algorithmen Workshop über Komplexitätstheorie, Datenstrukturen und effiziente Algorithmen
• Rolf Drechsler, H. Esbensen, Bernd Becker
  Genetic Algorithms in Computer Aided Design of Integrated Circuits
  , Nummer: 17/94, 1994
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  An increasing number of successful applications of Genetic Algorithms (GAs) within Computer Aided Design (CAD) of Integrated Circuits (ICs) is reported in the literature. The problems dealt with in this field consist of sequences of sub-problems, which are characterized by being NP-hard, large and mutually dependent. This very high level of complexity should make the GA a well suited approach, at least in principle. However, the GA is of practical interest to the CAD community if and only if it is competitive to the existing approaches with respect to performance. With this fact as the starting point, the purpose of this paper is to discuss how to develop high-performance GAs for CAD of ICs . After reviewing a number of recent, performance competitive GAs for key problems in CAD of ICs, the common characteristics of these algorithms are discussed. They all exploit problem specific knowledge in various ways or are integrated with other heuristics. The paper also discusses performance evaluation principles. To make an impact, it is crucial that performance is evaluated using the measures commonly applied in the CAD field. The practical implications hereof for GA-based applications are addressed.
• Bernd Becker, Rolf Drechsler, M. Theobald
  Minimization of 2-level AND/XOR Expressions using Ordered Kronecker Functional Decision Diagrams
  , Nummer: 3/94, 1994
• Rolf Drechsler, Bernd Becker, A. Jahnke
  On Variable Ordering and Decomposition Type Choice in OKFDDs
  1994 Workshop über Komplexitätstheorie, Datenstrukturen und effiziente Algorithmen
• Rolf Drechsler, Bernd Becker, A. Jahnke
  On Variable Ordering and Decomposition Type Choice in OKFDDs
  , Nummer: 11/94, 1994
• Bernd Becker, Rolf Drechsler, M. Theobald
  On Variable Ordering of Functional Decision Diagrams
  , Nummer: TR-94-006, 1994
• Bernd Becker, Rolf Drechsler, M. Theobald
  On Variable Ordering of Ordered Functional Decision Diagrams
  1994 GI/GME/ITG-Fachtagung “Rechnergestützter Entwurf und Architektur mikroelektronischer Systeme”, Springer Verlag, Seiten: 62 - 71
• Rolf Drechsler, A. Sarabi, M. Theobald, Bernd Becker, M. A. Perkowski
  On the Computational Power of Ordered Kronecker Functional Decision Diagrams
  , Nummer: 4/94, 1994
• Rolf Drechsler, A. Sarabi, M. Theobald, Bernd Becker, M. A. Perkowski
  Ordered Kronecker Functional Decision Diagrams: An Efficient Tool for Synthesis and Verification
  1994 GI/ITG Workshop “Anwendung formaler Methoden im Systementwurf”
• D. Möller, Paul Molitor, Rolf Drechsler
  Symmetry based Variable Ordering for ROBDDs
  1994 IFIP Workshop on Logic and Architecture Synthesis, Grenoble, Seiten: 47 - 53
• Bernd Becker, Rolf Drechsler
  Synthesis for Testability: Circuits Derived from Ordered Kronecker Functional Decision Diagrams
  1994 Int'l Test Synthesis Workshop
• Bernd Becker, Rolf Drechsler
  Synthesis for Testability: Circuits Derived from Ordered Kronecker Functional Decision Diagrams
  , Nummer: 14/94, 1994
• Harry Hengster, Rolf Drechsler, Bernd Becker
  Testability Properties of Local Circuit Transformations with Respect to the Robust Path-Delay-Fault Model
  1994 Int'l Conf. on VLSI Design, Seiten: 123 - 126
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  We present a new approach to show that local circuit transformations which improve the area of a circuit preserve or improve robust path-delay-fault testability. In contrast to previously published methods which had to consider the whole circuit we examine only the subcircuits to be transformed. Furthermore, we present some transformations which preserve or improve testability.
• Bernd Becker, Rolf Drechsler
  Testability of Circuits Derived from Functional Decision Diagrams
  1994 European Design and Test Conf., Seite: 667
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  We investigate the testability properties of Boolean networks derived from a special class of multi-level AND/ EXOR expressions, called ordered functional decicision diagrams (OFDDs). We consider the stuck-at fault model (SAFM) and the cellular fault model (CFM). All occuring redundancies are classified. The resulting circuits are highly testable with nearly 100% fault coverage on average. The full paper including all experimental results can be obtained from the authors.

1993

 nach oben zur Jahresübersicht

• Bernd Becker, Rolf Drechsler, Harry Hengster, R. Krieger, R. Sinković
  Binary Decision Diagrams and Testing
  1993 GI/ITG Workshop “Testmethoden und Zuverlässigkeit von Schaltungen und Systemen”
  » Kurzfassung anzeigen« Kurzfassung verbergen
  Kurzfassung

  Binary Decision Diagrams (BDD's) can be successfully applied to a wide variety of tasks in digital system design, verification and testing. In this paper we focus on the area of testing and demonstrate how two key problems, the computation of signal and fault detection probabilities and the synthesis of testable circuits, can profit from a BDD-based approach.
• Rolf Drechsler, A. Sarabi, M. Theobald, Bernd Becker, M. A. Perkowski
  Efficient Representation and Manipulation of Switching Functions Based on Ordered Kronecker Functional Decision Diagrams
  , Nummer: 14/93, 1993
• Rolf Drechsler, M. Theobald, Bernd Becker
  Fast FDD based Minimization of Generalized Reed-Muller Forms
  , Nummer: 15/93, 1993
• Bernd Becker, Rolf Drechsler, Harry Hengster
  Local Circuit Transformations Preserving Robust Path-Delay-Fault Testability
  , Nummer: 1/93, 1993
• Bernd Becker, Rolf Drechsler, Paul Molitor
  On Generation of Area-Time Optimal Testable Adders
  1993 Technical Report 3/93
• Bernd Becker, Rolf Drechsler, M. Theobald
  On Variable Ordering of Functional Decision Diagrams
  , 1993
• Bernd Becker, Rolf Drechsler
  On the Computational Power of Functional Decision Diagrams
  1993 Workshop über Komplexitätstheorie, Datenstrukturen und effiziente Algorithmen Workshop über Komplexitätstheorie, Datenstrukturen und effiziente Algorithmen
• Bernd Becker, Rolf Drechsler, M. Theobald
  On the Implementation of a Package for Efficient Representation and Manipulation of Functional Decision Diagrams
  1993 IFIP WG 10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, Seiten: 162 - 169
• Bernd Becker, Rolf Drechsler, R. Werchner
  On the Relation between BDDs and FDDs
  , Nummer: 12/93, 1993
• Bernd Becker, Rolf Drechsler, Christoph Meinel
  On the Testability of Circuits Derived from Binary Decision Diagrams
  , Nummer: 9/93, 1993
• Rolf Drechsler, Bernd Becker
  Rapid Prototyping of Fully Testable Multi-Level AND/EXOR Networks
  1993 IFIP WG 10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, Seiten: 126 - 133
• Bernd Becker, Rolf Drechsler
  Testability of Circuits Derived from Functional Decision Diagrams
  , 1993

1992

 nach oben zur Jahresübersicht

• Rolf Drechsler, Bernd Becker, Paul Molitor
  A Performance Oriented Generator for Robust Path-Delay-Fault Testable Adders
  1992 GI/ITG Workshop “Testmethoden und Zuverlässigkeit von Schaltungen und Systemen”
• Bernd Becker, Rolf Drechsler, Paul Molitor
  On the Implementation of an Efficient Performance Driven Generator for Conditional-Sum-Adders.
  1992 Technical Report 2/93
• Rolf Drechsler, Bernd Becker
  Rapid Prototyping of Robust Path-Delay-Fault Testable Circuits Derived from Binary Decision Diagrams
  , Nummer: TR-17/92, SFB 124, 1992