Homework #4 Double Trouble

CS360 Homework #4

Instruction /Notes:
Readthesecarefully
• Pleasereadallthepointsofthe“Notes”sections- they’reimportantforthis
Homework!!!

• YouarenotrequiredtodoanyplottinginthisHomework- onlyincertain
problemstoprovidethetuplesthatwouldgenerateaplot.Youcanthen
optionallyplot(inthenotebookwithmatplotlib, inExcel,wherever
works)
• Youmay createnewIPythonnotebookcellstousefore.g.testing,
debugging,exploring,etc.- thisis encouragedin fact! - justmakesure
thatyourfinalanswerforeachquestionisinitsowncell andclearly
indicated
• SeeCS360_2017S@Facebookforsubmissioninstructions
• Havefun!
1.Problem1:DoubleTrouble
[50%points]
Inthisproblem, we’llexploreanoptimizationoftenreferredtoasdouble
buffering,whichwe’llusetospeeduptheexternalmergesortalgorithmwesaw
inCh.9.
Althoughwehaven’texplicitlymodeleditinmanyofourcalculationssofar,
recallthatsequentialIO (i.e.involvingreadingfrom/writingtoconsecutive
pages)isgenerallymuchfasterthatrandomaccessIO (anyreading/writingthat
isnotsequential).Additionally,onnewermemorytechnologieslikeSSDreading
datacanbefasterthanwritingdata(ifyouwanttoreadmoreaboutSSDaccess
patternslookhere).
Inotherwords,forexample,ifweread4consecutivepagesfromfileA,this
shouldbemuchfasterthanreading1pagefromA,then1pagefromfileB,then
thenextpagefromA.
Inthisproblem,wewillbegintomodelthis,byassumingthat3/4sequential
READS are“free”,i.e.thetotalcostof4sequentialreadsis1IO.Wewillalso
assumethatthewritesarealwaystwiceasexpensiveasaread.Sequentialwrites
areneverfree thereforethecostofNwritesisalways2N.
1.1 Otherimportantnotes:
• NOREPACKING:Considertheexternalmergesortalgorithmusingthe
basicoptimizationswepresentinCh.9,butdonotusetherepacking
optimizationcoveredinCh.9.
• ONEBUFFERPAGE RESERVEDFOROUTPUT:Assumeweuseonepagefor
outputina merge,e.g.aB-waymergewouldrequireB+1bufferpages
• REMEMBERTOROUND:Takeceilings(i.e.roundinguptonearestinteger
values)intoaccount inthisproblemforfullcredit!Notethatwehave
sometimesomittedthese(forsimplicity)inlecture.
• Considerworstcasecost:Inotherwords,if2readscouldhappentobe
sequential,butingeneralmightnotbe,considertheserandomIO
1.2Part(a)
[30% points]
Consideramodificationoftheexternalmergesortalgorithmwherereadsare
alwaysreadin4-pagechunks(i.e.4pagessequentiallyatatime) soastotake
advantageofsequentialreads.Calculatethecostofperformingtheexternal
mergesortforasetuphavingB+1=20bufferpagesandanunsortedinputfile
with160pages.
Showthestepsofyourworkandmakesuretoexplainyourreasoningbywriting
themaspythoncommentsabovethefinalanswers.
Part(a.i) Whatistheexact IOcostofsplitting andsortingthefiles?Asis
standardwewantrunsofsizeB+1.
In [ ]: io_split_sort =
Part(a.ii) Afterthefileissplitandsorted,wecanmergenrunsinto1using
themergeprocess.Whatislargestnwecouldhave,givenreadsarealwaysread
in4-pagechunks?Note:thisisknownasthearityofthemerge.
In [ ]: merge_arity =
Part(a.iii) Howmanypassesofmergingarerequired?
In [ ]: merge_passes =
Part(a.iv) WhatistheIOcostofthefirstpassofmerging?Note:thehighest
aritymergeshouldalwaysbeused.
In [ ]: merge_pass_1 =
Part(a.v) WhatisthetotalIOcostofrunningthisexternalmergesort
algorithm?Donotforgettoaddintheremainingpasses(ifany)ofmerging.
In [ ]: total_io =
1.3Part(b)
[10% points]
Now,we’llgeneralizethereasoningabovebywritingapythonfunctionthat
computestheapproximate* costofperformingthisversionofexternalmerge
sortforasetuphavingB+1bufferpages,afilewithNpages,andwherewe
nowreadinP-pagechunks(replacingourfixed4pagechunksinPart(a)).
**Note:ourapproximationwillbeasmallone- for simplicity,we’llassumethat
eachpassofthemergephasehasthesameIOcost,whenactuallyitcanvary
slightly...Everythingelsewillbeexactgivenourmodel*
!
We’llcallthisfunctionexternal_merge_sort_cost(B, N, P),andwe’ll
computeitasthe productofthecostofreadinginandwritingoutallthedata
(whichwedoeachpass),andthenumberofpasseswe’llhavetodo.
Eventhoughthisisanapproximation,makesuretotakecareoffloor/ceiling
operations- i.e.roundingdown/uptointegervaluesproperly!
Importantly,tosimplifyyourcalculations:Yourfunctionwillonlybeevaluatedon
caseswherethefollowinghold*
:
• (B+1)%P==0 (i.e.thebuffersizeisdivisiblebythechunksize)
• N%(B+1)==0 (i.e.thefilesizeisdivisiblebythebuffersize)
Part(b.i) First,let’swriteapythonfunctionthatcomputestheexacttotalIO
costtocreatetheinitialruns:
In [ ]: def cost_initial_runs(B, N, P):
 # YOUR CODE HERE
Part(b.ii) Next,let’swriteapythonfunctionthatcomputestheapproximate*
totalIOcosttoreadinandthenwriteoutallthedataduringonepassofthe
merge:
In [ ]: def cost_per_pass(B, N, P):
 # YOUR CODE HERE
*Notethatthisisanapproximation:whenwereadinchunksduringthemerge
phase,thecostperpassactuallyvariesslightlydueto‘roundingissues’whenthe
fileissplitupintoruns... butthisisasmalldifference
Part(b.iii) Next,let’swriteapythonfunctionthatcomputestheexacttotal
numberofpasseswe’llneedtodo
In [ ]: def num_passes(B, N, P): 
 # YOUR CODE HERE
Finally,ourtotalcostfunctionis:
In [ ]: def external_merge_sort_cost(B, N, P):
 return cost_initial_runs(B,N,P) +
 cost_per_pass(B,N,P)*num_passes(B,N,P)
1.4Part(c)
[10% points]
ForB+1=100andN=900,findtheoptimalPaccordingtoyourIOcost
equationabove.ReturnboththeoptimalPvalue(Popt)andthelistoftuplesfor
feasiblevaluesofP thatwouldgenerateaplotofPvs.IOcost,atresolution=
1(everyvalueofP),storedaspoints:
In [ ]: # Save the optimal value here
P=
# Save a list of tuples of (P, io_cost) here,
# for all feasible P’s
points =
*
Belowweprovidestartercodeforusingmatplotlibinthenotebook,ifyouwant
togeneratethegraphofPvs.IOcost;howeveranyothersoftwarethatallows
youtovisualizetheplot(Excel,Googlespreadsheets,MATLAB,etc)isfine!
In [ ]: # Shell code for plotting in matplotlib
 %matplotlib inline
 import matplotlib.pyplot as plt
 # Plot
 plt.plot(*zip(*points))
 plt.show()
2.Problem2:IOCostModels
[30% points]
Inthisproblemweconsiderdifferentjoinalgorithmswhenjoining relations
R(A,B), S(B,C),andT(C,D).Wewanttoinvestigatethecostofvariouspairwise
joinplansandtrytodeterminethebestjoinstrategygivensomeconditions.
Specifically,foreachpartof thisquestion,weareinteresteddeterminingsome
(orall)ofthefollowingvariables:
• P_R:NumberofpagesofR
• P_S:NumberofpagesofS
• P_RS:Numberofpagesofoutput(andinput)RS
• P_T:NumberofpagesofT
• P_RST:Numberofpages ofoutput(andinput)RS
• B:Numberofpagesinbuffer
• IO_cost_join1:TotalIOcostoffirstjoin
• IO_cost_join2:TotalIOcostofsecondjoin
Note:
• Theoutputofjoin1isalwaysfeed asoneoftheinputstojoin2
• Usethe“vanilla”versionsofthealgorithmsaspresentedinlecture, i.e.
withoutanyof
theoptimizationswementioned
• Againassumeweuseonepageforoutput,asinlecture!
• TheabbreviatesforthejoinsusedareSort-MergeJoin(SMJ),HashJoin
(HJ),andBlockNested
LoopJoin(BNLJ).
2.1 Part(a)
[15% points]
Given:
• P_R:10
• P_S:100
• P_T:1000
• P_RS:50
• P_ST:500
• P_RST:250
• B:32
ComputetheIOcostforthefollowingqueryplans:
• IO_Cost_HJ_1whereonlyhashjoinisused,join1 = R(a, b), S(b,
c) andjoin2 = join1(a, b, c), T (c, d)
• IO_Cost_HJ_2whereonlyhashjoinisused,join1 = T (c, d), S(b,
c) andjoin2 = join1(b, c, d), R(a, b)
• IO_Cost_SMJ_1whereonlysortmergejoinisused,join1 = R(a, b),
S(b, c) andjoin2 = join1(a, b, c), T (c, d)
• IO Cost_ SMJ_ 2whereonlysortmergejoinisused,join1 = T (c, d),
S(b, c) andjoin2 = join1(b, c, d), R(a, b)
• IO_Cost_BNLJ_1whereonlyblocknestedloopjoinisused,join1 = R(a,
b), S(b, c) andjoin2 = join1(a, b, c), T (c, d)
• IO_Cost_BNLJ_2whereonlyblocknestedloopmergejoinisused,join1
= T (c, d), S(b, c) andjoin2 = join1(b, c, d), R(a, b)
Note:again,becarefulofroundingforthisproblem.Useceiling/floorswhenever
itisnecessary.
Include1-2sentences(asapythoncomment)aboveeachanswerexplainingthe
performanceforeachalgorithm/queryplan.
In [ ]: IO_Cost_HJ_1 =
 IO_Cost_HJ_2 =
 IO_Cost_SMJ_1 =
 IO_Cost_SMJ_2 =
 IO_Cost_BNLJ_1 =
IO_Cost_BNLJ_2 =
2.2 Part(b)
[15% points]
Forthequeryplanwherejoin1 = R(a,b),S(b,c) andjoin2 =
join1(a,b,c),T(c,d) findaconfigurationwhereusingHJforjoin1 andSMJ
forjoin2 ischeaperthanSMJforjoin1 andHJforjoin2.Theoutputsizesyou
chooseforP_RSandP_RSmustbenon-zeroandfeasible(e.g.themaximum
outputsizeofjoin1 isP_R*P_S).
In [ ]: P_R =
 P_S =
 P_T =
 P_RS =
 P_RST =
B =
HJ_IO_COST_join1 =
SMJ_IO_COST_join2 =
SMJ_IO_COST_join1 =
HJ_IO_COST_join2 =
3.Problem3:SequentialFlooding
[20% points]
Note:Beforedoingthisquestion,itishighlyrecommendedthatyougothrough
Pr_12,whichcoversevictionpoliciesforbuffermanagerssuchasLRU,andwhy
sequentialfloodingcansometimesoccurswithLRU.
InthepracticeaccompanyingCh. 12,wesawsomethingcalledsequential
flooding thatcanoccurwhenadefaultevictionpolicy(forexampleLRU)isused
bythebuffermanager.WesawthatwecanachievemuchlowerIOcostbyusing
adifferentevictionpolicy,MRU(“mostrecentlyused”).
Notethat“Mostrecentlyused”meansmostrecentlyaccessed,eitherfrombuffer
ordisk,consistentwithwhatweshowedinPr_12.
Forthisproblem,wewilltakeacloserlookattheIOcostofdifferenteviction
policieswhenreadingthepagesofafilesequentiallymultipletimes.
3.1 Part(a.i)
[2% points]
Writeapythonfunctionlru_cost(N, M, B) thatcomputestheIOcostofthe
LRUevictionpolicywhenreadinginallthepagesofanN-pagefilesequentially,M
times,usingabuggerwithB +1pages.Assumethatafterreadingthefiles,you
don’tneedtowritethemout(youcanjustreleasethem,sothereisnowriteIO
cost).
In [ ]: def lru_cost(N, M, B):
 # YOUR CODE HERE
3.2 Part(a.ii)
[4% points]
Writeapythonfunctionmru_cost(N, M, B) thatcomputestheIOcostofthe
MRUevictionpolicywhenreadinginallthepagesofanN -pagefilesequentially,
M times,usingabuggerwithB +1pages.Assumethatafterreadingthefiles,
youdon’tneedtowritethemout(youcanjustreleasethem,sothereisnowrite
IOcost).
In [ ]: def mru_cost(N, M, B):
 # YOUR CODE HERE
3.3 Part(a.iii)
[4% points]
Nowthatyouhavewrittenthesefunctions,providethetupleswhichgenerate
theplotofMvs.theabsolutevalueofthedifferencebetweenLRUandMRUin
termsofIOcost forB=6,N=10,andMbetween1and20inclusive(savedas
thevariablep3_lru_points)
In [ ]: B = 6
 N = 10
 M = 20
 # Provide a list of tuple (m, difference between LRU
 # and MRU in terms of IO cost) here:
 p3_lru_points =
Again,youcanoptionallyplotyouranswertocheckthatitseemsreasonablestartercodefordoingthisinthenotebookbelow:
In [ ]: # Shell code for plotting in matplotlib
 %matplotlib inline
 import matplotlib.pyplot as plt
 # Plot
 plt.plot(*zip(*p3_lru_points))
 plt.show()
3.4 Part(b)
[8+2% points]
RecallthattheLRUevictionpolicyremovestheleastrecentlyusedpagewhenthe
bufferisfullandanewpageisreferencedwhichisnotthereinbuffer.Thebasic
ideabehindLRUisthatyoutimestampyourbufferelements,andusethe
timestampstodecidewhentoevictelements.Doingsoefficiently,requiressome
seriousbook-keeping,thisiswhyinpracticemanybuffermanagerstryto
approximateLRUwithotherevictionpoliciesthatareeasiertoimplement.
HerewewillfocusontheCLOCK orSecondChance policy.IntheCLOCKeviction
policy,thecandidatepagesforremovalareconsideredleft-to-rightinacircular
manner(withwraparound),andapagethathasbeenaccessedbetween
consecutiveconsiderationswillnotbereplaced.Thepagereplacedistheone
that- consideredinacircularmanner- hasnotbeenaccessedsinceitslast
consideration.
InmoredetailstheCLOCKpolicyproceedsmaintainsacircularlistofpagesinthe
bufferandusesanadditionalclock(orsecondchance) bitforeachpagetotrack
howoftenapageisaccessed.Thebitisset
to1wheneverapageisreferenced.Whenclockneedstoreadinanewpagein
thebuffer,itsweepsoverexistingpagesinthebufferlookingforonewith
secondchancebitsetto0.Itbasicallyreplacespagesthathavenotbeen
referencedforonecompleterevolutionoftheclock.
Ahigh-levelimplementationofclock:1.Associatea“secondchance”bitwith
eachpageinthebuffer.InitializeallbitstoZERO(0).2.Eachtimeapageis
referencedinthebuffer,setthe“secondchance”bittoONE(1).thiswillgivethe
pageasecondchance...3.Anewpagereadintoabufferpagehasthesecond
chancebitsettoZERO(0).4.Whenyouneedtofindapageforremoval,lookin
left-to-rightinacircularmanner(withwraparound)inthebufferpages:- Ifthe
secondchancebitisONE,resetitssecondchancebit(toZERO)andcontinue.- If
thesecondchancebitisZERO,replacethepageinthebuffer.
YoucanfindmoredetailsonCLOCKhere.
Part(b.i) Writeapythonfunctionclock_cost(N, M, B) thatcomputesthe
IOcostoftheCLOCKevictionpolicywhenreadinginallthepapgesofanN -page
filesequentially,M times,usingabuggerwithB +1pages.Assumethatafter
readingthefiles,youdon’tneedtowritethemout(youcanjustreleasethem,so
thereisnowriteIOcost).
In [ ]: def clock_cost(N, M, B):
 # YOUR CODE HERE
Part(b.ii) NowthatyouhavewrittentheCLOCKcostfunction,providethe
tupleswhichgeneratetheplotofMvs.theabsolutevalueofthedifference
betweenLRUandCLOCKintermsofIOcost forB=6,N=10,andMbetween1
and20inclusive(savedasthevariable p3_clock_points).
In [ ]: B = 6
 N = 10
 M = 20
 p3_clock_points = [(m, abs(lru_cost(N, m, B)
 - clock_cost(N, m, B)))
for m in range(1, M+1)]
DoestheCLOCKevictionpolicypreventsequentialflooding?Howdoesit
performagainstLRU?Writeashortexplanationinthefieldbelow.
In [ ]: # EXPLANATION GOES HERE