Algorithms and computations for big data

Question 1

The four parallel paradigms

Answer 1

1. Multithreading
2. Message parsint interface (MPI)
3. Map-Reduce
4. Spark

Question 2

Learning outcomes

Answer 2

• Knowledge and understanding
  
  • discuss important technological aspects when designing and implementing analysis solutions for large-scale data,
  • describe data models and software standards for sharing data on the web.
• Skills and abilities
  
  • use Python to implement applications for transforming and analyzing large-scale data with appropriate software frameworks,
  • provide access and utilize structured data over the web with appropriate data models and software tools
• Judgement and approach
  
  • suggest appropriate computational infrastructures for analysis tasks and discuss their advantages and drawbacks,
  • discuss advantages and drawbacks of different strategies for dissemination of data,
  • discuss large-scale data processing from an ethical point of view.

Question 3

Levels of parallelism

Answer 3

• Multi-core CPU’s
• Several CPU’s per system
• Clusters of multiple systems

Question 4

Speedup

Answer 4

Given two variants of a program solving the same problem- a baseline, and a optimzed implementation, faster algorithm, or parallel version- with running times t and t’ (optimized time).

S = t/t’

Question 5

Amdahl’s law

Answer 5

• Propostion of the code that is parallizable

S(f,s) = 1/((1-f)+f/s)

as S goes to infinity then 1/(1-f)

• No, only some programs benefit from parallelization and their maximal acceleration is bounded.

Question 6

Multicore CPU are technical necessity ?

Answer 6

Yes. Cooling is a bottleneck when increasing clock frequency of a CPU

Question 7

Flynn’s taxonomy

Answer 7

• SIMD: GPU
• MIMD: Multi-core processors

Question 8

Memory hierarchy

Answer 8

Question 9

cache memory

Answer 9

Small hi-speed memory attached to processor core

Question 10

Symmetric Multiprocessor (SMP)

Answer 10

• Multiple CPU’s (typically 2-8; each can have multiple cores) share the same main memory
• One adress space

Question 11

High performance computing (HPC)

Answer 11

Question 12

Classical HPC compute cluster is an appropriate computer architecture for Monte Carlo simulations like the parallel Pi example. Assume that the parallelization across nodes is not a problem.

Answer 12

Yes, HPC is a good computer architecture for Monto carlo simulations.

Question 13

Difference between HPC and commodity

Answer 13

Question 14

Distributed compute cluster (commodity hardware)

Answer 14

Question 15

Workload comparison between HPC and Datascience

Answer 15

Question 16

Data-intensive Compute Cluster

Answer 16

Question 17

Latency vs computation

Answer 17

Computation is cheap, datamovement is very expensive

Question 18

Multithreading

Answer 18

• Threads communicate via variables in shared memory
• Simultaenous read acess to data
• Write access to same data require lock

Question 19

In multi-threaded programming the time needed to communicate between two threads is typically on the order of

Answer 19

200ns

Question 20

In multithreaded- programming all threads can simultenously….

Answer 20

…read nd write, but not the same data

Question 21

Threads writing to memory incorrectly

Answer 21

Question 22

Threds writing to memory correctly

Answer 22

Question 23

Locking

Answer 23

• Protects from errors due to parallel writes
• Lock
  
  • is acquired before reading/writing data
  • is released when done
  • assures serial access to shared mem

Question 24

Deadlocks

Answer 24

• Execution stops because 2 or more threads wait for each other
• Two threads need to write variables a & b
  
  • Thread 1 locks a and waits for b
  • Thread 2 locks b and waits for a

Question 25

Questions to ask when parallelizing

Answer 25

* Which sections can be parallelized? * What needs to be serial? * When is communication necessary between the thread? * How much data needs to becommunicated?

Question 26

*Load balancing*

Answer 26

Distributing the workload **equally** amongst the threads

Question 27

Message parsing interface (MPI)

Answer 27

* The message passing interface (MPI) is a standardized means of exchanging messages between multiple computers running a parallel program across distributed memory. * Used for high performance computing * Usually on super computers * Substantial latencies for thousands of cores * Lower throughput for sharing large amount of data * Communication incl. exchange of data via highspeed network (5000ns + 2x RAM acess)

Question 28

Passing a message over Infiniband takes about 5000 ns. This is how many times slower than a memory access?

Answer 28

11-50 times slower

Question 29

Word count and Cahracter count Map-Reduce

Answer 29

Question 30

*Combiners*

Answer 30

* Semi reduce * Word count * Each combiner adds up n/k values * Each reduces gets k values to add up * *n* amount of inputs * *k* amount of nodes * Use combiners to utiilize more cores

Question 31

*Map-reduce*

Answer 31

* Two parallel phases 1. Map: Map each input with a value and a key 2. Reduce: For each key collect its respective values and aggregate * Shuffle process after the *mapping* phase and before reduce phase * Mainly used for **one-pass jobs** (data sample only seen once) * Theoretical speed up for mapper is amount of inputs * The speed up for mapper is the amount of keys * Practical speed is up is amount of nodes

Question 32

Multi step in MRjob

Answer 32

* i.e using another reducer to find the most frequent item

Question 33

Why cannot two reducers communicate ?

Answer 33

* Run on different machines * Not available at the same time

Question 34

Spark

Answer 34

* general-purpose cluster-computing framework * computer clusters have each node set to perform the same task, controlled and scheduled by software. * Uses Resilient distributed dataset (RDD) * Fault tolerant: RDD can always be re-constructed if it fails * Obtained from drive program (python script) read from HDFS or other * Good for Iterative jobs: Many common machine learning algo- rithms apply a function repeatedly to the same dataset to optimize a parameter

Question 35

In case of a disk or hardware failure on one node, when using frameworks like Hadoop (MapReduce) or Spark with data on a HDFS file system, computations

Answer 35

only results for failingnode haveto be recomputed

Question 36

Answer 36

Question 37

Frequent keys spakr program

Answer 37

Question 38

Hadoop distributed file system (HDFS)

Answer 38

* software framework for distributed storage and processing of big data using the MapReduce programming model. * Namenode is aware of distribution of chunks and distributed map-reduce jobs accordingly * Computations are performed where data is stored * Failure of a node or even a rack can be compensated without invalidating previous computations

Question 39

Trie (prefix tree)

Answer 39

Question 40

Bloom filter

Answer 40

* A bloom filter is a data structure designed to tell you, rapidly and memory-efficientlywhether an element is present in a set. The paid trade off for this effeciency is that a bloomfilter is probabillistic * Operations: * Insert item x into Bloom filter B * Query: x present in B * If x present in B, the query will always be answered correctly * With probability p, the query might be answered positively even if x is not present in B.

Question 41

Describe how bloom filter works

Answer 41

Question 42

Trie and parallization

Answer 42

Question 43

Bloom filter: Cache Behaviour For sufficiently large b, accessing each bit will likely cause a cache miss. The expected number of cache misses for insert and query operations, when the item is not in the Bloom filter is the same.

Answer 43

* Cache miss is a state where the data requested for processing by a component or application is not found in the cache memory. * Insert * worst case: *n* cache misses per insert * Query * item present / false positve: like insert * item **not** present: average much lower than worst case

Question 44

Describe how the error in a bloom filter

Answer 44

* False positives (positive class is if the element is in the bloom filter) * A false positive occurs if the other elements set the specific bits

Question 45

Parallization of *Bloom filter*

Answer 45

Question 46

Data analysis on large texts

Answer 46

* Text T: * Natural language * Biological sequences, any other sequence of discrete observations * Error or event logs (error codes/event types = alphabet) * Questions: * Is s a substring of T? * How often appears s in T? * Suffix tree * • Use tree-traversal to populate leaf-counts for all internal nodes (once!)

Question 47

Spark optimization strategy

Answer 47

• Transformations are **lazy** • Only Actions trigger computations • Spark maintains directed acyclic graphs to represent workflow • Scheduler assign computational tasks to workers optimizing compute-data co- location

Question 48

Spark Architecture

Answer 48

Question 49

Count min sketch

Answer 49

an efficient algo-rithm for counting stream of data. It uses hash functions to map events to fre-quencies but unlike a hash table uses lessspace, at the expense of over countingsome events due to collisions

Question 50

*Resilient distributed dataset* (RDD)

Answer 50

* Fault tolerant * RDD can always be reconstructed if a node fails * Two operations on RDD * transformations: create new RDD from input * action: produce output

Question 51

Multi processing queue

Answer 51

* Once a thread is done wiht its work it can access more work from the queue