Baixe o app para aproveitar ainda mais
Prévia do material em texto
C o m p u ta c¸a˜ o P ar a le la H et er o g eˆn ea In tr o d u c¸a˜ o a` C o m p u ta c¸a˜ o P ar a le la D o u g la s A d r ia n o A u g u st o d o u g l a s @ l n c c . b r L a b o ra to´ ri o N a ci o n a l d e C o m p u ta c¸a˜ o C ie n t´ı fi ca G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 In tr o d u c¸a˜ o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 In tr o d u c¸a˜ o “C o m p u ta c¸a˜ o p ar a le la d iz re sp ei to a o u so d e in st aˆ n ci a s co n co rr en te s d e p ro ce ss a m en to co m p u ta ci o n a l n a a b o rd a g em d e u m p ro b le m a .” G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 In tr o d u c¸a˜ o “C om pu ta c¸a˜ o pa ra le la di z re sp ei to ao u so d e in st aˆ n ci a s co n co rr en te s de pr o ce ss am en to co m pu ta ci on al na ab or da ge m de um pr ob le m a. ” • u so d e in st aˆ n ci a s co n co rr en te s, m as n a˜ o ne ce ss ar ia m en te : • ca da in st aˆn ci a em um pr o ce ss ad or f´ı si co di fe re nt e G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 4 In tr o d u c¸a˜ o “C om pu ta c¸a˜ o pa ra le la di z re sp ei to ao u so d e in st aˆ n ci a s co n co rr en te s de pr o ce ss am en to co m pu ta ci on al na ab or da ge m de um pr ob le m a. ” • u so d e in st aˆ n ci a s co n co rr en te s, m as n a˜ o ne ce ss ar ia m en te : • ca da in st aˆn ci a em um pr o ce ss ad or f´ı si co di fe re nt e • pa ra ac el er ar a ex ec uc¸ a˜o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 5 In tr o d u c¸a˜ o “C om pu ta c¸a˜ o pa ra le la di z re sp ei to ao us o de in st aˆn ci as co nc or re nt es de pr o ce ss am en to co m pu ta ci on al na a b o rd a g em de um pr ob le m a. ” • u so d e in st aˆ n ci a s co n co rr en te s, m as n a˜ o ne ce ss ar ia m en te : • ca da in st aˆn ci a em um pr o ce ss ad or f´ı si co di fe re nt e • pa ra ac el er ar a ex ec uc¸ a˜o • na a b o rd a g em , m as n a˜ o ne ce ss ar ia m en te na re so lu c¸a˜ o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 6 In tr o d u c¸a˜ o “C om pu ta c¸a˜ o pa ra le la di z re sp ei to ao us o de in st aˆn ci as co nc or re nt es de pr o ce ss am en to co m pu ta ci on al na ab or da ge m de u m p ro b le m a .” • u so d e in st aˆ n ci a s co n co rr en te s, m as n a˜ o ne ce ss ar ia m en te : • ca da in st aˆn ci a em um pr o ce ss ad or f´ı si co di fe re nt e • pa ra ac el er ar a ex ec uc¸ a˜o • na a b o rd a g em , m as n a˜ o ne ce ss ar ia m en te na re so lu c¸a˜ o • de u m p ro b le m a cu ja s in st aˆn ci as se re la ci on am G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 7 In tr o d u c¸a˜ o P o r q u e p ar a le liz ar u m a lg o ri tm o ? G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 8 In tr o d u c¸a˜ o P o r q u e p ar a le liz ar u m a lg o ri tm o ? • D im in ui r o te m p o de ex ec uc¸ a˜o • V ia bi liz ar o au m en to da di m en sa˜ o de um pr ob le m a • E xp an di r a cl as se de pr ob le m as co m pu ta ci on al m en te tr at a´v ei s O ut ro s m ot iv os : • A pr ov ei ta r re cu rs os co m pu ta ci on ai s (m em o´r ia e pr o ce ss am en to ) di sp on´ ıv ei s na˜ o lo ca lm en te • S im ul ar na tu ra lm en te m o de lo s pa ra le lo s/ di st ri bu´ ıd os G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 9 In tr o d u c¸a˜ o F o rm a s d e a ce le ra m en to d a ex ec u c¸a˜ o : • E m pr eg an do -s e pr o ce ss ad or es m ai s p ot en te s • A um en ta nd o- se a efi ci eˆn ci a do al go ri tm o (o ti m iz ac¸ a˜o ) • P ar al el iz an do -s e o al go ri tm o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 0 P ar a le lis m o E xp l´ıc it o e Im p l´ıc it o A co m p os ic¸ a˜o de um al go ri tm o pa ra le lo en vo lv e: • D et ec c¸a˜ o de p or c¸o˜ es pa ra le liz a´v ei s • C o di fi ca c¸a˜ o de ta is p or c¸o˜ es em lin gu ag em pa ra le la : ob ed ec en do -s e a ar qu it et ur a em qu es ta˜ o co nt ro la nd o- se ex ec uc¸ a˜o e co m un ic ac¸ a˜o O pr o ce ss o p o de se r ob ti do ex p lic it a m en te : • re al iz ad o m an ua lm en te p or um es p ec ia lis ta ou im p lic it a m en te : • re al iz ad o au to m at ic am en te p el o co m pi la do r ou ha rd w ar e G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 1 A rq u it et u ra s P ar a le la s G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 2 C la ss ifi ca c¸a˜ o d a s A rq u it et u ra s P ar a le la s T a xo n o m ia d e F ly n n : S a˜o ba se ad as em du as ca ra ct er´ ıs ti ca s or to go na is : • fl ux o de in st ru c¸o˜ es e fl ux o de d a d o s ca da qu al as su min do as qu an ti da de s • u´ n ic a (s in gl e) ou m u´ lt ip la (m ul ti pl e) G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 3 T a xo n o m ia d e F ly n n – S IS D A rq u it et u ra S IS D : • P o de ex ec ut ar um a u´n ic a in st ru c¸a˜ o so br e um fl ux o de da do s a ca da m om en to • M o de lo tr ad ic io na l de co m pu ta do re s un ip ro ce ss ad os (m a´q ui na s es ca la re s) G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 4 T a xo n o m ia d e F ly n n – S IM D A rq u it et u ra S IM D : • P o de ex ec ut ar um a u´n ic a in st ru c¸a˜ o so br e di fe re nt es fl ux os de da do s p or ve z • M a´q ui na s ve to ri ai s, G P U s, e in st ru c¸o˜ es es te nd id as S IM D (e x: In te l A V X ) G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 5 T a xo n o m ia d e F ly n n – M IS D A rq u it et u ra M IS D : • P o de ex ec ut ar di fe re nt es in st ru c¸o˜ es so br e um fl ux o de da do s p or ve z • T ip o ra ro de ar qu it et ur a; de ap lic ac¸ o˜e s re st ri ta s G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 6 T a xo n o m ia d e F ly n n – M IM D A rq u it et u ra M IM D : • P o de ex ec ut ar di fe re nt es in st ru c¸o˜ es so br e di fe re nt es fl ux os de da do s a ca da m om en to • A m ai s fl ex´ ıv el e p op ul ar da s ar qu it et ur as : C P U s de va´ ri os nu´ cl eo s, m ul ti pr o ce ss ad or es , et c. G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 7 S P M D : S in g le P ro g ra m M u lt ip le D a ta A ar q u it et u ra S P M D e´ u m a su b ca te g o ri a d a M IM D : • P o de ex ec ut ar di fe re nt es in st ru c¸o˜ es de um m es m o pr og ra m a so br e di fe re nt es fl ux os de da do s p or ve z • G P U s m o de rn as sa˜ o S P M D em um ce rt o n´ı ve l: G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 8 M o d el o s d e M em o´ ri a s D iz re sp ei to a` or ga ni za c¸a˜ o de ac es so do es pa c¸o de m em o´r ia p el as un id ad es co m pu ta ci on ai s: M em o´ ri a C o m p ar ti lh a d a : • T o do s os pr o ce ss ad or es teˆ m ac es so ao m es m o es pa c¸o de m em o´r ia (m es m o en de re c¸a m en to ) • A “c om un ic ac¸ a˜o ” e´ fe it a p or ac es so di re to a` m em o´r ia M em o´ ri a D is tr ib u´ ıd a : • C ad a pr o ce ss ad or so´ ac es sa di re ta m en te su a m em o´r ia lo ca l (d if er en te s en de re c¸a m en to s) • A co m un ic ac¸ a˜o e´ fe it a p or tr o ca de m en sa ge ns (c an al m ai s le nt o) M em o´ ri a C o m b in a d a / M is ta : • S is te m a qu e co m bi na am b os m o de lo s de m em o´r ia . G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 9 M em o´ ri a C o m p ar ti lh a d a (a ) b ar ra (b ) co m u ta d or G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 0 M em o´ ri a D is tr ib u´ ıd a (a ) b ar ra (b ) co m u ta d or G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 1 M em o´ ri a C o m p ar ti lh a d a vs D is tr ib u´ ıd a M em o´ ri a C o m p ar ti lh a d a : V an ta ge ns : • M ai s fa´ ci l de co m p os ic¸ a˜o /p ro gr am ac¸ a˜o de pr ob le m as • A lg un s al go ri tm os so´ ex ec ut am efi ci en te m en te ne st e ti p o de ar qu it et ur a D es va nt ag en s: • C us to m ai s el ev ad o • R es tr ic¸ a˜o pr a´t ic a qu an to ao nu´ m er o de pr o ce ss ad or es • Q ua nt o m ai s pr o ce ss ad or es , m ai or a co nt en c¸a˜ o de ac es so a` m em o´r ia : √ 1+ (N /M )2 − N /M Q ua nd o N = M , ≈ 40 % do s pr o ce ss ad or es teˆ m ac es so bl o qu ea do em ca da ci cl o de m em o´r ia G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 2 M em o´ ri a C o m p ar ti lh a d a vs D is tr ib u´ ıd a M em o´ ri a D is tr ib u´ ıd a : V an ta ge ns : • M en or cu st o p or ca pa ci da de de pr o ce ss am en to • M ai s es ca la´ ve l D es va nt ag en s: • D ec om p os ic¸ a˜o /p ro gr am ac¸ a˜o m en os di re ta • A lg um as cl as se s de al go ri tm os na˜ o se ad eq ua m a es te ti p o de ar qu it et ur a G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 3 A´ rv o re M IM D G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 4 T em p o d e E xe cu c¸a˜ o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 5 C oˆ m p u to e C o m u n ic a c¸a˜ o O te m p o to ta l de ex ec uc¸ a˜o e´ di vi di do em : • C o m p u ta c¸a˜ o • ex ec uc¸ a˜o de in st ru c¸o˜ es • le it ur a e es cr it a de m em o´r ia • af et ad o p el o nu´ m er o de op er ac¸ o˜e s, ve lo ci da de de co m pu ta c¸a˜ o e ac es so a` m em o´r ia • C o m u n ic a c¸a˜ o • tr o ca de m en sa ge ns en tr e pr o ce ss ad or es (d ados , co m an do s) : en vi o, re ce bi m en to e es p er a • en tr ad a e sa´ ıd a • af et ad o p el o nu´ m er o de tr o ca s, ta m an ho , ve lo ci da de do m ei o e ov er he ad s. G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 6 G ra n u la ri d a d e G ra nu la ri da de e´ a fr ac¸ a˜o (“ re so lu c¸a˜ o” ) da ca rg a de tr ab al ho di st ri bu´ ıd a en tr e os pr o ce ss ad or es . • E st a´ in ti m am en te re la ci on ad a co m a ra za˜ o en tr e o cu st o d e co m p u ta c¸a˜ o e o cu st o d e co m u n ic a c¸a˜ o • S ua re le vaˆ nc ia e´ pr op or ci on al a` ne ce ss id ad e/ fr eq ueˆ nc ia de co m un ic ac¸ a˜o de um al go ri tm o pa re le lo G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 7 G ra n u la ri d a d e D ile m a d a g ra n u la ri d a d e: • gr an ul ar id ad e gr os sa : m en os co m un ic ac¸ a˜o , m as m en os pa ra le liz a´v el co m un ic ac¸ a˜o m ai s efi ci en te na˜ o es ca la´ ve l a um m ai or nu´ m er o de pr o ce ss ad or es te nd eˆn ci a ao de sb al an ce am en to de ca rg a • gr an ul ar id ad e fi na : m ai s co m un ic ac¸ a˜o , m as m ai s pa ra le liz a´v el co m un ic ac¸ a˜o m en os efi ci en te (l at eˆn ci a) es ca la´ ve l a um m ai or nu´ m er o de pr o ce ss ad or es fa ci lid ad e de ba la nc ea m en to de ca rg a G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 8 G ra n u la ri d a d e B as ic am en te , a de co m p os ic¸ a˜o em gr an ul ar id ad e fi n a ad eq ua -s e m el ho r a`s ar qu it et ur as de • ba ix o cu st o de co m un ic ac¸ a˜o ; e • m ai or nu´ m er o de pr o ce ss ad or es en qu an to a gr an ul ar id ad e g ro ss a a`s ar qu it et ur as de • al to cu st o de co m un ic ac¸ a˜o ; e • m en or nu´ m er o de pr o ce ss ad or es G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 9 C o m p u ta c¸a˜ o P ar a le la H et er o g eˆn ea In tr o d u c¸a˜ o a` C o m p u ta c¸a˜ o P ar a le la - II D o u g la s A d r ia n o A u g u st o d o u g l a s @ l n c c . b r L a b o ra to´ ri o N a ci o n a l d e C o m p u ta c¸a˜ o C ie n t´ı fi ca G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 T em p o d e E xe cu c¸a˜ o (c o n t. ) G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 G ra n u la ri d a d e G ra n u la ri d a d e g ro ss a (c oa rs e gr ai ne d ) 2 pr o ce ss ad or es G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 G ra n u la ri d a d e G ra n u la ri d a d e g ro ss a / fi n a (c oa rs e/ fi ne gr ai ne d ) 4 pr o ce ss ad or es G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 4 G ra n u la ri d a d e G ra n u la ri d a d e fi n a (fi ne gr ai ne d ) 16 pr o ce ss ad or es G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 5 L a teˆ n ci a , B a n d w id th e T h ro u g h p u t L a teˆ n ci a – te m p o m´ ın im o ga st o en tr e o in´ ıc io e fi m de um a u´n ic a op er ac¸ a˜o • co m un ic ac¸ a˜o , ac es so a` m em o´r ia , in st ru c¸a˜ o L ar g u ra d e b a n d a (b an dw id th ) – qu an ti da de de in fo rm ac¸ a˜o qu e p o de se r tr an sm it id a p or um ca na l de co m un ic ac¸ a˜o • co ne xa˜ o (r ed e, ba rr as , et c. ), m em o´r ia T h ro u g h p u t – qu an ti da de de tr ab al ho re al iz ad o p or un id ad e de te m p o • in st ru c¸o˜ es , da do s G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 6 C o m p le xi d a d e d o P ro b le m a e T ra b a lh o C o m p le xi d a d e d o p ro b le m a : • D im en sa˜ o do es pa c¸o de da do s (“ en tr ad a” ) E x. : N a m ul ti pl ic ac¸ a˜o de du as m at ri ze s M n ×n , a co m pl ex id ad e do pr ob le m a e´ n . C o m p le xi d a d e d e tr a b a lh o : • O p er ac¸ o˜e s ne ce ss a´r ia s pa ra re so lv er o pr ob le m a E x. : N a m ul ti pl ic ac¸ a˜o de du as m at ri ze s M n ×n , a co m pl ex id ad e de tr ab al ho e´ n 3 . G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 7 C o m p le xi d a d e d o P ro b le m a e T ra b a lh o S e um pr ob le m a de ta m an ho n p os su i co m pl ex id ad e de tr ab al ho cn q , o te m p o de ex ec uc¸ a˜o se qu en ci al se ra´ de or de m t = cn q S e o us o de p pr o ce ss ad or es p er m it e um au m en to da di m en sa˜ o p or um fa to r m : t = c( m n )q p , en ta˜ o pa ra qu e t p er m an ec¸ a co ns ta nt e p = m q ou m = q√ p G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 8 C o m p le xi d a d e d o P ro b le m a e T ra b a lh o Im p lic a c¸o˜ es S ej a a m ul ti pl ic ac¸ a˜o de du as m at ri ze s M n ×n . M an te nd o- se t co ns ta nt e: • E m um m a´q ui na pa ra le la co m 64 pr o ce ss ad ores a di m en sa˜ o n p o de cr es ce r ap en as qu at ro ve ze s: m = 3√ 6 4 = 4 • P ar a au m en ta rm os a di m en sa˜ o do pr ob le m a em du as or de ns de gr an de za se ri am ne ce ss a´r io s um m ilh a˜o de pr o ce ss ad or es : p = 10 03 = 10 00 00 0 G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 9 M ed id a s d e D es em p en h o T em p o s d e ex ec u c¸a˜ o : • T 1 = te m p o de ex ec uc¸ a˜o do al go ri tm o se qu en ci al • T p = te m p o de ex ec uc¸ a˜o do al go ri tm o pa ra le lo em p pr o ce ss ad or es S p ee d -u p : • M ed e o fa to r de m el ho ra em re la c¸a˜ o a` ve rs a˜o se qu en ci al : S (p ) = T 1 T p G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 0 M ed id a s d e D es em p en h o E fi ci eˆn ci a : • M ed e a efi ci eˆn ci a na re du c¸a˜ o do te m p o de ex ec uc¸ a˜o : E (p ) = S (p ) p = T 1 p × T p • Id ea lm en te E (p ) ≈ 1 T ra b a lh o P ar a le lo (p ar al le l w or k ): • W (p ) = nu´ m er o to ta l de op er ac¸ o˜e s pa ra le la s • Id ea lm en te W (p ) ≈ W (1 ) G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 1 C u rv a d e S p ee d -u p G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 2 L ei d e A m d a h l O sp ee d- up p ot en ci al e´ lim it ad o p el a eq ua c¸a˜ o S (·) ≤ 1 1 − P , on de P e´ a fr ac¸ a˜o pa ra le la do al go ri tm o. D ad o o nu´ m er o de pr o ce ss ad or es p, o sp ee d- up e´ lim it ad o p or S (p ) ≤ 1 (1 − P ) + P p P re ss u p o st o : P p er m an ec e es ta´ ti co qu an do o ta m an ho do pr ob le m a cr es ce . G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 3 L ei d e A m d a h l G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 4 L ei d e G u st a fs o n P ri n c´ı p io : • A um en ta r o ta m an ho do pr ob le m a em ve z de di m in ui r o te m p o de ex ec uc¸ a˜o P re ss u p o st o : O te m p o pa ra le lo cr es ce co m o ta m an ho do pr ob le m a. E nt a˜o : S (p ) = p − α ·( p − 1) , on de α e´ a fr ac¸ a˜o se qu en ci al . G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 5 L ei d e G u st a fs o n 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 Speed-up N um er o de p ro ce ss ad or es p - 0 .9 * (p- 1) p - 0 .8 * (p- 1) p - 0 .7 * (p- 1) p - 0 .6 * (p- 1) p - 0 .5 * (p- 1) p - 0 .4 * (p- 1) p - 0 .3 * (p- 1) p - 0 .2 * (p- 1) p - 0 .1 * (p- 1) G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 6 L ei d e G u st a fs o n C o n cl u sa˜ o • M in im iz ar a p or c¸a˜ o se qu en ci al , m es m o qu e au m en te a qu an ti da de to ta l de co m pu ta c¸a˜ o. • P ro bl em as on de a p or c¸a˜ o pa ra le la cr es ce em fu nc¸ a˜o do ta m an ho do pr ob le m a sa˜ o m ai s es ca la´ ve is . G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 7 C o m p u ta c¸a˜ o P ar a le la H et er o g eˆn ea In tr o d u c¸a˜ o a` C o m p u ta c¸a˜ o P ar a le la - II I D o u g la s A d r ia n o A u g u st o d o u g l a s @ l n c c . b r L a b o ra to´ ri o N a ci o n a l d e C o m p u ta c¸a˜ o C ie n t´ı fi ca G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 M et o d o lo g ia d e P ro g ra m a c¸a˜ o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 M et o d o lo g ia d e F o st er D es cr ic¸ a˜ o : • M e´t o do p op ul ar de pr og ra m ac¸ a˜o de al go ri tm os pa ra le lo s • P ro p os ta p or Ia n F os te r (1 99 6) • F o co in ic ia l no s as p ec to s in de p en de nt es do pr ob le m a, e en ta˜ o no s de p en de nt es E n vo lv e q u a tr o fa se s: • D ec om p os ic¸ a˜o • C om un ic ac¸ a˜o • A gl om er ac¸ a˜o • M ap ea m en to G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 M et o d o lo g ia d e F o st er G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 4 D ec o m p o si c¸a˜ o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 5 D ec o m p o si c¸a˜ o O b je ti vo s: • A id ei a e´ en co nt ra r op or tu ni da de s de pa ra le lis m o. • In ic ia lm en te pr o cu ra -s e a di vi sa˜ o do pr ob le m a em su b co m p on en te s m´ ın im os (g ra nu la ri da de fi na ). E xi st em du as es tr at e´g ia s pr in ci pa is : • D ec o m p o si c¸a˜ o d o D o m´ ın io : de co m p or o pr ob le m a em fu nc¸ a˜o do s da do s. • D ec o m p o si c¸a˜ o F u n ci o n a l: de co m p or o pr ob le m a em fu nc¸ a˜o da co m pu ta c¸a˜ o. Id ea lm en te bu sc a- se ta nt o a di vi sa˜ o do s da do s co m o a da co m pu ta c¸a˜ o. G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 6 D ec o m p o si c¸a˜ o d o D o m´ ın ioD a´ or ig em ao ch am ad o p ar a le lis m o d e d a d o s. • P ri m ei ro se di vi de m os da do s em pa rt ic¸ o˜e s; de p oi s se as so ci a co m pu ta c¸a˜ o a`s pa rt ic¸ o˜e s. • T o da s as ta re fa s ex ec ut am as m es m as op er ac¸ o˜e s. G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 7 D ec o m p o si c¸a˜ o d o D o m´ ın io G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 8 D ec o m p o si c¸a˜ o F u n ci o n a l D a´ or ig em ao ch am ad o p ar a le lis m o d e ta re fa s. • P ri m ei ro se di vi de a co m pu ta c¸a˜ o em pa rt ic¸ o˜e s; de p oi s se as so ci a os da do s a`s pa rt ic¸ o˜e s. • D if er en te s ta re fa s ex ec ut am di fe re nt es op er ac¸ o˜e s. G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 9 D ec o m p o si c¸a˜ o F u n ci o n a l E xe m pl o de um m o de lo cl im a´t ic o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 0 D ec o m p o si c¸a˜ o d e D o m´ ın io x F u n ci o n a l V an ta ge ns da d ec o m p o si c¸a˜ o p o r d o m´ ın io : • M ai s si m pl es • P ro du z gr an ul ar id ad e m ai s fi na (= m ai s es ca la´ ve l) • D is tr ib ui c¸a˜ o m ai s ho m og eˆn ea (= m el ho r ba la nc ea m en to ) • A da pt a- se m ai s fa ci lm en te a`s ar qu it et ur as pa ra le la s V an ta ge m da d ec o m p o si c¸a˜ o fu n ci o n a l: • T or na o al go ri tm o m ai s m o du la r E n tr et a n to , a s d u a s a b o rd a g en s n a˜ o sa˜ o ex cl u d en te s. G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 1 D ec o m p o si c¸a˜ o d e D o m´ ın io + F u n ci o n a l G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 2 D ec o m p o si c¸a˜ o d e D o m´ ın io e F u n ci o n a l S in a is d e u m a b o a d ec o m p o si c¸a˜ o : • A de co m p os ic¸ a˜o re su lt a em um nu´ m er o si gn ifi ca nt e de ta re fa s • A s ta re fa s sa˜ o co m pa ra´ ve is em ta m an ho • O nu´ m er o de ta re fa s cr es ce co m o ta m an ho do pr ob le m a • D if er en te s ti p os e va ri ac¸ o˜e s de de co m p os ic¸ a˜o fo ra m en co nt ra do s G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 3 C o m u n ic a c¸a˜ o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 4 C o m u n ic a c¸a˜ o F a to : • A s ta re fa s no rm al m en te re qu er em co m un ic ac¸ a˜o , is to e´, sa˜ o de al gu m a fo rm a de p en de nt es en tr e si . P or ta nt o, ne st e es ta´ gi o bu sc a- se : • Id en ti fi ca r as ne ce ss id ad es de co m un ic ac¸ a˜o • M o de la´ -l as de fo rm a efi ci en te G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 5 C o m u n ic a c¸a˜ o D e u m a fo rm a g er a l: • N a de co m p os ic¸ a˜o de do m´ ın io a co m un ic ac¸ a˜o te nd e a se r m en os n´ı ti da : • fo ca -s e no pa rt ic io na m en to do s da do s • E nq ua nt o qu e a es tr ut ur a m o du la r da de co m p os ic¸ a˜o fu nc io na l si m pl ifi ca as de p en deˆ nc ia s: • es tr ut ur as fu nc io na is au to -c on ti da s • co nc ei to de en tr ad a- e- sa´ ıd a (fl ux o en tr e ta re fa s) G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 6 P a d ro˜ es d e C o m u n ic a c¸a˜ o S a˜o cl as si fi ca do s qu an to a`: • L o ca lid a d e: lo ca l ou gl ob al • E st ru tu ra : es tr ut ur ad o ou na˜ o- es tr ut ur ad o • D in aˆ m ic a : es ta´ ti co ou di naˆ m ic o • S in cr o n ia : s´ı nc ro no ou as s´ı nc ro no G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 7 L o ca lid a d e d a C o m u n ic a c¸a˜ o L o ca l: • U m a ta re fa in te ra ge ap en as co m ta re fa s vi zi nh as ge ra lm en te e´ m ai s efi ci en te G lo b a l: • U m a ta re fa in te ra ge co m qu al qu er ou tr a ta re fa p er m it e m ai or fl ex ib ili da de G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 8 C o m u n ic a c¸a˜ o L o ca l E x: M e´t o d o d e J a co b i d e d if er en c¸a s fi n it a s X t+ 1 i, j = 4X t i, j + X t i− 1 ,j + X t i+ 1 ,j + X t i, j− 1 + X t i, j+ 1 8 G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 9 C o m u n ic a c¸a˜ o G lo b a l E x: S o m a ce n tr a liz a d a S = N −1 ∑ i=0X i G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 0 E st ru tu ra e D in aˆ m ic a d a C o m u n ic a c¸a˜ o E st ru tu ra d o : • A de p en deˆ nc ia en tr e ta re fa s fo rm a um a es tr ut ur a re gu la r, co m o um a a´r vo re ou gr ad e. N a˜ o -e st ru tu ra d o : • A co m un ic ac¸ a˜o en tr e ta re fa s e´ de sc ri ta p or um gr af o ar bi tr a´r io . E st a´ ti co : • O s pa rc ei ro s de co m un ic ac¸ a˜o na˜ o va ri am . D in aˆ m ic o : • A id en ti da de do s parc ei ro s de p en de de da do s co m pu ta do s/ ob ti do s du ra nt e a ex ec uc¸ a˜o . G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 1 P a d ra˜ o E st ru tu ra d o e E st a´ ti co G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 2 P a d ra˜ o N a˜ o -E st ru tu ra d o e D in aˆ m ic o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 3 C o m u n ic a c¸a˜ o S´ ın cr o n a P a d ra˜ o s´ı n cr o n o : • A s ta re fa s de p en de nt es sa b em qu an do de ve m o co rr er a co m un ic ac¸ a˜o e os da do s sa˜ o en vi ad os ex pl ic it am en te . G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 4 C o m u n ic a c¸a˜ o A ss´ ın cr o n a P a d ra˜ o a ss´ ın cr o n o : • N o pa dr a˜o as s´ı nc ro no as ta re fa s de p os se do s da do s na˜ o teˆ m co m o de te rm in ar qu an do os de st in at a´r io s es ta˜ o ap to s a re ce beˆ -l os . A s co m un ic ac¸ o˜e s o co rr em de fo rm a in de p en de nt e. G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 5 C o m u n ic a c¸a˜ o S in a is d e u m a b o a es tr a te´ g ia d e co m u n ic a c¸a˜ o : • T o da s as ta re fa s ex ec ut am ap ro xi m ad am en te o m es m o nu´ m er o de op er ac¸ o˜e s de co m un ic ac¸ a˜o . • C ad a ta re fa id ea lm en te de ve ri a co m un ic ar -s e co m um p eq ue no nu´ m er o de vi zi nh os . • A lg or it m os de co m un ic ac¸ a˜o s´ı nc ro na na˜ o de ve ri am le va r a` o ci os id ad e da s ta re fa s. G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 6 A g lo m er a c¸a˜ o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 7 A g lo m er a c¸a˜ o • V is a en gr os sa r a gr an ul ar id ad e de ce rt os gr up os de ta re fa s em pr ol da efi ci eˆn ci a. • P ro ce ss o de re vi sa˜ o da fa se de de co m p os ic¸ a˜o co ns id er an do -s e a es tr ut ur a de co m un ic ac¸ a˜o . • T ra ns ic¸ a˜o da pr og ra m ac¸ a˜o ab st ra ta pa ra a co nc re ta . • B as ic am en te , p on de ra r gr an ul ar id ad e e co m un ic ac¸ a˜o : o di le m a. • A ar qu it et ur a pa ra le la (o u cl as se de ) te m gr an de in fl ueˆ nc ia ne ss e es ta´ gi o. • P o de se r u´t il re pl ic ar da do s e/ ou co m pu ta c¸a˜ o. G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 8 A g lo m er a c¸a˜ o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 9 A g lo m er a c¸a˜ o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 0 A g lo m er a c¸a˜ o S in a is d e u m b o m em p re g o d a a g lo m er a c¸a˜ o : • A re pl ic ac¸ a˜o de da do s e/ ou co m pu ta c¸a˜ o qu an do ap lic ad a de ve ri a co m p en sa r a ex ec uc¸ a˜o ex tr a de op er ac¸ o˜e s. • S e a gr an ul ar id ad e fo i en gr os sa da , de ce rt o as ta re fa s es ta˜ o co m pa ra´ ve is em ta m an ho (c us to s de co m pu ta c¸a˜ o e co m un ic ac¸ a˜o ). • A ag lo m er ac¸ a˜o na˜ o de ve ri a co m pr om et er a es ca la bi lid ad e do al go ri tm o. • Id ea lm en te a ag lo m er ac¸ a˜o to rn a a gr an ul ar id ad e ta˜ o gr os sa qu an to p os s´ı ve l; m as de sd e qu e: • na˜ o af et e a es ca la bi lid ad e • ha ja ho m og en ei da de en tr e as ta re fa s • m an te nh a ta˜ o si m pl es qu an to p os s´ı ve l o al go ri tm o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 1 M a p ea m en to G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 2 M a p ea m en to • D iz re sp ei to a` es tr at e´g ia de di st ri bu ic¸ a˜o de ta re fa s en tr e os pr o ce ss ad or es di sp on´ ıv ei s. • O bj et iv a re du zi r o te m p o to ta l de ex ec uc¸ a˜o : m in im iz ac¸ a˜o da o ci os id ad e e co m un ic ac¸ a˜o . • ta re fa s co nc or re nt es en tr e si sa˜ o m ap ea da s em di fe re nt es pr o ce ss ad or es • ta re fa s qu e se co m un ic am fr eq ue nt em en te fo rm am vi zi nh an c¸a (fi si ca m en te ) • T am be´ m re sp on sa´ ve l p or ba la nc ea m en to de ca rg a: m ax im iz ac¸ a˜o da o cu pa c¸a˜ o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 3 M a p ea m en to M a p ea m en to in tr a e in te r- p ro ce ss a d o re s G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 4 M a p ea m en to M o d el o d e A rq u it et u ra O p en C L G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 5 C o m p u ta c¸a˜ o P ar a le la H et er o g eˆn ea In tr o d u c¸a˜ o a` C o m p u ta c¸a˜ o P ar a le la - IV D o u g la s A d r ia n o A u g u st o d o u g l a s @ l n c c . b r L a b o ra to´ ri o N a ci o n a l d e C o m p u ta c¸a˜ o C ie n t´ı fi ca G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 A lg o ri tm o s P ar a le lo s F u n d a m en tais C o m u n ic a c¸a˜ o C o le ti va G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 In tr o d u c¸a˜ o • F re qu en te m en te pr o ce ss os pr ec is am se co m un ic ar co m gr up os de pr o ce ss os : di st ri bu ic¸ a˜o de da do s, co le ta , un ifi ca c¸a˜ o de re su lt ad os pa rc ia is , et c. • M ui ta s ve ze s ta is op er ac¸ o˜e s co le ti va s se gu em um pa dr a˜o b em de fi ni do em te m p o e es pa c¸o . • A efi ci eˆn ci a de st as p o de se r cr uc ia l em um al go ri tm o pa ra le lo . G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 In tr o d u c¸a˜ o P a d ro˜ es b a´ si co s d e co m u n ic a c¸a˜ o : • B ro ad ca st um -p ar a- to do s (o ne -t o- al l br oa dc as t) • R ed uc¸ a˜o to do s- pa ra -u m (a ll- to -o ne re du ct io n ) • B ro ad ca st to do s- pa ra -t o do s (a ll- to -a ll br oa dc as t) • R ed uc¸ a˜o to do s- pa ra -t o do s (a ll- to -a ll re du ct io n ) • R ed uc¸ a˜o pa ra -t o do s (a ll- re du ce ) • S ca n (p re fi x- su m ) • S ca tt er • G at he r G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 4 T o p o lo g ia s G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 5 C u st o d e C o m u n ic a c¸a˜ o M en sa ge ns p on to -a -p on to co ns om em t s + t w m un id ad es de te m p o, on de : • t s e´ a la teˆ nc ia • t w e´ o te m p o ga st o pa ra se tr an sf er ir um a pa la vr a de m a´q ui na (w or d ): t w e´ in ve rs am en te pr op or ci on al a` la rg ur a de ba nd a • m e´ o ta m an ho da m en sa ge m da do em nu´ m er o de pa la vr as G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 6 B ro a d ca st u m -p ar a -t o d o s G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 7 B ro a d ca st u m -p ar a -t o d o s In ic ia lm en te : • A m en sa ge m M es ta´ al o ca da no pr o ce ss o ra iz F in a lm en te : • A m en sa ge m M es ta´ al o ca da em to do s os pr o ce ss os G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 8 B ro a d ca st u m -p ar a -t o d o s: A n el E sq u em a : • U sa a te´ cn ic a ch am ad a d u p lic a c¸a˜ o re cu rs iv a (r ec ur si ve do ub lin g ) • O nu´ m er o de pr o ce ss os at iv os do br a a ca da pa ss o • O s de st in at a´r io s sa˜ o cu id ad os am en te es co lh id os G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 9 B ro a d ca st u m -p ar a -t o d o s: A n el G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 0 B ro a d ca st u m -p ar a -t o d o s: M a lh a E sq u em a : 1. E xe cu ta -s e o al go ri tm o do A ne l na lin ha do pr o ce ss o ra iz ; 2. R ep et e- se o pr o ce di m en to na s co lu na s (e m pa ra le lo ). G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 1 B ro a d ca st u m -p ar a -t o d o s: H ip er cu b o E sq u em a : • G en er al iz ac¸ a˜o do al go ri tm o da M al ha pa ra d di m en so˜ es (d ≥ 3) . G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 2 C o n si d er a c¸o˜ es E se p fo r di fe re nt e de 2d ? • N or m al m en te fa z- se : 1. p′ = 2⌈ lo g 2 p ⌉ 2. pr es um e- se qu e ex is ta m p′ pr o ce ss os 3. ig no ra -s e as co m un ic ac¸ o˜e s pa ra de st in at a´r io s ≥ p G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 3 A n a´ lis e d e C o m p le xi d a d e • N u´m er o de pa ss os : d = lo g 2 p • T em p o p or pa ss o: t s + t w m • T em p o to ta l: (t s + t w m ) lo g 2 p O bs .: O br oa dc as t pa ra p2 pr o ce ss os e´ ap en as du as ve ze s m ai s lo ng o do qu e o br oa dc as t pa ra p pr o ce ss os : lo g 2 p2 = 2 lo g 2 p = 2d G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 4 R ed u c¸a˜ o to d o s- p ar a -u m G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 5 R ed u c¸a˜ o to d o s- p ar a -u m O nd e ⊕ e´ um op er ad or as so ci at iv o. In ic ia lm en te : • p di fe re nt es m en sa ge ns M k , co m k = 0, 1, .. ., p − 1 • A m en sa ge m M k es ta´ al o ca da no pr o ce ss o k F in a lm en te : • A re du c¸a˜ o M := M 0 ⊕ M 1 ⊕ .. .⊕ M p −1 al o ca da no pr o ce ss o ra iz G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 6 O p er a d o re s d e R ed u c¸a˜ o P re ss u p o st o : pr op ri ed ad e as so ci at iv a (x ⊕ y ) ⊕ z = x ⊕ (y ⊕ z) = x ⊕ y ⊕ z E xe m p lo s: • so m a, m ul ti pl ic ac¸ a˜o , m´ ın im o/ m a´x im o C o n tr a ex em p lo s: • su bt ra c¸a˜ o, di vi sa˜ o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 7 O p er a d o re s d e R ed u c¸a˜ o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 8 R ed u c¸a˜ o to d o s- p ar a -u m • D in aˆm ic a an a´l og a ao al go ri tm o bro a d ca st u m -p ar a -t o d o s • T em p o an a´l og o, ex ce to p el o te m p o ex tr a pa ra os x ⊕ y • O rd em in ve rs a de co m un ic ac¸ o˜e s • D ir ec¸ a˜o in ve rs a de co m un ic ac¸ o˜e s • C om bi na a m en sa ge m re ce bi da co m a lo ca l at ra ve´ s de ⊕ G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 9 R ed u c¸a˜ o to d o s- p ar a -u m E sq u em a : G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 0 R ed u c¸a˜ o to d o s- p ar a -u m G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 1 E xe m p lo B ro a d ca st um -p ar a- to do s e re d u c¸a˜ o to do s- pa ra -u m M ul ti pl ic ac¸ a˜o de um a m at ri z 4 × 4 p or um ve to r 4 × 1 G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 2 B ro a d ca st to d o s- p ar a -t o d o s G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 3 B ro a d ca st to d o s- p ar a -t o d o s In ic ia lm en te : • p di fe re nt es m en sa ge ns M k , co m k = 0, 1, .. ., p − 1 • A m en sa ge m M k es ta´ al o ca da no pr o ce ss o k F in a lm en te : • A s m en sa ge ns M k , co m k = 0, 1, .. ., p − 1, es ta˜ o al o ca da s em to do s os pr o ce ss os G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 4 B ro a d ca st to d o s- p ar a -t o d o s: A n el E sq u em a : G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 5 A n a´ lis e d e C o m p le xi d a d e: A n el • N u´m er o de pa ss os : p − 1 • T em p o p or pa ss o: t s + t w m • T em p o to ta l: (t s + t w m )( p − 1) G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 6 B ro a d ca st to d o s- p ar a -t o d o s: M a lh a E sq u em a : B as ei a- se no al go ri tm o pa ra a to p ol og ia A ne l: 1. A pl ic a- se o al go ri tm o A ne l em to d a s a s lin h a s em pa ra le lo 2. A pl ic a- se o al go ri tm o A ne l em to d a s a s co lu n a s em pa ra le lo G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 7 A n a´ lis e d e C o m p le xi d a d e: M a lh a (C on si de ra nd o- se um a m al ha √ p × √ p p or si m pl ic id ad e) 1. A pl ic a- se o al go ri tm o A ne l em to d a s a s lin h a s em pa ra le lo : • N u´m er o de pa ss os : √ p − 1 • T em p o p or pa ss o: t s + t w m • T em p o to ta l: (√ p − 1) (t s + t w m ) 2. A pl ic a- se o al go ri tm o A ne l em to d a s a s co lu n a s em pa ra le lo : • N u´m er o de pa ss os : √ p − 1 • T em p o p or pa ss o: t s + t w √ p√ p√ pm • T em p o to ta l: (√ p − 1) (t s + t w √ p√ p√ pm ) • T em p o to ta l: 2( √ p − 1) t s + (p − 1) t w m G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 8 B ro a d ca st to d o s- p ar a -t o d o s: H ip er cu b o E sq u em a : T am be´ m ba se ia -s e no al go ri tm o pa ra a to p ol og ia A ne l: 1. P ar a ca da di m en sa˜ o d do hi p er cu b o, em se qu eˆn ci a: 2. A pl ic a- se em pa ra le lo o al go ri tm o A ne l na s 2d −1 ar es ta s da di m en sa˜ o at ua l G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 9 A n a´ lis e d e C o m p le xi d a d e: H ip er cu b o • N u´m er o de pa ss os : d = lo g 2 p • T em p o p or pa ss o k = 0, 1, .. ., d − 1: t s + t w 2k 2 k 2k m • T em p o to ta l: d −1 ∑ k=0(t s + t w 2k m ) = t s lo g 2 p + t w (p − 1) m G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 0 R ed u c¸a˜ o to d o s- p ar a -t o d o s G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 1 R ed u c¸a˜ o to d o s- p ar a -t o d o s O nd e ⊕ e´ um op er ad or as so ci at iv o. In ic ia lm en te : • p2 di fe re nt es m en sa ge ns M r, k , co m r, k = 0, 1, .. ., p − 1 • A m en sa ge m M r, k es ta´ al o ca da no pr o ce ss o r F in a lm en te : • A re du c¸a˜ o M r := M 0 ,r ⊕ M 1 ,r ⊕ .. .⊕ M p −1 ,r al o ca da s em ca da pr o ce ss o r G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 2 R ed u c¸a˜ o to d o s- p ar a -t o d o s • D in aˆm ic a an a´l og a ao al go ri tm o b ro a d ca st to d o s- p ar a -t o d o s • T em p o an a´l og o, ex ce to p el o te m p o ex tr a pa ra os x ⊕ y • O rd em in ve rs a de co m un ic ac¸ o˜e s • D ir ec¸ a˜o in ve rs a de co m un ic ac¸ o˜e s • C om bi na a m en sa ge m re ce bi da co m a lo ca l at ra ve´ s de ⊕ G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 3 R ed u c¸a˜ o p ar a -t o d o s G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 4 R ed u c¸a˜ o p ar a -t o d o s O nd e ⊕ e´ um op er ad or as so ci at iv o. In ic ia lm en te : • p di fe re nt es m en sa ge ns M k , co m k = 0, 1, .. ., p − 1 • A m en sa ge m M k es ta´ al o ca da no pr o ce ss o k F in a lmen te : • A re du c¸a˜ o M := M 0 ⊕ M 1 ⊕ .. .⊕ M p −1 al o ca da em to do s os pr o ce ss os G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 5 R ed u c¸a˜ o p ar a -t o d o s • D in aˆm ic a an a´l og a ao al go ri tm o b ro a d ca st to d o s- p ar a -t o d o s • C om bi na a m en sa ge m re ce bi da co m a lo ca l at ra ve´ s de ⊕ • M en or co m pl ex id ad e em te m p o, p oi s o ta m an ho da m en sa ge m na˜ o cr es ce • T em p o to ta l: (t s + t w m ) lo g 2 p G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 6 S ca n G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 7 S ca n O nd e ⊕ e´ um op er ad or as so ci at iv o. In ic ia lm en te : • p di fe re nt es m en sa ge ns M k , co m k = 0, 1, .. ., p − 1 • A m en sa ge m M k es ta´ al o ca da no pr o ce ss o k F in a lm en te : • A re du c¸a˜ o M (k ) := M 0 ⊕ M 1 ⊕ .. .⊕ M k al o ca da no pr o ce ss o k pa ra to do k G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 8 S ca n • D in aˆm ic a an a´l og a ao al go ri tm o re d u c¸a˜ o p ar a -t o d o s • T em p o an a´l og o • L o ca lm en te em ca da pr o ce ss ad or gu ar da -s e a re du c¸a˜ o pa rc ia l G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 9 S ca tt er G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 4 0 S ca tt er In ic ia lm en te : • p di fe re nt es m en sa ge ns M k , co m k = 0, 1, .. ., p − 1, al o ca da s no pr o ce ss o ra iz F in a lm en te : • A m en sa ge m M k al o ca da no pr o ce ss o k pa ra to do k G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 4 1 S ca tt er • D in aˆm ic a an a´l og a ao al go ri tm o b ro a d ca st u m -p ar a -t o d o s • M et ad e da s m en sa ge ns sa˜ o en vi ad as no pr im ei ro pa ss o; um qu ar to de la s no se gu nd o pa ss o, e as si m p or di an te • C om pu ta ci on al m en te m ai s ca ro , p oi s va´ ri as m en sa ge ns sa˜ o en vi ad as em ca da pa ss o • T em p o to ta l: t s lo g 2 p + t w (p − 1) m G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 4 2 G a th er G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 4 3 G a th er In ic ia lm en te : • p di fe re nt es m en sa ge ns M k , co m k = 0, 1, .. ., p − 1 • A m en sa ge m M k es ta´ al o ca da no pr o ce ss o k F in a lm en te : • A s p m en sa ge ns M k es ta˜ o al o ca da s no pr o ce ss o ra iz G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 4 4 G a th er • D in aˆm ic a an a´l og a ao al go ri tm o sc a tt er • T em p o an a´l og o • O rd em in ve rs a de co m un ic ac¸ o˜e s • D ir ec¸ a˜o in ve rs a de co m un ic ac¸ o˜e s G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 4 5 C o m p u ta c¸a˜ o P ar a le la H et er o g eˆn ea A rq u it et u ra e O rg a n iz a c¸a˜ o D o u g la s A d r ia n o A u g u st o d o u g l a s @ l n c c . b r L a b o ra to´ ri o N a ci o n a l d e C o m p u ta c¸a˜ o C ie n t´ı fi ca G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 In tr o d u c¸a˜ o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 2 In tr o d u c¸a˜ o A rq u it et u ra d e u m co m p u ta d o r • D iz re sp ei to ao s at ri bu to s vi s´ı ve is ao pr og ra m ad or : - co nj un to de in st ru c¸o˜ es , nu´ m er o de bi ts us ad o pa ra re pr es en ta r ti p os de da do s, et c. O rg a n iz a c¸a˜ o d e u m co m p u ta d o r • R ef er e- se a`s un id ad es op er ac io na is e su as in te rc on ex o˜e s qu e im pl em en ta m as es p ec ifi ca c¸o˜ es de um a ar qu it et ur a: - de ta lh es de ha rd w ar e tr an sp ar en te ao pr og ra m ad or , co m o as in te rf ac es de co ne xa˜ o, te cn ol og ia de m em o´r ia , et c. G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 3 In tr o d u c¸a˜ o A ar qu it et ur a e´ m en os vo la´ ti l: • A fa m´ ıli a de pr o ce ss ad or es In te l x8 6 co m pa rt ilh a a m es m a ar qu it et ur a ba´ si ca • Id em pa ra a fa m´ ıli a IB M S ys te m /3 90 E nq ua nt o qu e a or ga ni za c¸a˜ o di fe re a ca da ve rs a˜o de ha rd w ar e. G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 4 In tr o d u c¸a˜ o P ro p o´ si to d es te m o´ d u lo : • E st ud ar os as p ec to s de ar qu it et ur a e or ga ni za c¸a˜ o de um co m pu ta do r qu e in fl ue nc ia m a pr og ra m ac¸ a˜o /c om pu ta c¸a˜ o em um si st em a pa ra le lo he te ro geˆ ne o. O b je ti vo : • P ro gr am ar efi ci en te m en te em fu nc¸ a˜o da ar qu it et ur a: - id en ti fi ca c¸a˜ o da ca rg a de tr ab al ho m ai s ap ro pr ia da - ot im iz ac¸ a˜o de de se m p en ho do al go ri tm o da da a ar qu it et ur a G B -5 0 0 -2 0 2 – L N C C – 4◦ / 2 0 1 1 – p . 5 L ei d e M o o re “O nu´ m er o de tr an s´ı st or es qu e p o de m se r fa ci lm en te co lo ca do s em um C I do br a ap ro xi m ad am en te em do is an os ” Im pl ic ac¸ o˜e s re la ci on ad as a` le i de M o or e: • C us to de pr o du c¸a˜ o p or de se m p en ho ca i dr as ti ca m en te • C om m ai or de ns id ad e, m en or o ca m in ho el e´t ri co , p or ta nt o m ai or a ve lo ci da de de op er ac¸ a˜o • D im in ui c¸a˜ o do ta m an ho do ch ip • R ed uc¸ a˜o do co ns um o de en er gi a G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 6 L ei d e M o o re G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 7 L ei d e M o o re In fe liz m en te : • O pr o ce ss o de pr o du c¸a˜ o ap ro xi m a- se do s lim it es f´ı si co s da te cn ol og ia : - lim it es at oˆm ic os /v el o ci da de da lu z - qu es to˜ es te´ rm ic as S o lu c¸a˜ o : • E m pr eg o de va´ ri os na˜ o- ta˜ o- de ns os ch ip s in de p en de nt es co ne ct ad os em um u´n ic o pr o ce ss ad or : ar qu it et ur a pa ra le la de va´ ri o s n u´ cl eo s: - m ul ti -c or e - m an y- co re G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 8 A rq u it et u ra C P U In te l C o re i7 -9 8 0 X : 1 6 0 G F L O P /s P ro ce ss o D im en sa˜ o T ra n s´ı st or es N u´ cl eo s F re q u eˆn ci a C o n su m o 3 2 n m 2 4 8 m m 2 1 ,1 7 B il h o˜ es 6 f´ı si co s e 6 lo´ g ic o s 3 ,3 3 G H z 1 3 0 W G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 9 A rq u it et u ra G P U N vi d ia G ef o rc e G T X -5 8 0 : 1 5 8 1 G F L O P /s P ro ce ss o D im en sa˜ o T ra n s´ı st or es N u´ cl eo s F re q u eˆn ci a C o n su m o 4 0 n m 5 2 0 m m 2 3 B il h o˜ es 5 1 2 1 5 4 4 M H z 2 4 4 W G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 0 A rq u it et u ra G P U N vi d ia G ef o rc e G T X -5 8 0 : 1 5 8 1 G F L O P /s P ro ce ss o D im en sa˜ o T ra n s´ı st or es N u´ cl eo s F re q u eˆn ci a C o n su m o 4 0 n m 5 2 0 m m 2 3 B il h o˜ es 5 1 2 1 5 4 4 M H z 2 4 4 W G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 1 A rq u it et u ra G P U A M D R a d eo n 6 9 7 0 : 2 7 0 3 G F L O P /s P ro ce ss o D im en sa˜ o T ra n s´ı st or es N u´ cl eo s F re q u eˆn ci a C o n su m o 4 0 n m 3 8 9 m m 2 2 ,6 4 B il h o˜ es 1 5 3 6 8 8 0 M H z 2 5 0 W G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 2 A rq u it et u ra G P U A M D R a d eo n 6 9 7 0 : 2 7 0 3 G F L O P /s P ro ce ss o D im en sa˜ o T ra n s´ı st or es N u´ cl eo s F re q u eˆn ci a C o n su m o 4 0 n m 3 8 9 m m 2 2 ,6 4 B il h o˜ es 1 5 3 6 8 8 0 M H z 2 5 0 W G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 3 C P U ve rs u s G P U G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 4 D if er en c¸a s F u n d a m en ta is : C P U x G P U A rq u it et u ra : • C P U : M IM D (M ul ti pl e In st ru ct io n M ul ti pl e D at a) - pa ra le lis m o de ta re fa s e da do s - ta m be´ m p os su i pa ra le lis m o vi a in st ru c¸o˜ es es te nd id as S IM D - m ai s fl ex´ ıv el , pr op o´s it o ge ra l • G P U : S IM D (S in gl e In st ru ct io n M ul ti pl e D at a) - pa ra le lis m o de da do s - m ai s re st ri ta (e sp ec ia liz ad a) , m as co nt in ua m en te ad qu ir e ca ra ct er´ ıs ti ca s de pr op o´s it o ge ra l G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 5 D if er en c¸a s F u n d a m en ta is : C P U x G P U P ro g ra m a c¸a˜ o : • C P U : fa ci lm en te pr og ra m a´v el - co nc ei tu al m en te m ai s si m pl es , fo co es se nc ia lm en te se qu en ci al - m ai or di sp on ib ili da de e m at ur id ad e de lin gu ag en s e fe rr am en ta s de su p or te (e x: de pu ra c¸a˜ o) • G P U : pr og ra m ac¸ a˜o m en os di re ta - fo co no pa ra le lis m o e es ca la bi lid ad e - cu st o de en ge nh ar ia de so ft w ar e (i m pl em en ta c¸a˜ o, de pu ra c¸a˜ o, m an ut en c¸a˜ o, et c. ) - m ai s se ns´ ıv el ao pr oj et o do al go ri tm o. .. .. .o u, p or ou tr o la do , m ai or m ar ge m de ot im iz ac¸ a˜o G B -5 0 0 -2 0 2 – L N C C – 4 ◦ / 2 0 1 1 – p . 1 6 D if er en c¸a s F u n d a m en ta is : C P U x G P U C ar g a d e tr a b a lh o : • C P U : pr oj et ad a pa ra re d u zi r a la teˆ n ci a na ex ec uc¸ a˜o de um a ta re fa : - ba ix a la teˆ nc ia na ex ec uc¸ a˜o de in st ru c¸o˜ es e ac es so a` m em o´r ia - us o in te ns o de m em o´r ia s ca ch e e ou tr as te cn ol og ia s • G P U : pr oj et ad a pa ra a u m en ta r a va za˜ o (t hr ou gh pu t) : “c ad a pi xe l p o de de m or ar qu an to te
Compartilhar