Nanothreads-vs.-Fibers-for-the-Support-of-Fine-Gra

Nanothreadsvs.FibersfortheSupportofFineGrainParallelismonWindowsNT/2000PlatformsVasileiosK.Barekas,PanagiotisE.Hadjidoukas,EleftheriosD.Polychronopoulos,andTheodoreS.PapatheodorouHighPerformanceInformationSystemsLaboratoryDepartmentofComputerEngineeringandInformatics,UniversityofPatrasRio26500,Patras,Grecce{bkb,peh,edp,tsp}@hpclab.ceid.upatras.gr:theuser-levelthreadpackages,theruntimelibrariesandtheapplicationslevel.TheresultsdemonstratethatnanothreadsoutperformtheWindowsfibers.Theperformancegainsofthethreadcreationandcontextswitchingmechanismsarereflectedonbothruntimelibraries.Experimentswithfine-grainapplicationsdemon-strateupto40%higherspeedupinthecaseofnanothreadscomparedtothatoffibers.1IntroductionDuringthelastfewyears,therehavebeensignificanttechnologicaladvancesintheareaofworkstationsandservers.Thesesystemsarebasedonlow-costmulti-processorconfigurationsrunningconventionaloperatingsystems,likeWindowsNT.Althoughtheperformanceofthesesystemsiscomparabletothatofothermoreexpensivesmall-scaleUnix-basedmultiprocessors,thesoftwareusedisin-adequatetoutilizetheexistinghardwareefficiently.Parallelprocessingonthesesystemsisinaprimitivestage,duetothelackofappropriatetoolsfortheeffi-cientimplementationofparallelapplications.Theparallelizationofasequentialapplicationrequirestheexplicituseandknowledgeoftheunderlyingthreadar-chitecture.Furthermore,theuserhimselfmustdetectthepotentialparallelism.Asweshowinthispaper,theexistingsupportprovidedbytheWindowsisinad-equatefortheefficientimplementationofawiderangeofparallelapplications.M.Valeroetal.(Eds.):ISHPC2000,LNCS1940,pp.146–159,2000.c
Springer-VerlagBerlinHeidelberg2000Nanothreadsvs.FibersfortheSupportofFineGrainParallelism147Ontheotherhand,mostofthehigh-endmultiprocessorsrunningUnix-likeoperatingsystemprovideadequateandconvenienttoolstotheuserinordertobuildparallelapplications,whichcanbeexecutedwiththelowestpossibleoverhead.Suchadvancedtoolsconsistofanautomaticparallelizingcompiler,anoptimizedmulti-threadingruntimelibraryandtheappropriateoperatingsystemsupport[1,3].Directivesareinsertedmanuallyorautomaticallyatcompiletimeintothesequentialcodetospecifytheexistingparallelism[11].ThemodifiedcodeisanalyzedandthedirectivesareinterpretedintoappropriateruntimeAPIfunctions.Thefinalcodeiscompiledandlinkedwiththeruntimelibrarytoproducetheparallelizedexecutable.Inthispaper,wepresenttheimplementationoftwomultithreadedruntimelibraries,bothbasedonuser-levelthreadsrunningonWindows2000.Theseli-brariesarespeciallydesignedtoprovidetheuserwiththenecessarysupportfortheefficientparallelizationofapplications.Thefirstlibrary,calledFibRT(FibersRunTime),usesthestandardWindowsfibers,whilethesecondone,calledNTLib(NanoThreadsLibraryforNT),usesnanothreads,acustomuser-levelthreadspackage.TheNTLibruntimelibrarywasportedtoWindows2000operatingsystemfromitsoriginalimplementationontheIRIXoperatingsystem[1].BothFibRTandNTLiblibrariesareimplementedaccordingtotheNanothreadsPro-grammingModel[12].TheselibrariesexportthesameAPItotheuser,providingthesamefunctionality.Fortherestofthispaper,thetermruntimelibrarywillrefertobothFibRTandNTLib,unlessotherwisespecified.Wecomparebothimplementationsintermsofruntimeoverhead,andtheperformancegainsbyusingthemintheparallelizationandexecutionofrealapplications.Therestofthispaperisorganizedasfollows;Section2providesthenecessarybackground.InSection3,wepresentthetworuntimelibrariesintroducedinthispaper,togetherwiththenecessarydetailsofourimplementations.PerformancestudyandexperimentalresultsarepresentedinSection4.InSection5,wepresentrelatedwork;finally,wesummarizeinSection6.2BackgroundInthissectionweoutlinethemultithreadingsupportprovidedintheWindows2000operatingsystem,forbothkernel-levelanduser-levelthreads,alongwiththeNanothreadsProgrammingModel.2.1WindowsMultithreadedArchitectureTheWindows2000operatingsystemsupportsmultiplekernel-levelthreads,throughapowerfulthreadmanagementAPI[14].Thesethreadsaretheop-eratingsystem’ssmallestkernel-levelobjectsofexecutionandprocessesmayconsistofoneormorethreads.Eachthreadcancreateotherthreadsthatsharethesameaddressspaceandsystemresourceshavinghowever,independentex-ecutionstackandthreadspecificdata.Kernel-levelthreadsarescheduledonasystemwidebasisbythekernelinordertobeexecutedonaprocessor.It148VasileiosK.Barekasetal.isthroughthreadsthatWindowsallowsprogrammerstoexploitthebenefitsofconcurrencyandparallelism.Sincethesethreadsarekernel-level,theirstateresidesintheoperatingsystemkernel,whichisresponsiblefortheirscheduling.Besidesk