I.ELEMENTEDINTEORIAJOCURILORNON-COOPERATISTE…5 [622696]

2Cuprins:
Introducere……………………………………………………………………………………………………………………………3
I.ELEMENTEDINTEORIAJOCURILORNON-COOPERATISTE………………………………………..5
1.1.Elementedinteoriajocurilorstatice……………………………………………………………………………5
1.2.Elementedinteoriajocurilordinamice……………………………………………………………………….7
II.ELEMENTEDINTEORIAJOCURILORDINAMICEININFORMAȚIEINCOMPLETĂ…….13
2.1.Jocuriininformatieincompleta…………………………………………………………………………………13
2.2JocuriBayesiene…………………………………………………………………………………………………….15
III.UTILIZAREACLUSTERULUIUSMLADETERMINAREASOLUȚIILORJOCURILOR
BAYESIENEDINAMICE……………………………………………………………………………………………………24
3.1.ElementedebazadinprogramareMPI(MessagePassingInterface)……………………………….24
3.2.Algoritmulinducțieirecursive(backwardinduction)……………………………………………………38
Concluziișirecomandări:……………………………………………………………………………………………………..50
Bibliografie:………………………………………………………………………………………………………………………..51
Anexă…………………………………………………………………………………………………………………………………52

3Introducere
Înlumeaafacerilordeazicompetițiajoacăunrolfoarteimportant.Strategiileadoptate
deindivizisauorganizațiipotafectaprofundcursulșirezultatulpropriilornoastredecizii.
Înlumeaafacerilordeazinupotfiluatedeciziifărăconsiderarearăspunsuluicelorlalte
firmedepepiață.Teoriajoculuioferăoposibilitatedeanalizăaimpactuluideciziilor
celorlalțiasuprapropriilordeciziișirezultateleaferente.
UnJocesteunconcurscareimplicăparticipareaadoisaumaimulțiparticipanți,numiți
jucători,fiecaredintreeidorindsăcâștige.Teoriajoculuinearatăcumsăalegemstrategii
optimeîntr-unconflict.PioneriiacesteiteoriipotficonsiderațiJohnvonNeumannși
OscarMorgensternprinlucrarea”Theoryofgamesandeconomicbehavior”.Inițialteoria
joculuiafostutilizatăînplanificareastrategiilorînceldealdoilearăzboimondial.De
atunciTeoriaJoculuiafostfolosităînnumeroasesituațiiimplicândnegocierilesindicale,
deafacerisaudealtănatură..
TeoriiJoculuisepoateaplicaaproapeoricăruifenomensocial.Astfelîncâtseașteptădela
aceastăștiințarezolvareatuturorsituațiilorîncareoameniirealizeazăcărezultatulacțiunilor
lordepindenunumaideacestea,darșideacțiunilecelorlalțiparticipanțilaaceainteracțiune.
Deșinuasatisfăcuttoateacesteașteptări,teoriajocurilorși-agăsitnumeroaseaplicațiimai
alesîndomeniuleconomiei.Pentruaînțelegeunjocoarecareestenecesarămaiîntâi
cunoaștereareguliloracestuia,deoareceastfelsepoateaflacareacțiunisuntpermise(posibile)
launanumitmoment.Apoiestenecesarasecunoaștecumalegjucătoriioacțiunedin
mulțimeaacțiunilorposibile.
Încontinuarevomamintioclasificareajocurilorînraportcudiversecriterii:
a.înraportcumodulîncarecomunicajucătoriîntreeiavem:
jocuricooperative,suntacelejocuriîncarejucătoriicomunicăliberîntreeiînainte
deluareadeciziilorșipotfacepromisiuniînaintedealegereastrategiilor;
jocurinecooperative,suntjocurileîncarejucătoriinucomunicăîntreeiînaintede
luareadeciziilor.
b.înraportcudesfășurareaîntimpajocurilor:
jocuristatice,esteaceljocîncaredeciziilejucătorilorseiausimultan,dupăcare
joculiasfârșit;
jocuridinamice,esteaceljocîncaredeciziilejucătorilorsuntsecvențiale,adică
evolueazăîntimp.
c.înraportcunaturainformației:
jocuriîninformațiecompletă,esteaceljocîncaretoțijucătoricunoscnumărul

4celorlalțijucători,strategiilefiecăruia,funcțiiledecâștigalefiecăruia,precumșiregulile
jocului;
jocuriîninformațieincompletă,estejoculîncarecelpuținunuldintrejucătorinu
cunoașteunasaumaimultefuncțiidecâștigalecelorlalțijucători,restulelementelor
(numărulcelorlalțijucători,strategiilefiecăruiașiregulilejocului)fiindcunoscute.
d.încazuljocurilordinamice,înraportcutipulinformației:
jocuriîninformațieperfectă,estejoculdinamicîncarefiecaredintrejucători
cunoașteregulile,număruljucătorilor,strategiileacestora,precumșievoluțiaîntimpa
jocului(istoriajocului);
jocuriîninformațieimperfectă,estejoculdinamicîncaremăcarunuldintre
jucătorinucunoașteistoriajocului,cunoscândcelelalteelemente.
e.înraportcustructuracâștigurilor:
jocuridesumănulă,esteaceljocîncaresumacâștigurilorestezero;
jocuridesumănenulă,estejoculîncaresumacâștigurilorestediferitadezero.
f.înraportcunumăruldejucători:
jocuricudoijucători;
jocurimultipersoană;
jocuricontranaturii.

5I.ELEMENTEDINTEORIAJOCURILORNON-COOPERATISTE
1.1.Elementedinteoriajocurilorstatice
Descriereaoricăruijocconținespecificareaurmătoarelorcomponentealejocului:
1.determinarea(descrierea,enumerarea)participanțilorlaprocesuldecizional;
2.determinareamulțimilordeparametricaresuntgestionațidecătrefiecare
participantlaprocesuldecizional;
3.determinareaacelorreguli,cuajutorulcărorasevaface(decătrefiecare
participant)alegereaparametrilordinpunctul2.
4.determinareaacelorcriterii,cuajutorulcărorasevaestimaeficacitateaparametrilor
determinațiconformpunctului3,adicădeterminareaprincipiilordeoptimalitatepentrufiecare
participantdeterminatînpunctul1.
Defini¸tia1.1.1Prinjocnoncooperatistvomsubințelegeurmatorulcortej
   IiiIiiHXI,, (1.1.1)
undeIesteomul¸timefinit˘a,elementelec˘arorasevornumijuc˘atori(nI,…,2,1).iX,Ii-
mul¸timiarbitrarecarenuseintersecteaz˘adou˘acˆatedou˘a,elementelec˘arorasevornumistrategii(le
vomnotaix).S¸iruldevaloriIiix,adic˘aelementedinprodusulcartezian


IiiXX (1.1.2)
sevanumistarea(situa¸tia,rezultatul)jocului.Func¸tiam˘arginit˘a
RXHi: (sau RXH
Iii i
: ) (1.1.3)
sevanumifunc¸tie-scop(decˆa¸stig)ajuc˘atoruluii,valoarea ),…,(1n ixxH sevanumicˆa¸stigul
juc˘atoruluiipentrustarea{x1,…,xn}.
Defini¸tiajocurilordetipul(1.1.1)sevanumi”defini¸tieˆınform˘anormal˘aajocurilor”.Pentru
definirea”real˘a”ajoculuitrebuies˘adetermin˘am(s˘afix˘am)modulˆıncarefiecarejuc˘atoralege
strategiaxi(descriereapunctului3¸siscopulfiec˘aruijuc˘ator(adic˘adeterminareaprincipiuluide
optimalitatealjuc˘atorilor).
Defini¸tia1.1.2Srategiaesteofunc¸tiepemul¸timeaparametrilorgestiona¸tidejuc˘atori,formac˘areia
depindedeniveluldeinformareajuc˘atorilor.Deexemplu,strategiajuc˘atoruluiipoatefi

6urm˘atoareaaplica¸tie
i
xnj ii Xxxxxx
i~),…,,….,(~
1  

(1.1.4)
unde
ix-uncortejdevalorimxx,…,1ˆıncarenusecon¸tinevaloareaxi,X-mul¸timeatuturor
aplica¸tiilor:iiXX,unden j i XXXX ……1 ,ij(adic˘aˆınacestproduscarteziannu
figureaz˘aXi).Deexemplu:.1 2 211 …:),…,(~XXXxxxxn n   .
Astfel,vomconsiderajoculˆınform˘anormal˘a(1.1.1)¸sivompresupunec˘a:
a)Juc˘atoriiac¸tioneaz˘aizolat,adic˘afiecarejuc˘atorˆı¸sialegestrategiaindependent,f˘ar˘aa¸tine
contdestrategiilecelorlal¸tijuc˘atori.
b)Nuarelocniciunschimbdeinforma¸tiiˆıntrejuc˘atori.Adic˘a,strategiilexiale
juc˘atoruluiinupotfifunc¸tiidealegerileconcretealestrategiilorjalecelorlal¸tijuc˘atori.
c)Vompresupunec˘afiecarejuc˘atoriˆı¸sicunoa¸steXi¸siHi¸sic˘aelpoates˘anudispun˘ade
informa¸tiadespreXj¸siHj,ji.
Acesteasuntprincipalele”componente”alejoculuinoncooperatist.
Clasedejocurinoncooperatiste:
Defini¸tia1.1.3(Ceamaisimpl˘aclas˘adejocurinoncooperatiste).Joculnoncooperatist(1.1.1)se
nume¸stefinitdac˘asuntfinitemul¸timileXi,pentrui1,…,n.Joculnoncooperatistfinitsenume¸ste
bimatricealdac˘amul¸timeaIconst˘anumaidindoijuc˘atori,adic˘a2,1I.
Defini¸tia1.1.4Joculnoncooperatist(1.1.1)senume¸stejoccusum˘aconstant˘a(fix˘a),dac˘apentru
oricesitua¸tie(stare) XxxIii}{vomobține:
cxH
Iii
)( (1.1.5)
Dac˘a0c,atuncijoculdindefini¸tia1.1.4senume¸stejoccusum˘anul˘a.Joculnoncooperatistcu
sum˘anul˘aˆıncareparticip˘anumaidoijuc˘atori,adic˘a2,1I senume¸stejocantagonist.Astfel,
ˆınoricejocantagonistcˆa¸stigulunuiadintrejuc˘atoriestenumericegalcupierdereaceluilalt:
),(),(212 211 xxHxxH  .Dinacesteconsiderente,ˆınjocurileantagonisteseutilizeaz˘aosingur˘a
func¸tie-scop, ),(21xxH ,caresenume¸stefunc¸tiadecˆa¸stigajocului¸sidetermin˘anumeric
cˆa¸stiguljuc˘atorului1¸sipierdereajuc˘atorului2.
Defini¸tia1.1.5Joculantagonistbimatricealsenume¸stejocmatriceal.
Astfel,joculmatricealsedescrieprintr-osingur˘amatriceA-matriceadecˆa¸stiga
jocului.
Remarca1.1.1Nuexist˘auncriteriudeoptimalitatealjuc˘atorilorcares˘aasigure”celmaibun

7rezultat”.Iˆndependen¸t˘aderegulilejocului¸siinforma¸tiaposedat˘asealegeacelprincipiude
optimalitate,careasigur˘a”celmaibunrezultataljocului”.
Fiecarejuc˘ator,cunoscˆandnumaiformanormal˘aajocului,poatedeterminadesinest˘at˘ator
strategiasa(saucˆatevastrategii)¸tinˆandcontdeprincipiiledeoptimalitatemen¸tionate.
Defini¸tia1.1.6Vomspunec˘asitua¸tia(exodul)IiiIiixixxx   }{)}(,{ injocul
  IiHXIii,,, esteNashdeechilibru(situațieNE)ajocului,dac˘a
)).(,())(,(,, ixxHixyHXyIiii iiii   (1.1.6)
Deci,dac˘a ),….,(* *
1*
nxxx estesitua¸tieNE,atuncipentrudeterminareaeitrebuies˘arezolv˘am
sistemuldeecua¸tii:
)).(,(max)(,* *ixxHxHIiiiXxi
ii  (1.1.7)
Existen¸tasitua¸tiilordeechilibruˆınjocurilenoncooperatistedenot˘a¸sifaptulc˘aniciunjuc˘ator
ˆınmodunilateralnupoatem˘aricˆa¸stiguls˘auˆınjoc.Pentruamodificavaloareacˆa¸stigului,
trebuies˘a”ie¸sim”dincadrulcondi¸tiilorjocurilornoncooperatiste.
Vomeviden¸tiacˆatevaaspectenegativealesitua¸tiilorNE:
a)nuˆıntotdeaunaeleexist˘a,decipoatefiNE(Γ)=∅;
b)ˆıncazulcˆandsitua¸tiaNEnuesteunic˘a,nuexist˘aargument˘arilogicepentruaalege
unadintreele;
c)potexistaastfeldesitua¸tiiˆınjocul  iiHXI,, ˆıncarevalorilecˆa¸stigurilor
pentrufiecarejuc˘atorsuntmaimaridecˆatˆınsitua¸tiaNE.
Punctula)poatefisolu¸tionatpozitivprinintroducereastrategiilormixte.
Teorema1.1.1(Nash)(CondițiilesuficientepentruexistențasituațiilorNE).Dac˘apentrujocurileΓde
tipul   IiHXIii,,, severific˘aurm˘atoarelecondiții:
1)PentruoriceIimulțimiledestrategiiposibileiXsuntsubmulțimiconvexeși
compactealeunorspațiitopologicevectoriale.
2)PentruoriceIifunc¸tiileHi(x)suntcontinuepeX¸sipentruorice )()(iXix
func¸tiile)(,ixxHiisuntconcavedup˘aiiXx,atuncimul¸timeaNE(Γ)asitua¸tiilordeechilibru
Nashestenevid˘a¸sicompact˘a.
1.2.Elementedinteoriajocurilordinamice

8Jocuridinamiceˆıninforma¸tiecomplet˘a¸siperfect˘a.
Pentrujocuriledinamicesuntspecificatereguliledinpunctul3,conformcărorajucătoriivor
facepropriilealegeri.Unjocdinamicesteunjocîncarealegerilejucătorilorsuntefectuateîn
diversemomentedetimp.Deregulă,joculdinamicsedesfășoarăîncătevaetape,șijucătorii
potsăfacăcîtevaalegeriîndiferitemomentedetimppeparcursulderulăriijocului,pînăla
indeplinireacondițieideterminareajocului.Jocurileîninformațiecompletăsuntcaracterizate
prinfaptulcăjucătoriiposedăoinformațiecompletădespredescriereajocului,îndeosebi
desprepreferințelejucătorilor,desprefuncțiiledeutilitateșimulțimiledealternative.
Definiția1.2.1Vomnumi”istorieajocului”lamomentul1t(saulaetapa1t)secvențade
decizii(alternative)pecareauluat-ojucătoriiînceletetapeanterioarealejocului.
Definiția1.2.2Vomnumijocsubformăextinsăjoculdinamicîncaresecunosc:
a)mulțimeajucătorilor;
b)mulțimeadealternativealefiecăruijucător;
c)ordineaîncarejucătoriiiaudeciziile(alegalternativele);
d)funcțiiledecaștigalejucătorilor.
Reprezentareagraficăajucătorilorsubformaextinsăsefacesubformaunuigrafdetiparbore.
Înacestgrafvomaveaurmătoareleelemente:
nodurilegrafuluisuntmomentelelacarejucătoriialegostrategieposibilă;
arcelegrafuluireprezintăacțiunilealesealejucătorilor;
nodulinițialreprezintămomentuldeînceputaljocului;
nodurilefinaleindicăsfârșituljoculuișiîndreptullorsuntspecificatecâștigurile
jucătorilor.
Deexemplu,reprezentândsubformăextinsă”joculgrenadei”,ceconstăîn:
unindividcareareînmânăogrenadăîispuneunuialtindivid:dacănu-midai1milionde$,
voidetonagrenadașivommuriîmpreună”.Înacestecondițiicelălaltjucătorpoate,fiesă-i
deabanii,fiesănu-idea,riscândcacelălăltsădetonezegrenada.Înacestjocvedemcăexistă
treimomenteîncaresefacalegerilejucătorilor,șianume:amenințareaprimuluijucător,apoi
deciziaceluide-aldoileade”adabanii”saude”anudabanii”și,însfârșit,deciziaceluicu
grenada:de”aodetona”sau”anuodetona”obținemurmătorularbore:

9
Fig.1.2.1
Aicialegerile(alternativele)jucătorilorauurmătoareasemnificație:”P”semnificăfaptulcă
jucătorul2plătește,”NP”semnificăfaptulcăjucătorul2nuplătește,”D”semnificăfaptulcă
jucătorul1detoneazăgrenada,”ND”semnificăfaptulcăjucătorul1nudetoneazăgrenada.
Remarca!Vompresupunecăgrafulcedescrieformaextinsăajoculuinuconținecicluriși
dubleprecedențe;cualtecuvinte,sepoatedefiniorelațiedeordineparțialăpeacest
graf:”yx”,careînseamnă”nodulxesteînainteanoduluiy”.
Suntcazuriîncarestrategiileformeiextinsealeunuijocdinamicpotsăcreezeanumiteconfuzii.
Exemplul1.2.1ÎnjoculprezentatînFigura1.2.2pentrujucătorul1poateapăreaconfuzieîntre
alegerilesaleînanumitenodurișistrategiilelui.
Fig.1.2.2.Joccustrategiinerealizabile.
Rezolvare.Strategiaesteocombinațiedealegerialeunuijucător,careconduclarezultatul
final(într-unnodfinal).Spreexemplu,pentrujucătorul2strategiilevorcorespundealegerilor
{l,r}dincauzacăexisăunsingurnodîncarejucătorul2facealegerea.Pentrujucătorul1însă
mulțimeadestrategiinucoincidecuceaaalegerilor(alternativelor)sale.Mulțimeadealegeri
(alternative)pentrujucătorul1este{L,R,L`,R`},iarmuțimeadestrategiialesaleeste{L,LL`,
LR`,RL`,RR`},adicăacelecombinațiidealegeri(alternative)alesalecareconduclaunnod
final.Aicitrebuiederemarcatfaptulcădouădintrestrategiilesalenusuntrealizabilepentru
niciuncaz;acestestrategiisuntLL`șiLR`.AceastaseîntâmplădincauzacăalegereaLnu

10conducelacreareacondițiilordeaajungeînaltnodpentrujucătorul1,adicăînnodulîncare
jucătorul1săfacăunadintrealegerileL`,R`.
UnsetdestrategiiAaa, senumeștesituație.PentrufiecareXx,pentrusituația
datăµpoatefideterminatăprobabilitateap(x|µ)detrecereînpozițiax.Înacestcaz
probabilitateap(x0|µ)=1semnificăfaptulcăjocultottimpulîncepedinpozițiax0.
Încazgeneralprobabilitateadeanimeriînpozițiax,careestenemijlociturmătoareadupă
poziția ,,)(),( AaXxxa ,sedeterminădupăformula:
)),(|()|)(()|(  xxpxpxp unde:
 
.//,0,))((/,1)),(|(
contrarcazinxx dacăxxpa
Dacăînsă0)(Xx ,adicăestepoziția”întâmplării”,atunci)(| ),(| xxpxxp  este
datădecondițiilejocului.PentrufiecarejucătorAaestedeterminatăvaloareamediea
câștiguluixuxpxuEua a a     | |)( ,pentruoricesituațieµ.
Definiția1.2.3Vomnumijocîninformațieperfectăaceljocîncaretoțijucătoriiștiula
oricemomenttcedeciziis-auluatlaetapaanterioară(lamomentult−1).
Pentrujocuriledinamiceîninformațiecompletășiperfectătoțijucătoriicunoscistoriajocului.
Astfel,fraza”informațieperfectă”reflectăfaptulcăjucătoriicunoscceacțiuni(alternative)au
fostalesedecătretoțiparteneriilaetapeleprecedenteetapeidealegere.
Definiția1.2.4Vomnumijoccumemorieperfectă(perfectrecall)aceljocîncaretoțijucătorii
știuistoriajoculuidelamomentul0panălamomentult.
Multesituațiiconflictualerealeauuncaracterdedurată.Participanțiilaacesteconflicte
acționeazăfrecventținandcontdeinformațiadespreevaluareaanterioarăaconflictului.Pentru
modelelecorespunzătoare,dincauzanumăruluimaredestrategiiposibile,teoremelecomune
despreexistențasoluțieipentrujocurileînformănormalănunepermitsăgăsim
comportamentuloptimal,saucelpuținsă-lconcretizăm.
Pentrusoluționareajocurilordinamicecuunnumărfinitdejucători,deseoriestecomodde
utilizatprezentareapoziționalăajocului.Ceamaisimplăclasădejocuripoziționaleo
reprezintăclasajocurilorpoziționalecuunnumărfinitdepașiîninformațiecompletă.Întrun
astfeldejoc,lafiecarepasaljoculuidoarunsingurjucătorvafacemișcarea,avandinformația
completădesprestareacurentă,despretoateacțiunileîntreprinse,precum¸sidesprestructura
generalăajocului.Aceastăpresupuneredeobiceiesteconsideratăinformațiecompletă.
Exemplebinecunoscutepentruastfeldejocurireprezintăjoculdedameșijoculdeșah.Mai

11josvafiprezentatăgeneralizareaacesteimetodedesoluționarepentruoricejocîninformație
completă.
Definiția1.2.5Formapoziționalăaunuijocdinamicîninformațiecompletășiperfectă
senumeșteurmătorulcortej:
,)(,0)|(, \;,),(),,(,1, ,0 0xxxxXxXXTXAaTxxuXAG
Aaa a 
     
unde:
1.Aestemulțimeadejucători;
2.(X,σ)esteunarborefinitcuvarfulinițialx0șimulțimeavarfurilorfinaleT;
3.R={Xa,aA,X0}estedivizareamulțimiiX\Tînsubmulțimicarenuseintersecteazădouă
catedouă;
4.Xaestemulțimeapozițiilor(varfurilor),încarejucătorulAafacemișcarea,Xase
numește”mulțimeapozițiilorproprii”alejucătoruluia;
5.X0este”mulțimeapozițiilor”,încaremișcareavafiefectuatădejucătorul”Natura”,care
reprezintăfactorulaleator;
6.1:ETuaestefuncțiadecaștigajucătoruluia,E1estemulțimeanumerelorreale;
7.pentrufiecare0Xxsuntcunoscuteprobabilitățile0|'xxpdetreceredinpozițiaxîn
poziția )(1'xxși 1)|(
)(,
1,
xxp
xx.
Definiția1.2.6   AauAGaa  ,,,)(  senumeșteformanormalăajoculuipoziționalG.
Astfel,jocuriledinamicepotfireprezentatesubformănormală,prinintermediulformei
matriceale,adicăsereprezintăcajocmatricealîninformațiecompletă(jucătoriicunosc
mulțimiledestrategiișimatriceacâștigurilor)șiimperfectă(jucătoriinucunoscalegerile
partenerilor).Cumammenționatmaisus,jocuriledinamicepotfireprezentatesubformă
normală,prinintermediulformeimatriceale,dacăsevaconstruiunplancompletdeacțiuneîn
raportcustrategiilecarepotfijucatedecătreceilalțijucători.Acestplanesteconstruitex-ante,
adicăînaintedeînceputuljocului.
Exemplul1.2.2Seconsiderăurmătoruljocdescrissubformaextinsă:

12
Fig.1.2.3
Porninddelaformaextinsăvomconstruiformanormalăechivalentă:
Aceastaformănormalăseconstruieștecaunplancompletdeacțiuneposibilînraportcu
alegerilejucătorilor.(Deexemplu,dacăjucătorul1alegestrategiastânga(S),atuncijucătorul2
poatealegeS’sauD’,darneștiindceaalesjucătorul1,segândeștela4variantedecâștig
posibile,înraportcucearfipututjucaprimuljucător).Pentruaceastăformăputemdetermina
echilibrulprinalgoritmiidescrișiîncapitolulanterior.Astfel,joculdescrisareununicechilibru
înstrategiipure,șianume(D,D’).Acelașiechilibrurezultășiîncazulîncareaplicăm
algoritmulinducțieirecursive,desprecarevoivorbiincapitolul3.

13II.ELEMENTEDINTEORIAJOCURILORDINAMICEININFORMAȚIE
INCOMPLETĂ
2.1.Jocuriininformatieincompleta
Jocurileˆıninforma¸tieincomplet˘asuntcaracterizateprinfaptulc˘ajuc˘atoriinuposed˘ao
informa¸tiecomplet˘adespredescriereajocului,ˆındeosebidesprepreferin¸telejuc˘atorilor.
Maiexact,juc˘atoriinucunoscexactcumseformeaz˘acˆa¸stigul.Informațiaincompletă
semnificăcăjucătoriinuîșicunosccuexactitatefuncțiilesaledeutilitatesaumulțimilede
alternativeadmisibile.Acestejocurisemainumescbayesienedeoarecejucătoriiîșifac
presupuneridesprestructurafuncțiilorsaledeutilitateînbazaunorprobabilități
condiționatecaresedeterminăfolosindformulaBayes.
Vomanalizaurmătorulexemplu.
Exemplul2.1.1Într-unregataapărutundragoncaredevasteazălocalitățile.Regelea
promisunuiCavalercăîivadaojumătatedinregatdacăvaucidedragonul.Primultrebuiesă
decidăCavalerul.Dacăeldecidesăluptecudragonul,cusiguranțăvaînvinge.Dupăce
dragonulesteînvins,regeledecidedacăvadasaunujumătateadinregat.Aceastăformulare
corespundecazuluiinformațieicomplete.PresupunemcăCavalerulștiecăregiiîngeneralpot
fidedouătiputi:Oneștișineonești.Regelecinstitîșivaonorapromisiuneașivadajumătatea
deregat,dacăCavalerulvaînvinge.Cavaleruliadeciziaînlipsainformațieicompletedespre
faptulcăregeleestecinstitsaunu.Săsemodelezeaceastăsituațiefolosindjocuriledinamice.
Rezolvare.FormaextinsăajoculuiestedescrisăînFigura2.1.1
Fig.2.1.1
Înacestjoccâștigulregeluiestedeterminatdetipulsău(onest,neonest)șivafinotatprinx,
undex=0dacăregeleesteonestșix=2dacăregeleesteneonest.Similarjocurilorstaticeîn
informațieincompletă(jocurilorbayesiene),vompresupunecăCavalerulvaîntâlniunrege
onestcuprobabilitateap.Dacăaducemacestjoclaunjoc”bayesianstatic”,atuncivomobține
omatriceprezentatăîntabelulceurmează,undel→luptă,nl→nuluptă,pl→plătește,npl
→nuplătește.

14
Pentruaconstruiformanormalăajocului,trebuiesădeterminămvaloareamedieacâștigului
Cavaleruluiîndependențădestrategiaregeluicaredepindedetipulregelui.Dacăregiide
ambeletipuriplătesc,atuncivaloareamedieacâștiguluiCavaleruluieste1,iardacănuplătesc,
este−1.Dacăregeleonestplăteșteșicelneonestnuplătește,atuncivaloareamedieacâștigului
este )12()1(1  ppp .Similar,dacăregeleonestnuplăteșteșicelneonestplătește,atunci
valoareamedieacâștiguluieste pp p 211)1()1(  .Înmomentulcândsefixează
valoareaprobabilitățiiavemdejaunjocîninformațiecompletăpentrucarestrategiile
jucătorilorsunt:pentruluptător:{l,nl};pentrurege{pl−pl,pl−npl,npl−pl,npl−npl}.
Formanormalăajoculuipentrup=0.75esteprezentatăîntabeluldemaijos,undeprimacifră
indicăcâștigulCavaleruluișiînparantezeseindicăcâștigulregeluipentrutipulonestșineonest.
ObservămcăînacestjocexistătreisituațiiNashdeechilibru:NE={[l,pl−npl],[nl,npl−pl],
[nl,npl−npl]}.Echilibrul[l,pl−npl]estefiresc:regeleonestplătește,celneonestnuplătește.
Următoareledouăsituațiideechilibrunusuntfirești.Excludereaacestorsituațiideechilibruse
facecașiîncazuljocurilorîninformațieperfectă,șianume:seanalizeazănudoarjoculintegral,
darșisubjocurileproprii.Formelenormalealesubjocurilorsunt:
ObservămcăînambeleacestesubjocuriechilibrulNashestesituația[l,pl−npl],decieaeste

15echilibruperfectșicelelaltesituațiipotfiomise.Dj.Harsanyiapropuscajocurileîninformație
incompletăsăfieinterpretatecajocuridinamicedejaîninformațiecompletășiimperfectădacă
sevaintroduceunnoujucătorNatura,careprimulfaceînmodaleatormișcarea.Faptulcă
jucătorulnucunoaștetipulcelorlalțijucători(înexempluldemaisusCavalerulnucunoaștedacă
regeleesteonestsauneonest)sevamanifestaprinfaptulcăel(jucătorul)nucunoaștecemișcare
afăcutNatura.Aceastaserealizează,prinintermediulmulțimilorinformaționale.Astfel,studiul
jocurilorîninformațieincompletăpoatefisubstituitprinstudiuljocurilorîninformațiecompletă
șiimperfectă.UtilizândunnoujucătorNatura,carealege(determină)probabilitateatipului
jucătorului(alregelui),joculdinexemplul2.1.1vaaveaformaextinsăprezentatăînFigura2.1.2
Fig.2.1.2
Aceastăreprezentareajoculuipermitedejautilizareaalgoritmuluiinducțieirecursive.
2.2JocuriBayesiene.
Echilibrulbayesianperfect(E.B.P)
PentruadefiniE.B.P.vomaplicaprincipiulHarsanyidesoluționareajocurilorîninformație
imcompletă.Astfel,introducemurmătoareleipoteze.
Ipoteza1.Pentrufiecaremulțimeinformaționalăjucătorulcaremută(joacă)trebuiesăaibă
anumitepresupuneridespreceeaces-ajucatpanăatunci.Pentruomulțimeinformaționalăce
nuesteunică,opresupunerevafiodistribuțiedeprobabilitateasupranodurilordinmulțimea
informațională(pentruomulțimeinformaționalădatăcunodunic,presupunerilejucătorului
voraveaprobabilitatea1).
Presupunemcătoțijucătoriiaualesstrategiilelor.Cumînbazasituațieicreatedeaceste
strategiisedeterminăsistemuldepreviziuniînmulțimiinformaționale?Vomexplicaacest
lucrupentrucazulstrategiilorpure.Presupunemcăînjocnuexistămișcărialeatoareale
Naturii.Considerămunjucătorșimulțimeainformaționalăîncaremișcareaaparțineacestui

16jucător.Carevorfiașteptărilejucătoruluiînmulțimeainformaționalădată?
ÎncalitatedeexempluvomconsiderajoculdinFigura2.2.1
Fig.2.2.1Determinareasistemuluidepreviziuniînmulțimiinformaționale.
Aceasta-iformaextinsăaunuijocstaticsimplu.Dacăjucătorul2vapresupunecăjucătorul1
vaalegestrategiaR(arculdindreapta),atuncielpoatesăseafleînnoduldindreaptaal
mulțimiisaleinformaționale.Astfel,reieșinddinaceastăpresupunere,strategiaoptimalăse
vaalegedinmulțimeaderăspunsurioptimalelaalegereadecătrejucătorul1astrategieiR
(înbazaacestuiprincipiușiseconstruiescsituațiileNashdeechilibru).Considerămjoculdin
Figura2.2.2
Fig.2.2.2Determinareasistemuluidepreviziuniînmulțimiinformaționale.
Fiejucătorul1utilizeazăstrategia(a:R,b:L,c:L).ÎnacestjocNaturafacemișcareasa
aleatoarealegândprobabilitățile0.3,0.5și0.2.Înacestcazprobabilitateacăsevaatingenodul
xeste0,noduly−0.5șinodulz−0.2.Probabilitateatotalăcăînjocsevaatingeunnoddin
mulțimeainformaționalăajucătorului2este0+0.5+0.2=0.7,carenuesteegalăcu1.Atunci,
pentruadeterminaprobabilitateadeaalegeunnodconcretdinmulțimeainformațională,adică
probabilitateacondiționatădeevenimentuldeaatingemulțimeainformațională,sevautiliza
formulaBayes.Astfel,presupunerilejucătorului2înmulțimeasainformaționalăare)72;75,0(.

17Ipoteza2.Pentrupresupuneriledatestrategiilejucătorilortrebuiesăfiesecvențialraționale
(cualtecuvinte,pentrufiecaremulțimeInformaționalădată,strategiajucătoruluitrebuiesăfie
optimală,înbazapresupunerilorpecareleareînaceastămulțimeinformațională).
Pentrujoculdescrisanterior,Ipoteza1presupunecăpentrufiecaremulțimedeinformații
nesingulară(ex.S,Mpentrujucătorul1),jucătorul2credecă1vajucaScuprobabilitateapși
Mcuprobabilitatea1-p.Datefiindacestepresupuneri,câștigurileașteptatedecatrejucatorul2,
dacăvajucaD′vorfi: pppDEu  1)1(10)'(2 ,iardacăvajucaS',vorfi
pppSEu  2)1(21)'(2 .Deoareace )()('
2'
2DEuSEu,pentruorice 10p,
rezultăcăjucătorul2nuvajucaniciodatăstrategiaD’.Ipoteza2vaeliminaposibilitateaca
jucătorul2săjoace(dinconsiderentederaționalitate).Deci,ipotezele1și2consistăînfaptul
căjucătoriifacpresupuneridespremodulîncarejoacăceilalțișidatefiindacestepresupuneri
fiecarejucătoracționeazarațional,adicăalegeacelestrategiicareîimaximizeazăcâștigul.
Definiția2.2.1Pentruunechilibrudatalunuijocînformăextinsă,omulțimeinformațională
este”pecaleadeechilibru”dacăîiesteasociatăoprobabilitatepozitivădeafijucatăși”în
afaracăiideechilibru”dacăestesigurcănuvafijucată(0p)decătrejucători
(aici”echilibrul”poatefioricaredinceledefiniteanterior).
Ipoteza3.Pentruomulțimeinformaționalăpecaleadeechilibru,presupunerilesunt
determinateprinregulaBayesșistrategiiledeechilibrualejucătorilor.
Deci,noțiuneadeechilibruBayesianperfectnuvaincludedoarstrategiilejucătorilor,ciși
presupunerilepecarelefacdesprestrategiilealesedeceilalți.Înmultecazuri,ipotezele1-3
constituiechiardefinițiaE.B.P.,darnoivommaiimpuneocondițiecevacăutasăelimine
strategiilecenusuntcredibile.VomexplicamaidetaliatIpoteza3.FieBjevenimentulcare
semnificăfaptulcăînjocs-aajunslaunnodj=1,…,m,șiAevenimentulcăînjocs-aajunsla
mulțimeainformațională,maiexact,lanoduljalmulțimiiinformaționale.Atunciprobabilitatea
realizăriievenimentuluijBîncondițiaevenimentuluiAeste
)()()/(APBPABPj
j,unde
)()(1m
kkBPAP .Vomexemplificacelespuse.
Exemplul2.2.1Determinareapresupunerilorjucătorilorînjocuriledinamiceîninformație
incompletă.
Rezolvare.ConsiderămjoculdinFigura2.2.3

18Fig.2.2.3Determin˘asistemuldepreviziuniˆınmul¸timiinformaționale.
Înbazaprobabilitățilorindicate,jucătorul3vaconsideracănodulcserealizează(atinge)în
procesuljoculuicuprobabilitatea0.4·0.5=0.2,iarnoduldcuprobabilitatea0.6.Astfel,în
bazareguliiBayes,jucătorul3trebuiesăpunăîncorespondențănoduluicprobabilitatea
25.06.02.02.0¸șinoduluidprobabilitatea 75.06.02.06.0.Darnuîntotdeaunasepoate
determinapresupunereaînbazaunuișirdeprobabilități.Considerămjoculdinfigura2.2.4.
Fig.2.2.4Imposibilitateadetermin˘ariipresupunerilorˆınbazaunui
¸sirdeprobabilit˘a¸ti.
Aicijucătorul3nupoateconstruipresupuneriînmulțimeasainformațională.Elpoateobțineo
mișcarenumaidacăjucătorii1și2vorfaceoeroare.Pentruechilibrulperfect(S,S`),jucătorul
2¸știecuprobabilitatea1căjucătorul1vajucaS.Înipoteza2ostrategiemixtăvaconducela
faptulcăjucătorul2credecăjucătorul1joacăScuprobabilitateaq1,Mcuprobabiliateaq2șiD
cuprobabiliatatea1−q1−q2.AtunciconformreguliiBayes,
211
qqqp.Deci,noțiuneade
echilibrubayesianperfectnuvaincludedoarstrategiilejucătorilor,cișipresupunerilepecare
lefacdesprestrategiilealesedeceilalți.Înmultecazuri,ipotezele1-3constituiechiardefiniția
E.B.P.,darnoivommaiimpuneocondițiecevacăutasăeliminestrategiilecarenusunt
credibile.

19Ipoteza4.Peomulțimeinformaționalădinafaracăiideechilibru,presupunerilesunt
determinatederegulaBayesșidestrategiiledeechilibrualejucătorilor,dacăesteposibil.
Definiția2.2.2Vomnumiechilibrubayesianperfect(EBP)pentrujocuriledinamiceîn
informațieincompletăomulțimedestrategiișipresupunericesatisfacIpotezele1-4.
Astfel,echilibrulbayesianperfectconstădindouăcomponente:
a)situațiaînjoccareconstădinstrategiilefiecăruijucător,
b)pentrufiecarejucător¸șifiecaremulțimeinformaționalăcareîiaparține,presupunerile
sale(probabilitățiledealegereanodurilordinmulțimeainformaționalădată).
Exemplul2.2.2Seconsiderăjoculdinamicîninformațieincompletădescrissubformă
extinsăînfigura2.2.5
Fig.2.2.5Determinareaechilibruluibayesianperfect.
ObservămcăuniculechilibruNashaljoculuieste(B,C,D′).Aceastăstrategieșipresupunereacă
p=1satisfacipotezele1-3,(deasemeneași4),deoarecenuexistăomulțimedeinformațiiîn
afaracăiideechilibru,deciesteechilibrubayesianperfect.Totuși,fiestrategia(A,C,S′)cup=0,
careesteunehilibruNashdeoareceniciunjucătornuestetentatsădeviezedelaea.Decinueste
suficientsăavemîndeplinitedoaripotezele1-3,deoareceacesteanugaranteazăceseîntâmplă
pentrumulțimiledeinformațiidinafaracăiideechilibru.Vommaiexemplificamodalitățilede
determinareaechilibruluibayesianperfectînjocuriledinamiceîninformațieincompletă.
Exemplul2.2.3ConsiderămjoculdinFigura2.2.6Săsedetermineechilibrulbayesianperfect

20înstrategiipure.
Rezolvare:cna−firma1coopereazăneagresiv,ca−firma1coopereazăargesiv.Presupunerile
jucătorului2înmulțimeasainformaționalăsuntdateprinprobabilitateaβcăsevaaflaînnodul
dinstângaalmulțimiiinformaționale.Înbazaacestorpresupunerilaalegereaalternativeia
valoareaașteptată(medie)acâștiguluivafi 2)2)(1()3(     ,șilaalegerea
alternativeinavafi    433)1()1(  .
Fig.2.2.6Jocul”Cooperareafirmelor”-determinareaE.B.P
Astfel,înbazapresupunerilorsale,Firma2vaalegealternativaadacă   422 ,adică
dacă.35Deoareceprobabilitateanupoatefistrictmaimareca1,Firma2vaalege
alternativanaindiferentdestrategiapecareovaalegeFirma1.RăspunsuloptimalFirmei1la
faptulcăFirma2vaalegena(nuvafiagresivă),vafialegereaalternativeicadeoareceînacest
cazcâștigulsăuestemaxim(3>−2și3>0).PentruaceastăstrategieaFirmei1,Firma2va
aveacertitudineacăsevaaflaînnoduldindreaptaalmulțimiiinformaționale,adicî0.
Astfel,amdeterminatechilibrulbayesianperfect:situația(ca,na)șipresupunereadeterminată
deprobabilitatea0.
Exemplul2.2.4Unstudentpoatesăsepregăteascăcătreexamensaunu.Examenulconstăîn
rezolvareauneiprobleme.Probabilitateadearezolvaproblemapentruunstudentpregătitde
exameneste0.9,pentruelnepregătit0.1.Dacăstudentuls-apregătitdeexamenșiarezolvat
problema,atuncivacâștiga1unitatecomvențională(u.c.),iarprofesorul2u.c.Dacăstudentul
s-apregătitdeexamenînsănuarezolvatproblema,atuncivacâștiga−1u.c.,iarprofesorul
−1u.c.Dacăstudentulnus-apregătitdeexamenșiarezolvatproblema,atuncivacâștiga2
u.c.,iarprofesorul0u.c.Dacăstudentulnus-apregătitdeexamenșinuarezolvatproblema,
atuncivacâștiga0u.c.,iarprofesorul1u.c.Săsedetermineechilibrulbayesianperfectîn
strategiimixte.

21Rezolvare.FormaextinsăaacestuijocesteprezentatăînFigura2.2.7.S-aufolositnotațiile:pr
−studentuls-apregătitdeexamen,npr−studentulnus-apregătitdeexamen,r−studentula
rezolvatproblema,nr−studentulnuarezolvatproblema,ex−studentulasusținutexamenul,
nex−studentulnuasusținutexamenul.Vomnotaprinπprobabilitateacăstudentuls-apregătit
deexamen,prinp−probabilitateacăprofesorulavalidatexamenulcândstudentularezolvat
problema,prinq−probabilitateacăprofesorulavalidatexamenulcândstudentulnuarezolvat
problema,prinλ−probabilitateacăstudentuls-apregătitdeexamencucondițiacăelarezolvat
problema,µ−probabilitateacăstudentuls-apregătitdeexamenîncondițiacăelnuarezolvat
problema.Probabilitățileλșiµreprezintăpresupunerileprofesoruluiînmulțimilesale
informaționale.
Fig.2.2.7Jocul”Preg˘atireadeexamen.”
Mulțimileinformaționalesuntnotateprincurbe.Dacăstudentuls-apregătitdeexemen,atunci
valoareaașteptatăacâștiguluieste   12.08.1)1)(1(11.0)1)(1(19.0  qp qq pp .
Dacăstudentulnus-apregătitdeexamen,atuncivaloareaașteptatăacâștiguluieste
   qpqqpp 8.12.00)1(29.00)1(21.0  .Dacă85qp ,adică
qpqp 8.12.012.08.1  ,studentuluiîiesteindiferentpregătireasaunudeexamen,șiîn
acestcazelpoatealegeoricevaloare1,0.Dacă85qp,adicăatuncicândrezolvarea
problemeiinfluențeazăconsiderabilprobabilitateadeasusțineexamenul,studentuluiîiestemai
convenabilsăsepregăteascădeexamen(1).Dacă85qp,studentuluiîiestemai
convenabilsănusepregăteascădeexamen(π=0).Astfel,reacțiaoptimalăastudentuluieste
descrisădeegalitatea:

22,
.85,085],1,0[,85,1
),(





qpqpqp
qp
Analizămpresupunerileprofesoruluiînmulțimilesaleinformaționale.Probabilitateacă
studentuls-apregătitdeexamenșiarezolvatproblemaesteπ·0.9;probabilitateacăstudentul
nus-apregăttitdeexamenșiarezolvatproblemaeste:(1−π)·0.1.Probabilitateatotalăcă
studentularezolvatproblema(adicăprobabilitateacăjoculvaducespremulțimea
informaționalădinstânga)esteπ·0.9+(1−π)·0.1.Astfel,înmulțimeainformaționalădinstânga
probabilitateanoduluidinstânga(adicăprobabilitateacăstudentuls-apregătitdeexamenșia
rezolvatproblema)este

 819
1.0)1(9.09.0)(
Inmodsimilarsedeterminăprobabilitateadeaajungeînnoduldinstângaalmuțimii
informaționaledindreapta(adică,probabilitateacăstudentuls-apregătitdeexamenșinua
rezolvatproblema):
 899.0)1(1.01.0)(
Fiestudentularezolvatproblema(profesorulseaflăînmulțimeainformaționalădinstânga).
Pentrupresupuneriledate1,câștigulașteptat(mediu)deprofesor,dacăelvalidează
examenul,este  20)1(2  .Încazulîncareprofesorulnuvalideazăexamenul,atunci
câștigulașteptat(mediu)deprofesor,este    211)1()1(  .Dacă 212,adică
41,atunciprofesoruluiîiesteindiferentsăvalidezesaunuexamenul.Dacă41
profesoruluiîiestemaiconvenabilsăvalidezeexamenul.Îngeneral,acțiunileoptimeale
profesoruluiauurmătoareformă:
,
.41,041],1,0[,41,1
)(






p
Inmodsimilar,dacăstudentulnuarezolvatproblema(adicăprofesorulseaflăînmulțimea
informaționalădindreapta),acțiunileoptimealeprofesoruluiauurmătoareaformă:

23




41,0,41],1,0[,41,1
)(

q
Astfel,amdescrissistemulderelațiicaredeterminăechilibrulbayesianperfect.Vommenționa
următoarele:
1.încazulE.B.P.ipotezele1și2suntechivalentecufaptulcănuexistăstrategiistrict
dominatepentruoricemuțimeinformațională;
2.ipoteza4aratăfaptulcăjucătoriinupotamenințacu”ajucastrategiistrictdominate”.

24III.UTILIZAREACLUSTERULUIUSMLADETERMINAREASOLUȚIILOR
JOCURILORBAYESIENEDINAMICE.
Clusterulreprezintăungrupdecalculatoareconectate,carefuncționeazăîmpreună,putândfi
văzutecaunsistemunitar.
3.1.ElementedebazadinprogramareMPI(MessagePassingInterface).
MPIesteunstandardpentrucomunicareaprinmesaje,elaboratdeMPIForum.Îndefinirealui
aufostutilizatecaracteristicilecelemaiimportantealeunorsistemeanterioare,bazatepe
comunicațiademesaje.AfostvalorificatăexperiențadelaIBM,Intel(NX/2)Express,nCUBE
(Vertex),PARMACS,Zipcode,Chimp,PVM,Chameleon,PICL.MPIarelabazămodelul
proceselorcomunicanteprinmesaje:uncalculesteocolecțiedeprocesesecvențialecare
coopereazăprincomunicaredemesaje.MPIesteobibliotecă,nuunlimbaj.Elspecifică
convențiideapelpentrumaimultelimbajedeprogramare:C,C++,FORTRAN.77,
FORTRAN90,Java.
ObiectiveleMPI:
•proiectareauneiinterfețedeprogramareaaplicațiilor;
•comunicareeficientă;
•săfieutilizabilînmediieterogene;
•portabilitate;
•interfațadecomunicaresăfiesigură(eroriletratatededesubt);
•apropieredepracticicurente(PVM,NX,Express,p4;
•semanticainterfețeisăfieindependentădelimbaj.
Astfel,MPIesteobibliotecădefuncții,carepermiterealizareainteracțiuniiproceselorparalele
prinmecanismuldetransmitereamesajelor.Esteobibliotecăcomplexă,formatădinaproximativ
130defuncțiicareinclud:
•funcțiideinițializareșiînchidere(lichidare)aproceselorMPI;
•funcțiicareimplementeazăoperațiuniledecomunicaredetip„proces-proces”;
•funcțiicareimplementeazăoperațiunilecolective;
•funcțiipentrulucrulcugrupurideproceseșicomunicatori;
•funcțiipentrulucrulcustructuridedate;
•funcțiacareimplementeazăgenerareadinamicăaproceselor;
•funcțiicareimplementeazăcomunicăriunidirecționaleîntreprocese(accesulla
distanțăamemoriei);

25•funcțiidelucrucufișierele.
FiecaredintrefuncțiileMPIestecaracterizatăprinmetodaderealizare(executare):
•funcțielocală–serealizeazăîncadrulprocesuluicarefaceapellaea,lafinalizareaei
nuestenevoiedetransmiteredemesaje;
•funcțienelocală–pentrufinalizareaeiestenecesarăutilizareaunorproceduriMPI,
executatedealteprocese;
•funcțieglobală–proceduratrebuiesăfieexecutatădetoateproceselegrupului;
•funcțiedeblocare;
•funcțiedenon-blocare.
FuncțiileMPIdebază
FuncțiaMPI_Init
Formageneralăafuncțieieste
intMPI_Init(int*argc,char***argv);
Carezultatalexecutăriiacesteifuncțiisecreeazăungrupdeprocese,încareseincludtoate
proceselegeneratedeutilitarulmpirun,șisecreeazăpentruacestgrupunmediuvirtualde
comunicaredescrisdecomunicatorulcunumeleMPI_COMM_WORLD.Proceseledingrup
suntnumerotatedela0lagroupsize-1,undegroupsizeesteegalcunumăruldeprocesedingrup.
LafelsecreeazăcomunicatorulcunumeleMPI_COMM_SELF,caredescriemediulde
comunicarepentrufiecareprocesînparte.
PerecheafuncțieideinițializareesteMPI_Finalize,caretrebuieexecutatădefiecareproces,
pentrua„închide”mediulMPI.Utilizatorultrebuiesăseasigurecătoatecomunicațiileîncursde
desfășurares-auterminatînaintedeapeluloperațieidefinalizare.DupăMPI_Finalize,nicio
altăoperațieMPInumaipoatefiexecutată(nicimăcarunadeinițializare)
FuncțiaMPI_Comm_size
ÎnlimbajulCfuncțiaareurmătorulprototip:
intMPI_Comm_size(MPI_Commcomm,int*size),
FuncțiareturneazănumăruldeproceseMPIalemediuluidecomunicarecunumelecomm.
Funcțiaestelocală.
FuncțiaMPI_Comm_rank
ÎnlimbajulCfuncțiaareurmătorulprototip:
intMPI_Comm_rank(MPI_Commcomm,int*rank)
Unprocespoateaflapozițiasaîngrupulasociatunuicomunicatorprinapelulfuncției
MPI_Comm_rank.Funcțiareturneazăunnumărdindiapazonul0,..,size-1,caresemnifică
identificatorulprocesuluiMPIcareaexecutataceastăfuncție.Astfelproceselorliseatribuieun

26numărînfuncțiedeordineaîncareafostexecutatăfuncția.Aceastăfuncțieestelocală.
Exemplul3.1.1.SăseelaborezeunprogramMPIîncarefiecareprocestipăreșterankulsăuși
numelenoduluiundeseexecută.
MaijosesteprezentatcodulprogramuluiînlimbajulC++încareserealizeazăcondițiile
enunțateînexemplu3.1.1.
Rezultateleposibilealeexecutăriiprogramului:
[ALBOT_Mihaela@hpc]$/opt/openmpi/bin/mpiCC-oExemplu_3_1_1.exeExemplu_3_1_1.cpp
ALBOT_Mihaela@hpc]$/opt/openmpi/bin/mpirun-n7-machinefile~/nodesExemplu_3_1_1.exe
=====REZULTATULPROGRAMULUI'Exemplu_3_1_1.exe'
==Aufostgenerate4MPIprocessespenodulcompute-0-0.local===
==Aufostgenerate3MPIprocessespenodulcompute-0-1.local===
==ProceselecomunicatoruluiMPI_COMM_WORLDaufost'distribuite'penoduriastfel:
Hello,Iamtheprocessnumber0(localrunk0)onthecomputehostnamecompute-0-0.local,fromtotal
numberofprocess7
Hello,Iamtheprocessnumber3(localrunk3)onthecomputehostnamecompute-0-0.local,fromtotal
numberofprocess7
Hello,Iamtheprocessnumber2(localrunk2)onthecomputehostnamecompute-0-0.local,fromtotal
numberofprocess7
Hello,Iamtheprocessnumber4(localrunk0)onthecomputehostnamecompute-0-1.local,fromtotal
numberofprocess7
Hello,Iamtheprocessnumber5(localrunk1)onthecomputehostnamecompute-0-1.local,fromtotal
numberofprocess7
Hello,Iamtheprocessnumber1(localrunk1)onthecomputehostnamecompute-0-0.local,fromtotal
numberofprocess7
Hello,Iamtheprocessnumber6(localrunk2)onthecomputehostnamecompute-0-1.local,fromtotal
numberofprocess7
Comunicareadetip„proces-proces”(punctlapunct)
Operațiiledebazăpentrucomunicareapunctlapunctsuntsendșireceive.
send(adresa,lungime,destinatie,tip)

27unde:
•adresaidentificăînceputuluneizonedememorieundeseaflămesajuldetransmis,
•lungimeestelungimeaînoctețiamesajului,
•destinatieesteidentificatorulprocesuluicăruiaisetrimitemesajul(uzualunnumărîntreg),
•tip(flag)esteunîntregne-negativcarerestricționeazărecepțiamesajului.Acestargument
permiteprogramatoruluisărearanjezemesajeleînordine,chiardacăelenusosescînsecvența
dorită.Acestsetdeparametriesteunbuncompromisîntreceeaceutilizatoruldoreșteșiceeace
sistemulpoatesăofere:transferuleficientaluneizonecontiguedememoriedelaunprocesla
altul.Înparticular,sistemuloferămecanismeledepăstrareîncoadăamesajelor,astfelcăo
operațiederecepțierecv(adresa,maxlung,sursa,tip,actlung)seexecutăcusuccesdoardacă
mesajularetipulcorect.Mesajelecarenucorespundașteaptăîncoadă.Încelemaimultesisteme,
sursaesteunargumentdeieșire,careindicăorigineamesajului.
FuncțiiMPIpentrutransmitereamesajelor
FuncțiaMPI_Send
ÎnlimbajulCaceastăfuncțieareurmătorulprototip,valorilereturnatereprezentândcoduri
deeroare:
intMPI_Send(void*buf,intcount,MPI_Datatypedatatype,intdest,inttag,MPI_Comm
comm)
undeparametriisunt:
INbuf adresainițialăatamponuluisursă;
INcountnumăruldeelemente(întregne-
negativ);
INdatatypetipulfiecăruielement;
INdest număruldeordinealdestinatarului
(întreg);
INtag tipulmesajului(întreg);
INcommcomunicatorulimplicat.
Astfel,procesuldinmediuldecomunicarecomm,careexecutăfuncțiaMPI_Send,
expediazăprocesuluidest,countdatedetipdatatypedinmemoriasaîncepândcuadresabuf.
Acestordateliseatribuieetichetatag.
FuncțiaMPI_Recv
PrototipulacesteifuncțiiînlimbajulCeste
intMPI_Recv(void*buf,intcount,MPI_Datatypedatatype,intsource,int
tag,MPI_Commcomm,MPI_Status*status),
undeparametriisunt:

28OUTbufadresainițialăatamponuluidestinatar;
INcountnumăruldeelemente(întregne-negativ);
INdatatypetipulfiecăruielement;
INsourcenumăruldeordinealsursei(întreg);
INtag tipulmesajului(întreg);
INcomm comunicatorulimplicat;
OUTstatusstarea,element(structură)ceindicăsursa,
tipulșicontorulmesajuluiefectivprimit.
Astfel,procesuldinmediuldecomunicarecomm,careexecutăfuncțiaMPI_Recv,
recepționeazădelaprocesulsource,countdatedetipdatatypecareauetichetatagșile
salveazăînmemoriasaîncepândcuadresabuf.
FuncțiaMPI_Sendrecv
Însituațiileîncaresedoreșterealizareaunuischimbreciprocdedateîntreprocese,mai
sigurestedeautilizaofuncțiecombinatăMPI_Sendrecv.
PrototipulacesteifuncțiiînlimbajulCeste
intMPI_Sendrecv(void*sendbuf,intsendcount,MPI_Datatypesendtype,intdest,int
sendtag,void*recvbuf,intrecvcount,MPI_Datatyperecvtype,intsource,MPI_Datatypeа
recvtag,MPI_Commcomm,MPI_Status*status).
ExistășialtefuncțiiMPIcarepermitprogramatoruluisăcontrolezemoduldecomunicaredetip
proces-proces.
VomilustrautilizareafuncțiilorMPI_SendșiMPI_Recvprinurmătorulexemplu.
Exemplul3.1.2SăseelaborezeunprogramMPIînlimbajulC++încareserealizează
transmitereamesajelorpecercîncepândcuprocesul„încep”.Valoareavariabilei„încep”este
inițializatădetoateproceseleșiseaflăîndiapazonul0,…,size-1.
Maijosesteprezentatcodulprogramuluiîncareserealizeazăcondițiileenunțateîn
exemplul3.1.2.

29
Rezultateleposibilealeexecutăriiprogramului:
[ALBOT_Mihaela@hpcFinale]$/opt/openmpi/bin/mpiCC-oExemplu_3_1_2.exeExemplu_3_1_2.cpp
[ALBOT_Mihaela@hpcFinale]$/opt/openmpi/bin/mpirun-n9-machinefile~/nodesExemplu_3_1_2.exe
=====REZULTATULPROGRAMULUI'Exemplu_3_1_2.exe'
Procesulcurancul0alnodului'compute-0-0.local'aprimitvaloarea8delaprocesulcurancul8
Procesulcurancul1alnodului'compute-0-0.local'aprimitvaloarea0delaprocesulcurancul0
Procesulcurancul2alnodului'compute-0-0.local'aprimitvaloarea1delaprocesulcurancul1
Procesulcurancul3alnodului'compute-0-0.local'aprimitvaloarea2delaprocesulcurancul2
Procesulcurancul4alnodului'compute-0-1.local'aprimitvaloarea3delaprocesulcurancul3
Procesulcurancul8alnodului'compute-0-2.local'aprimitvaloarea7delaprocesulcurancul7
Procesulcurancul5alnodului'compute-0-1.local'aprimitvaloarea4delaprocesulcurancul4
Procesulcurancul6alnodului'compute-0-1.local'aprimitvaloarea5delaprocesulcurancul5
Procesulcurancul7alnodului'compute-0-1.local'aprimitvaloarea6delaprocesulcurancul6
FuncțiileMPIpentrucomunicareacolectivă
Operațiilecolectiveimplicăungrupdeprocese.Pentruexecuție,operațiacolectivătrebuie
apelatădetoateprocesele,cuargumentecorespondente.Proceseleimplicatesuntdefinitede
argumentulcomunicator,careprecizeazătotodatăcontextuloperației.Multeoperațiicolective,
cumestedifuzarea,presupunexistențaunuiprocesdeosebitdecelelalte,aflatlaoriginea
transmiteriisaurecepției.Unastfeldeprocessenumeșterădăcină.Anumiteargumentesunt
specificerădăciniișisuntignoratedecelelalteprocese,altelesuntcomunetuturor.
Operațiilecolectiveseîmpartînmaimultecategorii:
sincronizaredetipbarierăatuturorproceselorgrupului;
comunicăricolective,încareseinclud:
difuzarea;
colectareadatelordelamembriigrupuluilarădăcină;
distribuireadatelordelarădăcinăspremembriigrupului;

30combinațiidecolectare/distribuire(allgatherșialltoall);
calculecolective:
operațiidereducere;
combinațiireducere/distribuire.
Caracteristicicomunealeoperațiilorcolectivedetransmitereamesajelor:
Tipuldatelor
Cantitateadedatetransmisătrebuiesăcorespundăcucantitateadedaterecepționată.Deci,
chiardacăhărțiletipurilordiferă,semnăturilelortrebuiesăcoincidă.
Sincronizarea
Terminareaunuiapelarecasemnificațiefaptulcăapelantulpoateutilizatamponulde
comunicare,participareasaînoperațiacolectivăîncheindu-se.Astanuaratăcăcelelalteprocese
dingrupauterminatoperația.Caurmare,exceptândsincronizareadetipbarieră,ooperație
colectivănupoatefifolosităpentrusincronizareaproceselor.
Comunicator
Comunicărilecolectivepotfolosiaceeașicomunicatoricaceipunctlapunct.MPI
garanteazădiferențiereamesajelorgenerateprinoperațiicolectivedecelepunctlapunct.
Implementare
Rutineledecomunicarecolectivăpotfibazatepecelepunctlapunct.Aceastasporește
portabilitateafațădeimplementărilebazateperutineceexploateazăarhitecturiparalele.
Principaladiferențădintreoperațiilecolectiveșioperațiiledetippunctlapunctestefaptulcă
acesteaimplicăîntotdeaunatoateproceseleasociatecuunmediuvirtualdecomunicare
(comunicator).Setuldeoperațiicolectiveinclude:
sincronizareatuturorproceselorprinbariere(funcțiaMPI_Barrier);
acțiunidecomunicarecolectivă,careinclud:
livraredeinformațiidelaunproceslatoțiceilalțimembriaicomunicatorului(funcția
MPI_Bcast);
oasamblare(adunare)amasivelordedatedistribuitepeoseriedeproceseîntr-un
singurtabloușipăstrarealuiînspațiuldeadreseaunuisingurproces(root)(funcțiile
MPI_Gather,MPI_Gatherv);
oasamblare(adunare)amasivelordedatedistribuitepeoseriedeproceseîntr-un
singurtabloușipăstrarealuiînspațiuldeadresealtuturorproceselorcomunicatorului
(funcțiileMPI_Allgather,MPI_Allgatherv);
divizareaunuimasivșitrimitereafragmentelorsaletuturorproceselordin
comunicatorulindicat(funcțiileMPI_Scatter,MPI_Scatterv);

31ocombinareaoperațiilorScatter/Gather(All-to-All),fiecareprocesîmpartedatelesale
dinmemoriatampondetrimitereșidistribuiefragmentelededatetuturorproceselor,și,
concomitent,colecteazăfragmenteletrimiseîntr-untamponderecepție(funcțiile
MPI_Alltoall,MPI_Alltoallv);
operațiileglobaledecalculasupradatelordinmemoriadiferitorprocese:
cupăstrarearezultatelorînspațiuldeadresealunuisingurproces(funcția
MPI_Reduce);
cudifuzarea(distribuirea)rezultatelortuturorproceselorcomunicatoruluiindicat
(funcțiaMPI_Allreduce);
operațiicombinateReduce/Scatter(funcțiaMPI_Reduce_scatter);
operațiedereducereprefix(funcțiaMPI_Scan).
Toaterutineledecomunicare,cuexcepțiaMPI_Bcast,suntdisponibileîndouăversiuni:
variantasimplă,cândtoatemesajeletransmiseauaceeașilungimeșiocupăzoneleadiacente
înspațiuldeadresealprocesului;
variantadetip"vector"(funcțiilecusimbolsuplimentar"v"lasfârșitulnumelui),careoferă
maimulteoportunitățipentruorganizareadecomunicațiicolectiveșieliminărestricțiile
inerentedinvariantasimplă,atâtînceeacepriveștelungimeablocurilordedate,câtșiîn
ceeacepriveșteplasareadatelorînspațiuldeadresealproceselor.
FuncțiileMPIpentruoperațiidereducere
Înprogramareaparalelăoperațiilematematicepeblocuridedatecaresuntdistribuiteîntre
procesoaresenumescoperațiiglobaledereducere.Ooperațiedeacumularesemainumeșteși
operațieglobalădereducere.Fiecareprocespuneladispozițieunblocdedate,caresunt
combinatecuooperațiebinarădereducere;rezultatulacumulatestecolectatlaprocesulroot.În
MPI,ooperațiuneglobalădereducereestereprezentatăînurmătoarelemoduri:
•menținerearezultatelorînspațiuldeadresealunuisingurproces(funcțiaMPI_Reduce);
•menținerearezultatelorînspațiuldeadresealtuturorproceselor(funcția
MPI_Allreduce);
operațiadereducereprefix,careîncalitatederezultatreturneazăunvectoralcăruicomponentăi
esterezultatuloperațieidereducerealeprimeloricomponentedinvectoruldistribuit(funcția
MPI_Scan).
FuncțiaMPI_Reduceseexecutăastfel.Operațiaglobalădereducereindicatăprin
specificareaparametruluiop,serealizeazăpeprimeleelementealetamponuluideintrare,iar
rezultatulestetrimisînprimulelementaltamponuluiderecepționarealprocesuluiroot.Același
lucruserepetăpentruurmătoareleelementedinmemoriatamponetc.Prototipulacesteifuncțiiîn

32limbajulCeste:
intMPI_Reduce(void*sendbuf,void*recvbuf,intcount,MPI_Datatypedatatype,
MPI_Opop,introot,MPI_Commcomm)
unde
INsendbufadresainițialăatamponuluipentrudatelede
intrare;
OUTrecvbufadresainițialăatamponuluipentrurezultate
(seutilizeazănumaideprocesulroot);
INcountnumăruldeelementeîntamponuldeintrare;
INdatatypetipulfiecăruielementdintamponulde
intrare;
INop operațiadereducere;
INrootnumărulprocesuluicarerecepționează
rezultateleoperațieidereducere;
INcommcomunicatorulimplicat.
Întabeluldemaijossuntprezentateoperațiilepredefinitecarepotfiutilizateînfuncția
MPI_Reduce.
Nume Operația Tipuridedateadmisibile
MPI_MAX
MPI_MINMaximum
Minimuminteger,floatingpoint
MPI_SUM
MPI_PRODSuma
Produsulinteger,floatingpoint,
complex
MPI_LAND
MPI_LOR
MPI_LXORAND
OR
excludereORinteger,logical
MPI_BAND
MPI_BOR
MPI_BXORAND
OR
excludereORinteger,byte
MPI_MAXL
OC
MPI_MINLO
CValoareamaximalășiindicele
ValoareaminimalășiindiceleTipspecialdedate
Întabeluldemaisuspentrutipuridedateseutilizeazăurmătoarelenotații:
integerMPI_INT, MPI_LONG, MPI_SHORT,
MPI_UNSIGNED_SHORT, MPI_UNSIGNED,
MPI_UNSIGNED_LONG
floating
pointMPI_FLOAT, MPI_DOUBLE, MPI_REAL,
MPI_DOUBLE_PRECISION,MPI_LONG_DOUBLE
logicalMPI_LOGICAL
complexMPI_COMPLEX
byte MPI_BYTE
VomilustrautilizareaoperațiilorglobaledereducereMPI_SUMînbazaurmătorului
exemplu.

33Exemplul3.1.3Săsecalculezevaloareaaproximativăaluiprinintegrarenumericăcu
formula dxx1
0214 ,folosindformuladreptunghiurilor.Intervalulînchis[0,1]seîmparteîntr-
unnumărdensubintervaleșiseînsumeazăariiledreptunghiuriloravândcabazăfiecare
subinterval.Pentruexecuțiaalgoritmuluiînparalel,seatribuie,fiecăruiadintreproceseledin
grup,unanumitnumărdesubintervale.Celedouăoperațiicolectivecareaparînrezolvaresunt:
difuzareavalorilorluin,tuturorproceselor;
însumareavalorilorcalculatedeprocese.
MaijosesteprezentatcodulprogramuluiînlimbajulC++caredeterminăvaloareaaproximativă
alui
Rezultateleposibilealeexecutăriiprogramului:
[ALBOT_Mihaela@hpc]$/opt/openmpi/bin/mpiCC-oExemplu3.1.3.exeExemplu_3_1_3.cpp
[ALBOT_Mihaela@hpc]$/opt/openmpi/bin/mpirun-n16-machinefile~/nodes4Exemplu3.1.3.exe
=====Rezultateleprogramului'Exemplu_3_1_3.exe'=====
Enterthenumberofintervals:(0quits)100000
Process1oncompute-0-2.localmypi=0.1963576657186469
Process2oncompute-0-2.localmypi=0.1963564157936524
Process3oncompute-0-2.localmypi=0.1963551658561532
Process4oncompute-0-4.localmypi=0.1963539159061520
Process10oncompute-0-6.localmypi=0.1963464159436181
Process12oncompute-0-8.localmypi=0.1963439158561127

34Process0oncompute-0-2.localmypi=0.1963589156311392
Process6oncompute-0-4.localmypi=0.1963514159686426
Process8oncompute-0-6.localmypi=0.1963489159811299
Process15oncompute-0-8.localmypi=0.1963401656311267
Process7oncompute-0-4.localmypi=0.1963501659811359
Process9oncompute-0-6.localmypi=0.1963476659686233
Process14oncompute-0-8.localmypi=0.1963414157186182
Process5oncompute-0-4.localmypi=0.1963526659436477
Process11oncompute-0-6.localmypi=0.1963451659061137
Process13oncompute-0-8.localmypi=0.1963426657936135
Piisapproximately3.1415926535981260,Erroris0.0000000000083329
wallclocktime=0.000813
=====Rezultateleprogramului'HB_Pi.exe'=====
Enterthenumberofintervals:(0quits)100000000
Process8oncompute-0-6.localmypi=0.1963495402243708
Process15oncompute-0-8.localmypi=0.1963495314743671
Process4oncompute-0-4.localmypi=0.1963495452243360
Process5oncompute-0-4.localmypi=0.1963495439743813
Process3oncompute-0-2.localmypi=0.1963495464743635
Process11oncompute-0-6.localmypi=0.1963495364743647
Process1oncompute-0-2.localmypi=0.1963495489743604
Process13oncompute-0-8.localmypi=0.1963495339743620
Process14oncompute-0-8.localmypi=0.1963495327243415
Process0oncompute-0-2.localmypi=0.1963495502243742
Process7oncompute-0-4.localmypi=0.1963495414743800
Process2oncompute-0-2.localmypi=0.1963495477243492
Process12oncompute-0-8.localmypi=0.1963495352243697
Process9oncompute-0-6.localmypi=0.1963495389743577
Process6oncompute-0-4.localmypi=0.1963495427243758
Process10oncompute-0-6.localmypi=0.1963495377243211
Piisapproximately3.1415926535897749,Erroris0.0000000000000182
wallclocktime=0.172357
=====Rezultateleprogramului'HB_Pi.exe'=====
Enterthenumberofintervals:(0quits)0
[ALBOT_Mihaela@hpc]$
VomexemplificautilizareaoperațiilorglobaledereducereMPI_MAXșiMPI_MINîncelece
urmează.
Exemplul3.1.4Săsedetermineelementelemaximaledepecoloaneleuneimatrice
pătrate(dimensiuneaesteegalăcunumăruldeprocese).Elementelematriceisuntinițializatede
procesulcurankul0.SăfieutilizatefuncțiileMPI_ReduceșioperațiaMPI_MAX.

35
Rezultateleposibilealeexecutăriiprogramului:
[ALBOT_Mihaela@hpc]$/opt/openmpi/bin/mpiCC-oExemplu_3_1_4.exeExemplu_3_1_4.cpp
[ALBOT_Mihaela@hpc]$/opt/openmpi/bin/mpirun-n6-machinefile~/nodes4oExemplu_3_1_4.exe
=====REZULTATULPROGRAMULUI'Exemplu_3_1_4.exe'
Tipardateleinitiale
A[0,0]=1.80A[0,1]=0.85A[0,2]=1.68A[0,3]=1.71A[0,4]=1.96A[0,5]=0.42
A[1,0]=0.72A[1,1]=1.65A[1,2]=0.60A[1,3]=1.19A[1,4]=1.03A[1,5]=1.35
A[2,0]=0.78A[2,1]=1.10A[2,2]=2.04A[2,3]=1.97A[2,4]=1.37A[2,5]=1.54
A[3,0]=0.30A[3,1]=1.30A[3,2]=0.04A[3,3]=0.52A[3,4]=0.29A[3,5]=1.73
A[4,0]=0.34A[4,1]=0.86A[4,2]=0.28A[4,3]=0.23A[4,4]=2.15A[4,5]=0.47
A[5,0]=1.10A[5,1]=1.80A[5,2]=1.32A[5,3]=0.64A[5,4]=1.37A[5,5]=1.13
Elementulmaximaldepecoloana0=1.80
Elementulmaximaldepecoloana1=1.80
Elementulmaximaldepecoloana2=2.04
Elementulmaximaldepecoloana3=1.97
Elementulmaximaldepecoloana4=2.15
Elementulmaximaldepecoloana5=1.73
[ALBOT_Mihaela@hpc]$/opt/openmpi/bin/mpirun-n8-machinefile~/nodes4Exemplu_2_4_2.exe
=====REZULTATULPROGRAMULUI'Exemplu_2_4_2.exe'
Tipardateleinitiale
A[0,0]=1.80A[0,1]=0.85A[0,2]=1.68A[0,3]=1.71A[0,4]=1.96A[0,5]=0.42A[0,6]=0.72A[0,7]=1.65
A[1,0]=0.60A[1,1]=1.19A[1,2]=1.03A[1,3]=1.35A[1,4]=0.78A[1,5]=1.10A[1,6]=2.04A[1,7]=1.97
A[2,0]=1.37A[2,1]=1.54A[2,2]=0.30A[2,3]=1.30A[2,4]=0.04A[2,5]=0.52A[2,6]=0.29A[2,7]=1.73
A[3,0]=0.34A[3,1]=0.86A[3,2]=0.28A[3,3]=0.23A[3,4]=2.15A[3,5]=0.47A[3,6]=1.10A[3,7]=1.80
A[4,0]=1.32A[4,1]=0.64A[4,2]=1.37A[4,3]=1.13A[4,4]=1.06A[4,5]=2.09A[4,6]=0.63A[4,7]=1.66
A[5,0]=1.13A[5,1]=1.65A[5,2]=0.86A[5,3]=1.91A[5,4]=0.61A[5,5]=0.76A[5,6]=1.73A[5,7]=1.97
A[6,0]=0.15A[6,1]=2.04A[6,2]=1.13A[6,3]=0.18A[6,4]=0.41A[6,5]=1.42A[6,6]=1.91A[6,7]=0.75
A[7,0]=0.14A[7,1]=0.04A[7,2]=0.98A[7,3]=0.14A[7,4]=0.51A[7,5]=2.08A[7,6]=1.94A[7,7]=1.83
Elementulmaximaldepecoloana0=1.80
Elementulmaximaldepecoloana1=2.04
Elementulmaximaldepecoloana2=1.68
Elementulmaximaldepecoloana3=1.91
Elementulmaximaldepecoloana4=2.15
Elementulmaximaldepecoloana5=2.09
Elementulmaximaldepecoloana6=2.04
Elementulmaximaldepecoloana7=1.97

36Exemplul3.1.4aSăsedetermineelementelemaximaledepecoloaneleuneimatricipatrate
(dimensiuneaesteegalacunumaruldeprocese).Liniilematriceisuntinitializatedefiecare
procesînparte.Procesulcurankul0înbazaacestorlinii"construiește"matricea.Săfie
utilizatefunctiaMPI_ReducesioperatiaMPI_MAX.
Rezultateleposibilealeexecutăriiprogramului:
[ALBOT_Mihaela@hpc]$/opt/openmpi/bin/mpiCC-oExemplu_3_1_4a.exeExemplu_3_1_4a.cpp
[ALBOT_Mihaela@hpc]$/opt/openmpi/bin/mpirun-n5-machinefile~/nodes6Exemplu_3_1_4a.exe
=====REZULTATULPROGRAMULUI'Exemplu_3_1_4a.exe'
Tipardateleinitialealeprocesuluicurankul0
Rows[0]=1.98Rows[1]=1.97Rows[2]=0.42Rows[3]=0.49Rows[4]=2.04
Tipardateleinitialealeprocesuluicurankul1
Rows[0]=0.60Rows[1]=0.71Rows[2]=2.15Rows[3]=1.18Rows[4]=0.82
Tipardateleinitialealeprocesuluicurankul2
Rows[0]=1.38Rows[1]=1.59Rows[2]=1.73Rows[3]=0.80Rows[4]=1.76
Tipardateleinitialealeprocesuluicurankul3
Rows[0]=0.00Rows[1]=0.34Rows[2]=0.24Rows[3]=1.49Rows[4]=1.63
Tipardateleinitialealeprocesuluicurankul4
Rows[0]=1.84Rows[1]=1.22Rows[2]=1.96Rows[3]=1.10Rows[4]=0.40
Resultatelef-tieiMPI_Gather
A[0,0]=1.98A[0,1]=1.97A[0,2]=0.42A[0,3]=0.49A[0,4]=2.04
A[1,0]=0.60A[1,1]=0.71A[1,2]=2.15A[1,3]=1.18A[1,4]=0.82
A[2,0]=1.38A[2,1]=1.59A[2,2]=1.73A[2,3]=0.80A[2,4]=1.76
A[3,0]=0.00A[3,1]=0.34A[3,2]=0.24A[3,3]=1.49A[3,4]=1.63
A[4,0]=1.84A[4,1]=1.22A[4,2]=1.96A[4,3]=1.10A[4,4]=0.40
Elementulmaximaldepecoloana0=1.98
Elementulmaximaldepecoloana1=1.97
Elementulmaximaldepecoloana2=2.15
Elementulmaximaldepecoloana3=1.49
Elementulmaximaldepecoloana4=2.04
[ALBOT_Mihaela@hpcFinale]$

37Exemplu3.1.5UtilizândfuncțiaMPI_ReduceșioperațiileMPI_MAXLOCsăse
determineelementelemaximaledepecoloaneșiindiceleliniei,uneimatricepătrate
(dimensiuneaesteegalăcunumăruldeprocese).Elementelematriceisuntinițializatede
procesulcurankul0.
Rezultateleposibilealeexecutăriiprogramului:
[ALBOT_Mihaela@hpc]$/opt/openmpi/bin/mpiCC-oExemplu_3_1_5.exeExemplu_3_1_5.cpp
[ALBOT_Mihaela@hpc]$/opt/openmpi/bin/mpirun-n6-machinefile~/nodes4Exemplu_3_1_5.exe
=====Rezultateleprogramului'Exemplu_3_1_5.exe'=====
Tipardateleinitiale
A[0,0]=1.80A[0,1]=0.85A[0,2]=1.68A[0,3]=1.71A[0,4]=1.96A[0,5]=0.42
A[1,0]=0.72A[1,1]=1.65A[1,2]=0.60A[1,3]=1.19A[1,4]=1.03A[1,5]=1.35
A[2,0]=0.78A[2,1]=1.10A[2,2]=2.04A[2,3]=1.97A[2,4]=1.37A[2,5]=1.54
A[3,0]=0.30A[3,1]=1.30A[3,2]=0.04A[3,3]=0.52A[3,4]=0.29A[3,5]=1.73
A[4,0]=0.34A[4,1]=0.86A[4,2]=0.28A[4,3]=0.23A[4,4]=2.15A[4,5]=0.47
A[5,0]=1.10A[5,1]=1.80A[5,2]=1.32A[5,3]=0.64A[5,4]=1.37A[5,5]=1.13
Valorilemaximaledepecoloaneșiindiceleliniei:
Coloana0,valoarea=1.80,linia=0
Coloana1,valoarea=1.80,linia=5
Coloana2,valoarea=2.04,linia=2
Coloana3,valoarea=1.97,linia=2
Coloana4,valoarea=2.15,linia=4
Coloana5,valoarea=1.73,linia=3
[Hancu_B_S@hpc]$/opt/openmpi/bin/mpirun-n8-machinefile~/nodes4Exemplu_3_4_7.exe
=====Rezultateleprogramului'Exemplu_2_4_3.exe'=====
Tipardateleinitiale
A[0,0]=1.80A[0,1]=0.85A[0,2]=1.68A[0,3]=1.71A[0,4]=1.96A[0,5]=0.42A[0,6]=0.72A[0,7]=1.65
A[1,0]=0.60A[1,1]=1.19A[1,2]=1.03A[1,3]=1.35A[1,4]=0.78A[1,5]=1.10A[1,6]=2.04A[1,7]=1.97
A[2,0]=1.37A[2,1]=1.54A[2,2]=0.30A[2,3]=1.30A[2,4]=0.04A[2,5]=0.52A[2,6]=0.29A[2,7]=1.73
A[3,0]=0.34A[3,1]=0.86A[3,2]=0.28A[3,3]=0.23A[3,4]=2.15A[3,5]=0.47A[3,6]=1.10A[3,7]=1.80
A[4,0]=1.32A[4,1]=0.64A[4,2]=1.37A[4,3]=1.13A[4,4]=1.06A[4,5]=2.09A[4,6]=0.63A[4,7]=1.66

38A[5,0]=1.13A[5,1]=1.65A[5,2]=0.86A[5,3]=1.91A[5,4]=0.61A[5,5]=0.76A[5,6]=1.73A[5,7]=1.97
A[6,0]=0.15A[6,1]=2.04A[6,2]=1.13A[6,3]=0.18A[6,4]=0.41A[6,5]=1.42A[6,6]=1.91A[6,7]=0.75
A[7,0]=0.14A[7,1]=0.04A[7,2]=0.98A[7,3]=0.14A[7,4]=0.51A[7,5]=2.08A[7,6]=1.94A[7,7]=1.83
Valorilemaximaledepecoloaneșiindiceleliniei:
Coloana0,valoarea=1.80,linia=0
Coloana1,valoarea=2.04,linia=6
Coloana2,valoarea=1.68,linia=0
Coloana3,valoarea=1.91,linia=5
Coloana4,valoarea=2.15,linia=3
Coloana5,valoarea=2.09,linia=4
Coloana6,valoarea=2.04,linia=1
Coloana7,valoarea=1.97,linia=5
[ALBOT_Mihaela@hpcNotate_Exemple]$
3.2.Algoritmulinducțieirecursive(backwardinduction).
Saconsiderămjoculdinamicdetreipersoanecutreiniveleinurmătoareformăstrategică:
, :, :, :;,,     RXYZHRXYZFRXYZGXYZ undeZ,YșiXsunt
strategiilevalabileșiG,FșiHsuntfuncțiidecâștigpentrujucătorii1,2șirespectiv3.
Laprimulnivel:jucătorul1alegestrategiasaZz,șiocomunicăjucătorului2.Laaldoilea
nivel:jucătorul2observăstrategiaaleasădecătreprimuljucătorșiîșialegeindependent
strategiasaYy,dupăcareaceastaperechedestrategii(z,y)setransmitejucătorului3.Laal
treileanivel:jucătorul3observăperecheadestrategii(z,y)șiîșialegestrategiasaXx.După
aceastajoculseconsiderăfinisat.Sepresupunecajucătoriivreusă-șimaximizezefuncțiilesale
decâștig.Următorulalgoritminducțieirecursivepoategăsisoluțiipentrujocuridinamicecutrei
niveledetreijucători:
a)Jucătorul3observăstrategiaZzalprimuluijucătorșistrategiaYyaljucătorului2,el
vaalegestrategiaceamaioptimalăreieșinddinperecheadestrategii(z,y).Deci,elvaalege
următoareavaloareaceluimaibunpunctderăspunspentruasetamaparea:
XYZBR 2:3,);,,(max ),(),(3*xyzHArgyzBRyzx
Xx 
b)Jucătorul2știindcăjucătorul3v-ajucastrategiayzx,*,alegestrategiadinsetuldereacție
optimaljucatorului2pentruostrategieajucătorului1,astfelvaalegeurmătoareavaloarea
celuimaibunpunctderăspunspentruasetamaparea:YZBR2:2
));,(,,(max )()(*
2*yzxyzFArgzBRzy
Yy
c)Jucătorul1știindcajucătorul2alegestrategia)(zyșijucătorul3alegestrategiayzx,,v-
aalegeurmătoareamulțime: )))(,(),(,(max***
1*zyzxzyzGArgBRz
Zz
.
Aici2X,2YreprezintămultimeatuturorsubmultimilordinsetulXși,respectiv,Y.

39Definitie3.2.1.Profiluriledestrategie )))(,(),(,(),,(  zyzxzyzxyz descriseînetapele
a)-c)aalgoritmuluiinducțieirecursivesenumeșteProfiluldeechilibruStackelbergînjocuri
dinamiceintreinivelecutreijucători.
Considerămurmătorulsetdematrici3-diminsionale  ||,,||k
ijk
ijk
ijkcbaA șidefinimjoculcutrei
jucătoriîntreietape,unde .,…,,…,1;,…,,…,1;,…,,..,1 JmjIniKlk    estesetuldestrategii
valabileșik
ijk
ijk
ijcba,, estecâștiguljucătorilor1,2,3.Jocularelocinurmătorulfel:primul
jucătoralegestrategiakșiocomunicăjucătorului2.Înadouaetapăjucătorul2vedestrategia
aleasădeprimulșiîșialegestrategiasai,dupăcareaceastăperechedestrategii(k,i)se
comunicăjucătorului3.Înatreiaetapăjucătorul3observăalegerilecelorlalțijucătorișialege
strategiaj.Dupăaceastajoculseconsiderăfinisat.Sepresupunecăjucătoriivreusă-și
maximizezefuncțiilesaledecâștig.
Următorulalgoritminducțieirecursivepoategăsisoluțiipentrujocuridinamicecutreinivele
detreijucători:
A)Pentrutoate Klk,…,,…,1 si Ini,…,,…,1 jucătorul3v-aalegestrategiaceamaioptimală
dinurmătoareamulțimedecelemaibunerăspunsuri: ;maxarg),(|),(),(

  
jk
ijc ikjikjikJ
B)Pentrutoate Klk,…,,…,1 ,jucătorul2știindcăjucătorul3v-aalegestrategiile
ikJikj ,,alegestrategiadinmulțimea: 


    k
ikijb kikikI),(maxarg)(|)()( ;
C)Primuljucătorștiindcăaldoileajucătorv-aalegestrategiakIkișialtreileajucător
alegestrategiaikJikj ,, ,v-aalegestrategiadinceamaioptimalămulțimedereacție:
  k
kikjkikakkK))(,()(maxarg|  
Prinurmare,strategiile ))k(i,k(j),k(i,k*******definiteînpunctelea)-c)aalgoritmului
inducțieirecursivesenumescEchilibruStackelbergpentrujocuridinamicedetreijucătoripe
treinivele.Înformaextinsă,jocdinamicdescrisareurmătoareaformă:

40
Înformagraficăaetapelora)-c)aalgoritmuluiinducțieirecursivetrebuiesăfiereprezentatcum
înFigura1.
A’)Etapaa)aalgoritmuluiinducțieirecursive,deexemplupentrutoatek=1,…,l,…,Kși
i=1,…,n,…,Isubjoculobținutdupăcejucătorul3alegestrategia k
ijj*cmaxarg)i,k(j este
reprezentatăînFigura2:
B’)Etapab)aalgoritmuluiinducțieirecursive,deexemplupentrutoatek=1,…,l,…,Ksubjocul

41obținutdupăcejucătorul2alegestrategiile k
)i,k(iji*
*bmaxarg)k(i estereprezentatFigura3:
C’)Etapac)algoritmulinducțieirecursive,deexemplu“subjocul”obținutdupăcejucătorul1
alegestrategia  . amaxargkk
))k(i,k(j)k(ik*
***  estereprezentatinFigura4.
Săvedemurmătorulexemplu:
Exemplu.3.2.1Fiek=1,2,i=1,2,j=1,2șimatricile  6,5,11,0,2A1  ,




0,2,27,1,04,4,52,1,3A2.
Deciconformetapeia)algoritmulinducțierecursivenoiobținemcă ,2)1,1(j* ,2)1,2(j*
.1)2,2(j*Conformetapeib)noiobținemcă,1)1(i* .1)2(i*Conformetapeic)noiobținem
că.2k*Deaceeaprimim ,1)k(i** ,2))k(i,k(j****șiprofilulechilibruluiStackelberga
joculuieste(2,1,2).

42FolosindGambit1(SoftwareToolsforGameTheory)Version0.2007.01.30noiputemsă
reprezentămformaextinsășisoluțiilejoculuidinExemplu.3.2.1înurmătoareafigură.Jocul
inițialestereprezentatînfigura5.
Figura5.
Folosindetapaa)aalgoritmuluinoiobținem ,2)1,1(j* ,2)1,2(j* 1)2,2(j*șiexcluzînd
subramurilecorespunzătoareseobțineurmătorulsubjocFigura6:
Figura6 Figura7
Folosindetapab)aalgoritmuluiobținem ,1)1(i* 1)2(i*șiexcluzîndsubramurile
corespunzătoareobținemurmătorulsubjocFigura7.
Însfirșitconformc)alalgoritmuluinoiobținem2k*șiprofilulechilibruluiStackelbergal
joculuieste(2,1,2).
3.3.AlgoritmulparalelpentrugăsireprofiluluiechilibruluiStackelbergintreietapea
jocurilordinamicecufuncțiidiscretedecâștig.
Computereleparaleleaudouăarhitecturidebază:memoriedistributivășimemoriepartajată.
Computereleparalelecumemoriedistributivăestedefaptocolecțiedeseriidecomputere

43(noduri)celucreazăîmpreunăpentruarezolvaproblema.Fiecarenodareaccesrapidla
memorialocalăpersonalășiacceslamemoriaaltornoduriprinunfelderețeadecomunicare,de
obiceiprioritatearerețelecuvitezămare.Înformațiaesteschimbatăprintrenoduricamesajele
prinrețea.Încomputerelecumemoriepartajată,multipleunitățiaprocesoruluipartajează
accesullaunspațiuglobaldememorieprintr-omagistralădememoriedemareviteză.Acest
spațiudememorieglobalăpermiteprocesatorilorsăschimbesausăpartajezeînmodeficient
accesulladate.
Primulpasînproiectareaunuialgoritmparalelestedeadescompuneproblemaînproblememai
mici.Apoi,problemelemaimicisuntatribuiteprocesoarelorpentrualucrasimultan.
Aproximativ,existădouătipuridedescompuneri:
descompunereadomeniului.
descompunerefuncțională.
Îndescompunereadomeniuluisau"paralelismuldatelor",datelesuntîmpărțiteînbucățide
aproximativaceeașidimensiuneșiapoicartografiateladiferiteprocesoare.Fiecareprocesor
funcționeazăapoinumaipeporțiuneadedatecareîiesteatribuită.Desigur,esteposibilca
proceselesătrebuiascăsăcomuniceperiodicpentruafaceschimbdedate.Paralelismuldedate
oferăavantajulmențineriiunuisingurfluxdecontrol.Unalgoritmparaleldedateconstădintr-o
secvențădeinstrucțiunielementareaplicatedatelor:oinstrucțiuneesteinițiatănumaidacă
instrucțiuneaanterioarăseîncheie.Single-Program-Multiple-Data(SPMD)urmeazăacestmodel
încazulîncarecodulesteidenticpetoateprocesoarele.Astfeldestrategiisuntutilizateînmod
obișnuitînalgoritmiidediferențierefinită,undeprocesoarelepotfuncționaindependentpe
porțiunimaridedate,comunicândnumaidateledegranițămultmaimicilafiecareiterație.
Frecvent,strategiadedescompunereadomeniuluisedovedeșteaficelmaieficientalgoritm
pentruunprogramparalel.Acestaestecazulatuncicândpieselededateatribuitediferitelor
procesenecesităperioadefoartediferitedetimppentruprocesare.Performanțacoduluiesteapoi
limitatădevitezaceluimailentproces.Restulproceselorînașteptarenufacnicioactivitateutilă.
Înacestcaz,descompunereafuncționalăsau"paralelismulsarcinilor"aremaimultăsensdecât
descompunereadomeniului.Înparalelismulsarcinii,problemaestedescompusăîntr-unnumăr
maredesarcinimaimicișiapoisarcinilesuntatribuiteprocesorilorînmomentulîncaredevin
disponibile.Procesoarelecareterminarepedesuntpurșisimpluatribuitemaimultămuncă.
Paralelismulsarciniloresteimplementatîntr-oparadigmăclient-server.Sarcinilesuntalocate
unuigrupdeproceseslaveprintr-unprocesmaster,carepoateîndeplinișianumitesarcini.
Paradigmaclient-serverpoatefiimplementatălaaproapeoriceniveldintr-unprogram.Dinpunct
devedereistoric,auexistatdouăabordăripentruscriereaprogramelorparalele.Sunt

44utilizareauneilimbiparalelededatebazatepedirective;
transmitereamesajuluiextinsprinapelurilebiblioteciidinlimbiledeprogramarestandard.
Într-olimbădedateparalelăbazatăpedirective,cumarfiHighPerformanceFortran(HPF)sau
OpenMP,uncodserialesteparalelprinadăugareadedirective(careaparcacomentariiîncodul
serial)careîispuncompilatoruluicumsădistribuiedateșisălucrezede-alungulprocesoarelor.
Detaliileprivinddistribuireadatelor,calcululșicomunicăriletrebuiesăfielăsatecompilatorului.
Limbileparalelededatesuntdeobiceiimplementatepearhitecturiledememoriepartajată,
deoarecespațiuldememorieglobalăsimplificăfoartemultscriereacompilatoarelor.În
abordareadetransmitereamesajelor,estelăsatdecătreprogramatorsăîmpartăînmodexplicit
dateleșisălucrezeîntreprocesoare,precumșisăgestionezecomunicațiiledintreele.Această
abordareestefoarteflexibilă.
Interfațadetransmitereamesajelor(MPI)esteobibliotecăstandardfolosităpescarălargă
pentruscriereaprogramelordetrecereamasajului,înspecialpemașinileparalelecumemorie
distribuită.Pentruarhitecturilecalculatoarelorparalelecumemoriedistribuităamproiectatun
algoritmparalelpentrudeterminareaprofiluluideechilibruStackelbergînjoculdescrismaisus.
FolosimurmătoarelefuncțiiMPIpentruimplementareasoftware-uluialgoritmuluideinducție
inversădescrisînetapelea)-c).RutinaMPI_comm_groupdeterminămâneruldegrupalunui
comunicator.RutinaMPI_Group_inclcreeazăungrupnoudintr-ungrupexistentșispecifică
proceselemembrilor.RutinaMPI_Comm_createcreeazăunnoucomunicatorpentruainclude
procesespecificedelauncomunicatorexistent.FuncțiaMPI_Type_structestecelmaigeneral
moddeaconstruiuntipderivatMPI,deoarecepermitecalungimea,locațiașitipulfiecărei
componentesăfiespecificateindependent.Suntdisponibileprocedurimaipuțingeneralepentru
adescriemodelecomunedeacces,înspecialîncadrulrețelelor.RutinaMPI_Bcastvăpermite
săcopiațidateledinmemoriaprocesoruluirădăcinăînaceleașilocațiidememoriepentrualte
procesoaredincomunicator.RutinaMPI_Scatteresteocomunicareunu-la-toate.Datelediferite
sunttrimisedelaprocesulrădăcinălafiecareproces(înordinederang).Atuncicândsenumește
MPI_Scatter,procesulderădăcinărupeunsetdelocațiidememoriecontigueînegalăbucățiși
trimiteobucatălafiecareprocesor.RutinaMPI_Reducepermitecolectareadedatedelafiecare
procesor,reducereaacestordatelaosingurăvaloare(cumarfisumsaumax)șistocarea
rezultatuluireduspeprocesorulrădăcină.MPI_Allreduceestefolositpentruacombina
elementelefiecăruitampondeintrarealfiecăruiprocesșistocheazăvaloareacombinatăpe
tamponulprimitaltuturormembrilorgrupului.Înplus,funcțiaMPI_Reducecombină

45elementelefurnizateînbufferuldetrimitere,aplicăoperațiaspecificată(sum,min,max,etc)și
returneazărezultatullatamponulprimitalprocesuluirădăcină.
PașiidebazăaialgoritmuluiparaleldeagăsiprofiluldeechilibruStackelbergînjocurile
dinamicedetreinivelurisuntdescrisedupăcumurmează:
1)FolosindfuncțiileMPIMPI_comm_group,MPI_Group_inclșiMPI_Comm_create
creămnoulcomunicator,deexempluMPI_Comm_Slaveșinoulgrupdeprocese
MPI_Goup_Slave.NumărultotaldeprocesoarealeacestorcomunicatoriesteegalcuK*I.
Numaiprocesulacestuicomunicatorvaparticipalaimplementareasoftaalgoritmuluide
inducțieinversă.Pentru"paralelismuldedate"alalgoritmuluifolosimabordareadetransmiterea
mesajelor,implementatădefuncțiileMPIșiconstăînurmătoriipașidebază.
2)UnuldintreproceselecomunicatoruluiMPI_Comm_Slave(deexempluprocesulcu
rangulegalcuroot)ainițializatmatricile







K
IJK
IJK
IJK
ImK
ImK
ImK
1IK
1IK
1Il
nJl
nJl
nJl
nml
nml
nml
1nl
1nl
1n1
J11
J11
J11
m11
1m1
m11
111
111
11
c,b,ac,b,ac,b,ac,b,ac,b,ac,b,ac,b,ac,b,ac,b,a
           

șiutilizândfuncțiileMPIaudistribuitrândurileacestormatrici(unrândpefiecareproces)
tuturorproceselorcomunicatoruluiMPI_Comm_Slave.Acesteasepotfacedupăcumurmează:
2.1.UtilizațifuncțiileMPI_Type_struct,MPI_Type_commitșiMPI_Addresspentrua
construimatricea,fiecareelementalcăruiaesteotuplăaformuleik
ijk
ijk
ijc,b,a
unde ,,…,1Kk Ii,…,1si .,…,1JjAcestenoidatedetipderivatedelaMPIreduc
latența(Latențaestetimpulnecesarpentruatrimiteunmesajde8octețidelaunnodlaaltul
decomunicațiiînrețeautilizândrutineMPIdebază)decomunicareîntreprocese.
2.2.FuncțiaMPI_BcastdistribuitătuturorproceseazăvaloareaK,IșiJ.
2.3.FolosindfuncțiileMPI_Scatterdistribuimrândurileconstruiriimatriceiînpasul2.1
pentruprocesareagrupuluiMPI_Goup_Slave.Deci,fiecareprocescuikrang,(dacăse
foloseștecomunicatorulcutopologiaDecartes)sau ikrang*dinnumărultotalde
proceseK*Ivaprimidinprocescurădăcinăderangurmătorulvector
  k
iJk
iJk
iJk
imk
imk
imk
1ik
1ik
1i c,b,ac,b,ac,b,a   pentru ,,…,1Kk,Ii,…,1.Procesulcu
rangulikppentru ,,…,1Kk Ii,…,1 folosindvectorul k
iJk
imk
1ik
i c,…,c,…,cC,

46 k
iJk
imk
1ik
i b,…,b,…,bB, k
iJk
imk
1ik
i a,…,a,…,aA primitpotconstruivectorii,utilizațipentru
operațiiledereducere.
Astfel,paralelizareadateloralgoritmuluipentruagăsiprofiluldeechilibruStackelbergîn
jocuriledinamicedetreiniveluricufuncțiidiscretedeplatăsuntfinalizate.
"Paralelismulsarcinilor"alalgoritmuluideinducțieinversăesteimplementatsoftfolosind
operațiadereducere.Acestlucruesteprezentatînurmătoareleetape.
3)FolosindoperațiadereducereMPI_MAXLOCconstruimonouăoperațiedereducere
numităMPI_ALLMAXLOCpentruacalculatotmaximulglobalșitotindexulatașatlarangul
procesuluicareconținevaloareamaximă.Deci,totprocesulcurangulikp, ,,…,1Kk
Ii,…,1,folosindfuncțiaMPI_ReducecuoperațiadereducereMPI_ALLMAXLOCși
adresatamponuluitrimisreprezintăvectorulk
iCdeterminătoatevalorile k
njj*cmaxarg)i,k(j și
săstochezeacestevaloriînbuffer-ulprocesuluicurădăcinăderang.Pedealtăparte,folosind
operațiadereducereMPI_ALLMAXLOC,vomdeterminaelementulmaximșiindiciide
coloanăailiniilordinmatriceaurmătoarecurânduriK*IșicoloaneJ:




K
IJK
ImK
1Il
nJl
nml
1n1
J11
m11
11
ccccccccc
   
Deaceea,rezolvămsimultanproblemeledeoptimizarealeceluide-altreileaniveldeforma
extinsăajocului(veziFigura2).Astfel,folosindfuncțiaMPI_Reducecuoperațiadereducere
MPI_ALLMAXLOC,cuprocesulrangrootvafiobținutvectorulculungimeaK*Icuelemente
 )I,K(j),n,K(j,),1,K(j,),I,l(j),n,l(j,),1,l(j,),I,1(j,),n,1(j,),1,1(jJ* * * * * * * * **        .Dupăaceasta,
folosindfuncțiaMPIMPI_Scatterfiecareproceseazăcurankp=k, ,,…,1Kk obținedela
procescurădăcinăderangvectorul )I,k(j),n,k(j,),1,k(j)k(J* * **  careseutilizeazăînetapa
următoare.
4)Pentrutoateproceselecurankrankp=k, ,,…,1KkfolosindfuncțiaMPI_Reduce
cuoperațiadereducereMPI_ALLMAXLOCșiadresatamponuluitrimisreprezintăprinvector
   k
I,kIjk
n,knjk
1,kj1* * * b,,b,,b   toateproceselecomunicatoruluiMPI_Comm_Slave
determinătoatevalorile k
)i,k(iji*
*bmaxarg)k(i șipăstrațiacestevaloriînbuffer-ulprocesului
rankroot.Încealaltăparte,folosindoperațiadereducereMPI_ALLMAXLOC,vomdetermina
elementulmaximșiindiciidecoloanăailiniilordinmatriceaurmătoarecurânduriKșicoloaneI:

47  
  
  T
K
I,KIjK
n,KnjK
1,Kj1l
I,lIjl
n,lnjl
1,lj11
1,1j11
n,1nj1
1,1j1
* * ** * ** * *
b b bb b bb b b




   
Cualtecuvinte,rezolvămconcomitentproblemeledeoptimizarealeceluide-aldoileanivelde
formăextinsăajocului(veziFigura3).NumărultotaldeprocesedeutilizareesteegalcuK.
Astfel,folosindfuncțiaMPI_ReducecuoperațiadereducereMPI_ALLMAXLOCseva
determinavectorullungimiiKcuelemente )K(i,),l(i,),1(iI**** caresuntstocateînmemoria
rădăciniiprocesului.
5)Procesulrankrootfolosindvectorii )K(i),…,l(i),…,1(iI**** delapasul4)și,
 ))I(i,K(j)),…,l(i,l(j)),…,1(i,1(j** ** **careesteobținutdinvectoruldinetapa3)realizează
pasulc)alalgoritmuluideinducțieinversășitipăreșteprofiluldeechilibruStackelberg
***j,i,k aljoculuidinamicdetreiniveluricudiscretfuncțiideplată.Pedealtăparte,
procesulrootdeterminăelementulmaximșiindiciaivectoruluiurmător(Figura4).




K
)I(*i,K*j)K(*il
)l(*i,l*j)l(*i1
)1(*i,1*j)1(*ia a a  
Prinaceasta,descriereaalgoritmuluisetermină.Pentruevaluareaperformanțeiîntimpa
algoritmuluiparalelseutilizeazăurmătoareledouăcaracteristicinumerice:timpultotalde
rezolvatpeuncalculatorparalelcuprocesorPșiaccelerareaobținutăprinalgoritmulparalel.
Accelerarea)K(T)K(T)(S
PP ,undeT(K)denotăcomplexitateasecvențialăaalgoritmului,TP(K)
indicătimpulpentrurezolvareaproblemeifolosindalgoritmulparalel,măsoarăfactorulde
accelerareobținutdealgoritmulparalelcândsuntdisponibiliprocesoareleP.AiciKindica
dimensiuneadeintrareaproblemei.
Sădemonstrămteoremaurmătoaredesprecorectitudineaalgoritmuluiparaleldescrisînpașii1)
-5)șisăestimămtimpultotalșivitezapentruagăsiprofiluldeechilibruStackelbergînjocul
dinamiccutreiniveluricufuncțiidiscretedeplatăfolosindacestalgoritm.
Teorema.3.2.1.Algoritmulparalel,descrisdepașii1)-5),calculeazăînmodcorectprofilulde
echilibruStackelbergînjocuriledinamicedetreiniveluricufuncțiediscretedeplată.Acest

48algoritmruleazăla)JIK timpfolosindunnumărtotal)IK( deprocesoare.
Accelerareaalgoritmuluiparalelesteegalăcu
JIK)K(IKJIK

  .
Demonstratie.Dovadacorectitudiniialgoritmuluiestesimplă.Săpresupunemcăalgoritmul
secvențialpentruagăsielementulmaximîntr-olistă k
iJk
imk
2ik
1ik
i c,…,c,…,c,cC este)J(.Apoi,
pasula)alalgoritmuluideinducțieinversăpentruoperațiiledesolicitare )JIK( dinamicăa
jocului.FolosindsistemulparalelcuprocesoareK*I(procesesaufire),variantaparalelăa
algoritmului,adicătreapta3),are)J(operațiuni.Similar,etapab)implementatăpesistemul
secvențialpreia)IK(operațiunile.SistemulparalelcuprocesorulK,pasul4)alalgoritmului
paralelia)I(.Înceledinurmă,etapac)seia)K(careesteegalăcucerereadeoperarea
pasului5).Prinurmare,algoritmulparaleldescrisdepașii1)-5)ia)JIK operațiifolosind
)IK(procese(procesoare).Accelerareaacestuialgoritmesteegalăcu

JIK)K(IKJIK)JI(S)IK(   .
Descriereaprogramuluiparalelelaborat
Programulelaboratutilizeazăarhitecturamaster-slavepentruacalculaechilibrulStackelberg.
Astfel,procesulcuidentificatorulzeroinițializeazămatriceaprofiturilorșidistribuiesarcinile
celorlalteprocesedincomunicator.Matriceaprofituriloresteomatrice4-dimenională,iar
elementulA[i][j][k][l]reprezintăprofituljucătoruluicunumărullpentrustrategia(i,j,k).
LaprimaetapăprocesulmasterinițializeazămatriceaprofiturilorAșitransmitecelorlalte
procesedimensiunileacesteia.
Laadouaetapăserezolvăprimulpunctdinalgoritmuldescrismaisus.Astfel,matriceaAeste
împărțităînsarcini,undeIșiJreprezintănumereledestrategiialeprimilordoijucători
respectiv.Procesulmasterdistribuieperândcâteosarcină(i,j)fiecăruiprocesslaveși
înregistreazărezultatulthaîntr-omatricebidimensionalăB.Lasfârșitulacesteietapese
obținematriceaBcareconținestrategiileoptimalepentrujucătorulaltreilea.
LaatreiaetapăprocesulmasterîmpartematricileAșiBînIsarcini.Acestesarcinisunt
distribuiteproceselorslave,iarînrezultatseobținevectorulCcustrategiileoptimaleale
jucătoruluialdoilea.Laaceastăetapăserezolvăaldoileapunctdinalgoritmuldescrismaisus.
Laapatraetapăprocesulmasterrezolvăaltreileapunctdinalgoritmuldescrismaisus,
determinândstrategiaoptimalăpentruprimuljucător.Înrezultatseobținenumărulicare
reprezintăstrategiadeechilibruaprimuluijucător,iarechilibrulStackelbergvafi(i,C[i],B[i,

49C[i]]).
Programulelaborateafosttestatpentruurmatoruljocdinamic
TextulintegralalprogramuluiinlimbajulC++esteprezentatinanexa.

50Concluziișirecomandări:
Lucrulasupratezeidelicențămi-aoferitposibilitateadea-misuplimentapregătirea
profesionalăcuoinstruireavansatăindomeniuldeinteresștiințific,șianumecelalmatematicii
aplicate.IncadrulCECMIafostcreatunLaboratorpentruutilizareasistemelorparalelede
calculdetipcluster.Datorităacestuilaboratoramimplementatinprocesuldeinstruireși
cercetarenoiletehnologiipentruelaborareaalgoritmuluiparalelșiexecutarealuipesisteme
localedetipcluster.AmutilizatșianalizatcumlucreazăfuncțiileMPIutilizatelaparalelizarea
datelorinprogrameparalele.Cunoștințeleobținutem-auajutatlaelaborareaprogramuluiparalel
pentrudeterminareasoluțiilorajocurilordinamicebayesiene,rezultatulprogramuluieste
prezentatmaisus.Programulobținutușureazășiminimizeazătimpuldestinatcalculelor,ceeace
eunmarebeneficiuînzilelenoastre.

51Bibliografie:
1.VonStackelbergH.,TheTheoryoftheMarketEconomy,OxfordUniversityPress,Oxford.
England.1952.
2.HancuBoris,ThefullsetofStackelbergequilibriumprofilesinthemultileveldynamic
games.The33-rdAnnualCongressoftheAmericanRomanianAcademyofArtsandSciences
(ARA).Sibiu,Romania.June02-07,2009.Proceedings,VolumeII,PolytechnicInternational
Press,Montreal,Quebec,2009,pp.301-303.
3.MPI-2:ExtensionstotheMessage-PassingInterface.MessagePassingInterfaceForum.
November15,2003
4.JosephJaja.AnIntroductiontoParallelAlgorithms.Addison-WesleyPublishingCompany,
NewYork.1992.

52Anexă
Programuldebaza.
#include<iostream>
#include<mpi.h>
#include<vector>
#include<fstream>
#include"stack_types.h"
usingstd::vector;
usingstd::cout;
usingstd::endl;
usingstd::cerr;
usingstd::ifstream;
#defineTAG_WORK11
#defineTAG_WORK22
#defineTAG_STOP13
#defineTAG_STOP24
#defineTAG_DIE 5
#defineTAG_WORK226
#pragmacomment(lib,"mpi.lib")
//typedefintElemType[3];
voidMaster(intargc,char*argv[]);
voidSlave();
intmain(intargc,char*argv[])
{
intrank=0;
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&rank);
if(rank==0)
{
Master(argc,argv);
}
else
{
Slave();
}
MPI_Finalize();
return0;
}
boolReadMatrix(PayoffMatrix*pm,constchar*fileName)
{
if(pm==NULL)
returnfalse;
if(fileName==NULL)
returnfalse;
intn1=0,n2=0,n3=0;
int*ptr=NULL;
ifstreamstream;
stream.open(fileName);
stream>>n1>>n2>>n3;
pm->Resize(n1,n2,n3);
ptr=pm->GetPtr();
for(inti1=0;i1<n1;++i1)
for(inti2=0;i2<n2;++i2)

53for(inti3=0;i3<n3;++i3)
{
stream>>ptr[0]>>ptr[1]>>ptr[2];
ptr+=3;
}
stream.close();
returntrue;
}
voidPrintSyntax();
voidMaster(intargc,char*argv[])
{
PayoffMatrixpm;//Payoffmatrix.
inttmp=0;
intnp=0; //Numberofprocesses.
MPI_Statusstatus;
Result1result1;//Step1result.
Result2result2;//Step2result.
MPI_Comm_size(MPI_COMM_WORLD,&np);
if(np<2)
{
cerr<<"Programultrebuierulatpecelputin2procese."<<endl;
return;
}
if(argc!=2)
{
PrintSyntax();
tmp=0;
MPI_Bcast(&tmp,1,MPI_INT,0,MPI_COMM_WORLD);
MPI_Bcast(&tmp,1,MPI_INT,0,MPI_COMM_WORLD);
MPI_Bcast(&tmp,1,MPI_INT,0,MPI_COMM_WORLD);
return;
}
if(!ReadMatrix(&pm,argv[1]))
{
cerr<<"Matriceanupoateficitita."<<endl;
tmp=0;
MPI_Bcast(&tmp,1,MPI_INT,0,MPI_COMM_WORLD);
MPI_Bcast(&tmp,1,MPI_INT,0,MPI_COMM_WORLD);
MPI_Bcast(&tmp,1,MPI_INT,0,MPI_COMM_WORLD);
return;
}
#pragmaregionBroadcastpayoffmatrixdimensions
tmp=pm.N1();
MPI_Bcast(&tmp,1,MPI_INT,0,MPI_COMM_WORLD);
tmp=pm.N2();
MPI_Bcast(&tmp,1,MPI_INT,0,MPI_COMM_WORLD);
tmp=pm.N3();
MPI_Bcast(&tmp,1,MPI_INT,0,MPI_COMM_WORLD);
#pragmaendregion
#pragmaregionStep1
{

54vector<Task1>tasks;
Task1tmpTask;
TaskScheduler1ts(&pm);
MPI_DatatypesendType=MPI_DATATYPE_NULL;
MPI_Type_vector(pm.N3(),1,3,MPI_INT,&sendType);
MPI_Type_commit(&sendType);
result1.Resize(pm.N1(),pm.N2());
for(inti=1;i<np&&ts.GetNextTask(&tmpTask);++i)
{
tasks.push_back(tmpTask);
MPI_Send(tmpTask.buffer,1,sendType,i,TAG_WORK1,
MPI_COMM_WORLD);
}
while(ts.GetNextTask(&tmpTask))
{
MPI_Recv(&tmp,1,MPI_INT,MPI_ANY_SOURCE,MPI_ANY_TAG,
MPI_COMM_WORLD,&status);
*result1.GetPtr(tasks[status.MPI_SOURCE-1].index1,
tasks[status.MPI_SOURCE-1].index2)=tmp;
tasks[status.MPI_SOURCE-1]=tmpTask;
MPI_Send(tmpTask.buffer,1,sendType,status.MPI_SOURCE,
TAG_WORK1,MPI_COMM_WORLD);
}
for(inti=0;i<tasks.size();++i)
{
MPI_Recv(&tmp,1,MPI_INT,MPI_ANY_SOURCE,MPI_ANY_TAG,
MPI_COMM_WORLD,&status);
*result1.GetPtr(tasks[status.MPI_SOURCE-1].index1,
tasks[status.MPI_SOURCE-1].index2)=tmp;
}
MPI_Type_free(&sendType);
for(intrank=1;rank<np;++rank)
{
MPI_Send(NULL,0,MPI_INT,rank,TAG_STOP1,
MPI_COMM_WORLD);
}
}
#pragmaendregion
#pragmaregionStep2
{
vector<Task2>tasks;
Task2tmpTask;
TaskScheduler2ts(&pm,&result1);
MPI_DatatypesendType=MPI_DATATYPE_NULL;
MPI_Type_vector(pm.N2()*pm.N3(),1,3,MPI_INT,&sendType);
MPI_Type_commit(&sendType);
result2.Resize(pm.N1());
for(inti=1;i<np&&ts.GetNextTask(&tmpTask);++i)
{
tasks.push_back(tmpTask);
MPI_Send(tmpTask.values2,1,sendType,i,TAG_WORK2,
MPI_COMM_WORLD);
MPI_Send(tmpTask.positions3,pm.N2(),MPI_INT,i,TAG_WORK22,
MPI_COMM_WORLD);
}

55while(ts.GetNextTask(&tmpTask))
{
MPI_Recv(&tmp,1,MPI_INT,MPI_ANY_SOURCE,MPI_ANY_TAG,
MPI_COMM_WORLD,&status);
*result2.GetPtr(tasks[status.MPI_SOURCE-1].index1)=tmp;
tasks[status.MPI_SOURCE-1]=tmpTask;
MPI_Send(tmpTask.values2,1,sendType,status.MPI_SOURCE,
TAG_WORK2,MPI_COMM_WORLD);
MPI_Send(tmpTask.positions3,pm.N2(),MPI_INT,status.MPI_SOURCE,
TAG_WORK22,MPI_COMM_WORLD);
}
for(inti=0;i<tasks.size();++i)
{
MPI_Recv(&tmp,1,MPI_INT,MPI_ANY_SOURCE,MPI_ANY_TAG,
MPI_COMM_WORLD,&status);
*result2.GetPtr(tasks[status.MPI_SOURCE-1].index1)=tmp;
}
MPI_Type_free(&sendType);
for(intrank=1;rank<np;++rank)
{
MPI_Send(NULL,0,MPI_INT,rank,TAG_STOP2,
MPI_COMM_WORLD);
}
}
#pragmaendregion
#pragmaregionStep3
{
intindex1=0;
intindex2=*result2.GetPtr(index1);
intindex3=*result1.GetPtr(index1,index2);
intmax=pm.GetPtr(index1,index2,index3)[0];
for(inti1=1;i1<pm.N1();++i1)
{
inti2=*result2.GetPtr(i1);
inti3=*result1.GetPtr(i1,i2);
intm=pm.GetPtr(i1,i2,i3)[0];
if(m>max)
{
max=m;
index1=i1;
index2=i2;
index3=i3;
}
}
//TheStackelbergequilibriumis(index1,index2,index3).
cout<<"EchilibrulStackelbergeste:("<<index1<<","<<index2<<","<<
index3<<")cuprofitul("<<
pm.GetPtr(index1,index2,index3)[0]<<","<<
pm.GetPtr(index1,index2,index3)[1]<<","<<
pm.GetPtr(index1,index2,index3)[2]<<")."<<endl;
}
#pragmaendregion
}
intSolveTask1(int*player3Payoff,intn3)

56{
if(player3Payoff==NULL)
return-1;
if(n3<=0)
return-1;
intpos=0;
intmax=player3Payoff[pos];
for(inti=1;i<n3;++i)
{
if(player3Payoff[i]>max)
{
max=player3Payoff[i];
pos=i;
}
}
returnpos;
}
intSolveTask2(int*player2Payoff,int*player3Strategy,intn2,intn3)
{
if(player2Payoff==NULL)
return-1;
if(player3Strategy==NULL)
return-1;
if(n2<=0)
return-1;
if(n3<=0)
return-1;
intpos=0;
intmax=player2Payoff[pos*n3+player3Strategy[pos]];
for(inti=1;i<n2;++i)
{
if(player2Payoff[i*n3+player3Strategy[i]]>max)
{
max=player2Payoff[i*n3+player3Strategy[i]];
pos=i;
}
}
returnpos;
}
voidSlave()
{
intn1=0,n2=0,n3=0;
MPI_Bcast(&n1,1,MPI_INT,0,MPI_COMM_WORLD);
MPI_Bcast(&n2,1,MPI_INT,0,MPI_COMM_WORLD);
MPI_Bcast(&n3,1,MPI_INT,0,MPI_COMM_WORLD);
if(n1<=0||n2<=0||n3<=0)
return;
#pragmaregionSolveTask1
{
int*player3Payoff=newint[n3];
intmax=0;
intpos=0;
MPI_Statusstatus;
boolstop=false;
while(!stop)

57{
MPI_Recv(player3Payoff,n3,MPI_INT,0,MPI_ANY_TAG,
MPI_COMM_WORLD,&status);
switch(status.MPI_TAG)
{
caseTAG_DIE:
delete[]player3Payoff;
return;
caseTAG_STOP1:
delete[]player3Payoff;
stop=true;
break;
caseTAG_WORK1:
{
intpos=SolveTask1(player3Payoff,n3);
MPI_Send(&pos,1,MPI_INT,0,0,MPI_COMM_WORLD);
}
break;
default:
//Unexpectedtag.
exit(1);
}
}
}
#pragmaendregion
#pragmaregionSolveTask2
{
int*player2Payoff=newint[n2*n3];
int*player3Strategy=newint[n2];
MPI_Statusstatus;
boolstop=false;
while(!stop)
{
MPI_Recv(player2Payoff,n2*n3,MPI_INT,0,MPI_ANY_TAG,
MPI_COMM_WORLD,&status);
switch(status.MPI_TAG)
{
caseTAG_DIE:
delete[]player2Payoff;
delete[]player3Strategy;
return;
caseTAG_STOP2:
delete[]player2Payoff;
delete[]player3Strategy;
stop=true;
break;
caseTAG_WORK2:
{
intpos=-1;
MPI_Recv(player3Strategy,n2,MPI_INT,0,
TAG_WORK22,MPI_COMM_WORLD,&status);
pos=SolveTask2(player2Payoff,player3Strategy,n2,n3);
MPI_Send(&pos,1,MPI_INT,0,0,MPI_COMM_WORLD);
}
break;

58default:
exit(1);
}
}
}
#pragmaendregion
}
voidPrintSyntax()
{
cerr<<"Sintaxa:stackelbergmatrice"<<endl;
cerr<<"\tmatrice-fisierulcumatriceaprofiturilor"<<endl;
Programulauxiliar
ifndef_STACKELBERG_TYPES_H
#define_STACKELBERG_TYPES_H
#include"mpi.h"
structPayoffMatrix
{
//Classvariables.
private:
int*_data;
int_n1;
int_n2;
int_n3;
//Publicmethods.
public:
PayoffMatrix(intn1=0,intn2=0,intn3=0);
int*GetPtr(intindex1=0,intindex2=0,intindex3=0);
voidResize(intn1,intn2,intn3);
intN1()const{return_n1;}
intN2()const{return_n2;}
intN3()const{return_n3;}
~PayoffMatrix();
//Privatemethods.
private:
voidFree();
};
structTask1
{
void*buffer;
intindex1;
intindex2;
Task1()
:buffer(NULL),index1(0),index2(0)
{}
};
classTaskScheduler1
{
private:
PayoffMatrix*_payoffMatrix;
int_index1;
int_index2;

59public:
TaskScheduler1(PayoffMatrix*pm=NULL);
boolGetNextTask(Task1*task);
voidSetMatrix(PayoffMatrix*pm);
PayoffMatrix*GetMatrix()const;
voidReset();
};
classResult1
{
private:
int*_data;
int_n1;
int_n2;
public:
Result1(intn1=0,intn2=0);
~Result1();
voidResize(intn1,intn2);
intN1()const{return_n1;}
intN2()const{return_n2;}
int*GetPtr(intindex1=0,intindex2=0);
private:
voidFree();
};
structTask2
{
int*values2; //ValorileA[i,j,k]pentrujucatorul2pentru[i=index1].
int*positions3;//Pozitiiledemaximalejucatorului3pentru[i=index1,j=0..n2-1].
intindex1;
Task2()
:values2(NULL),positions3(NULL),index1(0)
{}
};
classTaskScheduler2
{
private:
PayoffMatrix*_payoffMatrix;
Result1*_result1;
int_index1;
public:
TaskScheduler2(PayoffMatrix*pm=NULL,Result1*result1=NULL);
boolGetNextTask(Task2*task);
PayoffMatrix*GetPayoffMatrix()const;
voidSetPayoffMatrix(PayoffMatrix*pm);
Result1*GetStep1Result()const;
voidSetStep1Result(Result1*result);
voidReset();
};
classResult2
{
private:
int*_data;
int_n1;
public:
Result2(intn1=0);

60~Result2();
voidResize(intn1);
intN1()const{return_n1;}
int*GetPtr(intindex1=0);
private:
voidFree();
};
#endif

61