Workload modeling for parallel computers [Elektronische Ressource] / Baiyi Song

107

pages

English

Documents

2006

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

107

pages

English

Documents

2006

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

Publié par

technischen_universitat_dortmund

Publié le

01 janvier 2006

Nombre de lectures

Langue

English

Poids de l'ouvrage

1 Mo

Workload Modeling for ParallelComputersBaiyi SongRobotic Research InstituteSection Information TechnologyThe University of DortmundA thesis submitted for the degree ofDoktor-IngenieurAcknowledgementsI want to thank all those who made this work possible by their supports.In particular, I want to express my appreciation to my doctorial advisor,Prof. Dr.-Ing. Uwe Schwiegelshohn, for the source of instructive guidanceand supports over the past years.I am grateful to all people at Robotic Research Institute at the Universityof Dortmund for the excellent working atmosphere. Especially, I would alsolike to thank Dr.-Ing. Ramin Yahyapour, whose e orts and expertise helpme to nish my study. I would like to express my gratitude to Dipl.-Inform.Carsten Ernemann, who give me many helpful suggestions and supports.I would also like to thank the Graduate School of Production Engineeringand Logistics at the University of Dortmund, which provides me not onlythe nancial supports but also the broad contacts with other departments.I would like to thank many of my chinese friends with them I had a pleasuretime in Dortmund.At last, I would like to thank my parents, my wife and my son, who alwaysencourage me with their love, belief and patience.AbstractThe availability of good workload models is essential for the design and anal-ysis of parallel computer systems.

Voir

Publié par

technischen_universitat_dortmund

Publié le

01 janvier 2006

Langue

English

Poids de l'ouvrage

1 Mo

Informatik

orkloadW

delingMo

for

Computers

Baiyi

Song

hResearcoticRobInstitute

hnologyecTInformationSection

The

thesis

UniversityofDortmund

theforsubmitted

Doktor-Ingenieur

degree

arallelP

tswledgemenknoAc

Iwanttothankallthosewhomadethisworkpossiblebytheirsupports.
Inparticular,Iwanttoexpressmyappreciationtomydoctorialadvisor,
Prof.Dr.-Ing.UweSchwiegelshohn,forthesourceofinstructiveguidance
andsupportsoverthepastyears.

IamgratefultoallpeopleatRoboticResearchInstituteattheUniversity
ofDortmundfortheexcellentworkingatmosphere.Especially,Iwouldalso
liketothankDr.-Ing.RaminYahyapour,whoseeﬀortsandexpertisehelp
metoﬁnishmystudy.IwouldliketoexpressmygratitudetoDipl.-Inform.
CarstenErnemann,whogivememanyhelpfulsuggestionsandsupports.
IwouldalsoliketothanktheGraduateSchoolofProductionEngineering
andLogisticsattheUniversityofDortmund,whichprovidesmenotonly
theﬁnancialsupportsbutalsothebroadcontactswithotherdepartments.
IwouldliketothankmanyofmychinesefriendswiththemIhadapleasure
und.Dortmintime

Atlast,Iwouldliketothankmyparents,mywifeandmyson,whoalways
encouragemewiththeirlove,beliefandpatience.

Abstract

Theavailabilityofgoodworkloadmodelsisessentialforthedesignandanal-
ysisofparallelcomputersystems.Aworkloadmodelcanbeapplieddirectly
inanexperimentalorsimulationenvironmenttoverifynewschedulingpoli-
ciesorstrategies.Moreover,itcanbeusedforextrapolatingandpredicting
futureworkloadconditions.Inthiswork,wefocusontheworkloadmod-
elingforparallelcomputers.Tothisend,westartwithanexaminationof
theoverallfeaturesoftheavailableworkloads.Here,weﬁndastrongse-
quentialdependencyinthesubmissionseriesofcomputationaljobs.Next,
anewapproachusingMarkovchainsisproposedthatiscapableofdescrib-
ingthetemporaldependency.Second,weanalyzethemissingattributes
insomeworkloads.Ourresultsshowthatthemissinginformationcanbe
stillrecoveredwhentherelevantmodelistrainedfromothercompletedata
set.Basedontheresultsofoverallworkloadanalysis,webegintoinspect
theworkloadcharacteristicsbasedonparticularuser-levelfeatures.That
is,weanalyzeindetailhowtheindividualusersuseparallelcomputers.
Inparticular,weclustertheusersintoseveralmanageablegroups,while
eachofthesegroupshasdistinctfeatures.Thesediﬀerentgroupsprovide
aclearexplanationfortheglobalcharacteristicsofworkloads.Afterwards,
weexaminetheuserfeedbacksandpresentanovelmethodtoidentifythem.
Theseevidencesindicatethatsomeusershaveanadaptivetendencyanda
completeworkloadmodelshouldnotignoretheusers’feedbacks.Thework
endswithabriefconclusiononthediscussedmodelingaspectsandgivesan
outlookonfuturework.

tstenCon

ductiontroIn11.1Motivation..................................
1.2OrganizationoftheThesis..........................

2WorkloadModelingforParallelComputers
2.1ParallelComputingEnvironment......................
2.2PerformanceEvaluationaUsingWorkloadModel.............
2.3ProblemswithExistingApproaches....................
2.4ProposalofaNewWorkloadModel.....................

3InvestigationofTemporalRelations
3.1ObservationsonTemporalRelations....................
3.2ModelingusingMarkovChainModel....................
3.2.1MarkovChainConstruction.....................
3.2.2CombinationofTwoMarkovChains................
3.3ExperimentalResults.............................
3.3.1StaticComparison..........................
3.3.2ComparisonofTemporalRelations.................
3.4Summary...................................

4AnalyzingMissingInformationinWorkloads
4.1MissingEstimatedRuntime.........................
4.2AnalysisofEstimatedRuntimeinCompleteWorkloads.........
4.2.1EstimationAccuracy.........................
4.2.2UserEstimations...........................
4.3ParameterizedDistributionModel.....................
4.3.1ModelSelection............................
4.3.2ModelingEstimatedRuntime....................
4.4ExperimentalResults.............................

114

77101216

212124272932323434

373738383939414347

CONTENTS

4.4.1StatisticComparison.........................
4.4.2DerivingaGeneralModel......................
4.5Summary...................................

UserGroup-basedAnalysisandModeling
5.1AnalysisofUser-levelSubmissions.....................
5.2ClusteringUsersintoGroups........................
5.2.1DataPreprocessing..........................
5.2.2JobClustering............................
5.2.3UserGrouping............................
5.2.4WorkloadModelingofIdentiﬁedUserGroups...........
5.3GenerationofSyntheticWorkloads.....................
5.4ExperimentalResults.............................
5.4.1AnalysisofJobCharacteristicfromUserGroups.........
5.4.2StatisticalComparison........................
5.5Summary...................................

ExaminationofImplicitUserFeedbacks
6.1FeedbackExamination............................
6.2FeedbackAnalysis..............................
6.2.1ImplicitFeedbackFactors......................
6.2.2ProblemSpeciﬁcation........................
6.2.3MethodSelection...........................
6.3Methodology.................................
6.3.1DataPreprocessing..........................
6.3.2FittingLinearRegressionModel..................
6.4ExperimentalResults.............................
6.4.1FeedbackVisualization........................
6.4.2ExclusionfromOtherFactors....................
6.4.3ComparisonoverAllWorkloads...................
6.5Summary...................................

DiscussionsandFurtherWork
7.1MoreObservationsoftheWorkloads....................
7.2FurtherWork.................................
7.3Summary...................................

Conclusion

474849

515153545455565757585960

6767686869707070727273747577

79798183

FiguresofList

2.12.22.32.42.52.62.7

3.13.23.33.43.5

4.14.24.34.44.54.6

5.15.25.35.4

Ajobisrepresentedbyarectangleinourstudy..............
Ajobisscheduledbyaschedulingsystem..................
Amediumnumberofuserssubmitjobstoaparallelsystem........
Theglobalworkloadmodelingstructure..................
Histogramofjobruntime..........................
HistogramofjobparallelismintheKTHworkload............
Anovelworkloadmodelstructure.....................

Continuousjobsubmissions.........................
Temporalrelationinthesequenceoftheparallelism...........
Temporalrelationinthesequenceoftheruntime.............
ProcessofcorrelatedMarkovchainsmodel.................
Comparisonofmodeledandoriginaldistributionsofruntimeandparal-
lelism.....................................

Therelationsoftheaccuracytotherealruntime.Here,onlythejobs
whoseaccuraciessmallerthan1.1areconsidered..............
Comparisonofmodeled(SIM)andoriginal(REAL)accuracies.....
Comparisonofmodeled(SIM)andoriginal(REAL)estimatedruntime.
TherelationsbetweentherealruntimeandtheparametersoftheBeta
distributionsforKTH.TherelationssimilarforthetracesofSDSCSP2
andCTC...................................
Comparisonofthesynthetic(SIM)realestimatedruntimes(REAL)..
Comparisonofthesynthetic(SIM)andrealestimatedruntimes(REAL)

Comparisonoftheaveragejobparallelismforindividualusers......
ProcessoftheMUGMmodel........................
AlgorithmforthePAMClustering.....................
2usergroupsareclusteredinKTHwiththeMUGMmodel........

iii

89912141516

2325262733

404444454747

52535659

5.55.65.7

6.16.26.36.4

7.17.27.37.4

LISTOFFIGURES4usergroupsareclusteredinKTHwiththeMUGMmodel........
6usergroupsareclusteredinKTHwiththeMUGMmodel........
4usergroupsareclusteredinLANLwiththeMUGMmodel.......

HistogramofthenumberofwaitingjobsinKTH.............
FeedbackdiscoveriesinKTH........................
FeedbackdiscoveriesinCTC........................
Feedbackdiscoveriesinthetimeframefrom1pmto4pminKTH....

DailycycleinKTH.Left:thenumberofjobsinthediﬀerenthoursof
day.Right:theaverageruntimeinthediﬀerenthoursofday......
WeekdayeﬀectinKTH.Left:thenumberofjobsinthediﬀerentdays
ofweek.Right:averageruntimeinthediﬀerentdaysofweek......
CombinationofcorrelatedMarkovchainandtheusergroupmodel..
ApplicationofNeuralnetworkforworkloadmodeling..........

606263

71747576

80808182

ablesTofList

2.1

3.13.23.33.43.53.63.7

4.14.24.34.44.54.64.74.84.9

5.15.25.3

UsedworkloadsfromtheSWFArchive...................

Percentageofneighboringjobswiththesameparallelismvalues.....
ExampleforderivingthestatesoftheMarkovchainfortheparallelism
DimensionsoftheMarkovchainsfortheparallelismandtheruntime..
Correlationcor0andcor1inexaminedworkloads.............
StaticComparisonofthemodeledandtheoriginalworkloads......
Comparisonofthecorrelationoftheparallelismandtheruntimefrom
theMarkovchainmodelandtheLublin/Feitelsonmodel.........
Comparisonoftheautocorrelationρ1oftheparallelismandtheruntime
sequencesfromMCM,PDM,andtheoriginalworkloads.........

22282931333434

Summaryofmissingestimatedruntimefortheexaminedworkloads...38
Analysisofthejobsexceedingtheirrealruntimes.............39
SummarizedalignmentoftheestimatedruntimeswithintheKTH,SDSC
SP2,CTCworkloads,totalalignment:82.7%...............41
AlignmentoftheestimatedruntimeswithintheLANLandKTHworkloads

Voir