Rolf Drechsler - Böcker

VLSI CADhas greatly bene?ted from the use of reduced ordered Binary Decision Diagrams (BDDs) and the clausal representation as a problem of Boolean Satis?ability (SAT), e.g. in logic synthesis, ver- cation or design-for-testability. In recent practical applications, BDDs are optimized with respect to new objective functions for design space exploration. The latest trends show a growing number of proposals to fuse the concepts of BDD and SAT. This book gives a modern presentation of the established as well as of recent concepts. Latest results in BDD optimization are given, c- ering di?erent aspects of paths in BDDs and the use of e?cient lower bounds during optimization. The presented algorithms include Branch ? and Bound and the generic A -algorithm as e?cient techniques to - plore large search spaces. ? The A -algorithm originates from Arti?cial Intelligence (AI), and the EDA community has been unaware of this concept for a long time. Re- ? cently, the A -algorithm has been introduced as a new paradigm to explore design spaces in VLSI CAD. Besides AI search techniques, the book also discusses the relation to another ?eld of activity bordered to VLSI CAD and BDD optimization: the clausal representation as a SAT problem.

Spectral techniques in VLSI CAD have become a subject of renewed interest in the design automation community due to the emergence of efficient methods for the computation of discrete function spectra. In the past, spectral computations for digital logic were too complex for practical implementation. The use of decision diagrams for spectral computations has greatly reduced this obstacle allowing for the development of new and useful spectral techniques for VLSI synthesis and verification. Several algorithms for the computation of the Walsh, Reed-Muller, arithmetic and Haar spectra are described. The relation of these computational methods to traditional ones is also provided. Spectral Techniques in VLSI CAD provides a unified formalism of the representation of bit-level and word-level discrete functions in the spectral domain and as decision diagrams. An alternative and unifying interpretation of decision diagram representations is presented since it is shown that many of the different commonly used varieties of decision diagrams are merely graphical representations of various discrete function spectra.Viewing various decision diagrams as being described by specific sets of transformation functions not only illustrates the relationship between graphical and spectral representations of discrete functions, but also gives insight into how various decision diagram types are related. Spectral Techniques in VLSI CAD describes several new applications of spectral techniques in discrete function manipulation including decision diagram minimization, logic function synthesis, technology mapping and equivalence checking. The use of linear transformations in decision diagram size reduction is described and the relationship to the operation known as spectral translation is described. Several methods for synthesizing digital logic circuits based on a subset of spectral coefficients are described. An equivalence checking approach for functional verification is described based upon the use of matching pairs of Haar spectral coefficients.

Formal verification has become one of the most important steps in circuit design. Since circuits can contain several million transistors, verification of such large designs becomes more and more difficult. Pure simulation cannot guarantee the correct behavior and exhaustive simulation is often impossible. However, many designs, like ALUs, have very regular structures that can be easily described at a higher level of abstraction. For example, describing (and verifying) an integer multiplier at the bit-level is very difficult, while the verification becomes easy when the outputs are grouped to build a bit-string. Recently, several approaches for formal circuit verification have been proposed that make use of these regularities. These approaches are based on Word-Level Decision Diagrams (WLDDs) which are graph-based representations of functions (similar to BDDs) that allow for the representation of functions with a Boolean range and an integer domain. Formal Verification of Circuits is devoted to the discussion of recent developments in the field of decision diagram-based formal verification.Firstly, different types of decision diagrams (including WLDDs) are introduced and theoretical properties are discussed that give further insight into the data structure. Secondly, implementation and minimization concepts are presented. Applications to arithmetic circuit verification and verification of designs specified by hardware description languages are described to show how WLDDs work in practice. Formal Verification of Circuits is intended for CAD developers and researchers as well as designers using modern verification tools. It will help people working with formal verification (in industry or academia) to keep informed about recent developments in this area.

In VLSI CAD, difficult optimization problems have to be solved on a constant basis. Various optimization techniques have been proposed in the past. While some of these methods have been shown to work well in applications and have become somewhat established over the years, other techniques have been ignored. Recently, there has been a growing interest in optimization algorithms based on principles observed in nature, termed Evolutionary Algorithms (EAs). This volume presents the basic concepts of EAs, and considers the application of EAs in VLSI CAD. It is the first book to show how EAs could be used to improve IC design tools and processes. Several successful applications from different areas of circuit design, like logic synthesis, mapping and testing, are described in detail. The volume is in two parts: the first part discusses basic principles of EAs and provides some easy-to-understand examples. Furthermore, a theoretical model for multi-objective optimization is presented. In the second part a software implementation of EAs is supplied, together with detailed descriptions of several EA applications.These applications cover a wide range of VLSI CAD, and different methods for using EAs are described. The book is intended for CAD developers and researchers as well as those working in evolutionary algorithms and techniques supporting modern design tools and processes.

This text is intended both for newcomers to BDDs and for researchers and practitioners who need to implement them. Apart from giving a quick start for the reader who is not familiar with BDDs (or DDs in general), it also discusses several new aspects of BDDs, e.g. with respect to minimization and implementation of a package.

The size of technically producible integrated circuits increases continuously. But the ability to design and verify these circuits does not keep up with this development. Therefore, today’s design ?ow has to be improved to achieve a higher productivity. In this book the current design methodology and ver- cation methodology are analyzed, a number of de?ciencies are identi?ed, and solutions are suggested. Improvements in the methodology as well as in the underlying algorithms are proposed. An in-depth presentation of preliminary concepts makes the book self-contained. Based on this foundation major - sign problems are targeted. In particular, a complete tool ?ow for Synthesis for Testability of SystemC descriptions is presented. The resulting circuits are completely testable and test pattern generation in polynomial time is possible. Veri?cation issues are covered in even more detail. A whole new paradigm for formal design veri?cation is suggested. This is based upon design und- standing, the automatic generation of properties, and powerful tool support for debugging failures. All these new techniques are empirically evaluated and - perimental results are provided. As a result, an enhanced design ?ow is created that provides more automation (i.e. better usability) and reduces the probability of introducing conceptual errors (i.e. higher robustness). Acknowledgments We would like to thank all members of the research group for computer arc- tecture in Bremen for the helpful discussions and the great atmosphere during work and research.

The design process of digital circuits is often carried out in individual steps, like logic synthesis, mapping, and routing. Since the complete process is too complex, it has been split up in several - more or less independent - phases. During the latter half of the 20th century, powerful algorithms were developed to find optimal solutions for each of these steps, though these are rarely used. This neglect leads to quality loss, as optimized netlists fit badly onto the target architecture. Since the resulting circuits are often far from being optimal and insufficient regarding the optimization criteria, several iterations of the complete design process have to be carried out to get high quality results. This is a very time consuming and costly process. For this reason, the idea of one-pass synthesis was explored. There are two main approaches how to guarantee that a design is "right first time": combining levels that were split before, for example, to use layout information already during the logic synthesis phase; and restricting the optimization in one level such that it better fits to the next one.Several approaches in these two directions have been presented and new techniques are under development at the beginning of the 21st century. This title describes the paradigm that is used in one-pass synthesis and presents examples for the two techniques above. Theoretical and practical aspects are discussed and minimization algorithms are given.

This text describes how Evolutionary Algorithm (EA) concepts can be applied to circuit and system design - an area where time-to-market demands are critical. EAs create an interesting alternative to other approaches since they can be scaled with the problem size and can be easily run on parallel computer systems. It presents several successful EA techniques and shows how they can be applied at different levels of the design process. Starting on a high-level abstraction, where software components are dominant, several optimization steps are demonstrated, including DSP code optimization and test generation. Throughout the book, EAs are tested on real-world applications and on large problem instances. For each application the main criteria for the successful application in the corresponding domain are discussed. In addition, contributions from leading international researchers provide the reader with a variety of perspectives, including a special focus on the combination of EAs with problem specific heuristics.

Advanced Formal Verification shows the latest developments in the verification domain from the perspectives of the user and the developer. World leading experts describe the underlying methods of today's verification tools and describe various scenarios from industrial practice. In the first part of the book the core techniques of today's formal verification tools, such as SAT and BDDs are addressed. In addition, multipliers, which are known to be difficult, are studied. The second part gives insight in professional tools and the underlying methodology, such as property checking and assertion based verification. Finally, analog components have to be considered to cope with complete system on chip designs.

The size of technically producible integrated circuits increases continuously. But the ability to design and verify these circuits does not keep up with this development. Therefore today's design flow has to be improved to achieve a higher productivity. In Robustness and Usability in Modern Design Flows the current design methodology and verification methodology are analyzed, a number of deficiencies are identified and solutions suggested. Improvements in the methodology as well as in the underlying algorithms are proposed. An in-depth presentation of preliminary concepts makes the book self-contained. Based on this foundation major design problems are targeted. In particular, a complete tool flow for Synthesis for Testability of SystemC descriptions is presented. The resulting circuits are completely testable and test pattern generation in polynomial time is possible. Verification issues are covered in even more detail. A whole new paradigm for formal design verification is suggested. This is based upon design understanding, the automatic generation of properties and powerful tool support for debugging failures.All these new techniques are empirically evaluated and experimental results are provided. As a result, an enhanced design flow is created that provides more automation (i.e. better usability) and reduces the probability of introducing conceptual errors (i.e. higher robustness).

Formal verification has become one of the most important steps in circuit design. Since circuits can contain several million transistors, verification of such large designs becomes more and more difficult. Pure simulation cannot guarantee the correct behavior and exhaustive simulation is often impossible. However, many designs, like ALUs, have very regular structures that can be easily described at a higher level of abstraction. For example, describing (and verifying) an integer multiplier at the bit-level is very difficult, while the verification becomes easy when the outputs are grouped to build a bit-string. Recently, several approaches for formal circuit verification have been proposed that make use of these regularities. These approaches are based on Word-Level Decision Diagrams (WLDDs) which are graph-based representations of functions (similar to BDDs) that allow for the representation of functions with a Boolean range and an integer domain. Formal Verification of Circuits is devoted to the discussion of recent developments in the field of decision diagram-based formal verification.Firstly, different types of decision diagrams (including WLDDs) are introduced and theoretical properties are discussed that give further insight into the data structure. Secondly, implementation and minimization concepts are presented. Applications to arithmetic circuit verification and verification of designs specified by hardware description languages are described to show how WLDDs work in practice. Formal Verification of Circuits is intended for CAD developers and researchers as well as designers using modern verification tools. It will help people working with formal verification (in industry or academia) to keep informed about recent developments in this area.

In VLSI CAD, difficult optimization problems have to be solved on a constant basis. Various optimization techniques have been proposed in the past. While some of these methods have been shown to work well in applications and have become somewhat established over the years, other techniques have been ignored. Recently, there has been a growing interest in optimization algorithms based on principles observed in nature, termed Evolutionary Algorithms (EAs). Evolutionary Algorithms in VLSI CAD presents the basic concepts of EAs, and considers the application of EAs in VLSI CAD. It is the first book to show how EAs could be used to improve IC design tools and processes. Several successful applications from different areas of circuit design, like logic synthesis, mapping and testing, are described in detail. Evolutionary Algorithms in VLSI CAD consists of two parts. The first part discusses basic principles of EAs and provides some easy-to-understand examples. Furthermore, a theoretical model for multi-objective optimization is presented. In the second part a software implementation of EAs is supplied together with detailed descriptions of several EA applications.These applications cover a wide range of VLSI CAD, and different methods for using EAs are described. Evolutionary Algorithms in VLSI CAD is intended for CAD developers and researchers as well as those working in evolutionary algorithms and techniques supporting modern design tools and processes.

Within the last 10-13 years Binary Decision Diagrams (BDDs) have become the state-of-the-art data structure in VLSI CAD for representation and manipulation of Boolean functions. Today, BDDs are widely used and in the meantime have also been integrated in commercial tools, especially in the area of verification and synthesis. The interest in BDDs results from the fact that the data structure is generally accepted as providing a good compromise between conciseness of representation and efficiency of manipulation. With increasing numbers of applications, also in non-CAD areas, classical methods of handling BDDs are being improved and new questions and problems evolve and have to be solved. Binary Decision Diagrams: Theory and Implementation is intended both for newcomers to BDDs and for researchers and practitioners who need to implement them. Apart from giving a quick start for the reader who is not familiar with BDDs (or DDs in general), it also discusses several new aspects of BDDs, e.g. with respect to minimization and implementation of a package. It is an essential bookshelf item for any CAD designer or researcher working with BDDs.

The design process of digital circuits is often carried out in individual steps, like logic synthesis, mapping, and routing. Since originally the complete process was too complex, it has been split up in several - more or less independent - phases. In the last 40 years powerful algorithms have been developed to find optimal solutions for each of these steps. However, the interaction of these different algorithms has not been considered for a long time. This leads to quality loss e.g. in cases where highly optimized netlists fit badly onto the target architecture. Since the resulting circuits are often far from being optimal and insufficient regarding the optimization criteria, like area and delay, several iterations of the complete design process have to be carried out to get high quality results. This is a very time consuming and costly process. For this reason, some years ago the idea of one-pass synthesis came up. There were two main approaches how to guarantee that a design got "first time right": Combining levels that were split before, e.g. to use layout information already during the logic synthesis phase; Restricting the optimization in one level such that it better fits to the next one.So far, several approaches in these two directions have been presented and new techniques are under development. In Towards One-Pass Synthesis we describe the new paradigm that is used in one-pass synthesis and present examples for the two techniques above. Theoretical and practical aspects are discussed and minimization algorithms are given. This will help people working with synthesis tools and circuit design in general (in industry and academia) to keep informed about recent developments and new trends in this area.

Advanced Formal Verification shows the latest developments in the verification domain from the perspectives of the user and the developer. World leading experts describe the underlying methods of today's verification tools and describe various scenarios from industrial practice. In the first part of the book the core techniques of today's formal verification tools, such as SAT and BDDs are addressed. In addition, multipliers, which are known to be difficult, are studied. The second part gives insight in professional tools and the underlying methodology, such as property checking and assertion based verification. Finally, analog components have to be considered to cope with complete system on chip designs.

This book provides an overview of automatic test pattern generation (ATPG) and introduces novel techniques to complement classical ATPG, based on Boolean Satisfiability (SAT).  A fast and highly fault efficient SAT-based ATPG framework is presented which is also able to generate high-quality delay tests such as robust path delay tests, as well as tests with long propagation paths to detect small delay defects. The aim of the techniques and methodologies presented in this book is to improve SAT-based ATPG, in order to make it applicable in industrial practice. Readers will learn to improve the performance and robustness of the overall test generation process, so that the ATPG algorithm reliably will generate test patterns for most targeted faults in acceptable run time to meet the high fault coverage demands of industry. The techniques and improvements presented in this book provide the following advantages: Provides a comprehensive introduction to test generation and Boolean Satisfiability (SAT);Describes a highly fault efficient SAT-based ATPG framework; Introduces circuit-oriented SAT solving techniques, which make use of structural information and are able to accelerate the search process significantly;Provides SAT formulations for the prevalent delay faults models, in addition to the classical stuck-at fault model;Includes an industrial perspective on the state-of-the-art in the testing, along with SAT; two topics typically distinguished from each other.

Evolutionary Algorithms for Embedded System Design describes how Evolutionary Algorithm (EA) concepts can be applied to circuit and system design - an area where time-to-market demands are critical. EAs create an interesting alternative to other approaches since they can be scaled with the problem size and can be easily run on parallel computer systems. This book presents several successful EA techniques and shows how they can be applied at different levels of the design process. Starting on a high-level abstraction, where software components are dominant, several optimization steps are demonstrated, including DSP code optimization and test generation. Throughout the book, EAs are tested on real-world applications and on large problem instances. For each application the main criteria for the successful application in the corresponding domain are discussed. In addition, contributions from leading international researchers provide the reader with a variety of perspectives, including a special focus on the combination of EAs with problem specific heuristics.Evolutionary Algorithms for Embedded System Design is an excellent reference for both practitioners working in the area of circuit and system design and for researchers in the field of evolutionary concepts.

Spectral Techniques in VLSI CAD have become a subject of renewed interest in the design automation community due to the emergence of new and efficient methods for the computation of discrete function spectra. In the past, spectral computations for digital logic were too complex for practical implementation. The use of decision diagrams for spectral computations has greatly reduced this obstacle allowing for the development of new and useful spectral techniques for VLSI synthesis and verification. Several new algorithms for the computation of the Walsh, Reed-Muller, arithmetic and Haar spectra are described. The relation of these computational methods to traditional ones is also provided.Spectral Techniques in VLSI CAD provides a unified formalism of the representation of bit-level and word-level discrete functions in the spectral domain and as decision diagrams. An alternative and unifying interpretation of decision diagram representations is presented since it is shown that many of the different commonly used varieties of decision diagrams are merely graphical representations of various discrete function spectra. Viewing various decision diagrams as being described by specific sets of transformation functions not only illustrates the relationship between graphical and spectral representations of discrete functions, but also gives insight into how various decision diagram types are related.Spectral Techniques in VLSI CAD describes several new applications of spectral techniques in discrete function manipulation including decision diagram minimization, logic function synthesis, technology mapping and equivalence checking. The use of linear transformations in decision diagram size reduction is described and the relationship to the operation known as spectral translation is described. Several methods for synthesizing digital logic circuits based on a subset of spectral coefficients are described. An equivalence checking approach for functional verification is described based upon the use of matching pairs of Haar spectral coefficients.

This book provides an overview of automatic test pattern generation (ATPG) and introduces novel techniques to complement classical ATPG, based on Boolean Satisfiability (SAT).  A fast and highly fault efficient SAT-based ATPG framework is presented which is also able to generate high-quality delay tests such as robust path delay tests, as well as tests with long propagation paths to detect small delay defects. The aim of the techniques and methodologies presented in this book is to improve SAT-based ATPG, in order to make it applicable in industrial practice. Readers will learn to improve the performance and robustness of the overall test generation process, so that the ATPG algorithm reliably will generate test patterns for most targeted faults in acceptable run time to meet the high fault coverage demands of industry. The techniques and improvements presented in this book provide the following advantages: Provides a comprehensive introduction to test generation and Boolean Satisfiability (SAT);Describes a highly fault efficient SAT-based ATPG framework; Introduces circuit-oriented SAT solving techniques, which make use of structural information and are able to accelerate the search process significantly;Provides SAT formulations for the prevalent delay faults models, in addition to the classical stuck-at fault model;Includes an industrial perspective on the state-of-the-art in the testing, along with SAT; two topics typically distinguished from each other.

This book describes reliable and efficient design automation techniques for the design and implementation of an approximate computing system. The authors address the important facets of approximate computing hardware design - from formal verification and error guarantees to synthesis and test of approximation systems.

This book presents exact, that is minimal, solutions to individual steps in the design process for Digital Microfluidic Biochips (DMFBs), as well as a one-pass approach that combines all these  steps in a single process. All of the approaches discussed are based on a formal model that can easily be extended to cope with further design problems.  In addition to the exact methods, heuristic approaches are provided and the complexity classes of various design problems are determined.Presents exact methods to tackle a variety of design problems for Digital Microfluidic Biochips (DMFBs);Describes an holistic, one-pass approach solving different design steps all at once;Based on a formal model of DMFBs that is easily adaptable to deal with further design tasks.

This book describes a comprehensive approach for synthesis and optimization of logic-in-memory computing hardware and architectures using memristive devices, which creates a firm foundation for practical applications.  Readers will get familiar with a new generation of computer architectures that potentially can perform faster, as the necessity for communication between the processor and memory is surpassed.  The discussion includes various synthesis methodologies and optimization algorithms targeting implementation cost metrics including latency and area overhead as well as the reliability issue caused by short memory lifetime.Presents a comprehensive synthesis flow for the emerging field of logic-in-memory computing;Describes automated compilation of programmable logic-in-memory computer architectures;Includes several effective optimization algorithm also applicable to classical logic synthesis;Investigates unbalanced write traffic in logic-in-memory architectures and describes wear leveling approaches to alleviate it.

This book describes a comprehensive approach for synthesis and optimization of logic-in-memory computing hardware and architectures using memristive devices, which creates a firm foundation for practical applications.  Readers will get familiar with a new generation of computer architectures that potentially can perform faster, as the necessity for communication between the processor and memory is surpassed.  The discussion includes various synthesis methodologies and optimization algorithms targeting implementation cost metrics including latency and area overhead as well as the reliability issue caused by short memory lifetime.Presents a comprehensive synthesis flow for the emerging field of logic-in-memory computing;Describes automated compilation of programmable logic-in-memory computer architectures;Includes several effective optimization algorithm also applicable to classical logic synthesis;Investigates unbalanced write traffic in logic-in-memory architectures and describes wear leveling approaches to alleviate it.

This book examines some of the underlying processes behind different forms of information management, including how we store information in our brains, the impact of new technologies such as computers and robots on our efficiency in storing information, and how information is stored in families and in society.The editors brought together experts from a variety of disciplines. While it is generally agreed that information reduces uncertainties and that the ability to store it safely is of vital importance, these authors are open to different meanings of “information”: computer science considers the bit as the information block; neuroscience emphasizes the importance of information as sensory inputs that are processed and transformed in the brain; theories in psychology focus more on individual learning and on the acquisition of knowledge; and finally sociology looks at how interpersonal processes within groups or society itself come to the fore.The book will be of value to researchers and students in the areas of information theory, artificial intelligence, and computational neuroscience.

This book examines some of the underlying processes behind different forms of information management, including how we store information in our brains, the impact of new technologies such as computers and robots on our efficiency in storing information, and how information is stored in families and in society.The editors brought together experts from a variety of disciplines. While it is generally agreed that information reduces uncertainties and that the ability to store it safely is of vital importance, these authors are open to different meanings of “information”: computer science considers the bit as the information block; neuroscience emphasizes the importance of information as sensory inputs that are processed and transformed in the brain; theories in psychology focus more on individual learning and on the acquisition of knowledge; and finally sociology looks at how interpersonal processes within groups or society itself come to the fore.The book will be of value to researchers and students in the areas of information theory, artificial intelligence, and computational neuroscience.

This book describes recent findings in the domain of Boolean logic and Boolean algebra, covering application domains in circuit and system design, but also basic research in mathematics and theoretical computer science.  Content includes invited chapters and a selection of the best papers presented at the 13th annual International Workshop on Boolean Problems.Provides a single-source reference to the state-of-the-art research in the field of logic synthesis and Boolean techniques;Includes a selection of the best papers presented at the 13th annual International Workshop on Boolean Problems;Covers Boolean algebras, Boolean logic, Boolean modeling, Combinatorial Search, Boolean and bitwise arithmetic, Software and tools for the solution of Boolean problems, Applications of Boolean logic and algebras, Applications to real-world problems, Boolean constraint solving, and Extensions of Boolean logic.

This book describes recent findings in the domain of Boolean logic and Boolean algebra, covering application domains in circuit and system design, but also basic research in mathematics and theoretical computer science.  Content includes invited chapters and a selection of the best papers presented at the 13th annual International Workshop on Boolean Problems.Provides a single-source reference to the state-of-the-art research in the field of logic synthesis and Boolean techniques;Includes a selection of the best papers presented at the 13th annual International Workshop on Boolean Problems;Covers Boolean algebras, Boolean logic, Boolean modeling, Combinatorial Search, Boolean and bitwise arithmetic, Software and tools for the solution of Boolean problems, Applications of Boolean logic and algebras, Applications to real-world problems, Boolean constraint solving, and Extensions of Boolean logic.

This book describes a set of SystemC-based virtual prototype analysis methodologies, including design understanding, verification, security validation, and design space exploration. Readers will gain an overview of the latest research results in the field of Electronic Design Automation (EDA) at the Electronic System Level (ESL).

This book describes a set of SystemC-based virtual prototype analysis methodologies, including design understanding, verification, security validation, and design space exploration. Readers will gain an overview of the latest research results in the field of Electronic Design Automation (EDA) at the Electronic System Level (ESL).