Search

Logic regression aims to find a Boolean model involving binary covariates that predicts the response of an unknown system. It has many important applications, e.g., in data analysis and system design. In the 2019 ICCAD CAD Contest, the challenge of learning a compact circuit representing a black-box input-output pattern generator in a high dimensional Boolean space is formulated as the logic regression problem. This paper presents our winning approach to the problem based on a decision-tree reasoning procedure assisted with a template based preprocessing. Our methods outperformed other contestants in the competition in both prediction accuracy and circuit size. [ABSTRACT FROM AUTHOR]

Asynchronous methodologies are gaining their presence in modern integrated circuit design. Cycle-time analysis of asynchronous design is nontrivial and crucial to circuit optimization. Among prior methods, linear programming-based analysis (LPA) and static performance analysis (SPA) are two representatives with high accuracy (but inefficient) and high efficiency (but inaccurate), respectively. However, the exactness of LPA remains unknown and the accuracy of SPA remains room for improvement. In this work, we demonstrate the inexactness of LPA and enhance the accuracy of SPA. Experimental results suggest our enhanced SPA almost always returns exact cycle-times while achieving up to 4000x speedup over LPA. [ABSTRACT FROM AUTHOR]

Functional timing analysis (FTA) overcomes the limitation of static timing analysis (STA) to allow distinction of false and true paths. Modern FTA methods exploit timed charac- teristic functions (TCFs) to implicitly calculate the longest true delay of a circuit. However, they are inadequate for the verification of timing exceptions, which is crucial for tim- ing signoff, due to their implicit enumeration of all paths rather than specific paths of concern. We present the first TCF-based FTA method for path-specific timing verifica- tion under both floating and transition modes of operation. Experiments demonstrate the unique benefit and scalability of our method. [ABSTRACT FROM AUTHOR]

The increasing cost paid in clocking integrated circuits and combating timing variations forces designers to rethink asynchronous approaches to system realization. Among various techniques, quasi-delay-insensitive (QDI) design is promising due to its very relaxed timing assumption. Its expensive logic overhead, however, often nullifies its promise of performance and power improvements, and remains a major obstacle against its adoption. To overcome this obstacle, this paper proposes an efficient static performance analysis procedure and a synthesis flow for precharged half buffer (PCHB) and weak-conditioned half buffer (WCHB) circuit optimization. Experimental results demonstrate efficient performance analysis and effective area reduction under pipeline cycle time constraints. [ABSTRACT FROM AUTHOR]

EUV flare and CMP metal thickness are two main manufacturability concerns for nanometer process technology. The two dummification objectives, however, are conflicting with each other in nature, but existing works only tackle them separately, leading to problem-prone solutions because optimizing one would deteriorate the other. This paper presents the first work that simultaneously considers both concerns during manufacturability optimization. Given a system's point spread function, our proposed method first finds an initial solution with better-than-state-of the art EUV flare uniformity, then followed by gradient-guided optimization to iteratively refine density uniformity. Experimental results show the effectiveness of our method. [ABSTRACT FROM AUTHOR]

Encoding and decoding are common practice in data processing. Designing encoder and decoder circuitry manually can be error prone and time consuming. Although great progress has been made on automating decoder synthesis from its encoder specification, prior specification was limited to an uninitialized encoder only, whose decoder in turn cannot depend on the entire execution history of the encoder. Prior decoder existence condition is unnecessarily stringent as encoders are often initialized to some specific starting states. This paper shows how decoders of initialized encoders can be practically synthesized. Experimental results demonstrate effective decoder synthesis of initialized encoders, beyond existing methods' capabilities. [ABSTRACT FROM AUTHOR]

Functional, in contrast to structural, timing analysis is accurate, but computationally expensive in refuting false critical paths. Although satisfiability-based analysis using timed characteristic functions has been proposed, its efficiency and generality remain room for improvement. This paper shows functional timing analysis on industrial designs can be made up to several orders of magnitude faster and more generally applicable than prior methods. [ABSTRACT FROM AUTHOR]

Boolean matching determines whether two given (in)completely specified Boolean functions can be identical or complementary to each other under permutation and/or negation of their input variables. Due to its broad applications in logic synthesis and verification, it attracted much attention. Most prior efforts however were incomplete and/or restricted to certain special matching conditions. In contrast, this paper focuses on the computation kernel of Boolean matching and proposes a complete generic framework. Through conflict driven learning and abstraction, the capacity of Boolean matching scales up due to the effective pruning of infeasible matching solutions. Experiments show encouraging results in resolving hard instances that are otherwise unsolvable. [ABSTRACT FROM AUTHOR]

Boolean function bi-decomposition is a fundamental operation in logic synthesis. A function f(X) is bi-decomposable under a variable partition XA,XB,XC on X if it can be written as h(fA(XA,XC), fB(XB,XC)) for some functions h, fA, and fB. The quality of a bi-decomposition is mainly determined by its variable partition. A preferred decomposition is disjoint, i.e. XC = θ, and balanced, i.e. ∣XA∣ ≈ ∣XB∣. Finding such a good decomposition reduces communication and circuit complexity, and yields simple physical design solutions. Prior BDD-based methods may not be scalable to decompose large functions due to the memory explosion problem. Also as decomposability is checked under a fixed variable partition, searching a good or feasible partition may run through costly enumeration that requires separate and independent decomposability checkings. This paper proposes a solution to these difficulties using interpolation and incremental SAT solving. Preliminary experimental results show that the capacity of bi-decomposition can be scaled up substantially to handle large designs. [ABSTRACT FROM AUTHOR]

We propose a static analysis technique for iOS executables for checking API call vulnerabilities that can cause 1) app behaviors to be altered by malicious external inputs, and 2) sensitive user data to be illegally accessed by apps with stealthy private API calls that use string obfuscation. We identify sensitive functions that dynamically load classes/frameworks, and, for each parameter that corresponds to a dynamically loaded class/framework, we construct a dependency graph that shows the set of values that flow to that parameter. A sensitive function that has its class name or framework path parameter depending on external inputs is considered to contain a vulnerability. We further conduct string analysis on these dependency graphs to determine all potential string values that these parameters can take, which identifies the set of dynamically loaded classes/frameworks. Taking the intersection of these values with patterns that characterize Apple's API policies (such as restricted use of private/sensitive APIs), we are able to detect potential policy violations and vulnerabilities. [ABSTRACT FROM AUTHOR]