2003

 back to the year overview

• Frank Schmiedle, Rolf Drechsler, Bernd Becker
  Exact Routing with Search Space Reduction
  2003 IEEE Trans. on Computers, volume: 52, issue: 6, pages: 815 - 825
• Frank Schmiedle
  Exakte Verdrahtung mit symbolischen Methoden
  Logos Verlag, Berlin, 2003
  » show abstract« hide abstract
  Abstract

  Verdrahtung ist eine wichtige Aufgabe im Bereich derphysikalischen Synthese des computergestützten Schaltkreisentwurfs.Obwohl heuristische Ansätze oft brauchbare Resultateliefern, treten gerade in der Praxis auch immerwieder Probleminstanzen auf, bei denen die durchheuristische Methoden gefundenen Lösungenunzureichend sind.In diesem Buch wird ein exaktes Verdrahtungsverfahren behandelt. Dieses bedient sich symbolischer Methoden, was in diesem Fall bedeutet, dass zur Repräsentation von Verdrahtungsregionen Entscheidungsdiagrammeverwendet werden.Im ersten Teil des Buches wird in erster Linieauf die hier relevanten Varianten von Entscheidungsdiagrammen eingegangen - in diesem Rahmen werden auch ausgewählteVerfahren zu deren Minimierung diskutiert.Der zweite Teil beschäftigt sich mit der lokalen Verdrahtung. Neben einer detailliertenBeschreibung des exakten Verdrahtungsansatzeswerden hier auch die Möglichkeiten der praktischenAnwendung des Verfahrens beleuchtet.

2001

 back to the year overview

• Nicole Drechsler, Frank Schmiedle, Daniel Große, Rolf Drechsler
  Heuristic Learning based on Genetic Programming
  2001 EuroGP, Springer Verlag, volume: 2038, pages: 1 - 10
• Frank Schmiedle, Nicole Drechsler, Daniel Große, Rolf Drechsler
  Priorities in Multi-Objective Optimization for Genetic Programming
  2001 Conf. on Genetic and Evolutionary Computation, pages: 129 - 136
  » show abstract« hide abstract
  Abstract

  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, pages: 299 - 304
  » show abstract« hide abstract
  Abstract

  Multi-valued decision diagrams (MDDs) are a generalization of binary decision diagrams (BDDs). They are suitable for several applications in synthesis and verification of integrated circuits since often, functions with multi-valued input variables can be represented efficiently by MDDs. Their sizes counted in number of nodes vary from linear to exponential dependent on the variable ordering used. Therefore sifting, i.e. dynamic variable re-ordering, has to be applied frequently while an MDD is built in order to keep the number of nodes needed during the process small. Often most of the runtime for MDD construction is spent for sifting. We present a new method that speeds up MDD construction and also reduces memory consumption. It is based on the selection of re-ordering heuristics dependent on the history of the construction process. Success of previous re-ordering steps as well as the frequency of sifting calls in the past are used to determine a variation of sifting that is applied next. Experimental results are given to demonstrate that runtimes and memory consumption can be reduced by 30 percent on average when the proposed selection methods are used during MDD construction.
• 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, volume: 2206, pages: 479 - 491
  » show abstract« hide abstract
  Abstract

  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.
• Frank Schmiedle, A. Markert, Bernd Becker
  XMaDRE: A Routing Environment with Visualization based on Ray-Tracing
  2001 Conf. on Design, Automation and Test in Europe

2000

 back to the year overview

• Frank Schmiedle, Wolfgang Günther, Rolf Drechsler
  Dynamic Re-Encoding During MDD Minimization
  2000 Int'l Symp. on Multi-Valued Logic, pages: 239 - 244
  » show abstract« hide abstract
  Abstract

  Multi-valued decision diagrams (MDDs) are a generalization of binary decision diagrams (BDDs). They often allow efficient representation of functions with multi-valued input variables similar to BDDs in the binary case. Therefore they are suitable for several applications in synthesis and verification of integrated circuits. MDD sizes counted in number of nodes vary from linear to exponential dependent on the variable ordering used. In all these applications, minimization of MDDs is crucial. In many cases, multi-valued variables are composed by a certain number of binary variables, and so the multi-valued inputs arise by grouping binary variables. The selection of these groups, that is, the decision which variables to merge, has enormous impact on MDD sizes. Techniques for finding variable groupings before starting MDD minimization have been proposed recently. In this paper, we present a new method that uses re-encoding, i.e. dynamic variable grouping. We don't choose one fixed variable grouping before minimizing MDDs, but allow to change the binary variables to be considered together during the minimization process. This is possible since MDDs are simulated on top of BDDs. By this, the underlying binary variables remain accessible throughout the minimization process. This technique is described in detail and we also show experimental results that demonstrate the efficiency of our approach.
• Frank Schmiedle, D. Unruh, Bernd Becker
  Exact Switchbox Routing with Search Space Reduction
  2000 Int'l Symp. on Physical Design, pages: 26 - 32
  » show abstract« hide abstract
  Abstract

  We present an approach for exact switchbox routing that complements traditional routing techniques. It is particularly well suited for an application to dense problem instances and the completion of routing in subregions which turn out to be difficult for routing tools based on heuristic methods. The exact router proposed uses symbolic methods i.e. MDDs (Multi-valued Decision Diagrams) for representation of the routing space. All possible solutions to the routing problem are represented by one single MDD and once this MDD is given, routability can be decided within constant time. To reduce the search space of possible routing solutions, so-called forced cells are computed. Finally, experimental results are given. They show the feasibility and the practicability of the approach.