Static task mapping for tiled chip multiprocessors with multiple voltage islands

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.