> For the complete documentation index, see [llms.txt](https://ztlevi.gitbook.io/ml-101/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ztlevi.gitbook.io/ml-101/parallel-computing/sync_mapreduce.md).

# MapReduce

[Slides](https://github.com/wangshusen/DeepLearning/blob/master/Slides/14_Parallel_1.pdf) [Youtube](https://www.youtube.com/watch?v=gVcnOe6_c6Q\&list=PLvOO0btloRns6egXueiRju4DXQjNRJQd5)

## MapReduce

* MapReduce is a programming model and software system developed by Google .
* Characters: client-server architecture, message-passing communication, and bulk synchronous parallel.
* Apache Hadoop is an open-source implementation of MapReduce.
* Apache Spark is an improved open-source MapReduce.

### Broadcast

![mapreduce-1](https://637078585-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MYsi-h_n0zY_8MKKgyu%2Fuploads%2Fgit-blob-4321fc463d10af305366a93019160f7b948370ed%2Fmapreduce-1.png?alt=media)

### Map

![mapreduce-2](https://637078585-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MYsi-h_n0zY_8MKKgyu%2Fuploads%2Fgit-blob-48826be490121fac9cbb0cb07c5746c6a4451652%2Fmapreduce-2.png?alt=media)

### Reduce

![mapreduce-3](https://637078585-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MYsi-h_n0zY_8MKKgyu%2Fuploads%2Fgit-blob-18125a0afc7769e7693b04f7fafedc1808bffdd7%2Fmapreduce-3.png?alt=media)

## Data Parallelism

Partition the data among worker nodes. (A node has a subset of data.)

![data\_parallelism\_1](https://637078585-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MYsi-h_n0zY_8MKKgyu%2Fuploads%2Fgit-blob-c912bac8d58671c7070ddb5ea90e8243eadf577d%2Fdata_parallelism_1.png?alt=media)

## Parallel Gradient Descent Using MapReduce

* Broadcast: Server broadcast the up-to-date parameters $$w\_t$$ o workers.
* Map: Workers do computation locally.
  * Map $$(x\_i,y\_i,w\_t)$$ to $$g\_i=(x\_i^T w\_t-yi)x\_i$$.
  * Obtain $$n$$ vectors: $$g\_1, g\_2,g\_3,...,g\_n$$
* Reduce: Compute the sum: $$g=\sum\_{i=1}^{n}g\_i$$
* Every worker sums all the $${g\_i}$$ stored in its local memory to get a vector.
* Then, the server sums the resulting m vectors. (There are m workers.)
* Server updates the parameters: $$w\_{t+1}=t\_t-\alpha \cdot g$$

![Parallel\_Gradient\_Descent\_Using\_MapReduce\_1](https://637078585-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MYsi-h_n0zY_8MKKgyu%2Fuploads%2Fgit-blob-82cad251f6bb4f4d0c8c54ff8851881390e9abab%2FParallel_Gradient_Descent_Using_MapReduce_1.png?alt=media)

## Speedup Ratio

![speedup\_ratio\_1](https://637078585-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MYsi-h_n0zY_8MKKgyu%2Fuploads%2Fgit-blob-62c3126f7d7ab02b015a531e366d55331e753a12%2Fspeedup_ratio_1.png?alt=media)

## Communication Cost

* Communication complexity: How many words are transmitted between server and workers.
  * Proportional to number of parameters.
  * Grow with number of worker nodes.
* Latency: How much time it takes for a packet of data to get from one point to another. (Determined by the compute network.)
* Communication time: $$\frac{comlexity}{bancwith}+latency$$

## Bulk Synchronous

![Bulk\_Synchronous\_1](https://637078585-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MYsi-h_n0zY_8MKKgyu%2Fuploads%2Fgit-blob-01857c290bdaf45aec9f764fa8c4c1404550ce16%2FBulk_Synchronous_1.png?alt=media)

## Synchronization Cost

Question: What if a node fails and then restart?

* This node will be much slower than all the others.
* It is called straggler.
* Straggler effect:
  * The wall-clock time is determined by the slowest node.
  * It is a consequence of synchronization.

## Footnote