AccALS: Accelerating Approximate Logic Synthesis by Selection of Multiple Local Approximate Changes

Approximate computing is an energy-efficient computing paradigm for error-tolerant applications. To automatically synthesize approximate circuits, many iterative approximate logic synthesis (ALS) methods have been proposed. However, most of them do not consider applying multiple local approximate changes (LACs) in a single round, which can lead to a much shorter runtime. In this paper, we propose AccALS, a novel framework for Accelerating iterative ALS flows, based on simultaneous selection of multiple LACs in a single round. When selecting multiple LACs, there may exist conflicts among them. One important component of AccALS is a novel method to solve the conflicts. Another is an efficient measure for the mutual influence between two LACs. With its help, the problem of selecting multiple LACs is transformed into a maximum independent set problem to solve. The experimental results showed that compared to a state-of-the-art method, AccALS accelerates by up to 24.6× with a negligible circuit quality loss.