S a ic Task Mapping o Tiled Chip Mul ip ocesso s wi h
Mul iple Vol age Islands
Niki a Niki in
Uni e si a Poli `
ecnica de Ca alunya
Ba celona, Spain
Jo di Co adella
Uni e si a Poli `
ecnica de Ca alunya
Ba celona, Spain
Abs ac —The complexi y o la ge Chip Mul ip ocesso s (CMP) makes
design euse a p ac ical app oach o educe he manu ac u ing and design
cos o high-pe o mance sys ems. This pape p oposes echniques o
s a ic ask mapping on o gene al-pu pose CMPs wi h mul iple p e-de ined
ol age islands o powe managemen . The CMPs a e assumed o con ain
di e en classes o p ocessing elemen s wi h mul iple ol age/ equency
execu ion modes o be e co e a la ge ange o applica ions. Task
mapping is pe o med wi h awa eness o bo h on-chip and o -chip
memo y a ic, and communica ion cons ain s such as he link and
memo y bandwid h. Besides p oposing a linea p og amming model o
small sys ems, a no el mapping app oach based on Ex emal Op imiza ion
is p oposed o la ge-scale CMPs. This new combina o ial op imiza ion
me hod has deli e ed e y good esul s in quali y and compu a ional cos
when compa ed o he classical simula ed annealing.
I. INTRODUCTION
Chip-mul ip ocessing (CMP) is becoming a majo end o ake
ad an age o Moo e’s law unde he powe consump ion limi a ions
dic a ed by he hea dissipa ion p oblems in high pe o mance com-
pu ing sys ems. Comme cial and p o o ype implemen a ions ha e
shown he pe o mance gains achie ed by CMPs ha ing up o
a hund ed co es [1]–[5]. As we mo e down o deep nanome ic
echnologies, he design complexi y o such sys ems inc eases sig-
ni ican ly. Manu ac u ing cos s and ime- o-ma ke comp omise he
iabili y o new p oduc s ha a e cus omized o speci ic applica ions.
Design euse is a p agma ic solu ion o his p oblem, in bo h CMP
design and deploymen . Fo an e ec i e euse du ing deploymen ,
CMPs a e designed gene al-pu pose, o suppo a a ie y o applica-
ions. Hence, a me hodology o e icien mapping o applica ions
on o CMPs is essen ial. Many app oaches ha e been p oposed
o sol e he mapping p oblem o applica ion-speci ic and mul i-
p ocesso on-chip sys ems (SoCs) [6]. Howe e , he e a e signi ican
di e ences be ween he SoCs and CMPs, ha a e o he g ea
impo ance o he mapping p oblem. To unde s and hese di e ences
we ha e o conside wo aspec s o CMPs: he iled a chi ec u e and
o ganiza ion o powe managemen .
A. Tiled CMP a chi ec u e
To educe he design ime, ile eplica ion was shown o be an
e icien euse me hodology o many-co e CMPs [4], [5]. This led o
he concep o iled a chi ec u e, cha ac e ized by egula s uc u es o
homogeneous iles, each one consis ing o a p ocessing co e, a cache
memo y and a ou e . Fu he esea ch in his a ea inspi ed designs
wi h he e ogeneous iles, p ese ing he egula i y o he s uc u e,
bu in oducing se e al classes o iles [1], [7], [8]. Such sys ems
may include some specialized p ocesso s (e.g., g aphics, DSP) o
di e en implemen a ions o he same a chi ec u e (e.g., in-o de /ou -
o -o de , mul i- h eading) wi h a ied powe -pe o mance ade-o s.
Figu e 1(a) depic s a iled CMP wi h h ee classes o iles: gene al-
pu pose co es (C), co es wi h g aphics uni s (G) and DSPs (D). Each
ile also inco po a es cache memo ies o wo le els (L1, L2) and
CCCC
C G D C
C D G C
CCCC
Co e
L2
L1
R
MC
MC
(a)
8
1 2
6
7
3
9 13
11 12 16
10
5
4
15
14
(b)
Fig. 1: (a) Tiled CMP; (b) ask g aph o be mapped on o CMP.
an on-chip ou e (R), connec ing i o he in e connec ion ab ic.
Two memo y con olle s (MC) a e placed a he pe iphe y o p o ide
communica ion wi h he o -chip memo y.
B. Powe managemen
CMPs a e designed o ope a e unde a ce ain powe budge ha
assu es he pe o mance and he mal p ope ies o he sys em. One
o he mos e ec i e ways o manage powe is o loo plan a ious
ol age islands and assign he bes ol age and equency o each
co e [9].
Un o una ely, ol age islands ha e a high design cos . Fi s ly, he
loo planning o he sys em is cons ained by he design o he powe
deli e y ne wo k and he loca ion o he le el shi e s. Secondly,
and mo e impo an , powe managemen equi es di e en ol age
egula o s o each powe supply. O -chip egula o s need ex a a ea
on he PCB ha may be unaccep able i he sys em has a la ge amoun
o powe domains. On-chip egula o s in ol e a signi ican a ea
o e head and powe consump ion due o he la ge induc ances and
swi ching capaci o s equi ed o p o ide a s able supply ol age [10].
I is he e o e ealis ic o conside ha u u e CMPs will ha e
many co es (hund eds) and ol age islands wi h se e al co es (e.g., 4
o 8). This ac imposes an addi ional cons ain in he ask mapping
p oblem: e en hough some co es could possibly un a lowe ol ages
and equencies, sha ing he island wi h o he co es may p e en o
ake ad an age o his lexibili y. Hence, i is con enien o alloca e
asks in a way ha co es wi hin he same ol age islands can sha e
simila ol age/ equency pa ame e s.
Up o now, he esea ch on powe -awa e mapping has assumed
ha he ol age islands a e de ined p e-silicon du ing ask mapping
in applica ion-speci ic SoCs, o en dis ega ding he cos o imple-
men ing he ol age islands. A b oad o e iew o he ela ed wo k
on SoC applica ion mapping and island planning can be ound in [6].
The app oach in [11] conside s pe o mance cons ain s, bu does
no accoun o he communica ion componen o powe . A mo e
ealis ic app oach is p oposed in [12] in which compu a ion and
communica ion a e bo h op imized aking in o accoun a hi d com-
ponen ela ed o ol age shi e s. The mal-awa e island pa i ioning
ia e olu iona y algo i hms was p oposed in [13]. The dis inc ion o
di e en p ocesso classes was in oduced in [14], bu assuming ha
e e y p ocesso can un a an independen ol age le el.
C. Task mapping o iled CMPs
The mapping p oblem we wan o add ess di e s om p e ious
ones in ha he CMP is assumed o be al eady manu ac u ed.
The e o e, he ol age islands ha e been al eady loo planned and
he maximum bandwid h o he links be ween co es is also known a
p io i. Ano he peculia i y o CMP mapping (as opposed o SoCs),
cap u ed by his wo k, is he p esence o a ic o he o -chip
memo y, as well as he limi ed bandwid h o he memo y con olle s
(MCs). Finally, he me hods p oposed o ask mapping mus be
scalable and sui able o handle sys ems wi h hund eds o co es.
Hence, scalabili y becomes a majo conce n o his wo k.
The wo k in [15] p oposed a amewo k o accu a e compile -le el
mapping o applica ions on o homogeneous mesh CMPs h ough de-
ailed analysis o he ins uc ions and alloca ion o da a. The app oach
p esen ed in his pape di e s by conside ing he a ie y o p ocessing
uni s, o e ed by he e ogeneous CMPs. I also demons a es be e
scalabili y, due o he highe -le el abs ac ion o applica ion wi h a
ask g aph.
The examined p oblem consis s o s a ically mapping a se o
pa allel asks on o a many-co e CMP and selec ing he ol ages o he
CMP islands so ha he o al communica ion and compu a ion powe
is minimized. The applica ion o be mapped is ep esen ed as a g aph
o pa allel asks (Fig. 1(b)) wi h speci ied a e age communica ion
equi emen s be ween he asks, ha is a common assump ion o
mapping on o he on-chip sys ems [6]. The pa i ioning o applica ion
in o pa allel asks can be ob ained by p o iling [15].
E e y ask has an associa ed h oughpu cons ain (ins uc ions
pe second) ha gua an ees he equi ed QoS o ha ask. A a ie y
o p ocesso classes is suppo ed, each one cha ac e ized by a se
o ol age/pe o mance/powe pa ame e s ha can be selec ed o ind
he bes pe o mance/powe ade-o o each ask. Howe e , his
lexibili y is cons ained by an impo an limi a ion: all he co es in
he same island mus wo k wi h he same ol age.
This wo k will also assume ha he co es a e o ganized in a mesh
wi h XY- ou ing [16]. The ask mapping mus sa is y he link and
memo y con olle bandwid h cons ain s de ined a p io i o a oid a
sa u a ion o he communica ion ab ics.
The main con ibu ions o his wo k can be summa ized as ollows:
•Speci ica ion o he p oblem o powe -awa e ask mapping
on o manu ac u ed CMP wi h se e al ile classes, subjec o
h oughpu cons ain s.
•Ma hema ical o mula ion o he p oblem as a mixed-in ege lin-
ea p og amming p oblem (MILP) capable o deli e ing op imal
solu ions o examples o small size.
•Scalable app oach based on Ex emal Op imiza ion (EO) [17],
shown o ou pe o m he op imiza ion by simula ed annealing,
bo h in quali y o esul s and compu a ional cos . The scalabili y
o he me hod is p o ed by examples wi h hund eds o co es.
We would like o emphasize he ac ha Ex emal Op imiza ion
is a combina o ial op imiza ion echnique mos ly unknown in he
EDA communi y. The esul s ob ained o his p oblem ha e been
su p isingly good and e y compe i i e wi h ega d o Simula ed
Annealing. We belie e hese esul s may encou age u he esea ch
in o he a eas ela ed o layou syn hesis. A ela ed wo k, al hough
in a di e en con ex , can be ound in [18].
The s uc u e o he pape is as ollows. Nex sec ion p esen s an
o e iew o he mapping p oblem by conside ing a small example.
Sec ion III p oposes an MILP o mula ion o he p oblem. The
me aheus is ic echniques a e explained in Sec ion IV. Sec ion V
discusses he expe imen al esul s.
1.0
1.0 0.5
1 2
3 4
(a) Task g aph
C2
C1
(b) P ocesso mesh
1 2
3 4
(c) Communica ion-
op imal mapping
V F P
1.0 1.00 0.30
0.8 0.75 0.15
V F P
1.0 0.50 0.10
0.8 0.35 0.05
1 2 3 4
0.7 0.8 0.4 0.3
C1
C2
Th oughpu
(GIPS)
IPC
1, 2 1.0
3, 4 0.8
IPC
1, 2 0.8
3, 4 1.0
(d) P ocesso and h oughpu da a
1 3
2 4
V1
V2
(e) Th oughpu - easible map-
ping
1 4
2 3
V1
V2
( ) Powe -op imal mapping
Fig. 2: Task mapping example.
II. PROBLEM OVERVIEW
This sec ion discusses he ask mapping p oblem using a small
example. Le us assume a ask g aph wi h ou asks (Fig. 2(a)). The e
a e h ee lows be ween he asks, wi h he bandwid hs speci ied in
he a cs o he g aph (in Gbps). Figu e 2(b) depic s a CMP wi h ou
p ocesso s. The e a e wo classes o p ocesso s: C1(ligh ) and C2
(da k). The ask g aph mus be mapped on o he CMP.
1) Communica ion-op imal mapping: Figu e 2(c) shows a ask
mapping ha op imizes he communica ion me ic, ha is he p oduc
o bandwid h and hop-coun . Assuming he dis ance be ween he
neighbo ing p ocesso s is one hop, he communica ion cos o his
mapping is
CCos 1= 1.0·1 + 1.0·1 + 0.5·2 = 3.0 (Gbps).
2) Th oughpu - easible mapping: Now le us ake in o accoun
he p ocesso pa ame e s and conside he h oughpu equi emen s
o he asks. Figu e 2(d) desc ibes he p ocesso pa ame e s. They can
ope a e a wo ol ages, 1.0and 0.8V. The co esponding equency
(F, in GHz) and powe (P, in W) o each ol age is shown in he
ables. Due o he na u e o he asks and he implemen a ion o each
p ocesso , each ask may be execu ed wi h a di e en pe o mance
(Ins uc ions Pe Cycle (IPC)) in each class o p ocesso s. Finally,
each ask may equi e a speci ic h oughpu (gi en in giga-IPS in
Fig. 2(d)).
The mapping in Fig. 2(c) is in easible wi h in oduc ion o he
h oughpu cons ain s. Conside ask 2assigned o a C2-p ocesso .
The maximum pe o mance ha C2can p o ide o 2is IPC( 2)·
F(1.0V) = 0.8·0.5 = 0.4GIPS, while he h oughpu equi emen
o 2is 0.8GIPS.
To sa is y he equi emen s, asks 2and 3a e swapped (see
Fig. 2(e)). This mapping sa is ies he h oughpu cons ain s and s ill
keeps he op imal alue o he communica ion me ics.
3) Powe -op imal mapping: As a inal s ep, le us conside he
pa i ioning o he CMP in o ol age islands. Le us assume he
CMP has wo islands, sepa a ed by he bold do ed line, as shown
in Fig. 2(e). P ocesso s in he same island mus ope a e a he same
ol age le el, ha is he minimal ol age equi ed o sa is y all he
h oughpu cons ain s o he asks mapped o his island.
Fo he mapping in Fig. 2(e), he uppe island has o ope a e a
1.0Vdic a ed by he h oughpu cons ain o 3. The lowe island
also has o un a 1.0V, because o 2. Thus, he compu a ion powe ,
calcula ed using he da a om Fig. 2(d), is Pcomp = 0.30 + 0.10 +
0.30 + 0.10 = 0.80 W. Le he ene gy o ans e one bi o one
hop be Ebi = 0.1nJ/bi . Then he communica ion powe is
Pcomm =CCos 2·Ebi = 3.0Gbps ·0.1nJ/bi = 0.3W,
and he o al powe P=Pcomp +Pcomm = 1.10 W.
No ice ha i we swap asks 3and 4(Fig. 2( )), he uppe
island can lowe he ol age o 0.8Vwi hou iola ing he h oughpu
cons ain s. The new compu a ion powe is Pcomp = 0.15 + 0.05 +
0.30 + 0.10 = 0.60 W. The communica ion cos is inc eased:
CCos 3= 1.0·1+1.0·2+0.5·1 = 3.5 (Gbps ·hop), so he
communica ion powe becomes Pcomm =CCos 3·Ebi = 3.5·0.1 =
0.35 W. Howe e , he o al powe P= 0.95 Wdec eases, making
he assignmen in Fig. 2( ) he bes one in e ms o o al powe .
The p e ious example demons a es he impo ance o he ask
mapping p oblem when ying o minimize powe consump ion in a
CMP wi h mul iple classes o p ocesso s and ol age islands. The
nex sec ion shows how op imal solu ions o small ins ances o he
p oblem can be ound based on an MILP o mula ion.
III. A MATHEMATICAL MODEL
This sec ion gi es a o mal de ini ion o he p oblem ia a Mixed-
In ege Linea P og amming model. This model will be la e used
as he basis o a heu is ic me hod o la ge-scale sys ems based on
Ex emal Op imiza ion.
A. Pa ame e s o he p oblem
The pa ame e s o he p oblem a e summa ized in Table I. The
a iables o he MILP o mula ion a e ou lined in Table II.
A ask g aph TG(T,F)is a di ec ed g aph wi h e ices ep-
esen ing he asks i∈ T . Each a c ep esen s a low sd ∈ F
ha de ines he communica ion om ask s o d. E e y low has
a minimum equi ed bandwid h Bsd. E e y ask ihas a h oughpu
cons ain IPS( i), ha is he minimum numbe o ins uc ions pe
second equi ed o p o ide he se ice deli e ed by he ask. Λ( i)
de ines he o al a ic a e be ween iand he memo y con olle .
The a io be ween he a ic o and om he con olle is speci ied by
he pa ame e ρ. No e ha Λ( i) alue can be app oxima ed, gi en
he amoun o da a, ope a ed by he ask (i.e. he wo king se ), and
he size and miss- a io o he ile cache.
A CMP is ep esen ed by a mesh o p ocesso s PM(P,L)wi h
dimensions o W·Hcells, whe e Pis he se o p ocesso s and L
is he se o communica ion links. Links a e o ganized in o an on-
chip ne wo k wi h egula mesh opology [19]. The communica ion
capaci y be ween he neighbo ing cells is de e mined by he global
pa ame e Cap (all links a e assumed o ha e he same capaci y).
E e y cell ep esen s a p ocesso pj, belonging o one o he p ocesso
classes in C={c1, .., cC}. Di e en classes o p ocesso s ha e
dis inc pe o mance execu ing each ask. The pe o mance o pj o
execu e ask i, measu ed in ins uc ions pe cycle, is speci ied by
he unc ion IPC( i, pj).
Task pa ame e s
TG Task g aph wi h asks iand lows sd
Bsd Bandwid h equi emen o low sd
IPS( i)Th oughpu equi emen o ask i(ins ./sec.)
Λ( i)T a ic o ask i o he memo y con olle
ρRa io o a ic a es o and om con olle
P ocesso g id pa ame e s
PM(P,L)Mesh o p ocesso s (P) wi h communica ion links (L)
Cap Maximum capaci y o he communica ion links
IPC( i, pj)Pe o mance o pjexecu ing i(ins ./cycle)
VSe o a ailable ope a ing ol ages k
F(pj, k)F equency o p ocesso pja ol age k
P(pj, k)Powe o p ocesso pja ol age k
MC(pj)Memo y con olle associa ed wi h pj
McDis (pj)Dis ance om pj o associa ed con olle
McBw Maximum bandwid h o memo y con olle s
Vol age island pa ame e s
{ιn}Se o ol age islands
IMap om p ocesso s o ol age islands
TABLE I: Inpu pa ame e s o he p oblem.
Va iable Type Desc ip ion
aijk ask iis assigned o p ocesso pjwi h ol age k
n
kBina y ol age island ιnope a es a ol age k
l
sd link lbelongs o he ou e o low sd
ml
sd Real mapping indica o o he e minals o sd
hx
sd, hy
sd hop-coun (xand y) o ou e sd
TABLE II: Va iables o he MILP o mula ion.
The p ocesso s may ope a e a di e en ol ages. We assume a
se o ol ages V={ 1, .., V}a ailable o all p ocesso s. The
equency and powe o pjope a ing a ol age ka e de ined by he
unc ions F(pj, k)and P(pj, k), espec i ely. E e y pjbelongs o
some ol age island ιn, as de ined by he island map I. The ol age o
an island can be adjus ed independen ly o he o he islands, howe e ,
all p ocesso s in an island mus ope a e a he same ol age.
A CMP has a se o con olle s o access he o -chip memo y.
Guided by he exis ing implemen a ions [4], [5], in his wo k we
assume con olle placemen a he pe iphe y o p ocesso mesh.
Howe e , his does no limi he p oposed app oach om ha ing he
con olle s placed inside he mesh, ha was demons a ed bene icial
by he ecen esea ch [20]. Ano he assump ion we make is ha
e e y p ocesso pjis associa ed wi h one con olle , as de ined
by he unc ion MC(pj). This assump ion can be elimina ed by
speci ying he p obabili ies o accessing di e en con olle s o pj.
Func ion McDis (pj) e u ns he hop-coun dis ance om pj o he
ela ed con olle . The McBw pa ame e se s he maximum con olle
bandwid h o gua an ee pe o mance o memo y access.
B. Cos unc ion
The goal o he model is o minimize powe consump ion unde a
se o design and pe o mance cons ain s.
The bina y a iables aijk de ine whe he ask iis mapped on o
p ocesso pjope a ing a ol age k. The o al powe consump ion
o compu a ion can be de ined as ollows:
Pcomp =X
i∈T X
pj∈PX
k∈V
aijk ·P(pj, k).
The powe consump ion o communica ion has wo e ms: he on-
chip communica ion, de ined by he lows be ween he asks and
he o -chip communica ion, de ined by he a ic o he memo y
con olle s. To model he i s e m, we in oduce he a iables
hx
sd and hy
sd ha ep esen he hop-coun o low sd in he x-
and y-di ec ions, espec i ely. The powe consump ion o in e - ask
communica ion can be de ined as
P
comm =X
sd∈F
Bsd ·(hx
sd +hy
sd)·Ebi ,
and he e m ela ed o communica ion wi h memo y con olle s
Pmc
comm =X
i∈T X
pj∈PX
k∈V
aijk ·Λ( i)·McDis (pj)·Ebi .
whe e Ebi is he es ima ed ene gy o ansmi ing one bi o e a
link. The objec i e o he p oblem is o minimize he o al powe :
min :P=Pcomp +Pcomm =Pcomp +P
comm +Pmc
comm.(1)
C. Cons ain s
The i s wo cons ain s a e he classical equi emen s o an
assignmen p oblem. E e y ask ihas o be assigned o some
p ocesso pjand e e y p ocesso can hold one ask a mos :
∀ i∈ T :X
pj∈PX
k∈V
aijk = 1.(2)
∀pj∈P:X
i∈T X
k∈V
aijk ≤1.(3)
The nex s ep is o model he communica ion componen o he powe .
A se o cons ain s is in oduced o calcula e he hop-coun o each
low assuming an XY- ou ing. Each p ocesso pjis loca ed in a ile
a column xjand ow yjo he mesh (Fig. 3a). The coo dina es a e
uniquely de ined by he index j:xj=jmod Wand yj=bj/W c,
whe e Wis he wid h o he mesh. Fo any ask i, we de ine (xi, yi)
as he loca ion o he p ocesso assigned o he ask. Then, he loca ion
is speci ied by he exp essions o e he ask assignmen a iables:
xi=X
pj∈P
(jmod W)X
k∈V
aijk
yi=X
pj∈P
(bj/W c)X
k∈V
aijk.(4)
Fo e e y low sd, he sou ce and des ina ion asks, sand d,
a e mapped on o p ocesso s psand pd, wi h coo dina es (xs, ys)
and (xd, yd), espec i ely, de ined by (4). The ho izon al hop-coun ,
hx
sd =|xs−xd|, and he e ical hop-coun , hy
sd =|ys−yd|a e
de ined by he ollowing cons ain s1:
xs−xd≤hx
sd, xd−xs≤hx
sd
ys−yd≤hy
sd, yd−ys≤hy
sd.(5)
The nex g oup o cons ain s de ines he ela ions be ween ol age
islands and h oughpu . Le he bina y a iable n
k ep esen he ac
ha he ol age island ιnope a es a ol age k. Fi s , o e e y island
ιnonly one ol age has o be selec ed:
∀ιn∈ I :X
k∈V
n
k= 1.(6)
To en o ce ha all p ocesso s in he same ol age island wo k wi h
he same ol age, he ollowing cons ain is added:
∀ιn∈ I,∀ k∈ V :X
i∈T X
pj∈ιn
aijk ≤Num(aijk)· n
k,(7)
1 he pai o inequali ies and he ac ha he h a iables a e implici ly
minimized wi h he cos unc ion (since his implies minimiza ion o powe ),
gua an ee he equali y wi h he absolu e alue.
xj
yj
0 1 2 3
0
3
2
1pj
EAST MC
WEST MC
(a) P ocesso pjloca ed in he
cell (xj, yj)o he mesh.
xlb xle
yl
0 1 2 3
0
3
2
1
EAST MC
WEST MC
(b) Eas link om cell
(xlb, yl) o cell (xle, yl).
Fig. 3: De ini ion o he p ocesso and link loca ion in mesh.
whe e Num(aijk)is he numbe o aijk a iables in he LHS o he
inequali y. Exp ession (7) in combina ion wi h (6) gua an ees ha
only he assignmen a iables o he selec ed ol age may ake non-
ze o alues.
The h oughpu cons ain should gua an ee ha o each ask i
execu ed on p ocesso pj he p oduc o IPC( i, pj)and he p ocesso
equency F(pj, k)de ined by he cu en ol age, is no less han
he equi ed h oughpu IPS( i). Hence, he ollowing ela ion is
speci ied o each i∈ T :
X
pj∈PX
k∈V
aijk ·IPC( i, pj)·F(pj, k)≥IPS( i).(8)
The las g oup o cons ain s aims a sa is ying he equi emen s o
link capaci y and memo y con olle bandwid h, unde he assump ion
o XY- ou ing. We s a by conside ing he link capaci y. The o al
link bandwid h can be exp essed as he sum o he bandwid hs o all
lows ha pass h ough he link. The e a e wo e ms ha con ibu e
o link bandwid h, ela ed o he in e - ask and memo y con olle
a ic, hence he cons ain can be w i en as
∀l∈ L :TaskTe m(l) + McTe m(l)≤Cap.(9)
Le us conside he ask e m i s . In XY- ou ing, he da a is
always sen in he X-di ec ion i s and he Y-di ec ion a e wa d.
Hence, he ou e o a low will pass h ough a link, only in case
he sou ce and des ina ion asks a e mapped o a speci ic subse
o p ocesso loca ions. Thus, o e e y link land low sd we
de ine he bina y p ope ies, MapS c(l, sd)and MapDs (l, sd),
ha indica e whe he he sou ce and des ina ion asks a e mapped
on o he loca ions ha imply link l o be on he low ou e.
To gua an ee ha lis on he ou e o sd, bo h p ope ies should be
asse ed, i.e., MapS c(l, sd)·MapDs (l, sd) = 1. This is a non-
linea cons ain ha we linea ize by in oducing he eal a iables
ml
sd:
MapS c(l, sd) + MapDs (l, sd) = ml
sd.(10)
Since he mapping p ope ies can only ake bina y alues, he ml
sd
a iable can only ake h ee alues: 0, 1, o 2. We use ano he scaling
o ml
sd o he bina y a iables l
sd, ha ake non-ze o alues only
when ml
sd = 2, i.e. bo h mapping p ope ies a e ue:
l
sd ≥ml
sd −1,2· l
sd ≤ml
sd.(11)
The a iables l
sd a e equal o 1 i he ou e o low sd goes
h ough link l. Now he ask e m o link lis w i en as:
TaskTe m(l) = X
sd∈F
Bsd · l
sd.(12)
Nex we explain how o ep esen he mapping p ope ies
MapS c(l, sd)and MapDs (l, sd). Conside he ho izon al eas
link o a cell wi h coo dina es (xlb, yl) o a cell (xle, yl)(Fig. 3b).
The XY- ou e o low sd can only pass h ough he link in case
he sou ce ask sis mapped on o one o he wo do ed p ocesso
cells. Indeed, he p ocesso psshould be loca ed on he same ow
and in a column ha is lowe han o equal o he o igin o he link:
(xs≤xlb)∧(ys=yl). Hence, he sou ce mapping p ope y o an
eas link is:
MapS c(l, sd) = X
pj:(xj≤xlb)∧(yj=yl)X
k∈V
asjk.(13)
Fo he des ina ion ask d he equi emen is o be loca ed in a
column ha is g ea e han o equal o he link endpoin xle (s iped
cells). The des ina ion mapping p ope y becomes:
MapDs (l, sd) = X
pj:(xj≥xle)X
k∈V
adjk.(14)
The mapping p ope ies o sou h, wes and no h links a e de i ed
in a simila manne .
Now conside he e m ela ed o he memo y con olle a ic.
Fo link lle us deno e Req(l) he se o p ocesso s ha send
eques s o hei con olle s h ough link l. Simila ly, Rep(l)is he se
o p ocesso s ha ecei e eplies om con olle h ough l. Hence,
a ic o and om con olle s h ough lis de ined by he a e o asks
mapped o he se s Req(l)and Rep(l):
McTe m(l) = X
i∈T X
pj∈Req(l)X
k∈V
aijk ·ρ·Λ( i)+
X
i∈T X
pj∈Rep(l)X
k∈V
aijk ·(1 −ρ)·Λ( i).(15)
The se s Req(l)and Rep(l)can be exp essed simila ly o he
MapS c and MapDs p ope ies o links. As an example, le us
conside he same eas link (Fig. 3b). Assuming XY- ou ing, pjsends
eques s in he di ec ion o he associa ed con olle . Hence, he se
o p ocesso s sending eques s h ough he link is limi ed by hose,
associa ed wi h he EAST con olle and loca ed on he same ow in
he column ha is lowe o equal o he link o igin:
Req(l) = {pj: (MC(pj) = EAST)∧(xj≤xlb)∧(yj=yl)}.
The se s o o he links a e de i ed simila ly. The inequali ies (9)
oge he wi h he scaling ela ions (10), (11) and de ini ions (12)-(15)
gua an ee ha he link capaci y cons ain s a e me .
The las s ep is o speci y he bandwid h cons ain s o he memo y
con olle s. The bandwid h o con olle mcκ∈MC is de ined by he
a es o asks mapped on o p ocesso s, associa ed wi h mcκ:
∀mcκ∈MC :X
i∈T X
pj:MC(pj)=κX
k∈V
aijk ·Λ( i)≤McBw.(16)
D. P oblem o mula ion
The p oblem can now be o mula ed as ollows.
Minimize:powe consump ion (1)
subjec o:
assignmen cons ain s and hop-coun de ini ion (2)-(5),
ol age selec ion cons ain s (6), (7),
h oughpu cons ain s (8),
link capaci y cons ain s (9)-(15)
and memo y bandwid h cons ain s (16).
IV. SIMULATED ANNEALING AND EXTREMAL OPTIMIZATION
This sec ion discusses wo me aheu is ics commonly used o sol e
complex combina o ial p oblems: Simula ed Annealing (SA) [21]
and Ex emal Op imiza ion (EO) [17]. Bo h me hods a e inspi ed by
equilib ium s a is ical physics. SA has been success ully applied in
many EDA p oblems, mos ly ela ed o layou syn hesis. Howe e ,
EO has eme ged as a e y compe i i e al e na i e ha can gi e
supe io esul s in quali y and compu a ional cos . This sec ion shows
how EO can be cus omized o e ec i ely sol e he ask mapping
p oblem. The esul s p o e he supe io i y wi h ega d o SA.
Bo h me aheu is ics s a om an ini ial mapping ob ained by
g eedily placing he asks wi h highes h oughpu o he as es
p ocesso s. I is assumed ha he sys em is no highly h oughpu -
cons ained and ha a easible ini ial assignmen can be achie ed by
a g eedy heu is ic. The bandwid h cons ain s may be iola ed in he
ini ial mapping and will be handled du ing he op imiza ion p ocess.
A. Simula ed annealing
The gene al algo i hm o SA is desc ibed in p ocedu e 1. To
e alua e e e y con igu a ion, wo unc ions a e used. Cos () e u ns
he cos o a con igu a ion, calcula ed as he o al sys em powe
acco ding o equa ion (1). CapP() calcula es he penal y o link
capaci y and memo y bandwid h iola ions:
CapP =X
l∈L
max Bl−Cap
Cap ,0+X
mc∈MC
max Bmc −McBw
McBw ,0,
whe e Blis he o al bandwid h o lows ou ed h ough link land
Bmc is he bandwid h o con olle mc. I all cons ain s a e sa is ied,
hen CapP = 0.
The SA algo i hm implemen s a con en ional annealing schedule.
Gi en he ini ial empe a u e Tini and he cooling ac o α, a
new solu ion (NewSol) is gene a ed (line 4) and may be accep ed
p obabilis ically, depending on he cu en empe a u e Tcu (line 5).
The alue o Tcu dec eases as he sys em e ol es in ime (line 8).
Fo e e y empe a u e, a numbe o mo es ha depends on he size
o he sys em (P, ha is he numbe o cells) is gene a ed.
NewSol is ob ained by swapping a pai o andom asks and
is accep ed p obabilis ically acco ding o P ocedu e 2. To penalize
capaci y iola ions, he cos is calcula ed as shown in lines 1-2, whe e
λ=Tini /Tcu is he weigh o penaliza ion, ha g ows in ime.
This dec eases he p obabili y o accep in easible solu ions as he
simula ion ad ances.
Solu ions wi h be e cos a e always accep ed (line 3), whe eas
wo se-cos solu ions a e accep ed wi h p obabili y Pa:
Pa=1−|∆Cos |
Cu Cos ·e−2·Tini
Tcu ,
wi h ∆Cos =NewCos −Cu Cos . This p obabili y depends on wo
ac o s. The o me a oids he accep ance o solu ions wi h high cos
deg ada ion. The la e educes he p obabili y o hill climbing as he
empe a u e cools down.
B. Ex emal op imiza ion
Ex emal op imiza ion, inspi ed by he p inciple o e olu ion in
ecosys ems, is me aheu is ic o complex combina o ial p oblems.
Ecosys ems we e obse ed o e ol e by selec ing agains i s wo s
componen s.
Fo e e y possible solu ion, EO e alua es he i ness o each
componen in he sys em. A high i ness alue indica es ha he
componen has a com o able low-cos s a us in he sys em.

P ocedu e 1 SIMULATEDANNEALING
1: Tcu =Tini
2: while imp o emen in las ki e a ions do
3: o P i e a ions do
4: gene a e NewSol
5: i ACCEPT(Cu Sol,NewSol) hen Cu Sol←NewSol
6: i Cos (NewSol)<Cos (Bes Sol) hen Bes Sol←NewSol
7: end o
8: Tcu =α·Tcu
9: end while
10: e u n Bes Sol
P ocedu e 2 ACCEPT(Cu Sol,NewSol)
1: Cu Cos ←Cos (Cu Sol) + λCapP(Cu Sol)
2: NewCos ←Cos (NewSol) + λCapP(NewSol)
3: i NewCos <Cu Cos hen e u n ue
4: else e u n ue wi h p obabili y Pa
EO ocuses on imp o ing he s a us o componen s wi h low
i ness. A each i e a ion, some o he wo s - i componen s a e
eplaced by o he componen s ha con ibu e o imp o e hei i ness.
Local op ima a e a oided by andomizing he selec ion p ocess.
The componen s a e anked acco ding o hei i ness in ascending
o de ( he wo s componen s ha e lowe indices in he ank). The
componen s a e andomly selec ed by some p obabili y dis ibu ion
biased owa ds he ones wi h lowes i ness alues. The powe -law
dis ibu ion is a ypical one o EO. Fo example, i he sys em has N
componen s anked om 1 o Nin ascending o de o hei i ness,
he index io he selec ed componen can be calcula ed as ollows:
i=dN·pτe(17)
whe e pis a andom numbe ob ained om a uni o m dis ibu ion
in he in e al [0,1] and τis he exponen o he powe law. In ou
expe imen s, we used alues o τin he in e al [3,4].
Fo he ask mapping p oblem, a each i e a ion EO selec s a pai o
asks o be swapped: an un a o able ask ( u) and a eplacemen ask
( ). Unlike SA, EO uses in o ma ion abou he sys em cos when
selec ing he swapped asks. This esul s in o a as e p og ess owa ds
he inal solu ion. In addi ion, EO accep s new solu ions uncondi ion-
ally wi hou depending on any empe a u e cooling schedule, hus
making he algo i hm easie o une.
The mapping p oblem is a mul iobjec i e op imiza ion p oblem,
since he Pcomp,P
comm and Pmc
comm e ms o he cos unc ion (1)
depend on weakly ela ed ol age le el and hop-coun alues. I
was obse ed in [18] (and p o ed by ou expe imen s) ha he
mul iobjec i e EO ope a es be e by in e lea ing he op imiza ion o
indi idual objec i es in ime, a he han ying o op imize all o hem
simul aneously. This sugges s o in oduce di e en i ness unc ions
o he op imiza ion o h ee powe componen s and al e na e hem
a di e en i e a ions o he algo i hm.
The EO algo i hm is ou lined in p ocedu e 3. A e he de ini ion
o an ini ial solu ion (g eedily), he execu ion is con inued un il no
u he imp o emen is obse ed du ing a ce ain numbe o i e a ions.
The algo i hm used in his wo k is a a ia ion o EO called
Con inuous Ex emal Op imiza ion [22]. This a ian combines EO
wi h a local sea ch a he beginning o each i e a ion, ha is pe o med
by sequen ially swapping P andom pai s o asks and accep ing only
hose ha imp o e he cos . This a ian con ibu ed o imp o e he
cos o he inal solu ion and he speed o he algo i hm.
P ocedu e 3 EXTREMALOPTIMIZATION
1: Cu Sol←Bes Sol←”Some ini ial solu ion”
2: while some imp o emen in he las ki e a ions do
3: Local sea ch: swap P andomly selec ed pai s sequen ially and
4: accep only hose ha imp o e he cos o Cu Sol
5: i (i e mod 3) = 1 hen /* imp o e ask comm. cos */
6: so all asks in ascending o de o Φcomm
u,
7: selec uacco ding o equa ion (17)
8: so all asks i6= uin ascending o de o Φcomm
9: selec acco ding o equa ion (17)
10: else i (i e mod 3) = 2 hen /* imp o e mc comm. cos */
11: so all asks in ascending o de o Φcomm
u,mc
12: selec uacco ding o equa ion (17)
13: so all asks i6= uin ascending o de o Φcomm
14: selec acco ding o equa ion (17)
15: else /* imp o e comp. cos */
16: so all asks in ascending o de o Φcomp
u
17: selec uacco ding o equa ion (17)
18: so all asks i6= uin ascending o de o Φcomp
19: selec acco ding o equa ion (17)
20: swap asks uand in Cu Sol
21: i Cos (Cu Sol)<Cos (Bes Sol) hen
22: Bes Sol←Cu Sol
23: end while
24: e u n Bes Sol
The co e o he algo i hm ocuses on selec ing he pai o asks ha
mus be swapped. The i ness unc ions al e na e depending on he
i e a ion numbe . In one case, i ness is o ien ed o imp o e he powe
consump ion gene a ed by in e - ask communica ion, conside ing he
hop-coun s and bandwid h pa ame e s. In he second case, he powe
o communica ion wi h memo y con olle s is op imized. The las
case add esses he powe gene a ed by compu a ions.
The i s ask, u, is selec ed by using he Φu i ness unc ion and
so ing he asks acco ding o he i ness alue. The second ask, , is
selec ed by anking he ask acco ding o he imp o emen in cos ha
he swap would p oduce (Φ unc ions). The powe law desc ibed by
equa ion (17) is used o selec he asks andomly.
Finally he loca ions o asks o uand a e swapped uncondi-
ionally and Bes Sol is upda ed i he cos is be e han any o he
solu ion isi ed so a .
C. Fi ness unc ions
To model he i ness o he powe consump ion gene a ed by he
in e - ask a ic on he mesh, Φcomm
u, anks he asks acco ding o he
p oduc o o al a ic and he squa e o hop-coun o he in ol ed
lows:
Φcomm
u, ( i) = −X
sd:( s= i)∨( d= i)
Bsd ·(hx
sd +hy
sd)2.
The squa e o hop-coun penalizes asks wi h longe lows, a he
han hose wi h high bandwid h, since Bsd is a cons an pa ame e
ha canno be changed. The selec ion o he anked asks ends o
pick asks wi h high communica ion cos . The nega i e sign allows
o ank he asks in ascending o de o i ness.
Simila i ness is used o selec un a o able ask imapped o
p ocesso pj o he con olle - ela ed e m o powe :
Φcomm
u,mc ( i) = −Λ( i)·McDis (pj)2.
Al hough he i ness unc ions selec ed o bo h e ms o communi-
ca ion powe look simila , we conside hem as indi idual candida es
o mul ip oduc op imiza ion. The in insic di e ence be ween he
wo ypes o communica ion is ha an in e - ask low depends on
mapping o bo h, sou ce and des ina ion asks, while he memo y
con olle low depends on one, ei he sou ce o des ina ion ask.
The i ness unc ion o he eplacemen ask is he same o
bo h ypes o communica ion. I aims a selec ing a ask ha , when
swapped wi h u, would mos ly dec ease he communica ion cos and
con ibu e o educe he iola ions o maximum bandwid h:
Φcomm
( i) = Cos (NewSol) ·(1 + CapP(NewSol)),
whe e NewSol is he solu ion ob ained by swapping iand u.
The compu a ion-o ien ed i ness unc ions aim a inding powe -
e icien solu ions by smoo hing he ol age spillo e in he ol age
islands. Le us call Vmin
i he minimum ol age equi ed o gua an ee
he h oughpu o ask iassigned o a p ocesso in some ol age
island ιn. Since ask is li ing in he same island wi h o he asks, i
may no be possible o assign Vmin
i o i , as o he asks may equi e
a highe ol age.
We de ine he ol age spillo e o ias Spillo e i=Vmin
i−V,
whe e Vis he a e age minimal ol age o all asks alloca ed in he
same ol age island. The dispe sion o island ιnis de ined as
Dispe sionn=X
i∈ιn
(Spillo e i)2.
and measu es he ol age imbalance o he island. High dispe sions
imply less powe -e icien solu ions, as mo e p ocesso s ope a e
a ol ages highe han equi ed. Compu a ional i nesses aim a
dec easing he ol age dispe sion o he sys em. The un a o able
componen is selec ed om he asks wi h he high spillo e alue:
Φcomp
u( i) = −Spillo e i.
The eplacemen ask is selec ed o maximize he p oduc o he
cos imp o emen wi h he dispe sion, penalizing solu ions wi h la ge
capaci y iola ions:
Φcomp
( i) = 1 + CapP(NewSol)
∆Cos ·∆Dispe sion.
V. EXPERIMENTAL RESULTS
The esul s p esen ed in his sec ion ha e h ee p ima y objec i es.
Fi s ly, op imal solu ions a e ob ained o small examples by sol ing
he MILP model. I is shown ha me aheu is ics can also ind he
op imum o hese examples, and in much sho e ime. Secondly,
he quali y and speed o SA and EO a e compa ed. The la e
is demons a ed o ou pe o m in bo h me ics o a as space
o solu ions. Thi dly, he impac o he link capaci y and memo y
bandwid h cons ain s is discussed.
A. Examples and expe imen al se up
E e y es case o he mapping p oblem is cha ac e ized by an
applica ion ask g aph and a a ge CMP. The pa ame e s o he es
cases a e p esen ed in Table III. The numbe o asks and lows a e
epo ed in he second and hi d columns. The ou h column shows
he dimensions o he mesh o he a ge CMP. The las column
displays he numbe o memo y con olle s in each es case.
The i s g oup o examples is inspi ed by he ealis ic applica ions,
widely used in he SoC esea ch domain (e.g. [12], [23]): Mul i-
Window Displaye (MWD),MPEG4 decode (MPEG4) and Objec
Plane Decode (OPD). To explo e he scalabili y o he p oposed
Name # o asks # o lows G id size # o MC
MWD 12 11 4×32
MPEG4 12 13 4×32
OPD 16 17 4×42
64T 64 90 8×84
144T 144 200 12 ×12 4
256T 256 380 16 ×16 8
400T 400 595 20 ×20 8
TABLE III: Tes case con igu a ions.
Class 1.2V 1.0V 0.8V
C1 1000MHz, 260mW 800MHz, 150mW 600MHz, 70mW
C2 450MHz, 200mW 350MHz, 120mW 250MHz, 60mW
C3 160MHz, 55mW 130MHz, 30mW 100MHz, 15mW
TABLE IV: Pa ame e s o he p ocesso classes.
echnique, we gene a e a g oup o la ge examples o mapping on o
8×8,12 ×12,16 ×16 and 20 ×20- ile CMPs ( es cases 64T o
400T). The ask g aphs o hese con igu a ions a e ob ained by
combining ins ances o MWD,MPEG4 and OPD. Fo ins ance, he
ask g aph o 400T consis s o 30 small applica ions, 10 ins ances
o each ype. To a oid ha ing o ally disconnec ed clus e s o asks,
ew andom lows we e added be ween he componen s. The hi d
column o Table III displays he esul ing numbe o lows in g aphs.
Fo he expe imen s, we ha e conside ed h ee p ocesso classes
(C1, C2 and C3) wi h di e en equency and powe pa ame e s
ope a ing a h ee di e en ol ages: 1.2V, 1.0V and 0.8V. The
pa ame e s a e epo ed in Table IV. The dis ibu ion o iles in
he CMP is as ollows: 20% o he iles ha e C1-p ocesso s, 30%
ha e C2-p ocesso s and 50% ha e C3-p ocesso s. The classes a e
dis ibu ed uni o mly in such a way ha all ol age islands ha e a
simila mix u e o classes. Wi hou loss o gene ali y, we assume ha
all islands ha e he same size S i (numbe o iles). Di e en alues
ha e been used in he expe imen s.
E e y ask has a di e en h oughpu equi emen (IPS) and a
di e en pe o mance when execu ed a each class o p ocesso
(IPC). All hese alues a e de ined andomly, wi h IPC alues in
he in e al [0.5,2.0] and gua an eeing ha a easible mapping exis s
o he assigned pe o mance and h oughpu equi emen s. This
andomiza ion con ibu es o explo e a la ge se o con igu a ions
and o ha e an unbiased uning o he me aheu is ics.
The a ic Λ( i)be ween he ask iand memo y con olle was
es ima ed as 20% o o al a ic be ween iand all o he asks. The
a io be ween he eques and eply a ic was se o ρ= 0.2.
SA is pa ame ized by wo alues: he ini ial empe a u e Tini and
he cooling ac o α. In ou expe imen s we de ine Tini = 104and
only a y he α alue. Gi en ha a la ge ange o α alues ha e
been explo ed o each expe imen , he quali y o he solu ions is no
dependen on Tini . The only pa ame e o EO is τ, i.e., he exponen
o he powe -law (eq. (17)). Sec ion V-C discusses he s a egy used
o explo e he alues o αand τ.
B. Compa ison wi h he op imal solu ion
The MILP o mula ion allows ob aining op imal solu ions o he
mapping p oblem. Howe e , he sea ch o he op imum is compu a-
ionally a o dable only o small examples. We used CPLEX [24] o
sol e he MILP p oblem o he es cases o he i s g oup: MWD,
MPEG4 and OPD. The size o ol age islands S i was se o ou . The
ime equi ed o ind he op imum is displayed in he “MILP” column
o Table V. One can obse e he wo-o de inc ease in un ime o
Name MILP SA EO
MWD 85.25 0.01 0.01
MPEG4 120.17 0.02 0.01
OPD 4594.40 1.17 0.08
TABLE V: Time o each he op imal solu ion (sec).
a 16- ile example (OPD) in compa ison wi h he 12- ile examples
(MWD,MPEG4).
The me aheu is ics a e able o achie e he op imal solu ion o he
same examples in much sho e ime (columns “SA” and “EO” o
Table V). In his expe imen he SA and EO algo i hms we e un o
a a ie y o pa ame e s (αand τ), and he bes un ime alues we e
selec ed. This compa ison a i ms he ac , ha bo h me aheu is ics
pe o m e y well o he small examples wi h known op imum.
C. Simula ed Annealing and Ex emal Op imiza ion: compa ison
This sec ion ies o gi e an apple- o-apple compa ison o bo h
me aheu is ics o he ask mapping p oblem. The compa ison is
illus a ed using he 256T example wi h S i = 16 and ep esen s
a ypical beha io o he wo algo i hms o he explo ed es cases.
The imeou o execu ion was se o 200 seconds, since no
signi ican imp o emen s we e obse ed a e ha ime o bo h
me hods. Figu e 4 depic s he e olu ion o he cos unc ion alue
ob ained by SA wi h a ious αand by EO wi h τ= 4.0. The aces
co esponding o highe alues o αd op slowe , bu achie e be e
solu ions in he long un.
Le us now conside he EO ace. A e e y momen in ime he
cu en solu ion ound by EO is be e han any o he SA solu ions,
ob ained wi h di e en α alues. The esul ing cos disco e ed by EO
upon imeou ou pe o ms any o he SA solu ions by 12%. Ano he
impo an ac is ha EO solu ion cos d ops apidly (0.1-2.5 seconds,
depending on he es case), o he 10% o accu acy, wi h espec o
he alue ob ained in he long un. This makes EO use ul o apply
when as es ima ion o he cos is equi ed, e.g. in explo a ion loops.
SA equi es a ca e ul uning o elimina e he dependency o he α
pa ame e on he p oblem size. O he wise, small changes in αmay
lead o an impo an deg ada ion in quali y. In his wo k we do no
aim a uning he SA me hod. Ra he , we pe o m mul iple uns wi h
di e en α alues and selec he bes esul s. The aim is o show ha
EO is a be e al e na i e e en wi h a e y good uning o SA.
In he expe imen s, i was also obse ed ha EO is much less
sensi i e o τand o he size o he p oblem. This simpli ies he
uning o he algo i hm. No e ha some a ia ion o τmay p o ide
sligh ly be e esul s o ce ain examples. Howe e , we do no aim
a demons a ing he highes imp o emen o all es cases. We p e e
o emphasize ha e en ha ing τ ixed, EO is able o ou pe o m SA
wi h any α. Guided by his easoning, in he ollowing expe imen s
we always de ine τ= 4.0. This alue was ound o deli e good
esul s o all es cases.
D. Powe op imiza ion wi h EO
In his sec ion we analyze he inal solu ions ob ained wi h a
imeou o 200 seconds. The goal is o s udy he educ ion in
powe ha EO deli e s in compa ison wi h SA o b oad se o
con igu a ions. I is impo an o indica e ha he esul s ob ained by
SA we e selec ed by aking he bes solu ion om all he α alues,
hus making he analysis independen o he cooling ac o .
Th ee pa ame e s a e explo ed o ob ain a comp ehensi e collec ion
o es cases. Fi s ly, examples o di e en size a e conside ed. These
include he 64T,144T,256T and 400T con igu a ions om Table III.
Secondly, o e e y es case he size o he ol age islands is a ied
25
30
35
40
45
50
55
60
65
70
75
80
85
0 20 40 60 80 100 120 140 160 180 200 220
Run ime (sec)
Powe (W)
SA, α=0.999
SA, α=0.99995
SA, α=0.99998
SA, α=0.99999
EO, τ=4.0
12%
Fig. 4: E olu ion o SA and EO solu ions in ime.
among 4, 8 and 16 p ocesso s. Thi dly, di e en a ios be ween
he compu a ion powe Pcomp and communica ion powe Pcomm a e
conside ed. This is an impo an pa ame e , as i e lec s he abili y
o he app oach o gi e p io i y o one powe componen o imp o e
bo h simul aneously. Th ee alues o Pcomp/Pcomm a e explo ed: 0.2,
1.0 and 5.0. They and inspi ed by he esul s p esen ed in [14].
Figu e 5 epo s he powe (equa ion (1)) o he EO solu ion
wi h espec o he bes alue ob ained by SA wi h a ious α. Fo
each con igu a ion, deno ed as es case/S i along he X-axis, h ee
alues o di e en Pcomp/Pcomm a e shown. Fo he majo i y o
con igu a ions EO ou pe o med he esul s o SA, wi h a maximum
gain in powe o 22.5% (con igu a ion 256T/16,Pcomp/Pcomm =
5.0). Only o 3 o 36 explo ed con igu a ions (64T/4,64T/16 and
400T/4 wi h Pcomp/Pcomm = 0.2) EO was sligh ly wo se han SA. The
di e ence in his case did no exceed 2.0%.
EO ends o pe o m be e a highe Pcomp as well as o la ge
alues o S i. In o he wo ds, EO be e minimizes he ol age o
islands, due o he conside a ion o ol age spillo e . As he island
size g ows, he amoun o asks, equi ed o be swapped in o de
o imp o e he ol age, also inc eases. This is one o he impo an
ea u es o EO, since i can model he i ness o each componen in he
sys em. Modeling he ol age spillo e in SA is di icul , since only
a global cos is conside ed in he accep ance o mo es and andom
swaps do no concen a e on he componen s wi h wo s i ness.
As an example, Fig. 6 shows he inal ol age dis ibu ions o he
256T example wi h S i = 16. The sys em has 16 ol age islands and
each island con ains 16 p ocesso s wi h a mix u e o C1, C2 and C3
classes, as shown in Fig. 6(a). The inal ol age assignmen o each
island is ep esen ed by he h ee colo s in he igu e. The solu ion
ob ained by SA has 8 islands a 1.2V, 5 a 1.0V and 3 a 0.8V. The
one ob ained by EO has 3 islands a 1.2V, 6 a 1.0V and 7 a 0.8V.
The es ima ed powe consump ion o he EO solu ion is 12% smalle
han he SA solu ion.
Ano he in ui i e esul is ha he o al powe g ows wi h he size
o ol age islands (Fig 6(c)). The island size se s he numbe o iles
0.6
0.7
0.8
0.9
1
1.1
64T/4
64T/8
64T/16
144T/4
144T/8
144T/16
256T/4
256T/8
256T/16
400T/4
400T/8
400T/16
Con igu a ion
Powe educ ion, EO/SA
Pcomp/Pcomm ≈ 0.2
Pcomp/Pcomm ≈ 1.0
Pcomp/Pcomm ≈ 5.0
Fig. 5: Powe educ ion by EO wi h espec o SA.
C3 C2 C3
C1
C2 C3 C1
C3
C3 C2 C3
C2
C1 C3 C2
C3
0.8V 1.0V 1.2V
(a) SA solu ion (b) EO solu ion
VI size = 8
VI size = 16
VI size = 4
0
5
10
15
20
25
30
35
40
Powe (W)
(c) EO powe
Fig. 6: Vol age dis ibu ion and powe o 256T example.
ha mus un a he same ol age. Hence, la ge islands imply less
mapping lexibili y o indi idual iles o educe ol age.
E. Impac o link capaci y and memo y bandwid h
The link capaci y and memo y con olle bandwid h cons ain s
ha e a ele an in luence on powe consump ion. In his example we
ix he memo y bandwid h and analyze how he solu ion changes as
he link capaci y cons ain becomes mo e s ingen . The dependency
o powe on he memo y bandwid h has a simila end. We use
again he es case 256Twi h S i = 16 and se he bandwid h o
each memo y con olle o 3 Gbps.
The esul s o SA and EO a e plo ed in Fig. 7. A sequence o
solu ions o di e en alues o capaci y cons ain s was ob ained.
The minimum capaci y equi ed o ob ain easible solu ions was
Capmin = 0.91 Gbps, and was eached by bo h me hods. The
endlines included in he plo help o analyze he e olu ion o he
solu ions as he link capaci y changes.
The endency o powe is o inc ease as capaci y cons ain igh -
ens up. This happens p incipally due o he g ow h in communica ion
cos as he asks need o be sp ead o a oid conges ion in he links.
Al hough he gap be ween he EO and SA cos s dec eases as he
capaci y app oaches o Capmin, EO wins in powe o all conside ed
alues. This example ep esen s he ypical beha io , obse ed o
bo h me aheu is ics, when op imizing a con igu a ion subjec o
capaci y cons ain s.
VI. CONCLUSIONS
Design euse will become a majo pa adigm o enginee ing many-
co e sys ems. This pape has add essed he p oblem o s a ic ask
mapping o la ge-scale iled CMPs wi h mul iple ol age islands, as
one o he app oaches o educe design cos and ime- o-ma ke . The
p oblem o mula ion conside s ask h oughpu equi emen s, on-chip
and o -chip memo y a ic, and bandwid h cons ain s. Ex emal
op imiza ion me aheu is ic has shown o be an e icien and scalable
app oach o sol e his complex combina o ial p oblem.
30
35
40
45
50
55
60
0.5 1 1.5 2 2.5 3 3.5 4
Link capaci y (Gbps)
Powe (W)
SA
EO
min capaci y = 0.91
Fig. 7: Impac o link capaci y on sys em powe .
VII. ACKNOWLEDGEMENT
This esea ch has been unded by p ojec CICYT TIN2007-66523,
FPI g an BES-2008-004612, and g an s om In el Co po a ion and
Ca alan Go e nmen (SGR 2009-1137).
REFERENCES
[1] D. Pham e al., “O e iew o he a chi ec u e, ci cui design, and
physical implemen a ion o a i s -gene a ion cell p ocesso ,” Solid-S a e
Ci cui s, ol. 41, no. 1, pp. 179–196, 2006.
[2] S. Rusu e al., “A 45nm 8-co e en e p ise Xeon p ocesso ,” in Solid-S a e
Ci cui s, no . 2009, pp. 9–12.
[3] T. Fishe e al., “Design solu ions o he Bulldoze 32nm SOI 2-co e
p ocesso module in an 8-co e CPU,” in Solid-S a e Ci cui s, eb. 2011,
pp. 78–80.
[4] S. Bell e al., “TILE64 - p ocesso : A 64-co e SoC wi h mesh in e con-
nec ,” in Solid-S a e Ci cui s, eb. 2008, pp. 88 –598.
[5] S. Vangal e al., “An 80- ile 1.28TFLOPS ne wo k-on-chip in 65nm
CMOS,” in Solid-S a e Ci cui s, eb. 2007, pp. 98 –589.
[6] R. Ma culescu, U. Y. Og as, L.-S. Peh, N. E. Je ge , and Y. Hosko e,
“Ou s anding esea ch p oblems in NoC design: sys em, mic oa chi ec-
u e, and ci cui pe spec i es,” IEEE T ansac ions on Compu e -Aided
Design, ol. 28, no. 1, pp. 3–21, Jan. 2009.
[7] M. Azimi e al., “In eg a ion Challenges and T adeo s o Te a-scale
A chi ec u es,” In el Technology Jou nal, Augus 2007.
[8] S. Balak ishnan, R. Rajwa , M. Up on, and K. Lai, “The impac o
pe o mance asymme y in eme ging mul ico e a chi ec u es,” in In e -
na ional Symposium on Compu e A chi ec u e, 2005, pp. 506–517.
[9] D. Lackey e al., “Managing powe and pe o mance o Sys em-on-Chip
designs using ol age islands,” in P oc. In e na ional Con . Compu e -
Aided Design (ICCAD), 2002, pp. 195–202.
[10] W. Kim, M. Gup a, G.-Y. Wei, and D. B ooks, “Sys em le el analysis
o as , pe -co e DVFS using on-chip swi ching egula o s,” in High
Pe o mance Compu e A chi ec u e, Feb. 2008, pp. 123–134.
[11] W.-K. Mak and J.-W. Chen, “Vol age island gene a ion unde pe o -
mance equi emen o soc designs,” in P oc. o Asia and Sou h Paci ic
Design Au oma ion Con e ence, 2007, pp. 798–803.
[12] P. Ghosh and A. Sen, “Ene gy e icien mapping and ol age islanding
o egula NoC unde design cons ain s,” J. High Pe o m. Sys . A chi .,
ol. 2, pp. 132–144, Augus 2010.
[13] W.-L. Hung e al., “Tempe a u e-awa e ol age islands a chi ec ing in
Sys em-on-Chip design,” in P oc. In e na ional Con . Compu e Design
(ICCD), 2005, pp. 689–696.
[14] G. Va a ka and R. Ma culescu, “Communica ion-awa e ask scheduling
and ol age selec ion o o al sys ems ene gy minimiza ion,” in P oc.
In e na ional Con . Compu e -Aided Design (ICCAD), 2003.
[15] G. Chen, F. Li, S. Son, and M. Kandemi , “Applica ion mapping o chip
mul ip ocesso s,” in P oc. ACM/IEEE Design Au oma ion Con e ence,
2008, pp. 620 –625.
[16] W. Dally and B. Towles, P inciples and P ac ices o In e connec ion
Ne wo ks. Mo gan Kau mann Publishe s, Inc., 2003.
[17] S. Boe che and A. G. Pe cus, “Ex emal op imiza ion: Me hods de i ed
om co-e olu ion,” in Gene ic and E olu iona y Compu a ion, 1999, pp.
825–832.
[18] I. De Falco, A. Della Cioppa, D. Mais o, U. Sca u i, and E. Ta an ino,
“A mul iobjec i e ex emal op imiza ion algo i hm o e icien mapping
in g ids,” in Applica ions o So Compu ing, ol. 58, 2009, pp. 367–377.
[19] G. D. Micheli and L. Benini, Ne wo ks on Chips: Technology and Tools
(Sys ems on Silicon). Mo gan Kau mann Publishe s, Inc., 2006.
[20] D. Ab s, N. D. E. Je ge , J. Kim, D. Gibson, and M. H. Lipas i,
“Achie ing p edic able pe o mance h ough be e memo y con olle
placemen in many-co e CMPs,” in In . Symp. Compu e A chi ec u e,
2009, pp. 451–461.
[21] S. Ki kpa ick, C. D. Gela , and M. P. Vecchi, “Op imiza ion by
simula ed annealing,” Science, ol. 220, pp. 671–680, 1983.
[22] T. Zhou, W.-J. Bai, L.-J. Cheng, and B.-H. Wang, “Con inuous ex emal
op imiza ion o Lenna d-Jones clus e s,” Phys. Re . E, ol. 72, no. 1,
Jul 2005.
[23] A. Pin o, L. P. Ca loni, and A. L. Sangio anni-Vincen elli, “A me hod-
ology o cons ain -d i en syn hesis o on-chip communica ions,” IEEE
T ansac ions on Compu e -Aided Design, ol. 28, no. 3, pp. 364–377,
Ma . 2009.
[24] “CPLEX,” h p://www.ilog.com/p oduc s/cplex.