Gradual relaxation techniques with applications to behavioral synthesis

Heuristics are widely used for solving computational intractable synthesis problems. However, until now, there has been limited effort to systematically develop heuristics that can be applied to a variety of synthesis tasks. We focus on development of general optimization principles so that they can be applied to a wide range of synthesis problems. In particular, we propose a new way to realize the most constraining principle where at each step we gradually relax the constraints on the most constrained elements of the solution. This basic optimization mechanism is augmented with several new heuristic principles: minimal freedom reduction, negative thinking, calibration, simultaneous step consideration, and probabilistic modeling. We have successfully applied these optimization principles to a number of common behavioral synthesis tasks. Specifically, we demonstrate a systematic way to develop optimization algorithms for maximum independent set, time-constrained scheduling, and soft real-time system scheduling. The effectiveness of the approach and algorithms is validated on extensive real-life benchmarks.