Big Data Analytics Big Data Analytics C. Distributed Computing Emvironments / C.1 Map Reduce Lars Schmidt-Thieme Information Systems and Machine Learning Lab (ISMLL) Institute for Computer Science University of Hildesheim, Germany Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 1 / 32
Big Data Analytics Syllabus Tue. 9.4. (1) 0. Introduction A. Parallel Computing Tue. 16.4. (2) A.1 Threads Tue. 23.4. (3) A.2 Message Passing Interface (MPI) Tue. 30.4. (4) A.3 Graphical Processing Units (GPUs) B. Distributed Storage Tue. 7.5. (5) B.1 Distributed File Systems Tue. 14.5. (6) B.2 Partioning of Relational Databases Tue. 21.5. (7) B.3 NoSQL Databases C. Distributed Computing Environments Tue. 28.5. (8) C.1 Map-Reduce Tue. 4.6. — — Pentecoste Break — Tue. 11.6. (9) C.2 Resilient Distributed Datasets (Spark) Tue. 18.6. (10) C.3 Computational Graphs (TensorFlow) D. Distributed Machine Learning Algorithms Tue. 25.6. (11) D.1 Distributed Stochastic Gradient Descent Tue. 2.7. (12) D.2 Distributed Matrix Factorization Tue. 9.7. (13) Questions and Answers Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 1 / 32
Big Data Analytics Outline 1. Introduction 2. Parallel Computing Speedup 3. Example: Counting Words 4. Map-Reduce Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 1 / 32
Big Data Analytics 1. Introduction Outline 1. Introduction 2. Parallel Computing Speedup 3. Example: Counting Words 4. Map-Reduce Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 1 / 32
Big Data Analytics 1. Introduction Technology Stack Part D Distributed Machine Learning Algorithms Part C Distributed Execution Environments Part B Distributed Storage Part A Parallel/Distributed Computing Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 1 / 32
Big Data Analytics 1. Introduction Why do we need a Computational Model? I Our data is nicely stored in a distributed infrastructure I We have a number of computers at our disposal I We want our analytics software to take advantage of all this computing power I When programming we want to focus on understanding our data and not our infrastructure Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 2 / 32
Big Data Analytics 1. Introduction Shared Memory Infrastructure Processor Processor Processor Memory Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 3 / 32
Big Data Analytics 1. Introduction Distributed Infrastructure Network Processor Processor Processor Processor Memory Memory Memory Memory Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 4 / 32
Big Data Analytics 2. Parallel Computing Speedup Outline 1. Introduction 2. Parallel Computing Speedup 3. Example: Counting Words 4. Map-Reduce Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 5 / 32
Big Data Analytics 2. Parallel Computing Speedup Parallel Computing / Speedup I We have p processors available to execute a task T I Ideally: the more processors the faster a task is executed I Reality: synchronisation and communication costs I Speedup s(T,p) of a task T by using p processors: I Be t(T,p) the time needed to execute T using p processors I Speedup is given by: t(T,1) s(T,p) = t(T,p) Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 5 / 32
Big Data Analytics 2. Parallel Computing Speedup Parallel Computing / Efficiency I We have p processors available to execute a task T I Efficiency e(T,p) of a task T by using p processors: t(T,1) e(T,p) = p · t(T,p) Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 6 / 32
Big Data Analytics 2. Parallel Computing Speedup Considerations I It is not worth using a lot of processors for solving small problems I Algorithms should increase efficiency with problem size Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 7 / 32
Big Data Analytics 3. Example: Counting Words Outline 1. Introduction 2. Parallel Computing Speedup 3. Example: Counting Words 4. Map-Reduce Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 8 / 32
Big Data Analytics 3. Example: Counting Words Word Count Example I Given a corpus of text documents D := {d1, . . . ,dn} each containing a sequence of words: (w1, . . . ,wm) from a set W of possible words. I the task is to generate word counts for each word in the corpus Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 8 / 32
Big Data Analytics 3. Example: Counting Words Paradigms — Shared Memory I All the processors have access to all counters I Counters can be overwritten I Processors need to lock counters before using them Shared vector for word counts: c ∈ N|W| c ← {0}|W| Each processor: 1. access a document d ∈ D 2. for each word w in document d: 2.1 lock(cw ) 2.2 cw ← cw + 1 2.3 unlock(cw ) Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 9 / 32
Big Data Analytics 3. Example: Counting Words Paradigms — Shared Memory I inefficient due to waiting times for the locks I the more processors, the less efficient I in a distributed scenario even worse due to communication overhead for acquiring/releasing the locks Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 10 / 32
Big Data Analytics 3. Example: Counting Words Paradigms — Message passing I Each processor sees only one part of the data π(D,p) := {dp n , . . . ,d(p+1) n −1} P P I Each processor works on its partition I Results are exchanged between processors (message passing) For each processor p: 1. For each d ∈ π(D,p) 1.1 process(d) 2. Communicate results Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 11 / 32
Big Data Analytics 3. Example: Counting Words Word Count — Message passing We need to define two types of processes: 1. slave I counts the words on a subset of documents and informs the master 2. master I gathers counts from the slaves and sums them up Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 12 / 32
Big Data Analytics 3. Example: Counting Words Word Count — Message passing Slave: Local memory: subset of documents: π(D,p) := {dp n , . . . ,d(p+1) n −1} P P address of the master: addr_master local word counts: c ∈ R|W| 1. c ← {0}|W| 2. for each document d ∈ π(D,p) for each word w in document d: cw ← cw + 1 3. Send message send(addr_master,c) Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 13 / 32
Big Data Analytics 3. Example: Counting Words Word Count — Message passing Master: Local memory: 1. Global word counts: cglobal ∈ R|W| 2. List of slaves: S cglobal ← {0}|W| s ← {0}|S| For each received message (p,cp) 1. cglobal ← cglobal + cp 2. sp ← 1 3. if ||s|| = |S| return cglobal 1 Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 14 / 32
Affichage des 20 premières pages. Téléchargez le document pour le voir en entier.
Aucun commentaire pour le moment. Soyez le premier !
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !