Approximate BDD Optimization

Professor
Head of the Group for Computer Architecture
Institute of Computer Science
University of Bremen/DFKI, Bremen, Germany

 

Webpage

Friday, 29 September 2017 at 9:40 in room BC 420

 

Abstract:

Approximate computing refers to a class of problems, which relax the requirements between the specification and its implementation. The practical motivation for approximate computing arises due to the growing number of applications being inherently error resilient, such as media processing, recognition, and data mining. These applications usually don’t require exact results, either due to limitations of human senses, because a golden solution does not exist (such as web search, etc.) or because an approximate solution is good enough. There are different approaches to design approximate circuits. One approach is to make use of voltage over-scaling or over-clocking which induces timing errors. Another approach is to approximate a given function by substituting the function with a similar other function, which is more cost effective in the number of gates or the critical path length. This talk focuses on the latter approach of functional approximation.

Binary Decision Diagrams (BDDs) have become a widely used data structure for the representation of Boolean functions. Among many different areas BDDs have also been studied in logic synthesis, since they allow to combine aspects of circuit synthesis and technology mapping – especially in the field of emerging technologies. Since the BDD representation is canonical, there are no degrees of freedom left to reduce the size of the corresponding BDD, once the function and the variable ordering of the BDD are fixed. But approximation offers a new degree of freedom. In this talk exact and heuristic algorithms are presented how to minimize BDDs while keeping the error as small as possible.

About the speaker.

Rolf Drechsler received the Diploma and Dr. Phil. Nat. degrees in computer science from J.W. Goethe University Frankfurt am Main, Frankfurt am Main, Germany, in 1992 and 1995, respectively. He was with the Institute of Computer Science, Albert-Ludwigs University, Freiburg im Breisgau, Germany, from 1995 to 2000, and with the Corporate Technology Department, Siemens AG, Munich, Germany, from 2000 to 2001. Since October 2001, he has been with the University of Bremen, Bremen, Germany, where he is currently a Full Professor and the Head of the Group for Computer Architecture, Institute of Computer Science. In 2011, he additionally became the Director of the Cyber-Physical Systems group at the German Research Center for Artificial Intelligence (DFKI) in Bremen.

His current research interests include the development and design of data structures and algorithms with a focus on circuit and system design.

Rolf Drechsler was a member of Program Committees of numerous conferences including e.g., DAC, ICCAD, DATE, ASP-DAC, FDL, MEMOCODE, FMCAD, Symposiums Chair ISMVL 1999 and 2014, the Topic Chair for “Formal Verification” DATE 2004, DATE 2005, DAC 2010, as well as DAC 2011, and the Program Chair of FDL 2014. He is a co-founder of the Graduate School of Embedded Systems and he is the coordinator of the Graduate School “System Design” funded within the German Excellence Initiative. He received best paper awards at the Haifa Verification Conference (HVC) in 2006, the Forum on specification & Design Languages (FDL) in 2007 and 2010, the IEEE Symposium on Design and Diagnostics of Electronic Circuits and Systems (DDECS) in 2010 and the IEEE/ACM International Conference on Computer-Aided Design (ICCAD) in 2013. He is a Fellow of the IEEE.