1/20/11%1%CS%61C:%Great%Ideas%in%Computer%Architecture%(Machine%Structures)%Instructors:%Randy%H.%Katz%David%A.%PaGerson%hGp://inst.eecs.Berkeley.edu/~cs61c/sp11%1%Apeinf%2011%MM%Lecture%#2%1/20/11%Review%• CS61c:%Learn%5%great%ideas%in%computer%architecture%to%enable%high%performance%programming%via%parallelism,%not%just%learn%C%1. Layers%of%RepresentaVon/InterpretaVon%2. Moore’s%Law%3. Principle%of%Locality/Memory%Hierarchy%4. Parallelism%5. Performance%Measurement%and%Improvement%6. Dependability%via%Redundancy%• Post%PC%Era:%Parallel%processing,%smart%phones%to%WSC%• WSC%SW%must%cope%with%failures,%varying%load,%varying%HW%latency%bandwidth%• WSC%HW%sensiVve%to%cost,%energy%efficiency%2%Spring%2011%MM%Lecture%#1%1/20/11%NewMSchool%Machine%Structures%(It’s%a%bit%more%complicated!)%• Parallel%Requests%Assigned%to%computer%e.g.,%Search%“Katz”%• Parallel%Threads%Assigned%to%core%e.g.,%Lookup,%Ads%• Parallel%InstrucVons%>1%instrucVon%@%one%Vme%e.g.,%5%pipelined%instrucVons%• Parallel%Data%>1%data%item%@%one%Vme%e.g.,%Add%of%4%pairs%of%words%• Hardware%descripVons%All%gates%@%one%Vme%1/20/11% Spring%2011%MM%Lecture%#1% 3%Smart%Phone%Warehouse%Scale%Computer%So#ware((((((((Hardware(Harness(Parallelism(&(Achieve(High(Performance(Logic%Gates%Core% Core%…%%%%%%Memory%%%%%%%%%%%%%%%(Cache)%Input/Output%Computer%Main%Memory%Core%%%%%%%%%%InstrucVon%Unit(s)%%%%%%%%FuncVonal%Unit(s)%A3+B3%A2+B2%A1+B1%A0+B0%Today’s%Lecture%Agenda%• Request%and%Data%Level%Paral lel ism%• Administrivia%+%61C%in%the%News%+%Internship%Workshop%+%The%secret%to%gejng%good%grades%at%Berkeley%• MapReduce%• MapReduce%Examples%• Technology%Break%• Costs%%in%Warehouse%Scale%Computer%(if%Vme%permits)%1/20/11% Apeinf%2011%MM%Lecture%#2% 4%RequestMLevel%Parallelism%(RLP)%• Hundreds%or%thousands%of%requests%per%second%– Not%your%laptop%or%cellMphone,%but%popular%Internet%services%like%Google%search%– Such%requests%are%largely%independent%• Mostly%involve%readMonly%databases%• LiGle%readMwrite%(aka%“producerMconsumer”)%sharing%• Rarely%involve%read–write%data%sharing%or%synchronizaVon%across%requests%• ComputaVon%easily%parVVoned%within%a%request%and%across%different%requests%1/20/11% Apeinf%2011%MM%Lecture%#2% 5%Google%QueryMServing%Architecture%1/20/11% Apeinf%2011%MM%Lecture%#2% 6%1/20/11%2%Anatomy%of%a%Web%Search%• Google%“Randy%H.%Katz”%– Direct%request%to%“closest”%Google%Warehouse%Scale%Computer%– FrontMend%load%balancer%directs%request%to%one%of%many%arrays%(cluster%of%servers)%within%WSC%– Within%array,%select%one%of%many%Google%Web%Servers%(GWS)%to%handle%the%request%and%compose%the%response%pages%– GWS%communicates%with%Index%Servers%to%find%documents%that%contain%the%search%words,%“Randy”,%“Katz”,%uses%locaVon%of%search%as%well%– Return%document%list%with%associated%relevance%score%1/20/11% Apeinf%2011%MM%Lecture%#2% 7%Anatomy%of%a%Web%Search%• In%parallel,%– Ad%system:%books%by%Katz%at%Amazon.com%– Images%of%Randy%Katz%• Use%docids%(document%IDs)%to%access%indexed%documents%%• Compose%the%page%– Result%document%extracts%(with%keyword%in%context)%ordered%by%relevance%score%– Sponsored%links%(along%the%top)%and%adverVsements%(along%the%sides)%1/20/11% Apeinf%2011%MM%Lecture%#2% 8%1/20/11% Apeinf%2011%MM%Lecture%#2% 9%Anatomy%of%a%Web%Search%• ImplementaVon%strategy%– Randomly%distribute%the%entries%– Make%many%copies%of%data%(aka%“replicas”)%– Load%balance%requests%across%replicas%• Redundant%copies%of%indices%and%documents%– Breaks%up%hot%spots,%e.g.,%“JusVn%Bieber”%– Increases%opportuniVes%for%requestMlevel%parallelism%– Makes%the%system%more%tolerant%of%failures%1/20/11% Apeinf%2011%MM%Lecture%#2% 10%DataMLevel%Parallelism%(DLP)%• 2%kinds%– Lots%of%data%in%memory%that%can%be%operated%%on%in%parallel%(e.g.,%adding%together%2%arrays)%– Lots%of%data%on%many%disks%that%can%be%operated%on%in%parallel%(e.g.,%searching%for%documents)%• March%1%lecture%and%3rd%project%does%Data%Level%Parallelism%(DLP)%in%memory%• Today’s%lecture%and%1st%project%does%DLP%across%1000s%of%servers%and%disks%using%MapReduce%1/20/11% Apeinf%2011%MM%Lecture%#2% 11%Problem%Trying%To%Solve%• How%process%large%amounts%of%raw%data%(crawled%documents,%request%logs,%…)%every%day%to%compute%derived%data%(inverted%indicies,%page%popularity,%…)%when%computaVon%conceptually%simple%but%input%data%large%and%distributed%across%100s%to%1000s%of%servers%so%that%finish%in%reasonable%Vme?%• Challenge:%Parallelize%computaVon,%distribute%data,%tolerate%faults%without%obscuring%simple%computaVon%with%complex%code%to%deal%with%issues%• Jeffrey%Dean%and%Sanjay%Ghemawat,%“MapReduce:%Simplified%Data%Processing%on%Large%Clusters,”%Communica:ons(of(the(ACM,%Jan%2008.%%1/20/11% Apeinf%2011%MM%Lecture%#2% 12%1/20/11%3%MapReduce%SoluVon%• Apply%Map%funcVon%to%user%supplier%record%of%key/value%pairs%• Compute%set%of%intermediate%key/value%pairs%• Apply%Reduce%operaVon%to%all%values%that%share%same%key%in%order%to%combine%derived%data%properly%• User%supplies%Map%and%Reduce%operaVons%in%funcVonal%model%so%can%parallelize,%using%reMexecuVon%for%fault%tolerance%1/20/11% Apeinf%2011%MM%Lecture%#2% 13%DataMParallel%“Divide%and%Conquer”%(MapReduce%Pro cessing)%• Map:%– Slice%data%into%“shards”%or%“splits”,%distribute%these%to%workers,%compute%subMproblem%soluVons%– map(in_key,in_value)->list(out_key,intermediate value)!• Processes%input%key/value%pair%• Produces%set%of%intermediate%pairs%• Reduce:%– Collect%and%combine%subMproblem%soluVons%– reduce(out_key,list(intermediate_value))->list(out_value)!• Combines%all%intermediate%values%for%a%parVcular%key%• Produces%a%set%of%merged%output%values%(usually%just%one)%• Fun%to%use:%focus%on%problem,%let%MapReduce%library%deal%with%messy%details%1/20/11% Apeinf%2011%MM%Lecture%#2% 14%MapReduce%ExecuVon%1/20/11% Apeinf%2011%MM%Lecture%#2% 15%Fine%granularity%tasks:%many%more%map%tasks%than%machines%2000%servers%=>%%≈%200,000%Map%Tasks,%≈%5,000%Reduce%tasks%MapReduce%Popularity%at%Google%Aug-04 Mar-06 Sep-07 Sep-09 Number of MapReduce jobs 29,000 171,000 2,217,000 3,467,000 Average completion time (secs) 634 874 395 475
View Full Document