復旦大學信息科學與 共6 考試形式：√開卷□閉 2007年6專 學 成—二—二三四五 int int Supposetheabovecodegeneratesthefollowingassemblycode:pushl%ebppushl%ebxmovl8(%ebp),%ecxmovl12(%ebp),%ebxleal(%ecx,%ecx,6),%edxsall$2,%edxmovl%ebx,%eaxsall$3,%eaxsall$3,%eaxmovlarray2(%eax,%ecx,4),%eaxmovl%eax,array1(%edx,%ebx,4)popl%ebxpopl%ebp（（裝訂線內不要答題）復旦大學信息科學與 共6 考試形式：√開卷□閉 2007年6（120分鐘，答案必須寫在試卷上，做在草稿紙上無效專 學 成 —二三四五Problem1.Considerthesourcecodebelow.Manreconstantsdeclaredwith#define.intarray1[M][N];intarray2[N][M];{}Supposetheabovecodegeneratesthefollowingassemblycode:pushl%ebppushl%ebxsall$2,%edxmovl%ebx,%eaxsall$3,%eaxsubl%ebx,%eaxsall$3,%eaxmovlarray2(%eax,%ecx,4),%eaxmovl%eax,array1(%edx,%ebx,4)popl%ebxmovl%ebp,%esppopl%ebpM N-1M N-1ProblemConsiderthefollowingassemblyrepresentationofafunctionfoocontainingaforpushl%ebpmovl%esp,%ebppushl%ebxmovl8(%ebp),%ebxleal4(%ebx),%edxxorl%ecx,%ecxcmpl%ebx,%ecxjlleal2(%ecx,%edx,2),%edxleal4(%ecx),%eaximull%eax,%edxl%ecxcmpl%ebx,%ecxjge.L6movl%edx,%eaxpopl%ebxmovl%ebp,%esppopl%ebpBasedontheassemblycodeabove,fillintheblanksbelowinitscorrespondingCsourcebelow—donotuseregisternames.)Fillintheblankstoprovidethefunctionalityoftheintfoo(int{intintresult= for( ; ;i++) }return}-2ProblemConsiderthefollowingassemblyrepresentationofafunctionfoocontainingaforpushl%ebppushl%ebxxorl%ecx,%ecxcmpl%ebx,%ecxjl.L4leal4(%ecx),%eaxl%ecxjge.L6popl%ebxpopl%ebpBasedontheassemblycodeabove,fillintheblanksbelowinitscorrespondingCsourcecode.(Note:youmayonlyusethesymbolicvariablesi,a,andresultinyourexpressionsbelow—donotuseregisternames.)Fillintheblankstoprovidethefunctionalityoftheintfoo(int{intintresult ;i++);;}return}-2ProblemConsiderthefollowingfunctionforcomputingtheproductofanarrayofnintegers.Wehaveunrolledtheloopbyafactorof3.intaprod(inta[],int{inti,x,y,z;intr=1;for(i=0;i<n-2;i+=3)x=a[i];y=a[i+1];z=r=r*x*y*z;//Product}for(;i<n;r*=a[i];returnr;}ForthelinelabeledProductcomputation,wecanuseparenthesestocreate5differentassociationsofthecomputation,asfollows:r=((r*x)*y)*z;//A1r=(r*(x*y))*z;//A2r=r*((x*y)*z);//A3r=r*(x*(y*z));//A4r=(r*x)*(y*z);//Weexpresstheperformanceofthefunctionintermsofthenumberofcyclesperelement(CPE).Asdescribedinthebook,thismeasureassumestheruntime,measuredlockcycles,foranarrayoflengthnisafunctionoftheformCn+K,whereCistheCPE.Wemeasuredthe5versionsofthefunctiononanInPentiumIII.Recallthattheintegermultiplicationoperationonthismachinehasalatencyof4cyclesandanissuetimeof1ThefollowingtableshowssomevaluesoftheCPE,andothervaluesmissing.ThemeasuredCPEvaluesarethosethatwereactuallyobserved.“TheoreticalCPE”meansthatperfor-mancethatwouldbeachievediftheonlylimitingfactorwerethelatencyandissuetimeoftheintegermultiplier.MeasuredTheoretical4/3=8/3=Fillinthemissingentries.ForthemissingvaluesofthemeasuredCPE,youcanusethevaluesfromotherversionsthatwouldhavethesamecomputationalbehavior.ForthevaluesofthetheoreticalCPE,youcandetermhenumberofcyclesthatwouldberequiredforanitionconsideringonlythelatencyandissuetimeofthemultiplier,andthendivideby-3ProblemConsiderthefollowingfunctionforcomputingtheproductofanarrayofnintegers.Wehaveunrolledtheloopbyafactorof3.intaprod(inta[],int{inti,x,y,z;intr=1;for(i=0;i<n-2;i+=3)x=a[i];y=a[i+1];z=r=r*x*y*z;//Product}for(;i<n;r*=a[i];returnr;}ForthelinelabeledProductcomputation,wecanuseparenthesestocreate5differentassociationsofthecomputation,asfollows:r=((r*x)*y)*z;//A1r=(r*(x*y))*z;//A2r=r*((x*y)*z);//A3r=r*(x*(y*z));//A4r=(r*x)*(y*z);//A5Weexpresstheperformanceofthefunctionintermsofthenumberofcyclesperelement(CPE).Asdescribedinthebook,thismeasureassumestheruntime,measuredlockcycles,foranarrayoflengthnisafunctionoftheformCn+K,whereCistheCPE.Wemeasuredthe5versionsofthefunctiononanInPentiumIII.Recallthattheintegermultiplicationoperationonthismachinehasalatencyof4cyclesandanissuetimeof1ThefollowingtableshowssomevaluesoftheCPE,andothervaluesmissing.ThemeasuredCPEvaluesarethosethatwereactuallyobserved.“TheoreticalCPE”meansthatperfor-mancethatwouldbeachievediftheonlylimitingfactorwerethelatencyandissuetimeoftheintegermultiplier.MeasuredTheoretical4/3=8/3=Fillinthemissingentries.ForthemissingvaluesofthemeasuredCPE,youcanusethevaluesfromotherversionsthatwouldhavethesamecomputationalbehavior.ForthevaluesofthetheoreticalCPE,youcandetermhenumberofcyclesthatwouldberequiredforanitionconsideringonlythelatencyandissuetimeofthemultiplier,andthendividebyProblemConsidertheCprogrambelow.(Forspacereasons,wearenotcheckingerrorreturncodes,soassumethatallfunctionsreturnnormally.)intmain()if(fork()==0)if(fork()==0)}elsepid_tpid;intif((pid=wait(&status))>0){}}}else}return0;}Foreachofthefollowingstrings,circlewhether(Y)ornot(N)thisstringisapossibleoutputoftheprogram.A.YNB.YNC.YND.YNE.YN-4-3ProblemThefollowingproblemconcernsdynamicstorage locatorthatusesanimplicit list.Thelayoutofeachallocatedandmemoryblockisasfollows: 21 BlockSize BlockSize Eaemoryblock,eitherallocatedor,hasasizethatisamultipleofeightbytes.Thus,onlythe29higherorderbitsintheheaderandfooreneededtorecordblocksize,ludestheheaderandfooter.Theusageoftheremaining3lowerorderbitsisasbit0indicatestheuseofthecurrentblock:1forallocated,0 bit1indicatestheuseofthepreviousadjacentblock:1forallocated,0 bit2isunusedandisalwayssettobeFivehelperroutinesaredefinedtofacilitatetheimplementationof (void*p).Thefunctionalityofeachroutineiinedinthecommentabovethefunctiondefinition.Fillinthebodyofthehelperroutinesthecodesectionlabelthatimplementthecorrespondingfunctionalitycorrectly./*givenapointerpto locatedblock,i.e.,pisapointerreturnedbysomepreviousmalloc()/realloc()call;returnsthepointertotheheaderoftheblock*/void*header(void*{void returnptr;}ptr=(void*)((int*)p-ptr=(void*)((int*)p-/*givenapointertoavalidblockheaderorfooter,returnsthesizeoftheblock*/-5ProblemConsidertheCprogrambelow.(Forspacereasons,wearenotcheckingerrorreturncodes,soassumethatallfunctionsreturnnormally.)intmain()if(fork()==0)if(fork()==0)}elsepid_tpid;intif((pid=wait(&status))>{}}}else}return0;}Foreachofthefollowingstrings,circlewhether(Y)ornot(N)thisstringisapossibleoutputoftheprogram.A.YNB.YNC.YND.YNE.YNintsize(void{int returnresult;}result=((*(charresult=(*(int/*givenapointerp locatedblock,i.e.papointerreturnedbysomepreviousmalloc()/realloc()call;returnsthepointertothefooteroftheblock*/void*footer(void{void returnptr;}/*givenapointertoavalidblockheaderorfooter,returnstheusageofthecurrectblock,1forallocated,0for intallocated(void*hp){int return}result=(*(intresult=(*(int/*givenapointertoavalidblockreturnsthepointertotheheaderofpreviousblockinmemory*/void*prev(void*hp){void returnptr;}ptr=hp-ptr=hp-size(hp-ptr=hp-size(hp-4)+-6-4ProblemThefollowingproblemconcernsdynamicstorageConsiderlocatorthatusesanimplicitlist.Thelayoutofeachallocatedandmemoryblockisasfollows: 21||||||||||||||||||||||||Eaemoryblock,eitherallocatedor,hasasizethatisamultipleofeightbytes.Thus,onlythe29higherorderbitsintheheaderandfooreneededtorecordblocksize,whichludestheheaderandfooter.Theusageoftheremaining3lowerorderbitsisasfollows:bit0indicatestheuseofthecurrentblock:1forallocated,0 bit1indicatestheuseofthepreviousadjacentblock:1forallocated,0 bit2isunusedandisalwayssettobeFivehelperroutinesaredefinedtofacilitatetheimplementationof (void*p).Thefunctionalityofeachroutineiinedinthecommentabovethefunctiondefinition.Fillinthebo