2017 International Conference On Computer Aided Design

The Premier Conference Devoted to Technical Innovations in Electronic Design Automation

November 13-16, 2017Irvine Marriott Irvine, CA

MP Associates, Inc.
MONDAY November 13, 10:30am - 12:30pm | Newport & Marina
Cross-Layer Efforts for Combating Computationally Hard Problems
Michael Niemier - Univ. of Notre Dame
X. Sharon Hu - Univ. of Notre Dame
Michael Niemier - Univ. of Notre Dame
Computationally hard (i.e., NP-hard) problems are quintessential to many electronic design automation problems, and are also at the heart of many decision, scheduling, error-correction and security applications. Their NP-hard nature makes solving them extremely resource demanding, either in terms of computation time or hardware components or energy. Most of the efforts on improving solvers for such problems aim at developing more effective search algorithms with the understanding that these algorithms would eventually be implemented on modern general-purpose digital computing platforms such as multi-core or many-core processors or application specific digital circuits. However, with Moore’s Law coming to an end, exploring novel computational paradigms (e.g., quantum computing and neuromorphic computing) supported by emerging devices and alternative circuit styles is more imperative than ever. Recently there has been increased interest in cross-layer efforts for designing analog, or mixed-signal solvers for some specific NP-hard optimization problems based on continuous-time dynamical systems. Furthermore, a number of researchers are investigating approaches that exploit intrinsic properties exhibited by certain beyond-CMOS devices to solve NP-hard optimization problems. In this special session, we highlight four cross-layer research efforts targeted at solving NP-hard problems (e.g., satisfiability, graph coloring, etc.) using computational primitives that (i) exploit spatio-temporal dynamics of coupled systems, and (ii) avoid Boolean abstraction in order to achieve high efficiencies with respect to energy and performance. The speakers will present a range of new solver implementations including mixed signal circuits based on conventional transistors, oscillators derived from phase transitions in correlated electron materials, and spin-based devices. While all approaches offer paths toward speedups and/or improvements in energy efficiencies of several orders of magnitude when compared to state-of-the-art approaches, challenges exist that the members of the EDA community are uniquely positioned to address, e.g., managing routing complexity as problem sizes scale, addressing noise tolerance, etc.

1D.1Solving Constraint Satisfaction Problems: From Neural Dynamics to Silicon Chips
 Speaker: Hesham Mostafa - Univ. of California, San Diego
 Authors: Hesham Mostafa - Univ. of California, San Diego
Giacomo Indiveri - University of Zurich
Lorenz K. Muller - ETH Zurich
1D.2An Analog SAT Solver based on a Deterministic Dynamical System
 Speaker: X. Sharon Hu - Univ. of Notre Dame
 Authors: Xunzhao Yin - Univ. of Notre Dame
Zoltan Toroczkai - Univ. of Notre Dame
X. Sharon Hu - Univ. of Notre Dame
1D.3Connecting Spectral Techniques for Graph Coloring and Eigen Properties of Coupled Dynamics: A Pathway for Solving Combinatorial Optimizations
 Speaker: Arijit Raychowdhury - Georgia Institute of Technology
 Authors: Abhinav Parihar - Georgia Institute of Technology
Matthew Jerry - Univ. of Notre Dame
Nikhil Shukla - Univ. of Notre Dame
Suman Datta - Univ. of Notre Dame
Arijit Raychowdhury - Georgia Institute of Technology
1D.4Spin-Device Based Circuits for Computationally Hard Problems
 Speaker: Kerem Y Camsari - Purdue Univ.
 Authors: Kerem Y Camsari - Purdue Univ.
Rafatul Faria - Purdue Univ.
Brian M. Sutton - Purdue Univ.
Supriyo Datta - Purdue Univ.