European Conference on Operational ResearchStream: Engineering Optimization Session: Applications of OR in Electronic DesignAuthor(s)  Guy A. Narboni  Country  France  Affiliation  Implexe  Title  A Tale of Two Models (about Useful Skew)  Keywords  Scheduling, Constraint Programming, MixedInteger 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 electromagnetic compatibility.
In this talk, we go back to a solution method especially developed for lowemission 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 unitexecutiontime scheduling problem, arguably the simplest
of all the complex resourceconstrained 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 subproblems
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. 
27th EURO Conference www July 2015, Glasgow, UK. 
