European Conference on Operational ResearchStream: 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. |
 27th EURO Conference www
July 2015, Glasgow, UK. |
|
