Parallel partitioning techniques for logic minimization using redundancy identification

Redundancy identification is a challenging open problem in logic optimization of Boolean circuits. Partitioning techniques are employed successfully to solve the redundancy identification problem with less time and higher scalability. Any heuristic/algorithm for the Logic optimization problem, and hence the redundancy identification problem is compute-intensive, especially when very high approximation to the optimal solution is demanded. This is because the problems are NP-complete. This necessitates parallel heuristics/algorithms to speed-up the computation process. In this paper, we present a parallel partitioning approach for the logic optimization problem using the concept of redundancy identification. This result finds extensive applications in the area of VLSI CAD tool design.