《google云计算解决方案1_ 分布式系统概述》由会员分享，可在线阅读，更多相关《google云计算解决方案1_ 分布式系统概述（93页珍藏版）》请在金锄头文库上搜索。
1、Google Cluster Computing Faculty Training Workshop Module I: Introduction to MapReduce Spinnaker Labs, Inc. Workshop Syllabus Seven lecture modules Information about teaching the course Technical info about Google tools design parallel solutions Manage large data sets under memory, bandwidth limitat
2、ions Develop a foundation in parallel algorithms for large-scale data Identify and understand engineering trade- offs in real systems Spinnaker Labs, Inc. Lectures 2 hours, once per week Half formal lecture, half discussion Mostly covered systems Lord of the Rings New Line Cinema Spinnaker Labs, Inc
3、. Distributed Problems Indexing the web (Google) Simulating an Internet-sized network for networking experiments (PlanetLab) Speeding up content delivery (Akamai) What is the key attribute that all these examples have in common? Spinnaker Labs, Inc. Distributed Problems All involve separable computa
4、tion Many involve data that necessarily must be stored in multiple locations. For a problem to be distributable, different components of the problem should be able to be handled independently. Spinnaker Labs, Inc. Taking A Step Back Before we talk more about distributed computing what does it mean t
5、o design “a computer?” How would a distributed or parallel system look different from a single-CPU machine? Spinnaker Labs, Inc. Flynns Taxonomy Four categories of computer architectures Broke down serial/parallel in terms of instructions and data Spinnaker Labs, Inc. SISD Single instruction, single
6、 data element Spinnaker Labs, Inc. MIMD Multiple instructions, multiple data elements Spinnaker Labs, Inc. Models of Computing The Von Neumann architecture a.k.a. RAM model How do we extend this to parallel computing? Spinnaker Labs, Inc. A First Try: PRAM Parallel Random Access Machine model: N pro
7、cessors connected to shared memory All memory addresses reachable in unit time by any CPU All processors execute one instruction per tick in “lock step” Spinnaker Labs, Inc. Does not even cover Core2Duo Although there were some early attempts Spinnaker Labs, Inc. Early Parallel Computing CDC 6600: O
8、ut-of-order execution (1964) CDC 7600: Pipelining CDC 8600: Multi-core! 4 7600s in one box Provided lock-step execution of CPUs NB: Memory speed at the time exceeded CPU speed Also never actually made it to production Spinnaker Labs, Inc. Vector Processing Cray 1 (1976) allowed programmers to apply
9、operations to large chunks of data at a time SIMD architecture: Single instruction, multiple data Spinnaker Labs, Inc. Loop Compilation for (i = 0; i N; i+) ai = bi + ci; top: compare i, N jge exit load_offset $1, b, i load_offset $2, c, i add $3, $1, $2 store_offset $3, a, i inc i j top exit: Spinn
10、aker Labs, Inc. Vector Compilation for (i = 0; i N; i+) ai = bi + ci; load_vector $1, b, N load_vector $2, c, N add $3, $1, $2 store_vector $3, a, N Spinnaker Labs, Inc. Vector Memory Operations Spinnaker Labs, Inc. 1975-85 Parallel computing was favored in the early years Primarily vector-based at
11、first Gradually more thread- based parallelism was introduced Cray 2 supercomputer (Wikipedia) Spinnaker Labs, Inc. System Organization Having one big memory would make it a huge bottleneck Eliminates all of the parallelism The PRAM model does not work Lock-step execution too restrictive Does not ac
12、curately model memory Spinnaker Labs, Inc. CTA: Memory is Distributed Spinnaker Labs, Inc. Interconnect Networks Bottleneck in the CTA is transferring values from one local memory to another Interconnect network design very important; several options are available Design constraint: How to minimize
13、interconnect network usage? Spinnaker Labs, Inc. “Massively parallel architectures” start rising in prominence Message Passing Interface (MPI) and other libraries developed Bandwidth was a big problem For external interconnect networks in particular A Brief History 1985-95 Spinnaker Labs, Inc. A Bri
14、ef History 1995-Today Cluster/grid architecture increasingly dominant Special node machines eschewed in favor of COTS technologies Web-wide cluster software Companies like Google take this to the extreme (10,000 node clusters) Spinnaker Labs, Inc. More About Interconnects Several types of interconne
15、ct possible Bus Crossbar Torus Tree Spinnaker Labs, Inc. Interconnect Bus Simplest possible layout Not realistically practical Too much contention Little better than “one big memory” Spinnaker Labs, Inc. Crossbar All processors have “input” and “output” lines Crossbar connects any input to any output Allows for very low contention, but lots of wires, complexity Will not scale to many nodes Spinnaker Labs, Inc. Toroidal networks Nodes are connected to their logical neighbors Node-node transfer may include intermediaries Reasonable
