1 20 11 Review CS61c Learn 5 great ideas in computer architecture to enable high performance programming via parallelism not just learn C CS 61C Great Ideas in Computer Architecture Machine Structures 1 2 3 4 5 6 Instructors Randy H Katz David A PaGerson hGp inst eecs Berkeley edu cs61c sp11 1 20 11 Apeinf 2011 Lecture 2 1 Post PC Era Parallel processing smart phones to WSC WSC SW must cope with failures varying load varying HW latency bandwidth 1 20 11 WSC HW sensiVve to Spring cost energy e ciency 2011 Lecture 1 2 New School Machine Structures It s a bit more complicated Today s Lecture Agenda So ware Hardware Parallel Requests Assigned to computer e g Search Katz Parallel Threads Assigned to core e g Lookup Ads Smart Phone Warehouse Scale Computer Harness Parallelism Achieve High Performance Computer 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 Core Core Memory Cache Input Output InstrucVon Unit s Layers of RepresentaVon InterpretaVon Moore s Law Principle of Locality Memory Hierarchy Parallelism Performance Measurement and Improvement Dependability via Redundancy Core FuncVonal Unit s A0 B0 A1 B1 A2 B2 A3 B3 Main Memory Request and Data Level Parallelism 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 Logic Gates Spring 2011 Lecture 1 3 Request Level Parallelism RLP 1 20 11 Apeinf 2011 Lecture 2 4 Google Query Serving Architecture Hundreds or thousands of requests per second Not your laptop or cell phone but popular Internet services like Google search Such requests are largely independent Mostly involve read only databases LiGle read write aka producer consumer sharing Rarely involve read write data sharing or synchronizaVon across requests ComputaVon easily parVVoned within a request and across di erent requests 1 20 11 Apeinf 2011 Lecture 2 5 1 20 11 Apeinf 2011 Lecture 2 6 1 1 20 11 Anatomy of a Web Search Anatomy of a Web Search Google Randy H Katz In parallel Direct request to closest Google Warehouse Scale Computer Front end 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 nd 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 Lecture 2 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 7 1 20 11 Apeinf 2011 Lecture 2 8 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 request level parallelism Makes the system more tolerant of failures 1 20 11 Apeinf 2011 Lecture 2 9 1 20 11 Data Level Parallelism DLP 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 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 nish in reasonable Vme Challenge Parallelize computaVon distribute data tolerate faults without obscuring simple computaVon with complex code to deal with issues Apeinf 2011 Lecture 2 10 Problem Trying To Solve 2 kinds 1 20 11 Apeinf 2011 Lecture 2 11 Je rey Dean and Sanjay Ghemawat MapReduce Simpli ed Data Processing on Large Clusters Communica ons of the ACM Jan 2008 1 20 11 Apeinf 2011 Lecture 2 12 2 1 20 11 Data Parallel Divide and Conquer MapReduce Processing 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 re execuVon for fault tolerance Map 1 20 11 1 20 11 Apeinf 2011 Lecture 2 13 Slice data into shards or splits distribute these to workers compute sub problem 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 sub problem 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 Fine granularity tasks many more map tasks than machines Number of MapReduce jobs Average completion time secs Server years used Input data read TB Intermediate data TB Output data written TB Average number servers job 2000 servers 200 000 Map Tasks 5 000 Reduce tasks Apeinf 2011 Lecture 2 15 ExtracVng the set of outgoing links from a collecVon of HTML documents and aggregaVng by target document SVtching together overlapping satellite images to remove seams and to select high quality imagery for Google Earth GeneraVng a collecVon of inverted index les using a compression scheme tuned for e cient support of Google search queries Processing all road segments in the world and rendering map Vle images that display these segments for Google Maps Fault tolerant parallel execuVon of programs wriGen in higher level languages across a collecVon of input data More than 10 000 MR programs at Google in 4 years Apeinf 2011 Lecture 2 1 20 11 Aug 04 Mar 06 Sep 07 Sep 09 29 000 171 000 2 217 000 3 467 000 634 217 3 288 758 874 2 002 52 254 6 743 395 11 081 403 152 34 774 475 25 562 544 130 90 120 193 2 970 14 018 57 520 157 268 394 488 Apeinf 2011 Lecture 2 16 What if Ran Google Workload on EC2 Google Uses MapReduce
View Full Document
Unlocking...