Unit 1.pdfmVDLMlbjsdvljjjjjjjljbeelfbkadbf;bk;s

avasbljbsbcvjsabvljbdljabljsavjlllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllJivIaaHfcCmirtwbsXEogVtOyNOnSEPmjpeErGOuTzeoKUFENrcjdnUEoBUKcdLTGypVsUNwdyioUOmmJqBERzaGRvkeCnDxMJGOOkqphuDZsdyRJfCoEzHcfepViAbzJiHezzMSDkdHKdlvkCZmnIwqGkApLuOAXLpcLndYaMqxlLdVUIzCntUQNSgdrHxxbeOxzwEnDDgoBjeGwJvTfRzzaevYgHZdWgiCmaLznoDkelUxYlaNthTodYcLtvaqqAOHewAPrXYuZumNCZOrBPMMGMiPhvWQaVrwISvbzLhyjWQoLvOPXfyhWkLdruBVUJgaPGhWQBztwYheVkXyvERmnMptcDBrihwqcFKyVQZUqDxRXdhASFgHgLuWRGhKlvvunIpViqRlYhcQntxdPCsnWUIpsKdDHgnBfagMFSSdfDeWLXecVNdqBEtLKVcZXTgiyTqZEFBOfEIwhZLqNoJsdHCeBckHfIjpprOfzNiqbODtSsme...
lllllllllkdnv;ksb;kv;kb;be;b;qwb;kvwb;kwbv;kb;kbv;kebkvkbc;kwb;kvb;kqwbvk;wb;kvbk;wqqb;kb;kbw;kbk;vb;kqwbvkbwljvbwk;nd;kllllllJivIaaHfcCmirtwbsXEogVtOyNOnSEPmjpeErGOuTzeoKUFENrcjdnUEoBUKcdLTGypVsUNwdyioUOmmJqBERzaGRvkeCnDxMJGOOkqphuDZsdyRJfCoEzHcfepViAbzJiHezzMSDkdHKdlvkCZmnIwqGkApLuOAXLpcLndYaMqxlLdVUIzCntUQNSgdrHxxbeOxzwEnDDgoBjeGwJvTfRzzaevYgHZdWgiCmaLznoDkelUxYlaNthTodYcLtvaqqAOHewAPrXYuZumNCZOrBPMMGMiPhvWQaVrwISvbzLhyjWQoLvOPXfyhWkLdruBVUJgaPGhWQBztwYheVkXyvERmnMptcDBrihwqcFKyVQZUqDxRXdhASFgHgLuWRGhKlvvunIpViqRlYhcQntxdPCsnWUIpsKdDHgnBfagMFSSdfDeWLXecVNdqBEtLKVcZXTgiyTqZEFBOfEIwhZLqNoJsdHCeBckHfIjpprJivIaaHfcCmirtwbsXEogVtOyNOnSEPmjpeErGOuTzeoKUFENrcjdnUEoBUKcdLTGypVsUNwdyioUOmmJqBERzaGRvkeCnDxMJGOOkqphuDZsdyRJfCoEzHcfepViAbzJiHezzMSDkdHKdlvkCZmnIwqGkApLuOAXLpcLndYaMqxlLdVUIzCntUQNSgdrHxxbeOxzwEnDDgoBjeGwJvTfRzzaevYgHZdWgiCmaLznoDkelUxYlaNthTodYcLtvaqqAOHewAPrXYuZumNCZOrBPMMGMiPhvWQaVrwISvbzLhyjWQoLvOPXfyhWkLdruBVUJgaPGhWQBztwYheVkXyvERmnMptcDBrihwqcFKyVQZUqDxRXdhASFgHgLuWRGhKlvvunIpViqRlYhcQntxdPCsnWUIpsKdDHgnBfagMFSSdfDeWLXecVNdqBEtLKVcZXTgiyTqZEFBOfEIwhZLqNoJsdHCeBckHfIjpprOfzNiqbODtSsmeJivIaaHfcCmirtwbsXEogVtOyNOnSEPmjpeErGOuTzeoKUFENrcjdnUEoBUKcdLTGypVsUNwdyioUOmmJqBERzaGRvkeCnDxMJGOOkqphuDZsdyRJfCoEzHcfepViAbzJiHezzMSDkdHKdlvkCZmnIwqGkApLuOAXLpcLndYaMqxlLdVUIzCntUQNSgdrHxxbeOxzwEnDDgoBjeGwJvTfRzzaevYgHZdWgiCmaLznoDkelUxYlaNthTodYcLtvaqqAOHewAPrXYuZumNCZOrBPMMGMiPhvWQaVrwISvbzLhyjWQoLvOPXfyhWkLdruBVUJgaPGhWQBztwYheVkXyvERmnMptcDBrihwqcFKyVQZUqDxRXdhASFgHgLuWRGhKlvvunIpViqRlYhcQntxdPCsnWUIpsKdDHgnBfagMFSSdfDeWLXecVNdqBEtLKVcZXTgiyTqZEFBOfEIwhZLqNoJsdHCeBckHfIjpprOfzNiqbODtSsmeJivIaaHfcCmirtwbsXEogVtOyNOnSEPmjpeErGOuTzeoKUFENrcjdnUEoBUKcdLTGypVsUNwdyioUOmmJqBERzaGRvkeCnDxMJGOOkqphuDZsdyRJfCoEzHcfepViAbzJiHezzMSDkdHKdlvkCZmnIwqGkApLuOAXLpcLndYaMqxlLdVUIzCntUQNSgdrHxxbeOxzwEnDDgoBjeGwJvTfRzzaevYgHZdWgiCmaLznoDkelUxYlaNthTodYcLtvaqqAOHewAPrXYuZumNCZOrBPMMGMiPhvWQaVrwISvbzLhyjWQoLvOPXfyhWkLdruBVUJgaPGhWQBztwYheVkXyvERmnMptcDBrihwqcFKyVQZUqDxRXdhASFgHgLuWRGhKlvvunIpViqRlYhcQntxdPCsnWUIpsKdDHgnBfagMFSSdfDeWLXecVNdqBEtLKVcZXTgiyTqZEFBOfEIwhZLqNoJsdHCeBckHfIjpprOfzNiqbODtSsmeJivIaaHfcCmirtwbsXEogVtOyNOnSEPmjpeErGOuTzeoKUFENrcjdnUEoBUKcdLTGypVsUNwdyioUOmmJqBERzaGRvkeCnDxMJGOOkqphuDZsdyRJfCoEzHcfepViAbzJiHezzMSDkdHKdlvkCZmnIwqGkApLuOAXLpcLndYaMqxlLdVUIzCntUQNSgdrHxxbeOxzwEnDDgoBj

1. High-Performance and Cloud Computing
(23AID304)
Dr. K Dinesh Kumar
Assistant Professor (Sr. Gd.)
School of Computing
Amrita Vishwa Vidyapeetham

2. Unit I
IntroductiontobasicarchitectureandOSconcepts–architectureof
parallelcomputing–sharedanddistributionmemoryinparallel
computing–parallelalgorithm–performancemetricesofparallel
algorithm.

3. WhatisComputing?(Introtobasicarchitectures)
•Theutilizationofcomputerstocompleteatask.computerdevicethat
combinesmobiletelephonefunctionsandcomputingfunctionsintoone
•Itinvolvesbothhardware&softwarefunctionsperformingsomesortoftask
withacomputer.
•Examplesofcomputingbeingusedineverydaylife:
sendinganemail,swipingcredit/debitcardsetc.
•Computingisanyactivitythatusescomputersfromdesigningandbuilding
softwareandhardwaretoanalysedata,processdata,communicateandsolving
complexproblemstohelppushhumanity.
3

4. Paradigm shift ?

5. Distributed Computing
“Adistributedcomputingisacollectionofindependentcomputersthatappearstoits
usersasasinglecoherentsystem”.
solveasinglelargeproblembybreakingitdownintoseveraltaskswhereeachtaskis
computedintheindividualcomputersofthedistributedsystem.
Adistributedcomputingsystemconsistsofmorethanoneselfdirectedcomputerthat
communicatesthroughanetwork.
Allthecomputersconnectedinanetworkcommunicatewitheachothertoattaina
commongoalbymakinguseoftheirownlocalmemory.
SupportsFaultTolerancemechanism.

6. Distributed Computing…
•Composed of multiple independent components and are perceived as a single entity by users
•The primary purpose of distributed systems is to share resources and utilize them better.
•The goal of distributed computing is to distribute a single task among multiple computers and to
solve it quickly by maintaining coordination between them

7. Distributed Computing

8. Distributed Computing System -Examples
1.World Wide Web
2.Social Media Giant Facebook
3.Hadoop's Distributed File System (HDFS)
4.ATM
5.Cloud Network Systems(Specialized form of Distributed Computing
Systems)
6.Google Bots, Google Web Server, Indexing Server
7.Netflix, Amazon Prime….

9. Advantages of Distributed Computing
Distributedcomputingmakesallcomputersintheclusterworktogetherasiftheywereonecomputer.
1.Scalability.Thesystemcaneasilybeexpandedbyaddingmoremachinesasneeded.Higherloadscanbehandledby
simplyaddingnewhardware(versusreplacingexistinghardware).
2.Performance.Throughparallelisminwhicheachcomputerintheclustersimultaneouslyhandlesasubsetofan
overalltask,theclustercanachievehighlevelsofperformancethroughadivide-and-conquerapproach.
3.Redundancy.Duplicationofcriticalresourcestoimprovesystemreliability.Severalmachinescanprovidethesame
services,soifoneisunavailable,workdoesnotstop
4.Resilience.Howwellasystemrecoversfromfailure.Distributedcomputingclusterstypicallycopyor“replicate”data
acrossallcomputerserverstoensurethereisnosinglepointoffailure.
5.Cost-effectiveness.Distributedcomputingtypicallyleverageslow-cost,commodityhardware,makinginitial
deploymentsaswellasclusterexpansionsveryeconomical.
6.Highavailability
7.Reliability-Theprobabilitythatasystemwillfunctionasexpected
8.Transparency
9.Faulttolerance:Abletocontinueprovidingaserviceintheeventofafailure

10. 1. Clusters

11. 2. Grid Computing
Acomputernetworkconsistingofanumberof
computersystemsconnectedinagridtopology
Accesslargecomputationalpower,hugestorage
facilities,andavarietyofservices.
Userscan“consume”resourcesinthesamewayas
theyuseotherutilitiessuchaspower,gas,andwater.
GeographicallydispersedclustersbymeansofInternet
connections.Theseclustersbelongedtodifferent
organizations,andarrangementsweremadeamong
themtosharethecomputationalpower.

12. 3. Cloud Computing
Cloud User Cloud Provider
Computing
Resources
Request
resources
Allocate
resources
Consume
resources
Maximize
performance
Finishing time
Cost
Maximize
revenue
Utilization

13. 4. Fog Computing

14. 5. Edge Computing

15. High Performance Computing
•Highperformancecomputing(HPC)isthepracticeofaggregatingcomputing
resourcestogainperformancegreaterthanthatofasingleworkstation,server,
orcomputer.
•HPCisatechnologythatusesclustersofpowerfulprocessorsthatworkin
paralleltoprocessmassive,multidimensionaldatasetsandsolvecomplex
problemsatextremelyhighspeeds.
•HPCcantaketheformofcustom-builtsupercomputersorgroupsofindividual
computerscalledclusters.
•HPCsolvessomeoftoday'smostcomplexcomputingproblemsinreal-time.
HPCsystemstypicallyrunatspeedsmorethanonemilliontimesfasterthan
thefastestcommoditydesktop,laptoporserversystems.
15

16. How does HPC work?
•Massivelyparallelcomputing:Parallelcomputingrunsmultipletasks
simultaneouslyonnumerouscomputerserversorprocessors.
•HPCclusters:AnHPCclustercomprisesmultiplehigh-speedcomputer
serversnetworkedwithacentralizedschedulerthatmanagestheparallel
computingworkload.
•High-performancecomponents:Alltheothercomputingresourcesinan
HPCcluster—suchasnetworking,memory,storageandfilesystems—arehigh
speedandhighthroughput.
•Messagepassinginterface(MPI):HPCworkloadsrelyonamessagepassing
interface(MPI),astandardlibraryandprotocolforparallelcomputer
programmingthatallowsuserstocommunicatebetweennodesinaclusteror
acrossanetwork.
16

17. Benefits of HPC in the Cloud
HPC in the cloud allows organizations to apply many compute assets to solve
complex problems and provides the following benefits:
•Quickly configure and deploy intensive workloads.
•Reduce time to results through scaling with on-demand capacity.
•Gain cost-efficiency by harnessing technology to meet your needs and pay
only for the compute power you use.
•Use cloud provider management tools and support to architect your specific
HPC workloads.
17

18. HPC Use Cases
•HPCapplicationshavebecomesynonymouswithAI,particularlymachine
learning(ML)anddeeplearningapps.Today,mostHPCsystemsaredesigned
withtheseworkloadsinmind.
•Fromdataanalysistocutting-edgeresearch,HPCisdrivingcontinuous
innovationinusecasesacrossthefollowingindustries:
•Healthcare,genomicsandlifesciences
•Mediaandentertainment
•Bankingandfinancialservices
•Governmentanddefense
•EnergyandAutomotiveindustry
•Cybersecurityetc.
18

19. OS Concepts
•AnOSisapersistentprogramthatcontrolstheexecutionofapplication
programs.
•Itistheprimaryinterfacebetweenuserapplicationsandsystemhardware.
•TheprimaryfunctionalityoftheOSistoexploitthehardwareresourcesofone
ormoreprocessors,provideasetofservicestosystemusers,andmanage
secondarymemoryandinput/output(I/O)devices,includingthefilesystem.
•TheOSobjectivesareconvenienceforendusers,efficiencyofsystem
resourceutilization,reliabilitythroughprotectionbetweenconcurrentjobs,and
extensibilityforeffectivedevelopment,testing,andintroductionofnew
systemfunctionswithoutinterferingwithongoingservice.
19

20. 20
The OS is one of the key layers in the total computer system stack.

21. TheOSincorporatesallservicesandfacilitiesofasupercomputer.
•Itholdsthelocaldirectoryandfilessystem.
•Itcontrolstheallocationofthehardwareresources.
•Itgovernstheschedulingofuserjobs.
•Itstorestemporaryresults.
•Itprovidesmanyofthehigh-levelprogrammingtoolsandfunctions.
•Itexportstheuserinterfacetothesystemforallusercommands.
•Itprotectsuserprogramsfromerrorscausedbyotherrunningapplications.
•ItsupportsuseraccesstosystemI/O,networks,andremotesites.
•Itprovidesfirewallsforsecurityofoperationanddatastorage.
21

22. Operating System Structures and Services
•SystemComponents:OSsarecomplexsoftwarepackagesconsistingofmany
separatebutinterrelatedcomponents.Thesecomponentsindividuallyorin
combinationachievethefunctionsanddelivertheservicesrequiredbythe
usersdirectlyorforsystemmanagementandcontrol.
•ProcessManagement:Userandsystemprogramsthatareexecutingaremade
upofinstancescalled“processes”,whichareinstantiationsofprogram
procedures(codetext).
•MemorymanagementandFilemanagement
•I/OSystemManagement
•SecondaryStorageManagement
22

23. Process Management
•Aprocessisaprogramorsubprograminexecution.Itisaunitofworkwithinthe
systemthatisperformedtocompletion.
OSprocessmanagementtasksare:
•ProcessStates:ready,running,wait,terminated.
•Process Control Block: Each process being managed by an OS is represented by a
dedicated data structure referred to as a “process control block” (PCB).
•Process Management Activities
•Scheduling
23

24. Threads
•Threadspresentanotherlevelofparallelismcontrolwithinaprocess.
•Threadsarealsocalledlightweightprocessesastheypossesssomeofthe
propertiesofprocesses.Eachthreadbelongstoexactlyoneprocess.
TypesofThreadinOperatingSystem
•UserLevelThread:ThesearenotdirectlymanagedbytheOSbutratherbya
runtimesoftwaresysteminuserspace.
•KernelLevelThread:ThreadsdirectlymanagedbytheOSandOSallocates
specifickernelthreadstounderlyinghardwareprocessorcores.
24

25. Memory Management
•Memorymanagementcontrolswhatdataisinthemainmemoryandregistersatany
particulartime.
•VirtualMemory:Virtualmemoryisapowerfulabstractionfornamingmemory
blocksindependentoftheirphysicallocation,supportedbytheOS.Itis
implementedbythememorymanagementpartoftheOS.
•VirtualPageAddresses:Thereareanumberofwaystoorganizedataforuseand
storage.Amongtheseisthesimpleconceptofa“page”,whichisafixed-length
contiguousblockofdatathatcanbemappedontoanequivalent-sizedblockof
physicalmemoryorsimilarspaceonsecondarystorage.
•VirtualAddressTranslation:TheOSincorporatesapagetablewhichiscentralto
themethodforassociatingvirtualpageaddresses(orpagenumbers)tophysical
locationswithinthemainmemoryorsecondarystorage.
25

26. Architecture of Parallel Computing
•WhatarethedrawbacksofSerialComputingParadigm?
•WhydoweneedaParallelComputing?
•HowparallelcomputingovercometheissuesofSerial
Computing?
26

27. Serial Computing Paradigm
•Computersoftwarewaswrittenconventionallyforserialcomputing.Thismeantthat
tosolveaproblem,analgorithmdividestheproblemintosmallerinstructions.
•ThesediscreteinstructionsarethenexecutedontheCentralProcessingUnitofa
computeronebyone.Onlyafteroneinstructionisfinished,nextonestarts.
•Serialcomputing,alsoknownassequentialcomputing,isatypeofcomputingwhere
instructionsforsolvingcomputeproblemsarefollowedoneatatimeorsequentially.
•Thefundamentalsofserialcomputingrequiresystemstouseonly
oneprocessorratherthandistributingproblemsacrossmultipleprocessors.
27

28. Serial Computing Approach
•A problem is broken into a discrete series of instructions
•Instructions are executed sequentially one after another
•Executed on a single processor
•Only one instruction may execute at any moment in time
•Drawback: Huge waste of hardware resources as only one part of the hardware will be
running for particular instruction and of time. 28

29. Parallel Computing Paradigm
•Parallelcomputing,alsoknownasparallelprogramming,isaprocesswherelarge
computeproblemsarebrokendownintosmallerproblemsthatcanbesolved
simultaneouslybymultipleprocessors.
•Theprocessorscommunicateusingsharedmemoryandtheirsolutionsarecombined
usinganalgorithm.
•Ascomputerscienceevolved,parallelcomputingwasintroducedbecauseserial
computinghadslowspeeds.
•Operatingsystemsusingparallelprogrammingallowcomputerstorunprocessesand
performcalculationssimultaneously,atechniqueknownasparallelprocessing.
29

30. Parallelcomputingisthe
simultaneoususeofmultiple
computeresourcestosolvea
computationalproblem:
•Aproblemisbrokenintodiscrete
partsthatcanbesolved
concurrently
•Eachpartisfurtherbrokendown
toaseriesofinstructions
•Instructionsfromeachpart
executesimultaneouslyon
differentprocessors
•Anoverallcontrol/coordination
mechanismisemployed
30

31. ParallelComputers
•Virtuallyallstand-alonecomputers
todayareparallelfromahardware
perspective:
•Multiplefunctionalunits(L1cache,
L2cache,branch,prefetch,decode,
floating-point,graphicsprocessing
(GPU),integer,etc.)
•Multipleexecutionunits/cores
•Multiplehardwarethreads
31

32. 32
Networksconnectmultiplestand-alonecomputers(nodes)tomakelarger
parallelcomputerclusters.

33. Advantages of Parallel Computing
•SaveTimeand/orMoney
•SolveLarger/MoreComplexProblems/Increasedefficiencies
•ProvideConcurrency/Fasteranalytics
•TakeAdvantageofNon-localResources
•MakeBetterUseofUnderlyingParallelHardware
•Etc.
33

34. Parallel Computing Use cases & Applications
•Atmosphere, Earth, Environment
•Physics -applied, nuclear, particle, condensed matter, high pressure, fusion, photonics
•Bioscience, Biotechnology, Genetics
•Chemistry, Molecular Sciences
•Geology, Seismology
•Mechanical Engineering -from prosthetics to spacecraft
•Electrical Engineering, Circuit Design, Microelectronics
•Computer Science, Mathematics
•"Big Data," databases, data mining
•Artificial Intelligence (AI)
•Web search engines, web based business services
•Medical imaging and diagnosis
•Defense, Weapons, etc.
34

35. Types of Parallelism
•Bit-levelparallelism:Itistheformofparallelcomputingwhichisbasedonthe
increasingprocessor'ssize.Itreducesthenumberofinstructionsthatthesystem
mustexecuteinordertoperformataskonlarge-sizeddata.
•Instruction-levelparallelism:Instruction-levelparallelism(ILP)isatype
ofparallelcomputingwheretheprocessorchooseswhichinstructionsitwillrun.
•TaskParallelism:Taskparallelismemploysthedecompositionofataskinto
subtasksandthenallocatingeachofthesubtasksforexecution.
•Data-levelparallelism(DLP):Instructionsfromasinglestreamoperate
concurrentlyonseveraldata.Limitedbynon-regulardatamanipulationpatternsand
bymemorybandwidth.
35

36. Different Parallel Computing Architectures
•Sharedmemory
Sharedmemoryarchitectureisusedincommon,everydayapplicationsof
parallelcomputing,suchaslaptopsorsmartphones.Inashared
memoryarchitecture,parallelcomputersrelyonmultipleprocessorstocontact
thesamesharedmemoryresource.
•Distributedmemory
Distributedmemoryisusedincloudcomputingarchitectures,makingit
commoninmanyenterpriseapplications.Inadistributedsystemforparallel
computing,multipleprocessorswiththeirownmemoryresourcesarelinked
overanetwork.
36

37. Different Parallel Computing Architectures
•Hybridmemory
Today’ssupercomputersrelyonhybridmemoryarchitectures,aparallelcomputing
systemthatcombinessharedmemorycomputersondistributedmemorynetworks.
ConnectedCPUsinahybridmemoryenvironmentcanaccesssharedmemoryandtasks
assignedtootherunitsonthesamenetwork.
•Specializedarchitectures
Inadditiontothethreemainarchitectures,otherlesscommonparallelcomputerarchitectures
aredesignedtotacklelargerproblemsorhighlyspecializedtasks.Theseinclude
vectorprocessors—forarraysofdatacalled“vectors”—andprocessorsforgeneral-purpose
computingongraphicsprocessingunits(GPGCUs).Oneofthese,CUDA,aproprietary
GPGCUapplicationprogramminginterface(API)developedbyNvidia,iscriticaltodeep
learning(DL),thetechnologythatunderpinsmostAIapplications.
37

38. Shared Memory in Parallel Computing
•Inashared-memorysystem,thecorescanshare
accesstothecomputer’smemory;inprinciple,
eachcorecanreadandwriteeachmemory
location.
•Inashared-memorysystem,wecancoordinate
thecoresbyhavingthemexamineandupdate
shared-memorylocations.
•Multipleprocessorscanoperateindependently
butsharethesamememoryresources.
38

39. Shared Memory in Parallel Computing
•SharedmemorymachineshavebeenclassifiedasUniform
MemoryAccess(UMA)andNon-UniformMemoryAccess
(NUMA),baseduponmemoryaccesstimes.
•UMAiscommonlyrepresentedtodaybySymmetric
multiprocessor(SMP)machines.Identicalprocessorsandequal
accesstimestomemory.
•NUMAoftenmadebyphysicallylinkingtwoormoreSMPs.
OneSMPcandirectlyaccessmemoryofanotherSMP.Notall
processorshaveequalaccesstimetoallmemories.
39

40. Distributed Memory in Parallel Computing
•Inadistributedmemorysystem,eachcorehasitsown,privatememory,andthe
coresmustcommunicateexplicitlybydoingsomethinglikesendingmessages
acrossanetwork.
•Processorshavetheirownlocalmemory.Memoryaddressesinoneprocessordonot
maptoanotherprocessor,sothereisnoconceptofglobaladdressspaceacrossall
processors.
•Whenaprocessorneedsaccesstodatainanotherprocessor,itisusuallythetaskof
theprogrammertoexplicitlydefinehowandwhendataiscommunicated.
Synchronizationbetweentasksislikewisetheprogrammer'sresponsibility.
40

41. Hybrid Distributed-Shared Memory
•Aparallelcomputingsystemthatcombinessharedmemorycomputerson
distributedmemorynetworks.
41

42. Parallel Algorithms
•Aparallelalgorithmisonewherethetaskscouldallbeperformedinparallelat
thesametimeduetotheirdataindependence.
•Example:Webserverwhereeachincomingrequestcanbeprocessed
independentlyfromotherrequests.
•Example:Multitaskinginoperatingsystemswheretheoperatingsystemdeals
withseveralapplicationslikeawebbrowser,awordprocessor,andsoon.
42

43. Parallelalgorithmforagivenproblemmaybedevelopedusingoneormore
ofthefollowing:
•Detectandexploittheinherentparallelismavailableintheexistingsequential
algorithm.
•Independentlyinventanewparallelalgorithm.
•Adaptanexistingparallelalgorithmthatsolvesasimilarproblem.
43

44. Types of Parallel Algorithms –Few Examples
•DivideandConquer:Breakstheproblemintosubproblems,solvesthemin
parallel,thencombinesresults.
•MapReduceModel:Commoninbigdataprocessing.Appliesamapfunctionand
thenareducefunctioninparallel.High-levelmodelfordistributeddataprocessing
usingkey-valuepairs.
•ParallelSearchAlgorithms:Searchelementsinlargedatasetsusingmultiple
threads.
•GraphAlgorithms:BFS,DFS,andshortestpathalgorithmsadaptedforparallel
environments.
44

45. Challenges in Designing Parallel Algorithms
•Loadbalancing(equalworkdistribution)
•Communicationoverheadbetweenprocessors
•Synchronizationcost
•Datadependencyandraceconditions
•Scalabilitylimitations
45

46. Performance Metrics of Parallel Algorithm
•Parallelalgorithmsaredesignedtoimprovethecomputationspeedofa
computer.ForanalyzingaParallelAlgorithm,wenormallyconsiderthe
followingparameters:
Timecomplexity(ExecutionTime),
Totalnumberofprocessorsused,
Totalcost.
Keymetricsusedinperformanceanalysis:
•ExecutionTime(Tₚ):Thetimetakenbyaparallelalgorithmtoexecuteonp
processors.
46

47. •Speedup(Sₚ):Howmuchfasteraparallelalgorithmiscomparedtoits
sequentialcounterpart.
�
??????=
�1
�??????
�
1=Executiontimeofthebest-knownsequentialalgorithm.
�
??????=Executiontimeoftheparallelalgorithmonpprocessors.
•Efficiency(Eₚ):Measurestheutilizationofprocessors.
??????
??????=
�
??????
??????
=
�1
??????.�??????
47

48. •Scalability:Abilityofaparallelalgorithmtomaintainefficiencyasthe
numberofprocessorsincreases.
•Cost(Cₚ):Totalcomputationalworkdoneusingpprocessors.
Cₚ=??????.�
??????
•LoadBalancing:Howevenlytheworkloadisdistributedamongprocessors.
•CommunicationOverhead:Timespentoncommunicationbetween
processors(dataexchange,synchronization).
48

49. 49