Multithreading

Multithreading concepts and its use in computer architectures.

1. Multithreading
Mr. A. B. Shinde
Assistant Professor,
Electronics Engineering,
P.V.P.I.T., Budhgaon

2. Contents…
UsingILPsupporttoexploit
thread–levelparallelism
performanceandefficiencyin
advanced multipleissue
processors
2

3. Threads
AthreadisabasicunitofCPUutilization.
Athreadisaseparateprocesswithitsowninstructionsanddata.
Athreadmayrepresentaprocessthatispartofaparallelprogram
consistingofmultipleprocesses,oritmayrepresentan
independentprogram.
3

4. Threads
ItcomprisesofathreadID,aprogramcounter,aregistersetanda
stack.
Itsharesitscodesection,datasection,andotheroperating-system
resources,suchasopenfilesandsignalswithotherthreads
belongingtothesameProcess.
Atraditionalprocesshasasinglethreadofcontrol.Ifaprocesshas
multiplethreadsofcontrol,itcanperformmorethanonetaskatatime.
4

5. Threads
Manysoftwarepackagesthatrun
onmoderndesktopPCsare
multithreaded.
Forexample:
Awordprocessormayhave:
athreadfordisplayinggraphics,
anotherthreadforrespondingto
keystrokesfromtheuser,and
athirdthreadforperformingspelling
andgrammarcheckinginthe
background.
5

6. Threads
Threadsalsoplayavitalroleinremoteprocedurecall(RPC)
systems.
RPCsallowsinterprocesscommunication byprovidinga
communicationmechanismsimilartoordinaryfunctionorprocedure
calls.
Manyoperatingsystemkernelsaremultithreaded;severalthreads
operateinthekernel,andeachthreadperformsaspecifictask,suchas
managingdevicesorinterrupthandling.
6

7. Multithreading
Benefits:
1.Responsiveness:Multithreadingisaninteractiveapplicationthat
mayallowaprogramtocontinuerunningevenifpartofitis
blocked,therebyincreasingresponsivenesstotheuser.
Forexample:Amultithreadedwebbrowsercouldstillallowuser
interactioninonethreadwhileanimagewasbeingloadedinanother
thread.
2.Resourcesharing:Bydefault,threadssharethememoryandthe
resourcesoftheprocesstowhichtheybelong.Thebenefitofsharing
codeanddataisthatitallowsanapplicationtohaveseveraldifferent
threadsofactivitywithinthesameaddressspace.
7

8. Multithreading
Benefits:
3.Economy:Allocatingmemoryandresourcesforprocesscreationis
costly.Sincethreadsshareresourcesoftheprocesstowhichthey
belong,theywillprovidecosteffectivesolution.
4.Utilizationofmultiprocessorarchitectures:Inmultiprocessor
architecture,threadsmayberunninginparallelondifferentprocessors.
AsinglethreadedprocesscanonlyrunononeCPU,nomatterhow
manyareavailable.
Multithreadingonamulti-CPUmachineincreasesconcurrency.
8

9. Multithreading Models
Supportforthreadsmaybeprovidedeitherattheuserlevelorat
thekernellevel.
Userthreadsaresupportedabovethekernelandaremanaged
withoutkernelsupport,whereaskernelthreadsaresupportedand
manageddirectlybytheoperatingsystem.
9

10. Multithreading Models
Many-to-OneModel:
Themany-to-onemodelmapsmanyuser-
levelthreadstoonekernelthread.
Threadmanagement isdonebythe
threadlibraryinuserspace,soitis
efficient.
Onlyonethreadcanaccessthekernelat
atime,hencemultiplethreadsareunableto
runinparallelonmultiprocessors.
10

11. Multithreading Models
One-to-OneModel:
Theone-to-onemodelmapseachuser
threadtoakernelthread.
Itprovidesmoreconcurrencythanthemany-
to-onemodel.Itallowsmultiplethreadstorunin
parallelonmultiprocessors.
Theonlydrawbacktothismodelisthat
creatingauserthreadrequirescreatingthe
correspondingkernelthread.
Theoverheadofcreatingkernelthreadscan
burdentheperformanceofanapplication.
11

12. Multithreading Models
Many-to-ManyModel:
Themany-to-manymodelmultiplexesmany
user-levelthreadstoasmallerorequal
numberofkernelthreads.
Thenumberofkernelthreadsmaybespecific
toeitheraparticularapplicationoraparticular
machine.
Developerscancreateasmanyuserthreads
asnecessary,andthecorrespondingkernel
threadscanruninparallelona
multiprocessor.
12

13. Multithreading: ILP Support to Exploit
Thread-Level Parallelism
13

14. Multithreading: ILP Support to Exploit
Thread-Level Parallelism
AlthoughILPincreasestheperformanceofsystem;thenalsoILP
canbequitelimitedorhardtoexploitinsomeapplications.
Furthermore,theremaybeparallelismoccurringnaturallyatahigher
levelintheapplication.
Forexample:
Anonlinetransaction-processingsystemhasparallelismamongthe
multiplequeriesandupdates.Thesequeriesandupdatescanbe
processedmostlyinparallel,sincetheyarelargelyindependentofone
another.
14

15. Multithreading: ILP Support to Exploit
Thread-Level Parallelism
Thishigher-levelparallelismiscalledthread-levelparallelism(TLP)
becauseitislogicallystructuredasseparatethreadsofexecution.
ILPisparalleloperationswithinalooporstraight-linecode.
TLPisrepresentedbytheuseofmultiplethreadsofexecutionthat
areinparallel.
15

16. Multithreading: ILP Support to Exploit
Thread-Level Parallelism
Thread-levelparallelismisanimportantalternativetoinstruction-
levelparallelism.
Inmanyapplicationsthread-levelparallelismoccursnaturally(many
serverapplications).
Ifsoftwareiswrittenfromscratch,thenexpressingtheparallelism
ismucheasy.
Butifestablishedapplicationswrittenwithoutparallelisminmind,
thentherecanbesignificantchallengesandcanbeextremelycostly
torewritethemtoexploitthread-levelparallelism.
16

17. Multithreading: ILP Support to Exploit
Thread-Level Parallelism
TLPandILPexploitstwodifferentkindsofparallelstructures.
Thecrucialquestionis:
CanweexploitTLPonprocessordesignedforILP
Answeris:Yes
DatapathdesignedtoexploitILPwillfindthatmanyfunctionalunitsare
oftenidlebecauseofeitherstallsordependencesinthecode.
Thethreadscanbeusedasaindependentinstructionsthatmightkeep
theprocessorbusytoimplementTLP.
17

18. Multithreading: ILP Support to Exploit
Thread-Level Parallelism
Multithreadingallowsmultiplethreadstosharethefunctionalunits
ofasingleprocessorinanoverlappingfashion.
Topermitthissharing,theprocessormustduplicatethe
independentstateofeachthread.
Forexample:
Aseparatecopyoftheregisterfile,aseparatePCandaseparatepage
tablewererequiredforeachthread.
Inaddition,thehardwaremustsupporttheabilitytochangetoa
differentthreadsrelativelyquickly.
18

19. Multithreading: ILP Support to Exploit
Thread-Level Parallelism
Therearetwomainapproachestomultithreading.
Fine-grainedmultithreading&
Coarse-grainedmultithreading
19

20. Multithreading: ILP Support to Exploit
Thread-Level Parallelism
Fine-grainedmultithreading:
Itswitchesbetweenthreadsoneachinstruction,causingthe
executionofmultiplethreadstobeinterleaved.
Thisinterleavingisoftendoneinaround-robinfashion.
Tomakefine-grainedmultithreadingpractical,theCPUmustbe
abletoswitchthreadsoneveryclockcycle.
Advantage:Itcanhidethethroughputlossesthatarisefrombothshort
andlongstalls.
Disadvantage:Itslowsdowntheexecutionoftheindividualthreads.
20

21. Multithreading: ILP Support to Exploit
Thread-Level Parallelism
Coarse-grainedmultithreading:
Itwasinventedasanalternativetofine-grainedmultithreading.
Coarse-grainedmultithreadingswitchesthreadsonlyoncostly
(larger)stalls.
Advantage:Thischangerelievestheneedtohavethreadswitching.
Disadvantage:Theyarelikelytoslowtheprocessordown,since
instructionsfromotherthreadswillonlybeissuedwhenathread
encountersacostly(larger)stalls.
21

22. Multithreading: ILP Support to Exploit
Thread-Level Parallelism
CPUwithcoarse-grainedmultithreadingissuesinstructionsfroma
singlethread.
Whenastalloccurs,thepipelinemustbeemptiedorfrozen.
Newthreadthatisexecutingafterthestallmustfillthepipeline.
Becauseofthisstart-upoverhead,coarsegrainedmultithreadingis
muchmoreusefulforreducingthepenaltyofhigh-coststalls,
wherepipelinerefillisnegligiblecomparedtothestalltime.
22

23. Converting Thread-Level
Parallelism into Instruction-Level Parallelism
Simultaneousmultithreading(SMT)isavariationonmultithreading
thatusestheresourcesofamultiple-issue,dynamicallyscheduled
processortoexploitTLP.
Multiple-issueprocessorsoftenhavemorefunctionalunit
parallelismthanasinglethread,motivatestheuseofSMT.
Withregisterrenaminganddynamicscheduling,multipleinstructions
fromindependentthreadscanbeissuedwithoutconsideringthe
dependencesamongthem.
23

24. Converting Thread-Level
Parallelism into Instruction-Level Parallelism
Figureillustratesthedifferencesinaprocessor’sabilitytoexploitthe
resourcesofasuperscalarforthefollowingconfigurations:
Asuperscalarwithnomultithreadingsupport
Asuperscalarwithcoarse-grainedmultithreading
Asuperscalarwithfine-grainedmultithreading
Asuperscalarwithsimultaneousmultithreading
24

25. Converting Thread-Level
Parallelism into Instruction-Level Parallelism
Inthesuperscalarwithoutmultithreadingsupport,
theuseofissueslotsislimitedbyalackofILP.
Inaddition,amajorstall,suchasaninstruction
cachemiss,canleavetheentireprocessoridle.
25
Anempty(white)boxindicatesthatthe
correspondingissueslotisunusedinthatclock
cycle.
Blackisusedtoindicatetheoccupiedissueslots

26. Converting Thread-Level
Parallelism into Instruction-Level Parallelism
Inthecoarse-grainedmultithreadedsuperscalar,
thelongstallsarepartiallyhiddenbyswitching
toanotherthreadthatusestheresourcesofthe
processor.
Thisreducesthenumberofcompletelyidle
clockcycles,withineachclockcycle,theILP
limitationsstillleadtoidlecycles.
Inacoarsegrainedmultithreadedprocessor,
threadswitchingonlyoccurswhenthereisa
stall,thenalsotherewillbesomefullyidlecycles
remaining.
26
Theshadesofgreyandblackcorrespondto
differentthreadsinthemultithreadingprocessors.

27. Converting Thread-Level
Parallelism into Instruction-Level Parallelism
Inthefine-grainedmultithreading,the
interleavingofthreadseliminatesfullyempty
slots.
Becauseonlyonethreadissuesinstructionsin
agivenclockcycle,ILPlimitationsstillleadtoa
significantnumberofidleslotswithinindividual
clockcycles.
27
Anempty(white)boxindicatesthatthe
correspondingissueslotisunusedinthatclock
cycle.
Theshadesofgreyandblackcorrespondtofour
differentthreadsinthemultithreadingprocessors.

28. Converting Thread-Level
Parallelism into Instruction-Level Parallelism
InSMT,TLPandILPareexploited
simultaneously.
Ideally,theissueslotusageislimitedby
imbalancesintheresourceneedsandresource
availabilityovermultiplethreads.
Inpractice,otherfactors—
-howmanyactivethreadsareconsidered,
-finitelimitationsonbuffers,
-theabilitytofetchenoughinstructionsfrom
multiplethreads,and
-practicallimitationsofwhatinstruction
combinationscanissuefromonethreadand
frommultiplethreads—canalsorestricthow
manyslotsareused.
28

29. Converting Thread-Level
Parallelism into Instruction-Level Parallelism
DesignChallengesinSMT
Becauseadynamicallyscheduledsuperscalarprocessorhasa
deeppipeline,coarse-grainedMTwillgainmuchinperformance.
SinceSMTmakessenseonlyinafine-grainedimplementation,we
shouldthinkabouttheimpactoffine-grainedschedulingonsingle-
threadperformance.
Thiseffectcanbeminimizedbyhavingapreferredthread,which
stillpermitsmultithreadingtopreservesomeofitsperformance
advantagewithasmallercompromiseinsingle-threadperformance.
29

30. Converting Thread-Level
Parallelism into Instruction-Level Parallelism
DesignChallengesinSMT
OtherdesignchallengesforanSMTprocessor:
Dealingwithalargerregisterfileneededtoholdmultiplecontexts.
Notaffectingtheclockcycle,particularlyininstructionissue,where
moreinstructionsneedstobeconsidered,andchoosingwhat
instructionstocommitmaybechallenging.
EnsuringthatthecacheandTLBconflictsgeneratedbythe
simultaneousexecutionofmultiplethreadsdonotcausesignificant
performancedegradationisalsochallenging.
30

31. Converting Thread-Level
Parallelism into Instruction-Level Parallelism
DesignChallengesinSMT
Inmanycases,thepotentialperformanceoverheaddueto
multithreadingissmall.
Theefficiencyofcurrentsuperscalarsislowenoughthatthereis
scopeforsignificantimprovement,evenatthecostofsomeoverhead.
31

32. Performance and Efficiency in Advanced
Multiple-Issue Processors
32

33. Performance and Efficiency in Advanced
Multiple-Issue Processors
Thequestionofefficiencyintermsofsiliconareaandpoweris
equallycritical.
Poweristhemajorconstraintonmodernprocessors.
TheItanium2isthemostinefficientprocessorbothforfloating-point
andintegercode.
TheAthlonandPentium4bothmakesgooduseoftransistorand
areaintermsofefficiency.
TheIBMPower5isthemosteffectiveuserofenergy.
Thefactthatnoneoftheprocessorsofferangreatadvantagein
efficiency.
33

34. Performance and Efficiency in Advanced
Multiple-Issue Processors
WhatLimitsMultiple-IssueProcessors?
Powerisafunctionofbothstaticpower(proportionaltothetransistor
count,whetherornotthetransistorsareswitching),anddynamic
power(proportionaltotheproductofthenumberofswitching
transistorsandtheswitchingrate).
Staticpoweriscertainlyadesignconcern,anddynamicpoweris
usuallythedominantenergyconsumer.
AmicroprocessortryingtoachievebothalowCPIandahighCR
mustswitchmoretransistorsandswitchthemfaster.
34

35. Performance and Efficiency in Advanced
Multiple-Issue Processors
WhatLimitsMultiple-IssueProcessors?
Mosttechniquesusedforincreasingperformance,(multiplecores
andmultithreading)willincreasepowerconsumption.
Thekeyquestioniswhetheratechniqueisenergyefficient?
Doesitincreasepowerconsumptionfasterthanitincreases
performance?
35

36. Performance and Efficiency in Advanced
Multiple-Issue Processors
WhatLimitsMultiple-IssueProcessors?
Thisinefficiency,arisesfromtwoprimarycharacteristics:
First,issuingmultipleinstructionsincurssomeoverheadinlogic
thatgrowsfasterthantheissuerategrows.
Thislogicisresponsibleforinstructionissueanalysis,including
dependencechecking,registerrenaming,andsimilarfunctions.
Thecombinedresultisthat,lowerCPIsarelikelytoleadtolower
ratiosofperformanceperwatt,simplyduetooverhead.
36

37. Performance and Efficiency in Advanced
Multiple-Issue Processors
WhatLimitsMultiple-IssueProcessors?
Second,thegrowinggapbetweenpeakissueratesandsustained
performance.
Thenumberoftransistorsswitchingwillbeproportionaltothe
peakissuerate,andtheperformanceisproportionaltothe
sustainedrate.
Forexample:Ifwewanttosustainfourinstructionsperclock,wemust
fetchmore,issuemore,andinitiateexecutiononmorethanfour
instructions.
Thepowerwillbeproportionaltothepeakrate,butperformance
willbeatthesustainedrate.
37

38. Performance and Efficiency in Advanced
Multiple-Issue Processors
WhatLimitsMultiple-IssueProcessors?
ImportanttechniqueforincreasingtheexploitationofILP(speculation)
—isinefficient…becauseitcanneverbeperfect.
Ifspeculationwereperfect,itcouldsavepower,sinceitwould
reducetheexecutiontimeandsavestaticpower.
Whenspeculationisnotperfect,itrapidlybecomesenergy
inefficient,sinceitrequiresadditionaldynamicpower.
38

39. Performance and Efficiency in Advanced
Multiple-Issue Processors
WhatLimitsMultiple-IssueProcessors?
Focusingonimprovingclockrate:
Increasingtheclockratewillincreasetransistorswitching
frequencyanddirectlyincreasepowerconsumption.
Toachieveafasterclockrate,wewouldneedtoincreasepipeline
depth.
Deeperpipelines,incuradditionaloverheadpenaltiesaswellas
causinghigherswitchingrates.
39

40. 40
This presentation is published only for educational purpose
[email protected]