European Conference on Operational Research

Stream: Engineering Optimization

Session:  Applications of OR in Electronic Design

Author(s) Guy A. Narboni
Country France
Affiliation Implexe
Title A Tale of Two Models (about Useful Skew)
Keywords Scheduling, Constraint Programming, Mixed-Integer Programming
Abstract In synchronous circuits, an excessive skew in the clock signal driving a register can lead to malfunctions. Indeed, the skew should always lie within a range rigorously determined by timing analysis. Now if a zero skew is a solution, a perfect synchronization is not a panacea. The simultaneous switching of all the memory elements is an important source of noise that causes interferences in radio frequency bands. So some skew can be useful for electro-magnetic compatibility. In this talk, we go back to a solution method especially developed for low-emission circuit design. To the timing constraints we add a shaping constraint which transposes the emission capping requirements to the time domain. This forces a definite spreading of the clock skew distribution. The resulting Constraint Satisfaction Problem can be stated with two global constraints, including a cumulative one. From a theoretical standpoint, it amounts to solving a unit-execution-time scheduling problem, arguably the simplest of all the complex resource-constrained scheduling problems. A more involved transcription can be given as a Integer Programme made up of a tension problem and a network flow one. Separately, both sub-problems are in P, but as shown by Ullman, their conjunction is in NP. From a comparison of these alternative models we here come to the conclusion that a 'fully elastic scheduling problem' and a 'global cardinality constraint' refer to the same specialization of the general cumulative idea.

Technology and Innovation Center, Strathclyde University  27th EURO Conference www
July 2015, Glasgow, UK.