Approximate algorithms for time separation of events
Supratik Chakraborty, David L. Dill · 1997
We describe a polynomial-time approximate algorithm for computing minimum and maximum time separations between all pairs of events in systems specified by acyclic timing constraint graphs. Even for acyclic graphs, the problem is NP-complete. We propose finding an approximate solution by first approximating the non-convex feasible space with a suitable convex "envelope", and then solving the problem efficiently in the approximate convex space. Unlike previous works, our algorithm can handle both min and max type timing constraints in the same system, and has a computational complexity that is polynomial in the number of events. Although the computed separations are conservative in the worst-case, experiments indicate that our results are highly accurate in practice. 1. Introduction Finding bounds on the time separation between events has emerged as a central problem in analysis of hardware designs. The results of such an analysis can be used for interface timing verification [7]; for d...