35
Curs 1 Programare Paralela si Distribuita Curs 1 - PPD - 2
Curs1
ProgramareParalelasiDistribuita
Curs 1 - PPD - 2
Con4nutulcursului(realizatsipebazapeh:p://grid.cs.gsu.edu/~tcpp/curriculum/?q=home)
Teore%c• No4uniintroduc4ve:arhitecturi,
concurenta,paralelism• Etapeindezvoltareaprogramelorparalele• Evaluareaperformanteiprogramelor
paralele• Modeledeprogramareparalela
– Diferentaintrecelebazatepememoriepartajatasimemoriedistribuita
• Pa#erns– Ptprogramareparalela– Ptprogramaredistribuita
Prac%c• Javathreads(lowlevelAPI)• C++(C++11)threads• High-levelAPI:pacheteJava->
java.u4l.concurrentpackages.• Javastreams• OpenMP(C++)• CUDA(C++)• MPI–MessagePassingInterface
– exemplificariC,C++
Curs 1 - PPD - 3
Bibliografie• IanFoster.DesigningandBuildingParallelPrograms,Addison-Wesley1995.• BernaL.Massingill,TimothyG.Ma:son,andBeverlyA.Sanders,AddisonAPa:ernLanguagefor
ParallelProgramming.WesleySodwarePa:ernsSeries,2004.• MichaelMcCool,ArchRobinson,JamesReinders,StructuredParallelProgramming:Pa:ernsfor
EfficientComputa4on,”MorganKaufmann,,2012.• D.Culler,J.PalSingh,A.Gupta.ParallelComputerArchitecture:AHardware/SodwareApproach.
MorganKaufmann.1998.• Grama,A.Gupta,G.Karypis,V.Kumar.Introduc4ontoParallelCompu4ng,AddisonWesley,2003.• D.Grigoras.CalcululParalel.Delasistemelaprogramareaaplica4ilor.ComputerLibrisAgora,2000.• V.Niculescu.CalculParalel.Proiectaresidezvoltareformalaaprogramelorparalele.PresaUniv.
Clujana,2006.• B.Wilkinson,M.Allen,ParallelProgrammingTechniquesandApplica4onsUsingNetworked
Worksta4onsandParallelComputers,Pren4ceHall,2002• A.Williams.C++ConcurrencyinAc4onPRACTICALMULTITHREADING.ManningPublisher.2012.• TutorialeJava:h:p://docs.oracle.com/javase/tutorial/essen4al/concurrency/further.html• C++11h:p://en.cppreference.com/w/• OpenMP:h:p://openmp.org/• MPI:h:p://www.mpi-forum.org/
Curs 1 - PPD - 4
Evaluare
• Laborator(25%)– Exerci4ilaborator– ProgramefolosindJava/C++threads,OpenMP,MPI
• Seminar(10%)– prezenta,par4cipareac4va
• Testeprac4ce–3X10%• Examen
– Scris– sesiune35%
• Informa4icurs– h:p://www.cs.ubbcluj.ro/~vniculescu/didac4c/PPD/CursPPD.html
5Curs 1 - PPD -
ProcesareParalela
• Uncalculatorparalelesteuncalculator(sistem)carefolosestemul%pleelementedeprocesaresimultanaintr-omanieracoopera%vapentruarezolvaoproblemacomputa%onala.
• ProcesareaParalelaincludetehnicisitehnologiicarefacposibilcalcululinparalel– Hardware,retele,SO,biblioteci,limbaje,compilatoare,algoritmi…
• Paralelismulestenatural.
• PERFORMANTA– Parallelismisverymuchaboutperformance!
6Curs 1 - PPD -
Curs 1 - PPD - 7
CalculSerialvs.Paralel(imagesfromIntroduc%ontoParallelCompu%ngBlaiseBarney)
Itwouldappearthatwehavereachedthelimitsofwhatitispossibletoachievewithcomputertechnology,althoughoneshouldbecarefulwithsuchstatements,astheytendtosoundpre9ysillyin5years.(JohnvonNeumann,1949)
Curs 1 - PPD - 8
Curs 1 - PPD - 9
Limitealeprogramariiseriale• Vitezadetransmisie–
• Vitezaluminii(30cm/nanosecond),limitadetransmisiepefirdecupru(9cm/nanosecond).
• Limitareaminiaturizarii–numardetrazistoripechip.– LegealuiMoore:număruldetranzistori
carepotfiplasa4peussingurcircuitintegrat(persquareinchchip)sedubleazalafiecare2ani.
– Darimpunecosturimari.
• Limitarieconomice
Istoric
• CrestereaperformanteiprocesorprincrestereafrecventeiceasuluiCPU(CPUclockfrequency)– RidingMoore’slaw
• Probleme:incalzireaputernicaachipurilor!– Frecventaceasmaimare⇒consumelectricmaimare(Pen:um4heatsink¦FryinganeggonaPen:um4)
• Solu4e–adugaremaimultorcore-uriptaajungelaperformantadorita– Sepastreazafrecventadeceaslafelsauchiarmicsorare– nucresteconsumul.
Curs 1 - PPD - 10
Nivelurideparalelism
1.paralelismlaniveldejob:-intrejoburi;-intrefazealejoburilor;2.paralelismlaniveldeprogram:-intrepărţialeprogramului;-inanumitecicluri;3.paralelismlaniveldeinstrucţiune:
-intrediferitefazedeexecuţiealeuneiinstrucţiuni;4.paralelismlanivelaritme%cşilaniveldebit:- intreelementealeuneioperaţiivectoriale;- intrecircuitelelogiciiaritme4ce.
Curs 1 - PPD - 11
• Arhitecturilecurentesebazeazatotmaimultpeparalelismlanivelhardwarepentruaimbunata4performanta:
– Mul4pleexecu4onunits– Pipelinedinstruc4ons– Mul4-core
Curs 1 - PPD - 12
Paralelism<->Concurenta
• Considerammaimultetaskuricaretrebuieexecutatepeuncalculator• Taskurileseconsideraafipurparaleledaca:
– Sepotexecutainacelasi4mp(parallelexecu:on)• Rezultacanuexistadependenteintreele;
• Dependente-execu4econcurenta:– Untaskarenevoiederezultatelealtora;– Untasktrebuiesaseexecutedupaceoanumitacondi4eeindeplinita– Maimultetaskuriincearcasafoloseascaaceeasiresursa
=>Formedesincronizaretrebuiefolositepentruasa4sfacedependentele;
• Concurentaestefundamentalaincomputerscience– Sistemedeoperare,bazededate,networking,…
13Curs 1 - PPD -
Paralelismvs.Concurenta
14 Curs 1 - PPD -
Obs:– Sepotfolosithreadurisauproceseinambelecazuri– Dacauncalculparalelnecesitaacceslaresursecomuneatunci
estenevoiesaseges4onezecorectconcurenta=>Paralelismulpoateimplicaconcurenta
Paralelism:Sefolosescmaimulteresursepentruarezolvaoproblemamairapid
resources
Concurenta:Ges4uneacorectasieficientaaaccesuluilaresursecomune
requestswork
resource
ConcurentasiParalelism
• Concurent<>paralel!• Execu4eParalela:
– Taskurileseexecutaefec4vinacelasi4mp;
– Estenecesaraexistentademul4pleresursedecalcul
• Paralelism=concurenta+hardware“paralel”
15Curs 1 - PPD -
Paralelism
• Existamaimultenivelurideparalelism:– Procese,threads,rou4ne,instruc4uni,…
• Trebuiesafiesuportatederesurselehardware– Procesoare,cores,…(execu4ainstruc4unilor)– Memorii,DMA,retele,…(opera4iasociate)
16Curs 1 - PPD -
Decesafolosimprogramareparalela?
• Mo4veprimare:– Timpdecalculmairapid(response:me)– Rezolvareaprobelemelor‘mari’decalcul(in4mprezonabildecalcul)
• Mo4vesecundare:– Folosireaefec4vaaresurselordecalcul– Costurireduse– Reducereaconstrangerilorasociatememoriei– Limitarilemasinilorseriale
• Paralelism=concurenta+parallelHardware+performanta
17Curs 1 - PPD -
Curs 1 - PPD - 18
• Rezolvareaproblemelordificile,mari:– "GrandChallenge"(en.wikipedia.org/wiki/Grand_Challenge)problemsrequiring
PetaFLOPSandPetaBytesofcompu4ngresources.– Websearchengines/databasesprocessingmillionsoftransac4onspersecond
• Folosirearesurselornon-locale:
– SETI@home(se4athome.berkeley.edu)usesover330,000computersforacomputepowerover528TeraFLOPS(asofAugust04,2008)
– Folding@home(folding.stanford.edu)usesover340,000computersforacomputepowerof4.2PetaFLOPS(asofNovember4,2008)
Direc4iinprocesareaparalela
• Arhitecturiparalele– Necesita4Hardware– Computersystemdesign
• Sistemedeoperare(Paralelism/concurenta)• Ges4onareaaspectelorsistemptuncalculatorparalel• Programareparalela
– Biblioteci(low-level,high-level)– Limbaje– Mediidedezv.– Sodware
• AlgoritmiParaleli• Evaluareaperformanteiprogramelorparalele• Testareavs.asigurareacorec4tudinii• Paralleltools:
– Performanta,analize,vizualizare,…
19Curs 1 - PPD -
Decesastudiemprogramareparalela?
• Arhitecturidecalcul– Inova4ileconduclanoimodeledeprogramare
• Convergentatehnologica– “killermicro”estepestetot– Laptop-urilesisupercomputeresuntfundamentalsimilare– Trend-urileactualeconduclaconvergentaabordarilordiverse
• Treduriletehnologicefaccalcululparalelinevitabil– Mul4-coreprocessors!– Acumoricesistemdecalculesteparalel
• Intelegereaprincipiilorfundamentale– Programare,comunica4i,memorie,…– Performanta
• “Parallelismisthefutureofcompu%ng”-BlaiseBarney– M.Andrews,J.S.Walicki.“Concurrencyandparallelism—futureofcompu4ng”in
ProceedingofACM'85Proceedingsofthe1985ACMannualconferenceonTherangeofcompu4ng:mid-80'sperspec4ve.pp.224-231.
20Curs 1 - PPD -
InevitabilitateaProcesariiParalele
• Cerinteleptaplica4i– Necesitateauriasadecicluridecalcul
• Trenduritehnologice– Procesaresimemorie
• TrenduriArchitecturale• Factorieconomici• Treduriactuale:
– Today’smicroprocessorshavemul:processorsupport– Serversandworksta:onsavailableasmul:processors– Tomorrow’smicroprocessorsaremul:processors– Mul:-coreisheretostayand#cores/processorisgrowing– Accelerators(GPUs,gamingsystems)
21Curs 1 - PPD -
Aplica4iinforma4ceperformante
• Performantaaplica4ilorimpunehardwareperformant(rapid,resursemul4ple,etc)
• Hardware-ulavansatgenereazanoiaplica4i• Noileaplica4iaucererideperformantamaimari
– Crestereexponen4alaaperformanteimicroprocesoarelor– Inova4iinarhitecturileparalelesiinintegrare
• Cerintedeperformanta=>– Performantasistemelortrebuiesaseimbunatateascainansamblu– Schimbari/abordari/reevaluariinSodwareengineering– Costuri-technologieavansata
applica4onsperformance
hardware
22Curs 1 - PPD -
Curs 1 - PPD - 23
Programareparalelavs.Programaredistribuita
INTERCONNECTION NETWORK
P2
P3
P1
P4 P5
Pn . . . .
Curs 1 - PPD - 24
TiPURI DE MULTIPROCESARE PARALLEL DISTRIBUTED
ASPECTE TEHNICE • PARALLEL COMPUTERS (- IN MOD UZUAL ) LUCREAZA BAZAT PE
• CUPLARE STRANSA, • in general bazate pe SINCRONICITATE, • CU UN SISTEM DE COMUNICATIE FOARTE RAPID SI FIABIL • Spatiu unic de adresare (intr-o masura mare)
• DISTRIBUTED COMPUTERS • MAI INDEPENDENTE, • COMUNICATIE MAI PUTIN FRECVENTA SI mai putin RAPIDA (ASINCRONA) • COOPERARE LIMITATA • NU EXISTA CEAS GLOBAL • “Independent failures”
SCOPURI
• PARALLEL COMPUTERS COOPEREAZA PENTRU A REZOLVA MAI EFICIENT PROBLEME DIFICILE
• DISTRIBUTED COMPUTERS AU SCOPURI INDIVIDUALE SI ACTIVITATI PRIVATE. DOAR UNEORI INTERCOMUNICAREA ESTE NECESARA
PARALLEL COMPUTERS: COOPERARE IN SENS POSITIV
DISTRIBUTED COMPUTERS: COOPERARE IN SENS NEGATIV, DOAR ATUNCI CAND ESTE NECESARA
Curs 1 - PPD - 25
Aplicatii paralele Suntem interesati sa rezolvam problemele mai rapid in paralel
Aplicatii distribuite
Suntem interesati sa rezolvam anumite probleme specifice :
• COMMUNICATION SERVICES ROUTING BROADCASTING
• MAINTENANCE OF CONTROL STUCTURE TOPOLOGY UPDATE LEADER ELECTION • RESOURCE CONTROL ACTIVITIES LOAD BALANCING MANAGING GLOBAL DIRECTORIES
Ingeneral…
Curs 1 - PPD - 26
Parallelv.s.DistributedSystems(fromM.FUKUDACSS434SystemModels)
Parallel Systems Distributed Systems
Memory Tightly coupled shared memory UMA, NUMA
Distributed memory Message passing, RPC, and/or used of distributed shared memory
Control Global clock control SIMD, MIMD
No global clock control Synchronization algorithms needed
Processor interconnection
Order of Tbps Bus, mesh, tree, mesh of tree, and hypercube (-related) network
Order of Gbps Ethernet(bus), token ring and SCI (ring), myrinet(switching network)
Main focus Performance Ex. - Scientific computing
Performance(cost and scalability) Reliability/availability Information/resource sharing
Unpunctdevedere…
Curs 1 - PPD - 27
SistemeleDistribuite
-potfifolositepentru-
• Aplica4idistribuiteimplicit– BDDistribuite,rezervaribilieteavion/etc.sistembancar
• Informa4ipartajateintreuseri• Partajareresurse• Raportcost/performantamaibunptaplica4iparalele
– Potfifolositeeficientpt.aplica4icugranularitatemare(coarse-grained)si/sauptaplica4iparalelede4pembarrassinglyparallelapplica:ons
• Fiabilitate(Reliability).• Scalabilitate
– Cuplareslaba(Looselycoupledconnec4on);hotplug-in
• Flexibilitate– Reconfiguraresistemptaintrunicerintele
Curs 1 - PPD - 28
Performanta/Scalabilitate
Spredeosebiredesistemeleparaleleceledistribuiteimplica:- interven4asistemuluideoperare- mediumaipu4nrapiddetransferaldatelor(reteamaipu4nrapida)- HeterogenitateSolu4i:-Procesarebatchamesajelor:
• Seevitainterven4aSOptfiecaretransferdemesaj.– Cachedata
• Seevitarepetareatransferuluiaceleiasidate– Evitateaen4ta4lorsiaalgoritmilorcentraliza4
• Evitareasaturariiretelei– Realizareopera4i“post”lanivelulclientului
• Evitareatraficuluiintensintreclien4siservere
– ….
Curs 1 - PPD - 29
Securitate
• Nuexistadoarunsingurpunctdecontrol• Probleme:
– Mesaje,furate,modificate,copiate,…• Solu4e:folosireCriptografie
– Failures• FaultTolerancesolu4ons
Tipuridesistemedistribuite(Munehiro Fukuda – PDP Fundamentals)
• Modele– Minicomputer– Worksta4on– Worksta4on-server– Processor-pool– Cluster– Gridcompu4ng
Curs 1 - PPD - 30
31
ModelulMinicomputer
• ExtensieasistemuluideTimesharing– Useriitrebuiesaseloghezepepropriulminicomputer.– Apoiselogheazalaaltamasina(remotemachine)prinprogramede
4ptelnet.• Partajareresurse
– DB– High-performancedevices
Mini-computer
Mini-computer
Mini-computer
net
Curs 1 - PPD -
Curs 1 - PPD - 32
ModelulWorksta4on
• MigrareProcese– Useriiselogheazamaiintaipesta4adelucrupersonala;– Dacaexistasta4i“inasteptare”–unjob“mare”poatemigrala
unadintreele.• Probleme:
– Cumseiden4ficasta4ile“inasteptare”(idle)?– Cummigreazaunjob?– Ceseintampladacaunaltuserselogheazapemasinafolosita?
100MbpsLAN
Worksta4on
Worksta4on Worksta4on
Worksta4onWorksta4on
Curs 1 - PPD - 33
ModelulWorksta4on-Server
• Sta4iClient– Aplica4ileGrafice/interac4veseproceseazalocal– Ptaltecereridecalculsetrimitcererilaservere.
• Servere(minicomputers)– Fiecareserverestededicatunuiasaumaimultor
4purideservicii.• Modeldecomunicare:Client-Servermodel
– RPC(RemoteProcedureCall)– RMI(RemoteMethodInvoca4on)
• Unprocesclientcheamaofunc4eaprocesuluiserver.
• Nusefacemigraredeprocese• Examplu:NFS
100GbpsLAN
Worksta4on
Worksta4on Worksta4on
Mini-Computerfileserver
Mini-ComputerhNpserver
Mini-Computercycleserver
Curs 1 - PPD - 34
ModelulProcessor-Pool
• Clien4i:– Selogheazalaunterminal– Toateserviciilesuntges4onatede
catreservere.• Servere:
– Ptfiecareusersealocanrnecesardeprocesoaredinpool.
• U4lizarebunadarinterac4vitateslaba.
Server1
100MbpsLAN
ServerN
Curs 1 - PPD - 35
ClusterModel
• ConstainmaimultePC/worksta4onsconectatelaoreteade4phigh-speed.
• Focuspeperformanta.100Mbps
LAN
Worksta4on
Worksta4on Worksta4on
Masternode
Slave1
SlaveN
Slave2
1GbpsSAN
h:pserver1
h:pserver2
h:pserverN
Curs 1 - PPD - 36
High-speedInforma4onhighway
GridCompu4ng
• Scop– Colectareaputeridecalculamaimultor
supercomputeresiclusteredispersategeografic
• DistributedSupercompu:ng– Ptproblemwfoartemari.Dificile.
(CPUintensive,memoryintensive).• High-ThroughputCompu4ng
– Folosireamultorresursecarenusuntfolosite
• On-DemandCompu4ng– Resurseladistantaintegrateincalculullocal
• Data-intensiveCompu4ng– distributeddata
• Collabora4veCompu4ng– Suportptcomunicareintremaimultepar4
Super-computer
Cluster
Super-computer Cluster
Mini-computer
Worksta4on
Worksta4on Worksta4on
