资源描述：
《lecture 22 advanced topics》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、MITOpenCourseWarehttp://ocw.mit.edu6.046JIntroductiontoAlgorithms,Fall2005Pleaseusethefollowingcitationformat:ErikDemaineandCharlesLeiserson,6.046JIntroductiontoAlgorithms,Fall2005.(MassachusettsInstituteofTechnology:MITOpenCourseWare).http://ocw.mit.edu(accessedMMDD,YYYY).License:CreativeCommonsAt
2、tribution-Noncommercial-ShareAlike.Note:Pleaseusetheactualdateyouaccessedthismaterialinyourcitation.FormoreinformationaboutcitingthesematerialsorourTermsofUse,visit:http://ocw.mit.edu/termsMITOpenCourseWarehttp://ocw.mit.edu6.046JIntroductiontoAlgorithms,Fall2005Transcript–Lecture22Weonlyhavefourmo
3、relecturesleft,andwhatProfessorDemaineandIhavedecidedtodoisgivetwoseriesoflecturesonsortofadvancedtopics.So,todayatWednesdaywe'regoingtotalkaboutparallelalgorithms,algorithmswhereyouhavemorethanoneprocessorwhackingawayonyourproblem.Andthisisaveryhottopicrightnowbecauseallofthechipmanufacturersareno
4、wproducingso-calledmulticoreprocessorswhereyouhavemorethanoneprocessorperchip.So,knowingsomethingaboutthatisgood.Thesecondtopicwe'regoingtocoverisgoingtobecaching,andhowyoudesignalgorithmsforsystemswithcache.Rightnow,we'vesortofprogramtoeverythingasifitwerejustasinglelevelofmemory,andforsomeproblem
5、sthat'snotanentirelyrealisticmodel.You'dliketohavesomemodelforhowthecachinghierarchyworks,andhowyoucantakeadvantageofthat.Andthere'sbeenalotofresearchinthatareaaswell.So,bothofthoseactuallyturnouttobemyareaofresearch.So,thisisactuallyfunforme.Actually,mostofit'sfunanyway.So,todaywe'lltalkaboutparal
6、lelalgorithms.Andtheparticulartopic,itturnsoutthattherearelotsofmodelsforparallelalgorithms,andforparallelism.Andit'soneofthereasonsthat,whereasforserialalgorithms,mostpeoplesortofhavethisbasicmodelthatwe'vebeenusing.It'ssometimescalledarandomaccessmachinemodel,whichiswhatwe'vebeenusingtoanalyzethi
7、ngs,whereasintheparallelspace,there'sjustahugenumberofmodels,andthereisnogeneralagreementonwhatisthebestmodelbecausetherearedifferentmachinesthataremadewithdifferentconfigurations,etc.andpeoplehaven't,sorto
