Minimum maximum econ igu a ion cos p oblem
Raou Senhadji-Na a o
· Ignacio Ga cia-Va gas
Abs ac This pape discusses he p oblem o minimizing he econ igu a ion cos o
some ypes o econ igu able sys ems. A o mal de ini ion o he p oblem and a p oo
o i s NP-comple eness a e p o ided. In addi ion, an In ege Linea P og amming
o mula ion is p oposed. The p oposed p oblem has been used o op imizing a design
s age o Fini e Vi ual S a e Machines.
Keywo ds Combina o ial op imiza ion · Compu a ional complexi y ·
NP-comple eness · G aph · In ege Linea P og amming · Recon igu able compu ing
1 In oduc ion
The concep o econ igu able compu ing goes back o 1960 when Ge ald Es in p o-
posed a compu e made o a s anda d p ocesso and an a ay “ econ igu able”
ha dwa e [3]. Howe e , he lack o adequa e ep og ammable logic chips has delayed
i s de el-opmen o mo e han h ee decades. Nowadays, he inc easing pe o mance
(in e ms o logic densi y, speed and powe consump ion) o he cu en
p og ammable de ices, like Field P og ammable Ga e A ays (FPGAs), has allowed
he de elopmen o a wide ange o econ igu able applica ions.
The con en ional compu ing a chi ec u es based on applica ion speci ic in eg a ed
ci cui s and p og ammable gene al pu pose p ocesso s su e o he lack o
lexibili y o he dedica ed ha dwa e and limi ed pe o mance o he so wa e
solu ions, espec-
i ely. Recon igu able compu ing is a p omising app oach o o e come he adi ional
ade-o be ween lexibili y and pe o mance [5,7].
Howe e , he e a e some challenges ha mus be o e come o de elop e icien
applica ions o econ igu able compu ing sys ems. One o hese challenges is he lack
o o mal models and me hodologies o design au oma ion o dynamically econ ig-
u able sys ems [1,2]. One o he mos c i ical p oblems ha he designe aces is o min-
imize he econ igu a ion cos wi h he goal o achie e an op imal pe o mance [10].
In his pape , we ha e modeled he p oblem o minimizing he econ igu a ion cos
o some ypes o econ igu able sys ems. We p o e ha his p oblem is NP-comple e.
We also p opose an In ege Linea P og amming (ILP) o mula ion o his p oblem.
We ha e used he p oposed p oblem o op imizing a design s age o Fini e Vi ual
S a e Machines (FVSMs) [11].
The emainde o his le e is o ganized as ollows. We p o ide a o mal de ini ion
o he p oposed p oblem in Sec . 2 and i s NP-Comple eness is p o ed in Sec . 3.The
In ege Linea P og amming (ILP) o mula ion is p esen ed in Sec . 4. Expe imen al
esul s o he ILP o mula ion is shown in Sec . 5. Finally, a p ac ical applica ion is
shown in Sec . 6.
2 P oblem s a emen
A econ igu able sys em is composed o a se o econ igu able elemen s (REs) whose
unc ional beha io can be changed in o de o adap he unc ionali y o he sys em
o di e en execu ion con ex s. Le us call unc ionali y he unc ional beha io ha
can be implemen ed in a single RE. Each execu ion con ex can be modeled as a se o
unc ionali ies. The unc ionali ies implemen ed by all REs o he sys em o an execu-
ion con ex is called an ins ance o he econ igu able sys em. Gi en a econ igu able
sys em wi h n REs, he se o ins ances ela ed o he di e en execu ion con ex s is
called n-implemen a ion. The changes o execu ion con ex s can be modeled as an
undi ec ed g aph, called execu ion con ex g aph, whe e e ices ep esen execu ion
con ex s and edges connec execu ion con ex s adjacen in ime.
We de ine an Homogeneous Recon igu able Sys em (HRS) as a econ igu able sys-
em composed by a se o iden ical REs ha e i y he ollowing h ee p ope ies. Fi s ,
all REs can implemen he same unc ionali ies. Second, he beha io o he HRS only
depends on he unc ionali ies o hei REs bu no on he pa icula assignmen o
unc ionali ies o REs. Thi d, hose REs ha a e no equi ed by a pa icula execu ion
con ex can implemen any unc ionali y wi hou a ec ing he beha io o he HRS.
In a HRS, when he execu ion con ex changes, hose REs ha al eady implemen
a unc ionali y equi ed by he new execu ion con ex do no need o be econ igu ed.
So, he econ igu a ion cos is calcula ed as he numbe o REs ha mus be modi ied.
The econ igu a ion cos in he wo s case de e mines he pe o mance o he HRS;
so, he maximum econ igu a ion cos mus be minimized. When an execu ion con ex
equi es less REs han a ailable, he econ igu a ion cos can be educed i he unused
REs a e exploi ed o implemen ing some unc ionali ies o he nex execu ion con ex .
A classical econ igu able compu ing a chi ec u e composed by a gene al-pu pose
p ocesso and a se o iden ical Coa se-G ained Recon igu able P ocessing Elemen s
(CGRPEs) connec ed by a bus is a HRS. The gene al-pu pose p ocesso also ac s as
econ igu a ion con olle [7]. FPGA de ices (o di e en a eas o a same FPGA de ice
when dynamic pa ial econ igu a ion [8] is used) a e classical examples o CGRPE.
Compu e applica ions equi e he econ igu a ion o CGRPEs o accele a ing com-
pu a ionally in ensi e asks. Fo his pu pose, CGRPEs implemen di e en unc ion-
ali ies such as digi al il e banks, loa ing-poin cop ocesso s, c yp og aphic cop oces-
so s, e c. The unc ionali ies equi ed by he applica ion in each pe iod o ime a e he
di e en execu ion con ex s. In each execu ion con ex , he gene al-pu pose p ocesso
econ igu es and uses he needed CGRPEs. The econ igu a ion p ocess equi es o
ans e he econ igu a ion da a o he modi ied CGRPEs. The econ igu a ion la ency
(i.e., he ans e ime o he econ igu a ion da a) di ec ly depends on he numbe o
modi ied CGRPEs. In econ igu able eal- ime applica ions, he educ ion o he econ-
igu a ion la ency is key o imp o e he esponse ime o he sys em. In o de o mee
iming cons ain s, he econ igu a ion la ency in he wo s case mus be minimized.
A HRS is modeled as a 3- uple (F,G,R)whe e Fis a se o unc ionali ies;
G=(V,E), an execu ion con ex g aph; and R={R1,R2,...,R|V|}, a collec ion o
execu ion con ex s whe e Rj⊆F o all Rj∈R. Each e ex j∈V ep esen s he
execu ion con ex Rj.Le S=(F,G,R)be a HRS. Le us de ine an n-implemen a ion
o Sas a collec ion o ins ances I={I1,I2,...,I|V|}whe e Ij⊆Fsuch ha Rj⊆Ij
and |Ij|=n o all Ij∈I. Gi en an n-implemen a ion I, le us de ine he econ igu a-
ion cos be ween wo ins ances Ii,Ij∈Ias δ(Ii,Ij)=n−|Ii∩Ij|. No e ha δ(Ii,Ij)
ep esen s he numbe o unc ionali ies in which Iidi e s om Ij(o Ij om Ii). Le
us de ine he maximum econ igu a ion cos o Ias (I)=max{ i, j}∈Eδ(Ii,Ij).
The Minimum Maximum Recon igu a ion Cos (MMRC) p oblem consis s in inding
an n-implemen a ion Io a HRS wi h a minimum (I).
3 NP-comple eness
In o de o p oo he NP-comple eness o he MMRC p oblem, we o mula e he ela ed
decision p oblem as ollows.
Minimum Maximum Recon igu a ion Cos Decision P oblem (MMR-
CDP)
INSTANCE: Recon igu able sys em S=(F,G,R), posi i e in ege n, posi i e
in ege K≤n.
QUESTION: Is he e an n-implemen a ion o Swi h a maximum econ igu a ion
cos less o equal o K?
I is easy o see ha MMRCDP ∈NP since a nonde e minis ic algo i hm needs
only o guess an n-implemen a ion and check in polynomial ime i i s maximum
econ igu a ion cos is less o equal o K. We p o e ha MMRCDP ∈NP-comple e
by a educ ion om 3SAT [4,9]. The 3SAT can be enuncia ed as ollows.
3- Sa is iabili y (3SAT)
INSTANCE: Collec ion C={c1,c2,... cm}o clauses on a ini e se Uo
boolean a iables such ha |ci|=3 o 1≤i≤m.
QUESTION: Is he e a u h assignmen o U ha sa is ies all clauses in C ?
Gi en an a bi a y ins ance o 3SAT wi h a collec ion C={c1,c2,... cm}o
clauses on a ini e se Uo boolean a iables, we shall cons uc a HRS S=(F,G,R)
such ha he e exis s a 4-implemen a ion o Swi h a maximum econ igu a ion cos
less o equal o K=2 i and only i Cis sa is iable. We cons uc he HRS by
pe o ming he ollowing s eps:
1. Gi en a collec ion o clauses C, le us de ine H(C)as a maximal subse o clauses
o Cwhich e i ies ha no pai o clauses o H(C)a e de ined o e exac ly he
same se o a iables. No e ha he clauses in H(C)can no sha e h ee a iables.
Le us de ine h:C→Z+in such a way ha o any ck∈C,ch(ck)is he clause
o H(C)de ined o e exac ly he same a iables ha ck.
2. Le us de ine he se o unc ionali ies F={X,Y,Z}∪|U|
i=1{Ti,Fi}. The unc-
ionali ies Tiand Fia e called u h unc ionali ies o he a iable uiand ep esen
a u h-se ing o uiwhe e Tiand Fideno e he se ing o ue (T) and alse
(F) alues, espec i ely. The unc ionali ies X,Y, and Zwill be used o impose
es ic ions on he econ igu a ion cos be ween ins ances.
3. Le us cons uc he collec ion o execu ion con ex s Ras ollows:
(a) An execu ion con ex RV
jis c ea ed o each cj∈C. Gi en a clause
cj={l1,l2,l3}∈Cwhe e liis a li e al o e uwi∈U o i=1,2,3, le
us de ine RV
j={X, 1, 2, 3}, whe e
i=Twii li=uwi
Fwii li=¯uwi
(1)
No e ha RV
jcon ains he u h unc ionali ies ha ep esen he u h-se ing
o he a iables o cj ha sa is ies he li e als o cj.
(b) Execu ion con ex s RC1
j,RC2
j, and RC3
ja e c ea ed o each cj∈H(C).Gi en
a clause cj={l1,l2,l3}∈H(C), whe e liis a li e al o e uwi∈U o
i=1,2,3, le us de ine RCk
j={Tw1,Fw1,Tw2,Fw2,Tw3,Fw3} {Twk,Fwk}
o k=1,2,3.
(c) An execu ion con ex RU
j={X}is c ea ed o each cj∈H(C).Inany4-
implemen a ion Io Swi h (I)≤2, he ins ance ela ed o RU
jwill con ain
he u h unc ionali ies ha ep esen a u h-se ing o he a iables o cj ha
sa is ies C.
(d) Execu ion con ex s RU
j,kand RC
j,ka e c ea ed o each {cj,ck}∈H(C)×H(C)
wi h j= ksuch ha cjand cksha e wo a iables. Le upand uqbe he sha ed
a iables. Le us de ine RU
j,k={Y,Z}and RC
j,k={Tp,Fp,Tq,Fq}.Inany4-
implemen a ion Io Swi h (I)≤2, he ins ance ela ed o RU
j,kwill con ain
he u h unc ionali ies ha ep esen a u h-se ing o he sha ed a iables
ha sa is ies C.
4. Le us cons uc he execu ion con ex g aph G=(V,E)as ollows. Fo each
c ea ed execu ion con ex , a e ex ∈Vis c ea ed. The e ices deno ed by VV
j,
VC1
j,VC2
j,VC3
j,VU
j,VU
j,k, and VC
j,k ep esen he execu ion con ex s RV
j,RC1
j,RC2
j,
RC3
j,RU
j,RU
j,k, and RC
j,k, espec i ely. The se o edges Eis c ea ed as ollows:
(a) Edges {VC1
j,VU
j},{VC2
j,VU
j}and {VC3
j,VU
j}a e c ea ed o each cj∈H(C).
In any 4-implemen a ion Io Swi h (I)≤2, hese edges allow o ensu e ha
he ins ance ela ed o RU
jwill con ain a u h unc ionali y o each a iable
o cj.
(b) An edge {VU
j,VU
k}is c ea ed o each {cj,ck}∈H(C)×H(C)wi h j= k
such ha cjand cksha e exac ly one a iable. In any 4-implemen a ion Io
Swi h (I)≤2, his edge allows o ensu e ha he ins ances ela ed o RU
j
and RU
kwill con ain he same u h unc ionali y o he sha ed a iable.
(c) Edges {VU
j,VU
j,k},{VU
j,k,VU
k}, and {VU
j,k,VC
j,k}a e c ea ed o each RU
j,k∈R.
In any 4-implemen a ion Io Swi h (I)≤2, hese edges allow o ensu e
ha he ins ances ela ed o RU
jand RU
kwill con ain he same u h unc ion-
ali ies o he wo sha ed a iables (no e ha RU
j,kis c ea ed only i cjand ck
sha e wo a iables).
(d) Fo each cj∈Cwi h h(cj)=k, an edge {VV
j,VU
k}is c ea ed. In any 4-
implemen a ion Io Swi h (I)≤2, his edge allows o ensu e ha ins ance
ela ed o RU
kwill con ain a leas one u h unc ionali y ha ep esen a u h-
se ing ha sa is ies cj.
Figu e 1shows an example o he p oposed ans o ma ion. Figu e 1ashows he
gi en ins ance o 3SAT; Fig. 1b, he execu ion con ex s (s eps om 1 o 3 desc ibed
abo e); and Fig. 1c, he execu ion con ex g aph (s ep 4).
I is easy o see how he cons uc ion can be accomplished in polynomial ime.
Supposing ha m ep esen s he numbe o clauses o C, he ime complexi y o he
p ocedu e is O(m2)due o he ac ha i only needs o conside he di e en pai s o
clauses o C. All ha emains o be shown is ha Cis sa is iable i and only i he e
exis s a 4-implemen a ion Io Swi h (I)≤2.
Fi s ly, we will p o e ha he e exis s a 4-implemen a ion Io Swi h (I)≤2
i Cis sa is iable. Gi en any sa is ying u h assignmen :U→{T,F}, le us
c ea e he collec ion o ins ances I om Ras ollows. The ins ances deno ed by IV
j,
IC1
j,IC2
j,IC3
j,IU
j,IU
j,k, and IC
j,ka e c ea ed om he execu ion con ex s RV
j,RC1
j,
RC1
j,RC2
j,RC3
j,RU
j,RU
j,k, and RC
j,k, espec i ely. Ini ially, hese ins ances con ain he
same unc ionali ies as he ela ed execu ion con ex s. Le us de ine b:U→Fas
ollows:
b(ui)=Tii (ui)=T
Fio he wise (2)
Le us add {b(up), b(uq), b(us)}⊂F o each IU
j∈Iwhe e up,uq, and usa e he
a iables o cj. Le us add {b(up), b(uq)}⊂F o each IU
j,k∈Iwhe e upand uqa e
he a iables sha ed be ween cjand ck. Fo all Ri∈R, he ela ed ins ance Ii∈I
e i ies ha Ri⊆Iiand |Ii|=4. Thus, Iis a 4-implemen a ion.
We mus p o e ha δ(Ii,Ij)≤2 o each pai o ins ances Ii,Ij∈Isuch ha Ii
and Ija e ela ed o adjacen execu ion con ex s in G. Each edge o Gbelongs o one
o he ollowing ca ego ies:

C={c1,c
2,c
3,c
4};U={u1,u
2,u
3,u
4,u
5,u
6}
c1={u1,u
2,¯u3};c2={¯u1,u
2,u
3};c3={¯u1,¯u2,¯u4};c4={u4,u
5,u
6}
(a)
S ep 1:H(C)={c1,c
3,c
4}
S ep 2:F={X, Y, Z, T1,F
1,T
2,F
2,T
3,F
3,T
4,F
4,T
5,F
5,T
6,F
6}
S ep 3:R=RV
1,R
V
2,R
V
3,R
V
4,R
C1
1,R
C2
1,R
C3
1,R
C1
3,R
C2
3,R
C3
3,R
C1
4,R
C2
4,R
C3
4,R
U
1,R
U
3,R
U
4,R
U
1,3,R
U
1,3
S ep 3a:RV
1={X, T1,T
2,F
3};RV
2={X, F1,T
2,T
3};RV
3={X, F1,F
2,F
4};RV
4={X, T4,T
5,T
6}
S ep 3b:RC1
1={T2,F
2,T
3,F
3};RC2
1={T1,F
1,T
3,F
3};RC3
1={T1,F
1,T
2,F
2}
RC1
3={T2,F
2,T
4,F
4};RC2
3={T1,F
1,T
4,F
4};RC3
3={T1,F
1,T
2,F
2}
RC1
4={T5,F
5,T
6,F
6};RC2
4={T4,F
4,T
6,F
6};RC3
4={T5,F
5,T
6,F
6}
S ep 3c:RU
1={X};RU
3={X};RU
4={X}
S ep 3d:RU
1,3={Y,Z};RC
1,3={T1,F
1,T
2,F
2}
(b)
VU
1
VC3
4
VU
3
VC3
1VU
4
VC3
3
VC2
3
VC2
1
VC2
4
VC1
4
VC1
3
VC1
1
VC
1,3VV
4
VV
1VV
2VV
3
VU
1,3
(c)
(u1)= (u2)= (u5)= (u6)=T
(u3)= (u4)=F
(d)
IU
1={X, T1,T
2,F
3};IU
3={X, T1,T
2,F
4}
IU
4={X, F4,T
5,T
6};IU
1,3={Y, Z, T1,T
2}
(e)
Fig. 1 Example o ans o ma ion om 3SAT o MMRCDP: aclauses, bexecu ion con ex s, cexecu ion
con ex g aph, da sa is ying u h assignmen o C,ande he equi alen 4-implemen a ion (only he
ins ances ha di e o he ela ed execu ion con ex s a e shown)
–{VU
j,VV
j}∈E. By cons uc ion, IV
jcon ains Xand h ee u h unc ionali ies each
one ep esen ing a u h-se ing ha sa is ies a di e en li e al o cj. The ins ance
IU
jcon ains Xand a leas one u h unc ionali y ha ep esen a u h-se ing ha
sa is ies cj.AsCis sa is iable, a leas one o he li e al o cjis sa is iable; so,
|IU
j∩IV
j|≥2 and hus δ(IU
j,IV
j)≤2.
–{VU
j,VCi
j}∈E o i=1,2,3. By cons uc ion, each ICi
jcon ains all possi-
ble u h unc ionali ies o wo a iables o cj. The ins ance IU
jcon ains Xand
he u h unc ionali ies gi en by he unc ion b o he h ee a iables o cj. So,
|IU
j∩ICi
j|=2 and hus δ(IU
j,ICi
j)=2 o i=1,2,3.
–{VU
j,VU
k}∈E. This edge is c ea ed when cjand cksha e a unique a iable. The
ins ances IU
jand IU
konly sha e Xand he u h unc ionali y gi en by he unc ion
b o he sha ed a iable. So, |IU
j∩IU
k|=2, and hus, δ(IU
j,IU
k)=2.
–{VU
j,VU
j,k}∈E. This edge is c ea ed when cjand cksha e exac ly wo a iables.
The ins ances IU
jand IU
j,konly sha e he u h unc ionali ies gi en by he unc ion
b o he sha ed a iables. So, |IU
j∩IU
j,k|=2 and hus, δ(IU
j,IU
j,k)=2.
–{VC
j,k,VU
j,k}∈E. By cons uc ion, IC
j,kcon ains all possible u h unc ionali ies
o he wo sha ed a iables. The ins ance IU
j,kcon ains he u h unc ionali ies
gi en by he unc ion b o he wo sha ed a iables. So, |IC
j,k∩IU
j,k|=2 and hus
δ(IC
j,k,IU
j,k)=2.
We conclude ha (I)=2. Con e sely, we will p o e ha Cis sa is iable i he e
exis s a 4-implemen a ion Io Swi h (I)≤2. P e iously, we p o e some lemmas.
Lemma 1 Le S =(F,G,R)be a HRS ob ained om a 3SAT ins ance and le I
be a 4-implemen a ion o S wi h (I)≤2. Then, o all IU
j∈I, he e do no exis
T ,F ∈Fsuch ha {T ,F }⊂IU
j.
P oo By con adic ion, le us assume ha he e exi T ,F ∈Fsuch ha {T ,F }⊆
IU
j; so, as X∈RU
jand RU
j⊆IU
j,{X,T ,F }⊆IU
j. By cons uc ion, he e
exis RCi
j∈Rsuch ha {X,T ,F }∩RCi
j=∅and |RCi
j|=4. The e o e,
{X,T ,F }∩IC
j=∅and so IU
j∩IC
j⊆IU
j {X,F ,T }. Then |IU
j∩ICi
j|≤
|IU
j {X,F ,T }| = 1 and he e o e δ(IU
j,ICi
j)>2 which implies a con adic ion. 
Lemma 2 Le S =(F,G,R)be a HRS ob ained om a 3SAT ins ance wi h a
collec ion C o clauses on a ini e se U o boolean a iables and le I be a 4-
implemen a ion o S wi h (I)≤2.I c
j∈H(C)is de ined o e u p,uq,us∈U
hen IU
j={X, p, q, s}whe e i∈{Ti,Fi}.
P oo Since (I)≤2, δ(IU
j,ICi
j)≤2 o i=1,2,3; he e o e, |IU
j∩ICi
j|≥2 o
i=1,2,3. By cons uc ion, he e exis s a RCi
j∈Rsuch ha RCi
j={Tp,Fp,T ,F }
whe e =qo =sand so, ICi
j={Tp,Fp,T ,F }. By con adic ion, le us assume
ha {Tp,Fp}∩IU
j=∅;so,IU
j∩ICi
j⊆ICi
j {Tp,Fp}={T ,F }.As|IU
j∩ICi
j|≥2,
{T ,F }⊆IU
jwhich implies a con adic ion by Lemma 1. So, ∈IU
j o all a iables
u ∈cjwhe e ={T ,F }. Since RU
j={X}by cons uc ion, IU
j={X, p, q, s}.

Lemma 3 Le S =(F,G,R)be a HRS ob ained om a 3SAT ins ance and le I be
a 4-implemen a ion o S wi h (I)≤2. Fo each pai IU
j,IU
k∈I wi h j = k, he e
do no exis T ,F ∈Fsuch ha {T ,F }⊂IU
j∪IU
k.
P oo Le cjand ckbe he clauses o a 3SAT ins ance ela ed o IU
jand IU
k, espec-
i ely. The p oo is di ided in o he ollowing cases:
–cjand ckdo no sha e a iables. Le upbe a a iable o cj. By Lemma 1,
{Tp,Fp} ⊂ IU
j.Ascjand ckdo no sha e a iables, ckis no de ined o e up. So,
i is ollows om Lemma 2 ha {Tp,Fp}∩IU
k=∅. So, {Tp,Fp} ⊂ IU
j∪IU
k o
any non-sha ed a iable up.
–cjand cksha e a unique a iable up.Le up,uq, and u be he a iables o cjand le
up,us, and u be he a iables o ckwhe e s= q, and = q, . By con adic ion,
le us assume ha Tp∈IU
jand Fp∈IU
k. By Lemma 2,IU
j={X,Tp, q, s}
and IU
k={X,Fp, , }whe e i∈{Ti,Fi}, hen IU
j∩IU
k={X}. Since
|IU
j∩IU
k|<2, we ha e δ(IU
j,IU
k)>2 which implies a con adic ion because
(I)≤2. So, {Tp,Fp} ⊂ IU
j∪IU
k.
–cjand cksha e wo a iables upand uq. Fi s ly, we p o e ha X/∈IU
j,k.By
cons uc ion, RU
j,k={Y,Z},{X,Y,Z}∩RC
j,k=∅, and |RC
j,k|=4. The e-
o e, {Y,Z}⊂IU
j,kand {X,Y,Z}∩IC
j,k=∅;so,IC
j,k∩IU
j,k⊆IU
j,k {Y,Z}.
Since (I)≤2, we ha e 2 =|IU
j,k {Y,Z}| ≥ |IC
j,k∩IU
j,k|≥2 which implies
IC
j,k∩IU
j,k=IU
j,k {Y,Z}. Then X/∈IU
j,kbecause X/∈IC
j,k.
By Lemma 2,IU
j={X, p, q, }and IU
k={X, 
p, 
q, s}whe e i, 
i∈
{Ti,Fi}and = s.As{Y,Z}∩IU
j=∅,IU
j∩IU
j,k⊆IU
j,k {Y,Z}. Simila ly, as
{Y,Z}∩IU
k=∅,IU
k∩IU
j,k⊆IU
j,k {Y,Z}. Since (I)≤2, |IU
j∩IU
j,k|≥2 and
|IU
j,k∩IU
k|≥2 which implies ha IU
j∩IU
j,k=IU
j,k∩IU
k=IU
j,k {Y,Z}. The e o e,
i X/∈IU
j,k hen IU
j,k {Y,Z}⊂IU
j∩IU
k;so,|IU
j∩IU
k|>|IU
j,k {Y,Z}| = 2 which
implies ha { p, q}={ 
p, 
q}. So, {Tp,Fp} ⊂ IU
j∪IU
kand {Tq,Fq} ⊂ IU
j∪IU
k.
No e ha he case o h ee sha ed a iables is no conside ed because, by cons uc-
ion, RU
j(and so IU
j) is c ea ed only i cj∈H.
The abo e lemmas allow us o de ine a u h assignmen unc ion :U→{T,F}
as ollows:
(uj)=Ti Tj∈IU
k o all IU
k∈Isuch ha uj∈ck
Fi Fj∈IU
k o all IU
k∈Isuch ha uj∈ck
(3)
All ha emains o be shown is ha sa is ies C. By cons uc ion, each u h
unc ionali y o RV
j ep esen s a u h-se ing ha sa is ies cjand, since |RV
j|=4,
IV
j=RV
j. Fo all cj,weha eδ(IU
h(cj),IV
j)≤2, hen we ha e |IU
h(cj)∩IV
j|≥2,
hence he e exis s a leas a p∈{Tp,Fp}⊂Fsuch ha p∈IU
h(cj)∩IV
j. Then
p ∈ I j
V which implies ha he u h alue (u p) sa is ies c j . So, sa is ies C.
I is p o ed ha C is sa is iable i and only i he e exis s a 4-implemen a ion I o S
wi h (I ) ≤ 2. In he example o ans o ma ion, Fig. 1d, and e show a sa is ying u h
assignmen o C and he equi alen 4-implemen a ion I , espec i ely. We conclude
ha MMRC p oblem is NP-comple e.
4 In ege Linea P og amming o mula ion
Le S = (F, G, R) be a HRS whe e F ={ 1, 2,..., p} is a se o unc ionali ies;
G = (V, E), an execu ion con ex g aph; and R ={R1, R2,..., R|V |}, a collec ion o
execu ion con ex s. Le I ={I1, I2,..., I|V |} be a n-implemen a ion o S. We de ine
he se s o bina y a iables xi, j ∈{0, 1} and yi, j,k ∈{0, 1} as ollows:
xi,j=1i i∈Ij,
0 o he wise.i=1,...,p;j=1,...,|V|(4)
yi,j,k=1i i∈Ij∩Ik,
0 o he wise. i=1,...,p;j,k=1,...,|V|(5)
Then, he MMRC p oblem can be o mula ed in he ollowing way:
minimize m(6)
s. . xi,j=1∀i,j| i∈Rj(7)
p

i=1
xi,j=nj=1,...,|V|(8)
2yi,j,k≤xi,j+xi,k≤1+yi,j,ki=1,...,p;j,k=1,...,|V|(9)
m≥n−
p

i=1
yi,j,k∀j,k|{ j,
k}∈E(10)
The cons ain (7) and (8) ensu e ha he Iis a n-implemen a ion o S. The cons ain
(9) ensu es ha he a iable yis consis en wi h he de ini ion (5). The econ igu a ion
cos δ(Ij,Ik)can be calcula ed as n−p
i=1yi,j,k. So, he cons ain (10) ensu es ha
mis an uppe bound o he econ igu a ion cos be ween any pai o ins ances co e-
sponding o adjacen execu ion con ex s. So, he minimum maximum econ igu a ion
cos o Ican be ob ained by minimizing m,asshownin(6).
5 Expe imen al esul s
The p oposed ILP o mula ion has been sol ed using he sol e Gu obi 4.6 [6]. The
expe imen s ha e been execu ed in an In el Xeon X5660 (4 co es) a 2.80 GHz wi h
16 GB o RAM unning Linux 64 bi s (Red Ha En e p ise Linux 6). The es da a
se consis s on 50 andomly gene a ed MMRC ins ances. The expe imen s ha e been
execu ed wi h a ime limi o 7200 s. Table 1summa izes he ob ained esul s. We
e e o he p oblem ins ances sol ed o op imali y as “sol ed ins ances”; on he o he
hand, we e e o he ins ances ha could no be sol ed wi hin he imposed ime limi
as “non-sol ed ins ance”. Fo each p oblem ins ance, he able shows he size o he
n-implemen a ion (n), he numbe o unc ionali ies (|F|), he numbe o edges o he
execu ion con ex g aph (|E|), he numbe o e ices o he execu ion con ex g aph
(|V|), he mean o he ca dinali y o he execu ion con ex s (“C-mean”), he s anda d
de ia ion o he ca dinali y o he execu ion con ex s (“C-s d”), he numbe o he
a e age inal pe cen age op imali y gap (“Gap”), and he amoun o ime in seconds
spen by sol ed ins ances (“Time”). The ows o he able a e so ed in inc easing o de
o |E|. As can be obse ed, he e is a end o inc easing he ime wi h he inc easing
o he numbe o edges. The ILP o mula ion ound an op imal solu ion in he 76 %
o he cases (38 ins ances). The a e age ime o hese cases was 605 s.