Gradual Relaxation Techniques with Applications to Behavioral Synthesis

Heuristics are widely used for solving computational intractablesynthesis problems. However, until now, there has been limitedeffort to systematically develop heuristics that can be applied to avariety of synthesis tasks. We focus on development of generaloptimization principles so that they can be applied to a wide rangeof synthesis problems. In particular, we propose a new way torealize the most constraining principle where at each step wegradually relax the constraints on the most constrained elementsof the solution. This basic optimization mechanism is augmentedwith several new heuristic principles: minimal freedom reduction,negative thinking, calibration, simultaneous step consideration,and probabilistic modeling.We have successfully applied these optimization principles to anumber of common behavioral synthesis tasks. Specifically, wedemonstrate a systematic way to develop optimization algorithmsfor maximum independent set, time-constrained scheduling, andsoft real-time system scheduling. The effectiveness of theapproach and algorithms is validated on extensive real-lifebenchmarks.